Increasing Iterate Averaging for Solving Saddle-Point Problems
Increasing Iterate Averaging for Solving Saddle-Point Problems
复制标题
DOI：
10.1609/aaai.v35i9.16923
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Yuan Gao-;Christian Kroer;D. Goldfarb
中科院分区：
文献类型：
--
作者：
Yuan Gao-;Christian Kroer;D. Goldfarb
机器学习和博弈论中的许多问题都可以表述为鞍点问题，为此已经开发了各种一阶方法，并在实践中证明是有效的。在一般的凹凸假设下，大多数一阶方法只保证遍历收敛速度，即迭代的一致平均收敛于O（1/T）的鞍点残差。然而，在数值上，迭代本身往往比均匀平均收敛得快得多。这一观察结果促使越来越多的平均方案，把更多的权重放在后面的迭代，而不是通常的均匀平均。我们表明，这种增加平均计划，适用于各种一阶方法，能够保持O（1/T）的收敛速度，没有额外的假设或计算开销。在零和博弈求解、市场均衡计算和图像去噪等方面的大量数值实验证明了所提方案的有效性。特别是，增加的平均值在所有测试问题中始终优于均匀平均值。在解决矩阵和扩展形式的游戏时，增加平均值也始终优于最后一次迭代。对于矩阵游戏，一阶方法配备了增加平均优于竞争激烈的CFR+算法。
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.