Preprint · 2022 · Open access
RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates
arXiv (Cornell University) · Published 26 July 2022 · DOI 10.48550/arxiv.2207.12891
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
| Year | Citations | Share of the best year |
|---|---|---|
| 2022 | 2 | |
| 2023 | 2 | |
| 2024 | 8 | |
| 2025 | 6 | |
| 2026 | 4 |
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
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
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.