# Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 23 May 2023.

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

- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity](https://mlsanity.com/paper/1712.04104/) (2017)
- ["Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent](https://mlsanity.com/paper/1710.04718/) (2017)
- [Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses](https://mlsanity.com/paper/2010.12033/) (2020)
- [Stochastic model-based minimization under high-order growth](https://mlsanity.com/paper/1807.00255/) (2018)
- ["Efficient" Subgradient Methods for General Convex Optimization](https://mlsanity.com/paper/1605.08712/) (2016)
- [Radial Subgradient Method](https://mlsanity.com/paper/1703.09280/) (2017)

## Built on by (most cited first, 2 of 2)

- [Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity](https://mlsanity.com/paper/2401.13971/) (2024)
- [A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions](https://mlsanity.com/paper/2308.16362/) (2023)

## Abstract (arXiv)

The subgradient method is one of the most fundamental algorithmic schemes for nonsmooth optimization. The existing complexity and convergence results for this method are mainly derived for Lipschitz continuous objective functions. In this work, we first extend the typical iteration complexity results for the subgradient method to cover non-Lipschitz convex and weakly convex minimization. Specifically, for the convex case, we can drive the suboptimality gap to below varepsilon in O( varepsilon-2 ) iterations; for the weakly convex case, we can drive the gradient norm of the Moreau envelope of the objective function to below varepsilon in O( varepsilon-4 ) iterations. Then, we provide convergence results for the subgradient method in the non-Lipschitz setting when proper diminishing rules on the step size are used. In particular, when f is convex, we establish an O(log(k)/√k) rate of convergence in terms of the suboptimality gap, where k represents the iteration count. With an additional quadratic growth property, the rate is improved to O(1/k) in terms of the squared distance to the optimal solution set. When f is weakly convex, asymptotic convergence is established. Our results neither require any modification to the subgradient method nor impose any growth condition on the subgradients, while our analysis is surprisingly simple. To further illustrate the wide applicability of our framework, we extend the aforementioned iteration complexity results to cover the truncated subgradient, the stochastic subgradient, and the proximal subgradient methods for non-Lipschitz convex / weakly convex objective functions.