Toward a Unified Theory of Gradient Descent under Generalized Smoothness

We study the classical optimization problem minx ∈ ℝd f(x) and analyze the gradient descent (GD) method in both nonconvex and convex settings. It is well-known that, under the L-smoothness assumption (|nabla2 f(x)| ≤ L), the optimal point minimizing the quadratic upper bound f(xk) + langlenabla f(xk), xk+1 - xkrangle + fracL2 |xk+1 - xk|2 is xk+1 = xk - γk nabla f(xk) with step size γk = frac1L. Surprisingly, a similar result can be derived under the ℓ-generalized smoothness assumption (|nabla2 f(x)| ≤ ℓ(|nabla f(x)|)). In this case, we derive the step size γk = int01 fracd vℓ(|nabla f(xk)| + |nabla f(xk)| v). Using this step size rule, we improve upon existing theoretical convergence rates and obtain new results in several previously unexplored setups.