# Sketching Algorithms and Lower Bounds for Ridge Regression

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 22 references that are in the map.
- First posted on arXiv 13 Apr 2022.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Lower bounds for oblivious subspace embeddings](https://mlsanity.com/paper/1308.3280/) (2013)
- [Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms](https://mlsanity.com/paper/2009.01161/) (2020)
- [The Product of Gaussian Matrices is Close to Gaussian](https://mlsanity.com/paper/2108.09887/) (2021)
- [Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs](https://mlsanity.com/paper/2102.11251/) (2021)
- [On Two-Pass Streaming Algorithms for Maximum Bipartite Matching](https://mlsanity.com/paper/2107.07841/) (2021)

## Built on by (most cited first, 4 of 4)

- [Credal Learning Theory](https://mlsanity.com/paper/2402.00957/) (2024)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [Rotation-Invariant Random Features Provide a Strong Baseline for Machine Learning on 3D Point Clouds](https://mlsanity.com/paper/2308.06271/) (2023)
- [The Advantages of Fresh Sketching for Ridge Regression](https://mlsanity.com/paper/2609.38565/) (2026)

## Abstract (arXiv)

We give a sketching-based iterative algorithm that computes a 1+varepsilon approximate solution for the ridge regression problem minx |Ax-b|22 +λ|x|22 where A ∈ Rn × d with d ≥ n. Our algorithm, for a constant number of iterations (requiring a constant number of passes over the input), improves upon earlier work (Chowdhury et al.) by requiring that the sketching matrix only has a weaker Approximate Matrix Multiplication (AMM) guarantee that depends on varepsilon, along with a constant subspace embedding guarantee. The earlier work instead requires that the sketching matrix has a subspace embedding guarantee that depends on varepsilon. For example, to produce a 1+varepsilon approximate solution in 1 iteration, which requires 2 passes over the input, our algorithm requires the OSNAP embedding to have m= O(nσ2/λvarepsilon) rows with a sparsity parameter s = O(log(n)), whereas the earlier algorithm of Chowdhury et al. with the same number of rows of OSNAP requires a sparsity s = O(√σ2/λvarepsilon · log(n)), where σ = opnormA is the spectral norm of the matrix A. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression. Finally, we show that the sketch size required for our algorithm is essentially optimal for a natural framework of algorithms for ridge regression by proving lower bounds on oblivious sketching matrices for AMM. The sketch size lower bounds for AMM may be of independent interest.