Directional Smoothness and Gradient Methods: Convergence and Adaptivity
<|reference_start|>Directional Smoothness and Gradient Methods: Convergence and Adaptivity: 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.<|reference_end|>
@article{mishkin2024directional,
    title={Directional Smoothness and Gradient Methods: Convergence and Adaptivity},
    author={Aaron Mishkin, Ahmed Khaled, Yuanhao Wang, Aaron Defazio, and Robert
  M. Gower},
    journal={arXiv preprint arXiv:2403.04081},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.04081},
    primaryClass={cs.LG math.OC}
}