May, 2014

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

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

    提出和分析一种新型的 Follow-the-Perturbed-Leader 类型算法，用于在线方式解决一般的长期受约束的优化问题，其中目标和约束不一定是凸的。通过将随机线性扰动和强凸扰动分别引入原始和对偶方向，搜索全局极小极大点作为解决方案，并基于两个特定的预期静态累积遗憾定义，推导出这类问题的第一个次线性 $O (T^{8/9})$ 遗憾复杂度。该算法应用于解决长期（风险）受约束的河流污染源辨识问题，验证了理论结果的有效性，并表现出比现有方法更优越的性能。

    Nov, 2023

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

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

    Mar, 2019

  • 从价值到算法：松弛和本地化

    通过最小值极大分析推导出在线学习算法来应对困难的学习问题，利用本地顺序 Rademacher 复杂性与相关算法实现更快速的在线学习，并引入随机化方法以及其他的方法来完善算法性能。

    Apr, 2012

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

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

    Apr, 2005

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

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

    May, 2023

  • 无尺度在线学习

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

    Jan, 2016

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

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

    Feb, 2017

  • 利用不完美预测进行平滑的在线组合优化

    研究了具有预测模型的平滑在线组合优化问题，提出一种在线算法在规划窗口和开关代价之间实现平衡，通过对合成在线分布流问题进行实证，证明在累积规避中取得了显着的改进。

    Apr, 2022

  • 随机行走扰动预测

    本文提出了一种基于扰动随从最优策略算法版本，可以将累积损失通过独立的对称随机游动进行扰动，预测者能够实现期望遗憾最优阶 O (sqrt (n log N)), 且预测者的改变在预期下最多为 O (sqrt (n log N))，同时拓展分析在线组合优化，表明即使在更一般的情况下，预测者也很少在专家之间切换，同时达到近乎最优的遗憾级别。

    Feb, 2013

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

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

    Mar, 2024