# Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization

arXiv: https://arxiv.org/abs/2305.17323 · HTML: https://mlsanity.com/paper/2305.17323/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 58 references that are in the map.
- First posted on arXiv 27 May 2023.

## Builds on (most cited first, 26 of 26)

- [Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems](https://mlsanity.com/paper/1707.03505/) (2017)
- [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017)
- [Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity](https://mlsanity.com/paper/1712.04104/) (2017)
- [First-Order Methods for Nonsmooth Nonconvex Functional Constrained Optimization with or without Slater Points](https://mlsanity.com/paper/2212.00927/) (2022)
- [RSG: Beating Subgradient Method without Smoothness and Strong Convexity](https://mlsanity.com/paper/1512.03107/) (2015)
- ["Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent](https://mlsanity.com/paper/1710.04718/) (2017)
- [A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods](https://mlsanity.com/paper/1803.00151/) (2018)
- [Mirror Descent and Convex Optimization Problems With Non-Smooth Inequality Constraints](https://mlsanity.com/paper/1710.06612/) (2017)
- [Optimal Convergence Rates for the Proximal Bundle Method](https://mlsanity.com/paper/2105.07874/) (2021)
- [On the Linear Convergence of Extra-Gradient Methods for Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2201.06167/) (2022)
- [Radial Subgradient Method](https://mlsanity.com/paper/1703.09280/) (2017)
- [Faster Subgradient Methods for Functions with H"olderian Growth](https://mlsanity.com/paper/1704.00196/) (2017)
- [Revisiting Spectral Bundle Methods: Primal-dual (Sub)linear Convergence Rates](https://mlsanity.com/paper/2008.07067/) (2020)
- [On Modification of an Adaptive Stochastic Mirror Descent Algorithm for Convex Optimization Problems with Functional Constraints](https://mlsanity.com/paper/1904.09513/) (2019)
- [Radial Duality Part II: Applications and Algorithms](https://mlsanity.com/paper/2104.11185/) (2021)
- [Perturbed Fenchel duality and first-order methods](https://mlsanity.com/paper/1812.10198/) (2018)
- [Convergence rates of proximal gradient methods via the convex conjugate](https://mlsanity.com/paper/1801.02509/) (2018)
- [Accelerated Dual-Averaging Primal-Dual Method for Composite Convex Minimization](https://mlsanity.com/paper/2001.05537/) (2020)
- [Analogues of Switching Subgradient Schemes for Relatively Lipschitz-Continuous Convex Programming Problems](https://mlsanity.com/paper/2003.09147/) (2020)
- [Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets](https://mlsanity.com/paper/2303.05037/) (2023)
- [Dual-Based Approximation Algorithms for Cut-Based Network Connectivity Problems](https://mlsanity.com/paper/1508.05567/) (2015)
- [Randomized Block Subgradient Methods for Convex Nonsmooth and Stochastic Optimization](https://mlsanity.com/paper/1509.04609/) (2015)
- [Convergence of first-order methods via the convex conjugate](https://mlsanity.com/paper/1707.09084/) (2017)
- [Extended Regularized Dual Averaging Methods for Stochastic Optimization](https://mlsanity.com/paper/1904.02316/) (2019)
- [Bundle Method Sketching for Low Rank Semidefinite Programming](https://mlsanity.com/paper/1911.04443/) (2019)
- [General Holder Smooth Convergence Rates Follow From Specialized Rates Assuming Growth Bounds](https://mlsanity.com/paper/2104.10196/) (2021)

## Abstract (arXiv)

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.