关于连续时间在线学习的一点备注
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014
本文通过差分方程和随机微积分的连续时间分析视角,研究离散时间问题,提出了一个连续时间、无需参数算法,并开发了一个类似的离散算法,最后提出了一个任意时间的算法以应对最难情况,并给出了一些令人满意的实验证据。
Jun, 2022
本文介绍了在线学习的基本概念和现代在线凸优化的视角,并针对凸丢失,在欧几里得和非欧几里得环境中介绍了一阶和二阶算法。同时,还特别关注了算法参数调优和在无界域上的学习,并介绍了对非凸损失的处理方法和信息缺失的决策问题中的多臂赌博机问题。
Dec, 2019
通过建立连续在线学习(COL)这种新的设置,连续轮次中在线损失函数的梯度会随着学习者的决策而连续变化,我们可以更完整地描述许多有趣的应用,特别地,证明了满足单调 EPs(经济平衡问题)能够在 COL 中实现子线性的静态遗憾。 由此得出的启示是,我们提供了实现子线性动态遗憾的有效算法的条件,即使选择的损失在先验变化预算中没有适应性。 此外,我们还展示了一个从动态遗憾到静态遗憾和相关 EP(经济平衡问题)收敛的 COL 之间的简化,从而允许我们分析许多现有算法的动态遗憾。
Feb, 2019
该论文提出了当对手可以适应在线算法的动作时,标准遗憾定义变得不再有效,定义了替代的政策遗憾概念,用于测量在线算法在适应性对手下的性能,并研究了在线赌徒问题的情况,表明任何赌徒算法都无法针对带有无界内存的适应性对手保证次线性的政策遗憾,但同时提出了将标准遗憾限制在次线性边界以下的任何赌徒算法转换为政策遗憾限制在次线性边界以下的算法的一般技术, 并将这一结果扩展到其他遗憾变体。
Jun, 2012
本研究分析了在线凸优化问题在不同情境下的处理方法,并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板,同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外,通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较,我们证明了可以在面对不可避免对手时,设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此,我们提出了将一阶算法转换为零阶算法,并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化,如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析,我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。
Feb, 2024
在线学习不仅仅是记住一切。通过使用自适应在线学习中近期开发的技术重新审视折扣遗憾的经典概念,我们提出了一个能够优雅地在新数据到达时遗忘历史的关键算法,改进了传统的非自适应算法,即使用固定学习率的梯度下降算法。具体而言,我们的理论保证不需要任何除了凸性之外的结构假设,该算法在次优超参数调整时可以证明是鲁棒的。通过在线符合预测,我们进一步展示了这些好处,它是一个具有集合成员决策的下游在线学习任务。
Feb, 2024
本文研究了在线学习在没有循环的马尔可夫决策过程中的应用,提出了基于熵正则化方法实现的在线算法并给出了 $\tilde {O}(L|X|\sqrt {|A|T})$ 的遗憾界,通过处理凸性能标准并改进之前的遗憾界,扩展了对抗性 MDP 模型,并可以更好地处理单个 episode 的损失。
May, 2019