Toward a Unified Theory of Gradient Descent under Generalized Smoothness

We study the classical optimization problem ${\min }_{x\in {\mathbb{R}}^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 ($\mathrm{\parallel }{\mathrm{\nabla }}^{2}f(x)\mathrm{\parallel }\le L$), the optimal point minimizing the quadratic upper bound $f(x_k)+⟨\mathrm{\nabla }f(x_k),x_{k+1}-x_k⟩+\frac{L}{2}\mathrm{\parallel }{x}_{k+1}-x_k{\mathrm{\parallel }}^2$ is $x_{k+1}=x_k-{\gamma }_k\mathrm{\nabla }f(x_k)$ with step size ${\gamma }_k=\frac{1}{L}$. Surprisingly, a similar result can be derived under the $\mathrm{\ell }$-generalized smoothness assumption ($\mathrm{\parallel }{\mathrm{\nabla }}^{2}f(x)\mathrm{\parallel }\le \mathrm{\ell }(\mathrm{\parallel }\mathrm{\nabla }f(x)\mathrm{\parallel })$). In this case, we derive the step size $${\gamma }_k={\int }_0^1\frac{dv}{\mathrm{\ell }(\mathrm{\parallel }\mathrm{\nabla }f(x_k)\mathrm{\parallel }+\mathrm{\parallel }\mathrm{\nabla }f(x_k)\mathrm{\parallel }v)}\mathrm{.}$$ Using this step size rule, we improve upon existing theoretical convergence rates and obtain new results in several previously unexplored setups.