May, 2024

交替镜像下降方法的辛分析

HTML
PDF
TL;DR通过使用Hamiltonian动力学、李代数和辛数值积分器的结果，以及对连续时间Hamiltonian流通过辛欧拉方法的离散化的研究，我们提供了一个分析框架，并强调了修正Hamiltonian (MH)的存在和特性，计算了二次函数原Hamiltonian情况下的MH，并得出新的误差界。我们利用这些结果展示了Alternating Mirror Descent算法的改进的总遗憾界限和平均迭代的对偶间隙。最后，我们提出了一个猜想，如果成立，会导致AMD的总遗憾为O(K^ε)，平均迭代的对偶间隙为O(K^-1+ε)，其中ε>0，且在MH的特定收敛条件下可以取ε=0。
发现论文，激发创造
  • 可预测序列的优化、学习和游戏

    提供了乐观镜面下降算法的几个应用：将其用于线下优化中的镜像近端算法、扩展到 Holder 平滑函数、并将结果应用于鞍点问题；将其用于有限零和矩阵博弈中，为两个强耦合玩家提供最小化最大值均衡的渐进速率 O((log T)/T)；再考虑问题的部分信息版本并将结果应用于凸规划，展示了近似最大流问题的简单算法。

    Nov, 2013

  • n个玩家可微分游戏的力学

    本文介绍了用于解决许多深度学习模型中的问题的Symplectic Gradient Adjustment (SGA)算法，并提出了Hamiltonian game概念，使得SGA算法具有一定的保证，并在GANs等更广泛的游戏中表现出着和其他算法竞争力相当的性能。

    Feb, 2018

  • Hamiltonian Descent方法

    研究了一种基于动力学系统模拟的优化方法，该方法使用常量步长和一阶梯度信息，在更大的凸函数类中实现线性收敛性，包括那些在其极小值点处可能具有奇异或未有界的二阶导数，该方法的动力学梯度映射可以设计成以凸共轭的形式整合信息，允许在非平滑或非强凸的凸函数上实现线性收敛。

    Sep, 2018

  • 广义动量法：哈密顿视角

    采用基于哈密顿视角的方法，将Nesterov加速梯度下降法和Polyak重球方法泛化为广泛的动量方法，得到了无限制约束的最小化问题的一般性和统一性收敛分析，具有直观的时间变化哈密顿量和守恒量。

    Jun, 2019

  • 通过梯度下降学习可逆单元

    通过在交替操作序列的时间参数上应用梯度下降法，我们研究了学习$U(d)$中的单位转换的难度。我们提供了数值证据表明，尽管损失景观非凸，但当序列包含$d^2$个或更多参数时，梯度下降法总是收敛于目标齐次。收敛速度表明了一种“计算相变”。当小于$d^2$个参数时，梯度下降收敛于次优解，而当大于$d^2$个参数时，梯度下降以指数方式收敛于最优解。

    Jan, 2020

  • 平滑博弈的随机哈密顿梯度方法

    本文研究了随机哈密尔顿方法在一类随机光滑博弈上的应用，提出了一种新的无偏估计方法，证明了该方法具有收敛性和全局最优解保证性，并在随机双线性和足够双线性博弈上进行了实验。

    Jul, 2020

  • 强化学习、量化响应均衡和二人零和博弈的统一方法

    研究磁镜下降算法作为均衡求解器和两人零和游戏强化学习的方法，并证明其在多种场景中都可以取得优秀的性能表现，包括在可扩展形式下的均衡求解和在表格设置下的竞争性结果与CFR相比。

    Jun, 2022

  • 广义形式博弈中的本地化和自适应镜像下降

    我们研究了如何在带有轨迹反馈的零和不完全信息博弈中学习ε-最优策略，通过应用自适应在线镜像下降算法，在信息集中使用逐渐减小的学习率和正则化损失，我们证明了该方法在高概率下能够保证收敛速度为~T^(-1/2)，并且在理论上的最佳学习率和采样策略选择时，对于游戏参数的依赖性接近最优。为了实现这些结果，我们扩展了对OMD稳定性的概念，允许随时间变化的凸增量正则化。

    Sep, 2023

  • 镜像下山-上山法用于均场极值问题

    我们研究了解决度量空间中的极小-极大问题的两种变体的镜像下降-上升算法：同时和顺序。在满足凸凹性和支付函数相对平滑性的假设下，我们通过平测度上合适的Bregman散度定义，展示了收敛速度到混合纳什均衡的大小，以Nikaido-Isoda误差为度量，对于同时和顺序的方案分别为O(N^(-1/2))和O(N^(-2/3))，这与相关有限维度算法的最新结果一致。

    Feb, 2024

  • 基于动力系统的辛神经网络

    本研究针对传统神经网络在哈密尔顿微分方程中的局限性，提出了一种基于几何积分器的辛神经网络（SympNets）框架。该框架具有非消失梯度的特性，并能够完全参数化与二次哈密尔顿对应的辛映射，实验结果表明其在表现力和准确性上显著优于现有架构，尤其是在训练成本上更具优势。

    Aug, 2024