arXiv:2511.06597cs.LGmath.OC2025-11NeurIPS

提出新方法让优化算法更快收敛,且无需知道平滑性信息。

Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality

  • 用乐观在线转批量方法简化算法设计,理论证明有效
  • 在平滑与非平滑目标上均达最优加速收敛率
  • 仅需每轮一次梯度计算,适合实际应用

本文研究光滑目标下的离线凸优化问题。经典Nesterov加速梯度(NAG)方法可实现最优加速收敛。近年来,有研究从在线学习视角出发,通过在线转批量转换理解NAG,强调乐观在线算法对加速的作用。本文在此视角下提出新型乐观在线转批量转换,将乐观性理论融入分析,显著简化算法设计并保持最优收敛速率。具体而言:(i) 与简单在线梯度下降结合,实现最优加速收敛;(ii) 适用于强凸目标,首次通过在线转批量视角实现强凸光滑目标的最优加速率;(iii) 具备光滑性泛化能力——无需已知光滑性系数,即可适用于光滑与非光滑目标,且每轮仅需一次梯度查询,效率与非泛化方法相当。最后,我们通过精确对应关系揭示该转换与NAG的一致性。

原文摘要 · Abstract (English)

In this work, we study offline convex optimization with smooth objectives, where the classical Nesterov's Accelerated Gradient (NAG) method achieves the optimal accelerated convergence. Extensive research has aimed to understand NAG from various perspectives, and a recent line of work approaches this from the viewpoint of online learning and online-to-batch conversion, emphasizing the role of optimistic online algorithms for acceleration. In this work, we contribute to this perspective by proposing novel optimistic online-to-batch conversions that incorporate optimism theoretically into the analysis, thereby significantly simplifying the online algorithm design while preserving the optimal convergence rates. Specifically, we demonstrate the effectiveness of our conversions through the following results: (i) when combined with simple online gradient descent, our optimistic conversion achieves the optimal accelerated convergence; (ii) our conversion also applies to strongly convex objectives, and by leveraging both optimistic online-to-batch conversion and optimistic online algorithms, we achieve the optimal accelerated convergence rate for strongly convex and smooth objectives, for the first time through the lens of online-to-batch conversion; (iii) our optimistic conversion can achieve universality to smoothness -- applicable to both smooth and non-smooth objectives without requiring knowledge of the smoothness coefficient -- and remains efficient as non-universal methods by using only one gradient query in each iteration. Finally, we highlight the effectiveness of our optimistic online-to-batch conversions by a precise correspondence with NAG.

优化算法加速收敛在线学习泛化能力

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。