提出自适应在线学习算法,实现光滑与非光滑优化的统一加速。
Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness
- 基于梯度变化设计自适应算法,无需事先知道光滑参数。
- 在线到批量转换后,实现霍尔德光滑下的最优随机优化。
- 首次构建通用离线方法,在光滑时加速,非光滑时仍接近最优。
光滑性在离线优化加速和在线学习中梯度变差后悔最小化中起关键作用。有趣的是,这两类问题本质关联——加速优化可从梯度变差在线学习视角理解。本文研究霍尔德光滑函数下的在线学习,该类函数涵盖光滑与非光滑(Lipschitz)情形,并探讨其对离线优化的影响。针对(强)凸在线函数,我们设计了相应的梯度变差在线学习算法,其后悔界在光滑与非光滑情形间平滑插值。值得注意的是,我们的算法无需预先知晓霍尔德光滑参数,展现出强自适应性。通过在线到批量转换,该自适应性带来霍尔德光滑下随机凸优化的最优通用方法。然而,离线强凸优化中的通用性更具挑战。我们通过结合在线自适应与基于检测的猜-检机制,首次实现通用离线方法:在光滑情形下达到加速收敛,非光滑情形下保持近最优收敛。
原文摘要 · Abstract (English)
Smoothness is known to be crucial for acceleration in offline optimization, and for gradient-variation regret minimization in online learning. Interestingly, these two problems are actually closely connected -- accelerated optimization can be understood through the lens of gradient-variation online learning. In this paper, we investigate online learning with Hölder smooth functions, a general class encompassing both smooth and non-smooth (Lipschitz) functions, and explore its implications for offline optimization. For (strongly) convex online functions, we design the corresponding gradient-variation online learning algorithm whose regret smoothly interpolates between the optimal guarantees in smooth and non-smooth regimes. Notably, our algorithms do not require prior knowledge of the Hölder smoothness parameter, exhibiting strong adaptivity over existing methods. Through online-to-batch conversion, this gradient-variation online adaptivity yields an optimal universal method for stochastic convex optimization under Hölder smoothness. However, achieving universality in offline strongly convex optimization is more challenging. We address this by integrating online adaptivity with a detection-based guess-and-check procedure, which, for the first time, yields a universal offline method that achieves accelerated convergence in the smooth regime while maintaining near-optimal convergence in the non-smooth one.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。