Dec, 2023

在线鞍点问题与在线凸凹优化

PDF
TL;DR该研究论文围绕解决在线鞍点问题，引入了在线凸凹优化（OCCO）框架，该框架涉及一系列二人时变凸凹博弈。我们提出了广义对偶间隙（Dual-Gap）作为性能度量，并建立了 OCCO 与 Dual-Gap 之间与在线凸优化（OCO）与后悔之间的并行关系。为了展示 OCCO 从 OCO 的自然扩展，我们开发了两种算法：隐式在线镜象下降 - 上升和其乐观变体。分析表明，它们的对偶间隙与 OCO 中隐式更新导致的相应动态后悔具有类似的表达形式。实证结果进一步证明了我们算法的有效性。同时，我们揭示了最近一篇论文中最初引入的动态 Nash 均衡后悔具有固有的缺陷。
发现论文，激发创造
  • 在线鞍点问题与背包约束下的在线凸优化

    本文研究了在线鞍点问题和应用，提出了一些算法，包括使用基本对偶方法解决在线鞍点问题以及应用于动态定价、竞拍和众包等问题。

    Jun, 2018

  • 一种动态网络资源分配的在线凸优化方法

    该论文探讨了在线凸优化涉及敌对损失函数和敌对约束的情况，开发了一种修改的在线鞍点（MOSP）方案，并在动态网络资源分配任务中进行了应用，证明了其相对于梯度方法的性能优势。

    Jan, 2017

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

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

    May, 2024

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

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

    Oct, 2022

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

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

    Aug, 2017

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

    我们在分散的在线凸优化中（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

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

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

    Sep, 2023

  • 高效牛顿迭代算法实现无投影在线凸优化

    本文提出了一种新的在线凸优化投影免费算法，并通过利用牛顿迭代的稳定性来计算逆海森矩阵以获得具有最先进遗憾边界的新的高效算法。

    Jun, 2023

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

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

    May, 2023