Steffen Grünewälder - Compressed Empirical Measures

I will discuss some of my recent results on compressing the empirical measure in the context of finite dimensional reproducing kernel Hilbert spaces (RKHSs).The aim is to significantly reduce the size of the sample while preserving minimax optimal rates of convergence. Such a reduction in size is of crucial importance when working with kernel methods in the context of large-scale data since kernel methods scale poorly with the sample size. In the RKHS context, an embedding of the empirical measure is contained in a convex set within an RKHS and can be approximated by using convex optimization techniques. Such an approximation gives rise to a small core-set of data points. A key quantity that controls the size of such a core-set is the size of the largest ball that fits within the convex set and which is centred at the embedding of the empirical measure. I will give an overview of how high probability lower bounds on the size of such a ball can be derived before discussing how the approach can be adapted to standard problems such as non-linear regression.  (The talk will be based on an extended version of https://arxiv.org/pdf/2204.08847.pdf).