@inproceedings{
mishkin2023a,
title={A novel analysis of gradient descent under directional smoothness},
author={Aaron Mishkin and Ahmed Khaled and Aaron Defazio and Robert M. Gower},
booktitle={OPT 2023: Optimization for Machine Learning},
year={2023},
url={https://openreview.net/forum?id=exgeMa9fB5}
}
We develop new sub-optimality bounds for gradient descent that depend on the conditioning of the objective along the path of optimization, rather than on global, worst-case constants. Key to our proofs is directional smoothness, a measure of gradient variation that we use to develop upper-bounds on the objective. Minimizing these upper-bounds requires solving an implicit equation to obtain an adapted step-size; we show that this equation is straightforward to solve for convex quadratics and leads to new guarantees for a classical step-size sequence. For general functions, we prove that exponential search can be used to obtain a path-dependent convergence guarantee with only a log-log dependency on the global smoothness constant. Experiments on quadratic functions showcase the utility of our theory and connections to the edge-of-stability phenomenon.
A novel analysis of gradient descent under directional smoothness
Aaron Mishkin Ahmed Khaled Aaron Defazio Robert M. Gower