May, 2023

无 Lipschitzness 和 Smoothness 在线组合优化的数据相关上界

PDF
TL;DR本文介绍了在线组合优化中首个基于数据的小损失和渐变性遗憾界，并提出了相应算法实现，可在投资选择数目较多的情况下，拥有亚线性的遗憾率，并在某些情况下具有对数遗憾率。遗憾界是通过对对数损失的新光滑性特征、对遵循正则化领导者（FTRL）的本地基于范数的分析以及乐观 FTRL 的隐式变体得到的，后者采用对数障碍。
发现论文，激发创造
  • 不依赖利普希茨连续性的遗憾界：相对利普希茨损失下的在线学习

    本研究考虑在线凸优化问题的相对 Lipschitz 收敛性和相对强凸性，扩展了已知的算法在相对设置下的遗憾界，特别是基于正则聚类领导者算法和在线镜像下降算法的算法，同时将这些结果进一步扩展到具有额外正则化的算法。

    Oct, 2020

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

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

    Jan, 2014

  • 在线凸优化的自适应边界优化

    本文提出了一种新的在线凸优化算法，该算法根据迄今为止观察到的损失函数自适应地选择其正则化函数，其遗憾界是最坏情况下最优的，并且对于某些实际损失函数类别，它们比现有界限好得多。此算法不需要事先了解问题实例的结构，但提供了一定程度的竞争保证，并在范围内提供了一定程度的界限。

    Feb, 2010

  • 无限损失的无限制在线学习

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

    Jun, 2023

  • 自适应在线学习

    该论文提出了一种普遍框架，用于研究在线学习框架下的自适应遗憾界限，包括模型选择界限和数据相关界限；该框架基于顺序复杂度量的修正，并使用单侧尾不等式来界定此界限，并在线性优化和在线 PAC-Bayes 定理中进行了实例化。

    Aug, 2015

  • 平滑在线学习的简易性与统计学习相当

    本论文研究了在线设置下学习过程中涉及到的平滑度、最小极大后悔以及上下文干涉等问题，并提出了对应算法的解决方案。

    Feb, 2022

  • 完全无约束的在线学习

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

    May, 2024

  • 凸光滑函数的动态遗憾

    本文提出了一种在线凸优化算法，该算法在非稳态环境中表现出优异的动态后悔表现，通过充分利用流畅性条件，能够在动态后悔中代替对 T 的依赖，而采用问题相关的数量：损失函数的梯度变化、比较序列的累积损失和前两个 term 的最小值，从而使问题的复杂度自适应问题的困难程度，即在简单问题上使界限更紧，同时保证了最坏情况下相同的界限。

    Jul, 2020

  • 在线控制的对数后悔

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

    Sep, 2019

  • 非平稳在线学习的高效方法

    优化非稳态动态损失和自适应损失的有效方法涉及非稳态在线学习的减少投影和梯度查询次数，在参数自由在线学习的基础上进行了非平凡的改进。

    Sep, 2023