Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
Haichen Hu, David Simchi-Levi
Stochastic nonconvex optimization is central to training deep networks and LLMs in modern machine learning. We give a black-box reduction from stochastic nonconvex optimization to ordinary static regret minimization in online convex optimization (OCO), addressing the open problem posed by Chen and Hazan (2024). Our reduction maintains a predictable gradient tracker, while a black-box online learner $\mathcal A$ selects a preconditioner that transforms this tracker into the update direction. Given a $β$-smooth function with initial gap at most $M$ and an unbiased gradient oracle with variance bounded by $σ^2$, we bound the expected average squared gradient norm by $O(σ\sqrt{Mβ/T}+\sqrt{Mβ}\mathrm{Reg}_T(\mathcal A)/T+\frac{Mβ}{T})$, where $\mathrm{Reg}_T(\mathcal A)$ is the static regret of $\mathcal A$ against the identity preconditioner. Thus, any OCO oracle with $O(\sqrt T)$ regret recovers the classical $O(T^{-1/2})$ convergence rate. We also prove that the additive variance term cannot be removed: every conversion making a constant number of stochastic-oracle queries per round, whose guarantee is stated through static regret against a comparator that the online learner can play, must contain an additive term of order $σ\sqrt{Mβ/T}$ for sufficiently large $T$. Moreover, for every online learner, our conversion bound is tight up to universal constants. We also extend the framework to nonsmooth nonconvex optimization, still relying only on ordinary static regret, and attain the optimal convergence rate for Goldstein-type stationarity. Finally, we conduct numerical experiments on nonconvex objectives to illustrate how the reduction exploits online-selected preconditioners while using the same stochastic-oracle budget as stochastic gradient descent.
尚无 AI 解读，展示原文摘要