Research map / Learning theory and algorithms / Sample complexity
Private Geometric Median in Nearly-Linear Time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives an (ε,δ)-DP geometric median algorithm with multiplicative (1+α) approximation in Õ(nd + d/α²) time, using subsampled FriendlyCore-style warm start and a custom DP-SGD sensitivity analysis for the non-smooth objective.
Problem
Privately estimating the geometric median of a dataset with multiplicative approximation guarantees, where prior DP algorithms needed superlinear time (roughly n^2 d or n^3 ε^2).
Approach
Speeds up the warm-start phase of the prior DP geometric median algorithm via subsampled distance scores (radius estimation and FriendlyCore-style weighted centerpoint), and proves a tighter DP-SGD sensitivity bound for the non-smooth geometric median objective using a contractiveness argument, yielding nearly-linear runtime.
Key results
- Achieves (1+α)-multiplicative approximation to the geometric median under (ε,δ)-DP with n ≳ √d/(αε) samples in time Õ(nd + d/α²), improving on the prior Õ(n²d + n³ε²) or Õ(n²d + nd² + d^4.372) runtimes.
- Constant-factor warm start runs in Õ(nd) time, independent of the aspect ratio R/r, compared with the prior nearly-linear ≈ nd log(R/r) centerpoint step only being faster for large aspect ratios.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use subsampling and geometric aggregation to speed up the warm-start phase | Private geometric median algorithm · Private geometric median | runtime: ≈ n²d -> Õ(nd) | Helped |
| Use a custom sensitivity analysis for DP-SGD iterates on the geometric-median objective | Private geometric median algorithm · Private geometric median | runtime: Õ(nd + d/α²) | Helped |
| Subsample points when estimating radius scores | FastRadius · Private geometric median warm start | runtime: O(nd log(R/r) log(log(R/r) 1/δ)) | Helped |
| Subsample points when estimating FriendlyCore weights | FastCenter · Private geometric median warm start | runtime: Õ(nd) | Helped |
| Apply subsampled FriendlyCore for centerpoint estimation | Private geometric median warm start · Large aspect ratios R/r | runtime | Helped |
Surprising findings
- The paper argues the prior work's claimed runtime for radius estimation (O(n^2 log(R/r))) should be O(n^2 d log(R/r)) once the cost of each distance comparison is counted.
Limitations
- Runtime retains an additive d/α² overhead beyond nearly-linear, matching the best non-private first-order method but not the non-private interior-point Õ(nd).
- Sample complexity requires n ≳ √d/(αε), information-theoretically tight but restrictive for small datasets.
- Theoretical paper with no empirical experiments.
Experimental setup
Metrics: multiplicative approximation ratio runtime
Baselines: HSU24 private geometric median algorithm
Builds on: FriendlyCore DP-SGD AboveThreshold
Closest papers by meaning
- Private Geometric Median (NeurIPS 2024 · similarity 0.91)
- Simple and Optimal Sublinear Algorithms for Mean Estimation (NeurIPS 2025 · similarity 0.87)
- Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers (NeurIPS 2025 · similarity 0.84)
- Optimal Coresets for Low-Dimensional Geometric Median (ICML 2024 · similarity 0.83)
- Geometric Median (GM) Matching for Robust k-Subset Selection from Noisy Data (ICML 2025 · similarity 0.83)
- Revisiting Sampson Approximations for Geometric Estimation Problems (CVPR 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.