Sep, 2012

探讨赌博机和无导数随机凸优化的复杂性

PDF
TL;DR本文探讨了在带有巴氏反馈或者没有梯度知识下的凸随机优化问题。我们通过精确表征强凸平滑函数的性能以及非凸平滑函数的性能下界，证明了在这两种情况下，所需的查询次数至少要实现二次比例尺度关系。我们同时还发现对于二次函数，即使在没有梯度信息的情况下，也可以在平方次的询问内实现 O (1/T) 的误差率。此结果是在派生式随机情况下的首次结果，并且在之前暗示相反的情况下，依然成立。
stochastic convex optimizationbandit feedbackgradient-freelower boundsquadratic functions
发现论文，激发创造
  • 一种用于无导数平滑随机凸优化的加速方法

    本文研究优化问题中目标函数存在不确定的噪声干扰，提出了基于导数的无导数算法，考虑了稀疏向量情况下使用 1 范数正则化的优化模型。

    Feb, 2018

  • 带有强盗反馈的随机凸优化

    本文提出了一种基于随机赌博反馈模型的新型优化算法，采用椭球算法的泛化形式，对凸紧致集上的凸利普希茨（Lipschitz）函数最小化问题进行求解，证明其性能在满足一定条件下与时间步数 T 为 O（d^3/2）同阶，并获得了泛化性能的高阶乘性加速，表现出良好的应用前景和性能优势。

    Jul, 2011

  • 基于贝叶斯推断的网上凸优化：无梯度的梯度下降

    本文研究在线凸优化和赌博臂问题中的梯度近似算法，利用在单个随机点上估算的梯度实现在无法完全了解函数信息时的最优决策选择和回报最小化。

    Aug, 2004

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

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

    Jun, 2024

  • 联邦在线与强盗凸优化

    我们研究了面对自适应对手时的分布式在线和掷骰机凸优化问题。我们旨在在 $M$ 个并行工作的机器上通过 $T$ 轮和 $R$ 次间歇通信来最小化平均遗憾。在假设底层成本函数是凸函数并且可以自适应生成的情况下，我们的研究结果表明，在机器能够访问所查询点的一阶梯度信息时，合作是没有益处的。这与对于随机函数的情况形成了对比，其中每台机器从固定分布中抽样成本函数。此外，我们深入研究了带有掷骰机（零阶）反馈的联邦在线优化更具挑战性的情况，在该情况下，机器只能访问所查询点的成本函数值。这里的关键发现是确定合作有益且甚至可能导致机器数量的线性加速的高维度情况。我们通过开发新的分布式单点和双点反馈算法，进一步说明了我们的研究结果在联邦对抗线性掷骰机中的应用。我们的工作是对限制反馈的联邦在线优化的系统理解的首次尝试，并在间歇通信情况下获得了一阶和零阶反馈的严格遗憾界。因此，我们的研究填补了联邦在线优化中随机和自适应环境之间的差距。

    Nov, 2023

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

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

    Mar, 2016

  • 连续对抗波段的遗憾分析

    这篇研究论文提出了一个基于连续空间的成本函数的对决 Bandit 问题解决方案，介绍了一种随机镜像下降算法，并表明该算法在成本函数的强凸和平滑假设下实现了 O (sqrt (T log T)) 的遗憾界。此外，它还探讨了对决 Bandit 问题遗憾最小化与成本函数凸优化的等价性。

    Nov, 2017

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

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

    May, 2017

  • 关于标准和鲁棒高斯过程赌博优化的下限

    本文研究在 Reproducing Kernel Hilbert Space（RKHS）中具有有界范数的函数的黑盒优化问题的算法无关下限，并提供了在标准噪声和各类扰动下的决策边界。

    Aug, 2020

  • 带两点反馈的赌博机和零阶凸优化的最优算法

    本文介绍了一种基于梯度估计器的简单算法，可以在 convex Lipschitz 函数方面实现带有两个反馈信息的 bandit convex optimization 和带有两个函数评估的 zero-order stochastic convex optimization 问题的最优解，同时在比之前的算法更加简单的前提下可以扩展到非欧几里得问题。

    Jul, 2015