Research map / Learning theory and algorithms / Matrix and tensor methods

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

NeurIPS 2026 · Learning theory and algorithms › Matrix and tensor methods · approach: Low-rank approximation theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows random row-sampling induces systematic bias in oblique projections (via pseudoinverse nonlinearity) and proposes a row-rescaling debiasing (leverage-weighted diagonal) that yields sharper bias-variance bounds for subsampled OLS and a debiased fast CUR.

Problem

Subspace-embedding analyses do not precisely characterize the statistical bias of random oblique projections X(SX)^dagger S induced by row sampling, which affects subsampled least squares and fast CUR decomposition.

Approach

Derive a debiased sampling matrix whose row weights are sqrt(1/(1 - ell_i/(m pi_i))), so that the expected debiased oblique projection approximates the orthogonal projection; use leave-two-out arguments to get non-asymptotic bias and variance bounds for subsampled OLS and debiased fast CUR.

Key results

• Classical subsampled OLS with approximate leverage sampling has bias lower bound Omega(p^2/m^2) that no scalar rescaling can remove.
• Debiased subsampled OLS achieves bias of order tilde O(theta_max^3 p^3/m^3) with variance no larger than classical (Delta(X) + small term).
• For exact leverage score sampling the debiasing reduces to scalar sqrt(m/(m-p)) and the debiased and classical projections coincide, so no debiasing is needed.

Surprising findings

• Exact leverage score sampling and SRHT (in the analysed regime) are already nearly unbiased, so debiasing gives little benefit for them.
• Uniform sampling has the largest bias and debiasing it with exact leverage scores substantially reduces its bias.

Limitations

• Bounds rely on high-probability event conditioning and assume sketch sizes m >= C theta_max p log(p/delta).
• Lower bound counterexample is constructed for a specific data matrix, not a universal statement for all X.

Experimental setup

Datasets: Million Song Year Prediction Dataset Flight Delay dataset

Benchmarks: Million Song Year Prediction Dataset Flight Delay dataset

Metrics: relative bias relative variance CUR approximation error

Baselines: uniform sampling leverage score sampling SRHT LESS fast CUR (sketched)

Builds on: Sherman-Morrison formula leverage score sampling matrix-level debiasing of sketched inverses LESS embeddings

Closest papers by meaning

• Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton (ICML 2025 · similarity 0.92)
• High-Dimensional Optimization in Adaptive Random Subspaces (NeurIPS 2019 · similarity 0.87)
• Precise expressions for random projections: Low-rank approximation and randomized Newton (NeurIPS 2020 · similarity 0.87)
• Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.85)
• Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.84)
• Non-Asymptotic Uncertainty Quantification in High-Dimensional Learning (NeurIPS 2024 · similarity 0.84)