Acceleration through Optimistic No-Regret Dynamics
We consider the problem of minimizing a smooth convex function by reducing the optimization to computing the Nash equilibrium of a particular zero-sum convexconcave game. Zero-sum games can be solved using online learning dynamics, where a classical technique involves simulating two no-regret algorithms that play against each other and, after T rounds, the average iterate is guaranteed to solve the original optimization problem with error decaying as O(log T /T ). In this paper we show that the technique can be enhanced to a rate of O(1/T 2 ) by extending recent work [22,25] that leverages optimistic learning to speed up equilibrium computation. The resulting optimization algorithm derived from this analysis coincides exactly with the well-known NESTEROVACCELERATION [16] method, and indeed the same story allows us to recover several variants of the Nesterov's algorithm via small tweaks. We are also able to establish the accelerated linear rate for a function which is both strongly-convex and smooth. This methodology unifies a number of different iterative optimization methods: we show that the HEAVYBALL algorithm is precisely the non-optimistic variant of NESTEROVACCELERATION, and recent prior work already established a similar perspective on FRANKWOLFE [2, 1].
This paper shows that Nesterov’s accelerated gradient descent algorithms can be interpreted as computing a saddle point via online optimization algorithms. A convex optimization problem is transformed to be a minmax problem by the Fenchel dual, the solution of which is then approximated via online optimization algorithms.   This paper can be a significant contribution to the optimization community. I would say that this is one of the most natural interpretations of Nesterov’s accelerated gradient methods. The use of weighted regrets and (optimistic) FollowTheLeader (instead of follow the regularized leader) are a little bit artificial but acceptable. The latter is perhaps easier to accept, if the authors point out that \ell_t is strongly convex due to smoothness of f.   A possible issue is boundedness of the radius D in Section 4. To use Theorem 2 and Corollary 1 to prove the accelerated convergence rate, one has to provide an upper bound of the radius D. It is not immediate to me whether D is actually bounded or not in Section 4. (In Section 4.2, there is a constraint set K, but boundedness of K is not mentioned.)  Other comments:  1. ln 135: It seems that \ell_t(y) should be equal to -g(x_{t - 1}, y) instead of -g(x_t, y), according to Algorithm 1. Please check.  2. ln 4, Algorithm 2: The x in \nabal h_t (x) is not defined, though this is not really relevant.  3. Theorem 3: You need to specify \gamma to use Theorem 2 and Corollary 1.