On the Upper Bounds for the Matrix Spectral Norm

Alexey Naumov; Maxim Rakhuba; Denis Ryapolov; Sergey Samsonov

math.NAJun 18, 2025

On the Upper Bounds for the Matrix Spectral Norm

Authors: Alexey Naumov, Maxim Rakhuba, Denis Ryapolov, Sergey Samsonov

Organizations: HSE University, Russia · Steklov Mathematical Institute of Russian Academy of Sciences, Russia

Abstract

We consider the problem of estimating the spectral norm of a matrix using only matrix-vector products. We propose a new Counterbalance estimator that provides upper bounds on the norm and derive probabilistic guarantees on its underestimation. Compared to standard approaches such as the power method, the proposed estimator produces significantly tighter upper bounds in both synthetic and real-world settings. Our method is especially effective for matrices with fast-decaying spectra, such as those arising in deep learning and inverse problems.

Figures & tables

$\delta$	$\theta_{\mathrm{cb}}$	$g(\theta_{\mathrm{cb}})$	maximizing $\rho$
$0.1$	$1.40$	$0.094291$	$1.2391$
$0.05$	$1.76$	$0.045134$	$1.1631$
$0.01$	$3.00$	$0.008700$	$1.0577$
$0.001$	$6.45$	$0.000861$	$1.0126$

Table 1: Numerical maximization of the matrix-agnostic coupled bound

g(\theta)

at the parameter values used in the experiments.

$\delta$	$\theta_{\mathrm{cb}}$	$\theta_{\mathrm{v}}$
0.1	1.4	1.72
0.05	1.76	2.17
0.01	3.00	3.70
0.001	6.45	7.98

Table 2: Values of parameter

\theta

for Counterbalance ( 7 ) and Vanilla ( 3 ) estimators at different

\delta

Panel of Figure 1 — Figure 1: Empirical density comparison for different methods

Panel of Figure 2 — Figure 2: Empirical density comparison with Lanczos-type estimator.

Panel of Figure 3 — Figure 3: Finite-budget comparison of different estimators as the number of matrix-vector products increases. Solid lines show the mean estimates; shaded areas indicate empirical variance.

$\delta_{\textbf{real}}$	Hilbert	Rank 2	Dominant 0.1	Roget’s Thesaurus	Dominant 0.5
Counterbalance	0.034	0.031	0.045	0.0001	0.0001
Vanilla	0.011	0.019	0.016	0.013	0.0
Dixon	0.019	0.029	0.031	0.022	0.0
Lanczos-type	0.027	0.030	0.034	0.044	0.04

Table 3: Values of underestimation probability

\delta_{real}=\mathbb{P}\!\left(T(\theta,X)\leq\left\lVert A\right\rVert_{2}\right)

measured for different test statistics with 3 matvecs and

\delta=0.05

MAE	Hilbert	Rank 2	Dominant 0.1	Roget’s Thesaurus	Dominant 0.5	Fréchet derivative	ResNet Jacobian
Counterbalance	1.01	1.06	0.97	1.28	1.99	8.65	25.82
Vanilla	2.04	1.98	1.97	3.35	3.77	13.46	36.78
Dixon	1.65	1.60	1.6	2.97	3.26	13.44	38.60
Lanczos-type	1.44	1.25	1.31	2.32	1.78	6.95	19.73

Table 4: MAE for different test statistics

\delta=0.05

Panel of Figure 4 — Figure 4: Counterbalance and randomized power method comparison

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: Singular values for matrices from Section 6 .

Panel of Figure 6 — Figure 6: Results for Dominant 0.1 matrix.

Spectral Methods

Spectral methods use eigenvalues, eigenvectors, and frequency decompositions to analyze data, graphs, operators, and learning algorithms.

See all 236 papers

Cost-free Spectral Estimation for Adaptive Newton--Schulz in Matrix Optimizers
Sep 27, 2026Kristi Topollai, Anna ChoromanskaMatrix Optimization Newton-Schulz Iteration
New York University
A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation
Sep 6, 2026Huan QingSpectral Methods
School of Economics and Finance, Chongqing University of Technology, Chongqing, 400054, China
Uniform Sampling from High-dimensional Spectral Norm Balls
Jun 23, 2026Michael R. MetelRandom Matrix Theory

Sep 27, 2026J/K move · Enter open · S save

Cost-free Spectral Estimation for Adaptive Newton--Schulz in Matrix Optimizers

Kristi Topollai, Anna Choromanska

New York University

Matrix Optimization Newton-Schulz Iteration Muon Optimizer Spectral Methods

Open paper AskPDF arXiv

Matrix optimizers such as Muon transform each momentum matrix through an approximate orthogonalization, typically implemented by a small number of Newton-Schulz matrix multiplications. The quality and cost of this approximation depend strongly on the singular-value spectrum of its input, yet existing implementations use the same fixed polynomial routine for every layer and throughout training. We show that this uniform treatment is unnecessary: the computations in the Newton-Schulz method already reveal enough information to make the method adaptive. The Gram matrices formed inside Newton-Schulz iterations yield spectral moments through inexpensive scalar reductions, requiring no additional matrix multiplications. From these moments, we recover an estimate of the empirical singular-value distribution and use it to select a polynomial routine specialized to the current matrix. This turns Newton--Schulz orthogonalization into a spectrum-adaptive procedure that responds to differences across both layers and training time. On saved momentum matrices, spectral estimation substantially reduces orthogonalization error at a fixed iteration budget or reaches the same accuracy with fewer iterations, and in GPT pretraining up to 1B parameters it lowers the validation loss of two matrix optimizers. Our results suggest that matrix-function operations inside optimizers need not be designed for a conservative worst-case spectrum: they can cheaply measure the spectrum they are already processing and specialize computations accordingly.

Abstract

Spectral Methods

Explore similar work

Cost-free Spectral Estimation for Adaptive Newton--Schulz in Matrix Optimizers

A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation

Uniform Sampling from High-dimensional Spectral Norm Balls