Stochastic Rounding Implicitly Regularizes Tall-and-Thin Matrices

Gregory Dexter, Christos Boutsikas, Linkai Ma, Ilse C. F. Ipsen, Petros Drineas

TL;DR

Stochastic rounding (SR) acts as an implicit regularizer for tall-and-thin matrices, guaranteeing with high probability that the rounded matrix maintains full column rank. This regularization effect ensures the smallest singular value is bounded away from zero, even if the original matrix was completely rank-deficient, explaining why SR prevents numerical stagnation in low-precision machine learning workflows.

What Problem Does This Paper Address?

As machine learning models scale, researchers and hardware designers increasingly turn to low-precision arithmetic (like FP16 or INT8) to save compute and memory. However, standard deterministic rounding (like round-to-nearest) can introduce systematic errors, drive small singular values to zero, and cause matrices to become rank-deficient. This leads to numerical instability and optimization stagnation during deep neural network training.

While Stochastic Rounding (SR)—rounding probabilistically based on proximity to the nearest grid points—has empirically fixed these issues, a rigorous mathematical understanding of why it preserves matrix health was lacking. This paper addresses this gap by analyzing how SR impacts the smallest singular value ($\sigma_d$) of "tall-and-thin" matrices (matrices with significantly more rows than columns, $n \gg d$), which are ubiquitous in data analysis, regression, and neural network layers.

Methods

The authors employ Random Matrix Theory (RMT) to mathematically analyze the behavior of stochastically rounded matrices.

  1. Error Decomposition: They break the rounding error matrix ($\mathbf{E} = \tilde{\mathbf{A}} - \mathbf{A}$) into two components using an orthogonal projector onto the column space of the original matrix $\mathbf{A}$.
  2. RMT Bounding: They apply advanced RMT bounds (specifically adapting recent work by Dumitriu and Zhu on inhomogeneous random rectangular matrices) to show that the rounding errors do not concentrate in low-dimensional subspaces.
  3. Concentration Inequalities: They use Hoeffding's inequality to bound the deviation of the random variables and establish a lower bound for the smallest singular value of the rounded matrix $\tilde{\mathbf{A}}$.
  4. Simulation: To validate their theory, they emulate low-precision fixed-point and floating-point arithmetic using the chop software library, testing how closely empirical matrix behavior matches their theoretical bounds.

Datasets

The paper does not use real-world empirical datasets. Instead, it evaluates its theoretical claims using synthetic matrices designed to isolate specific numerical properties:

  • Matrices of size $n \times d$ where $n = 10^4$ and $d \in \{10, 100, 1000\}$.
  • Matrix entries are drawn from two distinct distributions: a standard normal distribution $\mathcal{N}(0,1)$ and a highly skewed Lognormal$(0,3)$ distribution.
  • The matrices are manually adjusted to be rank-deficient ($\sigma_d(\mathbf{A}) = 0$) or near rank-deficient ($\sigma_d(\mathbf{A}) = 10^{-2}$) to test the regularization effect under extreme conditions.

Key Insights and Ideas

  • Implicit Regularization: SR injects a structured, unbiased random perturbation that inherently prevents columns from becoming linearly dependent. It acts exactly like explicit regularization (e.g., Ridge regression), but happens automatically during the rounding step.
  • Independence from Original Rank: Remarkably, the lower bound for the smallest singular value of the rounded matrix $\tilde{\mathbf{A}}$ does not depend on the smallest singular value of the original matrix $\mathbf{A}$. Even if $\mathbf{A}$ is completely rank-deficient, $\tilde{\mathbf{A}}$ will have full column rank with high probability.
  • The Power of "Tallness": As the row dimension $n$ grows, the smallest singular value of the stochastically rounded matrix actually increases. Longer columns provide more geometric "space" and opportunities for the stochastic perturbations to establish linear independence.
  • The Variance Factor ($\nu$): The regularization effect is directly tied to the minimum normalized column-wise variance ($\nu$) of the rounding process. If an entry lands exactly on a floating-point representable number, $\nu=0$ and no regularization occurs. SR is most powerful when entries fall between grid points, maximizing rounding stochasticity.

Key Results

  • The Theoretical Bound: For a sufficiently tall-and-thin matrix, the authors prove that the smallest singular value scales as: $$\sigma_d(\tilde{\mathbf{A}}) \gtrsim \beta^{1-p}\sqrt{n\nu}$$ where $\beta$ is the arithmetic base, $p$ is the precision, $n$ is the row count, and $\nu$ is the rounding variance.

  • Empirical Validation: In experiments across 100 randomized runs, the strict theoretical bound was sometimes violated for "squarish" matrices ($d=1000$). However, introducing a very mild relaxation constant ($c \approx 0.8$ or $0.9$) resulted in zero violations across all tested distributions and dimensions.

  • Predictive Accuracy: The relative error between the paper's simplified estimate and the minimum observed singular value in simulations remained consistently below 6%, proving that the theory tightly mirrors practical behavior.

Limitations and Future Work

  • Pessimistic Lower-Order Terms: The strict mathematical bound includes a lower-order error term ($\epsilon_{n,d}$) derived from state-of-the-art RMT. Theoretically, this term requires an impractically large $n$ (e.g., $n > 10^{50}$) to completely vanish, even though experiments show it is not a concern in practice.
  • Assumption Relaxation: The authors note that their bound for general stochastic rounding is less sharp than the bound they proved for pure Gaussian perturbations (Theorem 7). Future work will focus on leveraging newer RMT techniques to bridge this gap and eliminate the pessimistic lower-order terms entirely.

Summary updated

Abstract

Motivated by the popularity of stochastic rounding in the context of machine learning and the training of large-scale deep neural network models, we consider stochastic nearness rounding of real matrices $\mathbf{A}$ with many more rows than columns. We provide novel theoretical evidence, supported by extensive experimental evaluation that, with high probability, the smallest singular value of a stochastically rounded matrix is well bounded away from zero -- regardless of how close $\mathbf{A}$ is to being rank deficient and even if $\mathbf{A}$ is rank-deficient. In other words, stochastic rounding \textit{implicitly regularizes} tall and skinny matrices $\mathbf{A}$ so that the rounded version has full column rank. Our proofs leverage powerful results in random matrix theory, and the idea that stochastic rounding errors do not concentrate in low-dimensional column spaces.
BibTeX
@article{dexter2025stochastic,
  author = {Gregory Dexter and Christos Boutsikas and Linkai Ma and Ilse C. F. Ipsen and Petros Drineas},
  title = {{Stochastic Rounding Implicitly Regularizes Tall-and-Thin Matrices}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2025},
  doi = {10.1137/24m1647679},
}
Figure