A Second-Order Complexity Theory for Spectral Optimization

Neural-network training combines approximate gradients with approximate update computations. Recent advances in spectral optimization, including Muon for large-scale training, make the balance between computational cost and update accuracy especially important. How much gradient information and arithmetic accuracy suffice to preserve optimization progress? We address this question using second-order complexity theory, which accounts for the requested accuracy and the cost of reading and processing gradient approximations. We measure spectral update quality by the shortfall in linearized descent relative to the best direction under the same spectral-norm constraint. This criterion weights weak gradient components by their small contribution to descent, even when their normalized directions are sensitive to error. We establish the exact minimax tradeoff between update sensitivity, uncertainty, and descent, attained by spectral clipping calibrated to a gradient-error bound and a supplied rank bound. On a normalized gradient class, we determine the input precision required for a target descent tolerance to within one bit. A certified matrix-multiplication algorithm achieves the guarantee in second-order polynomial bit time, uniformly across rank changes. For smooth nonconvex objectives, these local guarantees yield stationarity bounds that separate gradient uncertainty from implementation error and have optimal uncertainty dependence. These results quantify, in precise mathematical terms, how accurately gradients and updates need to be computed to preserve optimization progress, providing a complexity-theoretic framework for understanding when spectral optimization methods remain computationally feasible at high precision.