通过额外预测缓解延迟反馈，实现双线性博弈的线性收敛。
Linear Convergence in Games with Delayed Feedback via Extra Prediction
- 用额外乐观预测未来收益，改进优化算法
- 延迟为m时，收敛速度达exp(-Θ(t/m⁵))，额外预测可提速至exp(-Θ(t/(m²log m)))
- 适合研究多智能体学习中延迟问题的学者
真实世界中的多智能体学习不可避免地存在反馈延迟，严重损害性能，且延迟反馈下的收敛速率尚不明确，即使在双线性博弈中也是如此。本文推导了加权乐观梯度下降-上升（WOGDA）在无约束双线性博弈中的线性收敛速率，该算法通过额外乐观预测未来收益。我们将其视为对更远未来收益更新的额外近端点（EPP）方法的近似，优于经典近端点（PP）。理论分析表明，标准乐观（预测下一步收益）在经过t次迭代后，收敛速率为exp(-Θ(t/m⁵))（延迟为m）。而采用额外乐观（预测更远未来收益）可容忍更大步长，并将收敛速率显著提升至exp(-Θ(t/(m²log m)))。实验结果也显示额外乐观带来加速收敛，与理论一致。综上，本文验证了额外乐观是应对反馈延迟导致性能下降的有效策略。
原文摘要 · Abstract (English)
Feedback delays are inevitable in real-world multi-agent learning. They are known to severely degrade performance, and the convergence rate under delayed feedback is still unclear, even for bilinear games. This paper derives the rate of linear convergence of Weighted Optimistic Gradient Descent-Ascent (WOGDA), which predicts future rewards with extra optimism, in unconstrained bilinear games. To analyze the algorithm, we interpret it as an approximation of the Extra Proximal Point (EPP), which is updated based on farther future rewards than the classical Proximal Point (PP). Our theorems show that standard optimism (predicting the next-step reward) achieves linear convergence to the equilibrium at a rate $\exp(-Θ(t/m^{5}))$ after $t$ iterations for delay $m$. Moreover, employing extra optimism (predicting farther future reward) tolerates a larger step size and significantly accelerates the rate to $\exp(-Θ(t/(m^{2}\log m)))$. Our experiments also show accelerated convergence driven by the extra optimism and are qualitatively consistent with our theorems. In summary, this paper validates that extra optimism is a promising countermeasure against performance degradation caused by feedback delays.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。