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

A substantial body of work in machine learning (ML) and randomized numerical linear algebra (RandNLA) has exploited various sorts of random sketching methodologies, including random sampling and random projection, with much of the analysis using Johnson--Lindenstrauss and subspace embedding techniques. Recent studies have identified the issue of inversion bias -- the phenomenon that inverses of random sketches are not unbiased, despite the unbiasedness of the sketches themselves. This bias presents challenges for the use of random sketches in various ML pipelines, such as fast stochastic optimization, scalable statistical estimators, and distributed optimization. In the context of random projection, the inversion bias can be easily corrected for dense Gaussian projections (which are, however, too expensive for many applications). Recent work has shown how the inversion bias can be corrected for sparse sub-gaussian projections. In this paper, we show how the inversion bias can be corrected for random sampling methods, both uniform and non-uniform leverage-based, as well as for structured random projections, including those based on the Hadamard transform. Using these results, we establish problem-independent local convergence rates for sub-sampled Newton methods.

Modern machine learning often relies on randomized techniques to accelerate large-scale computations, such as approximating large matrices through random sampling or projection. However, recent studies have uncovered a subtle yet systematic error, known as inversion bias, which arises when these approximations are inverted within machine learning pipelines like stochastic optimization. This bias can degrade the reliability and performance of widely used algorithms. While previous work has addressed inversion bias for dense Gaussian and sparse sub-Gaussian projections, no general correction has been available for random sampling, which remains one of the most practical and computationally efficient sketching techniques. Our research introduces a unified correction framework that mitigates inversion bias for both uniform and leverage-based random sampling, as well as for structured projections such as those based on the Hadamard transform. We apply this framework to sub-sampled Newton methods and establish improved, problem-independent local convergence rates. By bridging theoretical insights with practical algorithm design, our work enhances the accuracy and robustness of randomized methods in large-scale machine learning and optimization tasks.