Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under (L₀,L₁)-Smoothness

2024/12/22 by Aleksandr Lobanov, Lobanov, Aleksandr, Alexander Gasnikov +5 · 4 citations
Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Iterative Methods for Nonlinear Equations #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2412.17050

openalex publication_date 2024/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 (L₀,L₁)-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 (L₀,L₁)-GD has the following behavior in the convex setup: as long as ‖∇ f(x^k)‖ ≥ (L₀)/(L₁) the algorithm has linear convergence in function suboptimality, and when ‖∇ f(x^k)‖ < (L₀)/(L₁) is satisfied, (L₀,L₁)-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 ∇ f(x) is available); Random Coordinate Descent (when the gradient component ∇_i 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 (L₀,L₁)-GD to the strongly convex case.

Cited by

• Frank-Wolfe Algorithms for (L0, L1)-smooth functions
• Decentralized Stochastic Nonconvex Optimization under the (L₀,L₁)-Smoothness
• Decentralized Relaxed Smooth Optimization with Gradient Descent Methods
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L₀, L₁)-Smoothness

Related

• Methods for Convex (L₀,L₁)-Smooth Optimization: Clipping, Acceleration, and Adaptivity
• Power of Generalized Smoothness in Stochastic Convex Optimization: First- and Zero-Order Algorithms
• Convergence of Clipped SGD on Convex (L₀,L₁)-Smooth Functions
• Optimizing (L₀, L₁)-Smooth Functions by Gradient Methods
• Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition