Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity

By Benjamin Grimmer. 2017

57 citations recorded by the source corpus.

We generalize the classic convergence rate theory for subgradient methods to apply to non-Lipschitz functions via a new measure of steepness. For the deterministic projected subgradient method, we derive a global $O(1/\sqrt{T})$ convergence rate for any function with at most exponential growth. Our approach 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/\sqrt{T})$ convergence rate for the stochastic projected subgradient method on functions with at most quadratic growth, which improves to $O(1/T)$ under strong convexity.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

The Value of Collaboration in Convex Machine Learning with Differential Privacy (2019, background): “In fact, we can select a constant learning rate to extract the non-private model; see [32] for convergence analysis of optimization algorithms with constant steps sizes.”
Better Theory for SGD in the Nonconvex World (2020, background): “There are only a handful of results under QFG (Drusvyatskiy & Lewis, 2018; Necoara et al., 2019; Grimmer, 2019) and only one applies to our setting (Grimmer, 2019).”
Unified Optimal Analysis of the (Stochastic) Gradient Method (2019, background): “Lemma 7 below, or (Stich et al., 2018; Grimmer, 2019)) gives f(x̄T )−f⋆ = O ( L(2)R(2) μT 2 + σ(2) μT )”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, background): “[14] Benjamin Grimmer.”