Sketching in Regression: Sketchy in Practice?
Abstract
The Johnson-Lindenstrauss (JL) lemma and its extensions provide tools for solving the L2 regression problem in high-dimensional settings with n>d, by transforming a subspace of ℝn to a subspace of ℝm, (where m<n) while approximately preserving the norms of elements of the subspace. In this paper, we study the theoretical guarantees made by various JL-based subspace embeddings critically and concretely to gauge their practical applicability. We derive concrete versions of results on subspace embeddings in the literature to establish lower bounds on the reduced dimension as well as to concretely analyze the complexity of the Fast JL, OSNAP Transforms among other embeddings. These analyses suggest that guaranteeing substantial computational savings while maintaining the accuracy of the sketched solution requires data dimensions larger than those typically encountered in practice. We also see that, for practically necessary accuracy requirements or for sparsity requirements for computational gain, existing theoretical guarantees lead to substantially large reduced dimensions. This leads to very stringent data requirements for establishing guarantees of any kind.
Related
- Sparsity by Default: The Theory and Practice of ARD in Gaussian Process Regression for Variable Selection
- Generative modeling via hierarchical tensor sketching
- Fast matrix-vector products in tensor-train format via structured sketching
- Sketching Outside the Hilbert Space for the Infinite-Dimensional Randomised SVD
- Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions
BibTeX
@misc{das2026sketching,
title = {{Sketching in Regression: Sketchy in Practice?}},
author = {Somarddha Das and Soupayan Das Gupta and Koustav Goswami},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02808},
eprint = {2611.02808},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02808},
}
RIS
TY - UNPB
TI - Sketching in Regression: Sketchy in Practice?
AU - Somarddha Das
AU - Soupayan Das Gupta
AU - Koustav Goswami
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02808
UR - https://arxiv.org/abs/2611.02808
AB - The Johnson-Lindenstrauss (JL) lemma and its extensions provide tools for solving the L_2 regression problem in high-dimensional settings with n>d, by transforming a subspace of ℝ^n to a subspace of ℝ^m, (where m<n) while approximately preserving the norms of elements of the subspace. In this paper, we study the theoretical guarantees made by various JL-based subspace embeddings critically and concretely to gauge their practical applicability. We derive concrete versions of results on subspace embeddings in the literature to establish lower bounds on the reduced dimension as well as to concretely analyze the complexity of the Fast JL, OSNAP Transforms among other embeddings. These analyses suggest that guaranteeing substantial computational savings while maintaining the accuracy of the sketched solution requires data dimensions larger than those typically encountered in practice. We also see that, for practically necessary accuracy requirements or for sparsity requirements for computational gain, existing theoretical guarantees lead to substantially large reduced dimensions. This leads to very stringent data requirements for establishing guarantees of any kind.
ER -