Search papers, labs, and topics across Lattice.
This paper explores the reduction of stochastic nonconvex optimization to static regret minimization in online convex optimization using a black-box approach. By employing a predictable gradient tracker and a preconditioner selected by a black-box learner, the authors establish convergence rates for smooth and Lipschitz nonconvex objectives, achieving optimal rates under certain conditions. Their findings not only resolve a prior open problem but also provide a new framework for understanding adaptive optimization methods through the lens of static regret.
Achieving optimal convergence rates for nonconvex optimization by transforming it into a static regret minimization problem could revolutionize how we design adaptive optimizers.
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.
MIT CSAIL