Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for
  Smooth Minimax Games
  We consider the problem of online learning and its application to solving
minimax games. For the online learning problem, Follow the Perturbed Leader
(FTPL) is a widely studied algorithm which enjoys the optimal $O(T^{1/2})$
worst-case regret guarantee for both convex and nonconvex losses. In this work,
we show that when the sequence of loss functions is predictable, a simple
modification of FTPL which incorporates optimism can achieve better regret
guarantees, while retaining the optimal worst-case regret guarantee for
unpredictable sequences. A key challenge in obtaining these tighter regret
bounds is the stochasticity and optimism in the algorithm, which requires
different analysis techniques than those commonly used in the analysis of FTPL.
The key ingredient we utilize in our analysis is the dual view of perturbation
as regularization. While our algorithm has several applications, we consider
the specific application of minimax games. For solving smooth convex-concave
games, our algorithm only requires access to a linear optimization oracle. For
Lipschitz and smooth nonconvex-nonconcave games, our algorithm requires access
to an optimization oracle which computes the perturbed best response. In both
these settings, our algorithm solves the game up to an accuracy of
$O(T^{-1/2})$ using $T$ calls to the optimization oracle. An important feature
of our algorithm is that it is highly parallelizable and requires only
$O(T^{1/2})$ iterations, with each iteration making $O(T^{1/2})$ parallel calls
to the optimization oracle.
