Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

On the convergence of stochastic primal-dual hybrid gradient

Abstract : 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-$\mu$ and other state-of-the-art algorithms including variance reduction methods and stochastic dual coordinate ascent.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-02362067
Contributor : Olivier Fercoq <>
Submitted on : Wednesday, November 13, 2019 - 4:56:36 PM
Last modification on : Thursday, May 27, 2021 - 1:54:06 PM

Links full text

Identifiers

  • HAL Id : hal-02362067, version 1
  • ARXIV : 1911.00799

Collections

Citation

Ahmet Alacaoglu, Olivier Fercoq, Volkan Cevher. On the convergence of stochastic primal-dual hybrid gradient. 2019. ⟨hal-02362067⟩

Share

Metrics

Record views

34