Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Online Robust Regression via SGD on the l1 loss
 
conference paper

Online Robust Regression via SGD on the l1 loss

Pesme, Scott  
•
Flammarion, Nicolas  
2020
Neurips
Neurips 2020

We consider the robust linear regression problem in the online setting where we have access to the data in a streaming manner, one data point after the other. More specifically, for a true parameter , we consider the corrupted Gaussian linear model $ y=\langle x, \theta^* \rangle+\varepsilon+ b $ where the adversarial noise can take any value with probability and equals zero otherwise. We consider this adversary to be oblivious (ie, independent of the data) since this is the only contamination model under which consistency is possible. Current algorithms rely on having the whole data at hand in order to identify and remove the outliers. In contrast, we show in this work that stochastic gradient descent on the loss converges to the true parameter vector at a rate which is independent of the values of the contaminated measurements. Our proof relies on the elegant smoothing of the non-smooth loss by the Gaussian data and a classical non-asymptotic analysis of Polyak-Ruppert averaged SGD. In addition, we provide experimental evidence of the efficiency of this simple and highly scalable algorithm.

  • Details
  • Metrics
Type
conference paper
ArXiv ID

2007.00399

Author(s)
Pesme, Scott  
Flammarion, Nicolas  
Date Issued

2020

Published in
Neurips
Subjects

SGD

•

Robust optimisation

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
TML  
Event name
Neurips 2020
Available on Infoscience
July 24, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/170345
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés