Acceleration through Optimistic No-Regret Dynamics

Abstract

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}.

Cited by in corpus (10)

• Hedging in games: Faster convergence of external and swap regrets
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• Local and Global Uniform Convexity Conditions
• Dynamic Data-Driven Estimation of Non-Parametric Choice Models
• Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Games
• Non-Asymptotic Pure Exploration by Solving Games
• Efficient Online-Bandit Strategies for Minimax Learning Problems
• Anytime Online-to-Batch Conversions, Optimism, and Acceleration
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Linear Separation via Optimism