Accelerated Stochastic Mirror Descent: From Continuous-time Dynamics to Discrete-time Algorithms

@InProceedings{pmlr-v84-xu18e,
  title = 	 {Accelerated Stochastic Mirror Descent: From Continuous-time Dynamics to Discrete-time Algorithms},
  author = 	 {Xu, Pan and Wang, Tianhao and Gu, Quanquan},
  booktitle = 	 {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics},
  pages = 	 {1087--1096},
  year = 	 {2018},
  editor = 	 {Storkey, Amos and Perez-Cruz, Fernando},
  volume = 	 {84},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {09--11 Apr},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v84/xu18e/xu18e.pdf},
  url = 	 {https://proceedings.mlr.press/v84/xu18e.html},
  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.}
}