证明了非欧版本的优化算法能收敛到鞍点，无需特殊假设。
Last-Iterate Convergence of Optimistic Multiplicative Weight Update
- 提出边界论证，分析迭代点在约束边界的行为
- 在平滑凸凹鞍点问题下，小学习率可保证渐近收敛
- 不依赖解唯一性或初始位置，适合理论研究者
乐观梯度下降上升（OGDA）与乐观乘法权重更新（OMWU）是求解凸-凹鞍点问题的两种经典算法，其中OMWU是OGDA的非欧、熵形式。已知自上世纪80年代以来，OGDA的末次迭代在平滑问题中渐近收敛至鞍点；但OMWU是否具有相同性质尚不清楚。本文证明，在平滑凸-凹鞍点问题中，只要学习率足够小，OMWU的末次迭代也渐近收敛。该结果无需解的唯一性、严格互补性、误差界或初始值靠近解等条件。核心新思路是边界论证，表明每个聚点均满足未激活坐标处的KKT不等式。该论证借助ChatGPT发现，并在附录中详细记录。
原文摘要 · Abstract (English)
Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative-Weights Update (OMWU) are two very popular algorithms to solve convex/concave saddle-point problems, where OMWU is the non-Euclidean, entropic version of OGDA. It is known since the '80s that the last iterate of OGDA asymptotically converges to a saddle point in smooth problems. On the other hand, it is unknown if OMWU has the same property. In this paper, I show that OMWU converges asymptotically for smooth convex-concave saddle-point problems, with a small enough constant learning rate. The result does not require uniqueness, strict complementarity, an error bound, or initialization near a solution. The main new ingredient is a boundary argument showing that every cluster point satisfies the inactive-coordinate KKT inequalities. The boundary argument was discovered with assistance from ChatGPT and is documented in the appendix.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。