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

[edit]

Pan Xu, Tianhao Wang, Quanquan Gu ;
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1087-1096, 2018.

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.

Related Material