32. Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under (L0,L1)-Smoothness
Invited abstract in session WC-6: Structured nonsmooth optimization -- Part III, stream Nonsmooth and nonconvex optimization.
Wednesday, 14:00-16:00Room: B100/7013
Authors (first author is the speaker)
| 1. | Aleksandr Lobanov
|
| Moscow Institute of Physics and Technology (MIPT) |
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). In this paper, we provide an improved convergence analysis of gradient descent and its variants, assuming generalized smoothness (L0,L1). In particular, we show that GD has the following behavior of convergence in the convex setup: At first, the algorithm has linear convergence, and approaching the solution, has standard sublinear rate. Moreover, we show that this behavior of convergence is also common for its variants using different types of oracle: Normalized Gradient Descent as well as Clipped Gradient Descent (the case when the oracle has access to the full gradient); Random Coordinate Descent (when the oracle has access only to the gradient component); Random Coordinate Descent with Order Oracle (when the oracle has access only to the comparison value of the objective function). In addition, we also analyze the behavior of convergence rate of GD algorithm in a strongly convex setup.
Keywords
- Global optimization
- First-order optimization
- Complexity and efficiency of algorithms
Status: accepted
Back to the list of papers