Private Geometric Median
Not on the map. Why?
Abstract (arXiv)
In this paper, we study differentially private (DP) algorithms for computing the geometric median (GM) of a dataset: Given n points, x1,dots,xn in ℝd, the goal is to find a point θ that minimizes the sum of the Euclidean distances to these points, i.e., sumi=1n |θ - xi|2. Off-the-shelf methods, such as DP-GD, require strong a priori knowledge locating the data within a ball of radius R, and the excess risk of the algorithm depends linearly on R. In this paper, we ask: can we design an efficient and private algorithm with an excess error guarantee that scales with the (unknown) radius containing the majority of the datapoints? Our main contribution is a pair of polynomial-time DP algorithms for the task of private GM with an excess error guarantee that scales with the effective diameter of the datapoints. Additionally, we propose an inefficient algorithm based on the inverse smooth sensitivity mechanism, which satisfies the more restrictive notion of pure DP. We complement our results with a lower bound and demonstrate the optimality of our polynomial-time algorithms in terms of sample complexity.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 28 of its 52 references that are in the map. First posted on arXiv 11 Jun 2024.
Builds on
28 of 52 references.
References · 28
- 2016Deep Learning with Differential Privacycited by 2,682
- 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
- 2019Robust Aggregation for Federated Learningcited by 314
- 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
- 2016Concentrated Differential Privacycited by 139
- 2018Privately Learning High-Dimensional Distributionscited by 103
- 2018Private PAC learning implies finite Littlestone dimensioncited by 73
- 2022Byzantine Machine Learning Made Easy by Resilient Averaging of Momentumscited by 63
- 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 62
- 2015Differentially Private Release and Learning of Threshold Functionscited by 58
- 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
- 2021Public Data-Assisted Mirror Descent for Private Model Trainingcited by 49
16 more
- 2016Geometric Median in Nearly Linear Timecited by 38
- 2023Why Is Public Pretraining Necessary for Private Model Training?cited by 36
- 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
- 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 30
- 2021Differentially private inference via noisy optimizationcited by 27
- 2016Locating a Small Cluster Privatelycited by 20
- 2021Robust Training in High Dimensions via Block Coordinate Geometric Median Descentcited by 20
- 2017Clustering Algorithms for the Centralized and Local Modelscited by 18
- 2021Differentially-Private Clustering of Easy Instancescited by 17
- 2022Differentially Private Generalized Linear Models Revisitedcited by 17
- 2022~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimizationcited by 16
- 2023Faster Differentially Private Convex Optimization via Second-Order Methodscited by 13
- 2019Efficient Private Algorithms for Learning Large-Margin Halfspacescited by 12
- 2021On the Strategyproofness of the Geometric Mediancited by 9
- 2022Differentially Private Learning with Margin Guaranteescited by 7
- 2023Differentially Private Medians and Interior Points for Non-Pathological Datacited by 2
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.