Accelerated Stochastic Mirror Descent: From Continuous-Time Dynamics to Discrete-Time Algorithms
Abstract
We present a new framework to analyze accelerated stochastic mirror descent through the lens of continuous-time stochastic dynamic systems. It enables us to design new algorithms, and perform a unified and simple analysis of the convergence rates of these algorithms. More specifically, under this framework, we provide a Lyapunov function based analysis for the continuous-time stochastic dynamics, as well as several new discrete-time algorithms derived from the continuous-time dynamics. We show that for general convex objective functions, the derived discrete-time algorithms attain the optimal convergence rate. Empirical experiments corroborate our theory.
Cite
Text
Xu et al. "Accelerated Stochastic Mirror Descent: From Continuous-Time Dynamics to Discrete-Time Algorithms." International Conference on Artificial Intelligence and Statistics, 2018.Markdown
[Xu et al. "Accelerated Stochastic Mirror Descent: From Continuous-Time Dynamics to Discrete-Time Algorithms." International Conference on Artificial Intelligence and Statistics, 2018.](https://mlanthology.org/aistats/2018/xu2018aistats-accelerated-a/)BibTeX
@inproceedings{xu2018aistats-accelerated-a,
title = {{Accelerated Stochastic Mirror Descent: From Continuous-Time Dynamics to Discrete-Time Algorithms}},
author = {Xu, Pan and Wang, Tianhao and Gu, Quanquan},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2018},
pages = {1087-1096},
url = {https://mlanthology.org/aistats/2018/xu2018aistats-accelerated-a/}
}