May, 2024

完全无约束的在线学习

PDF
TL;DR我们提供了一种在线学习算法，可以在不知道 G 或∥w∗∥的情况下，获得在 G-Lipschitz 凸损失函数上的遗憾 G∥w∗∥√(Tlog (∥w∗∥G√T)+∥w∗∥^2+G^2)，这与具有此类知识的最佳界限 G∥w∗∥√T 匹配（除了对数因子），除非∥w∗∥或 G 太大，以至于即使 G∥w∗∥√T 在 T 中也大致线性。因此，在可以实现次线性遗憾的所有场景中，它匹配了最佳界限，这可以说是最 “有趣” 的情况。
online learning algorithmregretlipschitz convex lossescomparison pointsublinear regret
发现论文，激发创造
  • 无限损失的无限制在线学习

    本文提出了一种新的在线学习模式，可以处理无界域和非 Lipschitz 损失的问题，并开发了新的基于套索的在线学习算法，同时利用此算法开发了新的鞍点优化算法，在无界域中实现对偶间隙的收敛；最终提供了第一个实现非 Lipschitz 损失下的动态遗憾度的算法，以及匹配的下界。

    Jun, 2023

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

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

    Jan, 2014

  • 指数凸在线学习的最优动态遗憾

    使用先进的证明技术和 Zinkevich-style 动态遗憾最小化框架，本研究提出了一个强适应的在线学习算法，其总变化控制下的动态遗憾为 O (n^(1/3)*C_n^(2/3))，并且可以扩展到局部自适应非参数回归问题中。

    Apr, 2021

  • 在线学习与不完美提示

    本文提出了一种算法来处理在线学习问题，该算法能够提高在线参与者的表现并创造出令人惊讶的后果，同时也是前人算法的改进。

    Feb, 2020

  • 在线连续子模最大化

    本文研究一种在线优化过程，其中目标函数不是凸函数（也不是凹函数），而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体，它可以访问目标函数的全梯度，并证明它对未来最佳可行解的（1-1/e）- 近似具有 O（T 的平方根）的遗憾界。对于只能获得梯度的无偏估计的情况，我们还提出了在线随机梯度上升算法，并证明它也具有 O（T 的平方根）的遗憾界，但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数，并证明相同的次线性遗憾界。最后，在几个问题实例上演示了算法的效率，包括非凸 / 非凹二次规划，子模集函数的多线性扩展和 D - 最佳设计。

    Feb, 2018

  • 未知约束的在线学习

    在线学习中最小化后悔，满足安全约束的广义元算法，估计未知的安全约束，并将在线学习预测转化为满足未知安全约束的预测，同时使用预测误差、各类模型的复杂度和新的复杂度度量来界定算法的后悔上限，同时提供了线性约束情况下的具体算法，使用比例变换平衡乐观探索和悲观约束满足，最小化根号 T 的后悔。

    Mar, 2024

  • 对抗性在线控制的对数遗憾

    本文针对已知系统且受到敌对扰动的情况下，介绍了新的在线线性二次控制算法，通过将在线控制问题转化为具有近似优越函数的（延迟的）在线学习，无需控制迭代的运动成本，从而提高了算法的效果。

    Feb, 2020

  • 在线控制的对数后悔

    本研究中，我们研究了在线控制下的线性动态系统在拥有转移动态知识的拥有敌意的变化强凸成本函数下的最优遗憾界限，并提出了在线梯度下降和在线自然梯度两种不同且高效的迭代方法来实现遗憾边界小而有效。

    Sep, 2019

  • 无约束在线凸优化的无悔算法

    本文提出了在线凸优化算法来解决无约束情况下在线预测和分类的问题，并证明了其相对于参数 x^* 几乎达到最优的遗憾界。

    Nov, 2012

  • 具有 $\tilde {O}(\sqrt {T})$ 遗憾的高效在线贪心多分类学习

    我们提出了一种高效的二阶算法，用于处理带依赖的多分类问题，同时考虑了由 ETA 参数化的一系列损失函数与竞争者的范式限制。算法能够同时处理从铰链损失 (ETA=0) 到平方铰链损失 (ETA=1) 的这一系列损失函数，这解决了 Abernethy 和 Rakhlin 在 COLT 2009 中的一个开放性问题，并通过实验与早期算法得到了良好的效果。

    Feb, 2017