arXiv:2510.03167math.OCcs.LG2025-10被引 3

提出新方法统一优化非凸问题,提升效率并简化算法。

Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism

  • 用外推梯度作提示,避免双重循环和对数因子
  • 确定性与随机情形下分别达 $O(\varepsilon^{-1.75})$ 与 $O(\varepsilon^{-3.5})$ 复杂度
  • 适合追求高效非凸优化的科研与工程人员

近期突破性工作将寻找 ε-一阶驻点问题转化为在线学习任务。当梯度与海森矩阵均满足利普希茨连续时,该框架结合两种在线学习器可实现确定性情形下 $O(\varepsilon^{-1.75}\log(1/\varepsilon))$ 和随机情形下 $O(\varepsilon^{-3.5})$ 的复杂度。但存在三方面局限:(i)确定性方法依赖复杂双循环结构求解固定点方程以构造提示向量,引入额外对数因子;(ii)随机方法假设随机梯度二阶矩有界,强于标准方差假设;(iii)两种情形使用不同学习算法。本文提出基于新型双重乐观提示函数的在线乐观梯度法。利用外推点梯度作为提示,基于两个乐观假设:提示与目标梯度差近似恒定,且由光滑性导致连续更新方向变化缓慢。所提方法无需双循环,消除对数因子。通过仅将全梯度替换为随机梯度,并在标准方差有界 $σ^2$ 假设下,获得统一算法,复杂度为 $O(\varepsilon^{-1.75} + σ^2 \varepsilon^{-3.5})$,平滑衔接最优确定性速率与最佳随机速率。

原文摘要 · Abstract (English)

A recent breakthrough in nonconvex optimization is the online-to-nonconvex conversion framework of [Cutkosky et al., 2023], which reformulates the task of finding an $\varepsilon$-first-order stationary point as an online learning problem. When both the gradient and the Hessian are Lipschitz continuous, instantiating this framework with two different online learners achieves a complexity of $O(\varepsilon^{-1.75}\log(1/\varepsilon))$ in the deterministic case and a complexity of $O(\varepsilon^{-3.5})$ in the stochastic case. However, this approach suffers from several limitations: (i) the deterministic method relies on a complex double-loop scheme that solves a fixed-point equation to construct hint vectors for an optimistic online learner, introducing an extra logarithmic factor; (ii) the stochastic method assumes a bounded second-order moment of the stochastic gradient, which is stronger than standard variance bounds; and (iii) different online learning algorithms are used in the two settings. In this paper, we address these issues by introducing an online optimistic gradient method based on a novel doubly optimistic hint function. Specifically, we use the gradient at an extrapolated point as the hint, motivated by two optimistic assumptions: that the difference between the hint and the target gradient remains near constant, and that consecutive update directions change slowly due to smoothness. Our method eliminates the need for a double loop and removes the logarithmic factor. Furthermore, by simply replacing full gradients with stochastic gradients and under the standard assumption that their variance is bounded by $σ^2$, we obtain a unified algorithm with complexity $O(\varepsilon^{-1.75} + σ^2 \varepsilon^{-3.5})$, smoothly interpolating between the best-known deterministic rate and the optimal stochastic rate.

非凸优化在线学习梯度法光滑优化

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