arXiv preprint ·
Sketching in Regression: Sketchy in Practice?
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $\mathbb{R}^{n}$ to a subspace of $\mathbb{R}^{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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
SynForecast: Controlled Synthetic Time Series for Forecasting Research
Post-stratified importance sampling
Shrinkage prior for implicit generative models
Bagel: A Fast Bayesian Online Changepoint Detection Algorithm for Linear Models via Posterior Merging
Transport along Local Annealing Paths: Wasserstein Geometry and Multimodal Sampling
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.