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.