Timezone: »

Sharper Bounds for $\ell_p$ Sensitivity Sampling
David Woodruff · Taisuke Yasuda

Thu Jul 27 04:30 PM -- 06:00 PM (PDT) @ Exhibit Hall 1 #336
In large scale machine learning, *random sampling* is a popular way to approximate datasets by a small representative subset of examples. In particular, *sensitivity sampling* is an intensely studied technique which provides provable guarantees on the quality of approximation, while reducing the number of examples to the product of the *VC dimension* $d$ and the *total sensitivity* $\mathfrak{S}$ in remarkably general settings. However, guarantees going beyond this general bound of $\mathfrak{S} d$ are known in perhaps only one setting, for *$\ell_2$ subspace embeddings*, despite intense study of sensitivity sampling in prior work. In this work, we show the first bounds for sensitivity sampling for $\ell_p$ subspace embeddings for $p\neq 2$ that improve over the general $\mathfrak{S} d$ bound, achieving a bound of roughly $\mathfrak{S}^{2/p}$ for $1\leq p<2$ and $\mathfrak{S}^{2-2/p}$ for $2

Author Information

David Woodruff (Carnegie Mellon University)
Taisuke Yasuda (School of Computer Science, Carnegie Mellon University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors