Jul, 2016

基于核的赌博式凸优化方法

PDF
TL;DR提出一种新的算法解决在无导数情况下的 $adversarial convex bandit$ 问题，其包含了核方法、伯努利卷积的一般化和新的退火时间表。这个算法在要求多次迭代的场景中可以取得佳效果。
adversarial convex bandit problemkernel methodsderivative-free optimizationexponential weightsregret
发现论文，激发创造
  • 赌博机凸优化问题的最优算法

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

    Mar, 2016

  • 在线牛顿方法在博弈凸优化问题中的应用

    零阶强化学习的计算方法在对抗性和随机性设置中的性能界限及其与维度的关系

    Jun, 2024

  • 对于带噪声高斯过程赌博优化的损失下界

    本文考虑如何基于无噪声样本和 Bandit 反馈来顺序优化黑盒函数，提出了一种新的 Gaussian 过程 Bandit 优化算法，并给出了算法无关的简单遗憾和累计遗憾的下界，进一步阐述了随机波动和目标函数的连续性对累计遗憾和简单遗憾的影响。

    May, 2017

  • 用一种新的平滑度对抗强盗

    定义了一种新的算法家族，用于对抗性多臂赌博问题，并提供基于凸平滑的简单分析技术。通过使用 Tsallis 熵进行正则化，证明了它的最小极大后悔度为 Θ(√TN)；同时，对于具有有界危害率的微扰分布，广泛类的扰动方法可获得近乎最优的后悔率，低至 O (√TN log N)，例如 Gumbel、Weibull、Frechet、Pareto 和 Gamma 分布都满足此特性。

    Dec, 2015

  • 一种几乎具有最优伪遗憾的算法，适用于随机和对抗性贝叶斯赌博机

    本研究提出了一种算法，能够在对抗式和随机式赌徒问题中实现几乎最优的伪后悔界限，并表明任何在随机式赌徒问题中具有 O (log n) 伪后悔界限的算法都无法对自适应对抗式赌徒问题实现 O (sqrt (n)) 的期望后悔。

    May, 2016

  • 针对零阶对抗性 Bandit 凸优化的改进遗憾

    以信息论为基础，改进探索性分布以在零阶对抗性 bandit 凸优化的 minimax regret 的信息理论上界上证明其为 O (d^{2.5} 根号 n 对数 (n))，并提高 Bubeck 等人 (2017) 的 O (d^{9.5} 根号 n 对数 (n)^{7.5} 上界。

    May, 2020

  • 一维贝叶斯优化的紧遗憾界

    对于一维高斯过程先验和高斯采样噪声下的贝叶斯优化问题，本研究提供了一个理论分析，证明在核函数的一些温和技术假设下，到时间 T 时最好的累积遗憾表现为 Ω(√T) 和 O (√TlogT)，这给出了一个紧密的特征，证明了现有界限的接近最优性 (对于 SE 核)，同时证明了它们对于 Matern 核 (nu>2) 是严格的次优的。

    May, 2018

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

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

    Oct, 2019

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

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

    Feb, 2017

  • 多对数级别的极小极大遗憾的线性赌博机

    研究线性随机赌博机的噪声模型，介绍一种基于加权最小二乘估计的算法，能够最小化后悔度，通过几何论证独立于噪声模型，能够紧密控制每个时间步骤的期望后悔度为 O (1/t)，从而导致了累积后悔度的对数缩放。

    Feb, 2024