Private Geometric Median in Nearly-Linear Time
Not on the map. Why?
Abstract (arXiv)
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 sumi ∈ [n] |· - xi|, given a dataset D := xii ∈ [n] subset ℝd. Their algorithm requires n gtrsim √ d · frac 1 αvarepsilon 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 √ d · frac 1 αε samples, but in time widetildeO(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.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 33 of its 50 references that are in the map. First posted on arXiv 26 May 2025.
Builds on
33 of 50 references.
References · 33
- 2016Deep Learning with Differential Privacycited by 2,728
- 2017Renyi Differential Privacycited by 650
- 2014Convex Optimization: Algorithms and Complexitycited by 575
- 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
- 2019Differentially Private Learning with Adaptive Clippingcited by 220
- 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
- 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
- 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
- 2017Finite Sample Differentially Private Confidence Intervalscited by 104
- 2018Privately Learning High-Dimensional Distributionscited by 104
- 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
- 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
21 more
- 2019Private Hypothesis Selectioncited by 60
- 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
- 2022Private Convex Optimization via Exponential Mechanismcited by 49
- 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
- 2016Geometric Median in Nearly Linear Timecited by 39
- 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
- 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
- 2024More Asymmetry Yields Faster Matrix Multiplicationcited by 27
- 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
- 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
- 2016Locating a Small Cluster Privatelycited by 20
- 2020Differentially Private Confidence Intervalscited by 20
- 2021Differentially-Private Clustering of Easy Instancescited by 17
- 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
- 2022Private Convex Optimization in General Normscited by 13
- 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
- 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
- 2022Differentially Private Online-to-Batch for Smooth Lossescited by 5
- 2024On Differentially Private Linear Algebracited by 4
- 2024Private Geometric Mediancited by 3
- 2024Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batchescited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.