Preprint · 2020 · Open access

Faster Randomized Primal-Dual Algorithms For Nonsmooth Composite Convex Minimization

Quoc Tran-Dinh, Deyi Liu

arXiv (Cornell University) · Published 3 March 2020

Read the free full textCite this paper

In brief

“Faster Randomized Primal-Dual Algorithms For Nonsmooth Composite Convex Minimization” 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
References
39
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 parallel 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. These rates can be obtained for both the primal and dual problems. With new parameter update rules, our algorithms can be boosted up to $\underline{o}(1/(k\sqrt{\log{k}}))$ or $\underline{o}(1/(k^2\sqrt{\log{k}}))$-rates in expectation, respectively (see definitions below). 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 state-of-the-arts.

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). Faster Randomized Primal-Dual Algorithms For Nonsmooth Composite Convex Minimization. arXiv (Cornell University). https://arxiv.org/pdf/2003.01322

MLA 9

Tran-Dinh, Quoc, and Deyi Liu. “Faster Randomized Primal-Dual Algorithms For Nonsmooth Composite Convex Minimization.” arXiv (Cornell University), 2020. https://arxiv.org/pdf/2003.01322.

Chicago

Tran-Dinh, Quoc and Deyi Liu. 2020. “Faster Randomized Primal-Dual Algorithms For Nonsmooth Composite Convex Minimization.” arXiv (Cornell University). https://arxiv.org/pdf/2003.01322.

Harvard

Tran-Dinh, Q. and Liu, D. (2020) ‘Faster Randomized Primal-Dual Algorithms For Nonsmooth Composite Convex Minimization’, arXiv (Cornell University). Available at: https://arxiv.org/pdf/2003.01322.

IEEE

Q. Tran-Dinh and D. Liu, “Faster Randomized Primal-Dual Algorithms For Nonsmooth Composite Convex Minimization,” arXiv (Cornell University), 2020.

BibTeX

@misc{trandinh2020faster,
  title     = {{Faster Randomized Primal-Dual Algorithms For Nonsmooth Composite Convex Minimization}},
  author    = {Tran-Dinh, Quoc and Liu, Deyi},
  howpublished = {arXiv (Cornell University)},
  year      = {2020},
  url       = {https://arxiv.org/pdf/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

  • nonsmooth convex optimization
  • convergence rate
  • strong convexity

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?

Tran-Dinh, Q., & Liu, D. (2020). Faster Randomized Primal-Dual Algorithms For Nonsmooth Composite Convex Minimization. arXiv (Cornell University). https://arxiv.org/pdf/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.