Jun, 2020

有约束鞍点优化中的线性最后迭代收敛性

PDF
TL;DR本研究对 OGDA 和 OMWU 在约束优化问题中的后迭代收敛性进行了显著扩展，提出了一种足够条件来保证 OGDA 在多面体上的双线性博弈问题中展现出线性的后迭代收敛性，并且没有唯一均衡假设，同时在强凸 - 强凹函数上也保持收敛性，这种条件也适用于多个一般目标和可行集合的约束下的 OGDA 算法，并通过实验结果验证了理论。
optimistic gradient descent ascentoptimistic multiplicative weights updatebilinear gameslast-iterate convergenceconstrained optimization
发现论文，激发创造
  • 末次迭代收敛：零和博弈与约束极小极大优化

    本文研究了一种叫做 OMWU 的算法，该算法在约束的 min-max 最优化问题中表现出优秀的收敛性以及稳定性。该算法与先前的梯度下降法及其他学习算法不同，且需要使用新的技术和思路。

    Jul, 2018

  • 快速学习游戏的最后迭代收敛需要健忘算法

    通过在线学习的自我对弈是解决大规模两人零和游戏的主要方法之一，尤其流行的算法包括乐观的乘积权重更新（OMWU）和乐观的梯度下降 - 梯度上升（OGDA），本文证明了 OMWU 存在潜在的较慢的最后迭代收敛问题。

    Jun, 2024

  • 无悔学习中的最后迭代收敛：凸凹景观的约束极小极大优化

    本文研究了凸凹零和博弈问题，并提出了一种遵循在线学习框架的近似算法 Optimistic Multiplicative-Weights Update，在本地范围内表现出最后收敛性。

    Feb, 2020

  • 关于零和博弈的收敛策略探讨

    本文研究了学习动态的最后迭代收敛问题，并提供了新的结果和技术，其中包括一类游戏模型及其动态下的结果，以及通过遗憾分析得到的性质，证明了具有有界二阶路径长度，而且无论玩家使用不同算法和预测机制，也能实现 O（1 /sqrt（T））的速率和最优 O（1）的后悔界。同时证明了 OMD 要么接近纳什均衡，要么在效率上优于强韧价格，最后，对一般和连续的游戏模型也进行了探讨。

    Mar, 2022

  • 解决博弈中的高效收敛算法

    通过转换问题为一系列凸凹优化问题， ' 无悔算法 ' 在学习纳什均衡中取得竞争性表现，在离散时间反馈设置下实现最后迭代收敛。

    Aug, 2023

  • 极大极小优化的最终迭代收敛速率

    该研究论文阐述了针对非凸函数最优化问题中的后向迭代收敛的挑战性，介绍了哈密顿梯度下降算法以及协作优化算法，并证明了这些算法在某些情况下表现出线性收敛性。

    Jun, 2019

  • 梯度基方法在全谱游戏中的紧密一致分析

    通过分析梯度方法在达到纳什均衡时的线性收敛特性，证明了变异梯度方法在双线性博弈和强单调性博弈中的各种表现，并发现了这些方法在极端情况下收敛机制的差异。同时证明了变异梯度可以在任意外推次数的情况下实现优化率，一个广泛算法类别的最佳值

    Jun, 2019

  • 共识乘权更新：使用基于投影器的游戏签名学习学习

    本研究介绍了一种新的以学习系数的增量式更新规则为主要方法的强化学习策略，该策略依据游戏的本质 —— 游戏签名进行调整，用于学习在游戏中达到最优状态的方法，其中游戏的多个方面分解成具有交换性的投影算子，介绍了一个新的算法 CMWU，在零和双矩阵游戏中具有局部收敛的保证。

    Jun, 2021

  • 鞍点问题中的乐观镜像下降：额外走 (梯度) 一英里

    本文研究了一类具有一致性属性的非单调问题中，优化镜像下降法（OMD）的收敛性和优化方式。分析表明，OMD 可以解决这些问题并推广了先前的结果，为建立凸凹博弈以外的收敛性提供了具体进展。在一系列 GAN 模型上的数值实验结果验证了分析的可行性。

    Jul, 2018

  • 拟合点方法下额外梯度和乐观梯度方法在鞍点问题中的统一分析

    本文研究使用 Extra-gradient 和 Optimistic Gradient Descent Ascent 算法解决鞍点问题，并表明这两种算法作为经典的近端点法的逼近。通过这个观点，我们开发了一种新的框架来分析 EG 和 OGDA 在双线性和强凸 - 强凹情况下的效果。此外，我们使用近端点逼近解释将结果推广到 OGDA 适用于广泛的参数范围。

    Jan, 2019