用静态后悔率优化器实现黑箱非凸优化,突破收敛瓶颈。
Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles

- 构建梯度追踪器与预条件选择器的分离框架
- 在平滑非凸下达经典 $O(1/\\/sqrt{T})$ 收敛率
- 无需强后悔保证,适配自适应优化器设计
我们研究能否以黑箱方式将随机非凸优化转化为在线凸优化中的静态后悔最小化。针对光滑非凸目标,该方法维护一个可预测梯度追踪器,而黑箱在线学习器选择决定如何将追踪器转换为更新方向的预条件器。学习器接收线性凸损失,在单次无折现在线博弈中与固定比较器对比。对于 $β$-光滑、范围有界于 $M$、且梯度方差受 $σ^2$ 控制的随机梯度算子,我们建立:$$\frac{1}{T}\sum_{t=1}^T \mathbb E\left[\|\nabla f(x_t)\|_2^2\right] \lesssim \frac{σ\sqrt{Mβ}}{\sqrt T} + \frac{\sqrt{Mβ}\, \mathscr R_T(\mathcal A,I_d)}{T} + \frac{Mβ}{T}.$$ 因此,任何具有 $\mathscr R_T(\mathcal A,I_d)=O(\sqrt T)$ 静态后悔的黑箱 OCO 算法均能恢复经典 $O(1/\sqrt{T})$ 收敛率。进一步证明该框架可拓展至无梯度连续性的 Lipschitz 非凸目标,仍仅依赖静态后悔保证,无需更强在线后悔定义。当 OCO 口令具备平方根静态后悔时,所得转换达到对应 Goldstein 稳定点的最优 $O(T^{-2/7})$ 收敛率。本工作解决 Chen 与 Hazan (2024) 提出的开放问题。更广泛地,该框架将优化器设计解耦为梯度预测与在线预条件选择,为自适应优化方法提供基于静态后悔的原理性理解,并可应用于非凸优化。
原文摘要 · Abstract (English)
We study whether stochastic nonconvex optimization can be reduced to ordinary static regret minimization in online convex optimization in a black-box manner. For smooth nonconvex objectives, our reduction maintains a predictable gradient tracker, while a black-box online learner selects a preconditioner that determines how this tracker is transformed into the update direction. The learner receives linear convex losses and is evaluated against a single fixed comparator over one undiscounted online game. For a $β$-smooth objective with range bounded by $M$ and an unbiased stochastic-gradient oracle with variance bounded by \(σ^2\), we establish $$\frac{1}{T}\sum_{t=1}^T \mathbb E\!\left[\|\nabla f(x_t)\|_2^2\right] \lesssim \frac{σ\sqrt{Mβ}}{\sqrt T} + \frac{\sqrt{Mβ}\, \mathscr R_T(\mathcal A,I_d)}{T} + \frac{Mβ}{T}.$$ Consequently, any black-box OCO algorithm with $\mathscr R_T(\mathcal A,I_d)=O(\sqrt T)$ recovers the classical $O(\frac{1}{\sqrt{T}})$ convergence rate. We further show that the same black-box framework extends beyond the smooth setting to Lipschitz nonconvex objectives without Lipschitz continuous gradients. Importantly, this extension continues to rely only on an ordinary static-regret guarantee and requires no stronger notion of online regret. When the OCO oracle admits square-root static regret, the resulting conversion achieves the optimal $O(T^{-2/7})$ convergence rate for the corresponding Goldstein stationary point. These results resolve the open problem posed by Chen and Hazan (2024). More broadly, our framework separates optimizer design into gradient prediction and online preconditioner selection, providing a principled perspective on how adaptive optimization methods may be understood through static regret and applied in nonconvex optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。