Feb, 2020

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

PDF
TL;DR本文研究了凸凹零和博弈问题，并提出了一种遵循在线学习框架的近似算法 Optimistic Multiplicative-Weights Update，在本地范围内表现出最后收敛性。
发现论文，激发创造
  • 末次迭代收敛：零和博弈与约束极小极大优化

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

    Jul, 2018

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

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

    Jun, 2019

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

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

    Aug, 2023

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

    本研究对 OGDA 和 OMWU 在约束优化问题中的后迭代收敛性进行了显著扩展，提出了一种足够条件来保证 OGDA 在多面体上的双线性博弈问题中展现出线性的后迭代收敛性，并且没有唯一均衡假设，同时在强凸 - 强凹函数上也保持收敛性，这种条件也适用于多个一般目标和可行集合的约束下的 OGDA 算法，并通过实验结果验证了理论。

    Jun, 2020

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

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

    Mar, 2022

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

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

    Jun, 2024

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

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

    Jul, 2018

  • 无限时段竞争马尔可夫博弈中分散乐观梯度下降 / 上升的最后迭代收敛

    研究无穷时间折扣二人零和马尔可夫博弈，开发了一种分散算法，自我对弈时能够收敛到 Nash 均衡点。

    Feb, 2021

  • 稀疏性与曲率的改进乐观镜像下降算法

    本文研究了在线凸优化的一些新进展，特别是对于在稀疏、可预测序列和曲线损失等易于数据实例中进一步提高后悔界限的方法的统一处理。我们提出了一种自适应、乐观的更新规则，并解释了一种可以动态适应损失函数曲率的更新规则，并最终将这些结果扩展到了复合损失情形。

    Sep, 2016

  • 约束单调变分不等式的 Extragradient 算法和乐观梯度下降上升算法的紧凑最后迭代收敛性

    本研究解决了开放性问题，证明了用切向残差作为潜势函数的 extragradient 算法（或乐观梯度上升下降算法）在任意凸可行域上具有极致的收敛速率，其简单的表达为 $O (1/√T)$ 。

    Apr, 2022