Limitations of sketching methods for efficient regression with common data sizes
Sketching in Regression: Sketchy in Practice?
Data Structures and Algorithms
Summary
Solving large regression problems quickly often involves shrinking data dimensions while keeping important details. The authors examined well-known mathematical tools for this shrinking and found that to keep accuracy and speed, the data needs to be much bigger than what is typical. Their analysis shows that current guarantees require a lot of data or result in less practical reductions. This means these methods may not be very useful for everyday datasets and usual accuracy needs.
What this means in practice
- •For machine learning engineers: Evaluate the feasibility of subspace embedding techniques for large-scale regression tasks based on realistic data sizes and accuracy requirements.
- •For data infrastructure teams: Plan data processing pipelines by considering the limited dimension reduction possible without compromising accuracy according to current theoretical bounds.
A theory result. No direct application yet.
Authors
Somarddha Das, Soupayan Das Gupta, Koustav Goswami
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.