在线凸优化算法(无内存限制)
有关在线凸优化和约束在线凸优化的一篇研究论文,证明了一个在线策略可以同时实现 O (√T) 的遗憾和 θ̃(√T) 的累积约束违规,通过将 AdaGrad 算法的自适应遗憾界与 Lyapunov 优化相结合,达到了这一结果。
May, 2024
我们研究了经典的在线凸优化(OCO)框架的一种推广,通过考虑额外的长期对抗性约束。我们提出了一种元策略,能够同时达到亚线性的累积约束违规和亚线性的遗憾,通过将约束问题转化为递归构建的一系列代理代价函数的标准 OCO 问题的黑盒减缩。我们展示了通过使用任何享有标准数据相关遗憾上界的自适应 OCO 策略求解代理问题,可以达到最优性能界限。通过一种新的基于李雅普诺夫的证明技术,我们揭示了遗憾和某些顺序不等式之间的联系,通过一种新颖的分解结果。最后,我们强调了在在线多任务学习和网络控制问题中的应用。
Oct, 2023
本文提出了一种基于 Online Convex Optimization with Memory 与 Frank-Wolfe 算法的无投影元基学习算法,可以实现投影 - 免费的在线学习,应用于自适应时变环境控制等领域。
Jan, 2023
我们在分散的在线凸优化中(D-OCO),通过仅使用本地计算和通信来最小化一系列全局损失函数的一组本地学习器。我们首先开发了一种新颖的 D-OCO 算法,将凸函数和强凸函数的遗憾边界分别降低到 O (nρ^{−1/4}√T) 和 O (nρ^{−1/2} log T)。通过设计一种在线加速的谣言策略并巧妙利用特定网络拓扑的谱特性,我们进一步提高了凸函数和强凸函数的下界为 Ω(nρ^{−1/4}√T) 和 Ω(nρ^{−1/2})。
Feb, 2024
在线凸优化(OCO)的未知约束设置是近年来备受关注的问题。本研究考虑了一种具有静态线性约束且玩家接收到噪声反馈并始终满足的问题版本。通过利用我们的乐观安全设计范例,我们提供了一种算法来解决该问题,其后悔值为 O (√T)。这比之前最佳后悔边界 O (T^2/3) 有所改进,并且只使用了更强烈一些的独立噪声和无意识对手的假设。然后,我们将该问题重新表述为随时间变化的随机线性约束下的 OCO 问题,并证明了我们的算法在这样的设置中具有相同的后悔保证,并且预期上不违反约束。这对于 OCO 在随时间变化的随机约束下的文献做出了贡献,其最先进的算法在约束为凸约束且玩家接收到完整反馈时具有 O (√T) 的后悔和 O (√T) 的违规。此外,我们提供了更加高效的算法版本,并通过与基准算法进行了数值实验比较。
Mar, 2024
研究了在线环境下的通用拟阵约束下的单调子模最大化问题,证明了一大类子模函数在在线凸优化问题中的优化等价性,通过合适的舍入方案,实现了在组合优化中达到次线性后悔的 OCO 算法。同时,该规约也适用于多种不同版本的在线学习问题,包括动态后悔、游走和乐观学习等。
Sep, 2023
该论文探讨了在线凸优化涉及敌对损失函数和敌对约束的情况,开发了一种修改的在线鞍点(MOSP)方案,并在动态网络资源分配任务中进行了应用,证明了其相对于梯度方法的性能优势。
Jan, 2017
研究了涉及亚指数噪声的无约束在线凸优化问题,设计了一种新的巴拿赫空间参数自由 OCO 算法 BANCO(Betting on Noisy Coins),证明了其具有最优的性能表现,并将其应用于局部随机梯度下降算法以及多次对数定律的应用。
Feb, 2019
基于在线凸优化和曲率的可行集合的分析,本文提出了一种新的方法通过利用可行集合的曲率来实现快速收敛,不仅可以适用于凸损失函数,同时还能在随机、对抗性和受干扰的环境下获得良好的性能。
Feb, 2024