Private Geometric Median
Authors: Mahdi Haghifam
Thomas Steinke
Jonathan Ullman
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Differentially Private Convex Optimization
Geometric Median
Primary area: privacy
TL;DR: In this paper, we develop private algorithms for computing the geometric median of a dataset with an adaptive error guarantee.

Abstract: In this paper, we study differentially private (DP) algorithms for computing the geometric median (GM) of a dataset: Given $n$ points, $x_1,\dots,x_n$ in $\mathbb{R}^d$, the goal is to find a point $\theta$ that minimizes the sum of the Euclidean distances to these points, i.e., $\sum_{i=1}^{n} \lVert|\theta - x_i\rVert_2$. Off-the-shelf methods, such as DP-GD, require strong a priori knowledge locating the data within a ball of radius $R$, and the excess risk of the algorithm depends linearly on $R$. In this paper, we ask: can we design an efficient and private algorithm with an excess error guarantee that scales with the (unknown) radius containing the majority of the datapoints? Our main contribution is a pair of polynomial-time DP algorithms for the task of private GM with an excess error guarantee that scales with the effective diameter of the datapoints. Additionally, we propose an inefficient algorithm based on the inverse smooth sensitivity mechanism, which satisfies the more restrictive notion of pure DP. We complement our results with a lower bound and demonstrate the optimality of our polynomial-time algorithms in terms of sample complexity.

Private Geometric Median
Mahdi Haghifam"
Thomas Steinke"
Jonathan Ullman
Abstract
In this paper, we study differentially private (DP) algorithms for computing the geometric median (GM) of dataset: Given n points, , in Rd the goal is to find a point that minimizes the sum of the Euclidean distances to these points, i.e., Ei=1 1 2:112- Off-the-shelf methods, such DP-GD, require strong priori knowledge locating the data within a ball of radius R, and the excess risk of the algorithm depends linearly on R. this paper, we ask: can we design an efficient and private algorithm with an excess eπror guarantee that scales with the (unknown) radius containing the majority of the datapoints? Our main contribution is a pair of polynomial-time time DP algorithms for the task of private GM with an excess error guarantee that scales with the effective diameter of the datapoints. Additionally, we propose an inefficient algorithm based on the inverse smooth sensitivity mechanism, which satisfies the more restrictive notion pure DP. We complement our results with a lower bound and demonstrate the optimality of our polynomial-time algorithms in terms of sample complexity.
Introduction
Differentially private (DP) convex optimization a fundamental task where we approximately minimize data-dependent convex loss function while limiting what be leareed about individual data points. The predominant algorithm for DP convex optimization is DP (stochastic) gradient descent, or DPD(S) for short [SCS13; BST14]. Given a dataset
(()) which contains private information, and loss function F(0; (m)), DP-(S)GD starts with an initial value 0g IRd and iteratively updates using 0c+1 = He (0, (0-00--10 (Vo, (V,, ((0;:(()))++)) where 17 > 0 is the step size, & noise to ensure DP, O C Rd is a closed convex feasible set, and ITe is the Euclidean projection operator. In the most general setting of Lipschitz convex functions, the excess on the radius of the set O and this linear dependence is necessary in the worst-case [BST14). This linear dependence is problematic because we can think of the diameter of the θ capturing measure of the uncertainty we have about the location of the minimizer, and we want our algorithm perform well even with high degree of uncertainty. This linear dependence can be improved under certain unrealistically strong assumptions, such as strong convexity, but it is unclear whether we can improve the dependence on the radius under weaker, more natural conditions. In this paper, as step towards answering this question, we identify a simple. optimization task computnnn the geometric median-wher we can exponentially improve the dependence on the radius.
depends linearly
We study private algorithms for computing the geometric median (GM) of a dataset: We are given set of n data points (a) A (I1,..., x E (Rd)), where I; represents the private information of
Khourr College of Computer Sciences, Northeastern University. Supported by Khoury College of Computer Sciences Distinguished Postdoctoral Fellowship. m. famno Google DeepMind.
Khoury College of Computer Sciences, Northeastemn University. Supported by NSF awards CNS-2232692 and CNS-2247484.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Algorithm
Privacy
Utility [F(An(X (3)); X(
Run-time
Samples
LocDPSGD (Section 3.1)
Approx
1 + vd
OPT
n² log(R/r) +n2d
(dlog(R/r)
LocDPCuttingl1es
(Section 3.2)
Approx
1 +1+ va
OPT
n² log( R/rr +nd + d
SInvS (Section 4)
Pure
(1 (R/r)
OPT
Exponential
d R//) dlog(R/r)
Baseline: DP-(S)GD
Approx
OPT Rva
n2d
N/A
Table I:
Summary of our results. Here OPT arg millieedd F(;; X (1) denotes optimal loss and is the matrix- multiii-uliilliiaiion exponent. The highlighted part is the runtime of the warm-up phase which is the same for LocDPSGD and LocDPCurtingPlane. We also assume that max [X(x) ( Ba(x,, 3n/4. (See Section 3.1, Section 3.2, and Section for the general results without this restriction.) For readability, we omit logarithmic factors that depend on n and d.
one individual, and we are interested in approximately solving the following optimization problem:
0r GM(X arg min F(0; X ()),, where, F(O; x (*)
F(0;X("))
Σ sE(n]
10 x2ll2
(1)
BER
The geometric median generalizes the standard one-dimensional median. The geometric median is a useful tool for robust estimation and aggregation, because it is less sensitive to outliers than the mean of the data, i.e., it a nontrivial estimator even when I 49% of the input data is arbitrarily corrupted. These properties make GM popular tool for designing robust versions of distributed optimization methods [CSX17: WLCG20; FGGPS22; AHISDT22: PKH22; EFGH23], boosting the confidence of weakly concentrated estimators [Min15], clustering [BMM03]. etc.
Baseline for Private GM. Since the geometric median is the minimizer of a Lipschitz convex loss function, we can privately approximate it using the standard approach of DP-(S)GD. In particular, if we know a priori that all the data points lie in known ball of radius R (without loss generality this ball is centered at the origin, i.c., ||2,|p < R for every i E [n]), then DP-(S)GD guarantees (s, with the following excess error [BST14]:
=0 o R (RVllog(1//)
F(DPGD, (x( x(")) F(0": ((m)))( =
As discussed in the beginning of this section, this guarantee has a significant drawback: the excess error of the algorithm depends linearly on the radius R of the a priori bound on the data. This bound could be very loose; it does not scale with the data. Can we do better? What quantity should the excess error guarantee scale with?
is known that the GM is inside the convex hull of the datapoints. However, this convex hull can have a very large diameter due to small number of outliers, while most of the datapoints live in ball with small diameter. key property of GM is robustness outliers, so we want our accuracy guarantee to also be robust to some outliers. Specifically, if 2 51% of the points lie in a ball of diameter A < R then the geometric median is ((A) far from that ball (see Lemma C.6 for a more precise statement). Thus, we aim to design a DP algorithm whose error is proportional to the actual scale of the majority of the data, rather than the priori worst-case bound. However, the algorithm designer does not have a priori knowledge of the location or diameter of a ball that contains most of the data; the algorithm must discover this information from the data. This prompts the following question: Can we design an efficient and private algorithm with an excess error guarantee that scules with the radius that contains majority of the datapoints? Our results provide a positive answer.
1.1 Contributions
Our main contribution is a pair of polynomial-tinn DP algorithms for approximating the geometric median with an excess error guarantee that scales with the effective diameter of the datapoints. Also, the sample complexity and the runtime of our algorithms depend logarithmically on the priori bound R. Both of our algorithms achieve the same excess error bounds up to logarithmic factors, but have incomparable running times. We also give simple numerical experiment on synthetic data proof of concept that our algorithm improves over DP-(S)GD, as presdicted by the theory. In

---

terms of optimality, we show the our proposed algorithms is optimal in terms of sample complexity. Furthermore, we propose an algorithm based on the inverse smooth sensitivity mechanism for the private geometric median problem that satisfies the more restrictive notion of pure DP. Below, we give an overview of these algorithms and the techniques involved.
Polynomial- Time Algorithmss Both of our algorithms for the private geometric median problem are two-phase algorithms: in the first phase, which we refer to warm-up, the algorithm shrinks the feasible set to a ball whose diameter is proportional to what we call the quantile radius in time that depends logarithmically on R. The second phase, which we call fine-tuning, uses the output of the warm-up algorithm to further improve the error.
First, formalize the notion of the quantile radius as the radius of the smallest ball containing sufficiently many points.
Definition 1.1 (Quantile Radius). Fix dataset X()) (x (....... I.)) (Rd)" and 0 RR For every 7 E [0, 1], define An, - m [m] ||,, 01 S A 2 ym).
To motivate the idea behind our algorithms, assume the algorithm designer knew a ball, with center 8g and radius Å such that |10, - 8*1| S O()) and Á = =((Aan/((*))) Then, running DP-(S)GD over this ball would give excess error O (ddsv). This guarantee is particularly interesting as the excess error scales with the quantile radius and not the largest possible norm of any point. Also, by definition of the quantile radius and the geometric median loss function, we have that This inequality shows that an algorithm whose excess error depends on 4mm (0*) has a multiplicattive guarantee rather than the standard additive guarantee for DP-(S)GD. This type of guarantee is particularly desirable for the geometric median since an algorithm with a multiplicative guarantee will be scale free and be adaptive to the niceness of the dataset. However, since we do not know such a pair 8g and Å a priori, the objective of the warm-up algorithm is to privately find these quantities.
F(0"; (m)) 2 (1 - 7)nn,,.(")))
The warm-up algorithm is based on the following structural result: given a point 0 that satisfies |10 10-0011 2 (0*), we have F(0; X ()) - F(O"; x(") 2 100 - 0*I (See Lemma 2.6 for a formal statement.) This result implies that, even though F(0; (")) is not a strongly convex function, we have a growth condition such that the excess error increases with the distance to the global minimizer, at least when the excess error is large enough. (In contrast, strong convexity would imply quadratic growth F(0; X(*) F(O"; ( ž |10 - 0-1]², rather than linear growth.) Intuitively, this growth condition allows us to take larger step sizes and make progress faster, consuming less of the privacy budget. However, since this growth condition only holds for 0 that is more than / (0*) away from the minimizer, which is a data-dependent property, we first need to develop a private algorithm to estimate (0n) (0") in order to make use of this property. In Section 2.1, we develop an efficient algorithm, RadiusFinde assumes that know some potentially very small lower bound r S A3n/4 (fn) which is necessary by the impossibility results in [BNSV15]. Since the sample complexity of this procedure depends only on (1r). we can choose this parameter to be very small. In Section 2.1, we show how to eliminate this assumption at the cost of a small additive error. With high probability, RadiusFinder (see Theorem 2.4) outputs À such that A0m/ < Å < (( )) Having obtained Á, the second step of the warm-up algorithm is finding a good initialization point. In Section 2.2, we propose Localization based on DP-GD with geometrically decaying step sizes, to perform this task. Due the growth condition we show that DP-GD makes a fast progress towards some point that is within O A 4n/5 )(*)) from the optimizer: in log( R)) iterations, with high probability. it outputs fn such that 0* is in the ball of radius O(Å) = O(Aan/s(0*)) centered at 0g.
for this task, which is inspired by [NSV16]. Our procedure
DP Cutting Plane Method for Private GM. The main drawback of using DP-SGD for the fine- tuning stage is that its run-time can be large when >> d. To address this, we design the second fine-tuning algorithm, LocDPCuttingPlanee based on private variant of the cutting plane method that has faster running time when is large. There are two challenges in the analysis: by using the noisy gradients, we cannot argue that the optimal point always lives in the intersection of the cutting planes, which is erucial part of the standard analysis. The second challenge is that the cutting plane method is not a descent method in the sense that the loss function is not decreasing with the iteration, and we need to privately select an iterate with small loss. The challenge for developing the private variant here is that the loss F(0; X (n) has sensitivity proportional to R, running the exponential
3

---

mechanism in the natural way incurs loss proportional to R. We address both of these challenges and develop an algorithm whose excess error is proportional (
Pure DP algorithm for Private Geometric Median Problem. In Section 4, we propose a pure (e, 0)-DP algorithm for the geometric median problem, albeit a computationally inefficient one. Our algorithm is based on the inverse smooth sensitivity mechanism of [AD20]] At a high level, the algorithm outputs & E Rdd with probability proportional to exp(-e Ien (x()), 0)/2) where len X (*), 0) is the minimum number of data points from X(") that needs to be modified to obtain a dataset X (n) such that the geometric median of (() be equal A. Our analysis shows that the proposed mechanism outputs Ô GM(X such that X
(m) differ in at most k* = O (ddlog(R)/45 with a high probability, Then, by a careful sensitivity analysis, we show 110 - 0 can be upper bounded by the ;(0"; (()). Using this result we provide an algorithm with multiplicative guarantee. Moreover, we show ||O 0*| upper bounded ((A)m((') for some y E (1/2, 1].
(n) and X
Lower bound on the Sample Complexity. We show every (e, 8)-DP algorithm requires (vVd/s)
samples so that it satisfies B..... [F(0; ())) s (1 + o)) minger F(0, (*)) for a constant a. This result shows that the sample complexity of our polynomial-time algorithms is nearly optimal.
summary of the results is provided in Table 1, comparing the proposed algorithms in terms of privacy, utility, runtime, and sample complexity. As discussed earlier, algorithms with error adaptive to the quantile radius can achieve a nearly multiplicative guarantee. The utility column in Table I
compares the algorithms based on the achievable a'uul and aadd in order to F(A,, (X( (x))) X (n)) <
(1 + mma) F(0;; X (") + aad with high probability.
1.2 Related Work
DP convex optimization is a well-studied problem [CMS1I; KST12: BST14; ACGMMTZI6: STU17; FKT20J. There has been significant interest in developing new algorithms that offer improved guaran- tees compared (S)GG for specific problem classes or by leveraging additional information. For instance, [LUZ20; SSTT21: ABGMU22; BMS22] demonstrate that for linear models the dependency of the excess error on the dimension can be improved, [GHST24: ABL23] study the impact of the second-order information on the convergence, [KDRT2I; AGMRSSSTT22; GHNOSTTW23] explore the impact of public data, etc. The current paper addresses a drawback of DPD(S)GD, namely, the linear dependence of the excess error on the distance from the initializer to the optimal point in non-strongly convex settings.
Another related line of work to our warm-up strategy is private averaging of INSVI6; NS18; CKMST21; TCKMS22). The advantage of the algorithm proposed in this work is its simplicity while being optimal in terms of sample complexity: we exploit a structural property of the geometric median and show that running DPGD with the geometrically decaying stepsizes can yield a suitable initialization point without the need for preprocessing steps such as filtering [CKMST21; TCKMS22), coordinate- wise discretization [NSV16], 16], hashing [NS18], etc. The proposed quantile radius can be seen as robust notion of radius proposed in [BHIO2].
In one dimension (i.e., d = 1), private versions of the median are well studied [DNPRIO, I0; BNS13; BNSVI5; DNRRI5 15; BDRS18; ALMM19; KLMNS20; ASSU23; CLNSS23). In particular, these works improve the dependence on the priori bound to log" R, rather than log our results.
1.3 Notation
Let d E N. For a vector & E Rdd ||>||| denotes the Ea norm of x. We use the following notation
for the ball of radius R: Ba(a, R) = {i E IRd ||æ all < R}. Also, B3 (a, R) denotes {z e Rd || allxa x0 < Rt.. We refer to Ba R) = (R).., similarly, it holds for B (0, R) = B (R). Let (,,-) denote the standard inner product in Rdd. For a convex and closed subset θ C Rd let He Rdd - θ be the Euclidean projection operator, given by (x = arg min yeelllll lly - x ll2- For a (measurable) space R, MM (R) denotes the set of all probability measures on R. Let Z be the data space and let C Rdd be the parameter space. Let ʃ x 2 - R be a loss function. We say f is L-Lipschitz iff there exists L E IR such that Vz Z, Yu, U E e lf(w,)) - f(e, 2) < L||w e/l.

---

1.4 Notions of DP
Definition 1.2. Let > and 8 (0, A randomized mechanism An 2 (i
(s, (DDP) iff, for every neighbouring dataset (i.e., replacement) X 2" and X' E z", and for every measurable subset M S e, holds 9. (x) (0 E M) S ( M) +
For some of our privacy analysis, we use concentrated differential privacy [DRI6; BS16], as it provides a simpler composition theorem the privacy parameter p adds up when we compose.
Definition 1.3 ([BS16, Def. 1.1]). A randomized mechanism A 2 - M1 (R) is p-zCDP, iff, for every neighbouring dataset (i.e., replacement)
Z" and X' E Z", and for every a E (1, holds D, (An, (X) (X))) & pa, where D, (AA (X) An (X') is the a-Renyi divergence between (X) and A., (
We should think of 2 ²² to attain (e, 0)-DP, it suffices to set 4 log (16)++42 [BS16, Lem. 3.5].
Lemma 1.4 ([BS16, Prop. 1.3]). Assume have randomized mechanism A 2 M1 that satisfies p-zCDP, then for every A is (p + 2 plo)(L
Private Localization
In this section, we present the proposed algorithm for the warm-up stage; it has two steps: Private Estimation of Quantile Radius and Private Localization.
2.1 Step 1: Private Estimation of Quantile Radius
Algorithm describes our private algorithm RadiusFinder for quantile radius estimation.
Algorithm RadiusFinder,
1: Inputs: data set (()) E (Ba(R))" fraction y E (1/2, 1], privacy budget p>zCDP, failure probability 8, discretization error < R.
2: [yn]
3: For every v 2 0 and E [n], let
N.(D) ((()) n Ba(ai v)
> Number of datapoints within distance of v from 4;;
4: For every v 2 0, define
max N(v) distinct ......m [[(n]
{Nr (v) ... + +N, (2))
5: Grid = (r. 2r, 4r... 2 [og (2 ))
6: Queries (N(u) Grid}
7:
18 /2p
2
2R
AboveThreshold Queries, p,
log
log
8
D Algorithm
8: Output Â 28r if Fail; else Output Fail.
Remark 2.1. The runtime of MadiusFinder is O(n2² + n log(n)) log( [R/r])): First, we need to compute the pairwise distances which take n² time. Then, for fixed v, we can compute N(v) using the pairwise distances in time (n?²). To compute Nv)), we need to sort (N:()) in O(n log(n))
time, and pick top m. Finally, we need to repeat this for each ( Dog 2d [1]]].
Notice that Algorithm 1 uses the datapoints as centers for computing the number of the datapoints in a given distance. The privacy proof of Algorithm is based on the following lemma.
Lemma 2.2. Fix N. For every dataset (n), for every 1/2 < 7 S 1 and for every fixed v. the query (v) m max (In.. (N,, (v) + +... N;,. (v)), has a sensitivity upper-bounded by where [yn]] and (1()) & (1) Ba(a,, v/)l. Here Ba(x, v) = tv E Rd Ily z|| vv.
5

---

The objective of Algorithm 1 is to privately approximate 4 (f"). Nonetheless, Algorithm 1 relies on computing the pairwise distances between datapoints. The following lemma elucidates why computing these pairwise distances serves as an effective proxy for computing (0")
Lemma 2.3. Fix E N. S m S T, 71 72 E (1/2,1 1] such that Y22 2 T1, and dataset X X(x) For every 2 O, define N(v) A 1 max (i......mm)) (N₂, (v) +... + Nim (v)), where N((v) - (Ba v) Let l- = GM(X ()). For every i such that (6) 2 [ri]] and ( < [22
have
271
Ayn
S i < 4A yan (0*)
471
Using these two lemmas, in the next theorem, we present the privacy and utility guarantees of Algo- rithm 1. As we are interested in finding the smallest radius, we use the standard AboveThreshold from [DNRRV09; DR+14] as a subroutine in Algorithm 1. The algorithmic description of AboveThreshold is provided in Appendix B for completeness.
Theorem 2.4. Let RadiusFindee
denote Algorithm I. Fix d EN 0,r 0, 3 E (0. 1). and > O. Then, for every n. E N and every dataset ((n) E (Ba(R))* the output of RadiussFindr,, satisfies p-zCDP. Also, the output of RadiusFinder, satisfies the the following utility guarantees:
1. Given (1-7)/2p log(4/3). then P (nm(()) - < )
18
2 1-
2. Assume that the data points satisfies ((r)
Les 7
minfy +
1 36
V2p log (2g log( 2R 1)/3), }.. then, given [1
18
log 4/B), we have
(1-7)v2p
27 1
5
P Ann (0+)
Å < 4 (0*)
2 1
47 1
2
3. Let 7 A minfy + 1 36
log ( 2n + 1)/3). 13. Given >
(1->)v2p 1og(4/3), we have
18
22p
P A (0))
27. 47 4
27 2--1
< Å and { < 40)m(00) or A (r) 2 2
Remark 2.5. A sufficient condition for ((r) < m in Item 2 is that max
[(()) n Ba r) <
m [] Intuitively, this means that no data point should have significant portion of other data points within a ball of radius r centered on
2.2 Step 2: Fast Localization
In the second step the warm-up phase, we develop a fast algorithm for finding a good initialization point using the private estimate of the quantile radius. The main structural result that we use for the algorithm design is stated in the next lemma.
Lemma 2.6. Fix E N. (*) E (Rd)) and 02, 0g E Rd. For every y E [0, 1]. define D.n (Bo) (0n) & min(r 2 0: l E [m] || - Boll S rl 2 yn). Assume there exists Ç 2 0 such that F(01; X())
F(0o; (()) S (n. Then, for every 7 E [1/2,11 1}, we have
(27 1) - -ool 20),,.(00) SC
To gain some intuition behind Lemma 2.6, let us instantiate 8,- 0" This result implies that
for a 0 E R such that ||0 - 01 2 (0')))). the loss function of the geometric median satisfies F(0; X (x")))=F() = (()) Z I|0 - 0 Using this result, propose Algorithm 2 for finding good initialization. The next theorem states the privacy and utility guarantees of Algorithm 2.
Theorem 2.7. Let Localization, denote Algorithm 2.
Fix d E N, R 0, r 0, p 0, and E (0, 1). Then for every dataset ((m) E (Ba(H))" the outputs of Localization, satisfies
p>cCDP. Moreover, let (0, Â) = Localization, (X (m), ,,,,, B) and define random set Qwe = (0
(R) || 6| $ 25.}. Then, given
/ Vdlog( R/rl)
log( ([[/r)
1
[R/r]
n 2 max
log
log
vp
3
vp
3

---

Algorithm 2 Localization,
Inputs: dataset ( (Ba(R))", privacy parameters p-zCDP, discretization error failure
probability B
2: 7 3/4
3: Â RadiusFinder,
(()) 77 2:
Algorithm 1
4: if Á = Fail then
5:
Output Fail and Halt.
6: hiw log(2) log R/A)
b kww S log(2) (og(R/r) with probability one
7: O, = E Rdd T 500, rad,- R
8: for E {0..... kwu
1 do
9:
θ {0 E (R(R)
0ell rad,)
10:
Te rad,
2dkkug 3pm
11:
0 1 DPGD 0₁ (m))
O U/e Twu
Algorithm
2k..
12: rad++1 = rad, + 12A
Output 0s... and Å.
have P (0+ ino and (0.75a(0)) S 4å and { 40a.sn (0*) or A }rr]) assuming that the datapoints satisfies max X (n) Ba(xxrr)) 33/44, we have
2B. Also,
P(0' E Ote and 00.75m (0*) S 4Â and Å 4A0.s (0*) 2 21 11--- 2,3.
3 Private Fine-tuning
In Section 2, we developed an algorithm for the warm-up stage. The output of the warm-up stage is 8o and radius Å such that |0o 0- O()) and Á Ó O(Aan/5(0*) formalized in Theorem 2.7. In this section, we build upon the output the warm-up algorithm to develop two polynomial-tin algorithms for the fine-tuning stage.
3.1 Fine-tuning Using DPGD
Our first algorithm is based on DP-GD [BST14]. The main ideas behind Algorithm 3 is as follows: 1) from the utility guarantee of the warm-up phase Theorem 2.7, the distance of the initialization and only depends on A, i.e., it does not depend on R, 2) By definition the quantile radius in Definition and Equation (I), we have that F00; (n)) > (1 ())AAn((")) (0*). in the case that the data satisfies some regularity conditions, we have < 40o.s (0*) from Theorem 2.7. The next theorem summarizes the utility and privacy guarantees of this algorithm.
Algorithm LocDPGD,
I: Inputs: dataset X (n) E (Ba(H))" privacy parameters p-zCDP, discretization error failure probability B.
2: 0o, À Localization, x 2,
Algorithm
3: On (R)
0oll & 25
4: 50Å,
Gpm2 and Th 256d
n?p
5: 0 DPGD
0o. (n) e Oo, ri. Ti
Algorithm
6: Output 0
Theorem 3.1. LocalizedDPGD, denote Algorithm 3. For every d N, R 0
and B (0, 1]. A [LocalizedDPGD.))..r satisfies the following: for every E N and every
7

---

dataset X E (Ba(R))" R the output of Local satisfies p-zCDP. Also, given
v Vdlog( R/rl]
log( R//r))
1
[R/r]
n
max
log
log
VP
3
have
Va P F (6.:x(m) - (1+0
v log (olog/(()))) F (0;; x(() + +0(1 dlog(1//))
2 1 1 23.
nyp"
Moreover, given that the datapoints satisfies max (x(m) Ba r)] < <3n/4, we have
P P(F(0:x(m) (
(1+0
Vi nVP /og((13)) F (0::x(0))
2 1 22,
where 0 the output of Algorithm 3.
3.2 Fine-tuning Using Noisy Cutting Plane Method
In this section, we present the second fine-tuning algorithm: LocDPCuttingPlare of Algorithm This algorithm is based on the well-known cutting plane method [New65; Lev65; Nes98).
Algorithm 4 LocDPCuttingPaane,,
I: Inputs: dataset X E (Ba(R))", privacy parameters (e, 6)-DP, discrctization error failure probability
+2 p 1olog(2/8)+82
3: Os, Á Localization,
(x)), 2.r, min ( 23)
Algorithm
Ou E Ba(R): : 110 0all S 25
5: kn = e log "v + vd)
b See Assumption for definition of
6: for (O...., 1) do
A: Centre(@.)
D See Assumption
8: Ear ~ N(1, Ta
9: 0 (0 E 0,| (F( x(n)) + 0 01) <0}
10: Define Probability Measure: (t)) x exp (-_ H' (():)(()))
fort E {O...., 1}
448A
Output where f
Similar to non-private cutting plane method, LocDPCuttingPL. is not descent algorithm. As result, we need to devise mechanism for selecting an iterate with minimal loss. In the next lemma, we provide a bespoke analysis of the exponential mechanism with the score function F(0; ((m) defined Equation (1). Note that the sensitivity of F(B: X (n)) is R. However, the next result demonstrates that through novel analysis of the sensitivity of F(0; x()),, the noise scale due to privacy can be significantly reduced. Proof can be found in Appendix E.
Lemma 3.2. Let & E IR, k E N. and d E N be constants. Lei C Rd be a set with a bounded diameter of diam. Let (()) E (Rdy" be dataset and l (M)) Let (01,..., ,00] C θ be k fixed vectors. Also, assume that O E e. Let be such that 3 / )+ + 2diam Consider the following probability measure over [1.....k}.
exp( - 25 F(B;; X (n))
T T(;; ((1)
i [k].
EjEN exp( F(0;
1. Let i ~ x(; (()) and OPT A minsets (F(0;; ((m)) F(0'; x(n)) Then, for every 3 E (0, 1).
we have
P F((0; (1)) - F(O' (w)) < OPT + 2A
log(k/B) 2 21-3. 3.
8

---

2. Let X(n) be dataset size n that differs in one sample from X Then, for every i E [k], we have
exp(-e)x(i (1))) S (ii;; S (xp(e))((; (i"))
The next theorem provides the privacy guarantee of Algorithm 4. The privacy analysis differs from the rest of the algorithms in the paper. This deviation arises from the fact that for analyzing the privacy guarantee of Line 10 of Algorithm 4, we use Lemma 3.2. Notice that the guarantee in Lemma 3.2 holds provided that Op defined in Line 4 of Algorithm 4, satisfies 0 E On. Ergo, the privacy guarantee Algorithm only satisfies approximate-DF?
Theorem 3.3. Lef LocDPCuttingPlane, denote Algorithm 4. Fix d E E,E,N,, R> 0, 0, ò E (0, 1}, and 3 E (0, 1]. Then, for every n E I4 and every dataset X(x) (Ba(R))" the output of LocDPCuttingPlang satisfies (e, 6)-DP.
We also make the following assumption about the performance of Centre subroutine Algorithm 4.
Assumption 1. There exists some T E (0, 1] such that for all t ko....,,kp 1 1]. the subroutine of Centre in Algorithm 4 satisfies vol(Or+1) (1 r))ol((,)) Furthermore, the time for calling the routine Centre Te.
Using the John Ellipsoid [Joh14] as the Centre makes dimension independent constant and T. +w) (by [LSWI5]). Now we are ready to state the utility guarantee of Algorithm
Theorem 3.4. Let LocDPCuttingPlane, denote Algorithm For every d E R 0. E > 0, 6 E (0, and 3 E (0,1), A = [LocDPCuttingPlans In21 satisfies the following: for every n E N and every dataset ((m) E (Ba(R))), given
V d R/rl)
log( (e((l
[R/r]
n 2 max
log
log
Vp
3
3
where
we have the following:
Let K &
ayD vd
+ vd and a =
16 1olo
o (V dlog(n)) log
<log(<)) +8
Then,
P (0:x(()) S (1+ a) (1+1)) F(0 x(n)) + ra)) 2 2133,
Moreover, assuming thut the datapoints satisfies maxte(m) (((1) n (B((Is,)) []] < 3n/44 we have
((F(0: = ( F(00; 21-33
where i is the output of Algorithm 4.
Pure-DP Algorithm for Geometric Median
In this section, we propose an algorithm based on the assumption that we have an access to an oracle that outputs an exact GM X (.)). Before presenting the algorithm, we need a definition: For two sequences of a = (a1, an) E (IRd)" and = (bI,...,by br)) E (Rdy", we define the hamming distance dH b) > Di [a; A bj]. The proposed algorithm shown in Algorithm 5, and its utility and privacy guarantees are presented in the following theorem.
Theorem 4.1. Let SInvS, denote the algorithm in Algorithm S. Fix d E N, R> 0, and & > Then, for every n E N and every dataset X (Ba(R))" the output of SInvS, satisfies c-DP. Also. for every 3 E 1) and for every T. 2k* A 2 least 1 - B, we have:
2 (log(1/3) dlog(R/r)) with probability at
The value of the cost function satisfies
4k*
F(0:x()) < (1+
F(0"; nr.
n1 2k

---

Algorithm 5 SInvSn
Input: dataset X(") E (Ba(R))", privacy parameter e-DP, discretization error
2: For every y E (R(
len, v) - min {d (m), (() such that 32 E Ba(y.r) with GM(X
X)(Rd)"
exp( - len, (X, 3)
3: Define density: dy(
1 e Ba(R))
()BB exp(-$ (x, v)) dy
4: Output ~ n
In terms of distance,
|0 0+
0+| sr+
(0))
min 1E(1/2.1)>> + 22(1 - k2/n// - -
The proof of Theorem 4.1 provided in Appendix The proof based on showing that the output
θ GM (() is such that (n) and (n) differ in at most k (d R)/e) datapoints with high probability. Then, we use the properties of the geometric median to show that the sensitivity of GM to changing lo < n1/2 points can be bounded by the value of the optimal loss at = GM(X()))
Lemma 4.2. For every n N and for every < 2" and for every (#1,.... ... Fnz U1....... Meb (Rd)) define 9o = GM((Z1,..... (n)) and 0x GM, En V..... "........... (.)). Then,
2
| 0oll
F(Oo: Tw))) 2k
5 Lower Bound on the Sample Complexity
In this section we prove lower bound on the sample complexity of any (c, 6)-DP algorithm for the task of private geometric median with multiplicative error.
Theorem 5.1. Let Eg. Clp, do be universal constants. Then, for every S Eo. a S ag, and d z do and every (e, DDD algorithun An : (Rd)" - (RR)) (with 5 = ((Vd/n)) such that for every dataset S (1+ + a) mingeBr F(0; X X
(()) E (RRd)n its output satisfies Eg-An(X()) [F(0] (0:x(")) }
we require n = 52 vd
This result, whose proof can be found in Appendix G, shows that the sample complexity of the proposed polynomial time algorithms is tight in terms of the dependence on and d.
Numerical Example
200, 3000, = 2,5 1/0
Ours
In this section, we numerically compare LocDPGD,, (Algorithm 3)
Fi0: P0 W00 g00
DPGD
and DPGD synthetic dataset. The dataset consists of two subsets: one tightly clustered at a random location on (R), and the other uniformly distributed over (R). We plot F(0; / F0*; (m) for both algorithms R varies. The results show that LocDPGD,, 's performance degrades more gracefully than DP-GD with increasing R. See Appendix H for experimental details and more results.
Conclusion and Limitations
In this paper, we presented three private algorithms for the geometric median task, ensuring an excess error guarantee that scales with the effective data scale. Our results open up many directions: believe our warm-up algorithm has broader applications, and finding other problems where it can be used subroutine is interesting. Another direction is characterize the optimal run-time: possible to develop linear time algorithm, i.e. ((nd), with an optimal excess error?
10

---

Acknowledgments
The authors would like to thank Jad Silbak, Eliad Tsfadia, and Mohammad Yaghini for helpful discussions.
References
[ACGMMTZ16]
M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L.. Zhang. "Deep learning with differential privacy". In: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 2016, pp. 308-318.
[AHJSDT22]
A. Acharya, A. Hashemi, P. Jain, S. Sanghavi, I. Dhillon, and U. Topeu. "Robust training in high dimensions via block coordinate geometric median descent". In: International Conference on Artificial Intelligence and Statistics.
PMLR. 2022, pp. 11145-11168.
[ASSU23]
M. Aliakbarpour, R. Silver, T. Steinke, and J. Ullman. "Differentially Pri- vate Medians and Interior Points for Non-Pathological Data". arXiv preprint arXiv:2305. 13440 (2023).
[ALMM19]
N. Alon, Livni, M. Malliaris, and S. Moran. "Private PAC learning implies finite Littlestone dimension". In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019, pp. 852-860.
[AGMRSSSTT22]
E. Amid, A. Ganesh, R. Mathews, Ramaswamy, Song, T. Steinke, V. M. Suriyakumar, O. Thakkar, and A. Thakurta. "Public data-assisted mirror descent for private model training". In: International Conference on Machine Learning. PMLR. 2022, pp. 517-535.
[ABGMU22]
R. Arora, R. Bassily, C. Guzmán, M. Menart, and E. Ullah. "Differentially private generalized linear models revisited". Advances in Neural Information Processing Systems 35 (2022), pp. 22505-22517.
[AD20]
H. Asi and J. C. Duchi. "Instancc-optimality in differential privacy via ap- proximate inverse sensitivity mechanisms" Advances in neural information processing systems 33 (2020). pp. 14106-14117.
[ABL23]
M. Avella-Medina, C. Bradshaw, and P.-L. Loh. "Differentially private inference via noisy optimization". The Annals of Statistics 51.5 (2023), pp. 2067-2092. M. Bădoiu, S. Har-Peled, and P. Indyk. "Approximate clustering via core- sets". In: Proceedings of the thiry-fourth annual ACM symposium Theory of computing. 2002, pp. 250-257.
[BH102]
[BMS22]
R. Bassily, M. Mohri, and A. T. Suresh. "Differentially private learning with margin guarantees". Advances in Neural Information Processing Systems 35 (2022), pp. 32127-32141.
[BST14]
R. Bassily, A. Smith, and A. Thakurta. "Private empirical risk minimization: Efficient algorithms and tight error bounds". 2014 IEEE 55th annual sympo- sium foundations of computer science. IEEE. 2014, pp. 464-473.
[BNS13]
A. Beimel, K. Nissim, and U. Stemmer. "Private learning and sanitization: Pure vs. approximate differential privacy".. In: International Workshop on Approxi- mation Algorithms for Combinatorial Optimization. Springer. 2013, pp. 363 378.
[BMM03]
P. Bose, A. Maheshwari, and P. Morin. "Fast approximations for sums of distances, clustering and the Fermat-Weber problem".. Computational Geometry 24.3 (2003), pp. 135-146.
[BDRS18]
M. Bun, C. Dwork, G. N. Rothblum, and T. Steinke. "Composable and versatile privacy via truncated cdp". In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018, pp. 74-86.
[BNVV15]
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.
[BS16]
M. Bun and T. Steinke. "Concentrated differential privacy: Simplifications, ex- tensions, and lower bounds".. In: Theory of Cryptography Conference. Springer. 2016, pp. 635-658.

---

[CMS11]
K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. "Differentially private empir- ical risk minimization" Journal of Machine Learning Research 12.Mar (2011),
pp. 1069-1109
[CSXI7]
Y. Chen, L. Su, and Xu. "Distributed statistical machine learning in adversarial settings: Byzantine gradient descent". Proceedings of the ACM on Measurement and Analysis of Computing Systems 1.2 (2017), pp. 1-25.
[CKMST21]
E. Cohen, H. Kaplan, Y. Mansour, U. Stemmer, and E. Tsfadia. "Differentially- private clustering of casy instances". In: International Conference on Machine Learning. PMLR. 2021, pp. 4049-20559
[CLNSS23]
E. Cohen, X. Lyu, Nelson, T. Sarlós, and U. Stemmer. "Optimal differentially private learning of thresholds and quasi-concave optimization", In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023, pp. 472- 482.
[CLMPS16]
M. B. Cohen, Y. T. Lee, G. Miller, J. Pachocki, and A. Sidford. "Geometric median in nearly linear time". In: Proceedings of the forty-eighth anmual ACM symposium Theory of Computing. 2016, pp. 9-21.
[DNPRIO]
C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum. "Differential privacy under continual observation". In: Proceedings of the forty-sssenonn ACM symposium Theory of computing. 2010, pp. 715-724.
[DNRR15]
C. Dwork, M. Naor, O. Reingold, and G. N. Rothblum. "Pure differential privacy for rectangle queries via private partitions". In: International Conference the Theory and Application of Cryptology and Information Security. Springer. 2015, pp. 735-751.
[DNRRV09]
C. Dwork, Naor, O. Reingold, G. N. Rothblum, and S. Vadhan. "On the com- plexity of differentially private data release: efficient algorithms and hardness results". : In: Proceedings of the forty-first annual ACM symposium on Theory of computing. 2009, pp. 381-390.
[DR+14]
C. Dwork, A. Roth, al. "The algorithmic foundations of differential pri- vacy". Foundations and Trends@ in Theoretical Computer Science 9.3-4 (2014), pp. 211-407.
[DR16]
C. Dwork and G. N. Rothblum. "Concentrated differential privacy". arXiv preprint arXiv: 10XXv:6603.00 603.01887 (2016).
[FGGPS22]
S. Farhadkhani, R. Guerraoui, N. Gupta, R. Pinot, and J. Stephan. "Byzan- tine machine learning made easy by resilient averaging of momentums". In: International Conference
Machine Learning. PMLR. 2022, pp. 6246-6283.
[FKT20]
V. Feldman, Koren, and K. Talwar. "Private stochastic convex optimization: optimal rates in linear time". " In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. 2020, pp. 439-449.
[GHNOSTTW23]
A. Ganesh, M. Haghifam, M. Nasr, S. Oh, Steinke, O. Thakkar, A. Thakurta, and L. Wang. "Why is public pretraining necessary for private model training?" In: International Conference on Machine Learning. PMLR. 2023, pp. 10611- 10627.
[GHST24]
A. Ganesh, M. Haghifam, T. Steinke, and A. Thakurta. "Faster differentially private convex optimization via second-order methods". Advances in Neural Information Processing Systems 36 (2024).
[Joh14]
F. John. "Extremum problems with inequalities as subsidiary conditions". Traces and emergence of nonlinear programmingg (2014), pp. 197-215.
[KDRT21]
P. Kairouz, M. R. Diaz, K. Rush, and A. Thakurta. "(Nearly) Dimension Inde- pendent Private ERM with AdaGrad Rates via Publicly Estimated Subspaces". In: Proceedings Thirty Fourth Conference on Learning Theory. Ed. by M. Belkin and S. Kpotufe. Vol. 134. Proceedings of Machine Learning Research. PMLR, 15-19 Aug 2021, pp. 2717-2746.
[KLSU19]
G. Kamath, Li, V. Singhal, and Ullman. "Privately learning high- dimensional distributions" In: Conference Learning Theory. PMLR. 2019, pp. 1853-1902.
12

---

[KLMNS20]
H. Kaplan, K. Ligett, Y. Mansour, M. Naor, and U. Stemmer. "Privately learning thresholds: Closing the exponential gap". In: Conference on Learning Theory. PMLR. 2020, pp. 2263-2285.
[KST12]
D. Kifer, A. Smith, and A. Thakurta. "Private convex empirical risk minimiza- tion and high-dimensional regression". In: Conference on Learning Theory.
2012, pp. 25-1.
[Ksc17]
F. Kschischang, "The complementary error function". Online, April (2017).
[LM00]
B. Laurent and Massart. "Adaptive estimation quadratic functional by model selection". Annals of Statistics (2000), pp. 1302-1338.
[LUZ20)
H. Lå Nguyen, Ullman, and L. Zakynthinou. "Efficient private algorithms for learning aage-margin halfspaces". In: Algorithmic Learning Theory. PMLR. 2020, pp. 704-724.
[LSW15]
Y. Lee, A. Sidford, and C.-w. Wong. "A faster cutting plane method and its implications for combinatorial and convex optimization". In: 20/5 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE. 2015, pp. 1049-1065.
[Lev65]
J. Levin. " "An algorithm for minimizing convex functions". Dokl. Akad. Nauk SSSR 160 (1965), pp. 1244-1247. ISSN: 0002-3264.
[MT07]
F. McSherry and K. Talwar. "Mechanism design via differential privacy". In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07).
IEEE. 2007, pp. 94-103.
[EFGH23]
E.-M. El-Mhamdi, S. Farhadkhani, R. Guerraoui, and L.-N. Hoang. "On the strategyproofness of the geometric median". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2023, pp. 2603-2640.
[Min15]
S. Minsker. "Geometric median and robust estimation in Banach spaces" (2015).
[Nes98]
Y. Nesterov. "Introductory lectures on convex programming volume Basic course". Lecture notes 3.4 (1998), 5.
[New65]
D. J. Newman "Location of the maximum unimodal surfaces". Journal of the ACM (JACM) 12.3 (1965), pp. 395-398.
[NS18]
K. Nissim and U. Stemmer. "Clustering algorithms for the centralized and local models". In: Algorithmic Learning Theory. PMLR. 2018, pp. 619-653 K. Nissim, Stemmer, and Vadhan. "Locating a small cluster privately". BAROOD-SGGACT-IGAAA Symposium Principles of Database Systems, 2016, pp. 413-427.
[NSV16]
In: Proceedings of the 35th ACM
[PKH22]
K. Pillutla, S. M. Kakade, and Z. Harchaoui. "Robust aggregation for federated learning". IEEE Transactions Signal Processing 70 (2022), pp. 1142-1154,
[Shal1]
O. Shamir. "A variant of azuma's inequality for martingales with subgaussian tails". arXiv preprint arXiv: 10.1292292 (2011).
[STU17]
A. Smith, A. Thakurta, and J. Upadhyay. "Is interaction necessary for distributed private learning?" R In: 2017 IEEE Symposium on Security and Privacy (SP). IEEE. 2017, pp. 58-77.
[SCS13]
S. Song, K. Chaudhuri. and A. D. Sarwate. "Stochastic gradient descent with differentially private updates". . In: 2013 IEEE global conference signal and information processing. IEEE. 2013, pp. 245-248.
[SSTT21]
S. Song, Т. Steinke, O. Thakkar, and A. Thakurta. "Evading the curse of di- mensionality in unconstrained private glms". In: International Conference Artificial Intelligence and Statistics. PMLR. 2021, pp. 2638-2648
[TCKMS22]
E. Tsfadia, E. Cohen, H. Kaplan, Y. Mansour, and U. Stemmer. "Friendlycore: Practical differentially private aggregation". In: International Conference on Machine Learning. PMLR. 2022, pp. 21828-21863.
[WLCG20]
Z. Wu, Q. Ling, T. Chen, and G. B. Giannakis. "Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks". IEEE Trans- actions Signal Processing 68 (2020), pp. 4583-4596.
13

---

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:
The abstract and the introduction completely summarize our findings.
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 the paper and important assumptions and limitations. A No or 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.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
In Section we discussed two limitations of our work.
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 encouraged to create separate "I "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 with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 address problems of privacy and fairness.
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 in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification: In our problem setup, we completely discussed all the assumptions. Also, complete proof of every claim is presented in the appendix.
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 to provide a short proof sketch 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 affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Appendix H, we discussed all the details behind our implementation. Also, we release the code. Since the dataset considered is synthetic, there is no concern regarding the dataset.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer 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.
the contribution is a 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 is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of 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 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 a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
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 way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to 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 (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We have released the code along with a Colab notebook.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.cc
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for 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 NeurIPS code and data submission guidelines (https: httpol/c/ggid////eeieooee
/ //nips.
cuubmissiooPaai wwsssssloiioiooo for more details.
The authors should provide instructions on 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. If 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 much information 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: In our experiments, we compare our proposed algorithm with a well-known baseline. We implemented our algorithm from scratch. Also, all the details are included in the code and Appendix H.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to 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: We have included the error bars in the plots.
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).
16

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It 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 figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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: Our results can be produced using public Google Colab.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: tttpps:/mnet /ttp///eeerpppeeeeee/ee httppp/cce/tttttccccseeeeeeleeee
Answer:[NA]
Justification:
This question is not applicable to our paper.
Guidelines:
The answer NA means that the authors have 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 in their jurisdiction).
10. 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 does not have any societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
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.
17

---

The conference expects that many papers will be foundational research and not tied 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 an 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 a 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
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:
It is not applicable to our work.
Guidelines:
The answer NA means that the paper poses 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 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Not applicable to work.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paper swi thcode. com/ 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.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: It is not applicable to work.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing 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: is not applicable our work.
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 as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at Ieast 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 or institution) were obtained?
Answer: [NA]
Justification:
is not applicable to our work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

A Preliminaries
A.1 Gradient of the Geometric Loss
0 +
Vo(110- =x]]
|0-
0 = Ø
A.2 DP Gradient Descent (DPGD)
In this section, we provide the algorithmic description of DPGD and its privacy and utility analysis for completeness.
Algorithm 6 DPGD
1: initialization Rd, dataset (n) (R*)(m), privacy budget p. feusible θ, stepsize 7) number of iterations
2:
= T
2pn
3: (l....: 7)
01t1 = (T - -V(F(((; &.)).
where (( 4: Output + Eia 0.
Lemma A.1. Ler θ S Rd be a closed and convex set with a finite diameter diam. Let e θ 2 - +R R be loss function such that for every 2 2, E(.,2) is convex and L-Lipschitz. Let X
(zI,..., kn) E n and (0) CiEpn) E(O, z4). Consider DP-Gradient descent algorithm 0.+1 = (0: - m/( V. (0.) ) + +.))), where & N00 Ta)- Then, for every E N, by setting ? diam, 12 and 0² 1,T,
2pnz. we have the following: {0s (Be)) satisfies p-zCDP. Also, for
every B > 0, given Td 2 log(4/3) and S /56log(2/B), with probability at least 1 B, we have
16vd nVP
V2 VT
in
Σ 02 LE[T]
min (n) S diam
Vlog(2/3)
T
8Ee
Proof. The privacy proof is based on the zCDP analysis of the Gaussian mechanism and the compo- sition property zCDP [BS16].
Let 9: - L.n (0.) + & and 6* E mingee (0). Note that we can replace (O.) by any subgradient 6, By the convexity of l and the first-order convexity condition we can write
in
Σo, 0, - (.)) LE(T]
< Σ (o.) - (.n)0)
T
iE(T]
Σ (0.) - -0)) KE
Then, by the contraction property of the projection, we can write ||0
1-1
[T (6: -ng+)= 11
s || - 8" - "gell" 1|
|00: 0r 1-12 + + 1191199111 22//11, Oz 0*)
110, or 12 + 2n² (1 VÍ (0:) + +115x11) 2n/ O2 - 0*)
10: 0* 1 + 27y² 1 2ny 11:.11 - 22 0, Q*).
Here, we have used for every a, Rdd, ||e + b11 < 2||||| +2|1b|1 and Vin (0)
< L for every
0. Therefore, we conclude that
(ge, 0g 0*) < 2m
(100, 0- - |10 - 0-113) + > + 12..
(4)
20

---

Define the following random variable for every E [T]
Y y= = (VL(((n)))) 0: - 0*) - 01 87)
(5)
Also, define the following filtration
Fe = (B
(6)
which is the sigma-field finna-fieldda generated by oo...., ,,.
Lemma A.2. (Yihe is a martingale difference sequence adapted to {FiJeEmm
Proof. Notice that V L..(0),, (0:), O., and 0 are F:-measurable. Therefore, we can write
v Fil = (g, 0: - 8*) ( (vi. 0: - - 1
= (B(g Fi), 0g 0*) (v (O.), ON 0²).
By definition & is independent of the history up to time Therefore, F((T|/F = 0 since [[Gr] = which gives
E Fi] = ((V + & (O.,,
(7)
Therefore, [[ = 0. Moreover, by Cuachy-Schwaan inequality and the boundedness of θ we can write
E|| = El[(s, A2 - 1] = ||ll@ 8* - REII&: || < 60.
(8)
Therefore, her is martingale difference sequence as was to be shown.
Using Equation (4) and by the definition of Y, in Equation (5), write
(VLn O. 8+)
(110,
0-1 -1 0*1 +n
Eell nL2 Yv.
211
Summing it from to T gives
(L.(),)) 0-)
5 29/T
100 -0-122 +
7
Σ tE(T]
| + +n² + T Σ Yr
T (E(T]
T
AE(T]
S
R²
+ 11T
+
7
Σ
||Ee|1
+ T
Σ Ye-
(9)
2TTT
T
[E[T]
KE(T]
(4)
(B)
Analyzing (A) in Equation (9)
Notice that El 12 - 0² 0212111 Therefore, for every B E (0, 1) provided that Td 2 log(4/B).
with probability at least - 3/2, we have
log(?/8)
Σ :E(T]
1 < no²d
1+41
(10)
Td
Analyzing (B) in Equation (9)
Lemma A.3 (Shamir [Shal1]), Let N. Let { be martingale difference sequence
Ime
adapted to a filtration {F m ImeMM] M and suppose there are constants b and > 0 such that for any m and any a > O, it holds that
P([ 2 alFi) S bexp((ccc'
Then for any 0, it holds with probability at least that
28b (1g(1
Σ 7m S
M
cM
mE(M]
21

---

We can rephrase Equation (5) as
Yi (VLn(00), 00) - 01 --)) = (Ee, 0" - 01).
Notice that condition on Fri (5r, 0* 0,) ~ NOO,
02 02
0" p²112). Therefore,
a²
a²
(() # 0c)l 2 aFFi) - 2 exp
- 2exp
20 @x1
20 R
Note that the bound holds for every [T]. Therefore, using Lemma A.3, with probability least 1 8/2, we have
28 log(2/3)
Σ
(5, 01) s R
(11)
TE[T]
From Equation (9), Equation (10), and Equation (11), we have with probability at least
R²
1og(4/3)
28
281og(2/3)
0:
min (0) -
+ nI. + no²d 1 + 1V
+ 20 RoRV
T
8E8
2n/T
Td
T
LE[T]
(12)
provided that Td 2 log(4/3)). Let
o² L
R
2pn2
LVT
+ /
5dT pn
Using these parameters, we obtain that
RLVd
2pn?
in
Σ Oi (E[T]
min
(0)
11+ Td
(56log(2/B)
T
AE
nyp
(13)
2RLVd
RLV2
(56log(2/3)+
nVP
VT
where the last step is by assuming that S /56log(2/5)
B Above Threshold Algorithm
Algorithm 7 AboveThreshold
1: Inputs: Queries (Sa, SR-1), Privacy Budget p-zCDP, Threshold T.
Eresh Lap V3p
7 Enesh
4: for E [K] do
5:
& Lap
V2D
6: if ft
T: then
7: Output Å = i.
8: Halt
9: Output Fail.
C Technical Lemma
Lemma C.I. Let a > O. Let Y be a random variable with the distribution (0, o2). Then, for every
(0, 1), we have TP ( (2log((/B) S 3.
22

---

Lemma C.2 (Laurent and Massart [LM00]]. Let m E N. Consider random vector Y (0 Im). Then, for every 2 0,
|||] 2 m + 2V tm + S exp(-()
Corollary C.3. Let (0, 1), m E and m log z. Consider
NN Im), then
1og(2/a) m
S | S m (1 1 + (1+ log(2/s)
m 1
2 1 11-3, 3
m
Lemma C.A. Let N and n 4. Let Xim) (RRy" and (()) (IR)) be two datasets that differ in one sample. Let H* GM(X and 8o E GM(X(")). Ler ( be the radius of the ball around 0r that contains at least 3n/4 of X(n) Then,
0 0-1 |1= Asn)s(0").
Proof. The proof is by contrapositive. In particular, show that for every O E Hd such that 10 0*11 A0sn/a(0)), we have, 0 & GM(X(")). Let I {i E [n] : æ; (a (0*) and I E { Using the variational representation of |1-1|g- we can write
0 0*
VF(0; (())
10 A-
Σ
0 x2
0 0*
0 0 z;
0 0*
110 mml
|00 A'
|10 z.|l
10 8+
0 - Tz
0 A*
(n
[Z]
100 0-
RE
where the last step follows from Mauchy-Schwenh inequality. Then, we can write
/Asn/a(0)) -(n (n- [Z])
VF
2 z
100 8-1l
1 V 11- (Asm/s(00)) 2
= I I
n
110 - 6-1l
(14)
Aan/a(00)
(3n/4)
1+ V1 1+
110 0+1|
n
N (3n/4)
1+ /I - 4/9) 1-///
00
Therefore ||@ 88 < 3/2A
Lemma C.5. For every n E N for every (m)) (II,,..., In), we have (X() lies the
convex hull of (I1,..., Rn).
Lemma C.6. Let (I In) (Rdy be dataset and 0r GM( v.)) Let B S [n] such that [ < n/2. Then, for every 0, we have
2n - B
10 0-
<
max 0 xi|]-
Y1 2
Proof. is simple modification of [CLMPS16, Lemma. 24].
23

---

D Proof of Section 2
Proof of Lemma 2.2. The proof follows closely INSVI6, Lemma 4.5]. Let X and X' are two neighboring datasets of size n that differ in the first sample. For a fixed v and i E [n], i 1, (.) change by one. Also, in the worst-case the new datapoint can be close to the rest of the datapoints. Therefore, the sensitivity is bounded by 1 ((m- - 1) + n) I 1+ 11+ S where the last step m
follows from y 2 1/2.
Proof of Lemma 2.3. Let & be such that (2) 2 [n by definition of [N))) it means that there exists datapoint z; such that the ball of radius i around it contains at least [ni]] datapoints. Let
B = (j E [m] ||:; æi > }) By the described argument, we have [3] v (1 - "n )m. Then, we
invoke Lemma C.6 with the described B and x; obtain
2n 2(1 7mm
110 xill
n - 2 -
271
2 - -1 D.
The first step follows because function h: RR + R, h(2)
2n-22 is increasing for z < n/2. In the n- 25
next step, use the triangle inequality write
A Ayn((')) S A ni (2x) 1|2 001
271 1
S ò +
271
471 1
2/11 D,
where A. (-) is defined in Definition 1.1.
Next, turn into proving the upperbound on D. By assumption (D/2)) < [2gn].
1. For the sake
of contradiction, assume that & > 44 Then, consider the set G = {i E [n] =10* x4 S
A Anga (0=)). By definition, |9] 2 [12m]. Consider arbitrary subset of G with the size of [2n]] The main observation, which follows from the triangle inequality, that a ball radius 24 oan (8*) around
every point in G contains at least [ygm] datapoint. Therefore, N(0/2) 2 N(2A van (8)) 2 h1nn
which contradicts with the assumption that (6/2) < [12n].
Proof of Theorem 2.4. The privacy proof simply follows from the privacy analysis in [DR+14, Sec. 3.6]. We focus here on the utility guarantees.
Part 1: Let k [log(
22 11 is simple see that
P Å Fail) S (P(N(2*)) + E S + Ethresh)
PPn S Ethresh Ex)
- (1)((11()) 7)m & Ethresh - Ek)
æz S 2R, which gives us (2*r)) = n by the definition of N-.). By a simple tail bound on the Laplace distribution, we
where the last step follows from the assumption that max,; ex((m) (00m)>lzz;
have Laheehh 2 22p log(4) (4)3) < 8/4 and IP (16x 2 12 log(4/3)) s 3/4. Therefore, given n V2p log (/)), P(nn m S Eibresh - (x) $ 8/2.
Part 2: Lemma C.6 implies that for every v such that N(v) 2 [ym], we have, 4,n (ft). 27-1 -4-1 S v.
Therefore, we can write
27 A (0))
27 > 2 <P <P(NN (A) < <nril). 47 S A 2 2P(N <P(N(A) 2 [ym]] + P A (80)
47
Consider
P( ((((A) < /ml) s <P(N(A) < [rr]] and Å + Fail) + +P(A =Fail).
(15)
24

---

Under the event that Á + Fail, there exists i E fo.....k k - 1}, such that
18
N(Ā) + & 2 m +
log(2(k: + 1)/3) + Sihresh
22p
By simple tail bound and union bound, we have
6
12
P(B) & Ethresal 2
1og(2(k + 1)/3) and {max &il 2
+ 1)/81} log(2(k+1)/88))
V2p
/2p
(16)
S 3/2,
where k = =loog( 2 2. We further upperbound the first term in Equation (15) as follows
N (N(A)) < [yn] and Å + Fail) s P (N [m]] and Å * Fail and 1²) + P(
We claim that the first term in this equation is zero. Recall that m = [yn]. Under the event B 18 log 1)/3) and as result, + 18
Sthresh 2 v2p
/2p log (2g( + 1)/3) + Eiuesh ç, 2 m.
Therefore, shows that the probability of the first term is zero. Also, as showed above, P(B) _ 3/2. Therefore, TP N ( < [xm]) s PP(B) + P Fail). Combining with Á Fail s 3//2 concludes the proof.
Part 3: Assume that (r) < m. Let h: = [log( 28
Let 5 = + 18 v20 log(2(k: + 1)/3). In
r
Part 2, we showed that given n >
18 <2p
log(4/33 we have
27 1
yn (0*)
47 - < A 21 3.
We only focus on the upperbound. From Lemma 2.3, we have
P(A s (0)) 2 TP N (A/22) = [iml) + (P (0))((0)) s <P(N(A/2) > +[iml)
(17)
We can write
P (NN(A/2) > [im])
S <P(N N (O(N(A))) A/2 [īm] and Å $ {r, (a,)))
P (r,Fail))
< <P(N N A/2))
[in] and Å (r, + PA
P P(A=Faal)
where the last step follows from the union bound. For the first term, we have
P P( [in] and Å & {r, Fa,1))
=P N A/2 [in]] and å & Fr,Fail) and N(Å/2) + + < log
18
2
2R
log
Eirresh
B
(18)
where i = log (//2r) 1. The last step follows from the following observation: under the event that Á $ Fail), during the execution of Algorithm 7, both N(Ā) and N(Á22) compared to the noisy threshold. Using the tail bounds in Equation (16), we have under the event B", with probability least 1 B/2.
18 22p
2R 2 r ))
18
2R
1)
18 log(2(k: + 1)/3)
m +
log
log
+ Eihresh - <3 S m +
log
log
+
22p
3
22p
36
m +
log (2(k + 1)/8).
22p
This shows that we have
NN (A/2)
18
12R
)) + Emrcsh 31/2.
[in] and Å $ Fail) and ((A22) + < m+
log
log
3
25

---

In the next step, we bound P P(A= r). Notice that
P(A=r) =
(()) (B
18
2 3
2R llog
1) Sthresh
+ E1 > m + log
log
V2p
Using simple tail bound, we have P Ethresh - E1 S v2p
log
(R)
S 3/22 which shows
that IP Å r) $ /3/2 since we assume that N(r)) < m. Therefore, combining all the pieces together,
proved
27 44-1 - Å < 44 (m 2 1 P Ann (0)) (0))
5,3 2
Part 4:
In Part 2, we showed that given
(1-7)v2p 1og(4/3) we have
18
27
TP
Å A ym
(8*)
4vy - S.
(19)
{ A < im (f*) or À =r]. We have
Consider the following event & =
P(E)) = ( Á 44 (0*) and Å + r)
$ P Â > 40jm (6*) and Â + fr. Fail)) + P(A = Fail
< N A [5m] and Å + (r. Fail)) + P A Fail
Here, the last step follows from Equation (17). Notice that in Equation (18), we analyzed the probability of the first term and we showed that it is most 3/2. We also have that P Á = Fail) s 3/2 from Part 1. Therefore, P(E S B. Combining it with Equation (19) concludes the proof. O
Proof of Lemma 2.6. Let I = {i E [n] 1160 - xil S 4m (fo))- For every i E I, we have ||> Boll I (0)) Using the triangle inequality, for every I, we can write
|00 2; 2 ||0] Ooll - |100 xz|
2 1|0 Goll (2A,.. (0)) 110. =zll).
The last equation is equivalent to
||0 . 10, ., 2 10 0oll 2m,mm (0u).
(20)
Then, for every $ I, by an application of the triangle inequality
||0 2; + |00 6nl 2 160 x;1l
(21)
(+)1 xxil - |10 x; 2 -1101 Gll
Then, by adding both sides of Equation (20) and Equation (21), we have
(()) F(f;; (()) 2 | [|0 - Poll (n - [ Gall - 2/ (m.()))
This equation can be represented as
F(B:: X (m)
F(oo; x()) A,.
||0 Pol -
2
(22)
$ <n + 2| (8o)
I
Let = [Z]. We know that 7 2 7. Using this representation we can write
|00 0oll S + 2 A.n (On)
2/'
For a fixed a, b > define h(x) A 2+bbb For x > 1/2,
dh(w) 2(a+6)
This shows that l(x)) is
2x-1
dar
[2x 1)2
decreasing for 1/2. Therefore using this observation
+ 27' Am (fo) < 2 A An (0o)
27 -1 <
27
to be shown.
26

---

Proof of Theorem 2.7. The privacy proof is straightforward. Algorithm 2 uses the data in Line 3 and Line 11. Based on the privacy budget allocation and the composition properties of zCDP, we can show that the output satisfies p-xCDP.
For the claim regarding utility, in the first step, consider the recursion in Line 12 of Algorithm i.., rad,+1 1 = radd 12 initialized rado R. It can be easily shown that radm 2 rado +
12Á Σ = (1/2)* for m 2 1. In particular, let kwu 1og(2) log RRA). then, we obtain that radk., - 252..
Let 7 = 3/4 and
1 16v/
log 2 [0og
(2(((1og))
2/
7 7
+ +1/
S 0.75 + 0.05 = 0.8,
n 22p
where the last step follows because n 2 2 vp ing event
(og(([log(R/rr) + 1)/B)) Then, define the follow-
9 - (orron (0)) 4Â and { I (.0.sn(0") or - P=r]}
In the next step, we analyze the probability that 0 Orc. We claim that
P(O" Oioc)gi) (1-3/((2km)) 3/(2knu))
We prove this by induction. In particular, we claim that for every m E ..,...,, Limnt we have P(#* E (mm())) 2 (1 B/(k Note that we O A
For the base case, by the assumption that the datapoints are in (2( we have P(0* 11) P(0* E Oo) = since On is trivially independent of every random variable. Then, we show the claim for m E {L...., } assuming the claim holds for m - 1. We can write
P(0* 6m (1) P(1 fml |l S ranm (1)
(23)
2 (110 Om ll s radm O E 0 and Gi) emm-1
We claim that P(1 0ml S radmm e 0 and 91) P 22(F(Om: x(x) - ((00) x())))
1
radm-1 1 6 and 97
n
To show this lets instantiate Lemma 2.6 with 0g 0* and 7 3/4 obtain that for every 0 E Rdd
110 O1l ((F(0: F(0": :(0":x(m)) x())))
+33mn(00) (0*).
Notice that conditioned on G1. we have 3A 3A,, (0*)
This shows that < frad implies that 1|0 0m I rad,,, conditioned on Gn by the definition of rad, in Line 12. In the next step, we invoke Lemma A.1. Conditioned on 8* E mm-1
v 12Å.
and G1, with probability at least 1 Zky
we have
16 2dlkinu
V2 Twu
F(0m; x()) - F(0"; x100;((1)) (n)) < 2rad
Vlog (4kww//w//// 1B)
n
Notice Awwu S log(2) Log(R/n) a.s. By setting Twu = 128 and the bound on the sample size, we have
F(0m; X (m)) F(O*; x(1))= < radm-1 Also, notice that the randomness in DPGD is independent of history. Therefore.
2(F x()) F(O;; x( (())
P
< radm-1 0 E Om and Gi 2 1
(24)
2k
Therefore, combining Equations (23) and (24), we obtain
IP E (m) >
1
2k
27

---

as was to be shown. From Theorem 2.4, given 2 22 (ogg((log((/r)) 11/0)). we have vp
P(G1) 2 1 - 9.
Therefore,
Aau
P(O" One and (1) 1P00 E One (()))(())
(1- 2 (1 223) (25)
2hiwu
This proves the first claim.
Regarding the second claim, define the following event
G2 = A00 & Å $450..sn(00)
Notice that in the proof of IP E Qwe)) we only used the fact that with high probability Aym (0*) S Å. Since G2 - G1, we can write
3 Kan (1 11-533 53/4) 2 23,
P(O" E One and 92) P(O" E (2e()2) 2 (1
2k
where the last step follows from Part 3 of Theorem 2.4 which states that (P( 2 -53/4.
E Proof of Section 3
Proof of Theorem 3.1. For the privacy proof, notice that Algorithm uses the training set in Line and Line 5. By the privacy budget allocation and the composition properties of zCDP in [BS16], it is immediate to see that the output satisfies p-zCDP.
Next, we prove the utility properties. Define the following event
91 = fr E 1oc and A0.75n(0)) < 4Â and { < 400.sn (0*) ) or Å =r]]
Also, by the non-negativity of |1-1122 we have
F(0"; ;(0r;
Σ 10 mill 2 0.2n (0)).
t=1
Using this inequality, for every 0, can write
Vd v log(1133 (0*)
F( =(0:x(m) F x())) 0o
(26)
Vd
+ + F (0:
S 5o
log (1/3)
F ((1x))
nvp
Under the event that 8* E Ou we can invoke Lemma A. to write
PP - S 50
/og(1/B)
Å 9 2 1 1-3322
where follows because the internal randomness of DPGD is independent of the randomness in Localization step.
By the definition of event G1 either = r or < 40o.sn (0*). Note that if À < can use Equation (26) provide a multiplicative guarantee. Therefore, conditioned on the event G1. we have
we
PP ((F():(()) -F( <
Vd v Tog(1/3) r or
(27)
F ((0:((m)) $
1+0
Vd
[og(113))
min F(;: x(m) ) 2 -8/2. 8E3d
nvp
28

---

The first statement then follows because, from Theorem 2.7, we have P(G)) 2 1-
For the second statement, under the condition that ma X (1) (Ba r) < 3n/4, we can define the following high probability event:
G2 0- Ono and 70.75n (0*) f 4Â and Å < 400.sn (0)))s((0))
The argument then proceeds in the same way the argument for the first claim.
Proof of Lemma 3.2. We can write (:; (m))
exp( 23 F(0; X - -(0);
(i; X (n))
E [A:].
(28)
ΣjENN exp(
c F(o3; X(m) F(0"; (())]
22
follows because (()) is a constant independent of Then, the first claim follows from the standard utility analysis of the exponential mechanism in [MT07].
In the next step, we provide the proof for the second claim. To this end, because of Equation (28), we analyze the sensitivity of F(0,; X F00;; (()) for every [R+]. Note that 0 is data dependent quantity. Let (n) be dataset that differ in one sample from (()), Also, let 0 GMMM (*)) and
assume, without loss of generality, that X()) (.11...,, .n)) and (m) (#1,...,,T.) .... For fixed 0 E (01...., :......,3... we can write
(()) ; x F(0:X(mm) - ;(00:x(m)
n-1
= =10 Inll - 110 1/11 - -10" - -xnll +1100 zn-1 111
Σ
(1 0 x.| - -110- - -x,ll)
i=1
(29)
< 10 00 + 110 0 + Σ
0 -x/l 110 -x:ll)
i=1
< 2110 - 0'1 + 1100 0
(1 e xill - -1100 -xxll)-
Here, the last two steps follow from the triangle inequality. Note that 8 is the geometric median of X Therefore by the first-order optimally condition, we have
v (1 - =x,l) = - - Znll)
(30)
Using the first-order convexity condition applied to the function h(0)) = |10 z|| for a fixed æ, we can write
n
Σ (110 vill -110- -xil)) -
V[100 xill) 0 0*)
(31)
= (V -x', 2',11) 0 8*)
< 000 0+||-
where the second step follows from Equation (30) and the last step follows because
( 11) < 1. Therefore, using Equation (29) and Equation (31), have
((0))( F(0;; x()) [((: x()) F (m) < 2| 0* + 2||0r 0
In the next step of the proof, we invoke Lemma C.4 to upperbound the sensitivity as follows
2|10 0* 2 t g*| < 2diam 3Asn/4400))
A.
where the last step follows because | 0- < diam by the assumption. Notice that the sensitivity analysis the reverse direction is also the same. Therefore, the second claim follows from the standard analysis of the privacy of the exponential mechanism.
29

---

Proof of Theorem 3.3. The privacy proof of Algorithm 4 is relatively non-standard. Let A1 (x((())
(A, (11 Also, let Ag (()); (Á, (0.Ive
i. In particular, A1 (X (1)
can be viewed as the first part of Algorithm 4 before Line 10. Also, A2(:;)) denotes the exponential mechanism Line 10 of Algorithm 4. Using the conversion between zCDP and DP, the privacy budget allocation, and the composition properties of zCDP, we have that A satisfies (e/2,6/2)-DB
Define the following event
G 10- E Oo and A0.75((0 S 4á}.
Let μ be measure on Mi (R x (R))) that satisfies the following: for every dataset X X(m), ((())( E < p()). Let Pi denote the density. Since Ai satisfies approximate-DP, we assume for every 2 R x (R have (2 X(m)== exp(e/2)P X(m) 6/2.
To prove the requirement of privacy, let S C R x (IR x (0....: kn 1}. Also, let X be dataset of size that differs in one sample from X Then, we can write
P. (x (2))())),.) Ax(xx))))) ((5,
ES)
Σ 1[S) (A, (0,lie 11)x
x (i]A, (0.)) x1))) du
Σ / [s) (A, (0: (n -1)(((( (
x [ (0, (0. An (): x ) 11 ((.. 0o) E Gg
Σ/ / [[S]P] (4.00)heeo.....-1111/1 (ijá, (1 ($. 0o) E @gdde
Σ 1[8) (A * [,, 1y ((á, 0o) E =g]du P(g)).
Notice that under the event that (ô, 0)) E G, we can invoke Lemma 3.2 to reason about the privacy properties of A2. Under the event G, we can see that 3A3m/4(00)) + 2diam((o) I 112Á. Therefore, by Lemma 3.2, we have
( (0, (0.))E AI x(m) S cxp(ee/2 n (A) (0:) An (n) x(r))
Moreover, by Theorem 2.7, we have P(G?) S 8/2. Therefore,
Σ/ i[sss (A. (0. x - (8)A, (0 x)))))))
x(m)) dd
I exp(e/22 Σ / 1[8] [. (0r (1)) π (i)A,,
((m) du + 8/2.
Then, we use the fact that Ai (x(1)) satisfies (8/2,5/2):
exple/2) Σ
11 [[8]P (A, (0.)se(o...... (0)) n (1jA, (T(1),, (1A,,00)eeta (0:)seto... An X()) dje +8/2
<exp(=) Σ / [[s] (A, A (0) a (AA (05. 1s]: X( due
) +8.
concludes the proof.
Proof of Theorem 3.4. Define the following event
91 = {00 Ome and Ap.75n (0*) < 4Â and { 40o.sn (0') or & []]
(32)
By Theorem 2.7, and the assumption the minimum number of samples, we have P(G) > 1 1- B.
30

---

By applying the standard tail bound on the norm of a Gaussian random vector (as outlined in Corollary C.3), we have
3dka
log (or(10kk/5) 1)
P( - P Vt {0,..... Kn 1} [err 2
1 +
4V
2p
d
(33)
2 1 - B/5.
Also, we can write
3kn
32 E {0, (O...., Knt 13 (Edir, 0r -0,) 50Å
log (10k//3)
p
3km
S TP 31 E (0....,kn - 1} (Edir,e; 0r - 01) > 50
log 1og(10kn//
91
+ +P(9))
3kn
IP
E {O...... ................................ Kn 1} (Edir,e, 0" 01) > 50
log (10kk/ 91
3,
where the last step follows because P( < 3. Conditioned on G1. for all t E f0...., we have ||0, 0* S 50å since 0* Oo 0g E On. and the diameter of On is 50Å. Also, notice that Sair.t (0., Oo). Using these observations, conditioned on the event G1. using the standard tail bound on Gaussian random variable (as outlined in Lemma C.1),
write
3kg
IP
3t E (0. An 1 (Edir,t 0 -0,) > 50Å
V
log log(10kn/9) S 3/5.
p
Therefore, we conclude
3km log (0g(1kkn/))
(( - Vt E {O....,ko, Kn 13 (Sdir, 0" -0,) S 50Å
(34)
1 63/5.
To prove the claim regarding the suboptimality gap, we consider two cases:
1. There exists & E (0...., kn 1} such that 0* O and 0* & O
2. 0 Ok
Note that these two events are mutually exclusive and their union covers all the space. what follows, we show that both cases there exists E (O....,kr 1} such that F(0;; (()) has small excess loss.
For the first case, suppose be such that 0* E EO, and 0* & O.41. Therefore, we can write
0r $ O+11 + VF( (n)) + Edir,e, 0* 0, 01))2
(35)
VF(0;; X()) (n)) 0* 0.) 2 ((dii,, Oz). -
Notice that using the first-order convexity condition, we have F(Bl; F(0"; x(m)
(())),; 0*). Therefore, by Equation (35), we have
F(0; x()) F(0;; x (1)) < (FFO;; x(m)), 0 - 0r)
(36)
$ (Etir,, 0²)-
Under the events G1 and Gn,2, defined in Equations (32) and (34), have
(()):(()))- F(A": x( < (Can.e, 0" - - 0 (1 kn
log log(Ann/3) )8)
(37)
31

---

For the second case, i.e., H E ①k. we have the following geometric fact [Nes98]: there exists t e {O....,ke kn 1r such that the distance of lr and the separating hyperplane time satisfies
(0, X (x)) + Edir,t
-
0
0z
S O.
(38)
VVF 0,;; (())) + Edir,t
Here is constant such that Da 2 cxp(-7kn) (255)) The values of v and ky will be determined later. Using the first order convexity, we can write
F x (m)) F(O;; X
(0, X(m) + Edir.
V VF(00;x + Exir,
0" - 0g - (Sair, 0- 0₂)
V (0,; X(m)) Edirae
VF(O;: ((00;:X(1) (1) + Sate.e/
(Eair,e 0" - Bb)
2 - / (2/ v F(2:: X ( 211Satr.ell) (Sdir, 0* Oz)
2 22n - Edir.
(Edir,e, 0" -0:) Oz),
where the second step follows from the well-known incquality ||a + 6ll < 2||a| + +|1|6|| for every
a, E Rdd Then, the last step follows because for every 0 E IR VV X S n. Therefore, under the events Gi. Gm,1, and Gm, defined in Equations (32) to (34), we have the following bound on the suboptimality gap
F(O;; (()) - F x (()) S v(2n + 2ll + (Edir,e; -
S v(2n + 2|1Ear + (
lin (
log(kn/B)
P
dkn
log( Log(knn/p ()
kn A
Vv. 0 n
0
log (knn/
P
p
(39)
(25 (xp(-Trk)(255))) Recall that y satisfies ad 2 exp(p= - rkn)
It can be easily seen that by setting
nvD + va)):
kn - log
vd
under the events G1, Gn,1, and Gn,2, we can further upperbound Equation (39) as follows
(
kn
F(0,;(()) - F(0"; (()) o
log log(ka/3)
(40)
Therefore, from Equations (37) and (40), under the event G1 n Gn,1 n Gn.2. for both cases we showed that there exists & such that
-(B < (0t) ( kn (og(ka/)))
(41)
or F(00; x (1) F(O"; x00=;((0)) x()) S sr.0 0(1
Kit log( (3)
By the non-negativity of 11-1122 we have
F(6"; x())) = > 100 2.11 2 0.2m (0*).
(42)
2m1
Therefore, we conclude that for both cases there exists such that
x(0,;((m)) < 1 11
dlog(k)
d log
7B log((s)
F(O*; X())
TP
(43)
or F(0;; F(8": x (1)) S rr. 0
0(1 dlog(x)
d log(k)
-log
TP
TB
32

---

A where
aVD vd + vd.
Let us define OPT min (o....... [0,; X( F(O"; ;(0);((1))} In the next step of the proof, we show that the exponential mechanism in Line 10 with high probability can identify an iterate whose suboptimality gap close OPT. Using the properties of the exponential mechanism in Line 10 as outlied in Lemma 3.2, we have with probability at least 3/3 over the randomness of the exponential mechanism
4484
F(O;: ((()) F((*:((m) (m)) S OPT +
(3og (3kg3/3n)) /8).
(44)
&
Notice that under the event G1 and using Equation (42), we have
4484
log(3kn/3) -
((0":X(m) ((Log((n/8)) or
4484
log(3kn/ /B) S _ (log((ka/ /B) (45)
NE
Moreover, under the event 91 gn.1 1 n nn,2, we provided an upperbound on OPT in Equation (43). Combining Equation (43), Equation (44), and Equation (45), proves the first claim.
For the second statement, under the condition that ma the following high probability event:
[X (*) n Ba r) < 3n/4, we can define
G2 0 E Ore and A0.75n S 4Á and À < 40 (07)
The argument then proceeds in the same way the argument for the first claim.
F Proof of Section 4
Proof of Lemma 4.2. For i [n kt,, write
| xill 2 ||0 Poll ||0g - x;|
||0g - 0oll 2116- zzil + |10 xz||-
Also for every j E [k)], we have
110- ا N 100 - 3ı ll - 110 021l-
Summing both sides of these inequalities, we obtain
k 10 xell
&
Σ
+
Σ
100k - Usl
j=1
n
n-k
2 (n-
21:]100
0xlll
110u x3ll
110
r;| + Σ
00 VU
5=1
nーk
カー
(+) > 1=1
110 - 24 + >
10 1351l
Σ 1100
x +
Σ
100 - 8.l1
5=1
j=1
2 (n- 2k)l100
0x11 2 Σ
1100 xzIl
1=1
Since En= 1 xill + Σ -= 10 - Uzル
Σ n f= 100 2 + -v51]
S 0 by the
assumption that 02 = GM
In Flr.... 3k)) we obtain
R-
(n 2k) -Oull - Σ
00 x; || S
2
k
+ 100 0 <
1100 x:
n 2k
1=1
100 0ull <
2
Σ
10u xyll +
Σ
1100 xill
n 2k
2
+ 100 0all <
F(O6; (#1 (......,.. x.))
n 2k
33

---

Proof of Theorem 4.1. We claim that for every neighbouring datasets X E (Ba(lt)) and X' (Ba(R))" and for every E Ba(lt), we have
[len, (X, v) len, (X', 3)1 S 1.
This follows from the fact that for every X, we have dn(X, (X, X) S dn(X', X) + 1. Then, the proof of privacy follows from the privacy proof of the exponential mechanism [MT07].
Next, we present the utility proof. Let & N be constant that determined later. Define the following two sets:
A1 {v E (R(R) len, (X,y) 2 k}
A2 {y E (R) Ien,(X,,,) (X.9) = 0}
Then,
P A (0 E A1)
SyEA: exp(- len, (X, dy
P N
( E A2)
SYEA: exp( (- len, X dy
(46)
exp(- SYEA, dy
SYEA dy
dy f
We the following simple facts:
dy Re where V1 is the volume of the ball of radius one in R For A notice that, for all y E (GM r), we have len, y) 0.
yEAr
(yBB2(R)
Thus, SyeA, dy 2 Vird. Putting these two pieces together,
P (0 E A1) Pawa (0 A2)
I exp exp( (-x( (+)
d = P PO A1) I exp ( k.)
R ( {
d
(47)
where the last step follows from the fact that P. Pann B E (0, 1) with probability at least 3 we have
(0 A2) S 1. Therefore, we obtain that for every
2
(1)
R +) ) - k
len, X 0) S
log
+ d dllog
(48)
3
E
where 0~ n.
Under the above event, let 0 E Ba(RR) be such that len, 0) < kt. This is equivalent to the
following: there exists = E (a(Q,r) and X (IRdy such that GM(X) and dx(X, X) kt. Using this observation, we can write
|| GM(X)
I || GM(X)) ||0 1 -
S ||= GM(X)) +r
(49)
- GM(X)
Suboptimality Gap: Let 0* e GM(X), then
"
F(0;X) - F(0" X) Σ (100 Iz - 110 - 1;51
[1| xi + -110 xz
GM(XX) - 2. - 1100 - 2:1l)
nr +
34

---

Define I S [n] be the indices of the points that X and X differs. We know that [Z] S k². Then, we can write
"
GM((X) 211 - - -xell)
-[ 2i|1 110- - -xell) =2i1)+
+
Σ (/GM((X)) - zi|
110 - x:ll)
(50)
IEI
sE/ni/2
A2
By triangle inequality, we can write
A1 Σ GM(XX) - 2: 1 -110- xzil)
< [ 1 0- - -GM(X) ||
(51)
I h- ||o- GM
For E I, let (X); = xf where (X); denote the i-th data point X. Since GM(X) is a geometric median of X. by the first-order optimality condition
VeF(GM(X); X) = ++
Σ V= =z kE(m)/I
-x; ==1))--> -
v. (/GGMM))) -2) <<|)) (52)
iEI
To control A2, notice that |00 xzl || is a convex function in 0 for every
Tü- By the first-order convexity condition, for every 0, and 02. we have ||0 x4I| | 24 S (V(10) x; [I), 01 02). Therefore, we can write
Σ (/GM(X)- iE/n]/I
110 - xxll) S E ( - GM - 0²) (53)
2ia|
im/n//I
Then, by Equation (52),
A = E
(V(
GM( =:|)) GM(X) 8.)
RE /I
GM((X) <.()) GM(X)) - 0²)
Finally notice that by Equation (3), for every 2/4 (/ - =<|)] s 1. Therefore, by cM())
Cauchy-Schwand inequality
Σ Vo (/GM(X)) - =2]l) cM(X) 0r)
A -
VEI
< [Z| GM(X) 8-
(54)
< k* GM(X) -0" 0-)
By Equations (51) and (54), we obtain
F(θ: x - F(O";)) S nr + 24 < - -
Then, we invoke Lemma 4.2 which states that [GM(X) GM(X) S n -222
2
F(GM(X):X)
Putting all the pieces together,
[(O:X) - F(0"; X) <n nr + 21
GM(X) 00-1
(55)
4k*
S nr +
F(00;
n 2k.
to be shown.
35

---

Ayn (0
0 x
X
0 0"
Figure 1: Graphical Intuition Behind Equation (57)
Distance to 0*: From Equation (49), we know that ||0 GM(X) s ((GM(X)-GM(X) +r -
where X is dataset of size such that (X, X) S k*. The proof is based on characterizing the worst case distance between the geometric median of two datasets that differ in at most k* points.
For the dataset X ((),, recall that 0* GM(X Also, recall the definition of 4 (8*) from Definition 1.1. Let 0 E Rd be such that ||0 - 8- > Ayn(0"). Define m = X n Ba Am (0*)) By the variational representation of |1-11,
write
0 0"
(F
0 (00;;)),
X),
0-1
Σ
0 -
0 0r
E
0 0-
0 0+
1 x|
1 0+|
110 x1
110 00
=0 (0+))
=EX)((xnBu(0 (A,)()))))
E
x
0 0r
(n - m)
0
=||
110 0+1
xx Am (0
(56)
where the last step follows from Cauchy-Sehward inequality. Then, we claim that for every x E X n Ba(0", (0*))))) we have
x
0*
1
A Am (0-) (0))
(57)
0
x||
100
0-1
0 0-
To gain the intuition behind it see Figure 1. Therefore, from Equation (56).
(m*)))
2 m/ 1 100 0-
(n - m).
0. A sufficient are interested on characterizing the condition under which VF X)| condition is that given < 2m
Anr (0-)
my
(n (n-m)) > 0 (+)
A (8*)
10 1*
100 0+1
2 m
m
This shows that the distance of GM(X) and 0* has to satisfy
GM((X) 8+
Ann (8*)
2
m
The function 1(x)) -2 is decreasing in the range of E (0, Also, notice that m
X n Ba An (0*)) 2 7m k* Therefore,
[GM(X) -0r1
Ayn(0*)
V 22(r k)) (γ k+
as was to be shown.
36

---

G Proof of Section
Proof of Theorem 5.1. The proof is based on the reduction provided in Lemma G. G.I and the lower- bound on the sample complexity of the mean estimation of Gaussian distribution with known covariance matrix in [KLSU19, Thm. 6.5].
Lemma G.1. Let v 49 x 10 a S 49 x 10 5, 8.8 S 10 be an arbitrary (e, 8)P algorithm such that for every dataset X(m), is output satisfies
+, and Z 22500 be constants. Let An
E (xim)(
S (1 +
F(0:X( x (EBT(1)
min
Let E B3 (1) and let ( (X1...., .n) (u, Let Ó ~ An(X(")). Then, with probability at least 2/3 over ((n) and the internal randomness of An we have
0 m| S 0.2V/.
Proof. The proof consists of several steps:
Step 1: Bound on the Empirical Error: Let An be an arbitrary (s, 6)-DP algorithm such that for every dataset (x), its output satisfies
F(O; x (m)) $ (1+a)
min DEBT(R) (1)
F(0; (*)).
Let su E BT (R) and ( (XI,..., X,) (N, Ia) on, implies that
The utility guarantee of the algorithm
(((0)
S (1 +
min F(0; x()) BEBT (R)
S (1 + B
F F(r;
To further upperbound the last step, we can use Jensen's 's inequality write
E (((xx(()))
E[I|X1 =1]]
E ||xx - =11²
dd
Therefore, in-expectation over (a) ~ Ia) fon and the internal randomness of An, we have
Mo.teN F (0:xx( - (1: I navd.
(58)
Step 2: Relating Empirical Error to Population Error. Let (Xo. X,) (i, @m++1, With abuse of notation, let An An X,)), and, for every i [m]. let ((0) An(,X...... X,-1, Xo. X X.))). Let T be constant that will be determined later. We can write
E E|1000 -00-xx||1
P -(|000>_x|| 22)2) +1)d
-x,
(59)
P [000 - x, 2 2) dt + J P P((000 x, 21) dr.
Consider the first term in Equation (59). Since An satisfies (E, 6)-DP,
P P([000 x, 2 = P ((0)) X, 2 (Xo, (Xo,...,X
< T ( (10 X,ll 2 (Xoo...... xn) +
(60)
expls) P([ X,ll 2 t) 5.
37

---

Therefore, the first term can be upperbounded
P(100) -x.| 21 1)dl exp(e) F(1 X:Il 2 ()d/ T8
S <ep((s) Bill0 xxII] + 78.
In the next step, we upperbound the the second term in Equation (59). Notice that
{10(), x,): |00) - r - (X; - 1> 2 # S (06)) X,) |X - الر 2 t 0 - -111
(61)
X | niIl 2 1 - 2Rvd).
where the first step follows from the triangle inequality and the last step follows because y and g(3) are in B (R). Using this, we can write
_ P 1(1000 x,
2 2tddt S
P(Ix:
- A|ll 2 2t 2RVd))2)o
T=
(62)
P F(II, all 2 u + vd)
12R+
where the last step follows from the change of variable u = (2R + 1d In the next step, we use the concentration bounds for the norm of multivariate Guassian random variable. Using Lemma C.2, we can write
( all 2 u +v
IP
IP
42 +d+2uvd
nll z u² + d 2uv
(63)
exp
2
Let T= = 2(2R + 1)vd. Then, using standard bounds on the complementary error function [Ksc17], can write
J P PIIX: - Alll 2 u va S
u2
exp
du
(2R41)VV
(64)
exp (-2(2R (-2(2R+1)>d))
(4R 2)
In the last step, we claim that B[100 Xoll| E xx||] for every [n]. is because g(t) s 8, X, $ Xu. and g(i) IL X,. Ergo, combining and summing over E [n]. we obtain
B1110
Xoll]
S eep((e)
1 Σ
n El110 x:11] + (4R 2)Vōō
exp 2(22R + 2((2 1)²a)
(4R 2)vd
This bound implies that
E|110 Xoll - Ellle Xoll
<xp((s)
[Bl]]0 X+lll BE[I x61l)) + (exp(s) 1)BlIla Xo [l]
(AR + 2d exp(- exp(-2(2RR + 1)²d)
+ (4R+ + 2)
This equation can be rephrased as follows
Bil00 Xoll] Ellly Xol1| < 3Vd
(65)
where
= exp(eea + (exp(e) - 1) + (4R + 2)6 +
exp (xp(-((2++))d))
(66)
(4R + 2)d
38

---

Step 3: Relating Population Error to Distance In Step 2, we showed that in-expectation over
(Xo...., x,) (M4 TT) (a+11) and ~ An (x()) where X = iX Xn), we have
E $116 X E Xoll S S.Vd.
(67)
For notiational convenience, let h Rd - R be h(0) Ex-MWallll 0 XII. Equation (67) can be written
E Ext: Ar (X(m)) [M(O] m(() S BBvd.
Since ja is the minimizer of h()), for every E Rdd we have that h()) 2 h(u). Therefore, h(0) - h(()) is a non-negative random variable. We can invoke Markov's inequality to write
X (00o:NNNNL))000mmA...... (M(O) - h(x) - 33vd 2
2
(68)
In the next step, provide deterministic argument: For every 0 R such that h(0) h(4) 1 33 vd, we provide upperbound on |10 1u||- By subtracting μ. we can write
h(0) h(p)) Bx (110 x || X|] -Z-NN(o 1110 μ + Z11 - [|]
(69)
Define the following events
log(1/7) d
log(4/7) /d1+44
E Z d 1 - 21
$ || S
d
(70)
Eg Z (0 μ. Z) 2 -10 - will log(2/7)
Using Corollary C.3 and simple concentration bound for Gaussian random variable we have that P(E (2) 2 1 7. Let & Eg. By dropping the positive term, we can write
|0 - μ ||||]
[[[[| + 21|
[ZI 1[]]] + E[[]@ + 211 - 1[T
(71)
- Z|| / [[]]] E[||Z| [[]]]
Using Cauchy-Setie Bauchy-Schwarz inequality, E[] 21| In the next step, we analyze the first term.
1[89] S VP(( E1I =1 VP(S/Vass vFva.
E[(lle
/1 21|
E
110
11|2
|| 2(0 11 2, |2|
[
(72)
110 11l
+ (0 n, 2)
E
|z||
VV
+
1 [[
|
|
The value of y will be determined later. Let d be large enough such that
(1 (1-2 1og(4/4)
0.9 and (1 (1+4)
log(1/>)
1.1.
(73)
Then, can write
||0 n1l2
+ +2(8-
(8 u4 Z)
E
(1 1+
-1) [[8]
11
1|211
(74)
110 - -ul
2 2/2log(2//))l mlll
2 V0.9d
|v++
1.1d
0.9d
39

---

Notice that we assumed that h(0) h(μ)) - 3Bvd. Therefore, we have
vo.9d
0 - 11ll
2 (o//)112/)) ulll
-1) VVva5333V
1.1d
0.9d
(75)
||0
ml
2 2//2lz (2/g(2/)))0 -
(3/ + v7)
(+) 1+
+1.
1.1d
0.9d
v0.9
Simple calculations show that this bound implies that
((1+
33 + v7
2
||0 nlll s 3..45vlog(21)) vi.1d,
v0.9
(76)
$ <3.45v/og(2//) +.1vV
$ 15 0.1vv.
We would like to set the parameters such that vI.ld, ((++
38+v7 (1++)) -1 v0.9
0.1vd. We can
easily see that implies 3, / = 0.0045. For example, we can pick B = 0.0014 a00014and-20 10- Recall that
8 exp(e)a (exp(=) - 1) (4R 2 (4R + 2)d (exp(=)
exp 2(2 + (22(2R
(77)
For instance, by setting < 49 10-5, 5, < 49 x 10-5, 8 <
10 and d > 2, we obtain
S 0.1. Finally, we need to set d such that Equation (73) holds. We can see that d 2 7050 satisfies this condition.
H Details of the Numerical Experiment
Our goal the experiments is to evaluate the impact of increasing the radius of the initial feasible set, Le. R, on the performance of our proposed algorithm and compare it with DPGD. Also, want to show that our method without any additional hyperparmeter tuning can achieve a good excess error.
Data Generation. Let n denote the number of samples. We assume that 0.9n of the data is distributed as follows: let µ E Rd be uniformly random vector within S We then sample 0.9n of the data points from (u, (0.01)2 La). The remaining 0.1n of the points sampled uniformly at random from (100).
Hyperparameters. We set the discretization parameter to r 0.05 in Algorithm 2 and failure probability to 5%. Additionally, we repeat each algorithm times and report the mean, For the other hyperparameters, we used exactly the same hyperparameters as stated in Algorithm 3. For DPGD,
we use the hyperparameters in Lemma A. and in particular, we choose T such that /2 16v7
VT
AVP
d = 200, n 000 1/n
d = 200, = 3000, = 1/n
10a
Ours
Ours DPGD
Xin)
10a
DPGD
Fl@: (F Xin)
10'
F(0:X IF
102
10a
10P
10a
R
R
Figure 2: Performance for Different Privacy Budget
40


Reviews:
[{"review_id": "N68MlJgapq", "reviewer": "Reviewer_3ZzL", "summary": "This paper studies differentially private algorithms for computing geometric median (GM) of a dataset.  Previous methods such as DP-SGD requires knowing in advance that all data points live in a ball of radius R (contribution bounding), and the resulting utility guarantee also has a dependency on that R, which can get very big even though the majority of the points are concentrated around the GM. The paper proposes three algorithms, two for approximate DP and one for pure DP. For approximate DP, we run a pre-step for finding a quantile radius which covers the majority of the points and then find a good initialization point using this radius. From there we can either run DP-SGD or using an DP-adapted cutting plane algorithm. For pure-DP the authors describe a discretized inverse-sensitivity mechanism.", "questions": "It seems that the authors have used $\\rho-zCDP$ and $(\\epsilon, \\delta)$-DP interchangeably but without providing preliminaries on the connection between the two? It's better to unify.\n\nFor others, see the weakness part.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem solved in this paper is a very interesting problem, that is important in practice, and the solution provided in this paper provides the first performance guarantee without the dependency on the spread of dataset that can be achieved with an implementable, polynomial-time algorithm, which is impressive.\n\nWhile developing the algorithms the paper made many observations that are insightful and could be worth knowing for the community. I think the way it relates the quantile radius around the GM to the average of top m quantile radii of all points in the dataset is clever, and so is the relationship between distance from GM and median cost expressed in terms of quantile radius. \n\nAlthough there are certain complicated aspects of algorithms, the overall quality of writing is good.", "weaknesses": "I found the pure-DP algorithm not as interesting as the approximate one for a couple of reasons: (1) it requires an oracle finding exact GM, which is not known, so I'm wondering what happens if we are given an approximation but then the definition of $len_r(X, y)$ is messed up; (2) the paper does not talk about how to compute $len_r(X, y)$; which I think is non-trivial? (3) is the purpose of introducing $r$ mostly to discretize the original inverse sensitivity mechanism? what is the benefit of using $r$ compared to $r \\to 0$?\n\nNumerical setting is relatively simple but I don't really mind that since the greatest merit of this paper is in the theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive and thorough review. We respond to the main points below.\n\n> **On Our Pure-DP Algorithm** \n\nOur pure DP algorithm is not the main focus of our paper. Our main result is a pair of polynomial time and sample-efficient algorithms for this problem using gradient methods under the constraint of approximate-DP. However, it is important to understand the achievable utility-privacy tradeoff under the stringent notion of pure-DP.  Our pure-DP algorithm is not computationally efficient, but it shows that under pure-DP, we can achieve a similar data-dependent utility guarantee with $\\sqrt(d)$ more samples. The analysis of this algorithm relies on the several robustness properties of the geometric median, which might be of independent interest.\n \n> **W1: Oracle access to exact GM** \n\nThank you for raising this point! We can relax the assumption of having access to an exact geometric median oracle. Instead, consider an oracle such that for every data set $\\mathbf{X}^{(n)}$, outputs $\\theta$ such that $\\lVert \\theta  - \\mathrm{GM}(\\mathbf{X}^{(n)}) \\rVert \\leq \\alpha$, i.e., the output has distance $\\alpha$ from the exact geometric median. We can modify the definition of the length function to use such an oracle. Obviously, inexact oracle changes the utility guarantees and we get an additional additive error. We did not develop this relaxation as it would add complexity without providing additional insight.\n\n> **W2: Computing $\\text{len}_r$ function**\n\nComputing this function is not efficient in general. This is a well-known limitation of the inverse sensitivity approach. Indeed, most of the DP algorithms that try to adapt to local sensitivity, such as smooth sensitivity [NRS07] and propose-test-release [DR09], have a similar step that one needs to compute such a length function. \n\n[NRS07] Nissim K, Raskhodnikova S, Smith A. Smooth sensitivity and sampling in private data analysis. InProceedings of the thirty-ninth annual ACM symposium on Theory of computing 2007 Jun 11 (pp. 75-84).\n\n[DR09] Dwork C, Lei J. Differential privacy and robust statistics. InProceedings of the forty-first annual ACM symposium on Theory of computing 2009 May 31 (pp. 371-380).\n\n> **W3: Benefit of r>0**\n\nIntroducing $r>0$ is necessary for analyzing the algorithm: In the analysis of the algorithm based on sampling, one can come up with some pathological datasets such that the normalization factor for the sampling distribution becomes infinity. A standard technique to address this is to smooth out the cost function using $r>0$. Notice that the sample complexity of this algorithm scales with $log(1/r)$ as shown in Theorem 4.1. Therefore, we need to assume $r$ is bounded away from zero.\n\n\n\n\n> **Q1: Privacy definitions** \n\nThanks for the suggestion! We already included in Appendix 3 (A.3) definitions of approximate-DP and zCDP as well as the connection between these two notions. Based on your suggestion, in the final version of this paper, we will add this appendix to the main body.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K1PSM0B7Ns", "reviewer": "Reviewer_M9WN", "summary": "This paper studies DP algorithms for geometric median. The paper starts with DP-SGD on geometric median as the baseline. The error scales linearly in R, the radius of a ball containing all data points. This can be a very loose bound since the geometric mean is known to be robust to outliers and one single outlier can make this radius R to be arbitrarily large. \n\nThe algorithms proposed in this paper has both multiplicative error and additive error. The idea is to replace the estimate of R by the quantile radius -- the value \\Delta such that a ball of radius \\Delta has at least a certain fraction of the points. This comes with a cost of a multiplicative error. \n\nThe algorithm has two phases, with the first phase to estimate the quantile radius in a private manner and the second phase to find the geometric median. The first phase uses techniques from [NSV16]. For the second phase the paper reports several ideas: 1) just apply DP-SGD using the quantile radius; 2) uses a cutting plane method (non-gradient descent method) and 3) for pure DP uses inverse smooth sensitivity of [AD20] -- this one is not efficient in terms of running time.\n\nIn summary I think this paper did an OK job but the ideas are in general incremental. I would give a positive rating but I am not extremely enthusiastic (or lacks excitement).", "questions": "See above.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper has merits of developing DP algorithms for geometric medians. The algorithms have both multiplicative error and additive errors. Adding these algorithms to the repository of DP algorithms for this problem is nice.", "weaknesses": "The idea of using \"robust\" notion of radius, essentially the quantile radius, is not new and has been a standard in many prior work on clustering algorithms -- search clustering with outliers. It will be good to include citation and discussion on that.  \n\nThe writing can be improved. There are many places where clarification and definition will be helpful to readers. Some examples are mentioned below.\n\nOn DP-SGD, may you explain what is the definition of \"excess error\" (line 23)? Is this the same as excess risk (line 45)?\n\nEquation (2), what is A_n? the DP -SGD algorithm? It is never defined.\n\nLine 63, effective diameter of the data points -- it will be good to explain what effective diameter means.\n\nTable 1, define lower case r? Again r does not appear until much later in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thorough review and valuable feedback. Below, we address each of the points raised.\n\n> **Q1: Robust Notion of Radius and Our Contribution**\n\nWe agree with the reviewer that proposing a new robust notion of radius is not a contribution of this work. Our primary contribution lies in connecting the notion of quantile radius to the convergence of gradient-based methods. We establish several fundamental properties of the quantile radius and leverage these properties to design private algorithms: \n\nFor instance, 1) the geometric median function satisfies a **growth condition** for a point $\\theta$ such that $\\lVert \\theta - \\theta^\\star \\rVert \\gtrsim \\Delta_{\\gamma n}(\\theta^\\star)$. (See Lemma  2.6 for a formal statemtn ).This is a key result for developing the warm-up algorithm. It lets us show that we can design gradient-based methods that use large steps sizes with the goal of consuming less privacy budget.  2) Quantile radius is a data-dependent quantity but one can privately estimate it using pairwise distances between the data points. In Lemma 2.3, we show that computing these pairwise distances serves as an effective proxy for determining the quantile radius, which again relies on specific properties of quantile radius. \n\nIn summary, we emphasize that the main contribution of our paper is not introducing a new notion of radius. Instead, we demonstrate that the quantile radius has several interesting connections to various properties of the geometric median function, and we exploit these connections to develop a pair of polynomial-time and sample-efficient private algorithms. \n\nBased on your suggestion, we have added a discussion on related work in clustering in the non-private case. In particular, we will mention in the revised version of the paper that the robust notion of radius appears in clustering with outliers algorithms as well (for instance, [BHI02]). We have already discussed the work on the private version of clustering, such as [NSV16; NS18; CKMST21; TCKMS22]. We appreciate the reviewer’s suggestion to include further work on robust clustering.\n\n[BHI02] Bādoiu M, Har-Peled S, Indyk P. Approximate clustering via core-sets. InProceedings of the thiry-fourth annual ACM symposium on Theory of computing 2002 May 19 (pp. 250-257).\n\n\n> **Q2: Excess Error and Excess Risk**\n\nThank you for catching this typo. We use the notion of excess error of Algorithm $\\mathcal{A}$ to refer the achievable cost function compared to the global optimum, i.e., $ F(\\mathcal{A}_n;\\mathbf{X}^{(n)}) -  F(\\theta^\\star;\\mathbf{X}^{(n)}) $ . We fixed it.\n \n> **Q3: $\\mathcal{A}_n$ in Equation 2**\n\nThank you for pointing this out. As you mentioned it is DP-SGD. We fixed this in the paper.\n\n> **Q4: Effective Diameter**\n\nIn Line 63, effective diameter of the data points is an informal way to refer to the quantile radius. Later in Line 77, we mentioned that quantile radius formalizes the idea of effective diameter. Based on your comment, we added a sentence to help a reader understand better the effective diameter. \n\n> **Q5: $r$ in Table 1**\n\n$r$ can be thought of as a very small constant that shows the minimum separation of the data points. More precisely, assume that no data point has 3n/4 of other data points within a ball of radius $r$ centered on it. Then, as we show in the second part of Theorem 3.1., our algorithm has a “purely” multiplicative error. However, in order to get a completely **general result** without placing any assumption on the dataset, we need to incur an additive error proportional to $r$. Note that as the sample complexity and runtime only depends on $\\log(1/r)$, we can assume it is very small. Introducing $r$ is unavoidable due to the impossibility results in [NSV16].\n\nBased on your suggestion to improve readability, we have removed $r$ from the summary of the results in Table 1 in the introduction and only present the multiplicative error guarantee. We defer the general results, including the additive error, to the later sections.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k4i5HvzwUv", "reviewer": "Reviewer_7SSt", "summary": "This paper considers the differentially private geometric median problem. The goal of the geometric median problem is given n data points, find a point to minimize the sum of Euclidean distances from this point to all data points. \n\nThe previous DP-GD algorithm requires prior knowledge of the radius R of the data set and also has the excess risk linearly depending on this radius R. \n\nThis paper provides three algorithms for the differentially private geometric median. They provide LocDPSGD and LocCuttingPlane algorithms which achieve approximate DP and the excess risk bound depends on the optimal cost instead of the radius R. Finally, they provide an exponential time algorithm that achieves pure DP.", "questions": "-", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 This paper considers the differentially private geometric median problem, which is an important problem since the geometric median is widely used in many algorithms and requires privacy for many real-world applications. \n\n2 This work provides interesting techniques and algorithms to achieve the excess risk bound depending on the optimal cost instead of the radius of data points R. They developed a private estimation of quantile radius and private localization for the warm-up stage such that the excess risk does not depend on the radius R.", "weaknesses": "-", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the positive comments!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cg3HEzjdvm", "reviewer": "Reviewer_wp5E", "summary": "This paper introduces a pair of polynomial-time DP algorithms for computing the geometric median of a dataset. The excess error guarantees of the algorithm scale with the effective radius. \n\nThe algorithm includes two parts. The first part shrinks the feasible set to a ball whose diameter is proportional to the quantile radius of the optima, which is defined as the radius of the smallest ball containing sufficiently many points. First, it gives a private estimation of the quantile radius. Then, it locates a good initializer based on the estimated quantile radius. AboveThreshold and DP-GD are implemented in the procedure to ensure the approximated DP. \n\nThe second part fine-tunes the output of the first part. The paper provides two fine-tuning methods. The first one utilizes DP-GD. The second one modifies the cutting plane method. It adds Gaussian noise to achieve DP. Using a novel sensitivity analysis of the loss function, the authors show that the noise can be scaled down.\n\nThis paper also provides the lower bound to demonstrate the optimality of the sample complexity of their algorithm.", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Quality of result:\nThis paper studies the DP convex optimization task. DP-GD method is well-established in this field. The authors point out that its excess error depends linearly on the radius R of the feasible set. Previous work shows the strongly convex assumption can remove this deficiency, but it is too strong and unrealistic. \nThis paper improves the dependence on the radius for the geometric median task under weak and natural assumptions. The main contribution of this work is a pair of polynomial-time DP algorithms (with different run-time) for geometric median estimation with an excess error linearly depending on the effective radius r of the dataset, instead of the worst-case radius R. This significantly improves the error bound when r << R. This condition is common since the dataset may have an enormous R due to a small number of outliers.\nOther contributions include a pure DP algorithm based on the inverse smooth sensitivity mechanism (yet it is computationally inefficient), and the demonstration of the sample lower bound, which verifies the optimality of the algorithm.\n\n2. Novel techniques: The algorithm's good error bound is based on a structural result stated by the paper: Given a point \\theta, if its distance to the optima \\theta^* is larger than the quantile radius \\Delta_{3n/4}(\\theta^*}, it has a linear growth in its loss value: F\\left(\\theta ; \\mathbf{X}^{(n)}\\right)-F\\left(\\theta^{\\star} ; \\mathbf{X}^{(n)}\\right) \\gtrsim\\left|\\theta-\\theta^{\\star}\\right|. This simulates the effect of strongly-convexity, which has a quadratic growth. This implies that one can take a larger step size when performing the DP-GD. It will move fast towards a sub-optimal point. To utilize this property, the authors build a private estimation algorithm to find this radius quantile. Then, the algorithm fine-tunes the sub-optimal point to find a good estimation of the geometric mean. This paper states a modified DP-SGD algorithm to do this task. To reach a better run-time under certain conditions, this paper also provides a private cutting plane method by adding local noise.\n\n3. Technically soundness: This paper is sound technical with solid proof and analysis. It has an informative technical overview. It also includes a numerical experiment to strengthen their result. It compares their algorithm with DPGD in solving the geometric mean task. Under large R, their algorithm shows significant improvement upon DPGD.\n\n4. Reproducibility: The quantile radius technique in the warm-up algorithm is of independent interest. It may be utilized to solve other DP convex optimization tasks. The authors also state the open problem of developing a linear time algorithm with the optimal excess error.", "weaknesses": "More words can be added in Section 1.1 to introduce the intuition of their solution (e.g., how to solve the challenge in line 122?). A comparison of run-time and excess risk with methods from previous work may also be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive and thorough review! We respond to the questions below. \n\n> **W1: Presentation of the ideas behind the algorithms**\n\nThanks for the suggestion. In the revised version of the paper, we expanded on these challenges and also presented the high level ideas of the proposed solutions. For instance, we added this sentence regarding the challenges discussed in Line 122:\n\nThe general analysis of the exponential mechanism involves analyzing the sensitivity of the numerator and normalizing factor separately. We provide a novel analysis of the exponential mechanism with the geometric median loss function as the quality function by **coupling** the sensitivity analysis of the numerator and denominator. In particular, we show that given a set of candidate points that lie in a ball with radius $\\Delta$, the noise due to the private selection is only $O(\\Delta/\\epsilon)$ instead of $O(R/\\epsilon)$ one would obtain by the direct application of the exponential mechanism.\n  \n> **W2: Comparison with prior work**\n\nSince the geometric median loss function is convex and 1-Lipschitz, one might use an off-the-shelve method for private convex optimization for this task. However, a key shortcoming of this approach is that the excess error scales linearly with $R$. In particular, one can use DP-SGD from [BST14]. The runtime of this method is $n^2 d$ and the excess error is \n$$\nF(\\text{DP-SGD};\\mathbf{X}^{(n)}) - \\min_{\\theta \\in \\mathbb{R}^d} F(\\theta;\\mathbf{X}^{(n)}) = O\\left(\\frac{R \\sqrt{d}}{\\epsilon}\\right)\n$$\nBased on your suggestion, we have added a row to Table 1 summarizing the performance of the off-the-shelve method for private convex optimization for this task.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "D1b4bt5Us6", "reviewer": "Reviewer_wFAP", "summary": "The paper proposes algorithms that compute the geometric median with differential privacy. Composed of two parts, the algorithm firstly finds the quantile radius that covers enough points. Secondly, it fine-tunes the geometric median. The authors suggest two methods for the second part: LocDPGD and LocDP cutting plane methods.\n\nAdditionally, the paper shows a pure DP algorithm for computing the geometric median and a lower bound on the sample complexity required to compute the geometric median with differential privacy.", "questions": "I am wondering if the authors can explain a bit more about the comparison between LocDPGD and LocDP cutting-plane. For example, you could compare the time complexity and explain under what circumstances one is better than the other. \n\nI am also wondering what part is the bottleneck if someone wants to improve this to a linear run-time.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies a well-motivated problem. As mentioned in the paper, a line of works has studied computing private versions of the medians, but little is known about the world when the dimension is larger than one. \n\nThis problem is difficult because the runtime of applying vanilla DP-GD is highly affected by outliers. This paper uses two steps: first, it estimates the quantile radius and an initial point that is not greatly affected by outliers, and then it fine-tunes the computation of the result. This idea is intuitive but requires some good techniques. For example, the way they implement the DP cutting plane method by adding Gaussian noise to the gradient that \"cuts\" the set seems novel and interesting to me.\n\nThis paper is also very complete in the sense that it shows results in pure DP setting and lower bound in sample complexity. \n\nFrom the writing perspective, this paper is well-organized and straightforward to read.", "weaknesses": "It is a bit difficult to understand the dependency between parameters in Thm 3.1 and Thm 3.4. It would be very helpful if the authors could make Thm 2.7, 3.1, and 3.4 more readable and easier to compare.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive and thorough review. Based on your suggestions, we revised the statements in Thm. 2.7, Thm. 3.1, and Thm. 3.4 to improve readability. \n\n\n> **W1: dependency between parameters in Thm 3.1 and Thm 3.4.**\n\nNote that there is **no** dependency between the parameters in Thm. 3.1 and Thm. 3.4. in the sense that the statements of the theorems are self-contained. Theorems 3.1 and 3.4 concern the utility of the algorithm using DP-(S)GD and DP cutting plane method, respectively. Both of the algorithms have the same utility guarantee. There is an additional log-factor (only in $n,d,\\varepsilon$) in the utility guarantee of the cutting plane method. \nDue to the space limitation, in the submitted version of the paper we needed to introduce $\\kappa$ and $\\alpha$ so that we can fit the equations in the line. In the revised version of the paper, we will improve the readability of the mentioned theorems. \n\n> **Q1:  On comparison of LocDPGD and LocDP.**\n\nBoth of the algorithms have the same utility guarantee (up to a log factor only in $n,d,\\varepsilon$). However, the runtime is different. Consider the case that $\\varepsilon=\\Theta(1)$. Then, if we approximate the matrix-multiplication exponent by $2.5$, we have the following:\nGiven  $n \\leq \\tilde{O}(d^{1.75})$, LocDPSGD achieves better runtime, while for $n > \\tilde{\\Omega}(d^{1.75})$,  localized DP cutting plane methods achieve a better runtime. This comparison is based on the runtimes presented in Table 1. We added this discussion into the paper.\n\n> **Q2:  Bottlenecks for improving runtime.**\n\nThere are two bottlenecks in our algorithms:\n\n1- The first roadblock is that the estimation of quantile radius requires $n^2$ computations as discussed in Remark 2.1. One possible solution here is to consider subsampling for estimating $N_i(v)$, i.e., the number of data points within distance of $v$ from $x_i$. In particular, one can sample a constant number of points and only use this subset to estimate $N_i(v)$. While this approach provides an accurate estimate of $N_i(v)$ with high probability in a non-private setting, it introduces technical challenges for privacy analysis.\n\n2- The second roadblock is that for private convex optimization of non-smooth loss functions there is **no** general first-order method with an optimal excess error that requires only $n$ gradient evaluations. (see [FKT20] and [CJJLLDT23] for recent developments.) To address this, we need to develop a specific first-order algorithm for the geometric median problem that requires $n$ gradient evaluation to achieve the optimal error. \n\nBy addressing the aforementioned challenges, we can develop a linear-time algorithm that achieves optimal excess error for the geometric median problem. We will incorporate this discussion into the revised version of the paper.\n\n[FKT20] Feldman V, Koren T, Talwar K. Private stochastic convex optimization: optimal rates in linear time. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing 2020 Jun 22 (pp. 439-449).\n\n[CJJLLDT23] Carmon Y, Jambulapati A, Jin Y, Lee YT, Liu D, Sidford A, Tian K. Resqueing parallel and private stochastic convex optimization. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) 2023 Nov 6 (pp. 2031-2058). IEEE.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers agree that the goal of improving the accuracy for the private geometric median problem with a large number of inliers is a well-motivated problem. This paper presents algorithms with various trade-offs and excess error guarantees that scale with the quantile radius, i.e., the effective diameter of the input dataset. The initial reviewer concerns were successfully addressed by the authors during the following discussion.

I would encourage the authors to address reviewer concerns and make improvements to the overall presentation, to strengthen the potential impact of the work.
Decision: Accept (poster)