AdaBoost and robust one-bit compressed sensing
Not on the map. Why?
Abstract (arXiv)
This paper studies binary classification in robust one-bit compressed sensing with adversarial errors. It is assumed that the model is overparameterized and that the parameter of interest is effectively sparse. AdaBoost is considered, and, through its relation to the max-ℓ1-margin-classifier, prediction error bounds are derived. The developed theory is general and allows for heavy-tailed feature distributions, requiring only a weak moment assumption and an anti-concentration condition. Improved convergence rates are shown when the features satisfy a small deviation lower bound. In particular, the results provide an explanation why interpolating adversarial noise can be harmless for classification problems. Simulations illustrate the presented theory.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 21 of its 68 references that are in the map. First posted on arXiv 5 May 2021.
Builds on
21 of 68 references.
References · 21
- 2016Understanding deep learning requires rethinking generalizationcited by 1,657
- 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,404
- 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
- 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
- 2019Benign Overfitting in Linear Regressioncited by 544
- 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
- 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
- 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
- 2019A Model of Double Descent for High-dimensional Binary Linear Classificationcited by 81
- 2014Learning without Concentrationcited by 50
- 2015Explaining the Success of AdaBoost and Random Forests as Interpolating Classifierscited by 45
- 2020A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifierscited by 44
9 more
- 2013Margins, Shrinkage, and Boostingcited by 35
- 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
- 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
- 2020On the robustness of minimum norm interpolators and regularized empirical risk minimizerscited by 18
- 2020Agnostic Learning of Halfspaces with Gradient Descent via Soft Marginscited by 14
- 2018Efficient active learning of sparse halfspacescited by 13
- 2014One-bit compressive sensing with norm estimationcited by 10
- 2020On the robustness of the minimum ℓ2 interpolatorcited by 4
- 2018A Quotient Property for Matrices with Heavy-Tailed Entries and its Application to Noise-Blind Compressed Sensingcited by 3
Built on by
Citing papers per year: 2022: 2.
2 papers.