Proximal Point Method for Online Saddle Point Problem

本文关注在线鞍点问题，涉及一系列两人博弈的时变凸凹函数。考虑到环境的非稳定性，我们采用对偶间隙和动态纳什均衡遗憾作为算法设计的性能指标。我们提出了三种近端点法的变体：在线近端点法（OPPM）、乐观OPPM（OptOPPM）和具有多个预测器的OptOPPM。每种算法都保证了对偶间隙和动态纳什均衡遗憾的上限，当以对偶间隙为度量时，实现了接近最优的效果。具体来说，在某些良性环境下，例如一系列稳定的收益函数，这些算法可以维持近乎恒定的度量上限。实验结果进一步验证了这些算法的有效性。最后，本文讨论了使用动态纳什均衡遗憾作为性能指标可能存在的可靠性问题。

论文解决的问题是在线鞍点问题，涉及一系列两人时间变化的凸凹博弈。试图通过采用对偶间隙和动态纳什均衡后悔作为算法设计的性能度量来解决这个问题。

论文提出了三种近端点法的变体：在线近端点法（OPPM）、乐观OPPM（OptOPPM）和具有多个预测器的OptOPPM。每种算法都保证了对偶间隙和动态纳什均衡后悔的上界，并在度量对偶间隙时实现了近似最优性。在某些良性环境中，如序列化支付函数，这些算法保持了几乎恒定的度量上界。

论文的亮点包括提出的三种算法及其性能保证，实验结果的验证以及对使用动态纳什均衡后悔作为性能度量的可靠性问题的讨论。

最近的相关研究包括“Online Learning with Gated Linear Networks”和“Online Learning with Randomized Regularization for Time-varying Regression”。