Margins, Shrinkage, and Boosting

Abstract

This manuscript shows that AdaBoost and its immediate variants can produce approximate maximum margin classifiers simply by scaling step size choices with a fixed small constant. In this way, when the unscaled step size is an optimal choice, these results provide guarantees for Friedman's empirically successful "shrinkage" procedure for gradient boosting (Friedman, 2000). Guarantees are also provided for a variety of other step sizes, affirming the intuition that increasingly regularized line searches provide improved margin guarantees. The results hold for the exponential loss and similar losses, most notably the logistic loss.

To appear, ICML 2013

References in corpus (2)

• Scikit-learn: Machine Learning in Python
• Analysis of boosting algorithms using the smooth margin function

Cited by in corpus (19)

• Characterizing Implicit Bias in Terms of Optimization Geometry
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• Risk and parameter convergence of logistic regression
• Implicit Bias of Gradient Descent on Linear Convolutional Networks
• Convergence of Gradient Descent on Separable Data
• A Model of Double Descent for High-dimensional Binary Linear Classification
• When Will Gradient Methods Converge to Max-margin Classifier under ReLU Models?
• Inductive Bias of Gradient Descent based Adversarial Training on Separable Data
• Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
• Patterns, predictions, and actions: A story about machine learning
• Bridging the Gap Between Adversarial Robustness and Optimization Bias
• Gradient descent follows the regularization path for general losses
• The Implicit Bias of AdaGrad on Separable Data
• On the Self-Penalization Phenomenon in Feature Selection
• Rethinking Breiman's Dilemma in Neural Networks: Phase Transitions of Margin Dynamics
• Robust Boosting for Regression Problems
• Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data
• Tree-based boosting with functional data
• Training Efficiency and Robustness in Deep Learning