Spectral Optimization on Manifolds: Geometry, Robustness, and Second-Order Methods

Abstract

Muon and related matrix optimizers choose updates by maximizing alignment with the gradient over a matrix-norm ball, a linear maximization oracle (LMO) in which the norm is a design choice. Many learning problems, however, involve low-rank, orthogonal, or positive-definite matrices, so the oracle must also respect tangent spaces and the symmetries of the parameterization.

In this talk we will present a unified framework for matrix LMOs on manifolds. Tangent directions are scaled before the norm constraint is imposed, and we will show that the right scaling is determined by the symmetries of the manifold rather than by a Riemannian metric. A second symmetry argument reduces the oracle to a problem over singular values, giving closed-form updates on fixed-rank, positive-definite, Stiefel, and Grassmann manifolds, with convergence guarantees that, on fixed-rank factorizations, depend on the rank rather than the scaling of the factors.

We will then consider a robust min-max oracle that maximizes worst-case alignment over norm-bounded gradient perturbations. Duality turns the adversary into a norm penalty, and for standard norm pairings the updates become thresholded polar factors, normalized singular-value soft thresholding, or normalized gradient steps with a global threshold, with guarantees for a relaxed stationarity criterion set by the uncertainty budget.

Finally, we will go beyond fixed steps: steepest descent with line search and trust regions can be formulated and analysed in the chosen norm without a Riemannian metric, with global guarantees and local superlinear convergence of trust regions. Experiments indicate that the norm matters most for first-order methods, while second-order models absorb much of the scaling.

Bio

Bamdev Mishra is a Principal Applied Scientist at Microsoft India, where he develops machine learning solutions for Microsoft 365 and other Microsoft products including Office products. His research interests include nonlinear and numerical optimization for machine learning, stochastic learning, and matrix and tensor methods. His applied work spans semantic search, cogs savings optimizations, personalized email understanding, and content generation. Before joining Microsoft, he was a Machine Learning Scientist at Amazon India, where he worked on pricing, recommendation systems, and seller-abuse detection.

An active contributor to the AI community, Bamdev serves as an Area Chair for NeurIPS, ICLR, ICML, and AAAI, and as an Action Editor for Transactions on Machine Learning Research (TMLR). He earned his B.Tech. and M.Tech. in Electrical Engineering from IIT Bombay in 2010, followed by a Ph.D. from the University of Liège in 2014.