Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles

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), thereby resolving the open problem posed by Chen and Hazan (2024). Our reduction maintains a predictable gradient tracker, while a black-box online learner A selects a preconditioner that transforms this tracker into the update direction. Given a (β)-smooth function with a range bounded by M and an unbiased gradient oracle with variance bounded by σ2, we bound the expected average squared gradient norm by O(σ√Mβ/T+√MβRegT(A)/T+fracMβT), where RegT(A) is the static regret of A. Thus, any OCO oracle with O(√T) regret recovers the classical O(T-1/2) convergence rate. We further extend the framework to nonsmooth nonconvex objectives, 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.