Private Geometric Median in Nearly-Linear Time
Authors: Syamantak Kumar
Daogao Liu
Kevin Tian
Chutong Yang
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Geometric Median
Stochastic Convex Optimization
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We give a nearly-linear time algorithm for privately computing the geometric median, addressing the main open question of Haghifam et al (NeurIPS '24).

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 $(\epsilon, \delta)$-differentially private algorithm obtaining an $\alpha$-multiplicative approximation to the geometric median objective, $\frac 1 n \sum_{i \in [n]} \|\cdot - \mathbf{x}_i\|$, given a dataset $D$ of $x_i$ for $i \in [n]$. Their algorithm requires $n \gtrsim \sqrt d \cdot \frac 1 {\alpha\epsilon}$ 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 \sqrt d \cdot \frac 1 {\alpha\epsilon}$ samples, but in time $\widetilde{O}(nd + \frac d {\alpha^2})$. Our runtime is nearly-linear, plus the cost of the cheapest non-private first-order method due to [CLMPS16]. To achieve our results, we use subsampling and geometric aggregation tools inspired by FriendlyCore [TCKMS22] 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.

Private Geometric Median in Nearly-Linear Time
Syamantak Kumar University of Texas at Austin syamantak@utexas. edu
Daogao Liu Google Research 1 iudaogao@gmail.com
Kevin Tian
Chutong Yang University Texas at Austin cyang988cs. utwxaseee.....m edu
University of Texas at Austin kjtiandcs utexas edu
Abstract
Estimating the geometric median of dataset is robust counterpart to mean estima- tion, and is fundamental problem in computational geometry. Recently, [HSU24) gave (c, d)ddifferentially private algorithm obtaining a-multiplicative ap- proximation to the geometric median objective, 1 [iejo ||,-,, given dataset
== {x, hien C Rd. Their algorithm requires n Z Vd. 1 samples, which they prove is information-theoretii
ae
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 improved algorithm that obtains the approximation quality, also using Z Vd 1. samples, but in time Onnd+ + - ). 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 speed up the "warm start" component of the [HSU24] algorithm, combined with a careful custom analysis of DP-SGD's sensitivity for the geometrie median objective.
Introduction
The geometric median problem, a.k.a. the Fermat- Weber problem, one of the oldest problems in computational geometry. In this problem, find point x, Rd that minimizes the average Euclidean distance points the dataset:
given dataset DD {xx (ie)) C Rd, and our goal
x, E arg min fx(x), where (x(x) = XERa
Σ EE|D]
x
This problem has received widespread interest due to its applications high-dimensional statistics. In particular, the geometric median of dataset D enjoys robustness properties that the mean (i.e., Eie(s) X,, the minimizer of Eve(n) ||x x; )2)) does not. For example, it is known (ef. Lemma 4) that if greater than half of 'D lies within a distance of some X E Rd then the geometric median lies within O(r) of Thus, the geometric median provides strong estimation guarantees even when D contains outliers. This is in contrast to simpler estimators such as the mean, which can be arbitrarily corrupted by single outlier. As result, studying the properties and computational aspects of the geometric median has long history, see e.g., [Web29, IR91] for some famous examples.
We provide improved algorithms for estimating (1) subject - privacy (DP, Defini- tion 1), the de facto notion of provable privacy in modern machine learning. Privately computing the geometric median naturally fits into a recent line of work on designing DP algorithms in the presence
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

of outliers. To explain the challenge of such problems, the definition of DP implies that privacy must hold for worst-case datasets. This stringent definition affords DP a variety of desirable properties, most notably composition of private mechanisms (ef. [DR14] 14], Section 3.5). However, it also begets challenges: for example, estimating the empirical mean of 'D subject to (c, 5)-DP necessarily results in error scaling < R, the diameter of the dataset (cf. Section 5, [BST14]]. Moreaver, the worst-case nature of DP is at odds with typical average-case machine learning settings, where most (or all) of D is drawn from distribution that we wish to learn about. From an algorithm design standpoint, the question follows: how do we design methods with privacy guarantees for worst-case data, but also with improved utility guarantees for (mostly) average-case data?
Such questions have been successfully addressed for various statistical problems, e.g., parameter esti- mation [BD14, KV17, BKSW19, DFM 20, BDKU20, BGS 21, AL22, LKJO22, KDH23, BHS23],
clustering [NRS07, NSV16, CKM+21, T2K+ and more. However, existing approaches for (1) (even non-privately) are based on iterative optimization methods, as the geometric median does not admit a simple, closed-form solution. Much of the DP optimization toolkit is exactly plagued by the aforementioned "worst-case sensitivity" issues, e.g., lower bounds for general stochastic optimization problems again scale with the domain size. This is troubling in the context of (I), because a major appeal of the geometric median is its robustness: its enror should not be significantly affected by any small subset of the data. Privately estimating the geometric median thus poses an interesting technical challenge, beyond its potential appeal subroutine in downstream robust algorithms.
To explain the distinction between worst-case and average-case error rates in the context of (1), we introduce the following helpful notation: for all quantiles E [0, 1). we let
,(rr == arg min
||x x11 2 on where x, == arg min (E(m)
1
x
xill
200
xER
n2
E [m]
(2)
11
||x: x,
Sr
and ||x: xx1=-
0
otherwise
when D D= (xx]]t) C Rd clear from context. In other words, (r(r) the smallest radius describing a ball around the geometric median x, containing at least 7n points in D. We also use R to denote an a priori overall domain size bound, where we are guaranteed that c B (R). Note that in general, is possible for, e.g., (0.9) < R 10% of consists of outliers with atypical norms. Due to the robust nature of the geometric median (i.e., the aforementioned Lemma 4), a natural target is estimation error scaling with the "effective radius" (() for some quantile T E (0.5. 1). This is much stronger guarantee than the error rates x R that typical DP optimization methods give.
Because a simple argument (Lemma 3) shows (+) = O(fD(x.))) for all 7 < 1, in this introduction our goal is to approximate the minimizer of (1) to additive error (x.) for some a E (0, 1), i.e., to give a-multiplicative error guarantees on optimizing fp.' Again, datasets with outliers may have fo (x.) < R, so this is beyond the reach of naively applying DP optimization methods.
In recent exciting work, [HSU24] bypassed this obstacle and obtained such private multiplicative approximations to the geometric median, and with near-optimal sample complexity. Assuming that DD has size n Z Vd- L.² ae [HSU24] gave two algorithms for estimating (1) to a-multiplicative error (cf. Appendix A). They also proved matching lower bound, showing this many samples is information- theoretically necessary." From both theoretical and practical perspective, the main outstanding question left by [HSU24] is computational efficiency: in particular, the [HSU24] algorithms ran in time Önn2d + n²² ) Ó(n2d nd d4.372). This leaves significant gap between algorithms for privately solving (1), and their counterparts in the non- non-private setting, where [CLM* 16) showed that (I) could be approximated to a-multiplicative error in nearly-linear time Ö(min(nd, (nd, 2 )).
'Our results (and those of [HSU24) in fact give stronger additive error bounds of (x(()) for any E (0.5, 1). II this introduction only, we use Ö, S. 2 to hide polylogarithmic factors in problem parameters, i.e., d, _. 1. 1 and R f. where D C (R))) and r S n (0.9), Our formal thcorem statements explicitly state all dependences. *. 3.
IIttuitively, we require a Rs 1/2 to obtain nontrivial estimation when D consists of i.i.d. Gaussian data (as typical radius is z Vdl, matching known lower bounds of z for Gaussian mean estimation [KLSU19].

---

1.1 Our results
Our main contribution is a faster algorithm for privately approximating (1) to a-multiplicative error.
Theorem 1 (informal, see Theorem 4). Let D = (x)) C (R) for R 0, 0 < r.(0.9), and e, E [0, There is an (e, () algorithm that returns & such that with probability 2 1 8, fD( & (1 + aDf(x)( assuming n 2 va The algorithm runs in time Ö(nd + 2z)
To briefly explain Theorem I's statement, it uses a priori knowledge of 0 < < R such that R upper bounds the domain size of D, and lower bounds the "effective radius" ,(0.9), However, its runtime only depends polylogarithmically on the aspect ratio R. rather than polynomially (as naive DP optimization methods would); we also remark that our sample complexity is independent of 7.
The runtime of Theorem is nearly-linear when 2 d (e.g.. if vd. - 2 2), but more generally it does incur an additive overhead of 2 This overhead matches the fastest non- non-private first-order method for approximating (1) to a-multiplicative error, due to [CLM+ 16]. We note that [CLM*16 16] also gave a second-order interior- interior-point method, that non-privately solves (1) in time (nd)). i.e. with polylogarithmic dependence a We leave removing this additive runtime term in the DP setting, or proving this is impossible in concrete query models, as a challenging question for future work.
Our algorithm follows a roadmap by [HSU24), who split their algorithm into two phases: initial "warm start" phase that computes an 0(1) m(t-pippiplicative approximation of the geometric median, and a secondary "boosting" phase that uses iterative methods to improve the warm start to multiplicative approximation. The warm start improves the domain size of the boosting phase to scale with the effective radius. However, both the warm start and the boosting phases of [HSU24) required superlinear Re n²d time. Our improvement to the warm start phase of the [HSU24] is quite simple, and may be of independent interest, we provide self-contained statement here.
Theorem 2 (informal, see Theorem 3). Let D = (xi) C CB for R > 0, 0 <r00 (0.9)) and (c, 5) E [0, 1].. There is an (e, DP algorithm that returns & such that with probability 2 1 - 8, (x) = (x,)).))) assuming 2 vdd The algorithm runs in time Ö(nd).
e
1.2 Our techniques
As discussed previously, our algorithm employs a similar framework as [HSU24). It is convenient to further split the warm start phase of the algorithm into two parts: finding an estimate i of the effective radius of D. and finding an approximate centerpoint at distance O(F) from the geometric median x..
Radius estimation. Our radius estimation algorithm is almost identical to that in [HSU24), Section 2.1, which uses the sparse vector technique (ef. Lemma 2) detect the first time estimate is 3 of 'D at a distance of A A. The estimate ý is geometrically updated over grid of size ( B )). Naïvely implemented, this strategy takes Z n²d time due to the need for pairwise distance comparisons (ef. Appendix A); even if dimesionality reduction techniques are used, this step appears to require 2(n²) time. We make a simple observation that a random sample of Ri log(3) ( points from is enough to determine whether a given point has >> f neighbors, or < 7
such that most points have 2 4
for appropriate (constant) quantile thresholds B, y, which is enough to obtain an Ö(nd) runtime.
Centerpoint estimation. Our centerpoint estimation step departs from [HSU24], Section 2.2, who analyzed a custom variant of DP gradient descent with crometrically-decyyii
step sizes. We make the simple observation that directly applying the FriendlyCore algorithm of [TCK +2] yields the same result. However, the standard implementation of FriendlyCore again uses (2n2) time to estimate weights for each data point. We show that FriendlyCore can be sped up to in ((nd) time (independently of E using subsampled weights. Our privacy proof is subtle, and based on an argument (Lemma 1) that couples our subsampled algorithm to an idealized algorithm that never fails to be private. We use this to account for the privacy loss due to the failure of our subsampling, ie., if the estimates are inaccurate. We note that the [HSU24] algorithm for this step already ran in nearly-linear x nd log( ( time, so we obtain an asymptotic improvement only if is large.
Boosting. The most technically novel part of our algorithm is in the boosting phase, which takes as input radius and centerpoint estimate from the previous steps, and outputs an a-multiplicative
3

---

approximation to (1). Like [HSU24], we use iterative methods to implement this phase. However, major bottleneck faster algorithm the lack of a mearly-linead time DP solver for non-smooth empirical risk minimization (ERM) problems. Indeed, such O(1)-pass optimizers are known only when the objective is convex and sufficiently smooth [FKT20], or n 2 de samples are taken [CJJ 23). This is an issue, because while computing the geometric median (1) is a convex ERM problem, is non-smooth, and multiplicative guarantees are possible even with n R vd samples.
[CJ]+23).
We give custom analysis of DP-SGD, specifically catered to the (non-smooth) ERM objective (1). Our main contribution is tighter sensitivity analysis of DP-SGD's s iterates, leveraging the structure of the geometric median. To motivate this observation, consider coupled algorithms with iterates z, z', both taking gradient steps with respect to the subsampled function || x; || for some dataset element X; D. A simple calculation (7) shows these gradients are unit vectors u, u', in the directions of z X; and
x; respectively. It is not hard to formalize (Lemma 11) that updating z f z nju and z' <- z' rju' is always contractive, unless 2, z' were both already very close to x; (and hence, each other) to begin with. We use this structural result to inductively control DP-SGD's ' sensitivity, which lets us leverage prior reduction from private optimization to stable optimization [FKT20].
Our result is the first we are aware of that obtains a mearly-lineat runtime for DP-SGD on a structured non-smooth problem. We were inspired by [ALT24], who also gave faster runtimes for (smooth) DP optimization problems with outliers under further assumptions on the objective. We hope that our work motivates future DP optimization methods that harness problem structure for improved rates.
1.3 Related work
Differentially private convex optimization. DP convex optimization has been studied extensively for over a decade [CM08, KST12, BST14, KJ16, BFGT20, FKT20, BGN21, GLL22, GLL+ and inspired the influential DP-SGD algorithm widely adopted in deep learning [ACG+16 16). In the classic setting, where functions are assumed to be Lipschitz and defined over a convex do- main of diameter R, optimal rates have been achieved with linear dependence on R [BFTGT19]. Recent years have seen significant advancements in the gradient complexity of DP stochastic con- vex optimization [FKT20, AFKT21, KLL21, ZTC22, CJJ+23, CCGT24]. Despite these efforts, a nearly-linear gradient complexity has only been established for sufficiently smooth functions [FKT20, ZTC22, CCGT24] and for non-smooth functions [CJJ+23] when vn 2 d is satisfied. Finally, in a related direction, [KMM [M] study private convex hull estimation and it remains an interesting future direction to see if our techniques apply to their setting. As noted in their work, the convex hull can be a very unstable function of the dataset, whereas multiplicative approximations to the geometric median are not affected drastically by a single datapoint (e.g., Lemma 4).
Differential privacy with average-case data. Adapting noise to the inherent properties of data, rather than catering to worst-case scenarios, is critical for making differential privacy practical in real- world applications. Several important approaches have emerged this direction: smooth sensitivity frameworks [NRS07] that refine local sensitivity to make it private; instance optimality techniques (AD20) with tailored guarantees for specific datasets; dmethods with improved performance under distributional assumptions such sub-Gaussian or heavy-tailed i.i.d. data [CWZ21, AL23, ALT24]; and data-dependent sensitivity computations that adapt during algorithm exccution [ATMR21]. These approaches collectively represent the frontier in balancing privacy and utility beyond worst-case analyses. We view our work as another contribution towards this broader program.
2 Preliminaries
Throughout, vectors are denoted in lowercase boldface, and the all-zeroes and all-ones vectors in dimension d are respectively O₂ and 1a. We use ||-|| to denote the Euclidean (E2) norm of a vector. We use [d] to denote {i N 1 S i i d]. We use (H, == fx Rd ||x Aa|| S r} to denote the Fuclidean ball of radius > 0 around μ E Rd: when fa is unspecified, then μ 0. by default. For compact IC C Rd. we use (x) to denote the Fuclidean projection arg minyek ||x -yl
We let Ig denote the 0-1 indicator random variable of an event E. For two densities n.v on the same sample space Q and a > 1, we define the a-Rényi divergence (a(p)))) == T log(] (( We use N oaI)) to denote the multivariate normal distribution
I

---

with mean f RR and covariance L'L where La is the d x d identity. We let Laplace(A) be the Laplace distribution with scale parameter O, whose density x exp(-#). We let Unif(S) denote the uniform distribution over a set S, and Bern(p) denote the Bernoulli distribution taking on values {0, } with mean p [0, 1]. We refer product distribution consisting of i.i.d. copies of base distribution 'D by Dok We also the bounded Laplace distribution with parameters X, 7 2 denoted Laladed r), i.e., the distribution of ~ Laplace(A) conditioned on |X] S T.
Differential privacy. Let X' be some domain, and let D E A be a dataset consisting of n elements from X. We say datasets D, D' E X" are neighboring if their symmetric difference has size 1, i.c., they differ in single element. We use the following definition of differential privacy in this paper.
Definition (Differential privacy). Let (c, E [0, 1]2 We say that a randomized algorithm A: X" Ω satisfies (c, -iffferrrtti privacy (or, is (c, 8)-DP) for all events & C S and for all neighboring datasets D, DD' E X",, Pr [A(() E E] S exp(e) Pr ( E
DP algorithms satisfy basic composition (Theorem B.1, [DR14)), i.e., A1 X - U2 is ((,,)) DP and A2 : X x S2 - S22 is ((2, 62)-DP, then their composition is (4 + 62, 51 + DDD We next state the Gaussian mechanism. Recall that if X + R* is vector-valued function of dataset, we say v has sensitivity A if for all neighboring D' X". l|v(D)) v(D') S A.
Fact 1 (Theorem A.1, [DR14)). Let V x + IR* have sensitivity A, and let (c, E [0, 1|2. Then, drawing sample from N (v()), I4) is 6D for any 24 ()
We also require the bounded Laplace mechanism, which is known to give the following guarantee. Fact 2 (Lemmaa 9, [ALT24]). Let X + R have sensitivity A. and let (e,6) E [0, 1|2. Then, drawing& & BoundedLaplace( è -) and outputting sD) + E is (e. for any è log(
Fact is proven in [ALT24] using a coupling argument, using the fact that BoundedLaplace( and Laplace(A) (A) result in the same sample except with some probability. We appeal to this technique several times in Section 3, so we explicitly state it here for convenience (with a proof in Appendix B).
Lemma 1. For (e, 8) E [0, 1]2, A: X + S be an (e, DDD algorithm, and let A be an algorithm such that on any input D X", we have that the total variation distance between A(D) and A(D)
at most 8. Then, A an (r, 5 + DDP algorithm.
We next recall the following well-known result on detecting the first large element in a stream.
Lemma 2 (Theorems 3.23, 3.24, [DR14]). Threshold (Algorithm 4) is (e, O)-DP. Moreover, halts at time k E [T+ + 1) such that
for E (0, 1), les a = 8A log( ) with probability 2 1 7: (D) < T + or for all <, k. and qu (D)
and DD E X",
or k- = T 1.
Geometric median. In the rest of the paper, for R > 0, we fix dataset D = (x: (e(N) C CB)(R). ie., with domain X (RR) Our goal is to approximate the geometric median of D, i.e.,
x, (D) == arg min fx(x), where fo(x) = 1 xERd
|
x;
n iE(m)
is the average Euclidean distance to the dataset. Following e.g., [CLM+16 16. HSU24], we also define the quantile radii associated with our dataset D centered at x E Rd by
(T) (D: x = arg min r20
Σ kE(m)
Upx 1 2 rn J for all 7 E [0,1]. 1].
(4)
When x is unspecified, by default x = x. (D). In our utility analysis we will often suppress the dependence on DD in x., p!T), etc., as the dataset of interest will not change. In the privacy analysis, specify the dependence of these functions the dataset explicitly when comparing algorithms run on neighboring datasets. Finally, we include two helper results from prior work.
'In principle, e can be larger than 1. However, in this paper, sample complexities are unaffected up to constants for any < 2 1 if we simply obtain (1, 8)8) guarantees rather than (c, -D guarantees. which are only stronger. Thus state all results for c E [0, for convenience, which simplifies some bounds.
5

---

Lemma 3. Let D == (xs)ee()) C. R Then, fo (x.) 2 (1-T)r()) for all T E [0, 1]. Lemma (Lemma 24, [CLM* 16]). Let D = (Ei C. IR and let - [n] have |S| < 2. Then,
2n 2|5]
|x, x|| -
max ||x; x||, for all x E R
n 2|5|
igS
Constant-Factor Approximation
In this section, we give our first result: a fast algorithm for computing an aappaaporoinmtaion the geometric median. We first show how to estimate quantile radii up to constant factors in nearly-linear time using subsampled scores, improving Section 2.1 of [HSU24]. We then adapt weighted variant of FriendlyCore to give simple algorithm for approximate centerpoint computation, improving Section 2.2 of [HSU24] for large aspect ratios. Proofs from this section are deferred Appendix C.
We first present our radius estimation algorithm.
Algorithm 1 FastRadius(D,r,.ll
Input: D E (R)"", 0 < <r R, (c E [0, 1|2
1: (T, k, r) t ([log2( (.). log 4F) 0,0.775)
2: ++ 7 1/trrssh for 1/thresh ~ Laplace
3: for I E [T' do
4: for i E [n] do
s(i)) + (nif([n])@*
5:
6:
N1 + Ejeso I 1x--x,11rr
for rt +- r 2t-1
7:
end for
8:
9i n Eiein N(O0)
1
9:
V1 ~ Laplace 12)
if q: + 2 then
11: Return: f
end if
13: end for
Return: R
Algorithm is an instance of Above AboveThreshold with A = 3, where the queries are given on Line 8. However, our queries have random sensitivities depending on the subsampling in Line 5. Nonetheless, Chernoff bounds control this sensitivity with high probability, which yields privacy via Lemma 2.
Lemma 5. Algorithm is (e, 6)-DP.
The proof Lemma is a simple combination of Fact 4, Lemma 1, and Lemma Next, we state utility bound for Algorithm 1, whose proof is essentially identical to the proof in [HSU24], after applying Chernoff bounds to ensure our estimated counts are accurate.
Lemma 6. Algorithm 1 runs in time (nd log( #) log(log( ())) Moreover, if r < 4y. and 2400 log( 4T ), with probability 1-6, 5, Algorithm outputs satisfying (,
4 (0.9)
In summary, Lemmas and 6 show that we can privately estimate & satisfying (0.75) < (0.9)
in nearly-lineat time. The upper bound implies (with Lemma 3) that á (x.. on the other hand, the lower bound will be critically used in our centerpoint estimation procedure, Algorithm 2.
Algorithm 2 is simplification of the FriendlyCore algorithm of [TCK+22], that outputs noisy weighted average of the dataset, where the weights [p: (e(x)) linearly interpolate estimated scores fa E (0.5k, 0.75k] into the range [0, 1), sending fi 2 0.75k to 1, and f, < 0.5% to 0. We first make some basic observations about the points that contribute positively to the weighted combination
Lemma 7. Assume that f 2 ,(077)) the context of Algorithm With probability 2 18 every i [n] that is assigned p: 0 in Algorithm 2 satisfies ||x; x. |l 3f, and Z > 0.6n.

---

log 12 0 Algorithm 2 FastCenter(D, (,
Input: D E (R))", f E RRs. () E 10
1: k +- 600 log( 18m
2: for E [n] do
3: S +- Uni
4: Ji - Ejesto |xx,x,
5: pj + minn(max( (0,
[ 4-0.3k
),
0.25k
6: end for
7: Z + Eie(n) P:
8: { BoundedLaplace?
log(? (4 ))
9: if Z + 24 log( 21) 0.55m then
10: Return: 0g
11: end if
12: & 3 EiEnn
13: & ~~ (NO2 I'),,, for o + 1600#
Return: +
We remark that to make Lemma 7 compatible with the output guarantee of Lemma 6, it is enough to pass in f + 4f where f the output Algorithm 1. By inspection, this only changes the definition of the constant in Theorem 3, the main export of this section.
Lemma 7 constitutes most of our utility analysis, as all contributing points x are O()) away from x., our final desired error. We next note that whenever the algorithm does not return on Line 10, all surviving points lie in a ball of diameter Of),, under high-probability event over our subsampling. Importantly, this holds independently of any assumption on (e.g., we do not require (0075))).
Lemma 8. Suppose that it is the case that in the context of Algorithm 2, we have
f S 0.45k = fi - 0.5k, and f < 0.55k = fs S 0.6k.
(5)
for all E [n]. If Z > 0.55n, there exists some x E Rd such that {x; P; > Oheem S Bxx, 4f). Moreover. the event (5) occurs with probability 2 1
We are now ready to prove a privacy bound on Algorithm 2. Our proof follows the original privacy analysis of FriendlyCore [TCK+*22] but accounts for the failure of the "accurate subsampling" event (5) by coupling to an algorithm that always ensures (5), and then applying Lemma
Lemma 9. nn n 2 20, Algorithm is (e, D)-..
Combining our developments gives our constant-factor approximation to the geometric median.
Theorem 3. Let D (xilie(n)) C (R) R > O. ler 0 < (r(9)) and let (c, [0, 1]..
Suppose that n 2 C. (vd. log(2) + log( (ooi://
). for a sufficiently large constant C. There is an (D algorithm that returns (š, such that with probability 1- following notation (3),
fo(x)= S (400" + (x,, $ 4r
(6)
for a universal constant C², Moreover, (D) - < C'F. The algorithm runs time
*||
R
log( B 8
nd nd log
log
We remark that Theorem 3 actually comes with the slightly stronger guarantee that we obtain the optimal value for the geometric median objective fD, up to an additive error scaling as (0.)). In general, while (0.9) = (x (D))) always holds (Lemma 3). is possible that (0.9) (D) if small fraction of outliers contributes significantly to fD- We also note that for datasets where we have more a priori information on the number of outliers we expect to see, we can adjust the quantile 0.9 in Theorem 3 to be any quantile > 0.5 by appropriately adjusting constants.
7

---

4 Boosting Approximations via Stable DP-SGD
In this section, we give a DP algorithm that efficiently minimizes the geometric median objective (3) over a domain B f), given a dataset D == [E))) In our final application to the geometric median problem. the optimization domain (i.e.. the parameters x E R and f R20) will be privately estimated using Theorem 3, such that with high probability f = ((f)(x(())) and ||x (D)Il S f. In the meantime, we treat the domain (x, f) as public input here.
Our strategy is to use localization framework given by [FKT20], which gives query-efficient reduction from private DP-SGD to stable DP-SGD executed in phases. Observe that outputting"
||
(z)
z
X;
for Unif([n) is unbiased for a subgradient of fo (z), leading to the following Algorithm 3.
Algorithm 3 StableDDSSGDDD
Input: D = [xi]ve()) C R", (x, E Rd x R20, P (0.1 0, 2 -1 - n for KEN
m + -3( log()))
2: for k E [K] do
(T(K), (8), (())) + (2 (T' (T' 1), 1,,,, 3-k (2m++)))
3:
vp
4: i (k)
then
5:
(z) K(R)) (x, Bd f))
6: else
7:
(z)
(k) k(()) t (* 1) Bd (x(()) v /dlog( 1K
8 )))
8:
end if
9:
for
0 S (K)) do
(N)
(4) -x; for i (nif((n))
10:
gt
+ 1 -xil
(k)
+ II Xx (2 (k) - (1gg
(k))
11:
2+1
12:
end
for
13:
((k)
Trrs Eosrerio 26 (1)
14: ((h) N(a,, (I(
15: (k)) + (k) + (())
16: end for
17: Return: {KK)
Remark 1. Several steps in Algorithmm 3 are used only in the worst-case utility proof, and do not affect privacy. Practical optimizations can be made while preserving privacy guarantees, e.g., removing projections onto the changing domains K.R) rather than K()), which is not used in the privacy proof.
One optimization we found useful in our experiments (described in Section 5) replacing the random sampling on Line 10 with deterministic passes through the dataset in fixed order. By doing so, we know the total number of accesses of any single element is S m m= ["' (rather than the high- probability estimate in Lemma 10 for the randomized variant in Algorithm 3). This lets tighten the noise level g(k) by a fairly significant constant factor, resulting in improved empirical performance.
We provide a privacy bound on Algorithm in Appendix D.I, and utility bound in Appendix D.2. Our utility proof is fairly standard, and makes small modifications to the original localization analysis in [FKT20] to obtain a high-probsn boobbbbbbbblity error guarantee using martingale arguments.
Our main technical novelty lies in our privacy proof, which is unconventional as it requires showing stability of DP-SGD on a non-smooth function (3). This contrasts with [FKT20], which assumed smoothness to achieve fast runtimes. Our main observation to this end is in Lemma 11 and Corollary I, (R)
which show Line 11 implemented with shared x, but different starting z, (z. y, is contractive,
By default, if Xi. let (7) evaluate to Oa. which is valid subgradient by first-order optimality.
8

---

unless x.()) .(z, were close. This yields a refined bound on the stability of each phase, allowing us to use the [FKT20] reduction for DP. Combining these pieces yields our following main result.
Theorem 4. Let D = (x, [x)) C (B) R > O, let O < I 4r (D), and let (a,, c, 6) E ((
[0, 113. Suppose that n 2 C. ave log2 1 gar))) )), for a sufficiently large constant C. There is 5. following notation (3),
(
an (e, 8D- algorithm that returns such that with probability fo & (1 +1+a0 (D). The algorithm runs in time
(
R
d dllo(( (1)g(=))
ade )
+ d log
log a ( 8
))
0 nd log
log
a2
Experiments
We present empirical evidence supporting the efficacy of our techniques." 6 Algorithm (the radius estimation step of Section 3) and Algorithm 3, to evaluate how subsampled estimates and DP-SGD respectively improve the performance of our algorithm.
We conduct experiments on
We do not present experiments on Algorithm 2, as our current analysis results in loose constants, which in our preliminary experimentation significantly impacted the performance of Algorithm 2 in practice. We leave optimizing the performance of this step as an important step for future work. Our Algorithm and Section 2.2 of [HSU24] had essentially the same theoretical guarantees, so we find it in line with the conceptual contribution of this work to evaluate the other two components.
We use two types of synthetic datasets with outliers, described in Appendix E: GaussianCluster (used in [HSU24] as well), and HeavyTaile Tailed (a multivariate Student's distribution).
Subsampling. We performed experiments to show the benefit of subsampling in FastRadius (Algo- rithm 1) over RadiusFinder (Algorithm from [HSU24]) for differentially private estimation of the quantile radius, which is the first step in differentially private estimation of the geometric median. Across a variety of settings of n. d, and aspect ratios in our Gaussian Cluster experiment and degrees of freedom in our Heavy Tailed, both Rast and RadiusFinder consistently resulted in estimates se 1.2-3x the true quantile radius, with FastRadius's estimates consistently about 10-20% worse. However, the average wall-clock time for our algorithm was roughly 30x faster, even d = 10. We present plots and experimental results for this evaluation in Appendix E.
1000,
Boosting, We also evaluate the performance of our boosting algorithm in Section 4, compared to the baseline method from [HSU24]. We in fact evaluate three methods: (1) the baseline method, DPGD (vanilla DP gradient descent), as described in Algorithms 3 and 6, [HSU24], but with an optimized step size selected through ablation studies (cf. Appendix E); (2) StableDPSGD, i.e., our Algorithm 3 implemented as written, and (3) FixedOrdeDDPSGD. variant of our Algorithm 3 with the last optimization described in Remark 1. calibrated our noise level DPSSOD to ensure fixed level of CDP via group privacy argument, where we use that each dataset element is deterministically accessed at most m = [ times in FixedOrderDPSGD with iterations.
n
We present here a representative experiment, deferring a more comprehensive set of experiments to Appendix E. Here, we vary n only, fixing all other parameters in a GaussianCluster dataset in R50 We report the performance of all three methods, plotting the passes over the dataset used by the excess error. Our error metric This is more reflective performance metric than the corresponding multiple of fD, as our algorithms achieve this bound (cf. discussion after Theorem 3), and fo 2 for our datasets due to outliers.
(fo(x) fo (x)), i.e., multiple of the "effective radius" used.
Throughout our experiments, we observed consistent trends to Figure 3, where our (optimized) algorithm DiXPOOD outperformed the baseline by an amount depending on n (with better performance for larger n),, and the unoptimized StableDPSGD achieved worse, but competitive, results. We remark that one limitation of our evaluation that DPGD gradient computations can be parallelized, which leads to wall-clock time savings; we discuss this point further in Appendix E.
*Our subsampling experiments were performed on a single Google Colab CPU, and our boosting experiments were performed on a personal Apple M4 with 16GB RAM.

---

Ducoila Ciutte SIGIAS, 100 N.-500
DusssarCkute crosd,,
DOCCS 1
10000
prasp
23
26.
273
15.3
36.
24
12.1
112
11.
15.0
10.5
13.
20.
(a) 100
(b) = 1000
(c) m
10000
Figure 1: Comparison of DPGD, StableDPSGD, and FixedOrderDPSGD across different datasets
over I850 All plots are averaged across 20 trials and standard deviations are reported as error bars.
Acknowledgments
We gratefully acknowledge NSF grants 2217069, 2019844, and DMS 2109155. We thank the Texas Advanced Computing Center (TACC) for computing resources used in this project.
10

---

References
[6CG+16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[AD20] Hital Asi and John C Duchi. Instance-opimaality in differential privacy via approximate inverse sensitivity mechanisms. Advances in neural information processing systems, 33:14106-14111 2020.
[ADV*25] 25] Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual -CAM Symposium on Discrete Algorithms, SODA 2025, pages 2005-2039, SIAM, 2025.
[AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in II geometry. In International Conference on Machine Learning, pages 393-403. PMLR, 2021.
[AL22]] Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning gaussians and beyond. In Conference on Learning Theory, pages 1075-1076. PMLR, 2022.
[AL23] Hilal Asi and Daogao Liu. User-level differentially private stochastic convex opti- mization: Efficient algorithms with optimal rates. arXiv preprint 2rX1v:2311.03797, 2023.
[ALT24] Hilal Asi, Daogao Liu, and Kevin Tian. Private stochastic convex optimization with heavy tails: Near-optimality from simple reductions. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024.
[ATMR21] Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Dif- ferentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:17455-17466, 2021.
[BD14] Rina Foygel Barber and John C Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arX1v:1412.4451, 2014.
[BDKU20] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan R. Ullman. Coinpress: Practical private mean and covariance estimation. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020.
[BFGT20] Raef Bassily, Vitaly Feldman, Cristóhal Guzmán, and Kunal Talwar. Stability of stochas- tic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 15:4381-43991 2020.
[BFTGT19] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32, 2019.
[BGN21] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. In Conference on Learning Theory, pages 474 499, PMLR, 2021.
BBG++21 Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthi- Covariance-aware private estimation without private covariance estimation. Advances in neural information processing systems, 34:7950-7964, 2021.
[BHS23] Gavin Brown, Samuel B. Hopkins, and Adam D. Smith. Fast, sample-efficient, affine- invariant private mean and covariance estimation for subgaussian distributions. In The Thirty Sixth Annual Conference on Learning Theory, COL.T volume 195 of Proceedings of Machine Learning Research, pages 5578-5579, PMLR, 2023.
11

---

[BKSW19] Mark Bun, Gautam Kamath, Thomas Steinke, and Steven Z Wu. Private hypothesis selection. Advances Neural Information Processing Systems, 32, 2019.
[BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, ex- tensions, and lower bounds. In Theory of Cryptography- 14th International Conference, TCC 2016-B, Proceedings, Part I, volume 9985 of Lecture Notes in Computer Science, pages 635 658, 2016.
[BST14) Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk mini- mization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 464 473. IEEE Computer Society, 2014.
[Bub15] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 833-4):2313357,22 2015.
[CCGT24] Christopher thoquette-Choo, Arun Ganesh, and Abhradeep Thakurta. Optimal rates for -mmothh dp-sco with single epoch and large batches. arXiv preprint arXiv:2406.022 0224440000276.. 2024.
[CJ]+23] Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, pages 2031-2058. IEEE, 2023.
[CKM+21] Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. Differentially-private clustering of easy instances. In Proceedings of the 38th In- ternational Conference on Machine Learning, ICML 2021, volume 139 of Proceedings of Machine Learning Research, pages 2049-2059. PMLR, 2021.
[CLM* 16] Michael B Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pages 9-21, 2016.
[CM08] Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression. Advances in neural information processing systems, 21, 2008
[CWZ21] Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825 28502220, 2021.
[DFM+20] Wenxin Du, Canyon Foot, Monica Moniot, Andrew Bray, and Adam Groce. Differen- tially private confidence intervals. arXiv preprint arXiv:2001.02285 2020.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3 44:2211-401) 2014.
[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, STOC 2020, pages 439-449, ACM, 2020.
[GLL22] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via ex- ponential mechanism. In Conference on Learning Theory, pages 1989, PMLR. 2022.
[G3L+23] Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, and Kevin Tian. Private convex optimization in general norms. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5068-5089, SIAM, 2023.
[HSU24] Mahdi Haghifam, Thomas Steinke, and Jonathan Ullman. Private geometric median. Advances in Neural Information Processing Systems, 37:46254 46293, 2024.
[KDH23] Rohith Kuditipudi, John Duchi, and Saminul Haque. A pretty fast algorithm for adaptive private mean estimation. In The Thirty Sixth Annual Conference on Learning Theory, pages 2511-2551. PMLR, 2023.
12

---

[KJ16] Shiva Prasad Kasiviswanathan and Hongxia Jin. Efficient private empirical risk min- imization for high-dimensional learning. In International Conference on Machine Learning, pages 488 497. PMLR, 2016.
[KLL21] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth erm and sco in subquadratic steps. Advances Neural Information Processing Systems, 34:4053-400 40644, 2021.
[KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan R. Ullman. Privately learning high-dimensional distributions. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, volume 99 of Proceedings of Machine Learning Research, pages 1853-1902. PMLR, 2019.
[5M Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, and Nitzan Tur. On differentially private linear algebra. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2362-2373 2025.
[KST12] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pages 25-1. JMLR Workshop and Conference Proceedings, 2012.
[KV17] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence inter- vals. arXiv preprint / 171100908, 2017.
[LKJO22] Xiyang Liu, Weihao Kong, Prateek Jain, and Sewoong Oh. DP-PCA: statistically optimal and differentially private PCA. In Advances Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022.
[LR91] Hendrik P. Lopuhaa and Peter J. Rousseuw. Breakdown points of affine equivariant estimators of multivariate location and covariance matrices. The Annals of Statistics, (9(1):229-248, 1991.
[Mir17] Ilya Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium, CSF 2017, pages 265.275. IEEE Computer Society, 2017.
[NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 75-84. ACM, 2007.
[NSV16] Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Locating small cluster privately. In Tova Milo and Wang- Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD- SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, pages 413-427. ACM, 2016.
Wang-Chiew
[Roc76] Tyrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM J. Control and Optimization, 14(5):877-898, 1976.
[TCK*22] Bliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Friend- lycore: Practical differentially private aggregation. In International Conference Machine Learning, pages 11828-21888 PMLR, 2022.
[Web29] Alfred Weber. Theory of the Location of Industries. University of Chicago Press, 1929.
[ZTC22] Qinzi Zhang, Hoang Tran, and Ashok Cutkosky. Differentially private online-to-batee batbatch for smooth losses. NeurlPS, 2022.
13

---

A Discussion of [HSU24] runtime
We give brief discussion of the runtime the [HSU24] algorithm in this section, as the claimed runtimes in the original paper do not match those described in Section 1. As the [HSU24] algorithm split into three parts (the first two of which correspond to the warm start phase and the third of which corresponds to the boosting phase), we discuss the runtime of each part separately.
Radius estimation. The radius estimation component of [HSU24] corresponds to Algorithm and Section 2. of the paper. The authors claim runtime of O log( Rt [) for this step due to need to do pairwise distance comparisons on dataset of size n, for (log( B)) times in total. However, believe the runtime should be O' ))), accounting for the ( cost of each comparison.
Centerpoint estimation. The centerpoint estimation component of [HSU24] corresponds to Algo- rithm 2 and Section 2.2 of the paper. We agree with the authors that this algorithm runs in time (nd log( )). and in particular, this step does not dominate any runtime asymptotically.
Boosting. The boosting component of [HSU24] corresponds to Algorithms 3 and 4 and Section of the paper. The authors provide two different boosting procedures (based on gradient descent and cutting- planne methods) and state their runtimes as ((n"d) and Ö(nd + df*),, where w < 2.372 is the current matrix multiplication exponent [ADV+25] 25]. We agree with the latter runtime analysis; however, believe there additive O(n*²²) term in the runtime of gradient descent. This follows by noting that Algorithm 3 uses x n22² iterations, each of which takes ((nd) time to implement.
B Deferred material from Section
In this appendix, we provide missing material from Section We begin by proving Lemmas and 3. Lemma 1. For 8) E [0, 1]2, A: X be an (c, ()DP algorithm,, and let be an algorithm such that on any input at most 8' Then, A an (r, + 48') DDP algorithm.
X", we have that the total variation distance between A(D) and A(D)
Proof. For neighboring datasets D, D', and any event & E Ω, we have that
Pr A(D)) El I Pr [A(D) E] + 5'
cxp (c) Pr (A(D') + S exp (E) A(D') E +
The first and last lines used the assumption between A and A, and the second used that AA is DP.
Lemma 3. Let D = (xx Rd. Then, fo (x.) 2 (1 () for all [0, 1].
Proof. This is immediate from the definition of Io and nonnegativity of each summand ||| x4||-
Next we provide pseudocode for Algorithm 4, analyzed in Lemma 2.
Algorithm 4 AboveTTreehhold (4, (4e
Input: D X", """,ssistiiiit--A queries (q: X RREeT T E R,
+- 7 Vthresh for V4theshh Laplace(225 24
2: for E [T) do
3:
~ Laplace 44
4: if (D) Vt 2 then
5: Output: t
6: Halt
7: else
8: Output: az <-
9: end if
10: end for
14

---

Finally, our developments in Section 4 use the notions of Rényi DP (RDP) and central DP (CDP), We provide a self-contained summary of the definitions and properties satisfied by RDP and CDP here, but refer the reader to [BS16, Mir17] 7] for a more detailed overview.
Definition (RDP and CDP), Let a 2 1, p 2 O. We say that a randomized algorithm A : X + Ω satisfies (a, P)-ényi differential privacy for, is (a,, p)-RDP) for all neighboring datasets D, D' E X".
Da(A(D))L((')) ap.
If this holds for all a 2 1, we say satisfies p-central differential privacy (or, p-CDP).
Fact 3 ([Mir17]). RDP and CDP satisfy the following properties.
1. (Composition); If A1 x 2 is (a,, P1)- and A 2 2 G2 is (a, p2) for any fixed choice of input from Q2 the composition of A2 and A₁ is (a, P1 + RDDP
2. (RDP to DP): If A is (a, p)-PDP it is also (ap + - log 3. DD for all E (0. 1).
3. (Gaussian mechanism): Let V X + R have sensitivity A. Then for any 0. drawing
a sample from (Vv(D),
2-2 -CDP.
Finally, we require the following standard bound on binomial concentration.
Fact (Chernoff bound). For all [ri]. let X; ~ Bern(p;) for some p. E [0, 1I. and let μ = Eieto Ps and i := ΣiE(n X;. Then, Pr[β > (1 + e)u] S exp(- + for all z 0, and
PrIp < - (1-c)p] S exp(p # for all E (0. 1).
C Deferred material from Section 3
In this appendix, we provide missing material from Section 3.
Lemma 5, Algorithm is (e, DD.
Proof. Fix neighboring datasets D' (RR"", and assume without loss that they differ in the nh entry. Observe that FastRadius (independently) uses randomness in two places: the random subsets in Line 5, and the Laplace noise added in the original Above Threshold algorithm in Lines and 9,
We next claim that in any iteration [T]. as long as the number of copies of the index n occurring in Use(n-1) (()) is at most 2k, then the sensitivity of the query di is at most 3. To see this, denoting by qt, de the random queries when Algorithm is on D, D' respectively, and similarly defining (Nr()) ((N!") ))E))) we observe that the sensitivity is controlled as follows:
9t- de S
1 Σ
(x(0))
(M
n
EE[m-1]
1 n
nnumber of copies of n occurring in
U s(i) vE[n-1]
+ +153.
k
The first line holds because the th (neighboring) point has N((m) S n. and (Nv(") 0: the second is because every U|x,~x/lisr, used in the computation of (²(() is coupled except when j = n is sampled.
Now, let A denote Algorithm 1, and let A denote variant that conditions on the randomly-sampled Usein-1j s(() containing most 2k copies of the index n, in all encountered iterations E [T]. By using Fact (with μ + k- السة e +- 1), due to our choice of k. Usein11 s. contains at most 24: copies of except with probability 5_. by union bound, the total variation distance between A and A most Moreover, A (e, O)-DP by using Lemma Thus, A is (c, 5)-D using Lemma 1.
L
Lemma 6. Algorithm runs in time (nd log( B) log(log( ()))). Moreover, ifr < (r((0.9) and
2100 log( 1T ), with probability 1 - ô, Algorithm I outputs satisfying (0.75))) 8 < (0.9
15

---

Proof. The first claim is immediate. To see the second, for all E [T] denote the "ideal" query by:
qi
U1x
SE|n] JEJn]
and recall Eg, q. Our first claim is that with probability 2 for all iterations E [2'] that Algorithm completes:
2' the following guarantees hold
q > 0.8n = qt > 0.79m, and qh < 0.75n = qi < 0.76n.
(8)
To see the first part of (8), can view n& random
of Bernoulli variables with mean nat 0.8n² > 20000 log( _ Fact 4 with 86 yields the claim in iteration t with probability
27. Similarly, the second part of (8) follows by using Fact 4 with μ < 0.7n² and (1 + c) +
0.71n2, because
(_ep E2p (-2+e) (2t)
E2p
qu 151
n2
exp
exp
exp
S exp
(9)
151e
15100
27
for the relevant range of n and 2 75. ep 2 t E [
n²
We thus obtain (8) after union bound over all
100
Now, suppose that E [T] is the first index where qi + 12 2 f, so that = r, and 3 = rt-1. where we let no 5. If no such query passes, then set t = T + 1 by default. Then by the utillity
guarantees of Lemma 2, we have that with probability 2 2
qt 2 0.76n, Q-1 S 0.79m,
since
By taking the contrapositive of (8), we can conclude that with probability 2 1 8, we have of 2 0.75n and q 1 < 0.8n. Condition this event for the rest of the proof.
n 100 2 a = 24 log( 4T)
Because 2 0.75n, there is clearly some E D such that [D n (x;, F)] 2 0.75m, as this is the average number of dataset elements radius-i ball centered at a random D. Now applying Lemma 4 with S set to the indices of D \ Bd Bxxx,, f), that |S| < 0.25n, gives
||x,
x,1 S 3
|x. Xy S 4 for all x; D B (),,
This implies 4f 2 y (0.75) as claimed. Further, because Ø S 0.8n, we claim > (0.9) cannot hold. Assume for contradiction that this happened, and let S == n Bd (x., 100.9)). By the triangle inequality, for all of the 0.9n choices of x; S, we have that
Σ jE(m]
x. x 2 0.9n,
which implies that -:11 2 0.81n, a contradiction. Thus, we obtain F S (0.9) as well.
We remark that all of this logic handles the case where 2 < S T' is the iteration where Algorithm 1 returns. However, it straightforward to check that the conclusion holds when = (i.c., == =)
because we assumed r S (0.9), and the lower bound logic on / the same as before. Similarly, i R. then the upper bound logic on f the same before, and 2R > (1) > (0.75) 2y is clear.
Lemma 7, Assume that f 2 (0.75)) in the context of Algorithum With probability 2
18 every
i E [n] that is assigned p; 0 in Algorithm 2 satisfies ||x, x, 3f, and Z 2 0.6n.
Proof. Our proof is analogous to Lemma 6, where for all E [x]] we define the "ideal score"
1xx-x,
JEjN
such that Eff, fr. We first claim that with probability 2 5 the following hold for all i [n]:
18
fr 2 0.75k
f. 2 0.7k, and ft s 0.45k
ft S 0.5k.
(10)
16

---

The first claim above is immediate from our choice of k and Fact 4 (with failure probability - for each E [n]);; the second follows (with the same failure probability) similarly (9), i.e.
5 18n
exp (- (-2+e
2/ 2++
eu 20
k:
8
S exp
S exp
400
18n
in our application, with E 2 5 and eji 2 20 Thus a union bound proves (10).
To obtain the first claim, observe that any i E [n] with ||x; x.Il > 3F must have that Bx,,, 2f) does
not intersect B(x,, f). However, [(x., f) contains 0.75n points in by assumption, so f I 0.25%
and thus as long as the implication (10) holds, then = 0 as desired. For the second claim, any X;
satisfying ||x; x. |l I r y(0.75) has [B(x,, 2 (nD) D 2 0.75m, so that f; 2 0.7k. Thus, every such x; has pi 0.8 as long as (10) holds, so the total contribution made by the 2 0.75n such x; to Z is at least 0.6n.
Lemma 8. Suppose that it is the case that in the context of Algorithm 2, we have
f S 0.45k
fi S 0.5k, and fi 0.55k ft S 0.6k,
(5)
for all E [n]. If Z > 0.55m, there exists some x E Rd such that {x, ps > O)ee(n] S [xx, 4f). Moreover, the event (5) occurs with probability > 1 9-
5 and the second Proof. The first statement in (5) was proven in (10) to hold with probability T8. statement's proof is identical to the first half up changing constants, so we omit it. Conditioned on this event, every x; with p; > 0 has f > 0.45k. Moreover, because Z 0.55m, there exists some j E [n]] (i.e., with the maximum value of pý) such that P, 0.55, which implies ʃ3 > 0.6k and thus fj > 0.55k.
So, we have shown that B(x,, 2f) contains more than 0.55n points D, and every surviving i E [n] (i.e.. with positive p:) contains more than 0.45n points in D. Thus, B(x,, 2 and [B(x,, 2F) intersect, and in particular, B(x,, 4f) contains every surviving point by the triangle inequality.
Lemma 9. If n 20, Algorithm 2 is (c, 8)-DP.
Proof. Fix neighboring datasets D, D' E (R)",, and assume without loss that they differ in the nh entry X * x/, We will define A, an alternate variant of Algorithm 2, which we denote A, where we condition on the following two events occurring. First, the index n should occur at most 2k times in Usein-1j Sj. Second, the implications (5) must hold. It is clear that the first described event occurs with probability 2 1 - T8 by using Fact 4 with our choice of k, and we proved in Lemma 8 that the second described event occurs with probability 2 1- - 5 Thus, the total variation distance between A and A is at most & We will prove that A is (e, $ DDP, from which Lemma 1 gives that A is (c, ()DP.
We begin by showing that according A, the statistic Z + 21 log( 22) satisfies ($, J-DP To do so, we will prove that Z has sensitivity < 12, and then apply Fact 2. Recall that by assumption, when A is run the number of times n appears in Use(m) St is most 2k. Thus, for coupled values of Z, z' corresponding to D, D', where the coupling is over the random indices selected on Line 3,
7 - 7' S 0.25k
(k- 0)
1
number of copies of n occurring in
U S iE 18[m-1]
S 12.
0.25k
In fact, we note that the following stronger unsigned bound holds:
Σ lp: 4
Σ
lp:
p41
kE(n]
=E(n-1]
(11)
< 4
number of copies of n occurring in
U iE|n-1]
S.
12,
0.25k
because the clipping to the interval [0, 1] in the definitions of pt, 24 can only improve |p; - -pll. and the distance between the corresponding fi, f( is at most the number of copies of n occurring in them.
17

---

Now. it remains to bound the privacy loss of the rest of A, depending on whether Line 9 passes. If the algorithm terminates on Line 10, then there is no additional privacy loss.
Otherwise, suppose we enter the branch starting on Line 12. Our next step is to bound the sensitivity of x. Observe that whenever this branch is entered, we necessarily have Z > 0.55n (and similarly, Z' > 0.55m), because Z + & 24 log( 24 S Z deterministically. Thus, Lemma 8 guarantees that in A, all x; D with p; are contained in DD' are contained in a ball of radius 4f. However, there are at least 0.55m surviving elements of both D and D', and in particular, for the given range of n there are at least two common surviving elements (one of which must be shared). A ball of radius 8/ around this element, which we denote in the rest of the proof, contains all surviving elements in D (according to (eem)) and in D (according to (p/)se(m)
ball of radius 4f, and similarly all surviving elements
Now we wish bound x- where x' := = P/ We have shown that in A. 1Z Z'| S 12 and min Z, Z 2 0.55n. For convenience, define y; := x; & for all i [n]. and similarly define y/ Recalling that all surviving elements of D U U are contained in [Bx;, 8f).
X x'11
1
Σ
1
Σ
ply!
p.y:
Z
Z' iE[m
iE(n]
1
Σ p.y:
+
1
Σ
(ps p()y;
+
Pa
1
+
Phx
Iy
Z
Z'
Z'
Z
Z'
kE|n-1]
KE(n-1]
-
1
8F
16F
P.Y
+
Pp:
p`l +
Z'
Z
0.55n
0.55m
iEin-1
(E
96f
104F
16
400F
0.55n
0.55n
0.55m
The first line shifted both x and X' by x. and the second line applied the triangle inequality. The third line applied the triangle inequality the middle term, and bounded the contribution of yn by using that || I 8f if > 0; a similar bound applies to y',. In the fourth line, we used the triangle
inequality on the first term, as well as that Eie(n-1] p; - P// < 1 + 12 by using (1 and accounting
for the nhth point separately. Thus, X has sensitivity 4008 in A. Fact now guarantees that Line 17 is also ( 5 -DP.
Theorem 3. Let D (xxlie(n) C (R) for R O, <r (r)), and let (c, [0, 1j3.
Suppose that n 2 C. (vd. loR(H) + logl lox: ). for a sufficiently large constant C. There is an (DP algorithm that returns (x, such that with probability 1 ô, following notation (3),
fD(2)= S (400" + (x) (D)), f S 4 (0.9)
(6)
for a universal constant C.. Moreover, [Ixx(D) - x|| - C'F. The algorithm runs in time
n log( R 8
o nd log
log
Proof. Regarding the utility bound, we will only establish that ||x, (D) - *|| < C"F, which also gives (6) upon observing that fo is 1-Lipschitz, and fx(xx Z (..1 due to Lemma 3.
We first run Algorithm with (c. 8) + ( 4) which gives for large enough C' (via Lemma 6)
1 (0.75) sF (0.9)
(12)
with probability 1 5. Next, we run Algorithm 2 with this value of and parameters (e, + (5. (. The privacy of composing these two algorithms now follows from Lemmas and 9, and the runtime follows from Lemma 6, because Algorithm I's runtime does not dominate upon inspection.
18

---

It remains to argue about the utility, i... that (Ix x|| I C. Conditioned on (12) holding,
Lemma 7 guarantees that with probability 2 11 - &. we have that ||x xxxxx,22 (D)ll - 3f, as a positively- weighted average of points in (x 3F). Finally, for the given value of in Algorithm 1, standard Gaussian concentration bounds imply that with probability 2 1 4
1 ( -0(( -
oo
Vdlog())) O(F) ne
X
x|
||||| S 30
d log
Thus, [Dx - x|| 2 C' holds for an appropriate C", except with probability 8.
D Deferred material from Section 4
In this appendix, we provide privacy and utility proof for Algorithm and combine them to prove Theorem 4. To recall, Algorithm 3 proceeds in phases K = log(T). In each phase (loop of Lines 2 to 16) other than h = 1, we define domain AC(A) centered at the output of the previous phase with geometrically shrinking radius x g(*); the domain for phase h = 1 is simply (* f). After this, we take (()) steps of SGD over ((() with step size 16)), and output noised variant of the average iterate Lines 13 to 15.
D.1 Privacy of Algorithm 3
We first show that Algorithm 3 satisfies (e, 8) for appropriate choice of When the sample functions of interest are smooth (i.e., have bounded second derivative), [FKT20] gives a proof based the contractivity of iterates. This is based on the observation that gradient descent steps with respect to a smooth function are contractive for an appropriate step size (see e.g., Proposition 2.10, [FKT20]). Unfortunately, our sample functions are of the form ||- xz|l. which not even differentiable, let alone smooth. Nonetheless, we inductively prove approximate contractivity of Algorithm 3's iterates by using the structure of the geometric median objective.
Throughout, we fix neighboring D' E (Rd)) ", and assume without loss of generality they differ in the th entry. To simplify notation, we let I E [n]" denote the multiset of T indices sampled in Line 10, across all phases. We prove DP of Algorithm 3 using Lemma I, where we let A denote Algorithm 3, and we let A denote a variant Algorithm 3 conditioned on I containing at most m : 3 + log(3)) copies of n. We first bound the total variation distance between A and using Fact 4.
Lemma 10. With probability 2 1 - g. Algorithm 3 yields I containing S m copies of n.
Proof. In expectation, we have m.
1 copies, so the result follows from Fact 4 and our choice of
We will show that A is (e, -DP, upon which Lemmas and 10 imply that A (Algorithm 3) is (c, 6)-DP. To do so, we control the sensitivity of each iterate 2, (k) using the following two helper facts.
Fact 5 ([Roc76]). Let K. Rd be compact, convex set. Then for any x, y E Rd. we have
(xx)) S ||x y/l
Lemma 11. For any unit vectors u, v E Rd, and a, b > 0, lel x = au and y = bv. Then, letting
(a r) and y' t (b n)v, we have ||x' -y'll < max(11x w1lxx-ll..00 3n).
Proof. We claim that
Xx' y'll < x x yl - a + nn
(13)
from which the proof follows from observing that if a + S then we can trivially bound
|x - y'll < | 27 - a + + 3n.
19

---

Indeed, (13) follows from a direct expansion:
|X yl1² - ||x y'll a² + b² -2ab (u, v) (a 17)2 (6 -n)² + +2(a 1)(bb 17) (u.v)
2n(a + b) 21p² 27/(a + b) (u, v) 21/² (u, v)
2m(a + b n) (u, v)).
Thus, for n 2 O and (u, v) 2 0. we conclude that (13) holds.
Corollary 1. For any phase l E [K] in Algorithm condition on the value of Zu and assume that I contains at most m copies of n. Then.for any 0 < t < Tu, the sensitivity of z is S. (2m + 1)7(k)
(k)
Proof. Throughout this proof only, drop the iteration k from superscripts for notational simplicity, so we let T := T** and 17 == 17(8), referring to the relevant iterates as {ze jzsJoses == {zz JogieTos. We also refer to the index i selected on Line 10 in iteration 0 s t < T by 4--
Fix two copies the 4thh phase of Algorithm 3, both initialized at Zu. but using neighboring datasets D, D' differing in the n entry. Also, fix realization of { Josee,, such that i, n at most m choices of (note that m is actually a bound on how many times i, = n across all phases, so certainly bounds the occurrence count in single phase). Conditioned on this realization, Algorithm 3 now deterministic mapping from Zo to the iterates (zJogteTT depending on the dataset used.
Denote the iterates given by the dataset D by {ze (2eto and the iterates given by D' by (z/Joscc7 so that Zo z by assumption. Also, let 4, ||z 10--2,, zill for all 0 S < T. We claim that for all 0 <T
$ S maxx + 1, 1,3) where me
Σ 0,,=n= 0Sect
(14)
i.e. m, is the number of times the index n was sampled in the first / iterations of the phase. If we can show (14) holds, then we are done because m. m by assumption.
We are left with proving ( (14), which we do by induction. The base case = 0 is clear. Suppose (14) sampled). then (14) holds by
holds at iteration t. In iteration + 1, if m,+1 m, + (i.e., & = the triangle inequality and the induction hypothesis, because all gradient steps 7/g: have || S 7, and projection to K can only decrease distances (Fact 5). Otherwise, let is i } be the sampled index, using the common point x; E D'. Now, (14) follows from applying Lemma 11 with
24 X;
z x;
x 2z X,, y f- z X1, 11
1
z x,1
In particular, we have that ||x yll Dt, and ||x' y'll 2
4141 (due to Fact 5), following notation from Lemma 11. We thus have Φ S max p,, 31)) which clearly also preserves (14)
inductively.
We can now conclude our privacy proof by applying composition to Corollary 1.
Lemma 12. Let c E 1]. 1f
4 4log( 3) + Algorithm 3 is (c, 5)DD.
Proof. We claim that Algorithm satisfies p-CDP, conditioned on I containing at most m choices of (we denote this conditional variant by A). By applying the second part of Fact 3 with 2log(3) + 1. this implies that A is (e, DDD. Because A has total variation distance at most É Algorithm 3 due to Lemma 10, we conclude using Lemma that Algorithm 3 is (c, 5DDD.
We are left to show AA satisfies p-CDP. In fact, will show that for all k [K], the output of the 4thh phase of A, i.e., (*), satisfies (16 (16)=k & f-CDP (treating the starting iterate zn (R-1)) as fixed). Using composition of RDP (the first part of Fact 3), this implies A is p-CDP as desired.
Finally, we bound the CDP of phase & E [K]. Under A, we showed in Corollary that all iterates of the thth phase have sensitivity Σ (2m + (8)) Thus the average iterate (k) also has sensitivity < (2m + (k)( by the triangle inequality. We can now bound the CDP of the ttth phase using the third part of Fact 3:
(2m + (k)2
((2m + 1)m)²
16- 9h
P
<
16
kk
((0(1))3
(2m + 1)n)²
2
2
20

---

D.2
Utility of Algorithm 3
We now analyze the error guarantees for Algorithm 3 on optimizing the geometrie median objective fo (3). We begin by providing a high-probability bound on the utility guarantees of each single phase.
Lemma 13. Following notation of Algorithm 3, we have with probability 2 1 that
17(1)
log T())
4K 0
fo(x(1) fD((x))
+
4P1
21y(1T(1))
2
where x, == argmin (x), and
2( (8))2 log( 4K)
(k)
[KK
2d
f -
((((((
2
+80
(2) log
8
V
((k) for all 2 2 k & K.
Proof.
First, with probability 2 1
8 4.
we have
{<)) S (x( d
4K
for all [K].
by standard Gaussian concentration. Thus, ((k-1) 1) E k((i) for all 2 S k S K, and x, E (CO), except with probability 1. Next, consider the hh phase of Algorithm 3, and for some 0 I t < Tg, let us denote
(R)
24
(k)
Z
X;
where E [n] the random index sampled on Line 10 in the th iteration of phase We also denote
gr
(k) Z
X
We observe that Elg gr Now, by the standard Euclidean mirror descent analysis, see e.g., Theorem 3.2 of [Bub15], for any k(()
for any realization of the randomness in all previous iterations.
(k)
2
(R)
Z
11
(n)
<
(15)
2
2
2
Here we implicitly used that ||g (1) || < 1 for all choices of the sampled index i E [n]. Now summing (15) for all iterations 0 < < (k), and normalizing by (k)) we obtain
20
(R)
Σ
(k) B:
(k) Zz
u
5
T(k)
(k)
2
OS1CTO
Next, we claim that with probability
2 1 - 5
2 4K
т()
g
(1)
81
21
(1)
u
< 4F
T(1)
(5
Σ
kk)
(K)
< (k) log
(4K)
2d for all 2 < k: < K.
((k)
gi
u
V T(k)
(5
u) is mean-zero random variable, that is bounded (with probability 1) by twice the diameter of (k), Thus can bound the sub-Gaussian parameter
In each case, this is because (g.
(k)
8i
(k)
2
(b)
21

---

of their sum, and applying the Azuma-Hoeffüde inequality then gives the result. Now, finally by convexity,
Σ USICTa)
Bc
(1)
1
2 T())
Σ
fo(z, - fb(u) 2 fo(x(") fo(u),
TU
OSt<T())
(b) (N)
fo(u) for all S $ K. Σ fo(z! - ffo(u) 2 fo(x(!)
T(k)
gr
4 //
2 T(k)
0St<T(0)
USL<T(0)
Combining the above three displays, and plugging in u t- x, or u + xlk-1), now gives the conclusion.
By summing the conclusion of Lemma 13 across all phases, we obtain an overall error bound.
Lemma 14. Following notation of Algorithm 3 and Lemma 13, we have with probability 2 1 ô that
R2 + 19n + +
4K log(
1314T ryd log"
8K
fD(x(())- - fD((.) S
+
167T
T
pm?
Proof. Throughout this proof, condition the conclusion of Lemma 13 holding, well
|<<]| s 20(k))
v ddlog
2 (
both of which hold with probability 2 21-1 - 6 by union bound. Next, by Lemma 13,
fo((k) fD(x.) = ) fo(xx))) Σ fx( fo(x((-11) fD((x) - fD(())
,2
+ (1
2 2 4K à
+ 4F1
(TT()
2
T(1)
K
(( 4K
(k)
+ 80 (8) log
4KK
2d
+ |
((K)
T(a)
2=
A2
log(
144m 2 nnd
12 12 log( 4K
+
?
+ VPV
16nT
2
T
pf
vpT
/2
log( (K)
12967 pn log
3 (88
36v dT 2
+
"
+
VPV
16nT
2
T
pn
/ pm
log( AK
1314T nd log ( 8K
19n
8//
16nT
T
pm?
The third line used Lipschitzness of fD, the fourth summed parameters using various geometric sequences, the fifth plugged in our value of m, and the last split the fifth term using 2ab S a² + 62 appropriately.
By combining Lemmas 12 and 14 with Theorem 3, we obtain our main result on privately approxi- mating the geometric median to arbitrary multiplicative factor + a, given enough samples.
Theorem 4. Let (xx Jiemn C. (R) for R O, let S (r(0 (D), and let (a, c,
[o, 113 Suppose that n 2 C. L' 2.5
احفي) )), for a sufficiently large constant C. There is (e. 5D-DP algorithm that returns & such that with probability 1 ô. following notation (3),
ac log
fx( S (1+ (x)xx(x((D)) The algorithm runs in time
R
d dogg( B))
d +
log( d ade δ
o nd
log
log
ade
a²
22

---

Proof. We first apply Theorem 3 to compute (x, f) pair satisfying
i i (0,1(0.))(()) (D), | - xx s,,
for universal constant C², subject (5, 2 )DP and 3 failure probability. We can verify that Theorem 3 gives these guarantees within the stated runtime, for a large enough C. Next, we call and ò +- o Algorithm 3 with 4 32
,
2. which is (5. & )DP by Lemma 12, so this composition
is (e, DD..
Denoting == x(K) to be the output of Algorithm 3, Lemma 14 guarantees that with probability 2 2
$2 + 191 + SP
16K log(
5256T 5256T'md log 16K
fD(x) - (x(( -
16nT
T
en1²
for some choice of T and our earlier choices of privacy parameters. Optimizing in 17. we have
log(
16K
37
d
16K
fo(2)
< 1
T
en
57600(C")) log(
16k
Finally, for large enough C' in the definition of n, and T n
we obtain
log( 16K
37 d d'log" 51 16K
at
(r.0
[D()) /p00)//p(xx00 (D)) < 12
5
S (x))(x,()),
T
en
100
10
The last inequality used Lemma 3. Now, the runtime follows from combining Theorem 3 and the fact
that every iteration of Algorithm 3 can clearly be implemented in O(d) time.
E Deferred material from Section 5
We first describe the datasets used for our experiments in Section 5.
GaussianCluster({ R, n, d, a, frac;.): This dataset is described in Appendix H of [HSU24]. We draw 7in = fracm n points i.idd. from ((,, o'Ia) with uniform on the sphere of radius R and Nout nin outliers uniformly from the Euclidean ball of radius R.
2'
Heavy (w, n, d): This dataset samples n points in Rd from a zero-mean multivariate Student's distribution with identity scale and degrees of freedom v.
To avoid contamination in hyperparameter selection, every experiment is performed with fresh dataset.
Subsampling. We now provide more details and results on evaluation of Algorithm 1.
In the first experiment (Figure 2a), we set 1000, d 10. inlier fraction fraci, 0.9, standard deviation = 0.1, and choose an upper bound R from the set {0.5, 1, 2, 4, 8, 10). The dataset is generated GaussianCluster R, n, d, a, fracm) dataset. We set privacy parameters 0.75, and for each trial we sample Tmin ~ Unif([0.005 0.02) to randomly initialize our search grid. Since 7 < fraci. we estimate the ground-truth quantile radius Trrue = dd,, run both algorithms on this dataset, measure the estimated radius and wall-clock runtime, and report the mean and standard deviation of the estimation ratio f/rtrue and runtime over 100 independent trials.
1.0 and
5 = 10-5, quantile fraction
In the second experiment (Figure 2b), we assess the robustness of FastRadius and RadiusFinder to heavy-tailed data. We set n 1000 and
10 in the SeavyTaaile((1,, n, d) dataset with varying degrees of freedom E {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}. For each trial, we sample Tmin ~ Uni00[0.005, 0.02]), set privacy parameters
1.0, 10 and quantile fraction y 0.75. We estimate the theoretical quantile radius Ttrue = / (T) where Fa,u is the CDF of an F(d, v) distribution, which is the Fisher F-distribution with d and v degrees of freedom, execute both algorithms, record i and runtime, and summarize the mean and standard deviation of the ratio / //eere and runtime across 100 repetitions.
23

---

Effect of changing aspect ratio i on private radius estimation
2.5
Ratio of estimated and true redius Aitee
RodupPider Nottudis
estimaated true redluus Fiteae
Faihadas
24
2.8
3.4
2.4
2.2
2.9
2.5
5.0
30.0
20.0
radius
Degrees of freadom
(a) Ratio of the estimated quantile radius to the true radius (b) Ratio of the estimated quantile radius to the true with varying data radius/ R.
radius with varying degrees of freedom
Figure 2:
Comparison of RadiusFinder and FastRadius across different data distributions. All plots are averaged across 100 trials and standard deviations are reported as error bars.
We observe that in both cases, across range of increasingly heavier tails of the distributions, both al- gorithms achieve reasonable approximation to the true quantile radius, always staying multiplicatively between roughly 1.2 to 3 of the true quantile radius. We further record the average wall-clock time required by both algorithms in Table We observe that FastRadius significantly faster compared to RadiusFinder, while performing competitively in terms of estimation quality.
We remark that we also experimented with varying n E (500, 1000, 2000} and d E: {5, 10, 20) and observed qualitatively similar trends for the performance of both algorithms.
Table 1: Average wall-clock time in seconds over 100 trials for each algorithm in each experiment
Experiment
RadiusFinder
FastRadius
Varying R (Figure 2a)
1.192 + 0.047
0.0411 1 + 0.002
Varying (Figure 2b)
1.204 + 0.171
0.0413 0.007
Boosting. We conclude by describing our evaluation the performance of our boosting algorithm in Section 4 based low-pass DP-SGD implementation, compared to the baseline method from [HSU24].
We briefly describe our hyperparameter optimization process for the baseline, DPGD. To satisfy
p-CDP, Algorithm 3 in [HSU24) recommends constant step size of 1/base V opn where is estimated radius. We examined performance using various step sizes v) = Ybase "/multtppier with multipliers Muultiplier {0.5, 1, 10, 30, 50, 100). Our results indicate that the 77multiplter depends significantly on dataset size, in that larger datasets benefit from higher 7 Specifically, observe that as increases, larger Mmultiplirr values consistently reduce optimization error, but with diminishing returns. Based on these experiments, we select Mmullippier = 30 for DPGD in our experiments, this consistently provides nearly the best performance across the range of datasets and parameter settings our evaluation.
We now describe our setup. In all our experiments, set d 50, {100, 1000, 10000). For the GaussianCluster dataset, we set o 0.1 and vary the bounding radius R E (25, 50, 1003. We set our estimated initial radius f = 20o / d and initialize all algorithms at a uniformly random point on the surface (0.75F). For the Heavy Tailed dataset, we use the same values of d, p, and the same range of n. We vary / E (2.5, 5.0, 10.0]. set our estimated initial radius f 20 /DF/Fa. (0.775 to be consistent with subsampling experiment, and again initialize randomly the surface of (0.75F).
0.5, and vary
We chose relatively pessimistic multiple of f create larger initial loss and account for estimation emror.

---

In our first set of experiments, we used the middle "scale" parameter, i... R = 50 for the GaussianCluster dataset and y 5.0 for the HeavyTailed dataset, varying n only. We report the performance of the three evaluated methods, plotting the passes over the dataset used by the excess error. Our error metric the experiment. This is more reflective performance metric than the corresponding multiple of fD- as our algorithms achieve this bound (see discussion after Theorem 3), and fo 2 f for our datasets due to outliers.
(fo(x) - [D))), i.e., a multiple of the "effective radius" used in
souadia Klacter Strtiae, 15B 4.u
Golas anClsserr detase: 8
wws.bb kuter C1156IC d.c. UASS W:
33
50
20.
22.
23-3
200
22.3
11.
21.
30
15
12.
23.5
22.3
27.
(a) 12
= 100
(b) n = 1000
(c) 72 = 10000
Figure 3: Comparison of DPGD, StableDPSGD, and FixedOrderDPSGD across GaussianCluster
data over R550, varying n. Plots averaged across 20 trials and standard deviations are reported as error bars.
Across GaussianCluster datasets of size n {100, 1000, 10000), we consistently saw that our optimized FixeOOrderDPSGD performed the best, with comparisons between the baseline DPGD and StableDPSGD fluctuating depending on the dataset size. As the theory predicts, the gains of stochastic methods in terms of error-to-pass ratios are more stark when dataset sizes are larger, reflecting the superlinear gradient query complexity (each requiring one pass) that DPGD needs to obtain the optimal utility.
6.2
1593
Mi Nuryflaker 103R) 12
34
25
203
22.
134
21.
253
11.
134
124
250
17.
134
(a) 12 = 1000
(b) 1 10000
Figure 4: Comparison of DPGD, StableDPSGD, and FixedOrderDPSGD across Heavy Tailed data
over R50 varying n. Plots averaged across 20 trials and standard deviations are reported as error bars.
We next present our comparisons for the HaiveT dataset. Here, step size multiple of Mjmuliipier 30 was too aggressive for the baseline DPGD to reliably converge when n = 100, but smaller steps impacted the performance of DPGD with larger sample sizes. On the sample sizes where DPGD successfully converged, we saw that our FiXSGOrderDPSGD consistently outperformed StableDPSGD, whereas the baseline DPGD slightly outperformed FixedOrderDPSGD when n 1000 was moderate. The improved performance of DPGD may be related to the relative simplicity of this dataset, where all the data is distributed in rotationally symmetric way around the "population geometric median," i.e., the mean.
In our second set of experiments, we fixed the size of the dataset at 1000, varying the scale parameter (R for GaussianCluster and for Heavy Tailed). We observed that the relative performance of our evaluated algorithms was essentially unchanged across the parameter settings we considered.
Finally, we remark that one major limitation of our evaluation is that full-batch gradient methods such as DPGD can be implemented with parallelized gradient computations, leading to wall-clock time savings. In our experiments, DPGD often performed better than FixeGOrderDPSGD in terms of wall-clock time (for the same estimation error), even when it incurred significantly larger pass
25

---

Cauasenn siter ditaust LONC 20
CoLSS anclutee ditane: 1006 8:
CeacsaaChater deuand
1200 R. 500
0.15
0.3
Wetter 9010 merwoat
wasser of Neree ever0r
R 25
(b) R 50
R 100
Figure 5: Comparison of DPGD, StableDPSGD, and FixedOrderDPSGD across GaussianCluster data over R50, varying R. Plots averaged across 20 trials and standard deviations are reported as error bars.
Hentay porvent 11W9
DeaeyDiee Eitrort Poe (900) a
303
360
13.5
(a) //
(b)
(C) 10
Figure 6: Comparison of DPGD, StableDPSGD, and FixeOOrderDPSGD across HeavyTailes Tailed data
over R50 varying v. Plots averaged across 20 trials and standard deviations are reported as error bars.
complexities. On the other hand, we expect the gains of methods based on DP-SGD be larger as the dataset size and dimension (n, d) grow. There are interesting natural extensions towards realizing the full potential of private optimization algorithms in practice, such our Algorithm 3, e-g., the benefits of using adaptive step sizes or minibatches, which we believe are important and exciting future directions.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We claimed a theoretical improvement to the private geometric median problem, which formally prove and provide experimental evaluation of.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We describe limitations of our theoretical results (e.g., a potentially suboptimal additive runtime term) when introduced in Section 1, and limitations of our experimental evaluation (e.g., accounting for parallelization and heuristics for centerpoint estimation) in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
27

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results except standard ones (e.g., textbooks) have self- contained proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We give a full description of every experiment in the paper, and provide reproducible code in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
28

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
As described above, we provide reproducible code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.. cc/
Souuiiddee/oeeeummiieeeeesseeees iatpommsssssooooolmoooooo MmPlicyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/publicgguiceee gwtp//gwie///eeee//ee//ee//eeees htte///oouuumsssiiee.eee
stiobbmmsssioooiooyy.y... for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
As described above, we specify all such details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
All reported figures come with at least 20 runs and error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
29

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We discuss the computational resources used in our experiments in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://neuripppp cttpriipppccppppplpe cttp///bbicccthicctuuceeeeelllll
Answer: [Yes]
Justification:
We confirm that our research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction..
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is primarily theoretical in nature, as it studies fundamental com- putational problem. There is likely a significant pipeline for applications of our results to have downstream social implications, which we do not feel is within our scope comment on in this paper. We remark that ultimately our algorithms are motivated by robustness and privacy desiderata, they are in line with (potential) positive socictal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
30

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
All of our data is synthetic, so we do not foresce this as a relevant concern.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use any existing assets in this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
31

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. con/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We do not release new assets beyond (simple) synthetic dataset creation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
These concerns are not relevant to the scope of this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: These concerns are not relevant to the scope of this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
32

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs do not play any significant component this research.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //tpar///..e..//eeeeee ///CCofferencee/225/LLLL for what should or should be described.
33


Reviews:
[{"review_id": "HSqqFPaejY", "reviewer": "Reviewer_bdcd", "summary": "This paper presents a new efficient algorithm for computing in a\ndifferentially private way the geometric median of a set of\ndata. Recent work has proposed two-phases (warm-up and boosting)\nalgorithms for a multiplicative approximation of the geometric median\nwith optimal sample complexity but running in polynomial time. The\nalgorithm proposed in this paper achieve similar accuracy and sample\ncomplexity but runs in almost linear time (for some range of the\nparameters).", "questions": "Can you clarify why you use the FriendlyCore procedure for estimating the centerpoints? What do you gain?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n\n- The paper address an important problem: improving the runtime of\n algorithms for differentially private geometric median with good\n average error rates.\n\n- The paper improves the runtime of the warm up phase by using\n  subsampling in a \n    \n- In the boosting phase the paper gives an analysis of DPSGD\n  leveraging the properties of the geometric median to obtain an\n  improved runtime.\n\n\nWeaknesses\n\n- The proposed algorithm uses as a subroutine an adaptation of the\n  FriendlyCore procedure from [TCK+22] but it is unclear why this\n  departure from the original algorithm is needed.\n\nRecent work proposed differentially private algorithms for the\ngeometric median with average error guarantees but those algorithm\nhave a polynomial runtime, which can be problematic in large data\nsettings. It is thus important to have more efficient algorithms and\nthis paper does exactly that.The proposed algorithm uses a two-phases\napproach, based on warm-up and boosting, as the ones in previous work\nbut it optimizes the running time of each step.\n\nTo optimize the runtime of the warm-up, which has itself two phases,\none for estimating the radius and one for estimating the centerpoints,\nthe paper uses subsampling. In the first phase the algorithm subsample\npoints to estimate the radius. This change is relatively\nstraightforward.  In the second phase, the proposed algorithm departs\nfrom previous work and uses as a subcomponent the FriendlyCore\nprocedure from [TCK+22].  In orde to improve the efficiency of this\nprocedure the algorithm uses subsample in the computation of the\nweights associated with each data point. This change is non-trivial\nand needs an interesting change in the privacy proof. However, it is\nunclear why this departure from the original algorithm is needed since\nthe obtained improvement is quite limited.\nTo optimize the runtime of the boosting phase the paper proposes an\ninteresting ad-hoc analysis of DP-SGD specific to the geometric\nmedian.  Specifically, the paper uses the properties of the geometric\nmedian to control the sensitivity of DP-SGD and obtain an optimization\nin nearly-linear time.\nOverall, the proposed algorithm shows considerable improvement thanks\nto non-trivial changes to the algorithms from previous work.\n\nA couple of minor points:\n- in equation (2) the notation for the indicator function is not yet\n  defined\n- line 110 has a wrong citation", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind words regarding the importance of the problem considered and the improved runtime. We will add the definition of the indicator in Eq. (2) and fix the citation in Line 110 to replace it with [TCK+21] – thank you for bringing up these comments.\n\nWe agree that there is no significant qualitative change in our runtime vs. that of [HSU24] in the centerpoint estimation phase. We stated as such in Section 1.2, but can further clarify that our motivation for including our alternative approach was to highlight the simplicity of directly adapting FriendlyCore. Indeed, our analysis of Algorithm 2 essentially directly extends [TCK+22] to tolerate inaccuracies due to subsampling. Our approach thus \n\n(1) gives an arguably much simpler approach to centerpoint estimation (prior work [HSU24] required a custom analysis of DP-GD with geometrically decaying step sizes), and \n\n(2) makes the observation that FriendlyCore can be sped up via subsampling, which to our knowledge has not been explicitly noted before. We do not view this section as a major technical contribution of our paper."}, {"review_id": "icWiyux6hh", "reviewer": "Reviewer_8pT7", "summary": "This paper presents a novel and practically relevant algorithm for computing a differentially private geometric median in high dimensions, achieving nearly-linear runtime. The authors build upon the FriendlyCore warm-start technique and integrate a refined DP-SGD procedure with a smoothed subgradient to overcome the non-smoothness of the geometric median objective.\nTheir proposed algorithm achieves:\n- Near-optimal sample complexity\n- Strong error guarantees comparable to prior work\n- A significant improvement in runtime from prior quadratic-time algorithms to near-linear.\nEmpirical evaluation demonstrates a 30 times speedup on synthetic and real data benchmarks, without significant loss of accuracy, and with robust error performance across multiple trials.", "questions": "The algorithm depends on the parameters r, R? The upper bound is more justified as there may be a natural bound on the points or one could normalize them. However, r is less justified. How can one compute it and what happens if it is not correct? Could you obtain an error with an additive term relative to r?\n\n- Lemma 9 seems strange. How does n >= 20 relate to (eps,delta)-dp? Seems like the condition is artificial and It would be nice to remove it.\n\n- I am never a fan of misusing the O tilde notation. Theorem 1 writes O tilde to hide all polylogarithmic factors (even for unrelated variables) but it should only be used to mean hiding polylogarithmic factors of the quantity inside the O tilde. It would be nice to fix the theorems appropriately rather than adding a footnote.", "limitations": "Yes, the authors describe the potential suboptimality of the runtime as a limitation tied to using first order methods for optimization. Alternative methods could potentially have better dependency.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The geometric median problem is a fundamental problem in many domains including clustering, robust statistics and social choice. This paper makes a technically sound and valuable contribution offering a novel and efficient . The combination of a warm-start approximation with a customly analyzed DP-SGD routine is elegant and well-justified, addressing the challenge of non-smooth optimization under differential privacy.\n\nThe authors do a rigorous analysis using mathematical proofs but also give an efficient implementation and empirical evaluation of their method. The writing is clear and well-organized, with helpful figures (notably Figures 1 and 2) to illustrate empirical gains.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging words regarding our contribution and rigorous analysis.\n\n**Need for parameters $r, R$** : As the reviewer mentions, $R$ can be estimated by a norm bound on the input datapoints. Regarding the need for estimating r, as noted in the prior work [HSU24], knowledge of such an a priori lower bound is necessary by the impossibility results in [BNSV15]. We note that our dependence on $r$ is relatively mild (i.e., essentially a single logarithmic factor in the runtime and a single loglog factor in the sample complexity). It is an interesting open question to improve the dependence on $R/r$, although we find it potentially challenging to do so while retaining the nearly-linear runtime.\n\n**Lemma 9 and $n \\geq 20$**: The $n \\geq 20$ is due to the particular constants used in our application of Chernoff bounds in Lemma 8 and we will optimize it in the revised manuscript.\n\n**$\\widetilde{O}$ notation**: We will modify $\\widetilde{O}$ to only include polylogarithmic factors of the quantity inside it, as our use may be confusing re: the dependence on $R/r$. We do note that we are not aware of a uniform convention in the usage of $\\widetilde{O}$, with many related works using a similar definition to our paper. Also, we remark this notation is only used in Section 1; statements in all other sections fully quantify dependences on all parameters. \n\n[BNSV15] M. Bun, K. Nissim, U. Stemmer, and S. Vadhan. “Differentially private release and learning of threshold functions”. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE. 2015, pp. 634–649."}, {"review_id": "ybzhNf9Qrf", "reviewer": "Reviewer_rNu7", "summary": "This paper proposes a DP optimization algorithm to solve the following task: given (x1,...,xn) in (R^d)^n, such that the data points have a norm of R, we aim to solve x* = argmin_x sum_i ||x - xi||. This problem is known as private geometric median. The previous work [Haghifam-Steinke-Ullman'24] proposes an algorithm to provide (1+alpha) multiplicative error with the sample complexity of sqrt(d)/(alpha*epsilon). However, the runtime of their proposed algorithms is either quadratic in n or quadratic in d. The main result of this paper is to push the time complexity to nd + d/alpha^2. Notice that d/alpha^2 is the optimal time complexity of the first-order method even non-privately.\nThe idea behind the proposed algorithm is as follows: it has three stages. \n\n1- In the first stage, an algorithm similar to the algorithm proposed in [Haghifam-Steinke-Ullman'24] (these algorithms are inspired by GoodRadius of [Stemmer-Nissim-Vadhan'16]). The goal is to find a radius privately around the geometric median that contains 70% of the data points. The main idea is instead of computing all the n^2 pairwise distances is sub-sampling that makes the algorithm run in linear time.\n\n2- The second stage is inspired by the FriendlyCore of Tsfadia et al. and it consists of finding a center with the promise that there exists a radius that contains 70% of the data points. The new idea is that FriendlyCore can be sped up to run in O~(nd) time (independently of R/r) using subsampled weights.\n\n3- Finally, the third stage, which is very interesting, is a bespoke analysis of the DP-SGD for the geometric median loss function. The idea here is to \"warm-start\" DP-SGD from the centerpoint given by the output of Stage 2 and the radius given by Stage 1. The main idea is to show that when gradient descent steps are contractive for an appropriate step size, we can use the reduction in [Koren-Feldman-Talwar'20] to convert the contractivity to a private algorithm.", "questions": "please see above the weakness part", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The result of this paper is interesting: it combines lots of interesting techniques to provide a very intuitive algorithm that improves the prior work's runtime.\n\nThere are a few weaknesses:\n\n- If we view this problem from the standpoint of DP optimization, it would be interesting to find a broader class of loss functions for which we can obtain an algorithm with multiplicative guarantee.\n\n- The optimal dependence of the sample complexity on R is unclear. Note that in one dimension there are algorithms that require log*(R) samples.\n\n- The problem of geometric median is very related to the problem of privately finding a point in the convex hull. A helpful comparison for the community is to compare the problem of private geometric median with the problem of privately finding a point in the convex hull, for instance, see the following paper:\nKaplan, H., Mansour, Y., Moran, S., Stemmer, U., & Tur, N. (2025, June). On differentially private linear algebra. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (pp. 2362-2373).\n\nLine 110 - the citation is wrong for the FriendlyCore algorithm.", "was_revised": true, "final_justification": "I think this paper merits acceptance.", "rebuttal": "We thank the reviewer for their positive words about our techniques and improvement in runtime. We will fix the citation in Line 110 to replace it with [TCK+21]; great catch.\n\n**Re: broader class with multiplicative guarantees**: We agree that this is a natural and important follow-up direction, and will mention this as an open problem in the revision. Some natural candidates are problems for which there exist non-private first-order methods with multiplicative guarantees, such as other GLMs (e.g., based on Huber loss) and approximate positive LPs.\n\n**Re: dependence on $R$**: We agree that it is unclear whether our dependence on $R$ is optimal, and that this is an interesting open question. We do note that many of the techniques used in prior work appear specific to the 1-dimensional setting, and that extending these tools to arbitrary dimension would likely come at a significant cost to dependences on other parameters.\n\n**Re: privately finding point in convex hull**: This is an interesting point of comparison. Exactly computing the geometric median privately is certainly a more challenging problem than the private convex hull problem; on the other hand, our paper only aims to solve an approximate version. Current techniques for private convex hull appear substantially more complex than for approximate private geometric median; as noted by [KMM+25], private convex hull can be very unstable as a function of the dataset. On the other hand, because our goal is only to approximate the optimum multiplicatively (which scales at least linearly with $r^{(\\alpha)}$ for any constant alpha > 0), it cannot be affected substantially by moving a single point, so our problem is potentially much simpler. We will mention this connection in a revision, and find it interesting to further explore the relationship between these two problems."}, {"review_id": "QkOQCYgGA9", "reviewer": "Reviewer_Nqyz", "summary": "The task is to compute geometric median of a point set in a differentially private way. The geometric median is the minimizer of $\\sum_i ||\\cdot - x_i ||$ for Euclidean norm, and this paper is happy with approximate minimizer achieving $1+\\alpha$  multiple of the minimum.\n\nA recent work (HSU24) has provided an algorithm solving the task with a certain sample complexity and proved that it is the optimal complexity. However, there was a significant gap in the computational efficiency between private and non-private geometric median computation in the prior work.\n\nThis work provides an algorithm similar in spirit to the one of (HSU24) that runs in a very similar time to the non-private algorithms. Per my understanding, the differences in the algorithms are subtle (but necessary for the improved runtime), but the big picture stays the same.\n\nThe algorithm runs in three phases, first, an effective radius r (i.e., the majority of points are contained in a ball of this radius) of the input is computed, then, a crude estimate of the geometric median (in a distance at most r) is computed. Finally, a custom DP-SGD analysis is performed leveraging the structure of geometric median problem.", "questions": "-", "limitations": "-", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is easy to read and I like the way how is it written, that it provides the intuition and sketches results before diving into the technicalities. I would only suggest to introduce the $r^{(0.9)}$ notation more explicitly.\n\nI find this to be a valuable contribution since (private) geometric median problem is quite important and the improvements in runtime are significant. The DP-SGD analysis technique used in the paper taking advantage of the fact that the gradients are unit vectors can potentially also be used elsewher.\n\nOn the other hand, the scope of the paper is very narrow and the improvements are only in the run time and that is why I do not lean to the highest score.", "was_revised": true, "final_justification": "I still think the paper is good and should be accepted.", "rebuttal": "Thank you for the positive assessment. We will insert an explicit definition of the “$r^{(0.9)}$” notation where it first appears and polish notation throughout."}, {"review_id": "kEr4DL6rjR", "reviewer": "Reviewer_osLn", "summary": "This paper considers the problem of privately estimating the geometric median, a topic that has been investigated previously and an information-theoretically optimal sample complexity is known. In this work, the authors propose an algorithm that achieves the same optimal sample complexity while running in a nearly linear time $\\tilde{O}(nd + d/\\alpha^2)$ for $n$ input data points of dimension $d$, significantly improving the previous result of [HSU24]. The workflow closely follows the framework established by [HSU24], incorporating several novel techniques that enhance runtime efficiency.\n\n[HSU24] Mahdi Haghifam, Thomas Steinke, and Jonathan Ullman. Private geometric median. Advances in Neural Information Processing Systems, 37:46254–46293, 2024.", "questions": "1. Is it possible to remove the requirement of knowledge $r$ and $R$ ? As mentioned in the paper, the resulting sample complexity is independent of these parameters. I wonder if this dependence in the time complexity bound can be removed as well.\n2. This work focuses on approximate DP, where a small probability $\\delta$ of privacy violation is allowed. Is it able to achieve the more stringent notion of pure DP?\n3. The runtime of the private algorithm is $\\tilde{O}(nd + d/\\alpha^2)$ while one of the non-private algorithms in [CLM+16] runs in $O(d/\\alpha^2)$. Is it possible to develop a private algorithm with this time complexity?\n\nSome (possible) typos:\n\n1. [Line 110] \"the FriendlyCore algorithm of [HSU24]\": This seems to be a wrong citation.\n2. In the proof of Lemma 5 [Line 520], the setting of $\\mu$ and $\\epsilon$ may only lead to a probability bound of $\\exp(-k\\cdot \\frac{n-1}{n} /3)$, which is slightly looser than the claimed $\\delta / 4T$.\n3. [Line 537] Lemma 6 should be referenced as Lemma 2.\n4. [Line 563] $f_i^\\star\\ge 0.7 k$ should be corrected to $f_i^\\star \\ge 0.75 k$\n5. [Line 618] what is meant by \"large enough $C$\"?\n6. [Line 619] \"we run Algorithm 2 with this value of $\\hat{r}$.\" However, Lemma 7 requires $\\hat{r} \\ge r^{(0.75)}$ while Lemma 6 only guarantees $\\hat{r}\\ge \\frac{1}{4}r^{(0.75)}$. I think this should be corrected by passing $4\\hat{r}$ to Algorithm $2$, and some related quantities need to be modified accordingly.\n7. [Line 623] Lemma 6 should be referenced as Lemma 7.\n\n[CLM+16] Michael B Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 9–21, 2016.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. The estimation of the geometric median is a fundamental problem in computational geometry. This work presents a private algorithm that operates in nearly linear time, marking a substantial advancement over previous results.\n2. The desired runtime is achieved by making several improvements to different parts of [HSU24]'s framework, which are novel and technically solid.\n3. Comprehensive experiments are conducted to show the effectiveness of the proposed techniques.\n\nWeakness:\n\n1. The algorithm requires prior knowledge of parameters $r$ and $R$, which provides lower and upper bounds on the effective radius $r^{(0.9)}$.\n2. In Section 5 the authors evaluate only Algorithm 1 and 3. The presented analysis of Algorithm 2 incurs large constants that largely affect its performance in practice. Therefore, the entire algorithm is not ready for real-world deployment.", "was_revised": true, "final_justification": "The rebuttal has addressed my concerns. I would like to keep my positive score.", "rebuttal": "Thank for your encouraging words about our contribution and runtime efficiency. We will fix all typographical errors pointed out by the reviewer in the revised manuscript and address key questions below:\n\n**Knowledge of $r$ and $R$**: Thank you for the interesting question. The reason for having these constants in the algorithm are due to application of the AboveThreshold technique, a standard method in DP, in Algorithm 1 which requires a finite set of queries and we are currently not aware of extensions to this method which can handle potentially unbounded range of queries. Moreover, [BNSV15] shows that some knowledge of the parameter $r$ is necessary (as observed by prior work [HSU24]), although it is an interesting open question to improve our dependence.\n\n**On Pure DP**: Currently, the subsampling based approach used in Algorithm 1 and 2 requires a failure probability, which is critical for the computational speed-up. Furthermore, the tools used for private stochastic convex optimization in [FKT20], which inspire the analysis of Algorithm 3 in our work also currently provide an approximate DP guarantee. Therefore, generalizing both of these techniques to handle pure DP remains an interesting direction for future work. We would like to point out that the dependence of both the runtime and the sample complexity on $1/\\delta$ is polylogarithmic, and therefore allows for $\\delta$ being polynomially small in $1/n$.\n\n**On runtime comparison with [CLM+16]**: A private algorithm cannot run in time $\\widetilde{O}(d/\\alpha^2)$, given that this runtime is independent of the privacy parameter eps, which shows up polynomially in the sample complexity. We do think it is interesting to remove this additive runtime term (and obtain an $\\widetilde{O}(nd)$ runtime, the other runtime in [CLM+16]), although this too seems quite challenging, as existing nearly-linear time methods for DP-ERM treat the objective as a stochastic optimization problem, and thus incur the runtime overhead of (non-private) SGD.\n\n**On constants in Algorithm 2**: We acknowledge in lines 289-293 that the constants in Algorithm 2 can potentially be further optimized as part of future work. \n\n[BNSV15] M. Bun, K. Nissim, U. Stemmer, and S. Vadhan. “Differentially private release and learning of threshold functions”. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE. 2015, pp. 634–649."}]

Author rebuttal:

Meta-review: This paper presents a new, efficient algorithm for computing the geometric median of a dataset in a differentially private manner. The proposed algorithm achieves a near-linear runtime, a significant improvement over prior polynomial-time works, while maintaining similar accuracy and sample complexity. The reviewers agree that the paper addresses an important problem and that the results are significant. The improved time complexity is a strong and clear technical contribution. Given the unanimous support and the paper's strengths, my recommendation is to ACCEPT.
Decision: Accept (poster)