Linear time dynamic programming for computing breakpoints in the regularization path of models selected from a finite set

Many learning algorithms are formulated in terms of finding model parameters which minimize a data-fitting loss function plus a regularizer. When the regularizer involves the ℓ0 pseudo-norm, the resulting regularization path consists of a finite set of models. The fastest existing algorithm for computing the breakpoints in the regularization path is quadratic in the number of models, so it scales poorly to high dimensional problems. We provide new formal proofs that a dynamic programming algorithm can be used to compute the breakpoints in linear time. Our empirical results include analysis of the proposed algorithm in the context of various learning problems (regression, changepoint detection, clustering, matrix factorization). We use a detailed analysis of changepoint detection problems to demonstrate the improved accuracy and speed of our approach relative to grid search and a previous quadratic time algorithm.

众多学习算法均以寻找能够最小化数据拟合损失函数及正则化项的模型参数为基本形式。当正则化项涉及ℓ0伪范数时，所得到的正则化路径由一系列有限模型构成。目前计算正则化路径中断点的最快算法在模型数量上呈现二次方增长，因此对于高维问题扩展性较差。本研究提供了新的形式化证明，证明了动态规划算法能够以线性时间计算断点。我们的实证研究包括对所提算法在各种学习问题（回归、变化点检测、聚类、矩阵分解）中的应用分析。通过详细分析变化点检测问题，我们展示了与网格搜索及之前的二次方时间算法相比，本方法在准确性和速度方面的提升。