2015/05/16 by Robert M. Freund, Freund, Robert M., Paul Grigas +3
Engineering · Mathematics · Decision Sciences · #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Multi-Criteria Decision Making
paper · pdf · doi:10.48550/arxiv.1505.04243
In this paper we analyze boosting algorithms in linear regression from a new\nperspective: that of modern first-order methods in convex optimization. We show\nthat classic boosting algorithms in linear regression, namely the incremental\nforward stagewise algorithm (FS_\ε) and least squares boosting\n(LS-Boost(\ε)), can be viewed as subgradient descent to minimize the\nloss function defined as the maximum absolute correlation between the features\nand residuals. We also propose a modification of FS_\ε that yields\nan algorithm for the Lasso, and that may be easily extended to an algorithm\nthat computes the Lasso path for different values of the regularization\nparameter. Furthermore, we show that these new algorithms for the Lasso may\nalso be interpreted as the same master algorithm (subgradient descent), applied\nto a regularized version of the maximum absolute correlation loss function. We\nderive novel, comprehensive computational guarantees for several boosting\nalgorithms in linear regression (including LS-Boost(\ε) and\nFS_\ε) by using techniques of modern first-order methods in convex\noptimization. Our computational guarantees inform us about the statistical\nproperties of boosting algorithms. In particular they provide, for the first\ntime, a precise theoretical description of the amount of data-fidelity and\nregularization imparted by running a boosting algorithm with a prespecified\nlearning rate for a fixed but arbitrary number of iterations, for any dataset.\n