# Tight bounds for maximum ℓ1-margin classifiers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 47 references that are in the map.
- First posted on arXiv 7 Dec 2022.

## Builds on (most cited first, 19 of 19)

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [A Model of Double Descent for High-dimensional Binary Linear Classification](https://mlsanity.com/paper/1911.05822/) (2019)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers](https://mlsanity.com/paper/2002.01586/) (2020)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022)
- [Margins, Shrinkage, and Boosting](https://mlsanity.com/paper/1303.4172/) (2013)
- [On the proliferation of support vectors in high dimensions](https://mlsanity.com/paper/2009.10670/) (2020)
- [Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias](https://mlsanity.com/paper/2203.03597/) (2022)
- [High-dimensional classification by sparse logistic regression](https://mlsanity.com/paper/1706.08344/) (2017)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [Tight bounds for minimum l1-norm interpolation of noisy data](https://mlsanity.com/paper/2111.05987/) (2021)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)
- [Support vector machines and linear regression coincide with very high-dimensional features](https://mlsanity.com/paper/2105.14084/) (2021)
- [AdaBoost and robust one-bit compressed sensing](https://mlsanity.com/paper/2105.02083/) (2021)

## Abstract (arXiv)

Popular iterative algorithms such as boosting methods and coordinate descent on linear models converge to the maximum ℓ1-margin classifier, a.k.a. sparse hard-margin SVM, in high dimensional regimes where the data is linearly separable. Previous works consistently show that many estimators relying on the ℓ1-norm achieve improved statistical rates for hard sparse ground truths. We show that surprisingly, this adaptivity does not apply to the maximum ℓ1-margin classifier for a standard discriminative setting. In particular, for the noiseless setting, we prove tight upper and lower bounds for the prediction error that match existing rates of order frac|w^*|12/3n1/3 for general ground truths. To complete the picture, we show that when interpolating noisy observations, the error vanishes at a rate of order frac1√log(d/n). We are therefore first to show benign overfitting for the maximum ℓ1-margin classifier.