Tight Sensitivity Bounds For Smaller Coresets

Alaa Maalouf, Adiel Statman, Dan Feldman

An $\epsilon$-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 distanc…