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. Journal articles
  4. On The Convergence Of Stochastic Primal-Dual Hybrid Gradient
 
research article

On The Convergence Of Stochastic Primal-Dual Hybrid Gradient

Alacaoglu, Ahmet  
•
Fercoq, Olivier
•
Cevher, Volkan  orcid-logo
January 1, 2022
Siam Journal On Optimization

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 with convexity and linear convergence with further structure, using standard step sizes independent of strong convexity or other regularity constants. In the general convex case, we also prove the \scrO (1/k) convergence rate for the ergodic sequence, on expected primal-dual gap function. Our assumption for linear convergence is metric subregularity, which is satisfied for strongly convex-strongly concave problems in addition to many nonsmooth and/or nonstrongly convex problems, such as linear programs, Lasso, and support vector machines. We also provide numerical evidence showing that SPDHG with standard step sizes shows a competitive practical performance against its specialized strongly convex variant SPDHG-\mu and other state-of-the-art algorithms, including variance reduction methods.

  • Details
  • Metrics
Type
research article
DOI
10.1137/19M1296252
Web of Science ID

WOS:000809754200033

Author(s)
Alacaoglu, Ahmet  
Fercoq, Olivier
Cevher, Volkan  orcid-logo
Date Issued

2022-01-01

Publisher

SIAM PUBLICATIONS

Published in
Siam Journal On Optimization
Volume

32

Issue

2

Start page

1288

End page

1318

Subjects

Mathematics, Applied

•

Mathematics

•

convex optimization

•

coordinate descent

•

primal-dual algorithms

•

alternating direction method

•

fixed-point iterations

•

convex-optimization

•

linear convergence

•

algorithms

•

framework

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIONS  
Available on Infoscience
July 4, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/188956
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