广义隐式 Follow-The-Regularized-Leader
本文设计并分析了一种不需要任何上限或下限的在线线性优化算法,实现了适应损失向量范数的缩放不变性,并且通过 FTRL 和 MD 元算法实现了最优遗憾,并为无界决策集开发了一种非真空遗憾绑定的自适应算法,并对基于 MD 的无标度算法在无界域上的下限进行了研究。
Jan, 2016
本文提出了 Follow The Regularized Leader (FTRL) 算法并应用于在线学习中,通过分离延迟反馈成本和赌博反馈成本,得出了在三种不同的情况下的新结果,包括组合半赌博、带延迟的对抗 Markov 决策过程以及带权值的线性赌博。我们的新型遗憾分解显示 FTRL 在正则化程序的 Hessian 矩阵上的温和假设下,可在多轮中保持稳定,并为线性赌徒提供了一种有效算法和接近最优的遗憾限制。
May, 2023
研究了在线学习算法中的 Follow the Leader (FTL) 算法,证明在一定条件下即使未必为凸损失函数时,其仍可以表现出与曲率相似的性能,同时可以在保证最坏情况下得到良好的结果。
Feb, 2017
Follow-The-Regularized-Leader (FTRL) 在在线学习中是一种有效且多功能的方法,调整其学习率的问题被形式化为序贯决策问题,并引入了竞争分析的框架。我们提出的学习率更新规则通过与竞争比率的下限相差一个常数因子来达到上限的目的,对于惩罚项的组成部分进行(近似)单调性的刻画,并针对一些特定环境构建了 BOBW 算法,从而在多臂赌博机、图赌博机、线性赌博机和上下文赌博机等不同设置下取得更紧的后悔界限和更广泛的算法适用性。
Mar, 2024
该研究探讨了三家在线凸优化算法家族:follow-the-proximally-regularized-leader(FTRL-Proximal)、正则化双平均(RDA)和组合目标镜像下降。研究证明了所有这些算法都是通用 FTRL 更新的实例。此外,通过使用紧凑的表示方法,文中还提出了一种更好的算法性能估计方法,在真实数据集上展现出了更好的性能。
Sep, 2010
研究基于非凸损失的在线学习问题,证明了经典的 Perturbed Leader 算法在该设置下可达到最佳遗憾率,进一步证明乐观的 FTPL 算法在序列损失可预测时的遗憾界更优。
Mar, 2019
通过设计自适应的正则化器和学习率,FTRL 是一个强大的框架,适用于各种在线学习问题。本文提出了一个新的自适应学习率框架来解决具有 Θ(T^{2/3}) 最小最大遗憾的问题,并应用于部分监控和图形赌博两个重要的间接反馈问题。
May, 2024
研究在线组合优化问题下的半强化反馈,提出了一种结合 FPL 预测方法和新颖的损失估计程序(称为 Geometric Resampling)的学习算法,并且在能够进行高效离线组合优化的任何决策集合上可以有效实现。假设决策集合的元素可以用至多 m 个非零项的 d 维二进制向量来描述,证明了我们算法的期望遗憾在 T 轮后是 O (m sqrt (dT log d)),并且在全信息设置中也改进了 FPL 的最佳遗憾限制。
May, 2013
本文介绍了一种新的优化理论方法,用于分析使用扰动作为正则化工具实现 Follow-the-Leader 程序的特定设置,该方法包括添加强凸罚函数到决策规则和添加随机扰动到数据的方法,并在 Follow the Regularized Leader 和 Follow the Perturbed Leader 之间建立了等价关系,从而得出了一个可以恢复和改进先前已知后悔上限的算法类 Follow the Perturbed Leader 的通用分析框架。
May, 2014
证明了在 Markov 博弈中,基于乐观的 Follow-the-Regularized-Leader (OFTRL) 算法的平滑值更新,可在 T 次迭代中找到 $O (T^{-1})$ 的近似 Nash 均衡,该算法的关键改进是通过紧化 OFTRL 权重的代数不等式,使竞争者的遗憾之和大致是非负的,使得学习动态的二阶路径长度被限制,最终实现了 $O (T^{-1})$ 的收敛速率提高。
Sep, 2022