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

This paper addresses a fundamental open problem in optimization: can we reduce offline stochastic nonconvex optimization to a black-box online convex optimization (OCO) problem using only standard static regret? While previous methods have successfully used online learning for nonconvex optimization, they often relied on stronger, non-standard notions of regret—such as dynamic, shifting, or discounted regret—or were tailored to specific optimizer architectures. This paper seeks to determine if the weakest standard form of regret (static regret) is sufficient to achieve optimal convergence in nonconvex settings.

The authors introduce a novel reduction framework that separates the optimization process into two distinct roles. Instead of using the OCO oracle to directly determine the update direction, the algorithm maintains a predictable gradient tracker—an exponential moving average of historical stochastic gradients. The OCO oracle is then tasked with selecting a preconditioning matrix that transforms this tracker into an effective update direction. By defining a linear loss function that measures how well a chosen preconditioner aligns the tracker with fresh stochastic gradient samples, the authors enable the OCO algorithm to operate as a genuine black box. This approach allows the algorithm to adapt the geometry of the descent direction while relying solely on the static regret guarantee of the underlying OCO oracle.

The authors prove that this black-box reduction recovers the classical $O(1/\sqrt{T})$ convergence rate for $\beta$-smooth nonconvex objectives, provided the OCO oracle achieves $O(\sqrt{T})$ static regret. Furthermore, they extend this framework to Lipschitz nonconvex objectives without requiring Lipschitz continuous gradients. In this setting, when the OCO oracle admits square-root static regret, the conversion achieves the optimal $O(T^{-2/7})$ convergence rate for Goldstein stationary points. These results resolve the open problem posed by Chen and Hazan (2024) and provide a unified theoretical perspective on how adaptive methods like AdaGrad and Shampoo can be understood through the lens of static regret.