Directional Smoothness and Gradient Methods: Convergence and Adaptivity
Aaron Mishkin Ahmed Khaled Yuanhao Wang Aaron Defazio Robert M. Gower
We develop new sub-optimality bounds for gradient descent (GD) 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 implicit equations to
obtain a sequence of strongly adapted step-sizes; we show that these equations
are straightforward to solve for convex quadratics and lead to new guarantees
for two classical step-sizes. For general functions, we prove that the Polyak
step-size and normalized GD obtain fast, path-dependent rates despite using no
knowledge of the directional smoothness. Experiments on logistic regression
show our convergence guarantees are tighter than the classical theory based on
L-smoothness.