Oct, 2023

具有切换成本和延迟梯度的在线凸优化

PDF
TL;DR在线凸优化问题中，我们考虑带有二次和线性切换成本的有限信息环境下的问题，通过使用关于先前目标函数的梯度信息，我们提出了在线多梯度下降算法 (Online Multiple Gradient Descent, OMGD)，并证明了其在二次切换成本的 OCO 问题的竞争比为至多 4 (L + 5) + (16 (L + 5))/μ。对于有界信息环境中的在线算法，其竞争比的上界和下界分别为 max {Ω(L), Ω(L/√μ)}。此外，还证明了 OMGD 算法实现了有限信息环境下的动态最优（按顺序）遗憾，并且对于线性切换成本，OMGD 算法的竞争比的上界取决于问题实例的路径长度、平方路径长度以及 L、μ，并且被证明是任何在线算法能够达到的最佳竞争比。因此，我们得出结论，在有限信息环境中，二次和线性切换成本的最优竞争比基本上是不同的。
online convex optimizationswitching costlimited information settingonline multiple gradient descentcompetitive ratio
发现论文，激发创造
  • 任意延迟的非平稳在线凸优化

    研究了非平稳环境下具任意延迟的在线凸优化问题，提出了一个简单的算法 DOGD，通过运用多个学习率的 DOGD，并跟踪最佳 one 的延迟性能，将动态遗憾边界降至 O (根号下 d*T*(P_T+1)) 和 O (根号下 S (1+P_T))，并毫无例外地证明了这是最优的。

    May, 2023

  • 平滑在线优化的最优算法：超越在线平衡下降

    研究了在线凸优化中的竞争比率和算法，证明了一个新的下限。同时提出了两种新的算法，G-OBD 和 R-OBD 并证明了其具有 $O (m^{-1/2})$ 的竞争比率及成功降低了回归成本。

    May, 2019

  • 具有对抗约束的在线凸优化的严格界

    有关在线凸优化和约束在线凸优化的一篇研究论文，证明了一个在线策略可以同时实现 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

  • 改进的差分隐私和惰性在线凸优化

    研究目标为（ε, δ）- 差分隐私在线凸优化（OCO），通过引入强对数凹密度的抽样，提升维度因子并消除平滑性要求，进而改进了（ε）非常小的情况下 Agarwal 等人的结果，达到了该领域已知的最佳速率。

    Dec, 2023

  • 利用可行集的曲率在在线凸优化中获得快速速率

    基于在线凸优化和曲率的可行集合的分析，本文提出了一种新的方法通过利用可行集合的曲率来实现快速收敛，不仅可以适用于凸损失函数，同时还能在随机、对抗性和受干扰的环境下获得良好的性能。

    Feb, 2024

  • 在线凸优化下的在线次模最大化

    研究了在线环境下的通用拟阵约束下的单调子模最大化问题，证明了一大类子模函数在在线凸优化问题中的优化等价性，通过合适的舍入方案，实现了在组合优化中达到次线性后悔的 OCO 算法。同时，该规约也适用于多种不同版本的在线学习问题，包括动态后悔、游走和乐观学习等。

    Sep, 2023

  • 具有未知延迟的在线顺序决策

    在在线顺序决策的领域中，我们利用在线凸优化（OCO）框架解决带有延迟的问题，其中决策的反馈可能会有未知的延迟。我们提出了三类基于近似解的延迟算法，以处理不同类型的接收反馈。我们提出的算法多功能且适用于通用范数，在每种算法类型下给出了相应的遗憾界限。我们通过具体示例展示了每种算法在不同范数下的效率，并且理论结果在标准设置下与当前最佳界限一致。

    Feb, 2024

  • 随机约束下的在线凸优化

    本文研究带随机约束的在线凸优化问题，提出了一种算法，能够达到预期和高概率的收益掉队和约束违反值等性能保证，并在真实数据中心调度问题上进行了实验验证。

    Aug, 2017

  • 具备预测和转换成本的在线优化：快速算法和基本极限

    本文研究了具有有限预测窗口和附加决策切换成本的在线优化问题。提出了两种基于梯度的在线算法：RHGD 和 RHAG。该文章报告了这些算法的动态遗憾的上限，并且发现我们的基于梯度的 RHAG 算法是一种接近最优的在线算法。

    Jan, 2018