# Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under (L0,L1)-Smoothness

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Dec 2024.

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

- [On the Interaction of Batch Noise, Adaptivity, and Compression, under (L0,L1)-Smoothness: An SDE Approach](https://mlsanity.com/paper/2506.00181/) (2025)
- [Smoothed Normalization for Efficient Distributed Private Optimization](https://mlsanity.com/paper/2502.13482/) (2025)
- [Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L0, L1)-Smoothness](https://mlsanity.com/paper/2508.06884/) (2025)
- [Decentralized Stochastic Nonconvex Optimization under the (L0,L1)-Smoothness](https://mlsanity.com/paper/2509.08726/) (2025)

## Abstract (arXiv)

The gradient descent (GD) method -- is a fundamental and likely the most popular optimization algorithm in machine learning (ML), with a history traced back to a paper in 1847 (Cauchy, 1847). It was studied under various assumptions, including so-called (L0,L1)-smoothness, which received noticeable attention in the ML community recently. In this paper, we provide a refined convergence analysis of gradient descent and its variants, assuming generalized smoothness. In particular, we show that (L0,L1)-GD has the following behavior in the convex setup: as long as |nabla f(xk)| ≥ fracL0L1 the algorithm has linear convergence in function suboptimality, and when |nabla f(xk)| < fracL0L1 is satisfied, (L0,L1)-GD has standard sublinear rate. Moreover, we also show that this behavior is common for its variants with different types of oracle: Normalized Gradient Descent as well as Clipped Gradient Descent (the case when the full gradient nabla f(x) is available); Random Coordinate Descent (when the gradient component nablai f(x) is available); Random Coordinate Descent with Order Oracle (when only sign [f(y) - f(x)] is available). In addition, we also extend our analysis of (L0,L1)-GD to the strongly convex case.