# AdaBoost and robust one-bit compressed sensing

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 68 references that are in the map.
- First posted on arXiv 5 May 2021.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [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)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Explaining the Success of AdaBoost and Random Forests as Interpolating Classifiers](https://mlsanity.com/paper/1504.07676/) (2015)
- [A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers](https://mlsanity.com/paper/2002.01586/) (2020)
- [Margins, Shrinkage, and Boosting](https://mlsanity.com/paper/1303.4172/) (2013)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [Efficient active learning of sparse halfspaces with arbitrary bounded noise](https://mlsanity.com/paper/2002.04840/) (2020)
- [On the robustness of minimum norm interpolators and regularized empirical risk minimizers](https://mlsanity.com/paper/2012.00807/) (2020)
- [Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins](https://mlsanity.com/paper/2010.00539/) (2020)
- [Efficient active learning of sparse halfspaces](https://mlsanity.com/paper/1805.02350/) (2018)
- [One-bit compressive sensing with norm estimation](https://mlsanity.com/paper/1404.6853/) (2014)
- [On the robustness of the minimum ℓ2 interpolator](https://mlsanity.com/paper/2003.05838/) (2020)
- [A Quotient Property for Matrices with Heavy-Tailed Entries and its Application to Noise-Blind Compressed Sensing](https://mlsanity.com/paper/1806.04261/) (2018)

## Built on by (most cited first, 2 of 2)

- [Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias](https://mlsanity.com/paper/2203.03597/) (2022)
- [Tight bounds for maximum ℓ1-margin classifiers](https://mlsanity.com/paper/2212.03783/) (2022)

## 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.