Research map / Learning theory and algorithms / Matrix and tensor methods
Distributed Least Squares in Small Space via Sketching and Bias Reduction
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 leverage-score sparsified (LESS) sketches with moderate sparsity yield nearly unbiased sketched least squares estimates, enabling two-pass, O(d^2 log(nd))-bit distributed averaging in current matrix multiplication time.
Problem
Sketching-based least squares estimators have bias that limits distributed averaging; existing unbiased constructions are too expensive in time or space or need many passes, so the time-space trade-off for distributed least squares remains unresolved.
Approach
A sharp bias analysis of LESS-sketched least squares showing bias scales as roughly d^2/(s m^2) in the sketch sparsity s, so sparser-than-needed-for-accuracy sketches (mixing ~1/eps leverage-score samples per row) give near-unbiased estimators; averaging q=1/eps such estimators recovers a (1+eps) approximation. Uses new higher-moment restricted Bai-Silverstein inequalities and Holder-based moment
Key results
- Bias of LESS-sketched least squares bounded by O((d/m^2)(1+d/s)) log^9 relative to L(x*), recovering the standard d^2/m^2 bias bound at s=1 and improving by a factor min(s,d) for larger s.
- Two-pass distributed algorithm achieves (1+eps) least squares approximation with O(d^omega + eps^-1 d^(2+gamma)) time, O(d^2 log(nd)) bits of space per machine, and O(d log(nd)) bits of communication, using O(1/eps) machines.
- Empirically, on YearPredictionMSD, the bias of single sketched estimators stays essentially unchanged as sketch size varies while total sketching cost is held fixed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase LESS sketch sparsity s above 1 | LESS-sketched least squares · Least squares | bias: improves on it for s\gg 1 by a factor of \min\{s, d\} | Helped |
| Average q=1/\epsilon independently sketched estimators | Leverage Score Sparsification · Distributed least squares | expected loss ratio: (1+2\epsilon) | Helped |
| Decrease sketch size while adjusting sparsity to keep total sketching cost the same | Distributed averaging of sketched least squares estimators · Benchmark datasets | single-estimator error | Hurt |
| Decrease sketch size while adjusting sparsity to keep total sketching cost the same | Distributed averaging of sketched least squares estimators · Benchmark datasets | bias | No clear effect |
| Use the proposed LESS sparsification instead of leverage score sampling | Distributed least squares · Least squares, preconditioner given | parallel passes: 1 versus 1/\epsilon | Helped |
Surprising findings
- Sparser sketches (mixing ~1/eps leverage score samples per row) preserve near-unbiasedness with no extra computational cost, a 'free lunch' effect.
Limitations
- Preconditioner construction costs worst-case d^omega time and the bound needs a preconditioner with condition number O(1).
- Bias bound contains polylog factors (log^9) and a lower-order d/m^2 term; the bound is only sharp up to these factors.
- Analysis assumes n = poly(d) and sketch dimension m large enough relative to d, with a bias bound holding only on a high-probability event (failure probability delta).
Experimental setup
Datasets: YearPredictionMSD
Benchmarks: YearPredictionMSD
Metrics: bias variance loss ratio L(x)/L(x*)
Baselines: Gaussian sketch leverage score sampling determinantal point process sampling Weighted Mb-SGD OSNAP
Builds on: LESS embeddings Bai-Silverstein inequality Rosenthal inequality Sherman-Morrison formula Dobriban and Liu inversion bias analysis
Closest papers by meaning
- Debiasing Sketched Ridge Regression: A Functional Estimation Perspective (NeurIPS 2026 · similarity 0.89)
- Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging (ICML 2017 · similarity 0.89)
- Matrix Product Sketching via Coordinated Sampling (ICLR 2025 · similarity 0.89)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.88)
- Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees (ICLR 2025 · similarity 0.88)
- Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton (ICML 2025 · 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.