Feb, 2024

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

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

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

    Jan, 2013

  • 一种连续时间的在线优化方法

    研究一种基于连续时间的在线优化策略族，证明其能够达到无遗憾学习。从传统的离散时间角度来看，这种方法可导出大量离散时间算法（包括一些经典遗憾分析算法）的无遗憾性质，并统一了许多经典的遗憾上界，得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。

    Jan, 2014

  • 在线非凸学习：跟随扰动领袖是最优的

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

    Mar, 2019

  • 无尺度在线学习

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

    Jan, 2016

  • 有限随机部分监控的自适应算法

    本文提出了一种新的随时算法，实现了对于有限的随机部分监测任何实例的近似最优遗憾，特别是对于 “容易” 和 “困难” 问题，该新算法在对数因子内实现了极小化遗憾。对于容易的问题，它还实现了对数个体遗憾。最重要的是，该算法在对手策略位于策略空间的 “容易区域” 时是自适应的。作为一个推论，我们展示了在一些合理的额外假设下，此算法在动态定价 (Dynamic Pricing) 中具有 O (根号 T) 的遗憾，该问题由 Bartok et al.(2011) 被证明是困难的。

    Jun, 2012

  • 在线学习中 FTRL 的简单自适应学习率与 Θ(T^{2/3}) 的最小 max 遗憾及其在最佳两全之间的应用

    通过设计自适应的正则化器和学习率，FTRL 是一个强大的框架，适用于各种在线学习问题。本文提出了一个新的自适应学习率框架来解决具有 Θ(T^{2/3}) 最小最大遗憾的问题，并应用于部分监控和图形赌博两个重要的间接反馈问题。

    May, 2024

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

    研究了在线学习算法中的 Follow the Leader (FTL) 算法，证明在一定条件下即使未必为凸损失函数时，其仍可以表现出与曲率相似的性能，同时可以在保证最坏情况下得到良好的结果。

    Feb, 2017

  • 自适应对冲

    本文介绍了一种基于 Hedge 算法且用于决策论在线学习的新方法 —— 自适应设置学习率，该方法在最坏情况下保证了最优表现，但在简单的情况下可以达到更小的错误率。除此之外，本文还提供了一项仿真研究，以比较自适应设置学习率方法与现有方法的优劣。

    Oct, 2011

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

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

    Mar, 2024

  • 具有切换成本和其他自适应对手的在线学习

    本文研究了预测中的不同类型自适应（非固定的）对手的强度，使用新概念的策略遗憾去衡量玩家的表现，特别关注记忆和切换成本的自适应对手，具有均摊 2/3 次幂的速率且强度显著较弱。

    Feb, 2013