A precise high-dimensional asymptotic theory for boosting and minimum-_1-norm interpolated classifiers

DOI10.1214/22-AOS2170MaRDI QIDQ2148995zbMATH OpenOpenAlexWikidataFDO

Authors Tengyuan Liang, Pragya Sur

Publication date 24 June 2022

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.01586

zbMATH Keywords

boostinghigh-dimensional asymptoticsoverparametrizationmargin theoryminimum-norm interpolation

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

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 $el{l}_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-$el{l}_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 $el{l}_q$-geometry, $qin[1,2]$. As a final component, via the Lindeberg principle, we establish a universality result showcasing that the scaled $el{l}_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.

Recommendations

• Some theory for generalized boosting algorithms
• Boosting as a regularized path to a maximum margin classifier
• Boosting with early stopping: convergence and consistency
• scientific article; zbMATH DE number 1804118
• Boosting for high-dimensional linear models

Cites work

• scientific article; zbMATH DE number 2089371 (Why is no real title available?)
• scientific article; zbMATH DE number 1804118 (Why is no real title available?)
• scientific article; zbMATH DE number 4061904 (Why is no real title available?)
• scientific article; zbMATH DE number 4096600 (Why is no real title available?)
• scientific article; zbMATH DE number 7370646 (Why is no real title available?)
• scientific article; zbMATH DE number 7415120 (Why is no real title available?)
• 10.1162/1532443041424319
• A Unifying Tutorial on Approximate Message Passing
• A modern maximum-likelihood theory for high-dimensional logistic regression
• A new perspective on boosting in linear regression via subgradient optimization and relatives
• A note on A. Albert and J. A. Anderson's conditions for the existence of maximum likelihood estimates in logistic regression models
• AdaBoost is consistent
• Additive logistic regression: a statistical view of boosting. (With discussion and a rejoinder by the authors)
• Analysis of boosting algorithms using the smooth margin function
• Arcing classifiers. (With discussion)
• Benign overfitting in linear regression
• Boosting With theL₂Loss
• Boosting a weak learning algorithm by majority
• Boosting algorithms: regularization, prediction and model fitting
• Boosting as a regularized path to a maximum margin classifier
• Boosting for high-dimensional linear models
• Boosting in the presence of outliers: adaptive classification with nonconvex loss functions
• Boosting the margin: a new explanation for the effectiveness of voting methods
• Boosting with early stopping: convergence and consistency
• Breaking the curse of dimensionality with convex neural networks
• Complexities of convex combinations and bounding the generalization error in classification
• Efficient margin maximizing with boosting
• Empirical margin distributions and bounding the generalization error of combined classifiers
• Enumeration of Seven-Argument Threshold Functions
• Greedy function approximation: A gradient boosting machine.
• High dimensional robust M-estimation: asymptotic variance via approximate message passing
• Just interpolate: kernel ``ridgeless regression can generalize
• Learning Theory
• On robust regression with high-dimensional predictors
• On the Bayes-risk consistency of regularized boosting methods.
• On the equivalence of weak learnability and linear separability: new relaxations and efficient boosting algorithms
• On the existence of linear weak learners and applications to boosting
• On the existence of maximum likelihood estimates in logistic regression models
• On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators
• Population theory for boosting ensembles.
• Precise Error Analysis of Regularized <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math> </inline-formula>-Estimators in High Dimensions
• Prediction Games and Arcing Algorithms
• Process consistency for AdaBoost.
• Reconciling modern machine-learning practice and the classical bias-variance trade-off
• Recovering structured signals in noise: least-squares meets compressed sensing
• Rigorous solution of the Gardner problem
• Soft margins for AdaBoost
• Some inequalities for Gaussian processes and applications
• Some theory for generalized boosting algorithms
• Sparse boosting
• Statistical behavior and consistency of classification methods based on convex risk minimization.
• Surprises in high-dimensional ridgeless least squares interpolation
• The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve
• The asymptotic distribution of the MLE in high-dimensional logistic models: arbitrary covariance
• The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square
• The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression
• The rate of convergence of AdaBoost
• The space of interactions in neural network models
• Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits
• Two models of double descent for weak features
• Which bridge estimator is the best for variable selection?

Cited in

(21)

• The generalization error of max-margin linear classifiers: benign overfitting and high dimensional asymptotics in the overparametrized regime
• A new central limit theorem for the augmented IPW estimator: variance inflation, cross-fit covariance and beyond
• A Unifying Tutorial on Approximate Message Passing
• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• Tight bounds for maximum _1-margin classifiers
• Mehler’s Formula, Branching Process, and Compositional Kernels of Deep Neural Networks
• Equivalence of state equations from different methods in high-dimensional regression
• Kronecker-product random matrices and a matrix least squares problem
• Deterministic equivalent and error universality of deep random features learning
• Spectrum-aware debiasing: a modern inference framework with applications to principal components regression
• Precise asymptotics of bagging regularized M-estimators
• Universality of regularized regression estimators in high dimensions
• Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions
• Differentially private learning beyond the classical dimensionality regime
• scientific article; zbMATH DE number 7370646 (Why is no real title available?)
• Universality of estimators for high-dimensional linear models with block dependency
• Correlation adjusted debiased Lasso: debiasing the Lasso with inaccurate covariate model
• High-dimensional learning of narrow neural networks
• On the robustness of minimum norm interpolators and regularized empirical risk minimizers
• The curse of overparametrization in adversarial training: precise analysis of robust generalization for random features regression
• AdaBoost and robust one-bit compressed sensing

Describes a project that uses

Uses Software

• AdaBoost.MH

This page was built for publication: A precise high-dimensional asymptotic theory for boosting and minimum-\(\ell_1\)-norm interpolated classifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2148995)