A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers

Abstract

This paper establishes a precise high-dimensional asymptotic theory for boosting on separable data, taking statistical and computational perspectives. We consider a high-dimensional setting where the number of features (weak learners) $p$ scales with the sample size $n$, in an overparametrized regime. Under a class of statistical models, we provide an exact analysis of the generalization error of boosting when the algorithm interpolates the training data and maximizes the empirical ${\ell }_1$-margin. Further, we explicitly pin down the relation between the boosting test error and the optimal Bayes error, as well as the proportion of active features at interpolation (with zero initialization). In turn, these precise characterizations answer certain questions raised in \cite{breiman1999prediction, schapire1998boosting} surrounding boosting, under assumed data generating processes. At the heart of our theory lies an in-depth study of the maximum-${\ell }_1$-margin, which can be accurately described by a new system of non-linear equations; to analyze this margin, we rely on Gaussian comparison techniques and develop a novel uniform deviation argument. Our statistical and computational arguments can handle (1) any finite-rank spiked covariance model for the feature distribution and (2) variants of boosting corresponding to general ${\ell }_q$-geometry, $q\in [1,2]$. As a final component, via the Lindeberg principle, we establish a universality result showcasing that the scaled ${\ell }_1$-margin (asymptotically) remains the same, whether the covariates used for boosting arise from a non-linear random feature model or an appropriately linearized model with matching moments.

arXiv comment68 pages, 4 figures

References in corpus (32)

• Message Passing Algorithms for Compressed Sensing
• Understanding deep learning requires rethinking generalization
• Boosting Algorithms: Regularization, Prediction and Model Fitting
• Benign Overfitting in Linear Regression
• Boosting for high-dimensional linear models
• Boosting with early stopping: Convergence and consistency
• A modern maximum-likelihood theory for high-dimensional logistic regression
• The generalization error of random features regression: Precise asymptotics and double descent curve
• The Frontiers of Fairness in Machine Learning
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Two models of double descent for weak features
• A framework to characterize performance of LASSO algorithms
• To understand deep learning we need to understand kernel learning
• Just Interpolate: Kernel "Ridgeless" Regression Can Generalize
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• Complexities of convex combinations and bounding the generalization error in classification
• Boosting in the presence of outliers: adaptive classification with non-convex loss functions
• Analysis of boosting algorithms using the smooth margin function
• The Asymptotic Distribution of the MLE in High-dimensional Logistic Models: Arbitrary Covariance
• The Impact of Regularization on High-dimensional Logistic Regression
• Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms
• Statistical Mechanics of High-Dimensional Inference
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• Universality Laws for High-Dimensional Learning with Random Features
• The Gaussian min-max theorem in the Presence of Convexity
• A Model of Double Descent for High-dimensional Binary Linear Classification
• Interpolating Classifiers Make Few Mistakes
• On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
• AdaBoost and Forward Stagewise Regression are First-Order Convex Optimization Methods
• Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits
• Mehler's Formula, Branching Process, and Compositional Kernels of Deep Neural Networks
• Sharp Asymptotics and Optimal Performance for Inference in Binary Models

Cited by in corpus (2)

• High-dimensional Asymptotics of Langevin Dynamics in Spiked Matrix Models
• Kronecker-product random matrices and a matrix least squares problem