A Universal Primal-Dual Convex Optimization Framework

We propose a new primal-dual algorithmic framework for a prototypical con- strained convex optimization template. The algorithmic instances of our frame- work are universal since they can automatically adapt to the unknown Ho ̈lder con- tinuity properties within the template. They are also guaranteed to have optimal convergence rates in the objective residual and the feasibility gap for each smooth- ness level. In contrast to existing primal-dual algorithms, our framework avoids the proximity operator of the objective function altogether. 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. Our analysis technique unifies Nesterov’s universal gradient methods and GCG- type methods to address the more broadly applicable primal-dual setting.

Presented at:
29th Annual Conference on Neural Information Processing Systems (NIPS2015), Montreal, Canada, December 7-12, 2015

 Record created 2015-02-15, last modified 2019-08-28

Supplementary document:
Download fulltextPDF
Download fulltextPDF
Rate this document:

Rate this document:
(Not yet reviewed)