Jan, 2014

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

PDF
TL;DR研究一种基于连续时间的在线优化策略族，证明其能够达到无遗憾学习。从传统的离散时间角度来看，这种方法可导出大量离散时间算法（包括一些经典遗憾分析算法）的无遗憾性质，并统一了许多经典的遗憾上界，得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
online optimizationcontinuous-time approachno-regretregret boundsinfinite horizon learning
发现论文，激发创造
  • 关于连续时间在线学习的一点备注

    连续时间模型中，我们提出了在线学习问题的连续时间算法，并给出了最优遗憾界的简明证明。

    May, 2024

  • 连续博弈中的自适应学习：最优遗憾边界和纳什均衡收敛

    本文提出了一种基于乐观的镜像下降的无悔策略算法，可以在非稳态环境下实现 O (sqrt (T)) 的后悔度，并可在变分稳定游戏中收敛到纳什均衡。

    Apr, 2021

  • 专家建议下的连续预测

    本文通过差分方程和随机微积分的连续时间分析视角，研究离散时间问题，提出了一个连续时间、无需参数算法，并开发了一个类似的离散算法，最后提出了一个任意时间的算法以应对最难情况，并给出了一些令人满意的实验证据。

    Jun, 2022

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

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

    Nov, 2012

  • 结合在线学习保证

    本文提出了一种简单的方法，可以将两个具有不同遗憾保证的无参数在线学习算法结合起来得到一个新的算法，其遗憾值是两个算法中的最小值。此外，作者还提出了一种基于该方法的黑盒子算法，可以生成乐观的在线学习算法，并提供无拘束设定下的第一个乐观遗憾保证。

    Feb, 2019

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

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

    Sep, 2023

  • 在线学习与不完美提示

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

    Feb, 2020

  • 在线连续子模最大化

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

    Feb, 2018

  • 在线组合优化中的遗憾

    本文研究使用二进制向量表示决策者可能的选择时的在线线性优化问题及其反悔，探讨了决策者在不同反馈条件下的最优反悔幅度，并提出了一种使用镜像下降算法和隐式归一化预测策略的解决方案，获得了半强盗情形的最优界限，同时也证明了在线组合优化基准算法的次优性。

    Apr, 2012

  • 使用函数遗憾估计来解决游戏

    本文提出了一种新的在线学习方法，用于在大型 extensive-form 游戏中最小化后悔。该方法通过在线学习函数逼近器来估计选择特定行动的后悔值，并使用无悔算法根据这些估计值来定义一系列策略。我们证明了该方法的正确性，并证明了只要逼近函数能够实现后悔值，方法就能自我学习并收敛到纳什均衡。我们的技术可以被理解为现有大型游戏中抽象工作的原则性推广；在我们的工作中，抽象和均衡都是在自我博弈中学习的。我们在实验中展示了该方法可以在相同资源条件下实现比最先进的抽象技术更高质量的策略。

    Nov, 2014