Stochastic Rounding Increases Small Singular Values

Technical Summary: Stochastic Rounding Increases Small Singular Values

Problem Statement
Recent research has established that Stochastic Rounding (SR) acts as an implicit regularizer by increasing the smallest singular value of matrices, particularly those with extreme aspect ratios (very tall-and-thin or short-and-fat). However, the current theoretical understanding of this phenomenon is limited in two critical ways:

1. Aspect Ratio Constraints: Existing bounds largely apply only to matrices where the number of rows and columns differ significantly (e.g., $d \ll n^{1/4}$). They fail to address matrices with constant aspect ratios, which are ubiquitous in modern machine learning (e.g., self-attention weights, fully connected layers).
2. Spectral Scope: Prior analyses focus almost exclusively on the smallest singular value ($\sigma_{\min}$). They do not account for the "spectral tail"—clusters of small singular values that encode fine-grained information and influence generalization in deep learning.

The paper seeks to determine if SR's regularization effect persists for matrices with constant aspect ratios and whether it extends beyond the single smallest singular value to lift entire clusters of singular values at the tail of the spectrum.

Methodology
The authors analyze a matrix $\tilde{A} \in \mathbb{R}^{n \times d}$ obtained by applying a Uniformly Dithered Quantizer entrywise to a matrix $A$. This process is modeled as $\tilde{A} = A + E$, where $E$ is a noise matrix with independent, centered, bounded, and sub-Gaussian entries.

The analysis proceeds in two main directions:

1. Smallest Singular Value ($\sigma_d(\tilde{A})$):
   The authors utilize the inequality $\sigma_d(\tilde{A}) \geq \sigma_d(E) - \|P_A E\|_2$, where $P_A$ is the orthogonal projector onto the column space of $A$.

   • They employ a sharp lower bound for $\sigma_d(E)$ derived from Brailovskaya and van Handel [2024], which accounts for non-homogeneous noise variances.
   • They derive a new, tighter upper bound for the projection term $\|P_A E\|_2$ using $\epsilon$-net arguments and Hoeffding's inequality.
   • By combining these via a union bound, they establish a high-probability lower bound for $\sigma_d(\tilde{A})$ that holds under constant aspect ratio constraints ($d \leq c_0 n$).

2. Spectral Tail Regularization:
   To analyze clusters of singular values, the authors assume $A$ has a large spectral gap at index $k$ ($\sigma_k(A) \gg \sigma_{k+1}(A)$). They define the "expected excess tail energy" $T$ as the difference in the sum of squared singular values from index $k+1$ to $d$ between $\tilde{A}$ and $A$.

   • Contour Integration: They utilize the resolvent representation of spectral projectors. By defining a contour $\Gamma$ that encloses the top $k$ eigenvalues of the Gram matrix $G = A^\top A$ but excludes the rest, they express the energy shift as a series of contour integrals.
   • Neumann Expansion: The perturbed resolvent is expanded into a Neumann series. The leading terms ($I_1, I_2$) are computed exactly using residue calculus, while higher-order terms are bounded using concentration inequalities and operator norm bounds on the perturbation $\Delta = \tilde{G} - G$.
   • Energy Identity: They leverage the identity that the expected total squared singular value mass increases by the expected squared Frobenius norm of the noise, allowing them to relate the tail energy shift to the top-$k$ energy shift.

Key Contributions and Results

1. Generalization to Constant Aspect Ratios:
   The paper proves that the regularization effect of SR is not restricted to extreme dimensional imbalances.

   • Result: For a matrix $A$ with $d \leq c_0 n$, the smallest singular value of the rounded matrix $\tilde{A}$ satisfies $\sigma_d(\tilde{A}) \gtrsim \rho \sqrt{n} \nu$ with high probability, where $\rho$ is the quantization resolution and $\nu$ measures the column-wise variance of the noise.
   • Comparison: This significantly improves upon previous work (e.g., Dexter et al. [2025]), which required $d = o((n/\log n)^{1/4})$. The new bound covers matrices where $d$ and $n$ are of the same order, making the result applicable to standard deep learning weight matrices.

2. Regularization of Singular Value Clusters:
   The paper demonstrates that SR lifts not just the minimum singular value, but a non-trivial portion of the spectral tail.

   • Result: The expected excess tail energy $T$ is lower-bounded by the sum of the smallest $(d-k)$ column variances of the noise matrix, minus lower-order terms dependent on the spectral gap and perturbation magnitude.
   • Implication: This indicates that SR injects noise that diffuses across directions, preventing concentration in low-dimensional subspaces. Consequently, it strengthens weak spectral modes across a cluster, rather than acting as a one-dimensional regularizer.

Significance and Claims
The authors claim that these results provide a more general and accurate characterization of stochastic rounding as a spectral regularizer.

• Theoretical Foundation: The work offers a rigorous theoretical basis for the empirical success of SR in low-precision training, suggesting that the "harmful" quantization noise is actually structured in a way that improves spectral geometry.
• Mechanism of Implicit Regularization: By showing that SR affects the spectral tail, the paper connects SR to the phenomenon of implicit self-regularization observed in deep learning, where heavy-tailed spectra correlate with generalization capacity.
• Limitations: The authors modestly acknowledge that their bounds for the spectral tail rely on restrictive assumptions, including a strong spectral gap, bounded eigenvalue ratios, and small perturbation levels. They note that the near-square regime ($d \approx n$) for the smallest singular value bound is not fully covered by their current analysis, and further empirical validation in downstream deep learning tasks is needed.

In summary, the paper establishes that stochastic rounding acts as a general-purpose spectral regularizer that operates on matrices with constant aspect ratios and lifts entire clusters of small singular values, thereby reshaping the low-energy subspace of the matrix spectrum.