Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization
This work addresses a foundational problem in optimization theory by offering improved convergence guarantees and practical tools like stopping criteria for a wide range of non-Lipschitz problems, though it is incremental in extending existing methods.
The paper tackles the problem of strongly convex but potentially nonsmooth and non-Lipschitz optimization by providing new dual descriptions for classic subgradient methods, enabling O(1/T) convergence guarantees for both primal and dual gaps, and ensuring eventual convergence even in cases where early iterations may diverge exponentially quickly.
We consider (stochastic) subgradient methods for strongly convex but potentially nonsmooth non-Lipschitz optimization. We provide new equivalent dual descriptions (in the style of dual averaging) for the classic subgradient method, the proximal subgradient method, and the switching subgradient method. These equivalences enable $O(1/T)$ convergence guarantees in terms of both their classic primal gap and a not previously analyzed dual gap for strongly convex optimization. Consequently, our theory provides these classic methods with simple, optimal stopping criteria and optimality certificates at no added computational cost. Our results apply to a wide range of stepsize selections and of non-Lipschitz ill-conditioned problems where the early iterations of the subgradient method may diverge exponentially quickly (a phenomenon which, to the best of our knowledge, no prior works address). Even in the presence of such undesirable behaviors, our theory still ensures and bounds eventual convergence.