Increasing Iterate Averaging for Solving Saddle-Point Problems
This addresses the problem of faster convergence in saddle-point problems for machine learning and game theory practitioners, offering an incremental improvement over existing averaging methods.
The paper tackles the slow convergence of uniform averages in first-order methods for saddle-point problems by proposing increasing averaging schemes that weight later iterates more heavily, achieving a $O(1/T)$ convergence rate without extra assumptions and outperforming uniform averages by orders of magnitude in experiments, including beating CFR$^+$ in matrix games.
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.