Review for NeurIPS paper: Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games

Summary and Contributions: - It is known in the literature that optimistic variants of FTRL algorithm can yield better bounds when the sequence of loss functions are predictable. Such results are relatively rare for FTPL. This paper proposes the optimistic variant of the FTPL algorithm, which in the worst case known optimal bounds, but has the potential to achieve better regret for predictable sequence of loss functions. Specifically, the bounds depend on the g_t - abla_t _* where g_t is the estimate of the gradient for the next loss function and abla_t is the observed gradient. They instantiate this generic result for the worst case analysis via treating the future estimate g_t 0 and achieve the optimal O(T {\frac{1}{2}}) regret.