Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
2026-07-20 • Machine Learning
Machine Learning
AI summaryⓘ
The authors investigate whether solving complicated nonconvex optimization problems can be simplified by using a known online convex optimization method as a black box. They create a system that tracks gradients and uses an online learner to pick how to adjust updates, allowing the method to achieve known convergence rates for smooth problems. They also extend this approach to less smooth, Lipschitz continuous problems without needing stronger guarantees, still obtaining good results. This work answers a previously open question and offers a new way to understand adaptive optimizers like AdaGrad and Shampoo through the lens of static regret.
nonconvex optimizationstochastic gradientsonline convex optimizationstatic regretgradient trackingpreconditioningAdaGradShampoo optimizerLipschitz continuityGoldstein stationary point
Authors
Haichen Hu, David Simchi-Levi
Abstract
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 such as AdaGrad and Shampoo may be understood through static regret and applied in nonconvex optimization.