Tight Sensitivity Bounds For Smaller Coresets
| Autor: | Dan Feldman, Adiel Statman, Alaa Maalouf |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning Iterative method Machine Learning (stat.ML) Low-rank approximation 02 engineering and technology Computer Science::Computational Geometry Linear subspace Machine Learning (cs.LG) Combinatorics Reduction (complexity) Statistics - Machine Learning TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 020204 information systems 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Affine transformation Coreset Row Subspace topology Mathematics |
| Zdroj: | KDD |
| DOI: | 10.1145/3394486.3403256 |
| Popis: | An $\varepsilon$-coreset for Least-Mean-Squares (LMS) of a matrix $A\in{\mathbb{R}}^{n\times d}$ is a small weighted subset of its rows that approximates the sum of squared distances from its rows to every affine $k$-dimensional subspace of ${\mathbb{R}}^d$, up to a factor of $1\pm\varepsilon$. Such coresets are useful for hyper-parameter tuning and solving many least-mean-squares problems such as low-rank approximation ($k$-SVD), $k$-PCA, Lassso/Ridge/Linear regression and many more. Coresets are also useful for handling streaming, dynamic and distributed big data in parallel. With high probability, non-uniform sampling based on upper bounds on what is known as importance or sensitivity of each row in $A$ yields a coreset. The size of the (sampled) coreset is then near-linear in the total sum of these sensitivity bounds. We provide algorithms that compute provably \emph{tight} bounds for the sensitivity of each input row. It is based on two ingredients: (i) iterative algorithm that computes the exact sensitivity of each point up to arbitrary small precision for (non-affine) $k$-subspaces, and (ii) a general reduction of independent interest from computing sensitivity for the family of affine $k$-subspaces in ${\mathbb{R}}^d$ to (non-affine) $(k+1)$- subspaces in ${\mathbb{R}}^{d+1}$. Experimental results on real-world datasets, including the English Wikipedia documents-term matrix, show that our bounds provide significantly smaller and data-dependent coresets also in practice. Full open source is also provided. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|