A Universal Primal-Dual Convex Optimization Framework

Abstract

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 guaran- teed 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

18 pages, 2 figures (accepted for NIPS-2015)

References in corpus (1)

• Convex Optimization for Big Data

Cited by in corpus (9)

• On the Complexity of Approximating Wasserstein Barycenter
• An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
• A Conditional Gradient-Based Augmented Lagrangian Framework
• Adaptive Similar Triangles Method: a Stable Alternative to Sinkhorn's Algorithm for Regularized Optimal Transport
• Provable quantum state tomography via non-convex methods
• A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization
• Construction and Iteration-Complexity of Primal Sequences in Alternating Minimization Algorithms
• Numerical methods in large-scale optimization: inexact oracle and primal-dual analysis
• Geometry-Aware Universal Mirror-Prox