Accelerated Mirror Descent in Continuous and Discrete Time
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/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.
The paper combines the ODE interpretation of mirror descent with the work of [25], which interprets AGD as a discretized ODE, to formulate an ODE system that corresponds to what should be accelerated mirror descent. Proofs of existence, uniqueness, and convergence follow standard ODE methods using compactness and contraction mappings. Discretizing the ODE yields the derivation of discrete-time accelerated mirror descent methods, one example of which is accelerated entropic descent. The authors provide experiments validating the improvement of accelerated entropic descent over its non-accelerated variant.     Quality: The paper is relatively well-written, outlining recent work in the field, motivating its contribution, and methodically arriving at concrete algorithms at the end.Clarity: The authors mention and leverage the Cauchy-Lipschitz theorem many times throughout the paper, but not once provide an exact statement or a reference. Since the theorem is sometimes presented in different forms, it seems important to cite it precisely. It is not clear why the 2nd inequality on line 251 is true. It is also not clear why the 2nd inequality in the proof of Lemma 2 on page 5 of the supplementary material is true. [15] is cited improperly without any journal or conference reference.EDIT: The authors addressed many of these complaints in their rebuttal.Originality: The formulation of accelerated mirror descent is a natural extension of recent work, but to the best of the reviewer's knowledge, new. Significance: The results are new, but the proof techniques and ideas are relatively standard extensions to what exists in the literature. The experiments seem to indicate that the algorithms present an improvement upon commonly used methods.