When dealing with massive datasets, computing the exact inverse of a large matrix—such as a $d \times d$ Hessian matrix in second-order optimization—becomes a massive computational bottleneck, costing $O(d^3)$ time. To bypass this, modern machine learning relies heavily on randomized sketching and distributed estimation. Instead of working with the full matrix, we compute smaller, random sketches or distribute sub-sampled chunks of the matrix across parallel workers.
While these randomized approximations work exceptionally well for linear operations, they hit a fundamental mathematical snag when matrix inversion is involved. This snag is known as inversion bias.
The Non-Linearity Trap
To understand why inversion bias occurs, consider a simple scalar analogy. Suppose we want to estimate $1/x$ for some true value $x = 2$. We use an unbiased random estimator $\hat{x}$ that equals $1$ half the time and $3$ the other half. On average, our estimator is perfectly accurate:
$$\mathbb{E}[\hat{x}] = \frac{1 + 3}{2} = 2$$
However, if we invert this estimator to find $1/\hat{x}$, we get $1/1 = 1$ half the time, and $1/3$ the other half. The expected value of our inverted estimator is:
$$\mathbb{E}\left[\frac{1}{\hat{x}}\right] = \frac{1 + 1/3}{2} = \frac{2}{3} \approx 0.667$$
But the true value we wanted was $1/2 = 0.5$. Because the inversion function $f(k) = 1/k$ is convex, Jensen's inequality guarantees that the expected value of the inverse will systematically deviate from the inverse of the expected value.
In randomized linear algebra, this exact phenomenon occurs at a higher dimension. Even if a random sketch $X$ is an unbiased estimator of a matrix $A$ (meaning $\mathbb{E}[X] = A$), its inverse $X^{-1}$ is systematically biased:
$$\mathbb{E}[X^{-1}] \neq (\mathbb{E}[X])^{-1}$$
As identified by Derezinski et al. (2021), this systematic discrepancy distorts the eigenvalues of the resulting matrix, creating a severe bottleneck in large-scale optimization and statistical estimation.
Why Simple Averaging Fails
In distributed systems, a standard strategy to eliminate noise is parallel averaging. If you have $K$ independent workers computing noisy estimates, averaging their results typically reduces the variance by a factor of $1/\sqrt{K}$, converging cleanly to the true value.
However, averaging only reduces variance; it does nothing to eliminate bias.
If $K$ distributed workers compute independent sketches of a Hessian matrix and invert them locally, simply taking the arithmetic mean of those inverses will not yield the true global inverse Newton step Derezinski et al., 2019. Instead, the parallel workers will collectively converge to an inaccurate, biased matrix.
As noted by Zhang et al. (2023), this inversion bias acts as an inescapable noise floor. No matter how many parallel machines are added to the cluster, the optimization algorithm hits a performance wall and fails to achieve high precision Romanov et al., 2025. The systematic error introduced by row-sampling or sketching permanently misaligns the descent direction Niu et al., 2025.
Standard Estimation:
[Unbiased Sketches] ───> [Average] ───> [True Solution] (Variance drops to 0)
Sketched Inversion:
[Biased Inverses] ───> [Average] ───> [Biased Solution] (Stuck at Noise Floor)
Correcting the Bias with Random Matrix Theory
If the bias is an inherent mathematical property of inversion, how can we get rid of it? The core insight of modern Randomized Numerical Linear Algebra (RandNLA) is that while the bias is systematic, it is also highly predictable if we understand the spectral geometry of random matrices Derezinski et al., 2024.
Spectral Shrinkage
One elegant solution is to apply a theoretically derived scalar adjustment to the sketched matrices before or during inversion. Zhang et al. (2023) demonstrated that by calculating an optimal shrinkage factor based on the dimensions and properties of the sketch, one can rescale the eigenvalues of the sketched matrix. This simple scalar shift counteracts the inflation caused by the non-linear inversion step, effectively dropping the noise floor to zero without adding any computational overhead.
Marchenko-Pastur Debiasing
When using random Gaussian matrices to sketch a Hessian down to a lower dimension, the distribution of the sketch's eigenvalues follows predictable statistical laws. Romanov et al. (2025) utilized the Marchenko-Pastur law—a cornerstone of Random Matrix Theory—to derive an exact debiasing term. By applying this correction factor directly to the regularization parameter of the local sub-sampled Hessians, the systematic error is neutralized. This allows distributed workers to produce coarse local estimates that, when averaged, successfully converge to the true, high-precision Newton direction.
Bias-Aware Sketching and Averaging
Rather than correcting the bias after the fact, alternative strategies alter the sketching or averaging mechanisms themselves to be inherently "bias-aware."
Determinantal Averaging
Instead of a standard arithmetic mean, Derezinski et al. (2019) introduced a non-uniform weighting scheme known as determinantal averaging. By weighting each local inverse Hessian proportional to its determinant, the algebraic distortions of inversion are perfectly counterbalanced. This approach yields the first asymptotically consistent distributed Newton step, ensuring that accuracy scales dynamically with the number of machines.
LESS Embeddings
Another angle is to design the random projection matrix itself to minimize the introduction of bias from the start. Derezinski et al. (2021) developed LESS (LEverage Score Sparsified) embeddings. By utilizing sparse random matrices combined with leverage-score sampling, LESS embeddings achieve near-optimal inversion bias. This provides a computationally lightweight alternative to dense random projections while preserving the ability to safely average multiple independent sketches.
Ultimately, recognizing and mitigating inversion bias bridges the gap between fast, randomized approximations and the high-precision requirements of advanced optimization, proving vital in fields ranging from distributed second-order optimization to large-scale network clustering Su et al., 2025.
Key Foundational Work
Sparse sketches with small inversion bias (2021) — contributed 4 concept elements to this direction.
Distributed estimation of the inverse Hessian by determinantal averaging (2019) — contributed 1 concept elements to this direction.