Preprint · 2022 · Open access

RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates

Laurent Condat, Peter Richtárik

arXiv (Cornell University) · Published 26 July 2022 · DOI 10.48550/arxiv.2207.12891

Free PDFView at the publisherCite this paper

In brief

“RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates” is a 2022 preprint by Laurent Condat and Peter Richtárik, published in arXiv (Cornell University). OpenAlex counts 22 citations as of 16 November 2026. It is open access: the full text is free to read at arXiv (Cornell University).

Citations
22
Most cited in
2024 (8)
References
9
Authors
2

Abstract

Proximal splitting algorithms are well suited to solving large-scale nonsmooth optimization problems, in particular those arising in machine learning. We propose a new primal-dual algorithm, in which the dual update is randomized; equivalently, the proximity operator of one of the function in the problem is replaced by a stochastic oracle. For instance, some randomly chosen dual variables, instead of all, are updated at each iteration. Or, the proximity operator of a function is called with some small probability only. A nonsmooth variance-reduction technique is implemented so that the algorithm finds an exact minimizer of the general problem involving smooth and nonsmooth functions, possibly composed with linear operators. We derive linear convergence results in presence of strong convexity; these results are new even in the deterministic case, when our algorithms reverts to the recently proposed Primal-Dual Davis-Yin algorithm. Some randomized algorithms of the literature are also recovered as particular cases (e.g., Point-SAGA). But our randomization technique is general and encompasses many unbiased mechanisms beyond sampling and probabilistic updates, including compression. Since the convergence speed depends on the slowest among the primal and dual contraction mechanisms, the iteration complexity might remain the same when randomness is used. On the other hand, the computation complexity can be significantly reduced. Overall, randomness helps getting faster algorithms. This has long been known for stochastic-gradient-type algorithms, and our work shows that this fully applies in the more general primal-dual setting as well.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Condat, L., & Richtárik, P. (2022). RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2207.12891

MLA 9

Condat, Laurent, and Peter Richtárik. “RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates.” arXiv (Cornell University), 2022. https://doi.org/10.48550/arxiv.2207.12891.

Chicago

Condat, Laurent and Peter Richtárik. 2022. “RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2207.12891.

Harvard

Condat, L. and Richtárik, P. (2022) ‘RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates’, arXiv (Cornell University). doi:10.48550/arxiv.2207.12891.

IEEE

L. Condat and P. Richtárik, “RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates,” arXiv (Cornell University), 2022, doi: 10.48550/arxiv.2207.12891.

BibTeX

@misc{condat2022randprox,
  title     = {{RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates}},
  author    = {Condat, Laurent and Richtárik, Peter},
  howpublished = {arXiv (Cornell University)},
  year      = {2022},
  doi       = {10.48550/arxiv.2207.12891},
  url       = {https://doi.org/10.48550/arxiv.2207.12891}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
202222
202322
202488
202566
202644

Topic and keywords

Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques

  • primal-dual optimization
  • proximal splitting algorithms
  • nonsmooth optimization
  • variance reduction
  • linear convergence
  • strong convexity
  • randomized algorithms
  • data compression

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Condat, L., & Richtárik, P. (2022). RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2207.12891

How many times has this paper been cited?

22 times, according to OpenAlex on 16 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access: read the free full text at arXiv (Cornell University).

Who wrote this paper?

Laurent Condat, Peter Richtárik.

What is the DOI of this paper?

10.48550/arxiv.2207.12891. The permanent link is https://doi.org/10.48550/arxiv.2207.12891.

Bibliographic data from OpenAlex (CC0), last checked 16 November 2026. ResearchGuru does not host this paper; the links go to the publisher or the repository that does.