通过交替梯度下降上升实现固定步长的有限遗憾和循环
本文提出了一种基于乐观的镜像下降的无悔策略算法,可以在非稳态环境下实现 O (sqrt (T)) 的后悔度,并可在变分稳定游戏中收敛到纳什均衡。
Apr, 2021
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014
本文研究递归最小二乘算法中的遗忘因子对在线牛顿算法动态后悔的影响,对于指数凸和强凸目标,算法可实现动态后悔的界限,同时提出一种用于强凸函数的梯度下降步长规则以获得更高的计算效率。
Sep, 2019
本文研究了具有有限预测窗口和附加决策切换成本的在线优化问题。提出了两种基于梯度的在线算法:RHGD 和 RHAG。该文章报告了这些算法的动态遗憾的上限,并且发现我们的基于梯度的 RHAG 算法是一种接近最优的在线算法。
Jan, 2018
简而言之,本文提出了一种针对广义和博弈的、分散、计算高效的算法,其保证所有代理都使用时可以提供次线性遗憾保证,并且不需要代理之间的通信。该算法的主要观察结果是,通过马尔可夫游戏的在线学习基本上可以归结为一种加权遗憾最小化。
Jul, 2022
研究随机误差对两个约束性增量次梯度算法的影响,并以分布式网络为基础,研究标准增量次梯度算法和随机误差下的方法。通过 Markov 随机增量次梯度方法,对移动网络拓扑变化的建模,研究其稳定性和误差上界。
Jun, 2008
本文提出了一种用于计算竞争性双人游戏纳什均衡的新算法,该算法基于正则化双线性局部逼近的纳什均衡,避免了交替梯度下降中出现的振荡和发散,而且在达到指数级 (局部) 收敛性的同时,其收敛和稳定性的性质对于玩家之间的强交互是稳健的,具有更快的收敛速度。
May, 2019
本文提供一个简明的证明,只需遵循两个规则即可自动化梯度下降:1)不要过快增加步长,2)不要超出局部曲率;通过遵循这些规则,可以得到对局部几何条件自适应的方法,收敛保证只取决于解的附近的平滑度,因此收敛于任何凸问题中,包括可以最小化任意连续两次可微的凸函数的问题,本文将探讨该方法在一系列凸和非凸问题上的性能。
Oct, 2019
本文应用马尔科夫链理论,通过随机梯度下降(SGD)算法来计算目标函数,并提供了一种新的 Richardson-Romberg 外推方法来优化 SGD 算法,通过渐进展开分析,总结出其与初始条件、噪声和步长的相关性。
Jul, 2017
在机器学习中普及的基于梯度的方法需要 “超参数调整”,因为 Armijo 规则等回溯过程需要每一步的质量评估并且不适用于随机优化。本文提出了一种名为 “随机函数下降” 的优化方法,证明在贝叶斯优化场景下,RFD 与梯度下降是相同的,但具有可计算的步长,在合成基准测试中超越了未调整的 Adam 方法,并提出一种启发式扩展,使其与调整后的 Adam 相当。
May, 2023