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

Chengmei Niu, Zhenyu Liao, Zenan Ling, Michael W. Mahoney
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:46649-46692, 2025.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-niu25c, title = {Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled {N}ewton}, author = {Niu, Chengmei and Liao, Zhenyu and Ling, Zenan and Mahoney, Michael W.}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {46649--46692}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/niu25c/niu25c.pdf}, url = {https://proceedings.mlr.press/v267/niu25c.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton %A Chengmei Niu %A Zhenyu Liao %A Zenan Ling %A Michael W. Mahoney %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-niu25c %I PMLR %P 46649--46692 %U https://proceedings.mlr.press/v267/niu25c.html %V 267 %X 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.
APA
Niu, C., Liao, Z., Ling, Z. & Mahoney, M.W.. (2025). Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:46649-46692 Available from https://proceedings.mlr.press/v267/niu25c.html.

Related Material