鞍点问题中的乐观镜像下降:额外走 (梯度) 一英里
提供了乐观镜面下降算法的几个应用:将其用于线下优化中的镜像近端算法、扩展到 Holder 平滑函数、并将结果应用于鞍点问题;将其用于有限零和矩阵博弈中,为两个强耦合玩家提供最小化最大值均衡的渐进速率 O ((log T)/T);再考虑问题的部分信息版本并将结果应用于凸规划,展示了近似最大流问题的简单算法。
Nov, 2013
本文提出使用乐观镜像下降(OMD)解决在训练生成对抗网络中的极限循环问题,通过实验验证 OMD 解决了 WGAN 训练中的极限循环问题并同时提高了模型性能,尤其应用于生物信息学中生成 DNA 序列的任务中表现优异。
Oct, 2017
本研究主要探讨过参数模型中采用 stochastic mirror descent 方法,在足够小的步长下,通过初始化接近全局最小值,其可以收敛和迭代到一种接近 Bregman 散度且具有更好泛化性能的解决方案,并探究该方法中不同的隐式正则化方式对结果表现的影响。
Jun, 2019
该论文重新审视了当今非凸优化设置中随机镜像下降(Stochastic Mirror Descent,SMD)的收敛性。通过支持一般距离生成函数(distance generating function,DGF)的新的非凸 SMD 收敛分析,该论文克服了先前结果对于具有光滑连续的梯度的可微性 DGF 的限制,并仅依赖于标准假设。此外,该论文通过 Bregman 前向 - 后向包络建立了收敛性,该包络是比常用的梯度映射的平方范数更强的度量。进一步,该论文将结果扩展到在次高斯噪声下的高概率收敛和在广义 Bregman Proximal Polyak-Lojasiewicz 条件下的全局收敛。此外,通过利用非光滑 DGFs,我们展示了改进的 SMD 理论在各种非凸机器学习任务中的优势。值得注意的是,在非凸差分隐私(differentially private,DP)学习的背景下,我们的理论提供了一个(几乎)维度无关的效用界算法。对于训练线性神经网络的问题,我们开发了可证明收敛的随机算法。
Feb, 2024
我们提出了一类基于镜像下降的高效自适应双层优化方法,用于求解非凸双层优化问题,其中上层问题可能是非凸的且具有非光滑正则化,而下层问题也是非凸的但满足 Polyak-Lojasiewicz 条件。我们提出了一种基于镜像下降的高效自适应投影梯度方法来解决确定性双层问题,并证明其在寻找非凸双层问题的 ε- 稳定解时具有已知最好的梯度复杂度 O (ε^(-1))。为了解决随机双层问题,我们提出了一种基于镜像下降和方差约减技术的高效自适应随机投影梯度方法,并证明其在寻找 ε- 稳定解时具有已知最好的梯度复杂度 O (ε^(-3/2))。由于 Polyak-Lojasiewicz 条件放宽了强凸性,我们的算法可以用于非凸强凸双层优化问题。从理论上讲,我们在一些温和条件下提供了有用的收敛性分析框架,并证明了我们的方法具有较快的收敛速度 O (1/T),其中 T 表示迭代次数。
Nov, 2023
本文研究使用 Extra-gradient 和 Optimistic Gradient Descent Ascent 算法解决鞍点问题,并表明这两种算法作为经典的近端点法的逼近。通过这个观点,我们开发了一种新的框架来分析 EG 和 OGDA 在双线性和强凸 - 强凹情况下的效果。此外,我们使用近端点逼近解释将结果推广到 OGDA 适用于广泛的参数范围。
Jan, 2019
该论文探讨了基于在线凸优化的强化学习的新框架,特别是镜像下降及相关算法,提出了一种新的类似于梯度下降的迭代方法。其中,基于不同 Bregman 散度的抛物线梯度强化学习法比常规 TD 学习更为普适。还提出了一种新型的稀疏镜像下降强化学习方法,相比之前基于二阶矩阵方法的方法,在寻找一个 l1 正则化 Bellman 方程的稀疏不动点时具有显著的计算优势。
Oct, 2012
我们研究了如何在带有轨迹反馈的零和不完全信息博弈中学习 ε- 最优策略,通过应用自适应在线镜像下降算法,在信息集中使用逐渐减小的学习率和正则化损失,我们证明了该方法在高概率下能够保证收敛速度为~T^(-1/2),并且在理论上的最佳学习率和采样策略选择时,对于游戏参数的依赖性接近最优。为了实现这些结果,我们扩展了对 OMD 稳定性的概念,允许随时间变化的凸增量正则化。
Sep, 2023
在多面体环境中,我们研究了差分隐私(DP)随机凸 - 凹鞍点问题。我们提出了基于随机镜像下降的(ε,δ)-DP 算法,实现了接近维度无关的收敛速率用于预期对偶间隙,这种保证类型以前仅适用于双线性目标。对于凸 - 凹和一阶平滑的随机目标,我们的算法取得了一个速率为√(log (d)/n) + (log (d)^(3/2)/[nε])^(1/3),其中 d 是问题的维度,n 是数据集大小。在额外的二阶平滑性假设下,我们将预期间隙的速率改进为√(log (d)/n) + (log (d)^(3/2)/[nε])^(2/5)。在此额外的假设下,我们还通过使用减少偏差的梯度估计器展示了对偶间隙受限于常数成功概率的边界为 log (d)/√n+log (d)/[nε]^(1/2)。这个结果证明了该方法的接近最优性。最后,我们展示了将我们的方法与在线学习的加速技术相结合,得到了第一个在多面体环境中不基于 Frank-Wolfe 方法的 DP 随机凸优化算法。对于凸和一阶平滑的随机目标,我们的算法获得了过量风险为√(log (d)/n) + log (d)^(7/10)/[nε]^(2/5),在另外假设二阶平滑性的情况下,我们将速率提高到√(log (d)/n) + log (d)/√nε。所有这些结果都依赖于经典 Maurey 稀疏化引理的各种推广,可能具有独立的兴趣。
Mar, 2024
本文研究了学习动态的最后迭代收敛问题,并提供了新的结果和技术,其中包括一类游戏模型及其动态下的结果,以及通过遗憾分析得到的性质,证明了具有有界二阶路径长度,而且无论玩家使用不同算法和预测机制,也能实现 O(1 /sqrt(T))的速率和最优 O(1)的后悔界。同时证明了 OMD 要么接近纳什均衡,要么在效率上优于强韧价格,最后,对一般和连续的游戏模型也进行了探讨。
Mar, 2022