Research map / Optimization / Nonconvex and smooth optimization
Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees
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.
Proposes Sketching for Regularized Optimization (SRO) and an Iterative SRO variant that sketch the data matrix in the quadratic term of regularized least squares, with approximation-error bounds for convex and nonconvex regularizers and minimax sparse-estimation rates.
Problem
Efficiently solving large-scale least squares problems with convex or nonconvex regularization (Lasso, ridge, generalized Lasso, sparse nonconvex penalties) when the number of samples n is large, with guarantees on the approximation error of sketched solutions.
Approach
Sketch only the quadratic term X^T X with a subspace embedding P, solve the resulting sketched regularized problem, and analyze the error via a degree-of-nonconvexity quantity; iterate the sketch on the residual problem (Iterative SRO) to reduce error geometrically while reusing one sketch matrix.
Key results
- Iterative SRO's approximation error is roughly one third of one-shot SRO's for generalized Lasso (N=10 iterations, averaged over 100 trials).
- For generalized Lasso, Iterative SRO took 4.91s versus 11.57s for solving the original problem (gamma=4), with error 0.031.
- Theory gives minimax sparse estimation rate O(sqrt(s log d / n)) for sketched Lasso and sparse nonconvex (MCP/SCAD-type) learning under stated assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Iteratively refine the sketch-based solution instead of using one-pass SRO | SRO on GLasso · GLasso | approximation error: roughly 1/3 of that of SRO | Helped |
| Reuse one sketch matrix rather than resampling and recomputing the sketch at each iteration | Iterative SRO-IHS on GLasso · GLasso | running time: 5.32s -> 4.91s | Helped |
| Iteratively refine the sketch-based solution instead of using one-pass SRO | SRO on Lasso with sparse subspace embedding · Lasso, sparse subspace embedding | ℓ2 error to true regression vector: 0.115 ± 0.149 -> 0.010 ± 0.017; 0.063 ± 0.023 -> 0.009 ± 0.009; 0.059 ± 0.010 -> 0.004 ± 0.002; 0.025 ± 0.054 -> 0.008 ± | Helped |
| Iteratively refine the sketch-based solution instead of using one-pass SRO | SRO on Lasso with Gaussian subspace embedding · Lasso, Gaussian subspace embedding | ℓ2 error to true regression vector: 0.067 ± 0.092 -> 0.008 ± 0.003; 0.043 ± 0.066 -> 0.008 ± 0.007; 0.044 ± 0.038 -> 0.004 ± 0.002; 0.046 ± 0.030 -> 0.003 ± | Helped |
| Use Iterative SRO rather than the original problem solution | Lasso with sparse subspace embedding · Lasso, sparse subspace embedding | ℓ2 error to true regression vector: 0.010 ± 0.017 vs 0.008 ± 0.002; 0.009 ± 0.009 vs 0.007 ± 0.006; 0.004 ± 0.002 vs 0.003 ± 0.001; 0.008 ± 0.005 vs 0.006 ± | Mixed |
| Use Iterative SRO rather than the original problem solution | Lasso with Gaussian subspace embedding · Lasso, Gaussian subspace embedding | ℓ2 error to true regression vector: 0.008 ± 0.003 vs 0.007 ± 0.001; 0.008 ± 0.007 vs 0.006 ± 0.003; 0.004 ± 0.002 vs 0.003 ± 0.001; 0.003 ± 0.004 vs 0.002 ± | Mixed |
| Increase the sketch size | Iterative SRO on ridge regression · Ridge regression | approximation error | Helped |
| Use SRO rather than Iterative SRO | SRO on Lasso · Lasso | approximation error | Hurt |
Surprising findings
- Sketched Noisy SSC with SRO sometimes performs better than the original unsketched Noisy SSC for most values of lambda on Extended Yale-B, attributed to sketching reducing noise effects.
Limitations
- Relative-error bounds for nonconvex regularizers require a smoothness condition (L_h) and a small-nonconvexity regime tied to sigma_min^2(X).
- Minimax rates for sparse nonconvex learning rely on several technical assumptions (sparse eigenvalue conditions, RIP-type conditions, choice of sketch size) that the paper calls mild but does not fully verify in general.
Experimental setup
Datasets: Extended Yale-B
Benchmarks: Extended Yale-B
Metrics: relative approximation error ||beta_tilde - beta*||_X^2 / n running time parameter estimation error clustering accuracy NMI
Baselines: Iterative Hessian Sketch (IHS) Noisy SSC K-means Spectral Clustering SMCE SSC-OMP
Builds on: Iterative Hessian Sketch Johnson-Lindenstrauss sketching SCAD MCP
Closest papers by meaning
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.89)
- Learning the Positions in CountSketch (ICLR 2023 · similarity 0.89)
- Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces (ICML 2018 · similarity 0.89)
- Iterative Double Sketching for Faster Least-Squares Optimization (ICML 2022 · similarity 0.89)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.88)
- Can Gaussian Sketching Converge Faster on a Preconditioned Landscape? (ICML 2024 · 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.