Preprint · 2020 · Open access
Randomized Primal-Dual Algorithms for Composite Convex Minimization with Faster Convergence Rates
arXiv (Cornell University) · Published 3 March 2020
In brief
“Randomized Primal-Dual Algorithms for Composite Convex Minimization with Faster Convergence Rates” is a 2020 preprint by Quoc Tran-Dinh and Deyi Liu, published in arXiv (Cornell University). OpenAlex counts 0 citations as of 16 November 2026. It is open access: the full text is free to read at arXiv (Cornell University).
- Citations
- 0
- Authors
- 2
Abstract
We develop two novel randomized primal-dual algorithms to solve nonsmooth composite convex optimization problems. The first algorithm is fully randomized, i.e., it has randomized updates on both primal and dual variables, while the second one is a semi-randomized scheme which only has one randomized update on the primal (or dual) variable while using the full update for the other. Both algorithms achieve the best-known $\mathcal{O}(1/k)$ or $\mathcal{O}(1/k^2)$ convergence rates in expectation under either only convexity or strong convexity, respectively, where $k$ is the iteration counter. Interestingly, with new parameter update rules, our algorithms can achieve $o(1/k)$ or $o(1/k^2)$ best-iterate convergence rate in expectation under either convexity or strong convexity, respectively. These rates can be obtained for both the primal and dual problems. To the best of our knowledge, this is the first time such faster convergence rates are shown for randomized primal-dual methods. Finally, we verify our theoretical results via two numerical examples and compare them with the state-of-the-art.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Tran-Dinh, Q., & Liu, D. (2020). Randomized Primal-Dual Algorithms for Composite Convex Minimization with Faster Convergence Rates. arXiv (Cornell University). https://arxiv.org/abs/2003.01322
MLA 9
Tran-Dinh, Quoc, and Deyi Liu. “Randomized Primal-Dual Algorithms for Composite Convex Minimization with Faster Convergence Rates.” arXiv (Cornell University), 2020. https://arxiv.org/abs/2003.01322.
Chicago
Tran-Dinh, Quoc and Deyi Liu. 2020. “Randomized Primal-Dual Algorithms for Composite Convex Minimization with Faster Convergence Rates.” arXiv (Cornell University). https://arxiv.org/abs/2003.01322.
Harvard
Tran-Dinh, Q. and Liu, D. (2020) ‘Randomized Primal-Dual Algorithms for Composite Convex Minimization with Faster Convergence Rates’, arXiv (Cornell University). Available at: https://arxiv.org/abs/2003.01322.
IEEE
Q. Tran-Dinh and D. Liu, “Randomized Primal-Dual Algorithms for Composite Convex Minimization with Faster Convergence Rates,” arXiv (Cornell University), 2020.
BibTeX
@misc{trandinh2020randomized,
title = {{Randomized Primal-Dual Algorithms for Composite Convex Minimization with Faster Convergence Rates}},
author = {Tran-Dinh, Quoc and Liu, Deyi},
howpublished = {arXiv (Cornell University)},
year = {2020},
url = {https://arxiv.org/abs/2003.01322}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Topic and keywords
Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- composite convex optimization
- nonsmooth optimization
- convergence rate
- strong convexity
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?
Tran-Dinh, Q., & Liu, D. (2020). Randomized Primal-Dual Algorithms for Composite Convex Minimization with Faster Convergence Rates. arXiv (Cornell University). https://arxiv.org/abs/2003.01322
How many times has this paper been cited?
0 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?
Quoc Tran-Dinh, Deyi Liu.
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.