Research map / Optimization / Optimizers
Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton
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 that inverses of randomly sampled (uniform, leverage-based) and SRHT sketches are biased, derives a fine-grained reweighted sampling that corrects this bias, and uses it to get problem-independent local convergence rates for de-biased sub-sampled Newton.
Problem
Sketched matrix inverses (A^T S^T S A + C)^{-1} from random sampling and structured random projections are biased, which hurts ML pipelines such as sub-sampled Newton that need the inverse to be nearly unbiased.
Approach
A deterministic-equivalent analysis shows the sampled inverse concentrates around (A^T D A + C)^{-1} with a self-consistent diagonal D; reweighting each sampled row by 1/sqrt(m*pi_i - l_i^C) (using exact leverage scores) yields a nearly unbiased inverse, and for approximate leverage or SRHT this reduces to a scalar rescaling m/(m-d_eff).
Key results
- De-biased SSN with approximate ridge leverage sampling outperforms Newton-LESS across all tested sketch sizes m on MNIST and CIFAR-10 logistic regression, with running time of SSN-ARLev roughly constant in m while Newton-LESS time grows.
- Theory gives a local convergence rate of (rho_max d_eff / m)(1+eps) per iteration for de-biased SSN, with eps = O~(d_eff^{-nu/2}), matching the dense Gaussian Newton Sketch scale.
- Naive scalar debiasing m/(m-d_eff) with random sampling gives a vacuous inversion-bias bound of order sqrt(d_eff)/log d_eff, whereas the fine-grained reweighting gives non-vacuous bias.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use de-biased SSN with approximate ridge leverage score sampling (ARLev) instead of Newton-LESS | Logistic regression · MNIST | convergence–complexity trade-off | Helped |
| Use de-biased SSN with approximate ridge leverage score sampling (ARLev) instead of Newton-LESS | Logistic regression · CIFAR-10 | convergence–complexity trade-off | Helped |
| Use de-biased SSN methods instead of first-order methods | Logistic regression · MNIST and CIFAR-10 | convergence–complexity trade-off | Helped |
| Use de-biased SSN methods instead of Newton-LESS | Logistic regression · MNIST and CIFAR-10 | convergence–complexity trade-off | Helped |
| Use SRHT sampling rather than Newton-LESS | De-biased SSN · MNIST and CIFAR-10 | convergence–complexity trade-off | Helped |
| Use SRHT sampling rather than other de-biased SSN variants | De-biased SSN · MNIST and CIFAR-10 | speed | Hurt |
| Use SLev rather than ALev sampling | De-biased SSN · MNIST and CIFAR-10 | speed | Hurt |
| Use ARLev sampling rather than other evaluated methods | De-biased SSN · MNIST and CIFAR-10 | convergence–complexity trade-off | Helped |
Surprising findings
- Naively adapting the scalar debiasing proof for random projections yields a vacuous bound for random sampling, so the standard m/(m-d_eff) factor is insufficient without refinement.
- For approximate leverage sampling, any scalar rescaling of the sampled inverse remains biased by order d_eff/m, a lower bound from prior work.
Limitations
- Fine-grained debiasing requires exact leverage scores, which are expensive; approximate scores increase bias slightly.
- Local convergence only, with neighborhood-dependent conditions and sketch size requirements m >= C rho_max d_eff^{1+nu}.
Experimental setup
Datasets: MNIST CIFAR-10
Benchmarks: MNIST logistic regression CIFAR-10 logistic regression
Metrics: relative error ||beta_T - beta*||_H^2 / ||beta_0 - beta*||_H wall-clock running time
Baselines: Gradient Descent Stochastic Gradient Descent Newton-LESS Shrinkage leverage sampling (SLev) SRHT sketch
Builds on: Newton Sketch LESS embeddings Newton-LESS Sherman-Morrison formula
Closest papers by meaning
- Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions (NeurIPS 2026 · similarity 0.92)
- Optimal Iterative Sketching Methods with the Subsampled Randomized Hadamard Transform (NeurIPS 2020 · similarity 0.90)
- Precise expressions for random projections: Low-rank approximation and randomized Newton (NeurIPS 2020 · similarity 0.89)
- Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update (NeurIPS 2021 · similarity 0.88)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.87)
- RSN: Randomized Subspace Newton (NeurIPS 2019 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.