mlsanityData to 14 Oct 2026

Tight bounds for maximum ℓ1-margin classifiers

arXiv 2212.03783 ↗First posted 7 Dec 2022stat.ML cs.LGcited by 0

Not on the map. Why?

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.

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

19 of 47 references.

References · 19

  1. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  2. 2019Benign Overfitting in Linear Regressioncited by 549
  3. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  4. 2015Coordinate Descent Algorithmscited by 219
  5. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
  6. 2019A Model of Double Descent for High-dimensional Binary Linear Classificationcited by 81
  7. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  8. 2020A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifierscited by 44
  9. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 42
  10. 2022The Implicit Bias of Benign Overfittingcited by 38
  11. 2013Margins, Shrinkage, and Boostingcited by 35
  12. 2020On the proliferation of support vectors in high dimensionscited by 32
7 more
  1. 2022Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Biascited by 22
  2. 2017High-dimensional classification by sparse logistic regressioncited by 19
  3. 2021Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regressioncited by 17
  4. 2021Tight bounds for minimum l1-norm interpolation of noisy datacited by 16
  5. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11
  6. 2021Support vector machines and linear regression coincide with very high-dimensional featurescited by 8
  7. 2021AdaBoost and robust one-bit compressed sensingcited by 2

Built on by

Not cited yet.