Some primal-dual theory for subgradient methods for strongly convex optimization.
Saved in:
| Title: | Some primal-dual theory for subgradient methods for strongly convex optimization. |
|---|---|
| Authors: | Grimmer, Benjamin1 (AUTHOR) grimmer@jhu.edu, Li, Danlin1 (AUTHOR) dli91@alumni.jh.edu |
| Source: | Mathematical Programming. Nov2025, Vol. 214 Issue 1/2, p759-788. 30p. |
| Subjects: | Subgradient methods, Convex programming, Mathematical programming, Nonsmooth optimization, Asymptotic analysis, Mathematical optimization |
| Abstract: | 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 to 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
Be the first to leave a comment!
