Research map / Learning theory and algorithms / Kernels and regression theory
Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
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 |
|---|---|---|---|
| Use classical sketch instead of solving full MRR | Matrix ridge regression · MRR optimization | objective gap: f ({{\bf W}}^{\textrm{c}}) -f ({\bf W}^\star ) \leq \epsilon \beta \, f ({\bf W}^\star ) | Helped |
| Use Hessian sketch instead of solving full MRR | Matrix ridge regression · MRR optimization | objective gap: f ({{\bf W}}^{\textrm{h}}) - f ({\bf W}^\star ) \leq \epsilon \beta^2 \left(\tfrac{\|{\bf Y}\|_F^2 }{n } - f ({\bf W}^\s | Mixed |
| Use classical sketch | Matrix ridge regression · MRR statistical risk | variance: \Theta (\frac{n}{s}) | Hurt |
| Use Hessian sketch | Matrix ridge regression · MRR statistical risk | bias: (1+\epsilon ) ( 1 + \tfrac{\epsilon \|{\bf X}\|_2^2 }{n \gamma} ) | Hurt |
| Average independently sketched classical solutions (ablation) | Classical sketch · MRR optimization | objective gap: \beta \Big( \frac{\epsilon }{g} + \beta^2 \epsilon^2 \Big) \, f ({\bf W}^\star ) | Helped |
| Average independently sketched classical solutions (ablation) | Classical sketch · MRR statistical risk | variance: \frac{n}{s} \bigg( \frac{ \sqrt{ 1 + \epsilon }}{ \sqrt{h}} + \epsilon \bigg)^2 | Helped |
| Average independently sketched Hessian solutions (ablation) | Hessian sketch · MRR optimization | objective gap: \beta^2 \, \Big( \frac{\epsilon}{g} + \epsilon^2 \Big) \, \Big( \frac{\|{\bf Y}\|_F^2}{n} - f ({\bf W}^\star ) \Big) | Helped |
| Average independently sketched Hessian solutions (ablation) | Hessian sketch · MRR statistical risk | bias: 1 + \epsilon + \Big( \frac{\epsilon }{ \sqrt{g} } + \epsilon^2 \Big) \frac{\| {\bf X} \|_2^2 }{n \gamma} | Helped |
| Increase regularization γ | Classical and Hessian sketches · MRR optimization | objective approximation: \beta = \frac{\|{\bf X}\|_2^2}{\|{\bf X}\|_2^2 + n \gamma} | Helped |
| Increase regularization γ | Classical sketch · MRR statistical risk | variance | Helped |
| Increase the number g of averaged classical sketches (ablation) | Classical sketch · MRR statistical risk | bias | No clear effect |
| Increase the number g of averaged Hessian sketches (ablation) | Hessian sketch · MRR statistical risk | variance | No clear effect |
Closest papers by meaning
- An Iterative, Sketching-based Framework for Ridge Regression (ICML 2018 · similarity 0.93)
- Debiasing Sketched Ridge Regression: A Functional Estimation Perspective (NeurIPS 2026 · similarity 0.92)
- Sketching Algorithms and Lower Bounds for Ridge Regression (ICML 2022 · similarity 0.91)
- Asymptotically Free Sketched Ridge Ensembles: Risks, Cross-Validation, and Tuning (ICLR 2024 · similarity 0.89)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.89)
- Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees (ICLR 2025 · similarity 0.86)
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.