- Main
Accelerated Mirror Descent in Continuous and Discrete Time
- Krichene, Walid;
- Bayen, Alexandre M;
- Bartlett, Peter L
- Editor(s): Cortes, Corinna;
- Lawrence, Neil D;
- Lee, Daniel D;
- Sugiyama, Masashi;
- Garnett, Roman
Abstract
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 converge to the optimum at a O(1/t2) 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/k2) rate. This connection between accelerated mirror descent and the ODE provides an intuitive approach to the design and analysis of accelerated first-order algorithms.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.