Least-mean squares (LMS) solvers such as Linear Ridge Lasso-Regression, SVD and Elastic-Net not only solve fundamental machine learning problems, but are also the building blocks in a variety of other methods, such as decision trees and matrix factorizations. We suggest an algorithm that gets a finite set of @math @math -dimensional real vectors and returns a weighted subset of @math vectors whose sum is the same. The proof in Caratheodory's Theorem (1907) computes such a subset in @math time and thus not used in practice. Our algorithm computes this subset in @math time, using @math calls to Caratheodory's construction on small but "smart" subsets. This is based on a novel paradigm of fusion between different data summarization techniques, known as sketches and coresets. As an example application, we show how it can be used to boost the performance of existing LMS solvers, such as those in scikit-learn library, up to x100. Generalization for streaming and distributed (big) data is trivial. Extensive experimental results and complete open source code are also provided.
A main advantage of a coreset over a sketch is that it preserves sparsity of the input rows @cite_35 , which usually reduces theoretical running time. Our experiments show, as expected, that coresets can also be used to significantly improve the numerical stability of existing algorithms, even if the running time is the same. Another advantage is that the same coreset can be used for parameter tuning over a large set of candidates. In addition to other reasons, this significantly reduced the running time of such algorithms in our experiments; see .
@cite_35
1580060649
In this paper we present a practical solution with performance guarantees to the problem of dimensionality reduction for very large scale sparse matrices. We show applications of our approach to computing the Principle Component Analysis (PCA) of any @math matrix, using one pass over the stream of its rows. Our solution uses coresets: a scaled subset of the @math rows that approximates their sum of squared distances to @math -dimensional subspace. An open theoretical problem has been to compute such a coreset that is independent of both @math and @math . An open practical problem has been to compute a non-trivial approximation to the PCA of very large but sparse databases such as the Wikipedia document-term matrix in a reasonable time. We answer both of these questions affirmatively. Our main technical result is a new framework for deterministic coreset constructions based on a reduction to the problem of counting items in a stream.