Optimization Online


A New Perspective on Boosting in Linear Regression via Subgradient Optimization and Relatives

Robert M. Freund(rfreund***at***mit.edu)
Paul Grigas(pgrias***at***mit.edu)
Rahul Mazumder(rahul.mazumder***at***gmail.com)

Abstract: In this paper we analyze boosting algorithms in linear regression from a new perspective: that of modern first-order methods in convex optimization. We show that classic boosting algorithms in linear regression, namely the incremental forward stagewise algorithm (FS-epsilon) and least squares boosting (LS-Boost-epsilon), 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 FS-epsilon that yields an algorithm for the LASSO, and that may be easily extended to an algorithm that computes the LASSO path for different values of the regularization parameter. Furthermore, we show that 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-epsilon and FS-epsilon) by using techniques of modern first-order methods in convex optimization. Our computational guarantees 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 prespecified learning rate for a fixed but arbitrary number of iterations, for any dataset.

Keywords: subgradient descent, steepest descent, boosting, linear regression, LASSO

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Applications -- Science and Engineering (Data-Mining )

Citation: MIT Operations Research Center Technical Report

Download: [PDF]

Entry Submitted: 05/15/2015
Entry Accepted: 05/15/2015
Entry Last Modified: 05/15/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society