Linear time dynamic programming for the exact path of optimal models selected from a finite set
This provides a faster method for model selection in high-dimensional problems, but it is incremental as it builds on existing dynamic programming ideas with new proofs and empirical validation.
The paper tackled the problem of efficiently computing breakpoints in regularization paths for models with l0 pseudo-norm regularizers, which previously had quadratic time complexity, and demonstrated that a dynamic programming algorithm achieves linear time with improved accuracy and speed in changepoint detection tasks.
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 l0 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. Empirical results on changepoint detection problems demonstrate the improved accuracy and speed relative to grid search and the previous quadratic time algorithm.