mlsanityData to 7 Oct 2026

Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity

arXiv 1712.04104 ↗First posted 12 Dec 2017math.OC cs.LGcited by 18

Not on the map. Why?

Abstract (arXiv)

We extend the classic convergence rate theory for subgradient methods to apply to non-Lipschitz functions. For the deterministic projected subgradient method, we present a global O(1/√T) convergence rate for any convex function which is locally Lipschitz around its minimizers. This approach is based on Shor's classic subgradient analysis and implies generalizations of the standard convergence rates for gradient descent on functions with Lipschitz or H"older continuous gradients. Further, we show a O(1/√T) convergence rate for the stochastic projected subgradient method on convex functions with at most quadratic growth, which improves to O(1/T) under either strong convexity or a weaker quadratic lower bound condition.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Dec 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 6; 2025: 3; 2026: 2.

18 papers.

Sort:

  1. 2025Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimizationcited by 81
  2. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  3. 2023Normalized Gradients for Allcited by 18
  4. 2024Directional Smoothness and Gradient Methods: Convergence and Adaptivitycited by 15
  5. 2024Revisiting Convergence of AdaGrad with Relaxed Assumptionscited by 14
  6. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 13
  7. 2024Stochastic Weakly Convex Optimization Beyond Lipschitz Continuitycited by 3
  8. 2023Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Setscited by 2
  9. 2023Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuitycited by 2
  10. 2023A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functionscited by 2
  11. 2025Glocal Smoothness: Line search and adaptive step sizes can help in theory too!cited by 2
  12. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 2
6 more
  1. 2022Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimizationcited by 1
  2. 2024Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspectivecited by 1
  3. 2024Towards Stability of Parameter-Free Optimizationcited by 1
  4. 2024Learning-Rate-Free Stochastic Optimization over Riemannian Manifoldscited by 1
  5. 2026Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizescited by 1
  6. 2023Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimizationcited by 0