Please note: This PhD seminar will take place in DC 3317 and online.
Thomas Humphries, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Florian Kerschbaum
Clustering is an essential unsupervised learning problem that allows analysts to interpret complex datasets. However, without modification, classic clustering algorithms can leak substantial information about the underlying sensitive data.
In this talk, I give an overview of our work on various versions of the differentially private clustering problem. First, I discuss an evolutionary solution to the k-medians or facility location problem. We observe that the inherently random search process of evolutionary algorithms and their ability to minimize non-differentiable, low-information utility functions give them an edge over traditional approaches. Our work presents one of the first private genetic algorithms with practical utility. Second, I present FastLloyd, a lightweight solution to the federated k-means problem. FastLloyd combines a novel relative cluster update step with a lightweight secure aggregation protocol, resulting in a fast, accurate, and private federated solution. Finally, I introduce PE-means, an extension of the private evolution (PE) algorithm (an increasingly popular method for synthetic data generation), to the problem of k-means clustering. Building on insights from our first work, PE-means uses a low-information utility function to achieve an average improvement of 20% in clustering loss over state-of-the-art baselines. Our adaptation of PE includes new evolutionary operators for clustering, as well as other algorithmic improvements of independent interest.
To attend this PhD seminar in person, please go to DC 3317. You can also attend virtually on BigBlueButton.