跟随领袖如果可以,如果必要则对冲
研究了在线学习算法中的 Follow the Leader (FTL) 算法,证明在一定条件下即使未必为凸损失函数时,其仍可以表现出与曲率相似的性能,同时可以在保证最坏情况下得到良好的结果。
Feb, 2017
我们提出了一种在线学习算法 —— 通过单调适应性遗憾追踪(SMART)进行切换,它适应数据并实现了在每个输入序列上相对于领导者跟随(FTL)策略的表现和任何其他输入策略的最坏情况保证同时有效的遗憾,通过我们的算法,我们证明 SMART 政策在任何输入序列上的遗憾在与 FTL 获得的遗憾和给定最坏情况策略保证的遺憾上都在乘法因子 e/(e-1)≈1.58 的范围内,同时它是简单易实施的,并通过一种基本的分析方法证明了实例上在线学习相对于滑雪租赁问题的竞争分析的可行性,我们还提出了 SMART 的一个修改版本,通过将 FTL 与 “小损失” 算法相结合,实现了在 FTL 和小损失遗憾上的实例最优性。
Feb, 2024
研究基于非凸损失的在线学习问题,证明了经典的 Perturbed Leader 算法在该设置下可达到最佳遗憾率,进一步证明乐观的 FTPL 算法在序列损失可预测时的遗憾界更优。
Mar, 2019
本文研究了在对抗性和随机的 K 臂赌博机中,随机扰动策略(Follow-the-Perturbed-Leader)的最优性。我们建立了对于扰动实现 O (√KT) 遗憾的充分条件,并展示了随机扰动策略在具有特定尾部分布的情况下实现的最佳两者能力。
Mar, 2024
通过研究 Follow-the-Perturbed-Leader 算法在 Adversarial Markov Decision Processes 中的应用,作者发现该算法不仅在有限时间内能够实现近似最优的 regret bound,并且能够有序地处理 Delayed Bandit Feedback 问题,并且进一步提出了第一个无悔学习算法来解决在无限时间内、使用有限的 bandit feedback 和随机转移的情况下解决 AMDPs 问题。
May, 2022
该研究提出了一种新的在线学习算法,即广义隐式 FTRL,该算法扩展了 FTRL 框架的范围,可恢复已知算法,设计新的更新规则,直接改善遗憾的最坏情况的上界。
May, 2023
研究在线组合优化问题下的半强化反馈,提出了一种结合 FPL 预测方法和新颖的损失估计程序(称为 Geometric Resampling)的学习算法,并且在能够进行高效离线组合优化的任何决策集合上可以有效实现。假设决策集合的元素可以用至多 m 个非零项的 d 维二进制向量来描述,证明了我们算法的期望遗憾在 T 轮后是 O (m sqrt (dT log d)),并且在全信息设置中也改进了 FPL 的最佳遗憾限制。
May, 2013
应用聚合策略进行预测时,需要自适应调整学习速率以避免复杂度和当前损失率之间的分析难题;本文基于 Kalai 和 Vempala(2003)的 “Follow the Perturbed Leader”(FPL)算法,在两种不同的专家类别下得出了可调学习速率的损失界限,其中前者的损失界限与迄今为止最佳结果匹配,而后者为新结果。
Apr, 2005
研究了在线随机环境下的 Hedge 算法行为,证明了降低学习率的任何时候版本,能够同时适应较容易的随机问题和顶峰问题,并与其他变体算法的表现有质的差异,最终讨论了该算法的局限性和 Stochastic 情况下双重遗憾边界带来的改进。
Sep, 2018
本文介绍了一种基于 Hedge 算法且用于决策论在线学习的新方法 —— 自适应设置学习率,该方法在最坏情况下保证了最优表现,但在简单的情况下可以达到更小的错误率。除此之外,本文还提供了一项仿真研究,以比较自适应设置学习率方法与现有方法的优劣。
Oct, 2011