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

arXiv: https://arxiv.org/abs/2607.17607 · HTML: https://mlsanity.com/paper/2607.17607/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 59 references that are in the map.
- First posted on arXiv 20 Jul 2026.

## Builds on (most cited first, 30 of 37)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projection](https://mlsanity.com/paper/2403.03507/) (2024)
- [Symbolic Discovery of Optimization Algorithms](https://mlsanity.com/paper/2302.06675/) (2023)
- [Muon is Scalable for LLM Training](https://mlsanity.com/paper/2502.16982/) (2025)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization](https://mlsanity.com/paper/1708.01012/) (2017)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Dynamical Models and Tracking Regret in Online Convex Programming](https://mlsanity.com/paper/1301.1254/) (2013)
- [A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions](https://mlsanity.com/paper/2112.06969/) (2021)
- [Memory-Efficient LLM Training with Online Subspace Descent](https://mlsanity.com/paper/2408.12857/) (2024)
- [On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functions](https://mlsanity.com/paper/2112.09002/) (2021)
- [Deterministic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2302.08300/) (2023)
- [Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise](https://mlsanity.com/paper/2402.01567/) (2024)
- [Adam with model exponential moving average is effective for nonconvex optimization](https://mlsanity.com/paper/2405.18199/) (2024)
- [Random Scaling and Momentum for Non-smooth Non-convex Optimization](https://mlsanity.com/paper/2405.09742/) (2024)
- [General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization](https://mlsanity.com/paper/2411.07061/) (2024)
- [Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2602.08232/) (2026)
- [Gradient Methods with Online Scaling](https://mlsanity.com/paper/2411.01803/) (2024)
- [Fast and Near-Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2008.01722/) (2020)
- [Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking](https://mlsanity.com/paper/2306.02527/) (2023)
- [Scalable Approximate Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2312.15594/) (2023)
- [Private Zeroth-Order Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2406.19579/) (2024)
- [Stochastic Nonconvex Optimization with Large Minibatches](https://mlsanity.com/paper/1709.08728/) (2017)

## Abstract (arXiv)

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.