Adaptive Averaging in Accelerated Descent Dynamics
We study accelerated descent dynamics for constrained convex optimization. This dynamics can be described naturally as a coupling of a dual variable accumulating gradients at a given rate η(t), and a primal variable obtained as the weighted average of the mirrored dual trajectory, with weights w(t). Using a Lyapunov argument, we give sufficient conditions on η and w to achieve a desired convergence rate. As an example, we show that the replicator dynamics (an example of mirror descent on the simplex) can be accelerated using a simple averaging scheme. We then propose an adaptive averaging heuristic which adaptively computes the weights to speed up the decrease of the Lyapunov function. We provide guarantees on adaptive averaging in continuous-time, prove that it preserves the quadratic convergence rate of accelerated first-order methods in discrete-time, and give numerical experiments to compare it with existing heuristics, such as adaptive restarting. The experiments indicate that adaptive averaging performs at least as well as adaptive restarting, with significant improvements in some cases.
Building upon an early work that connects accelerated Mirror Descent and continuous-time ODE, the authors extend the ODE dynamics with a more general averaging scheme and propose a novel adaptive averaging strategy for one of its discretization. In some cases, the new variant of AMD with adaptive averaging outperforms existing AMD algorithms with restarting. 
The proposed adaptive averaging strategy is interestingly new and comes with a good intuition. While the paper looks nice overall, the originality and usefulness remains a big concern.   - Most elements (e.g. Lyapunov function, discretization, etc.)  directly follow from an early NIPS paper [7]. The extension from simple averaging to generalized averaging is kind of trivial and not of much use since eventually the authors only consider the case with quadratic rate; faster rate would require higher-order methods which are not always applicable.    - Some results, e.g.,  interpretation of energy function, reformulation into primal form, reduction to replicator dynamics, promote a better understanding of accelerated Mirror Descent algorithm, but are not significantly important to advance machine learning.   - Although the  adaptive averaging is introduced to satisfy the conditions sufficient to guarantee convergence of ODE, it is not fully theoretically grounded due to the approximation during discretization. Still, there is no explicit convergent result provided, meaning it is again just  a heuristic, as referred by the authors. Also, there exist a number of different averaging schemes of Nester's accelerated algorithms; without comparing to other alternatives, it is unclear whether this adaptive variant makes a big different.   - The experiment on a toy example with only quadratic/linear objective is not interesting or convincing enough to demonstrate the adavantage with adaptive averaging, especially for the general case with strongly convexity.     == post-rebuttal answer== I have read the authors' rebuttal and they promise to add - additional higher dimensional and non-quadratic examples in the revision - theoretical proof of convergence of adaptive averaging - implementation of adaptive averaging on Nesterov's cubic-regulariezed Newton method - discussion comparing to other adaptive averaging   I have updated my scores accordingly.