自适应反馈延迟未知的在线凸优化算法研究

本文针对反馈延迟未知的在线凸优化(OCO)问题，提出自适应延迟镜像下降(ADMD)算法，通过虚拟迭代序列和基于累积未反馈次数的学习率η=O(1/√MT)，实现了无需延迟先验知识的O(√MT)遗憾界，并创新性地引入延迟加倍技巧，在广告推荐和金融交易等场景展现优越性能。

　　

研究亮点

• 提出自适应延迟镜像下降(ADMD)算法，通过虚拟迭代序列和基于累积未反馈次数m_t的学习率η=O(1/√M_T)，突破传统算法需预知延迟的局限

• 首创延迟加倍技巧，通过动态调整学习率周期解决延迟环境下的时间窗同步难题

• 实验验证在点击率预测和股价波动场景中，ADMD较基线方法提升收敛速度达37%

方法创新

自适应延迟镜像下降(ADMD)

核心思想是构建虚拟决策序列{x?_k}，按实际反馈到达顺序更新：

x?_k+1 = argmin_x∈X{η_k〈?f_k(x?_k),x〉 + D_ψ(x,x?_k)}

其中学习率η_k=1/√∑^k_i=1m_i动态适应延迟情况，Bregman散度D_ψ保证强凸性。

延迟加倍技巧

设计自适应时间窗机制：

1. 初始化窗宽τ=2⁰

2. 当∑^t_s=t-τm_s > 2τ时触发窗宽倍增

3. 重置η_t←1/√∑^t_s=1m_s

   该机制使算法在延迟突变时保持稳定性。

实验验证

在合成数据集和真实金融数据测试中：

• 延迟波动场景下ADMD遗憾界较传统OMD降低19-26%

• 窗宽自适应调整耗时仅增加8%但避免37%的性能震荡

结论

本研究为延迟敏感型决策系统（如实时医疗诊断和自动化交易）提供了理论保障，未来可拓展至随机延迟和非凸场景。