任意延迟的非平稳在线凸优化
在在线顺序决策的领域中,我们利用在线凸优化(OCO)框架解决带有延迟的问题,其中决策的反馈可能会有未知的延迟。我们提出了三类基于近似解的延迟算法,以处理不同类型的接收反馈。我们提出的算法多功能且适用于通用范数,在每种算法类型下给出了相应的遗憾界限。我们通过具体示例展示了每种算法在不同范数下的效率,并且理论结果在标准设置下与当前最佳界限一致。
Feb, 2024
在线凸优化问题中,我们考虑带有二次和线性切换成本的有限信息环境下的问题,通过使用关于先前目标函数的梯度信息,我们提出了在线多梯度下降算法 (Online Multiple Gradient Descent, OMGD),并证明了其在二次切换成本的 OCO 问题的竞争比为至多 4 (L + 5) + (16 (L + 5))/μ。对于有界信息环境中的在线算法,其竞争比的上界和下界分别为 max {Ω(L), Ω(L/√μ)}。此外,还证明了 OMGD 算法实现了有限信息环境下的动态最优(按顺序)遗憾,并且对于线性切换成本,OMGD 算法的竞争比的上界取决于问题实例的路径长度、平方路径长度以及 L、μ,并且被证明是任何在线算法能够达到的最佳竞争比。因此,我们得出结论,在有限信息环境中,二次和线性切换成本的最优竞争比基本上是不同的。
Oct, 2023
有关在线凸优化和约束在线凸优化的一篇研究论文,证明了一个在线策略可以同时实现 O (√T) 的遗憾和 θ̃(√T) 的累积约束违规,通过将 AdaGrad 算法的自适应遗憾界与 Lyapunov 优化相结合,达到了这一结果。
May, 2024
我们在分散的在线凸优化中(D-OCO),通过仅使用本地计算和通信来最小化一系列全局损失函数的一组本地学习器。我们首先开发了一种新颖的 D-OCO 算法,将凸函数和强凸函数的遗憾边界分别降低到 O (nρ^{−1/4}√T) 和 O (nρ^{−1/2} log T)。通过设计一种在线加速的谣言策略并巧妙利用特定网络拓扑的谱特性,我们进一步提高了凸函数和强凸函数的下界为 Ω(nρ^{−1/4}√T) 和 Ω(nρ^{−1/2})。
Feb, 2024
本文研究动态环境下的在线凸优化问题,通过提出一种自适应学习的方法 Ader,利用专家跟踪算法结合一组专家来最小化动态遗憾,并扩展到可用于表征比较器的动态模型序列的情形。
Oct, 2018
该论文探讨了在线凸优化涉及敌对损失函数和敌对约束的情况,开发了一种修改的在线鞍点(MOSP)方案,并在动态网络资源分配任务中进行了应用,证明了其相对于梯度方法的性能优势。
Jan, 2017
在线凸优化(OCO)的未知约束设置是近年来备受关注的问题。本研究考虑了一种具有静态线性约束且玩家接收到噪声反馈并始终满足的问题版本。通过利用我们的乐观安全设计范例,我们提供了一种算法来解决该问题,其后悔值为 O (√T)。这比之前最佳后悔边界 O (T^2/3) 有所改进,并且只使用了更强烈一些的独立噪声和无意识对手的假设。然后,我们将该问题重新表述为随时间变化的随机线性约束下的 OCO 问题,并证明了我们的算法在这样的设置中具有相同的后悔保证,并且预期上不违反约束。这对于 OCO 在随时间变化的随机约束下的文献做出了贡献,其最先进的算法在约束为凸约束且玩家接收到完整反馈时具有 O (√T) 的后悔和 O (√T) 的违规。此外,我们提供了更加高效的算法版本,并通过与基准算法进行了数值实验比较。
Mar, 2024
本文提出了一个新的在线凸优化框架,能够利用过去的决策历史对当前损失进行建模,并引入了 “p 有效内存容量” 来量化过去决策对当前损失的最大影响。在此框架下,证明了一些政策遗憾的较好上界,并展示了该框架对于各种在线学习任务的适用性。
Oct, 2022
本研究中,我们在边缘学习方面进行了调查,探讨了在线凸优化问题下的对抗性延迟反馈,提出了两种无投影算法,用于集中式和分布式环境中,通过与现有方法在真实世界问题上的比较,我们理论上和实验证明了算法的性能,实现了延迟环境中 OCO 问题的 O (√B) 的后悔界。
Feb, 2024