Preprint · 2015 · Open access

Universal Primal-Dual Proximal-Gradient Methods

Alp Yurtsever, Quoc Tran-Dinh, Volkan Cevher

arXiv (Cornell University) · Published 10 February 2015

Read the free full textCite this paper

In brief

“Universal Primal-Dual Proximal-Gradient Methods” is a 2015 preprint by Alp Yurtsever and 2 co-authors, published in arXiv (Cornell University). OpenAlex counts 5 citations as of 15 November 2026. It is open access: the full text is free to read at arXiv (Cornell University).

Citations
5
Most cited in
2015 (2)
References
13
Authors
3

Abstract

We propose a primal-dual algorithmic framework for a prototypical constrained convex minimization problem. The new framework aims to trade-off the computational difficulty between the primal and the dual subproblems. We achieve this in our setting by replacing the standard proximal mapping computations with linear minimization oracles in the primal space, which has been the hallmark of the scalable Frank-Wolfe-type algorithms. Our analysis extends Nesterov's universal gradient methods to the primal-dual setting in a nontrivial fashion, and provides optimal convergence guarantees for the objective residual as well as the feasibility gap without having to know the smoothness structures of the problem. As a result, we obtain stronger primal-dual convergence results than the existing Frank-Wolfe-type algorithms for important machine learning problems involving sparsity and low-rank, and also illustrate them numerically.

Cite this paper

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

APA 7

Yurtsever, A., Tran-Dinh, Q., & Cevher, V. (2015). Universal Primal-Dual Proximal-Gradient Methods. arXiv (Cornell University). https://arxiv.org/pdf/1502.03123.pdf

MLA 9

Yurtsever, Alp, et al. “Universal Primal-Dual Proximal-Gradient Methods.” arXiv (Cornell University), 2015. https://arxiv.org/pdf/1502.03123.pdf.

Chicago

Yurtsever, Alp, Quoc Tran-Dinh, and Volkan Cevher. 2015. “Universal Primal-Dual Proximal-Gradient Methods.” arXiv (Cornell University). https://arxiv.org/pdf/1502.03123.pdf.

Harvard

Yurtsever, A., Tran-Dinh, Q. and Cevher, V. (2015) ‘Universal Primal-Dual Proximal-Gradient Methods’, arXiv (Cornell University). Available at: https://arxiv.org/pdf/1502.03123.pdf.

IEEE

A. Yurtsever, Q. Tran-Dinh, and V. Cevher, “Universal Primal-Dual Proximal-Gradient Methods,” arXiv (Cornell University), 2015.

BibTeX

@misc{yurtsever2015universal,
  title     = {{Universal Primal-Dual Proximal-Gradient Methods}},
  author    = {Yurtsever, Alp and Tran-Dinh, Quoc and Cevher, Volkan},
  howpublished = {arXiv (Cornell University)},
  year      = {2015},
  url       = {https://arxiv.org/pdf/1502.03123.pdf}
}

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

Citations by year

YearCitationsShare of the best year
201522
201811
202122

Topic and keywords

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

  • primal-dual algorithm
  • proximal gradient method
  • constrained convex minimization
  • linear minimization oracle
  • convergence guarantees
  • sparsity
  • low-rank optimization
  • machine learning optimization

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?

Yurtsever, A., Tran-Dinh, Q., & Cevher, V. (2015). Universal Primal-Dual Proximal-Gradient Methods. arXiv (Cornell University). https://arxiv.org/pdf/1502.03123.pdf

How many times has this paper been cited?

5 times, according to OpenAlex on 15 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?

Alp Yurtsever, Quoc Tran-Dinh, Volkan Cevher.

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