# Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees

arXiv: https://arxiv.org/abs/2311.01806 · HTML: https://mlsanity.com/paper/2311.01806/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 37 references that are in the map.
- First posted on arXiv 3 Nov 2023.

## Builds on (most cited first, 11 of 11)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Practical sketching algorithms for low-rank matrix approximation](https://mlsanity.com/paper/1609.00048/) (2016)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares](https://mlsanity.com/paper/1406.5986/) (2014)
- [Universality laws for randomized dimension reduction, with applications](https://mlsanity.com/paper/1511.09433/) (2015)
- [Noisy Sparse Subspace Clustering](https://mlsanity.com/paper/1309.1233/) (2013)
- [Optimal computational and statistical rates of convergence for sparse nonconvex learning problems](https://mlsanity.com/paper/1306.4960/) (2013)
- [Greedy Feature Selection for Subspace Clustering](https://mlsanity.com/paper/1303.4778/) (2013)
- [Isometric sketching of any set via the Restricted Isometry Property](https://mlsanity.com/paper/1506.03521/) (2015)
- [Theory of Dual-sparse Regularized Randomized Reduction](https://mlsanity.com/paper/1504.03991/) (2015)
- [Sparse Learning for Large-scale and High-dimensional Data: A Randomized Convex-concave Optimization Approach](https://mlsanity.com/paper/1511.03766/) (2015)

## Abstract (arXiv)

Randomized algorithms are important for solving large-scale optimization problems. In this paper, we propose a fast sketching algorithm for least square problems regularized by convex or nonconvex regularization functions, Sketching for Regularized Optimization (SRO). Our SRO algorithm first generates a sketch of the original data matrix, then solves the sketched problem. Different from existing randomized algorithms, our algorithm handles general Frechet subdifferentiable regularization functions in an unified framework. We present general theoretical result for the approximation error between the optimization results of the original problem and the sketched problem for regularized least square problems which can be convex or nonconvex. For arbitrary convex regularizer, relative-error bound is proved for the approximation error. Importantly, minimax rates for sparse signal estimation by solving the sketched sparse convex or nonconvex learning problems are also obtained using our general theoretical result under mild conditions. To the best of our knowledge, our results are among the first to demonstrate minimax rates for convex or nonconvex sparse learning problem by sketching under a unified theoretical framework. We further propose an iterative sketching algorithm which reduces the approximation error exponentially by iteratively invoking the sketching algorithm. Experimental results demonstrate the effectiveness of the proposed SRO and Iterative SRO algorithms.