Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications

Antonin Chambolle, Matthias J. Ehrhardt, Peter Richtárik, Carola-Bibiane Schönlieb
6/15/2017
math.OCcs.CVmath.NA

Official code: odlgroup/odl (434 stars, MPL-2.0, last commit 2026-03-11).

Abstract

We propose a stochastic extension of the primal-dual hybrid gradient algorithm studied by Chambolle and Pock in 2011 to solve saddle point problems that are separable in the dual variable. The analysis is carried out for general convex-concave saddle point problems and problems that are either partially smooth / strongly convex or fully smooth / strongly convex. We perform the analysis for arbitrary samplings of dual variables, and obtain known deterministic results as a special case. Several variants of our stochastic method significantly outperform the deterministic variant on a variety of imaging tasks.

View on arXivView PDF

Code Implementations(1)

odlgroup/odlOfficial100%
MPL-2.0

Operator Discretization Library https://odl.readthedocs.io/

434122Shell, PythonNov 5, 20157 months agoMPL-2.0
discretizationimaginginverse-problemsmathematicsoptimization+3 more

Similar Papers

Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problems

87% match2023

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization

81% match2023

Convergence of the Chambolle-Pock Algorithm in the Absence of Monotonicity

80% match2023

Dealing with unbounded gradients in stochastic saddle-point optimization

80% match2024

Multiple Greedy Quasi-Newton Methods for Saddle Point Problems

79% match2024

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints

79% match2025

Cite this paper

@article{chambolle2017stochastic,
  title  = {Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications},
  author = {Antonin Chambolle and Matthias J. Ehrhardt and Peter Richtárik and Carola-Bibiane Schönlieb},
  year   = {2017},
  eprint = {1706.04957},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1706.04957}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1706.04957.svg)](https://codeofpaper.com/paper/1706.04957)

Discussion