Improved Step-Size Schedules for Noisy Gradient Methods
Lists
Only you see this
Abstract
Noise is inherited in many optimization methods such as stochastic gradient methods, zeroth-order methods and compressed gradient methods. For such methods to converge toward a global optimum, it is intuitive to use large step-sizes in the initial iterations when the noise is typically small compared to the algorithm-steps, and reduce the step-sizes as the algorithm progresses. This intuition has been con-firmed in theory and practice for stochastic gradient methods, but similar results are lacking for other methods using approximate gradients. This paper shows that the diminishing step-size strategies can indeed be applied for a broad class of noisy gradient methods. Unlike previous works, our analysis framework shows that such step-size schedules enable these methods to enjoy an optimal $\mathcal{O}(1/k)$ rate. We exemplify our results on zeroth-order methods and stochastic compression methods. Our experiments validate fast convergence of these methods with the step decay schedules.
BibTeX
@inproceedings{khirirat2021improved,
author = {Sarit Khirirat and Xiaoyu Wang and Sindri Magnússon and Mikael Johansson},
title = {{Improved Step-Size Schedules for Noisy Gradient Methods}},
booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
year = {2021},
url = {https://openreview.net/forum?id=01fxahZPYk},
}Loading related content...