B0291
Title: A new perspective on boosting in linear regression via subgradient optimization and relatives
Authors: Robert Freund - MIT (United States) [presenting]
Paul Grigas - MIT (United States)
Rahul Mazumder - Columbia University (United States)
Abstract: The aim is to analyze boosting algorithms in linear regression from the perspective modern first-order methods in convex optimization. We show that classical boosting algorithms in linear regression, namely the incremental forward stagewise algorithm (FSe) and least squares boosting (LS-Boost-e), can be viewed as subgradient descent to minimize the loss function defined as the maximum absolute correlation between the features and residuals. We also propose a modification of FSe that yields an algorithm for the LASSO, and that may be easily extended to an algorithm that computes the LASSO path. These new algorithms for the LASSO may also be interpreted as the same master algorithm (subgradient descent), applied to a regularized version of the maximum absolute correlation loss function. We derive novel, comprehensive computational guarantees for several boosting algorithms in linear regression (including LS-Boost-e and FSe), which inform us about the statistical properties of boosting algorithms. In particular they provide, for the first time, a precise theoretical description of the amount of data-fidelity and regularization imparted by running a boosting algorithm with a pre-specified learning rate for a fixed but arbitrary number of iterations, for any dataset.
