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

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.