Research map / Learning theory and algorithms / Matrix and tensor methods
Iterative Hessian Sketch: Fast and Accurate Solution Approximation for Constrained Least-Squares
Mert Pilanci, Martin J. Wainwright
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 |
|---|---|---|---|
| use IHS (sketched subproblems) instead of homotopy on the original problem, with sketching time included | Lasso via homotopy · Sparse regression running time, n=524288, d=500 | running time (seconds): 12.0969 -> 5.5792 | Improved |
| use IHS without sketching time instead of homotopy on the original problem | Lasso via homotopy · Sparse regression running time, n=524288, d=500 | running time (seconds): 12.0969 -> 3.1593 | Improved |
| use IHS on the smallest problem including sketching time | Lasso via homotopy · Sparse regression running time, n=4096, d=500 | running time (seconds): 0.0840 -> 0.0877 | Hurt |
| use IHS instead of naive sketch with same total number of projections | l1-constrained least squares · Sparse least squares, d in {16..256} | error: 0.11 vs roughly twice as large for the naive sketch | Improved |
| use IHS instead of classical sketch for nuclear-norm constrained matrix regression over n | nuclear-norm least squares · Matrix recovery 20x20, Figure 8a | mean-squared error | Improved |
| use IHS instead of classical sketch for multi-task classifier on JAFFE | nuclear-norm multi-task classifier · JAFFE facial expression | classification error rate | Improved |
| use IHS sketched solution instead of original least-squares solution for prediction | sparse least squares · Prediction MSE versus n, Figure 6 | prediction MSE | No clear effect |
Closest papers by meaning
- Optimal Iterative Sketching Methods with the Subsampled Randomized Hadamard Transform (NeurIPS 2020 · similarity 0.92)
- Iterative Double Sketching for Faster Least-Squares Optimization (ICML 2022 · similarity 0.92)
- Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees (ICLR 2025 · similarity 0.90)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.90)
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.88)
- Matrix Product Sketching via Coordinated Sampling (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.
