Timezone: »

 
Spotlight
Acceleration through Optimistic No-Regret Dynamics
Jun-Kun Wang · Jacob Abernethy

Wed Dec 05 07:20 AM -- 07:25 AM (PST) @ Room 220 CD
in Wed Track 1 -- Session 1 »
We consider the problem of minimizing a smooth convex function by reducing the optimization to computing the Nash equilibrium of a particular zero-sum convex-concave 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 \cite{RS13,SALS15} that leverages \textit{optimistic learning} to speed up equilibrium computation. The resulting optimization algorithm derived from this analysis coincides \textit{exactly} with the well-known \NA \cite{N83a} 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 \HB algorithm is precisely the non-optimistic variant of \NA, and recent prior work already established a similar perspective on \FW \cite{AW17,ALLW18}.

Author Information

Jun-Kun Wang (Georgia Institute of Technology)
Jacob Abernethy (Georgia Institute of Technolog)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors