Research map / Learning theory and algorithms / Matrix and tensor methods
Sketching Algorithms and Lower Bounds for Ridge Regression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Replace an error-dependent subspace embedding with a constant subspace embedding plus an AMM guarantee | One-iteration ridge regression sketching with OSNAP · Ridge regression | OSNAP sparsity: O(\sqrt{\sigma^2/\lambda\varepsilon} \cdot \log(n)) -> O(\log(n)) | Helped |
| Replace an error-dependent subspace embedding with a constant subspace embedding plus an AMM guarantee | One-iteration ridge regression sketching · Ridge regression | total running time: O(\nnz(A)\operatorname{poly}(\log(n))/\sqrt{\varepsilon} + n^{\omega}\operatorname{poly}(\log(n))/\varepsilon) -> O(\nnz | Helped |
| Increase the number of iterative refinement steps from one to t (ablation) | Proposed iterative sketching algorithm · Ridge regression | solution relative error: \varepsilon\opnorm{x^*} -> (\sqrt{\varepsilon})^t\opnorm{x^*} | Helped |
| Use fresh sketching matrices at each iteration | Proposed iterative sketching algorithm · Ridge regression | solution relative error: (\sqrt{\varepsilon})^t\opnorm{x^*} | Helped |
| Use OSNAP with any sparsity parameter while meeting the AMM guarantee | OSNAP sketch for ridge regression · Ridge regression | AMM guarantee: m = \Omega(1/\varepsilon^2\delta) | Helped |
Closest papers by meaning
- An Iterative, Sketching-based Framework for Ridge Regression (ICML 2018 · similarity 0.92)
- Matrix Product Sketching via Coordinated Sampling (ICLR 2025 · similarity 0.88)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.88)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.88)
- Asymptotically Free Sketched Ridge Ensembles: Risks, Cross-Validation, and Tuning (ICLR 2024 · similarity 0.88)
- Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees (ICLR 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.