带延迟反馈的通用在线凸优化

arXiv:2610.28058v1 公告类型：new 摘要：我们研究带延迟反馈的通用在线凸优化。我们提出一种单一算法，无需预先知道损失的曲率类别或参数，即可同时适应一般凸损失、强凸损失和指数凹损失。我们的遗憾界在时间跨度 $T$ 和延迟方面达到了已知的最佳依赖关系（仅相差双对数因子）：对于凸损失，遗憾大致为 $\sqrt{T + d_{\mathrm{tot}}}$；对于具有曲率的损失，遗憾率为 $\sigma_{\max}\log T$，其中 $d_{\mathrm{tot}}$ 是累计总延迟，$\sigma_{\max}$ 是同时缺失观测的最大数量。我们的主要技术贡献是一种带延迟的元学习器，它具有二阶超额损失保证，从而能够对带延迟的基础学习器进行自适应曲率聚合。此外，我们新的指数凹基础学习器给出了更紧的遗憾界：在保留互补的 $\sqrt{d_{\mathrm{tot}}}$ 依赖关系的同时，用可能小得多的 $\sigma_{\max}$ 替代最大延迟，从而改进了当前最先进方法对延迟的依赖关系。