利用可行集的曲率在在线凸优化中获得快速速率
内容提要
本文综述在线凸优化（OCO）的研究进展，涵盖分散式D-OCO算法（降低遗憾界并证明下界）、随机约束算法在数据中心调度中的应用、基于历史损失建模的记忆容量量化、相对Lipschitz与强凸性研究、拟阵约束下的子模最大化、约束OCO向凸-凹优化的转化、对抗时变约束算法、任意延迟非平稳OCO、连续次模函数的Frank-Wolfe变体，以及带切换成本的有限信息OCO竞争比分析。
延伸解读
分散式在线凸优化的理论突破
文章介绍了分散式在线凸优化（D-OCO）中遗憾界的新进展。通过仅使用本地计算和通信，新算法将凸和强凸函数的遗憾界分别降至O(nρ^{-1/4}√T)和O(nρ^{-1/2} log T)，并利用在线加速谣言策略和网络拓扑谱特性，证明了匹配的下界。这表明在分散设置下，凸和强凸问题的遗憾界已达到最优，为多智能体在线学习提供了理论保障。
随机约束在线凸优化的实际应用
针对带随机约束的在线凸优化问题，文章提出了一种算法，能在期望和高概率下保证收益掉队和约束违反值等性能，并在真实数据中心调度问题上进行了实验验证。这显示了在线凸优化在资源调度等实际场景中的潜力，同时强调了算法需兼顾性能保证与约束满足，为相关应用提供了参考。
非平稳与延迟环境下的算法进展
文章涵盖了非平稳环境下具任意延迟的在线凸优化问题，提出的DOGD算法通过多学习率跟踪最佳延迟性能，将动态遗憾边界降至O(√(d*T*(P_T+1)))和O(√(S(1+P_T)))，并证明其最优性。此外，对抗时变约束的算法通过线性优化预言机实现了O(T^{3/4})的遗憾和O(T^{7/8})的约束违反。这些结果有助于理解复杂动态环境中的在线学习极限。
Q&A
分散式在线凸优化（D-OCO）中，最新的算法在遗憾界和下界方面取得了哪些改进？
最新的D-OCO算法将凸函数和强凸函数的遗憾界分别降低到O(nρ^{-1/4}√T)和O(nρ^{-1/2} log T)，并通过在线加速的谣言策略和利用网络拓扑的谱特性，将下界提高到Ω(nρ^{-1/4}√T)和Ω(nρ^{-1/2})。
在线凸优化中如何处理随机约束？有什么实际应用？
针对带随机约束的在线凸优化问题，有算法能够达到预期和高概率的收益掉队和约束违反值等性能保证，并在真实数据中心调度问题上进行了实验验证。
什么是在线凸优化中的“p有效内存容量”？它有什么作用？
“p有效内存容量”是一个量化过去决策对当前损失最大影响的指标，用于建模历史损失。基于此框架，可以证明一些政策遗憾的较好上界，并适用于各种在线学习任务。
在线凸优化中，相对Lipschitz和相对强凸性是如何定义的？相关算法有哪些？
研究考虑了在线凸优化问题的相对Lipschitz收敛性和相对强凸性，扩展了已知算法在相对设置下的遗憾界，特别是基于正则聚类领导者算法和在线镜像下降算法的算法，并将结果扩展到具有额外正则化的算法。
在线拟阵约束下的子模最大化问题如何与在线凸优化等价？
研究证明了一大类子模函数在在线凸优化问题中的优化等价性，通过合适的舍入方案，实现了在组合优化中达到次线性后悔的OCO算法。该规约也适用于动态后悔、游走和乐观学习等在线学习问题。
如何将约束在线凸优化问题转化为凸-凹优化问题？
通过将约束在线凸优化问题转化为在线凸-凹优化问题，提出了一种有效的算法，可以实现收敛性较好的结果，并为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
在对抗性时变约束下，在线凸优化算法能达到怎样的后悔和约束违反界？
针对对抗性时变约束，提出了一种算法，通过线性优化预言机（LOO）访问约束集，在长度为T的序列上，后悔为Õ(T^{3/4})，约束违反为O(T^{7/8})，且这些边界适用于任何区间。还提出了一种更高效的算法，仅需对软约束进行一阶预言机访问，并获得类似边界，并扩展到强化学习场景。
非平稳环境下具有任意延迟的在线凸优化问题，有什么算法可以降低动态遗憾？
提出了一个简单的算法DOGD，通过运用多个学习率的DOGD，并跟踪最佳one的延迟性能，将动态遗憾边界降至O(√(d*T*(P_T+1)))和O(√(S(1+P_T)))，并证明了这是最优的。
对于连续次模函数的在线优化，Frank-Wolfe变体算法能达到什么遗憾界？
提出了一种Frank-Wolfe算法的变体，可以访问目标函数的全梯度，并证明它对未来最佳可行解的(1-1/e)-近似具有O(√T)的遗憾界。对于只能获得梯度无偏估计的情况，还提出了在线随机梯度上升算法，也具有O(√T)的遗憾界，但只能达到1/2的近似度。结果还可推广到γ-弱次模函数。
在有限信息环境下，带有二次和线性切换成本的在线凸优化问题，竞争比如何？
提出了在线多梯度下降算法（OMGD），对于二次切换成本，竞争比至多为4(L+5)+(16(L+5))/μ。对于有界信息环境中的在线算法，竞争比的上界和下界分别为max{Ω(L), Ω(L/√μ)}。对于线性切换成本，OMGD的竞争比上界取决于路径长度、平方路径长度以及L、μ，并被证明是最佳竞争比。因此，二次和线性切换成本的最优竞争比基本上是不同的。
