# A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers

arXiv: https://arxiv.org/abs/2002.01586 · HTML: https://mlsanity.com/paper/2002.01586/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2020.

## Built on by (most cited first, 30 of 44)

- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions](https://mlsanity.com/paper/2106.03791/) (2021)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [Deterministic equivalent and error universality of deep random features learning](https://mlsanity.com/paper/2302.00401/) (2023)
- [Universality laws for Gaussian mixtures in generalized linear models](https://mlsanity.com/paper/2302.08933/) (2023)
- [Interpolating Classifiers Make Few Mistakes](https://mlsanity.com/paper/2101.11815/) (2021)
- [The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks](https://mlsanity.com/paper/2108.11489/) (2021)
- [Theoretical characterization of uncertainty in high-dimensional linear classification](https://mlsanity.com/paper/2202.03295/) (2022)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [On the interplay between data structure and loss function in classification problems](https://mlsanity.com/paper/2103.05524/) (2021)
- [Asymptotics of Learning with Deep Structured (Random) Features](https://mlsanity.com/paper/2402.13999/) (2024)
- [High-dimensional learning of narrow neural networks](https://mlsanity.com/paper/2409.13904/) (2024)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [Mitigating multiple descents: A model-agnostic framework for risk monotonization](https://mlsanity.com/paper/2205.12937/) (2022)
- [Preventing Model Collapse Under Overparametrization: Optimal Mixing Ratios for Interpolation Learning and Ridge Regression](https://mlsanity.com/paper/2509.22341/) (2025)
- [Support vector machines and linear regression coincide with very high-dimensional features](https://mlsanity.com/paper/2105.14084/) (2021)
- [Deep Linear Networks can Benignly Overfit when Shallow Ones Do](https://mlsanity.com/paper/2209.09315/) (2022)
- [Minimum ℓ1-norm interpolators: Precise asymptotics and multiple descent](https://mlsanity.com/paper/2110.09502/) (2021)
- [Unraveling Projection Heads in Contrastive Learning: Insights from Expansion and Shrinkage](https://mlsanity.com/paper/2306.03335/) (2023)
- [Universality of max-margin classifiers](https://mlsanity.com/paper/2310.00176/) (2023)
- [Certified Data Removal Under High-dimensional Settings](https://mlsanity.com/paper/2505.07640/) (2025)
- [Minimum complexity interpolation in random features models](https://mlsanity.com/paper/2103.15996/) (2021)
- [A New Central Limit Theorem for the Augmented IPW Estimator: Variance Inflation, Cross-Fit Covariance and Beyond](https://mlsanity.com/paper/2205.10198/) (2022)
- [Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings](https://mlsanity.com/paper/2402.08543/) (2024)
- [On how to avoid exacerbating spurious correlations when models are overparameterized](https://mlsanity.com/paper/2206.12739/) (2022)
- [Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression](https://mlsanity.com/paper/2402.13622/) (2024)
- [ROTI-GCV: Generalized Cross-Validation for right-ROTationally Invariant Data](https://mlsanity.com/paper/2406.11666/) (2024)
- [On Optimal Interpolation In Linear Regression](https://mlsanity.com/paper/2110.11258/) (2021)

## Abstract (arXiv)

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 ℓ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 citebreiman1999prediction, schapire1998boosting surrounding boosting, under assumed data generating processes. At the heart of our theory lies an in-depth study of the maximum-ℓ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 ℓq-geometry, q ∈ [1, 2]. As a final component, via the Lindeberg principle, we establish a universality result showcasing that the scaled ℓ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.