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

What the math gives to ML

The paper provides a black-box way to turn any static-regret online convex optimizer into a nonconvex optimizer that learns its preconditioner online, rather than fixing Adam-like coordinate scaling by hand. The transferable asset is the separation between a predictable gradient tracker and a regret-minimizing preconditioner: the tracker predicts the direction, while an OCO learner chooses how strongly each coordinate or subspace is applied. The signed comparator-regret term is especially useful because the learned preconditioner can provably outperform the identity update when its regret against the identity comparator is negative. A practical first transfer is a diagonal projected-OGD preconditioner driven by linear losses measuring alignment between the stochastic gradient and the predicted gradient.