An Optimal Multistage Stochastic Gradient Method for Minimax Problems
  In this paper, we study the minimax optimization problem in the smooth and
strongly convex-strongly concave setting when we have access to noisy estimates
of gradients. In particular, we first analyze the stochastic Gradient Descent
Ascent (GDA) method with constant stepsize, and show that it converges to a
neighborhood of the solution of the minimax problem. We further provide tight
bounds on the convergence rate and the size of this neighborhood. Next, we
propose a multistage variant of stochastic GDA (M-GDA) that runs in multiple
stages with a particular learning rate decay schedule and converges to the
exact solution of the minimax problem. We show M-GDA achieves the lower bounds
in terms of noise dependence without any assumptions on the knowledge of noise
characteristics. We also show that M-GDA obtains a linear decay rate with
respect to the error's dependence on the initial error, although the dependence
on condition number is suboptimal. In order to improve this dependence, we
apply the multistage machinery to the stochastic Optimistic Gradient Descent
Ascent (OGDA) algorithm and propose the M-OGDA algorithm which also achieves
the optimal linear decay rate with respect to the initial error. To the best of
our knowledge, this method is the first to simultaneously achieve the best
dependence on noise characteristic as well as the initial error and condition
number.
