Feb, 2024

分散式在线凸优化的近优遗憾

PDF
TL;DR我们在分散的在线凸优化中（D-OCO），通过仅使用本地计算和通信来最小化一系列全局损失函数的一组本地学习器。我们首先开发了一种新颖的 D-OCO 算法，将凸函数和强凸函数的遗憾边界分别降低到 O (nρ^{−1/4}√T) 和 O (nρ^{−1/2} log T)。通过设计一种在线加速的谣言策略并巧妙利用特定网络拓扑的谱特性，我们进一步提高了凸函数和强凸函数的下界为 Ω(nρ^{−1/4}√T) 和 Ω(nρ^{−1/2})。
decentralized online convex optimizationregret boundslocal learnersspectral propertiesnetwork topology
发现论文，激发创造
  • 具有对抗约束的在线凸优化的严格界

    有关在线凸优化和约束在线凸优化的一篇研究论文，证明了一个在线策略可以同时实现 O (√T) 的遗憾和 θ̃(√T) 的累积约束违规，通过将 AdaGrad 算法的自适应遗憾界与 Lyapunov 优化相结合，达到了这一结果。

    May, 2024

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

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

    Feb, 2024

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

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

    Aug, 2017

  • 在线凸优化算法（无内存限制）

    本文提出了一个新的在线凸优化框架，能够利用过去的决策历史对当前损失进行建模，并引入了 “p 有效内存容量” 来量化过去决策对当前损失的最大影响。在此框架下，证明了一些政策遗憾的较好上界，并展示了该框架对于各种在线学习任务的适用性。

    Oct, 2022

  • 不依赖利普希茨连续性的遗憾界：相对利普希茨损失下的在线学习

    本研究考虑在线凸优化问题的相对 Lipschitz 收敛性和相对强凸性，扩展了已知的算法在相对设置下的遗憾界，特别是基于正则聚类领导者算法和在线镜像下降算法的算法，同时将这些结果进一步扩展到具有额外正则化的算法。

    Oct, 2020

  • 线性约束在线凸优化的乐观安全性

    在线凸优化（OCO）的未知约束设置是近年来备受关注的问题。本研究考虑了一种具有静态线性约束且玩家接收到噪声反馈并始终满足的问题版本。通过利用我们的乐观安全设计范例，我们提供了一种算法来解决该问题，其后悔值为 O (√T)。这比之前最佳后悔边界 O (T^2/3) 有所改进，并且只使用了更强烈一些的独立噪声和无意识对手的假设。然后，我们将该问题重新表述为随时间变化的随机线性约束下的 OCO 问题，并证明了我们的算法在这样的设置中具有相同的后悔保证，并且预期上不违反约束。这对于 OCO 在随时间变化的随机约束下的文献做出了贡献，其最先进的算法在约束为凸约束且玩家接收到完整反馈时具有 O (√T) 的后悔和 O (√T) 的违规。此外，我们提供了更加高效的算法版本，并通过与基准算法进行了数值实验比较。

    Mar, 2024

  • 每轮只需 1 个投影的通用在线凸优化

    通过黑匣子减少，我们使用简化域上定义的替代损失函数，构建了一种只需要进行一次投影的通用 OCO 算法，对于一轮在线问题，我们维护每种类型函数的一组专家，并通过元算法聚合他们的预测。我们的方法的关键在于针对强凸函数设计的专家损失函数，并通过创新地将遗憾分解为元遗憾和专家遗憾，从而对替代损失函数的遗憾和原损失函数的遗憾之间的差异进行了严格的研究，并在强凸性条件下仔细控制了元遗憾。通过这种方式，我们建立了一轮中的通用凸函数、指数凹函数和强凸函数的最优遗憾上界，并通过增强专家损失函数来利用光滑性质，从而证明了我们的算法可以达到多种类型的凸函数和光滑函数的小损失遗憾。

    May, 2024

  • 具有次指数噪声的无参数在线凸优化

    研究了涉及亚指数噪声的无约束在线凸优化问题，设计了一种新的巴拿赫空间参数自由 OCO 算法 BANCO（Betting on Noisy Coins），证明了其具有最优的性能表现，并将其应用于局部随机梯度下降算法以及多次对数定律的应用。

    Feb, 2019

  • 任意延迟的非平稳在线凸优化

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

    May, 2023

  • 指数凸在线学习的最优动态遗憾

    使用先进的证明技术和 Zinkevich-style 动态遗憾最小化框架，本研究提出了一个强适应的在线学习算法，其总变化控制下的动态遗憾为 O (n^(1/3)*C_n^(2/3))，并且可以扩展到局部自适应非参数回归问题中。

    Apr, 2021