paper-with-me

홈 › Papers

Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions

2026-05-24 · Chengmei Niu, Sachin Garg, Michał Dereziński, Zhenyu Liao arxiv

Random sampling is a fundamental tool in modern machine learning and numerical linear algebra for reducing the computational cost of large-scale matrix problems. Existing analyses, however, rely primarily on subspace embedding guarantees, which do not precisely characterize the statistical bias of nonlinear random oblique projections induced by sampling, which arises ubiquitously in subsampled least squares and fast low-rank approximation methods. Because (pseudo)inversion is nonlinear, these random oblique projections can be systematically biased even when the underlying sketch is unbiased, thereby introducing hidden bias into downstream least squares and low-rank approximation solutions. In this work, we develop a unified non-asymptotic theory for random oblique projections in high dimensions. We show that standard random sampling schemes generally induce a systematic statistical bias overlooked by classical subspace embedding-style analyses, and we propose a principled debiasing framework to correct it. We illustrate the power of the theory through two canonical applications. For subsampled least squares, we obtain sharp bias--variance characterizations, reveal previously unrecognized statistical suboptimality in widely used sampling schemes, and identify when debiasing yields provable improvements. For fast CUR decomposition, we develop a debiased approach with improved approximation accuracy. Numerical experiments further validate our theoretical findings.

📄 PDF Abstract BibTeX arXiv:2605.24955

Code (0)

등록된 구현이 없습니다.

Similar Papers 제목 키워드 기반

Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform

2020-02-03 · Jonathan Lacotte, Sifan Liu, Edgar Dobriban, Mert Pilanci

Random projections or sketching are widely used in many algorithmic and learning contexts. Here we study the performance of iterative Hessian sketch for least-squares problems. By leveraging and extending recent results …

Dimensionality Reduction

Optimal Iterative Sketching Methods with the Subsampled Randomized Hadamard Transform

2020-12-01 · NeurIPS 2020 12 · Jonathan Lacotte, Sifan Liu, Edgar Dobriban, Mert Pilanci

Random projections or sketching are widely used in many algorithmic and learning contexts. Here we study the performance of iterative Hessian sketch for least-squares problems. By leveraging and extending recent results …

Dimensionality Reduction

Sparse Projection Oblique Randomer Forests

2015-06-10 · Tyler M. Tomita, James Browne, Cencheng Shen, Jaewon Chung 외

Decision forests, including Random Forests and Gradient Boosting Trees, have recently demonstrated state-of-the-art performance in a variety of machine learning settings. Decision forests are typically ensembles of axis-…

Computational Efficiency

Optimal Randomized First-Order Methods for Least-Squares Problems

2020-02-21 · ICML 2020 1 · Jonathan Lacotte, Mert Pilanci

We provide an exact analysis of a class of randomized algorithms for solving overdetermined least-squares problems. We consider first-order methods, where the gradients are pre-conditioned by an approximation of the Hess…

Accelerated and interpretable oblique random survival forests

2022-08-01 · Byron C. Jaeger, Sawyer Welden, Kristin Lenoir, Jaime L. Speiser 외

The oblique random survival forest (RSF) is an ensemble supervised learning method for right-censored outcomes. Trees in the oblique RSF are grown using linear combinations of predictors to create branches, whereas in th…

BenchmarkingComputational EfficiencyNegation