Distance-Aware Muon: Adaptive Step Scaling for Normalized Optimization

Muon and related normalized optimizers determine a geometry-aware update direction but leave its magnitude to be tuned. Existing stochastic guarantees for star-convex Muon set this magnitude using the unknown distance to a minimizer. We formulate the missing scale as a one-dimensional online-learning problem and introduce Distance-Free Muon, which uses weighted follow-the-regularized-leader to learn the corresponding radius from past stochastic estimates of directional derivatives. For smooth star-convex objectives in general norm geometries, it achieves $\tilde{O}(T^{-1/3})$ expected last-iterate suboptimality, matching the known-distance method in its dependence on $T$. The method requires neither the distance to a minimizer nor the noise level and assumes neither a bounded domain nor a bounded trajectory. A complementary predictable stepsize rule gives an $O(T^{-1/4})$ bound on the expected gradient norm for general smooth non-convex objectives. Controlled matrix experiments quantify both the finite-horizon cost of learning the radius and its benefit when a fixed radius is transferred across distance scales. For practical additive variants beyond the analyzed updates, separate GPT-124M/WikiText-103 studies show that FTRL rules match tuned Muon, while a current-gradient stepsize-search proxy with a Nesterov-style momentum direction improves an otherwise identical fixed-scale baseline tuned on a disjoint seed.