A Universal Primal-Dual Convex Optimization Framework

By Alp Yurtsever, Quoc Tran-Dinh, Volkan Cevher. 2015

63 citations recorded by the source corpus.

We propose a new primal-dual algorithmic framework for a prototypical constrained convex optimization template. The algorithmic instances of our framework are universal since they can automatically adapt to the unknown Holder continuity degree and constant within the dual formulation. They are also guaranteed to have optimal convergence rates in the objective residual and the feasibility gap for each Holder smoothness degree. In contrast to existing primal-dual algorithms, our framework avoids the proximity operator of the objective function. We instead leverage computationally cheaper, Fenchel-type operators, which are the main workhorses of the generalized conditional gradient (GCG)-type methods. In contrast to the GCG-type methods, our framework does not require the objective function to be differentiable, and can also process additional general linear inclusion constraints, while guarantees the convergence rate on the primal problem.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Martin Jaggi
2. Simon Lacoste-Julien
3. Peter Richtárik
4. Gauthier Gidel
5. Fabian Pedregosa
6. Sebastian U. Stich
7. Martin Takác
8. Jakub Konecný

In Computational Mechanics

1. Martin Jaggi
2. Simon Lacoste-Julien
3. Gauthier Gidel
4. Fabian Pedregosa
5. Peter Richtárik
6. Martin Takác
7. Jakub Konecný
8. Sebastian U. Stich

In Numerical Analysis

1. Simon Lacoste-Julien
2. Gauthier Gidel
3. Fabian Pedregosa
4. Kfir Yehuda Levy
5. Martin Jaggi
6. Celestine Mendler-Dünner
7. Soomin Lee
8. Volkan Cevher

In Optimization & Training

1. Simon Lacoste-Julien
2. Martin Jaggi
3. Peter Richtárik
4. Gauthier Gidel
5. Fabian Pedregosa
6. Sebastian U. Stich
7. Martin Takác
8. Nicolas Loizou

Citations in the corpus

• Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “Yurtsever et al. (2015) proposed a general algorithm (UniPDGrad) based on the Lagrangian method which, with some work, can be reduced to a splitting method using only LMO as a particular case.”
• Online Adaptive Methods, Universality and Acceleration (2018, methodology): “In (Yurtsever et al., 2015), the authors devise a universal accelerated method for primal dual problems.”
• Primal-Dual Rates and Certificates (2016, background): “also objectives with efficient Fenchel-type operator (Yurtsever et al., 2015).”
• Dropping Convexity for Faster Semi-definite Optimization (2015, background): “Recently, [79] presented a universal primal-dual convex framework, which includes the QST problem as application and outperforms the above approaches, both in terms of recovery performance and execution time.”
• A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks (2018, background): “Also known as the sharp-operator [87].”