Improved Step-Size Schedules for Noisy Gradient Methods
| Autor: | Sarit Khirirat, Sindri Magnusson, Xiaoyu Wang, Mikael Johansson |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Optimization
distributed algorithms Signal processing Computer science Approximation algorithm Control Engineering Noise Global optimum machine learning Reglerteknik Compression (functional analysis) Convergence (routing) Optimization methods zeroth-order algorithms Signal processing algorithms quantization Algorithm |
| Zdroj: | ICASSP |
| Popis: | 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 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. Part of proceedings: ISBN 978-1-7281-7605-5, QC 20230117 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|