On Acceleration with Noise-Corrupted Gradients

Michael Cohen, Jelena Diakonikolas, Lorenzo Orecchia
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1019-1028, 2018.

Abstract

Accelerated algorithms have broad applications in large-scale optimization, due to their generality and fast convergence. However, their stability in the practical setting of noise-corrupted gradient oracles is not well-understood. This paper provides two main technical contributions: (i) a new accelerated method AGDP that generalizes Nesterov’s AGD and improves on the recent method AXGD (Diakonikolas & Orecchia, 2018), and (ii) a theoretical study of accelerated algorithms under noisy and inexact gradient oracles, which is supported by numerical experiments. This study leverages the simplicity of AGDP and its analysis to clarify the interaction between noise and acceleration and to suggest modifications to the algorithm that reduce the mean and variance of the error incurred due to the gradient noise.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-cohen18a, title = {On Acceleration with Noise-Corrupted Gradients}, author = {Cohen, Michael and Diakonikolas, Jelena and Orecchia, Lorenzo}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {1019--1028}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/cohen18a/cohen18a.pdf}, url = {https://proceedings.mlr.press/v80/cohen18a.html}, abstract = {Accelerated algorithms have broad applications in large-scale optimization, due to their generality and fast convergence. However, their stability in the practical setting of noise-corrupted gradient oracles is not well-understood. This paper provides two main technical contributions: (i) a new accelerated method AGDP that generalizes Nesterov’s AGD and improves on the recent method AXGD (Diakonikolas & Orecchia, 2018), and (ii) a theoretical study of accelerated algorithms under noisy and inexact gradient oracles, which is supported by numerical experiments. This study leverages the simplicity of AGDP and its analysis to clarify the interaction between noise and acceleration and to suggest modifications to the algorithm that reduce the mean and variance of the error incurred due to the gradient noise.} }
Endnote
%0 Conference Paper %T On Acceleration with Noise-Corrupted Gradients %A Michael Cohen %A Jelena Diakonikolas %A Lorenzo Orecchia %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-cohen18a %I PMLR %P 1019--1028 %U https://proceedings.mlr.press/v80/cohen18a.html %V 80 %X Accelerated algorithms have broad applications in large-scale optimization, due to their generality and fast convergence. However, their stability in the practical setting of noise-corrupted gradient oracles is not well-understood. This paper provides two main technical contributions: (i) a new accelerated method AGDP that generalizes Nesterov’s AGD and improves on the recent method AXGD (Diakonikolas & Orecchia, 2018), and (ii) a theoretical study of accelerated algorithms under noisy and inexact gradient oracles, which is supported by numerical experiments. This study leverages the simplicity of AGDP and its analysis to clarify the interaction between noise and acceleration and to suggest modifications to the algorithm that reduce the mean and variance of the error incurred due to the gradient noise.
APA
Cohen, M., Diakonikolas, J. & Orecchia, L.. (2018). On Acceleration with Noise-Corrupted Gradients. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:1019-1028 Available from https://proceedings.mlr.press/v80/cohen18a.html.

Related Material