多方偏好加速收敛
本文介绍了一种基于梯度估计器的简单算法,可以在 convex Lipschitz 函数方面实现带有两个反馈信息的 bandit convex optimization 和带有两个函数评估的 zero-order stochastic convex optimization 问题的最优解,同时在比之前的算法更加简单的前提下可以扩展到非欧几里得问题。
Jul, 2015
我们研究了面对自适应对手时的分布式在线和掷骰机凸优化问题。我们旨在在 $M$ 个并行工作的机器上通过 $T$ 轮和 $R$ 次间歇通信来最小化平均遗憾。在假设底层成本函数是凸函数并且可以自适应生成的情况下,我们的研究结果表明,在机器能够访问所查询点的一阶梯度信息时,合作是没有益处的。这与对于随机函数的情况形成了对比,其中每台机器从固定分布中抽样成本函数。此外,我们深入研究了带有掷骰机(零阶)反馈的联邦在线优化更具挑战性的情况,在该情况下,机器只能访问所查询点的成本函数值。这里的关键发现是确定合作有益且甚至可能导致机器数量的线性加速的高维度情况。我们通过开发新的分布式单点和双点反馈算法,进一步说明了我们的研究结果在联邦对抗线性掷骰机中的应用。我们的工作是对限制反馈的联邦在线优化的系统理解的首次尝试,并在间歇通信情况下获得了一阶和零阶反馈的严格遗憾界。因此,我们的研究填补了联邦在线优化中随机和自适应环境之间的差距。
Nov, 2023
本文提出了一种基于随机序列算法的最小化极限风险收敛速率的方法,其鲁棒性得到了保证, 并对于损失函数的凸度及输出分布中的噪声级别等因素,提供了紧凑的可执行上限界。
Mar, 2007
在本篇论文中,我们考虑了在强凸集上进行的优化的特殊情况。我们证明,与一般情况的收敛速度为 1/t 相比,vanila FW 方法以 1/t² 的速度收敛。我们还展示了如何通过在这些集合上进行线性优化来推导 FW 方法的多个快速收敛结果。
Jun, 2014
该研究探讨了使用函数值而不是梯度的无导数算法在随机和非随机凸优化问题中的应用,同时关注其收敛速率,经实验表明使用随机扰动的梯度估算方法具有比传统随机梯度方法更快的收敛速率,尤其在光滑和非光滑情况下,且可以扩展到多次评估的情况。
Dec, 2013
本文提出了一种基于贝叶斯优化和偏好探索的框架,通过实时采用基于成对比较的交互式学习和使用基于学习到的 DM 效用和结果的组合模型的贝叶斯优化来进行昂贵评估实验的优化。通过详细的模拟研究验证了偏好探索策略的表现。
Mar, 2022
对抗性多对决赌博机中的后悔最小化问题进行了介绍,并引入了一种新算法 MiDEX(Multi Dueling EXP3)来学习来自成对子集选择模型的偏好反馈。证明了 MiDEX 相对于从 K 个臂中选择 Borda 赢家的累计 T 轮后悔的期望上界为 O ((KlogK)^{1/3} T^{2/3}),同时证明了在该设置下预期后悔的下界为 Ω(K^{1/3} T^{2/3}),表明我们提出的算法是接近最优的。
Jun, 2024