Private Geometric Median

In this talk, I will discuss differentially private algorithms for computing the geometric median, a basic and robust estimation problem. Standard private optimization methods, such as DP gradient descent, require an a priori bound on a ball of radius R containing the data, and their error scales linearly with this worst-case radius. For the geometric median, this can be overly pessimistic: a small number of outliers may make R very large even when most datapoints lie in a much smaller region. I will show how to go beyond this worst-case dependence by designing private algorithms whose error depends instead on the effective diameter of most of the data.