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.
A_Universal_PrimalDual_Convex_Optimization_Framework.pdf
openaccess
350.99 KB
Adobe PDF
86b1b2fbd349143d0d1a54d73689fcd6
A_Universal_PrimalDual_Convex_Optimization_Framework_SuppMat.pdf
openaccess
2.38 MB
Adobe PDF
f472446a5b70b25ca5729f0e36cd0dd8