16:00
14:30 - "\ell_p Sensitivity Sampling: Optimal bounds and an Application to Poisson pth-Root-Link Models"
\ell_p Sensitivity Sampling: Optimal bounds and an Application to Poisson pth-Root-Link Models
Abstract:
Sensitivity sampling is a general purpose technique for importance subsampling that is very popular for the construction of \ell_p subspace embeddings. These methods are important building blocks with broad applications in Machine Learning, Computational Statistics, and Computer Science.
Although other subsampling distributions have been shown to achieve smallest possible sample size for constructing \ell_p subspace embeddings, existing analyses of sensitivity sampling fall behind. However, sensitivity sampling is conceptionally and computationally
simpler than other methods and performs equally well or often better in practice. This motivates to reconsider the complexity of constructing \ell_p subspace embeddings via sensitivity sampling.
We first prove that sensitivity sampling is indeed suboptimal in the worst case. However, we introduce a new variation that samples proportional to a mixture of \ell_p and \ell_2 sensitivities. This \ell_2 augmentation technique allows us to obtain a provably optimal
subsample size. As an application, we show how sensitivity sampling can be used to approximate Poisson regression with pth-root-link.
The talk is based on the following two publications (also available on arXiv):
* Alexander Munteanu, Simon Omlor.
Optimal bounds for \ell_p sensitivity sampling via \ell_2 augmentation.
International Conference on Machine Learning (ICML), 2024.
https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Farxiv.org%2Fabs%2F2406.00328&data=05%7C02%7Ceugen.pircalabelu%40uclouvain.be%7C943f388491f841e2ab1408dd4683bccc%7C7ab090d4fa2e4ecfbc7c4127b4d582ec%7C1%7C0%7C638744253815359406%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=Zak%2BklIlL7DZeNveBJG2BrT%2BVpQv%2F1nx%2BEPGZcvbmc0%3D&reserved=0
* Han Cheng Lie, Alexander Munteanu.
Data subsampling for Poisson regression with pth-root-link.
Advances in Neural Information Processing Systems (NeurIPS), 2024.
https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Farxiv.org%2Fabs%2F2410.22872&data=05%7C02%7Ceugen.pircalabelu%40uclouvain.be%7C943f388491f841e2ab1408dd4683bccc%7C7ab090d4fa2e4ecfbc7c4127b4d582ec%7C1%7C0%7C638744253815379684%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=JtXte4tm2MqjT1E4M3Q80k7ar00QN5GtbFmNtMtGT24%3D&reserved=0