Private Geometric Median in Nearly-Linear Time

Syamantak Kumar, Daogao Liu, Kevin Tian, Chutong Yang

TL;DR

This paper presents the first nearly-linear time algorithm for computing a differentially private geometric median, drastically reducing the computational complexity from superlinear ($\widetilde{O}(n^2d)$) to nearly-linear ($\widetilde{O}(nd + \frac{d}{\alpha^2})$). By combining clever random subsampling with a custom stability analysis for DP-SGD on non-smooth objectives, the authors achieve information-theoretically optimal sample complexity while matching the efficiency of the fastest non-private first-order methods.

What Problem Does This Paper Address?

In high-dimensional statistics, estimating the "average" of a dataset is a foundational task. While the standard empirical mean is simple to compute, it is notoriously fragile—a single outlier can completely corrupt it. The geometric median is a classic, robust alternative that minimizes the sum of Euclidean distances to all data points, naturally resisting outliers.

However, computing the geometric median under the constraints of Differential Privacy (DP) introduces a fundamental paradox. DP guarantees must hold for worst-case datasets, meaning privacy noise typically scales with the absolute worst-case boundary (the total domain size $R$). This completely undercuts the purpose of using a robust estimator, which should ideally only care about where most of the data lies (the effective radius $r$).

A recent breakthrough by Haghifam, Steinke, and Ullman (HSU24) proved that it is possible to achieve optimal DP error scaling only with the effective radius rather than the worst-case domain. Unfortunately, their algorithm was computationally expensive, requiring superlinear time ($\widetilde{O}(n^2d)$) due to pairwise distance calculations. This paper tackles the computational bottleneck: How can we compute this robust, private geometric median in nearly-linear time?

Methods

The authors accelerate the two-phase framework established by HSU24: a Warm Start phase (to find a rough estimate) followed by a Boosting phase (to refine the accuracy).

  1. Accelerated Warm Start via Subsampling:
  2. Radius Estimation: Instead of computing all $O(n^2)$ pairwise distances to find the effective radius, the authors show that randomly sampling a small subset of points ($\approx \log(1/\delta)$) is sufficient to accurately estimate quantile thresholds, bringing the runtime down to $\widetilde{O}(nd)$.
  3. Centerpoint Estimation: They adapt FriendlyCore (a private data-filtering framework) using weights estimated through subsampling. They introduce a subtle privacy coupling argument to account for potential privacy leaks if the subsampling fails to accurately represent the dataset.
  4. Boosting via Stable DP-SGD:
  5. Standard DP optimization algorithms struggle with the geometric median objective because it is non-smooth (non-differentiable when an iterate lands exactly on a data point).
  6. The authors provide a custom sensitivity analysis for DP-SGD. They prove a structural property: gradient steps for the geometric median objective are inherently contractive (they bring coupled simulation paths closer together) unless the iterates are already extremely close to a data point. This stability allows them to bound the algorithm's sensitivity tightly and achieve fast convergence without requiring smoothness.

Datasets

The algorithm was evaluated using two types of synthetic datasets designed to test robustness against outliers and heavy tails:

  • GaussianCluster: Inlier data points are drawn identically and independently from a high-dimensional Gaussian distribution, while a fraction of outliers are distributed uniformly within a massive bounding ball of radius $R$.
  • HeavyTailed: Data points are sampled from a zero-mean multivariate Student’s $t$-distribution with varying degrees of freedom ($\nu$), simulating realistic, non-Gaussian noise.

Key Insights and Ideas

  • Quantiles via Subsampling: You don't need to look at every pair of points to know if a specific radius captures 75% of your data. A tiny random sample provides a highly accurate proxy, turning a quadratic-time bottleneck into a linear-time operation.
  • Non-Smooth Contractivity: The "aha!" moment for the boosting phase is realizing that the geometry of the geometric median forces gradient steps to be contractive. Even though the loss function is non-smooth, the paths of the algorithm run on neighboring datasets naturally converge, which inherently limits how much a single data point can alter the final outcome (lowering its sensitivity).

Key Results

  • Theoretical Speedup: The algorithm drops the runtime to $\widetilde{O}(nd + \frac{d}{\alpha^2})$, where $\alpha$ is the accuracy parameter. This matches the runtime of the best-known non-private first-order optimization methods.
  • Empirical Performance: In benchmarks against the HSU24 baseline (RadiusFinder), the authors' FastRadius algorithm achieved identical estimation quality but ran ~30x faster (e.g., 0.04 seconds vs. 1.2 seconds for $n=1000, d=10$).
  • Boosting Efficiency: Their optimized DP-SGD variant (FixedOrderDPSGD) consistently outperformed standard DP gradient descent on Gaussian cluster data, achieving lower error with significantly fewer passes over the dataset as the sample size grew.

Limitations and Future Work

  • Loose Constants in Centerpoint Estimation: The authors note that while their centerpoint estimation algorithm (Algorithm 3) is theoretically sound, its mathematical analysis results in loose constants that negatively impact practical performance. Consequently, they omitted it from their empirical evaluation, leaving room for future optimization.
  • Parallelization vs. Pass Complexity: Full-batch gradient methods can be easily parallelized across GPUs, meaning they can sometimes beat sequential DP-SGD variants in pure wall-clock time despite having worse theoretical pass complexity. Adapting this method to leverage mini-batches or adaptive step sizes effectively in parallel environments remains an open challenge.

Summary updated

Abstract

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 $(\varepsilon, δ)$-differentially private algorithm obtaining an $α$-multiplicative approximation to the geometric median objective, $\frac 1 n \sum_{i \in [n]} \|\cdot - \mathbf{x}_i\|$, given a dataset $\mathcal{D} := \{\mathbf{x}_i\}_{i \in [n]} \subset \mathbb{R}^d$. Their algorithm requires $n \gtrsim \sqrt d \cdot \frac 1 {α\varepsilon}$ samples, which they prove is information-theoretically optimal. This result is surprising because its error scales with the \emph{effective radius} of $\mathcal{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 {αε}$ samples, but in time $\widetilde{O}(nd + \frac d {α^2})$. 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.
BibTeX
@inproceedings{kumar2025private,
  author = {Syamantak Kumar and Daogao Liu and Kevin Tian and Chutong Yang},
  title = {{Private Geometric Median in Nearly-Linear Time}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=b3tygCf3T7},
}
Figure