Feb, 2024

二阶方法在赌局优化和控制中的应用

PDF
TL;DR本文介绍了一种简单且实用的在线牛顿步骤算法，该算法在一类称为 κ- 凸的凸函数中具有最优（以时间长度衡量）的遗憾界，并且在包括线性、二次和广义线性模型在内的广泛实际损失函数中为最高效的已知方法。此外，我们研究了我们的二阶赌博算法在具有一定仿射结构的损失函数中适应在线凸优化，我们证明了延伸算法达到最优遗憾界，从而解决了在 gradu2020non 和 sun2023optimal 中提出的一个开放问题，即完全敌对噪声模型下的赌博 LQR/LQG 问题。最后，我们证明了 BCO 与（非仿射）内存的更一般问题更难，在光滑且二次损失的假设下，导出了一个 T^{2/3} 遗憾界的下界。
bandit convex optimizationregret boundsonline newton step algorithmaffine structurelqr/lqg problems
发现论文，激发创造
  • 非静态环境下的臂匠凸优化

    探讨了分布不稳定的环境下，采用动态遗憾作为衡量标准的医生凸优化问题，并提出了一种新的算法，在不需要预知路径长度情况下，可以分别实现 $O (T^{3/4}(1+P_T)^{1/2})$ 和 $O (T^{1/2}(1+P_T)^{1/2})$ 的动态遗憾.

    Jul, 2019

  • 无投影赌博凸优化改进遗憾界

    本文提出一种基于条件梯度法的 projection-free 的算法，通过线性优化预测每一轮的动作并达到了 $O (T^{3/4})$ 的预期最小化损失 (expected regret)。

    Oct, 2019

  • 无投影随机凸优化

    该论文提出了第一个计算有效的基于投影的算法来解决 Bandit 凸优化问题，并以各种问题（包括二次规划、组合优化和矩阵完成问题）上的实验结果证明了其性能。

    May, 2018

  • 带有延迟反馈的强化学习优化中的改进后悔度

    我们研究了具有延迟反馈的强凸波段优化问题，通过精细地利用延迟波段反馈的阻塞更新机制，我们的算法改进了损失边界并将其与延迟设置下的传统波段梯度下降（BGD）算法相匹配。

    Feb, 2024

  • 自适应速写的二阶核在线凸优化

    本文介绍了一种新的二阶核在线协方差优化方法 (KONS)，通过引入矩阵扰动算法，大大降低了计算时间和空间成本。

    Jun, 2017

  • 具有对抗约束的在线凸优化的严格界

    有关在线凸优化和约束在线凸优化的一篇研究论文，证明了一个在线策略可以同时实现 O (√T) 的遗憾和 θ̃(√T) 的累积约束违规，通过将 AdaGrad 算法的自适应遗憾界与 Lyapunov 优化相结合，达到了这一结果。

    May, 2024

  • 赌博机凸优化问题的最优算法

    本文针对带有随机反馈的在线凸优化问题（称为 bandit convex optimization），通过将椭球法应用于在线学习，给出了第一个 $\tilde {O}(\sqrt {T})$-regret 算法，并引入了离散凸几何中的新工具。

    Mar, 2016

  • 具有次指数噪声的无参数在线凸优化

    研究了涉及亚指数噪声的无约束在线凸优化问题，设计了一种新的巴拿赫空间参数自由 OCO 算法 BANCO（Betting on Noisy Coins），证明了其具有最优的性能表现，并将其应用于局部随机梯度下降算法以及多次对数定律的应用。

    Feb, 2019

  • 量子贝叶斯优化

    通过引入量子高斯过程 - 置信上界（Q-GP-UCB）算法，我们得到了第一个 BO 算法，可以在经典设置中将遗憾上界压缩为 O（对数多项式级别的 T），明显小于其遗憾下界 Omega（sqrt（T））。

    Oct, 2023

  • 离线赌博机中基于贝叶斯遗憾最小化的凸松弛方法

    本文提出了一种利用高效对偶锥优化器，直接最小化贝叶斯遗憾的上界以及与 VaR 和机遇约束优化之间的关系建立的边界的新方法来优化不确定环境下离线数据的决策问题，并与现有算法进行了比较。

    Jun, 2023