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. On the theory of variance reduction for stochastic gradient monte carlo
 
conference paper

On the theory of variance reduction for stochastic gradient monte carlo

Chatterji, N.S.
•
Flammarion, Nicolas  
•
Ma, Yi-An
Show more
2018
Proceedings of Machine Learning Research

We show that accelerated gradient descent, averaged gradient descent and the heavy-ball method for quadratic non-strongly-convex problems may be reformulated as constant parameter secondorder difference equation algorithms, where stability of the system is equivalent to convergence at rate O(1/n2), where n is the number of iterations. We provide a detailed analysis of the eigenvalues of the corresponding linear dynamical system, showing various oscillatory and non-oscillatory behaviors, together with a sharp stability result with explicit constants. We also consider the situation where noisy gradients are available, where we extend our general convergence result, which suggests an alternative algorithm (i.e., with different step sizes) that exhibits the good aspects of both averaging and acceleration.

  • Details
  • Metrics
Type
conference paper
Author(s)
Chatterji, N.S.
Flammarion, Nicolas  
Ma, Yi-An
Bartlett, P.L.
Jordan, Michael I.
Date Issued

2018

Published in
Proceedings of Machine Learning Research
Volume

80

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
TML  
Available on Infoscience
December 2, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/163506
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