Increasing Iterate Averaging for Solving Saddle-Point Problems
  Many problems in machine learning and game theory can be formulated as
saddle-point problems, for which various first-order methods have been
developed and proven efficient in practice. Under the general convex-concave
assumption, most first-order methods only guarantee an ergodic convergence
rate, that is, the uniform averages of the iterates converge at a $O(1/T)$ rate
in terms of the saddle-point residual. However, numerically, the iterates
themselves can often converge much faster than the uniform averages. This
observation motivates increasing averaging schemes that put more weight on
later iterates, in contrast to the usual uniform averaging. We show that such
increasing averaging schemes, applied to various first-order methods, are able
to preserve the $O(1/T)$ convergence rate with no additional assumptions or
computational overhead. Extensive numerical experiments on zero-sum game
solving, market equilibrium computation and image denoising demonstrate the
effectiveness of the proposed schemes. In particular, the increasing averages
consistently outperform the uniform averages in all test problems by orders of
magnitude. When solving matrix and extensive-form games, increasing averages
consistently outperform the last iterates as well. For matrix games, a
first-order method equipped with increasing averaging outperforms the highly
competitive CFR$^+$ algorithm.
