一种动态网络资源分配的在线凸优化方法
有关在线凸优化和约束在线凸优化的一篇研究论文,证明了一个在线策略可以同时实现 O (√T) 的遗憾和 θ̃(√T) 的累积约束违规,通过将 AdaGrad 算法的自适应遗憾界与 Lyapunov 优化相结合,达到了这一结果。
May, 2024
我们研究了经典的在线凸优化(OCO)框架的一种推广,通过考虑额外的长期对抗性约束。我们提出了一种元策略,能够同时达到亚线性的累积约束违规和亚线性的遗憾,通过将约束问题转化为递归构建的一系列代理代价函数的标准 OCO 问题的黑盒减缩。我们展示了通过使用任何享有标准数据相关遗憾上界的自适应 OCO 策略求解代理问题,可以达到最优性能界限。通过一种新的基于李雅普诺夫的证明技术,我们揭示了遗憾和某些顺序不等式之间的联系,通过一种新颖的分解结果。最后,我们强调了在在线多任务学习和网络控制问题中的应用。
Oct, 2023
该研究论文围绕解决在线鞍点问题,引入了在线凸凹优化(OCCO)框架,该框架涉及一系列二人时变凸凹博弈。我们提出了广义对偶间隙(Dual-Gap)作为性能度量,并建立了 OCCO 与 Dual-Gap 之间与在线凸优化(OCO)与后悔之间的并行关系。为了展示 OCCO 从 OCO 的自然扩展,我们开发了两种算法:隐式在线镜象下降 - 上升和其乐观变体。分析表明,它们的对偶间隙与 OCO 中隐式更新导致的相应动态后悔具有类似的表达形式。实证结果进一步证明了我们算法的有效性。同时,我们揭示了最近一篇论文中最初引入的动态 Nash 均衡后悔具有固有的缺陷。
Dec, 2023
本文提出了一个新的在线凸优化框架,能够利用过去的决策历史对当前损失进行建模,并引入了 “p 有效内存容量” 来量化过去决策对当前损失的最大影响。在此框架下,证明了一些政策遗憾的较好上界,并展示了该框架对于各种在线学习任务的适用性。
Oct, 2022
研究了非平稳环境下具任意延迟的在线凸优化问题,提出了一个简单的算法 DOGD,通过运用多个学习率的 DOGD,并跟踪最佳 one 的延迟性能,将动态遗憾边界降至 O (根号下 d*T*(P_T+1)) 和 O (根号下 S (1+P_T)),并毫无例外地证明了这是最优的。
May, 2023
针对在线凸优化中的时间变化的损失函数和约束条件进行分析,提出了一种 bandit online saddle-point(BanSaP)算法,该算法可适应不断变化的损失函数和环境,同时进行优化,在雾计算下的实验表明相对于已有的基于梯度反馈的算法,提出的方法提供了竞争性的性能。
Jul, 2017
本文提出了一种基于 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