Research map / Learning theory and algorithms / Sample complexity
Private Geometric Median
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 polynomial-time (ε,δ)-DP algorithms for geometric median whose excess error scales with the quantile radius of the data rather than an a priori bound R, plus an inefficient pure-DP inverse smooth sensitivity method and a near-matching sample complexity lower bound.
Problem
Differentially private computation of the geometric median when the data lies in an unknown-location ball; standard DP-GD has excess error linear in an a priori radius R, which can be very loose.
Approach
A two-phase approach: a warm-up that privately estimates a quantile radius (RadiusFinder) and localizes the optimum (DP-GD with geometrically decaying step sizes), followed by fine-tuning via DP-GD or a noisy cutting-plane method; the geometric median's linear growth condition makes excess error scale with the quantile radius. Also an inverse smooth sensitivity mechanism for pure DP.
Key results
- Polynomial-time algorithms achieve excess error scaling with the quantile radius Δ_{4n/5}(θ*) instead of the a priori radius R, with sample complexity and runtime depending only logarithmically on R.
- Lower bound: any (ε,δ)-DP algorithm needs n = Ω̃(√d/ε) samples for a constant multiplicative approximation, matching the polynomial-time algorithms' sample complexity in ε and d.
- Inverse smooth sensitivity algorithm (SInvS) is ε-pure DP with multiplicative error (1+O(d log(R/r)/(nε))) and additive term nr, but runs in exponential time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use quantile-radius localization before DP-GD | LocDPGD · Synthetic dataset, varying R | F(θ; X⁽ⁿ⁾)/F(θ⋆; X⁽ⁿ⁾) | Helped |
| Replace the a priori radius dependence with localization based on the effective data scale | LocDPSGD and LocDPCuttingPlane · Private geometric median | excess risk | Helped |
Limitations
- The pure-DP inverse smooth sensitivity algorithm is computationally inefficient (exponential time).
- The cutting-plane fine-tuning gives only approximate (ε,δ)-DP because its privacy analysis requires θ* in Θ0, which is a data-dependent condition.
- Results assume a bounded a priori ball of radius R and a lower bound r on the quantile radius; logarithmic dependence on R and 1/r remains.
Experimental setup
Metrics: excess risk F(theta)/F(theta*)
Baselines: DP-GD DP-SGD LocDPSGD
Builds on: DP-GD inverse smooth sensitivity mechanism AboveThreshold
Closest papers by meaning
- Private Geometric Median in Nearly-Linear Time (NeurIPS 2025 · similarity 0.91)
- Optimal Coresets for Low-Dimensional Geometric Median (ICML 2024 · similarity 0.85)
- On the Price of Differential Privacy for Hierarchical Clustering (ICLR 2025 · similarity 0.84)
- Online Differentially Private Consistent Clustering (NeurIPS 2026 · similarity 0.84)
- Differentially Private Equivalence Testing for Continuous Distributions and Applications (NeurIPS 2024 · similarity 0.84)
- Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization (ICML 2025 · similarity 0.83)
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.