Continuous and Discrete-time Accelerated Stochastic Mirror Descent for Strongly Convex Functions

Pan Xu, Tianhao Wang, Quanquan Gu
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:5492-5501, 2018.

Abstract

We provide a second-order stochastic differential equation (SDE), which characterizes the continuous-time dynamics of accelerated stochastic mirror descent (ASMD) for strongly convex functions. This SDE plays a central role in designing new discrete-time ASMD algorithms via numerical discretization, and providing neat analyses of their convergence rates based on Lyapunov functions. Our results suggest that the only existing ASMD algorithm, namely, AC-SA proposed in Ghadimi & Lan (2012) is one instance of its kind, and we can actually derive new instances of ASMD with fewer tuning parameters. This sheds light on revisiting accelerated stochastic optimization through the lens of SDEs, which can lead to a better understanding of acceleration in stochastic optimization, as well as new simpler algorithms. Numerical experiments on both synthetic and real data support our theory.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-xu18g, title = {Continuous and Discrete-time Accelerated Stochastic Mirror Descent for Strongly Convex Functions}, author = {Xu, Pan and Wang, Tianhao and Gu, Quanquan}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {5492--5501}, 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/xu18g/xu18g.pdf}, url = {https://proceedings.mlr.press/v80/xu18g.html}, abstract = {We provide a second-order stochastic differential equation (SDE), which characterizes the continuous-time dynamics of accelerated stochastic mirror descent (ASMD) for strongly convex functions. This SDE plays a central role in designing new discrete-time ASMD algorithms via numerical discretization, and providing neat analyses of their convergence rates based on Lyapunov functions. Our results suggest that the only existing ASMD algorithm, namely, AC-SA proposed in Ghadimi & Lan (2012) is one instance of its kind, and we can actually derive new instances of ASMD with fewer tuning parameters. This sheds light on revisiting accelerated stochastic optimization through the lens of SDEs, which can lead to a better understanding of acceleration in stochastic optimization, as well as new simpler algorithms. Numerical experiments on both synthetic and real data support our theory.} }
Endnote
%0 Conference Paper %T Continuous and Discrete-time Accelerated Stochastic Mirror Descent for Strongly Convex Functions %A Pan Xu %A Tianhao Wang %A Quanquan Gu %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-xu18g %I PMLR %P 5492--5501 %U https://proceedings.mlr.press/v80/xu18g.html %V 80 %X We provide a second-order stochastic differential equation (SDE), which characterizes the continuous-time dynamics of accelerated stochastic mirror descent (ASMD) for strongly convex functions. This SDE plays a central role in designing new discrete-time ASMD algorithms via numerical discretization, and providing neat analyses of their convergence rates based on Lyapunov functions. Our results suggest that the only existing ASMD algorithm, namely, AC-SA proposed in Ghadimi & Lan (2012) is one instance of its kind, and we can actually derive new instances of ASMD with fewer tuning parameters. This sheds light on revisiting accelerated stochastic optimization through the lens of SDEs, which can lead to a better understanding of acceleration in stochastic optimization, as well as new simpler algorithms. Numerical experiments on both synthetic and real data support our theory.
APA
Xu, P., Wang, T. & Gu, Q.. (2018). Continuous and Discrete-time Accelerated Stochastic Mirror Descent for Strongly Convex Functions. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:5492-5501 Available from https://proceedings.mlr.press/v80/xu18g.html.

Related Material