BARC talk by Chris Schwiegelshohn 2025

Wednesday, 21 May 2025, Chris Schwiegelshohn, Associate Professor at Aarhus University, Denmark, will give a talk on "Almost Optimal PAC Learning for k-Means".

Abstract:
In PAC learning, we are given n samples from an unknown distribution D. Our goal is to find a solution using these samples that generalizes well with respect to D. We study the k-means problem where the goal is to minimize the squared Euclidean distance between points and the closest of at most k-centers. An important technique in this line of research are dimension reduction methods based on the Johnson-Lindenstrauss lemma. These methods, while optimal in many regimes, are not able to yield optimal PAC-learning bounds for k-means. Our main contribution is a nearly optimal bound on the sample complexity. Our technique is based on an ensemble of dimension reductions that bypass the barriers inherent to Johnson-Lindenstrauss-based methods, which may be of independent interest.

Bio:
Chris is an associate professor at Aarhus University. He has been part of the Danish research landscape since 2019, initially as a semi-regular house guest at BARC before joining Aarhus in 2020. His primary research interests are most aspects of clustering such as approximation, learning, and big data algorithms, as well as dynamic algorithms (in particular with people from Copenhagen).

Host:
Mikkel Thorup