Feb, 2017

线性预测中的跟随者和快速收敛：曲线约束集合和其他规律

PDF
TL;DR研究了在线学习算法中的 Follow the Leader (FTL) 算法，证明在一定条件下即使未必为凸损失函数时，其仍可以表现出与曲率相似的性能，同时可以在保证最坏情况下得到良好的结果。
follow the leader algorithmconvex loss functionslinear predictioncurvatureregret
发现论文，激发创造
  • 在线非凸学习：跟随扰动领袖是最优的

    研究基于非凸损失的在线学习问题，证明了经典的 Perturbed Leader 算法在该设置下可达到最佳遗憾率，进一步证明乐观的 FTPL 算法在序列损失可预测时的遗憾界更优。

    Mar, 2019

  • 广义隐式 Follow-The-Regularized-Leader

    该研究提出了一种新的在线学习算法，即广义隐式 FTRL，该算法扩展了 FTRL 框架的范围，可恢复已知算法，设计新的更新规则，直接改善遗憾的最坏情况的上界。

    May, 2023

  • 无尺度在线学习

    本文设计并分析了一种不需要任何上限或下限的在线线性优化算法，实现了适应损失向量范数的缩放不变性，并且通过 FTRL 和 MD 元算法实现了最优遗憾，并为无界决策集开发了一种非真空遗憾绑定的自适应算法，并对基于 MD 的无标度算法在无界域上的下限进行了研究。

    Jan, 2016

  • 跟随领袖如果可以，如果必要则对冲

    介绍了一种名为 FlipFlop 算法的新方法，该方法将 Follow-the-Leader 算法和 AdaHedge 策略相结合，同时不会牺牲前者的强势表现和后者的最坏情况保证。

    Jan, 2013

  • 利用可行集的曲率在在线凸优化中获得快速速率

    基于在线凸优化和曲率的可行集合的分析，本文提出了一种新的方法通过利用可行集合的曲率来实现快速收敛，不仅可以适用于凸损失函数，同时还能在随机、对抗性和受干扰的环境下获得良好的性能。

    Feb, 2024

  • Follow-the-Regularized-Leader 竞争比分析及最佳学习率自适应

    Follow-The-Regularized-Leader (FTRL) 在在线学习中是一种有效且多功能的方法，调整其学习率的问题被形式化为序贯决策问题，并引入了竞争分析的框架。我们提出的学习率更新规则通过与竞争比率的下限相差一个常数因子来达到上限的目的，对于惩罚项的组成部分进行（近似）单调性的刻画，并针对一些特定环境构建了 BOBW 算法，从而在多臂赌博机、图赌博机、线性赌博机和上下文赌博机等不同设置下取得更紧的后悔界限和更广泛的算法适用性。

    Mar, 2024

  • 跟随扰动领袖进行自适应在线预测

    应用聚合策略进行预测时，需要自适应调整学习速率以避免复杂度和当前损失率之间的分析难题；本文基于 Kalai 和 Vempala（2003）的 “Follow the Perturbed Leader”（FPL）算法，在两种不同的专家类别下得出了可调学习速率的损失界限，其中前者的损失界限与迄今为止最佳结果匹配，而后者为新结果。

    Apr, 2005

  • 通过平滑实现在线线性优化

    本文介绍了一种新的优化理论方法，用于分析使用扰动作为正则化工具实现 Follow-the-Leader 程序的特定设置，该方法包括添加强凸罚函数到决策规则和添加随机扰动到数据的方法，并在 Follow the Regularized Leader 和 Follow the Perturbed Leader 之间建立了等价关系，从而得出了一个可以恢复和改进先前已知后悔上限的算法类 Follow the Perturbed Leader 的通用分析框架。

    May, 2014

  • 实例最优在线学习的 SMART 方法

    我们提出了一种在线学习算法 —— 通过单调适应性遗憾追踪（SMART）进行切换，它适应数据并实现了在每个输入序列上相对于领导者跟随（FTL）策略的表现和任何其他输入策略的最坏情况保证同时有效的遗憾，通过我们的算法，我们证明 SMART 政策在任何输入序列上的遗憾在与 FTL 获得的遗憾和给定最坏情况策略保证的遺憾上都在乘法因子 e/(e-1)≈1.58 的范围内，同时它是简单易实施的，并通过一种基本的分析方法证明了实例上在线学习相对于滑雪租赁问题的竞争分析的可行性，我们还提出了 SMART 的一个修改版本，通过将 FTL 与 “小损失” 算法相结合，实现了在 FTL 和小损失遗憾上的实例最优性。

    Feb, 2024

  • 带有弗雷歇特 - 类型尾部分布的跟随扰动领导者：对抗性赌博机中的最优性和最佳选择之间的折衷

    本文研究了在对抗性和随机的 K 臂赌博机中，随机扰动策略（Follow-the-Perturbed-Leader）的最优性。我们建立了对于扰动实现 O (√KT) 遗憾的充分条件，并展示了随机扰动策略在具有特定尾部分布的情况下实现的最佳两者能力。

    Mar, 2024