风险规避的随机凸臂老虎机
本文针对带有随机反馈的在线凸优化问题(称为 bandit convex optimization),通过将椭球法应用于在线学习,给出了第一个 $\tilde {O}(\sqrt {T})$-regret 算法,并引入了离散凸几何中的新工具。
Mar, 2016
本文提出了一种基于随机赌博反馈模型的新型优化算法,采用椭球算法的泛化形式,对凸紧致集上的凸利普希茨(Lipschitz)函数最小化问题进行求解,证明其性能在满足一定条件下与时间步数 T 为 O(d^3/2)同阶,并获得了泛化性能的高阶乘性加速,表现出良好的应用前景和性能优势。
Jul, 2011
本研究分析了在线凸优化问题在不同情境下的处理方法,并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板,同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外,通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较,我们证明了可以在面对不可避免对手时,设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此,我们提出了将一阶算法转换为零阶算法,并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化,如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析,我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。
Feb, 2024
我们研究了面对自适应对手时的分布式在线和掷骰机凸优化问题。我们旨在在 $M$ 个并行工作的机器上通过 $T$ 轮和 $R$ 次间歇通信来最小化平均遗憾。在假设底层成本函数是凸函数并且可以自适应生成的情况下,我们的研究结果表明,在机器能够访问所查询点的一阶梯度信息时,合作是没有益处的。这与对于随机函数的情况形成了对比,其中每台机器从固定分布中抽样成本函数。此外,我们深入研究了带有掷骰机(零阶)反馈的联邦在线优化更具挑战性的情况,在该情况下,机器只能访问所查询点的成本函数值。这里的关键发现是确定合作有益且甚至可能导致机器数量的线性加速的高维度情况。我们通过开发新的分布式单点和双点反馈算法,进一步说明了我们的研究结果在联邦对抗线性掷骰机中的应用。我们的工作是对限制反馈的联邦在线优化的系统理解的首次尝试,并在间歇通信情况下获得了一阶和零阶反馈的严格遗憾界。因此,我们的研究填补了联邦在线优化中随机和自适应环境之间的差距。
Nov, 2023
针对在线凸优化中的时间变化的损失函数和约束条件进行分析,提出了一种 bandit online saddle-point(BanSaP)算法,该算法可适应不断变化的损失函数和环境,同时进行优化,在雾计算下的实验表明相对于已有的基于梯度反馈的算法,提出的方法提供了竞争性的性能。
Jul, 2017
近年来,与人类不断互动的现实世界安全关键系统中的强盗优化引起了极大关注。本文提出了一个综合性研究,重点研究了安全线性强盗算法的计算方面,通过引入凸规划工具创建了计算效率高的策略。具体而言,我们首先对安全线性强盗问题的最优策略进行了特征化,并提出了一个仅涉及求解凸问题的端到端安全线性强盗算法流程。我们还对我们提出的方法的性能进行了数值评估。
Nov, 2023
本文提出了一种利用高效对偶锥优化器,直接最小化贝叶斯遗憾的上界以及与 VaR 和机遇约束优化之间的关系建立的边界的新方法来优化不确定环境下离线数据的决策问题,并与现有算法进行了比较。
Jun, 2023
提出了一种新颖的算法,采用乐观性和适应性技术,结合在线镜像下降框架和特殊的对数障碍正则化器来解决对抗性多臂赌博机问题和组合半赌博问题,并在提高先前工作的同时,取得了多种新的数据依赖性遗憾界。
Jan, 2018