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. Reports, Documentation, and Standards
  4. On the convergence of stochastic primal-dual hybrid gradient
 
research report

On the convergence of stochastic primal-dual hybrid gradient

Alacaoglu, Ahmet  
•
Fercoq, Olivier
•
Cevher, Volkan  orcid-logo
2019

In this paper, we analyze the recently proposed stochastic primal-dual hybrid gradient (SPDHG) algorithm and provide new theoretical results. In particular, we prove almost sure convergence of the iterates to a solution and linear convergence with standard step sizes, independent of strong convexity constants. Our assumption for linear convergence is metric subregularity, which is satisfied for smooth and strongly convex problems in addition to many nonsmooth and/or nonstrongly convex problems, such as linear programs, Lasso, and support vector machines. In the general convex case, we prove optimal sublinear rates for the ergodic sequence and for randomly selected iterate, without bounded domain assumptions. We also provide numerical evidence showing that SPDHG with standard step sizes shows favorable and robust practical performance against its specialized strongly convex variant SPDHG-μ and other state-of-the-art algorithms including variance reduction methods and stochastic dual coordinate ascent.

  • Details
  • Metrics
Type
research report
Author(s)
Alacaoglu, Ahmet  
Fercoq, Olivier
Cevher, Volkan  orcid-logo
Date Issued

2019

Subjects

ml-ai

Note

Under review.

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIONS  
Available on Infoscience
November 8, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/162779
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