Open access
Date
2021-12-08Type
- Working Paper
ETH Bibliography
yes
Altmetrics
Abstract
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-$\ell_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. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000585779Publication status
publishedJournal / series
arXivPages / Article No.
Publisher
Cornell UniversityEdition / version
v4Organisational unit
03717 - van de Geer, Sara (emeritus) / van de Geer, Sara (emeritus)
More
Show all metadata
ETH Bibliography
yes
Altmetrics