Research map / Learning theory and algorithms / Combinatorial and search optimization
Householder Sketch for Accurate and Accelerated Least-Mean-Squares Solvers
Jyotikrishna Dass, Rabi Mahapatra
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Householder sketch (QR-based R and Q^T y) used to accelerate scikit-learn LMS solvers instead of raw data | RIDGECV, LASSOCV, ELASTICCV, LINREG · synthetic sequential data, n up to 24M | training time speedup vs default LMSCV: up to 100x (LASSO/ELASTIC), 400x (RIDGE) | Improved |
| Householder sketch replacing Caratheodory coreset (LMS-BOOST) | RIDGE, LASSO, ELASTIC, LINREG · synthetic sequential data, d=7 | training time vs LMS-BOOST: 10x (RIDGE); up to 100x for n<2.4M and 10x for n>2.4M (LASSO/ELASTIC/LINREG) | Improved |
| Distributed Householder-QR across p workers (local QR + master QR) (ablation) | DISTRIBUTED RIDGE-QR · 10M x 10 synthetic, p=2 to 16 | local Householder-QR time: halves with each doubling of workers | Improved |
| Distributed Householder-QR across workers, parallel speedup (ablation) | DISTRIBUTED RIDGE-QR · 500K/1M/2M x 100 synthetic | parallel speedup vs ideal speedup: near-linear speedup up to p=16 | Improved |
| Householder sketch vs ADMM on original data for ridge | RIDGE solver, 10M x 10 synthetic | computation time | Improved |
| Householder sketch based LMS-QR vs default LMS solvers on n=24M with d=25 and 50 | LMSCV and LMS-BOOST · synthetic n=24M, d up to 50 | ability to run (memory) | Improved |
| Householder QR-based LINREG-QR vs Caratheodory LINREG-BOOST numerical accuracy | LINREG on Household Power Consumption · ~2M x 8 real data | abs(||Xw*-y||^2 - ||Xw-y||^2) | No clear effect |
| Distributed Householder sketch vs ADMM in numerical accuracy | DISTRIBUTED RIDGE-QR · 10M x 10 synthetic, p=1 to 16 | accuracy vs scikit-learn RIDGE solution | Improved |
Closest papers by meaning
- Fast and Accurate Least-Mean-Squares Solvers for High Dimensional Data (TPAMI 2022 · similarity 0.88)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.86)
- Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees (ICLR 2025 · similarity 0.85)
- Matrix Product Sketching via Coordinated Sampling (ICLR 2025 · similarity 0.84)
- Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing (ICLR 2025 · similarity 0.83)
- Flag Aggregator: Scalable Distributed Training under Failures and Augmented Losses using Convex Optimization (ICLR 2024 · similarity 0.83)
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.
