Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
Abstract
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 𝒜 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(σ√(Mβ/T)+√(Mβ)RegT(𝒜)/T+Mβ/T), where RegT(𝒜) is the static regret of 𝒜 against the identity preconditioner. Thus, any OCO oracle with O(√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 σ√(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.
Related
- An Ω(T3/4) lower bound for projection-free online learning with linear minimization oracles
- A method for global minimization of nonconvex quadratic functions
- Variable Bregman Majorization-Minimization algorithms for nonconvex nonsmooth optimization, with application to Poisson imaging
- A restart-free accelerated algorithm for nonconvex minimization: continuous- and discrete-time analysis
- Regularized coordinate minimization for nonconvex composite optimization with application to quantized image compression
BibTeX
@misc{hu2026optimizing,
title = {{Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles}},
author = {Haichen Hu and David Simchi-Levi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.17607},
eprint = {2607.17607},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.17607},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
AU - Haichen Hu
AU - David Simchi-Levi
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2607.17607
UR - https://arxiv.org/abs/2607.17607
AB - 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 𝒜 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(σ√(Mβ/T)+√(Mβ)Reg_T(𝒜)/T+Mβ/T), where Reg_T(𝒜) is the static regret of 𝒜 against the identity preconditioner. Thus, any OCO oracle with O(√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 σ√(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.
ER -