波段凸优化
近年来,与人类不断互动的现实世界安全关键系统中的强盗优化引起了极大关注。本文提出了一个综合性研究,重点研究了安全线性强盗算法的计算方面,通过引入凸规划工具创建了计算效率高的策略。具体而言,我们首先对安全线性强盗问题的最优策略进行了特征化,并提出了一个仅涉及求解凸问题的端到端安全线性强盗算法流程。我们还对我们提出的方法的性能进行了数值评估。
Nov, 2023
本文介绍了一种基于梯度估计器的简单算法,可以在 convex Lipschitz 函数方面实现带有两个反馈信息的 bandit convex optimization 和带有两个函数评估的 zero-order stochastic convex optimization 问题的最优解,同时在比之前的算法更加简单的前提下可以扩展到非欧几里得问题。
Jul, 2015
本文研究了在线凸优化的问题,在该问题中,决策者是风险规避的。我们提供了两个算法来解决这个问题。第一个是降落算法,易于实现。第二个算法结合了椭圆体方法和中心点装置,对于回合数实现了(几乎)最优的后悔界限。据我们所知,这是在在线凸博弈问题中首次尝试解决风险规避问题。
Oct, 2018
本文针对带有随机反馈的在线凸优化问题(称为 bandit convex optimization),通过将椭球法应用于在线学习,给出了第一个 $\tilde {O}(\sqrt {T})$-regret 算法,并引入了离散凸几何中的新工具。
Mar, 2016
我们研究了面对自适应对手时的分布式在线和掷骰机凸优化问题。我们旨在在 $M$ 个并行工作的机器上通过 $T$ 轮和 $R$ 次间歇通信来最小化平均遗憾。在假设底层成本函数是凸函数并且可以自适应生成的情况下,我们的研究结果表明,在机器能够访问所查询点的一阶梯度信息时,合作是没有益处的。这与对于随机函数的情况形成了对比,其中每台机器从固定分布中抽样成本函数。此外,我们深入研究了带有掷骰机(零阶)反馈的联邦在线优化更具挑战性的情况,在该情况下,机器只能访问所查询点的成本函数值。这里的关键发现是确定合作有益且甚至可能导致机器数量的线性加速的高维度情况。我们通过开发新的分布式单点和双点反馈算法,进一步说明了我们的研究结果在联邦对抗线性掷骰机中的应用。我们的工作是对限制反馈的联邦在线优化的系统理解的首次尝试,并在间歇通信情况下获得了一阶和零阶反馈的严格遗憾界。因此,我们的研究填补了联邦在线优化中随机和自适应环境之间的差距。
Nov, 2023
针对在线凸优化中的时间变化的损失函数和约束条件进行分析,提出了一种 bandit online saddle-point(BanSaP)算法,该算法可适应不断变化的损失函数和环境,同时进行优化,在雾计算下的实验表明相对于已有的基于梯度反馈的算法,提出的方法提供了竞争性的性能。
Jul, 2017
本文研究非凸奖励的赌博机问题,提出了一种适用于一类具有非凸奖励函数的赌博机算法,通过统一的零阶优化范式达到了多项式设置下的最优速率,并在生成模型的 RL 中实现了算法的应用,从而取得了比之前方法更好的样本复杂度。
Jul, 2021