具有未知延迟的在线顺序决策
内容提要
该文综述延迟反馈下的在线凸优化研究，涵盖非平稳环境任意延迟、对抗性延迟、多臂赌博延迟、异步分布式优化、长期约束、多步切换成本及差分隐私等场景，提出DOGD、DEXP3、DBGD、RCL等算法，并给出动态遗憾与竞争比的理论保证。
延伸解读
延迟反馈下的算法设计思路
文章综述了多种应对延迟反馈的在线凸优化算法，如DOGD、DEXP3、DBGD和RCL。这些算法分别针对非平稳环境、多臂赌博、异步分布式优化以及多步切换成本等场景。其核心思路包括使用多学习率跟踪最佳延迟性能、通过黑盒元算法改进UCB、以及结合机器学习预测与专家算法增强鲁棒性。这些设计为不同延迟环境提供了理论保证，如动态遗憾边界和竞争比。
理论保证与性能边界
文章给出了多个算法在延迟环境下的理论保证。例如，DOGD在非平稳环境下达到O(√(d*T*(P_T+1)))的动态遗憾，并证明其最优性；对抗性延迟下无投影算法实现O(√B)的后悔界；对于带切换成本的OCO，OMGD算法在二次切换成本下竞争比至多4(L+5)+(16(L+5))/μ，并证明线性切换成本的最优竞争比与二次情形本质不同。这些边界为算法性能提供了严格的理论依据。
应用场景与实际问题
文章不仅关注理论，还涉及实际应用。例如，异步分布式优化中的鲁棒约束训练方法适用于云和数据中心等共享资源环境，能适应动态延迟变化；长期对抗性约束下的元策略可应用于在线多任务学习和网络控制；RCL算法以电动交通的电池管理为案例，展示了在鲁棒性和平均性能上的改进。这些例子说明了延迟反馈在线学习在现实系统中的重要性。
隐私与约束的扩展
文章还探讨了差分隐私和长期约束等扩展问题。在(ε,δ)-差分隐私OCO中，通过强对数凹密度抽样改进了维度因子并消除平滑性要求，达到了已知最佳速率。对于长期对抗性约束，元策略能同时实现亚线性累积约束违规和亚线性遗憾，并通过李雅普诺夫技术揭示了遗憾与顺序不等式之间的联系。这些扩展丰富了在线凸优化的理论框架。
Q&A
在非平稳环境下，具有任意延迟的在线凸优化问题，DOGD算法能达到怎样的动态遗憾界？
DOGD算法通过运用多个学习率并跟踪最佳学习率的延迟性能，将动态遗憾边界降至O(√(d*T*(P_T+1)))和O(√(S(1+P_T)))，并证明这是最优的。
针对对抗性延迟反馈的在线凸优化，有哪些无投影算法？它们的后悔界如何？
提出了两种无投影算法，分别用于集中式和分布式环境，实现了延迟环境中OCO问题的O(√B)后悔界。
多臂赌博和赌博凸优化中处理未知延迟反馈的算法是什么？
开发了延迟探索、利用和指数迭代（DEXP3）和延迟赌博梯度下降（DBGD）算法，通过统一分析框架证明了其性能优越。
在异步分布式优化中，如何解决更新延迟问题？
提出了一种鲁棒的约束训练方法，其非渐近收敛保证不依赖于更新延迟、目标平滑度和梯度方差的先验知识，能隐式适应动态分配机器带来的延迟变化。
在线凸优化中带有长期对抗性约束的问题，如何同时达到亚线性遗憾和约束违规？
提出一种元策略，通过将约束问题转化为递归构建的代理代价函数的标准OCO问题，使用自适应OCO策略求解，可同时达到亚线性的累积约束违规和亚线性的遗憾。
具有多步非线性切换成本和反馈延迟的平滑在线凸优化，RCL算法有什么特点？
RCL（Robustness-Constrained Learning）通过受限投影将不受信任的ML预测与可信的专家在线算法结合，对于任何给定的专家保证（1+λ）竞争力，是第一个在多步切换成本和反馈延迟下具有可证明鲁棒性保证的ML增强算法。
差分隐私在线凸优化中，如何改进(ε, δ)-差分隐私的速率？
通过引入强对数凹密度的抽样，提升维度因子并消除平滑性要求，改进了(ε)非常小的情况下Agarwal等人的结果，达到了该领域已知的最佳速率。
