Directional Smoothness and Gradient Methods: Convergence and Adaptivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909455266873344 |
|---|---|
| author | Mishkin, Aaron Khaled, Ahmed Wang, Yuanhao Defazio, Aaron Gower, Robert M. |
| author_facet | Mishkin, Aaron Khaled, Ahmed Wang, Yuanhao Defazio, Aaron Gower, Robert M. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04081 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Directional Smoothness and Gradient Methods: Convergence and Adaptivity Mishkin, Aaron Khaled, Ahmed Wang, Yuanhao Defazio, Aaron Gower, Robert M. Machine Learning Optimization and Control 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. |
| title | Directional Smoothness and Gradient Methods: Convergence and Adaptivity |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2403.04081 |