Private Geometric Median in Nearly-Linear Time

Estimating the geometric median of a dataset is a robust counterpart to mean estimation, and is a fundamental problem in computational geometry. Recently, HSU24 gave an (, ) -differentially private algorithm obtaining an -multiplicative approximation to the geometric median objective, 1 n ₈ ₍ \| - xᵢ\|, given a dataset D: = \xᵢ\₈ ₍ Rᵈ. Their algorithm requires n d 1 samples, which they prove is information-theoretically optimal. This result is surprising because its error scales with the effective radius of D (i. e. , of a ball capturing most points), rather than the worst-case radius. We give an improved algorithm that obtains the same approximation quality, also using n d 1 samples, but in time O (nd + d ²). Our runtime is nearly-linear, plus the cost of the cheapest non-private first-order method due to CLM+16. To achieve our results, we use subsampling and geometric aggregation tools inspired by FriendlyCore TCK+22 to speed up the "warm start" component of the HSU24 algorithm, combined with a careful custom analysis of DP-SGD's sensitivity for the geometric median objective.