赌博机凸优化问题的最优算法
本文研究了在线凸优化的问题,在该问题中,决策者是风险规避的。我们提供了两个算法来解决这个问题。第一个是降落算法,易于实现。第二个算法结合了椭圆体方法和中心点装置,对于回合数实现了(几乎)最优的后悔界限。据我们所知,这是在在线凸博弈问题中首次尝试解决风险规避问题。
Oct, 2018
本文提出了一种基于随机赌博反馈模型的新型优化算法,采用椭球算法的泛化形式,对凸紧致集上的凸利普希茨(Lipschitz)函数最小化问题进行求解,证明其性能在满足一定条件下与时间步数 T 为 O(d^3/2)同阶,并获得了泛化性能的高阶乘性加速,表现出良好的应用前景和性能优势。
Jul, 2011
提出一种新的算法解决在无导数情况下的 $adversarial convex bandit$ 问题,其包含了核方法、伯努利卷积的一般化和新的退火时间表。这个算法在要求多次迭代的场景中可以取得佳效果。
Jul, 2016
本研究分析了在线凸优化问题在不同情境下的处理方法,并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板,同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外,通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较,我们证明了可以在面对不可避免对手时,设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此,我们提出了将一阶算法转换为零阶算法,并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化,如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析,我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。
Feb, 2024
本文提出一种基于条件梯度法的 projection-free 的算法,通过线性优化预测每一轮的动作并达到了 $O (T^{3/4})$ 的预期最小化损失 (expected regret)。
Oct, 2019
我们提出了一种高效的二阶算法,用于处理带依赖的多分类问题,同时考虑了由 ETA 参数化的一系列损失函数与竞争者的范式限制。算法能够同时处理从铰链损失 (ETA=0) 到平方铰链损失 (ETA=1) 的这一系列损失函数,这解决了 Abernethy 和 Rakhlin 在 COLT 2009 中的一个开放性问题,并通过实验与早期算法得到了良好的效果。
Feb, 2017
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
我们研究了面对自适应对手时的分布式在线和掷骰机凸优化问题。我们旨在在 $M$ 个并行工作的机器上通过 $T$ 轮和 $R$ 次间歇通信来最小化平均遗憾。在假设底层成本函数是凸函数并且可以自适应生成的情况下,我们的研究结果表明,在机器能够访问所查询点的一阶梯度信息时,合作是没有益处的。这与对于随机函数的情况形成了对比,其中每台机器从固定分布中抽样成本函数。此外,我们深入研究了带有掷骰机(零阶)反馈的联邦在线优化更具挑战性的情况,在该情况下,机器只能访问所查询点的成本函数值。这里的关键发现是确定合作有益且甚至可能导致机器数量的线性加速的高维度情况。我们通过开发新的分布式单点和双点反馈算法,进一步说明了我们的研究结果在联邦对抗线性掷骰机中的应用。我们的工作是对限制反馈的联邦在线优化的系统理解的首次尝试,并在间歇通信情况下获得了一阶和零阶反馈的严格遗憾界。因此,我们的研究填补了联邦在线优化中随机和自适应环境之间的差距。
Nov, 2023