AdaBoost and robust one-bit compressed sensing

  • Geoffrey Chinot

    ETH Zürich, Switzerland
  • Felix Kuchelmeister

    ETH Zürich, Switzerland
  • Matthias Löffler

    ETH Zürich, Switzerland
  • Sara van de Geer

    ETH Zürich, Switzerland
AdaBoost and robust one-bit compressed sensing cover
Download PDF

This article is published open access under our Subscribe to Open model.


This paper studies binary classification in robust one-bit compressed sensing with adversarial errors. It is assumed that the model is overparametrized and that the parameter of interest is effectively sparse. AdaBoost is considered, and, through its relation to the max 1\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.

Cite this article

Geoffrey Chinot, Felix Kuchelmeister, Matthias Löffler, Sara van de Geer, AdaBoost and robust one-bit compressed sensing. Math. Stat. Learn. 5 (2022), no. 1/2, pp. 117–158

DOI 10.4171/MSL/31