Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton

1. Problem Statement

Randomized Numerical Linear Algebra (RandNLA) utilizes random sketching (projection or sampling) to accelerate large-scale machine learning tasks. A common approach involves constructing a sketch $\tilde{A} = SA$ of a tall matrix $A \in \mathbb{R}^{n \times d}$ ($n \gg d$) to approximate the inverse of the Gram matrix, $(A^\top A + C)^{-1}$, where $C$ is a positive semi-definite regularizer.

While the sketch $\tilde{A}^\top \tilde{A}$ is often an unbiased estimator of $A^\top A$ (i.e., $\mathbb{E}[\tilde{A}^\top \tilde{A}] = A^\top A$), the non-linearity of the matrix inverse operator implies that the inverse of the sketch is biased:
$$\mathbb{E}[(\tilde{A}^\top \tilde{A} + C)^{-1}] \neq (A^\top A + C)^{-1}$$
This phenomenon, known as inversion bias, degrades the performance of second-order optimization methods like Sub-sampled Newton (SSN).

Previous work (e.g., Dereziński et al., 2021) successfully characterized and corrected this bias for dense Gaussian and sparse sub-Gaussian (LESS) projections. However, these results did not apply to random sampling (uniform or leverage-based) or structured random projections (like SRHT), where existing proof techniques yielded vacuous (useless) bounds. The paper addresses the gap: Can the inversion bias of random sampling and structured projections be precisely characterized and corrected to enable problem-independent convergence rates?

2. Methodology

The authors employ tools from Non-Asymptotic Random Matrix Theory (RMT) to analyze the spectral properties of randomly sampled matrices.

A. Fine-Grained Characterization of Bias

Instead of relying on standard subspace embedding arguments, the authors derive a self-consistent equation for the expected inverse.

• They define a diagonal matrix $D$ such that the expected inverse of the sketch is approximately the inverse of a modified matrix:
  $$\mathbb{E}[(A^\top S^\top S A + C)^{-1}] \approx (A^\top D A + C)^{-1}$$
• The diagonal entries $D_{ii}$ are determined by a fixed-point equation involving the leverage scores $\ell_i^C$ and the sampling probabilities $\pi_i$:
  $$D_{ii} = \frac{m}{m + a_i^\top (A^\top D A + C)^{-1} a_i / \pi_i}$$
• This reveals that the bias is not a simple scalar factor but depends on the specific structure of the sampling distribution and the leverage scores.

B. De-biasing Strategy

Based on the fine-grained analysis, the authors propose a matrix-valued de-biasing scheme.

• They construct a new sampling matrix $\check{S}$ by re-weighting the original sampling matrix $S$:
  $$\check{S} = \text{diag}\left( \sqrt{\frac{m}{m - \ell_{is}^C / \pi_{is}}} \right) \cdot S$$
• This re-weighting effectively cancels out the bias term derived in the self-consistent equation, rendering $(A^\top \check{S}^\top \check{S} A + C)^{-1}$ an unbiased estimator of $(A^\top A + C)^{-1}$.

C. Approximate and Structured Cases

• Approximate Leverage Scores: The authors show that using computationally efficient approximate leverage scores in the re-weighting factor introduces only a negligible increase in bias, provided the approximation is within a certain factor.
• Scalar Debiasing for SRHT: For the Subsampled Randomized Hadamard Transform (SRHT), the leverage scores are approximately uniform. In this specific case, the complex matrix re-weighting simplifies to a scalar rescaling factor $\frac{m}{m - d_{\text{eff}}}$, similar to the Gaussian case but with rigorous justification for the sampling context.

3. Key Contributions

1. Precise Characterization of Inversion Bias: The paper provides the first non-vacuous, fine-grained characterization of inversion bias for general random sampling (uniform and leverage-based) and structured projections (SRHT). It moves beyond the "leave-one-out" scalar analysis used for Gaussian projections.
2. Novel De-biasing Technique: It introduces a re-weighting scheme (Theorem 3.2) that corrects the bias for random sampling. It proves that this scheme yields an $(\epsilon, \delta)$-unbiased estimator.
3. Problem-Independent Convergence Rates for SSN: By applying the de-biasing technique to Sub-sampled Newton methods, the authors establish the first problem-independent local convergence rates for SSN using random sampling. The convergence rate matches that of Newton Sketch with dense Gaussian projections, overcoming previous limitations where rates depended on condition numbers or Lipschitz constants.
4. Phase Transition Analysis: The paper analyzes the behavior of scalar debiasing (using $\frac{m}{m-d_{\text{eff}}}$) under approximate leverage sampling. It identifies a phase transition: if the sampling distribution is sufficiently close to exact leverage sampling, scalar debiasing works well; otherwise, the bias grows significantly, necessitating the fine-grained matrix re-weighting.

4. Results

Theoretical Results

• Theorem 3.1 & 3.2: Establish that the inverse of a de-biased random sampling sketch is an unbiased estimator of the true inverse, with error bounds depending on the effective dimension $d_{\text{eff}}$ and the number of samples $m$.
• Theorem 4.3: Proves that the de-biased SSN algorithm converges locally with a rate proportional to $\frac{d_{\text{eff}}}{m}$. This rate is independent of the problem's condition number, a significant improvement over prior SSN analyses.

Empirical Results

• Datasets: Experiments were conducted on MNIST and CIFAR-10 datasets using logistic regression.
• Performance:
  • De-biased SSN consistently outperformed the Newton-LESS method (which uses random projections) in terms of the "complexity-convergence" trade-off.
  • While Newton-LESS running time increased significantly with sketch size $m$, the proposed SSN-ARLev (using approximate ridge leverage scores with de-biasing) maintained a nearly constant running time while achieving superior convergence.
  • Among various sampling schemes (SRHT, Shrinkage Leverage, Approximate Leverage), the Approximate Ridge Leverage (ARLev) with de-biasing offered the best balance of speed and accuracy.
• Bias Reduction: Numerical experiments confirmed that the proposed scalar and matrix debiasing techniques drastically reduced the spectral norm of the inversion bias compared to uncorrected sketches.

5. Significance

This work bridges a critical gap between Randomized Numerical Linear Algebra and Random Matrix Theory.

• Practical Impact: It enables the use of random sampling (which is often cheaper and more scalable than random projections, especially for sparse data) in second-order optimization without sacrificing convergence guarantees.
• Theoretical Advancement: It resolves the issue of "vacuous bounds" in previous analyses of sampling-based inverses, providing a rigorous foundation for de-biasing.
• Algorithmic Improvement: The proposed de-biased SSN method offers a practical alternative to Gaussian-based Newton Sketch, achieving similar convergence rates with lower computational overhead, making it highly suitable for massive-scale machine learning applications.

In summary, the paper demonstrates that by precisely understanding and correcting the inversion bias inherent in random sampling, one can achieve the theoretical benefits of dense Gaussian sketches while retaining the computational efficiency of random sampling.