Timezone: »

 
Poster
Accelerated Mirror Descent in Continuous and Discrete Time
Walid Krichene · Alexandre Bayen · Peter Bartlett

Wed Dec 09 04:00 PM -- 08:59 PM (PST) @ 210 C #96
in Poster Session »
We study accelerated mirror descent dynamics in continuous and discrete time. Combining the original continuous-time motivation of mirror descent with a recent ODE interpretation of Nesterov's accelerated method, we propose a family of continuous-time descent dynamics for convex functions with Lipschitz gradients, such that the solution trajectories are guaranteed to converge to the optimum at a $O(1/t^2)$ rate. We then show that a large family of first-order accelerated methods can be obtained as a discretization of the ODE, and these methods converge at a $O(1/k^2)$ rate. This connection between accelerated mirror descent and the ODE provides an intuitive approach to the design and analysis of accelerated first-order algorithms.
[ PDF] 

Author Information

Walid Krichene (UC Berkeley)
Alexandre Bayen (UC Berkeley)
Peter Bartlett (UC Berkeley)

More from the Same Authors