Timezone: »

Continuous and Discrete-time Accelerated Stochastic Mirror Descent for Strongly Convex Functions
Pan Xu · Tianhao Wang · Quanquan Gu

Fri Jul 13 07:40 AM -- 07:50 AM (PDT) @ A9

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 \citet{ghadimi2012optimal} 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.

Author Information

Pan Xu (University of California, Los Angeles)
Tianhao Wang (University of Science and Technology of China)
Quanquan Gu (UCLA)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors