Increasing Iterate Averaging for Solving Saddle-Point Problems

Authors

  • Yuan Gao Columbia University
  • Christian Kroer Columbia University
  • Donald Goldfarb Columbia University

Keywords:

Optimization, Equilibrium, Game Theory, Imperfect Information

Abstract

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.

Downloads

Published

2021-05-18

How to Cite

Gao, Y., Kroer, C., & Goldfarb, D. (2021). Increasing Iterate Averaging for Solving Saddle-Point Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 35(9), 7537-7544. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16923

Issue

Section

AAAI Technical Track on Machine Learning II