A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics

Yuchen Zhang, Percy Liang, Moses Charikar
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1980-2022, 2017.

Abstract

We study the Stochastic Gradient Langevin Dynamics (SGLD) algorithm for non-convex optimization. The algorithm performs stochastic gradient descent, where in each step it injects appropriately scaled Gaussian noise to the update. We analyze the algorithm’s hitting time to an arbitrary subset of the parameter space. Two results follow from our general theory: First, we prove that for empirical risk minimization, if the empirical risk is point-wise close to the (smooth) population risk, then the algorithm achieves an approximate local minimum of the population risk in polynomial time, escaping suboptimal local minima that only exist in the empirical risk. Second, we show that SGLD improves on one of the best known learnability results for learning linear classifiers under the zero-one loss.

Cite this Paper

BibTeX
@InProceedings{pmlr-v65-zhang17b, title = {A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics}, author = {Zhang, Yuchen and Liang, Percy and Charikar, Moses}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {1980--2022}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/zhang17b/zhang17b.pdf}, url = {https://proceedings.mlr.press/v65/zhang17b.html}, abstract = {We study the Stochastic Gradient Langevin Dynamics (SGLD) algorithm for non-convex optimization. The algorithm performs stochastic gradient descent, where in each step it injects appropriately scaled Gaussian noise to the update. We analyze the algorithm’s hitting time to an arbitrary subset of the parameter space. Two results follow from our general theory: First, we prove that for empirical risk minimization, if the empirical risk is point-wise close to the (smooth) population risk, then the algorithm achieves an approximate local minimum of the population risk in polynomial time, escaping suboptimal local minima that only exist in the empirical risk. Second, we show that SGLD improves on one of the best known learnability results for learning linear classifiers under the zero-one loss.} }
Endnote
%0 Conference Paper %T A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics %A Yuchen Zhang %A Percy Liang %A Moses Charikar %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-zhang17b %I PMLR %P 1980--2022 %U https://proceedings.mlr.press/v65/zhang17b.html %V 65 %X We study the Stochastic Gradient Langevin Dynamics (SGLD) algorithm for non-convex optimization. The algorithm performs stochastic gradient descent, where in each step it injects appropriately scaled Gaussian noise to the update. We analyze the algorithm’s hitting time to an arbitrary subset of the parameter space. Two results follow from our general theory: First, we prove that for empirical risk minimization, if the empirical risk is point-wise close to the (smooth) population risk, then the algorithm achieves an approximate local minimum of the population risk in polynomial time, escaping suboptimal local minima that only exist in the empirical risk. Second, we show that SGLD improves on one of the best known learnability results for learning linear classifiers under the zero-one loss.
APA
Zhang, Y., Liang, P. & Charikar, M.. (2017). A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:1980-2022 Available from https://proceedings.mlr.press/v65/zhang17b.html.

Related Material