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 $(ϵ,\delta )$-differentially private algorithm obtaining an $\alpha$-multiplicative approximation to the geometric median objective, $\frac{1}{n}{\sum }_{i\in n}\Vert \cdot$, given a dataset $D$ of $x_i$ for $i\in n$. Their algorithm requires $n\gtrsim \sqrt{d}\cdot \frac{1}{\alpha ϵ}$ 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\gtrsim \sqrt{d}\cdot \frac{1}{\alpha ϵ}$ samples, but in time $O(nd+\frac{d}{{\alpha }^2})$. Our runtime is nearly-linear, plus the cost of the cheapest non-private first-order method due to CLMPS16.

To achieve our results, we use subsampling and geometric aggregation tools inspired by FriendlyCore TCKMS22 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.