Private Geometric Median

Authors: mahdi  haghifam
thomas  steinke
jonathan  ullman
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 16:01:15

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.

Main paper: 
 introduction: 
 Differentially private (DP) convex optimization is a fundamental task where we approximately minimize a data-dependent convex loss function while limiting what can be learned about individual data points. The predominant algorithm for DP convex optimization is DP (stochastic) gradient descent, or DP-(S)GD, for short [SCS13; BST14] . Given a dataset X (n) which contains private information, and a loss function F (θ; X (n) ), DP-(S)GD starts with an initial value θ 0 ∈ R d and iteratively updates it using θ t+1 = Π Θ θ t -η• ∇ θt F (θ t ;X (n) )+ξ t where η > 0 is the step size, ξ t is noise to ensure DP, Θ ⊆ R d is a closed convex feasible set, and Π Θ is the Euclidean projection operator. In the most general setting of Lipschitz convex functions, the excess error depends linearly on the radius of the set Θ, 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 set Θ as capturing a measure of the uncertainty we have about the location of the minimizer, and we want our algorithm to perform well even with a 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 a step towards answering this question, we identify a simple, optimization task-computing the geometric median-where we can exponentially improve the dependence on the radius.We study private algorithms for computing the geometric median (GM) of a dataset: We are given a set of n data points X (n) ≜ (x 1 , . . . , x n ) ∈ (R d ) n , where x i represents the private information of Table 1: Summary of our results. Here OPT = arg min θ∈R d F (θ; X (n) ) denotes the optimal loss and ω is the matrix-multiplication exponent. The highlighted part is the runtime of the warm-up phase which is the same for LocDPSGD and LocDPCuttingPlane. We also assume that max i∈[n] |X (n) ∩ B d (xi, r)| < 3n/4. (See Section 3.1, Section 3.2, and Section 4 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:θ ⋆ ≜ GM(X (n) ) ∈ arg min θ∈R d F (θ; X (n) ), where, F (θ;X (n) ) ≜ i∈[n]∥θ -x i ∥ 2 .(1)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 is a nontrivial estimator even when ≤ 49% of the input data is arbitrarily corrupted. These properties make GM a popular tool for designing robust versions of distributed optimization methods [CSX17; WLCG20; FGGPS22; AHJSDT22; 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 a known ball of radius R (without loss of generality this ball is centered at the origin, i.e., ∥x i ∥ 2 ≤ R for every i ∈ [n]), then DP-(S)GD guarantees (ε, δ)-DP with the following excess error [BST14] :EQUATIONAs 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?It 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 a small number of outliers, while most of the datapoints live in a ball with a small diameter. A key property of GM is robustness to outliers, so we want our accuracy guarantee to also be robust to some outliers. Specifically, if ≥ 51% of the points lie in a ball of diameter ∆ ≪ R then the geometric median is O(∆) 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 a 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 scales with the radius that contains majority of the datapoints? Our results provide a positive answer.Our main contribution is a pair of polynomial-time 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 a 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 a simple numerical experiment on synthetic data as a 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 Algorithms. Both of our algorithms for the private geometric median problem are two-phase algorithms: in the first phase, which we refer to as 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, we formalize the notion of the quantile radius as the radius of the smallest ball containing sufficiently many points. Definition 1.1 (Quantile Radius). Fix a dataset X (n) = (x 1 , . . . , x n ) ∈ (R d ) n and θ ∈ R d . For every γ ∈ [0, 1], define ∆ γn (θ) ≜ min{∆ : |i ∈ [n] : ∥x i -θ∥ ≤ ∆| ≥ γn}.To motivate the idea behind our algorithms, assume the algorithm designer knew a ball, with center θ 0 and radius ∆ such that ∥θ 0 -θ ⋆ ∥ ≤ O( ∆) and ∆ = O(∆ 4n/5 (θ ⋆ )). Then, running DP-(S)GD over this ball would give excess error O(∆ 4n/5 (θ ⋆ ) √ d/ε). 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 F (θ ⋆ ; X (n) ) ≥ (1 -γ)n∆ γn (θ ⋆ ). This inequality shows that an algorithm whose excess error depends on ∆ γn (θ ⋆ ) has a multiplicative 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 θ 0 and ∆ a priori, the objective of the warm-up algorithm is to privately find these quantities.The warm-up algorithm is based on the following structural result: given a point θ that satisfies ∥θ -θ ⋆ ∥ ≳ ∆ 3n/4 (θ ⋆ ), we have F (θ; X (n) ) -F (θ ⋆ ; X (n) ) ≳ ∥θ -θ ⋆ ∥. (See Lemma 2.6 for a formal statement.) This result implies that, even though F (θ; X (n) ) 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 (θ;X (n) ) -F (θ ⋆ ; X (n) ) ≳ ∥θ -θ ⋆ ∥2 , 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 θ that is more than ∆ 3n/4 (θ ⋆ ) away from the minimizer, which is a data-dependent property, we first need to develop a private algorithm to estimate ∆ 3n/4 (θ ⋆ ) in order to make use of this property. In Section 2.1, we develop an efficient algorithm, RadiusFinder, for this task, which is inspired by [NSV16] . Our procedure assumes that we know some potentially very small lower bound r ≤ ∆ 3n/4 (θ ⋆ ), which is necessary by the impossibility results in [BNSV15] . Since the sample complexity of this procedure depends only on log(1/r), 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 ∆ 3n/4 (θ ⋆ ) ≤ ∆ ≤ O(∆ 4n/5 (θ ⋆ )). 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 to the growth condition we show that DP-GD makes a fast progress towards some point that is within O(∆ 4n/5 (θ ⋆ )) from the optimizer: in log(R) iterations, with high probability, it outputs θ 0 such that θ ⋆ is in the ball of radius O( ∆) = O(∆ 4n/5 (θ ⋆ )) centered at θ 0 . DP Cutting Plane Method for Private GM. The main drawback of using DP-SGD for the finetuning stage is that its run-time can be large when n ≫ d. To address this, we design the second fine-tuning algorithm, LocDPCuttingPlane, based on private variant of the cutting plane method that has faster running time when n 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 a crucial 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 (θ; X (n) ) has sensitivity proportional to R, so running the exponential 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 to ∆ 4n/5 (θ ⋆ ).Pure DP algorithm for Private Geometric Median Problem. In Section 4, we propose a pure (ε, 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 θ ∈ R d with a probability proportional to exp(-ε • len(X (n) , θ)/2) where len(X (n) , θ) is the minimum number of data points from X (n) that needs to be modified to obtain a dataset X(n) such that the geometric median of X(n) be equal θ. Our analysis shows that the proposed mechanism outputs θ = GM( X(n) ) such that X(n) and X (n) differ in at most k ⋆ = O(d log(R)/ε) with a high probability. Then, by a careful sensitivity analysis, we show ∥ θ -θ ⋆ ∥ can be upper bounded by the F (θ ⋆ ; X (n) ). Using this result we provide an algorithm with a multiplicative guarantee. Moreover, we show∥ θ -θ ⋆ ∥ is upper bounded O(∆ γn (θ ⋆ )) for some γ ∈ (1/2, 1].Lower bound on the Sample Complexity. We show every (ε, δ)-DP algorithm requires Ω(√ d/ε) samples so that it satisfies E θ∼An(X (n) ) [F ( θ; X (n) )] ≤ (1 + α) min θ∈R d F (θ, X (n) ) for a constant α.This result shows that the sample complexity of our polynomial-time algorithms is nearly optimal.A 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 1 compares the algorithms based on the achievable α mul and α add in order to F (A n (X (n) ); X (n) ) ≤ (1 + α mul )F (θ ⋆ ; X (n) ) + α add with a high probability.DP convex optimization is a well-studied problem [CMS11; KST12; BST14; ACGMMTZ16; STU17; FKT20]. There has been significant interest in developing new algorithms that offer improved guarantees compared to DP-(S)GD 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, [KDRT21; AGMRSSSTT22; GHNOSTTW23] explore the impact of public data, etc. The current paper addresses a drawback of DP-(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 [NSV16; 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] , hashing [NS18] , etc. The proposed quantile radius can be seen as a robust notion of radius proposed in [BHI02] .In one dimension (i.e., d = 1), private versions of the median are well studied [DNPR10; BNS13; BNSV15; DNRR15; BDRS18; ALMM19; KLMNS20; ASSU23; CLNSS23]. In particular, these works improve the dependence on the a priori bound R to log * R, rather than log R in our results.Let d ∈ N. For a vector x ∈ R d , ∥x∥ denotes the ℓ 2 norm of x. We use the following notation for the ball of radius R:B d (a, R) = {x ∈ R d : ∥x -a∥ ≤ R}. Also, B ∞ d (a, R) denotes {x ∈ R d : ∥x -a∥ ∞ ≤ R}. We refer to B d (0, R) = B d (R), similarly, it holds for B ∞ d (0, R) = B ∞ d (R). Let ⟨•, •⟩ denote the standard inner product in R d .For a convex and closed subset Θ ⊆ R d , let Π Θ : R d → Θ be the Euclidean projection operator, given by Π Θ (x) = arg min y∈Θ ∥y -x∥ 2 . For a (measurable) space R, M 1 (R) denotes the set of all probability measures on R. Let Z be the data space and let Θ ⊆ R d be the parameter space. Let f : Θ × Z → R be a loss function. We say f isL-Lipschitz iff there exists L ∈ R such that ∀z ∈ Z, ∀w, v ∈ Θ : |f (w, z) -f (v, z)| ≤ L∥w -v∥. 1.4 Notions of DP Definition 1.2. Let ε > 0 and δ ∈ [0, 1). A randomized mechanism A n : Z n → M 1 (Θ) is (ε, δ)-DP, iff,for every neighbouring dataset (i.e., replacement) X ∈ Z n and X ′ ∈ Z n , and for every measurable subset M ⊆ Θ, it holdsP θ∼An(X) (θ ∈ M ) ≤ e ε • P θ∼An(X ′ ) (θ ∈ M ) + δ.For some of our privacy analysis, we use concentrated differential privacy [DR16; BS16] , as it provides a simpler composition theorem -the privacy parameter ρ adds up when we compose. Definition 1.3 ([BS16, Def. 1.1]). A randomized mechanism A : Z n → M 1 (R) is ρ-zCDP, iff, for every neighbouring dataset (i.e., replacement) X ∈ Z n and X ′ ∈ Z n , and for every α∈ (1, ∞), it holds D α (A n (X)∥A n (X ′ )) ≤ ρα, where D α (A n (X)∥A n (X ′ )) is the α-Renyi divergence between A n (X) and A n (X ′ ).We should think of ρ ≈ ε 2 : to attain (ε, δ)-DP, it suffices to set ρ =ε 2 4 log(1/δ)+4ε [BS16, Lem. 3.5]. Lemma 1.4 ([BS16, Prop. 1.3]). Assume we have a randomized mechanism A : Z → M 1 (R) that satisfies ρ-zCDP, then for every δ > 0, A is (ρ + 2 ρ log(1/δ), δ)-DP.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 in 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 as long as it is clear that these goals are not attained by the paper. 
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.Algorithm 1 describes our private algorithm RadiusFinder for quantile radius estimation.Algorithm 1 RadiusFinder n 1: Inputs: data set X (n) ∈ (B d (R)) n , fraction γ ∈ (1/2, 1], privacy budget ρ-zCDP, failure probability β, discretization error 0 < r < R . 2: m = ⌈γn⌉. 3: For every ν ≥ 0 and i ∈ [n], let N i (ν) ≜ |X (n) ∩ B d (x i , ν)|.▷ Number of datapoints within distance of ν from x i 4: For every ν ≥ 0, defineN (ν) ≜ 1 m max distinct{i1,...,im}⊆[n] {N i1 (ν) + • • • + N im (ν)}. 5: Grid = {r, 2r, 4r • • • , 2 ⌈log( 2R r )⌉ r}. 6: Queries = {N (v) : v ∈ Grid} 7: î = AboveThreshold Queries, ρ, m + 18 √ 2ρ log 2 β • log 2R r ▷ Algorithm 7 8: Output ∆ = 2 îr if î ̸ = Fail; else Output Fail.Remark 2.1. The runtime of RadiusFinder is Θ((n 2 + n log(n)) log(⌈R/r⌉)): First, we need to compute the pairwise distances which take n 2 time. Then, for a fixed ν, we can compute N (ν) using the pairwise distances in time Θ(n 2 ). To compute N (ν), we need to sort{N i (ν)} i∈[n] , in Θ(n log(n))time, and pick top m. Finally, we need to repeat this for each ν ∈ [r, . . . , 2 ⌈log( 2R r )⌉ r]. ◁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 1 is based on the following lemma. Lemma 2.2. Fix n ∈ N. For every dataset X (n) , for every 1/2 ≤ γ ≤ 1 and for every fixed ν, the query The objective of Algorithm 1 is to privately approximate ∆ γn (θ ⋆ ). 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 ∆ γn (θ ⋆ ).N (ν) ≜ 1 m max {i1,...,im}⊆[n] {N i1 (ν) + • • • + N im (ν)},Lemma 2.3. Fix n ∈ N, 1 ≤ m ≤ n, γ 1 , γ 2 ∈ (1/2, 1] such that γ 2 ≥ γ 1 , and dataset X (n) . For every ν ≥ 0, define N (ν) ≜ 1 m max {i1,...,im}⊆[n] {N i1 (ν) + • • • + N im (ν)}, where N i (ν) ≜ |X (n) ∩B d (x i , ν)|. Let θ ⋆ = GM(X (n) ).For every ν such that N (ν) ≥ ⌈γ 1 n⌉ and N (ν/2) < ⌈γ 2 n⌉, we have∆ γ1n (θ ⋆ ) • 2γ 1 -1 4γ 1 -1 ≤ ν ≤ 4∆ γ2n (θ ⋆ ).Using these two lemmas, in the next theorem, we present the privacy and utility guarantees of Algorithm 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 RadiusFinder n denote Algorithm 1. Fix d ∈ N, R > 0, r > 0, β ∈ (0, 1], and ρ > 0. Then, for every n ∈ N and every dataset X (n) ∈ (B d (R)) n the output of RadiusFinder n satisfies ρ-zCDP. Also, the output of RadiusFinder n satisfies the following utility guarantees:1. Given n > 18 (1-γ) √ 2ρ log(4/β), then P ∆ γn (θ ⋆ ) 2γ-1 4γ-1 ≤ ∆ ≥ 1 -β.2. Assume that the data points satisfies N (r) < m.Let γ ≜ min{γ + 1 n 36 √ 2ρ log 2( log 2R r + 1)/β , 1}, then, given n > 18 (1-γ) √2ρ log(4/β), we haveP ∆ γn (θ ⋆ ) 2γ -1 4γ -1 ≤ ∆ ≤ 4∆ γn (θ ⋆ ) ≥ 1 - 5 2 β. 3. Let γ ≜ min{γ + 1 n 36 √ 2ρ log 2( log 2R r + 1)/β , 1}. Given n > 18 (1-γ) √2ρ log(4/β), we haveP ∆ γn (θ ⋆ ) 2γ -1 4γ -1 ≤ ∆ and ∆ ≤ 4∆ γn (θ ⋆ ) or ∆ = r ≥ 1 -2β. Remark 2.5. A sufficient condition for N (r) < m in Item 2 is that max i∈[n] |X (n) ∩ B d (x i , r)| < m = ⌈γn⌉.Intuitively, this means that no data point should have a significant portion of other data points within a ball of radius r centered on it. ◁In the second step of 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 n ∈ N,X (n) ∈ (R d ) n and θ 1 , θ 0 ∈ R d . For every γ ∈ [0, 1], define ∆ γn (θ 0 ) ≜ min{r ≥ 0 : |i ∈ [n] : ∥x i -θ 0 ∥ ≤ r| ≥ γn}. Assume there exists ζ ≥ 0 such that F (θ 1 ; X (n) ) - F (θ 0 ; X (n) ) ≤ ζn.Then, for every γ ∈ (1/2, 1], we have(2γ -1)∥θ 1 -θ 0 ∥ -2γ∆ γn (θ 0 ) ≤ ζTo gain some intuition behind Lemma 2.6, let us instantiate θ 0 = θ ⋆ . This result implies that for a θ ∈ R d such that ∥θ -θ ⋆ ∥ ≳ ∆ γn (θ ⋆ ), the loss function of the geometric median satisfies F (θ; X (n) ) -F (θ ⋆ ; X (n) ) ≳ ∥θ -θ ⋆ ∥.2: γ = 3/4 3: ∆ = RadiusFinder n X (n) , γ, ρ 2 , β 2 , r ▷ Algorithm 1 4: if ∆ = Fail then 5:Output Fail and Halt.6: k wu = 1 log(2) log R/ ∆ ▷ k wu ≤ 1 log(2) log(R/r) with probability one 7: θ 0 = 0 ∈ R d , T wu = 500, rad 0 = R 8: for t ∈ {0, . . . , k wu -1} do 9: Θ t = {θ ∈ B d (R) : ∥θ -θ t ∥ ≤ rad t } 10: η t = rad t 2dkwu 3ρn 2 11: θ t+1 = DPGD θ t , X (n) , ρ 2kwu , Θ t ,P θ ⋆ ∈ Θ loc and ∆ 0.75n (θ ⋆ ) ≤ 4 ∆ and ∆ ≤ 4∆ 0.8n (θ ⋆ ) ≥ 1 -2β.3 Private Fine-tuningIn Section 2, we developed an algorithm for the warm-up stage. The output of the warm-up stage is θ 0 and radius ∆ such that ∥θ 0 -θ ⋆ ∥ ≤ O( ∆) and ∆ = O(∆ 4n/5 (θ ⋆ )) as formalized in Theorem 2.7.In this section, we build upon the output of the warm-up algorithm to develop two polynomial-time algorithms for the fine-tuning stage.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: In Section 7, we discussed two limitations of our work.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 to 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, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 in Theorem 2.7, the distance of the initialization and θ ⋆ only depends on ∆, i.e., it does not depend on R, 2) By definition of the quantile radius in Definition 1.1 and Equation (1), we have that F (θ ⋆ ; X (n) ) ≥ (1 -γ)n∆ γn (θ ⋆ ), 3) in the case that the data satisfies some regularity conditions, we have ∆ ≤ 4∆ 0.8n (θ ⋆ ) from Theorem 2.7. The next theorem summarizes the utility and privacy guarantees of this algorithm.Algorithm 3 LocDPGD n 1: Inputs: dataset X (n) ∈ (B d (R)) n , privacy parameters ρ-zCDP, discretization error r, failure probability β. 2: θ0, ∆ = Localizationn X (n) , ρ 2 , r, β 2 ▷ Algorithm 2 3: Θ0 = {θ ∈ B d (R) : ∥θ -θ0∥ ≤ 25 ∆} 4: ηft = 50 ∆ d 6ρn 2 and Tft = n 2 ρ 256d 5: θ = DPGD θ0, X (n) , ρ 2 , Θ0,P F θ; X (n) ≤ 1 + O √ d n √ ρ log(1/β) F θ ⋆ ; X (n) + O d log(1/β) ρ r ≥ 1 -2β.Moreover, given that the datapoints satisfies max i∈[n] |X (n) ∩ B d (x i , r)| < 3n/4, we haveP F θ; X (n) ≤ 1 + O √ d n √ ρ log(1/β) F θ ⋆ ; X (n) ≥ 1 -2β,where θ is the output of Algorithm 3.In this section, we present the second fine-tuning algorithm: LocDPCuttingPlane of Algorithm 4. This algorithm is based on the well-known cutting plane method [New65; Lev65; Nes98].Algorithm 4 LocDPCuttingPlane n 1: Inputs: dataset X (n) ∈ (B d (R)) n , privacy parameters (ε, δ)-DP, discretization error r, failure probability β 2: ρ = ε 2 16 log(2/δ)+8ε 3: θ0, ∆ = Localizationn X (n) , ρ 2 , r, min{ β 3 , δ 2 } ▷ Algorithm 2 4: Θ0 = {θ ∈ B d (R) : ∥θ -θ0∥ ≤ 25 ∆} 5: kft = Θ d τ log n √ τ •ρ √ d + √ d ▷ See Assumption 1 for definition of τ 6: for t ∈ {0, . . . , kft -1} do 7: θt = Centre(Θt) ▷ See Assumption 1 8: ξdir,t ∼ N 0, k ft ρ I d 9: Θt+1 = θ ∈ Θt ∇F (θt; X (n) ) + ξdir,t, θ -θt < 0 10: Define Probability Measure: π(t) ∝ exp - ε 448 ∆ F θt; X (n) for t ∈ {0, . . . , kft -1} 11: Output θ t where t ∼ πSimilar to non-private cutting plane method, LocDPCuttingPlane is not a descent algorithm. As a result, we need to devise a 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 (θ; X (n) ) defined in Equation (1). Note that the sensitivity of F (θ; X (n) ) is R. However, the next result demonstrates that through a novel analysis of the sensitivity of F (θ; X (n) ), the noise scale due to privacy can be significantly reduced. Proof can be found in Appendix E.Lemma 3.2. Let ε ∈ R, k ∈ N, and d ∈ N be constants. Let Θ ⊆ R d be a set with a bounded diameter of diam. Let X (n) ∈ (R d ) n be a dataset and θ ⋆ ∈ GM(X (n) ). Let {θ 1 , . . . , θ k } ⊆ Θ be k fixed vectors. Also, assume that θ ⋆ ∈ Θ. Let ∆ be such that 3∆ 3n/4 (θ ⋆ ) + 2diam ≤ ∆.Consider the following probability measure over {1, . . . , k}:π(i; X (n) ) = exp -ε 2∆ F (θ i ; X (n) ) j∈[k] exp -ε 2∆ F (θ j ; X (n) ) , i ∈ [k]. 1. Let î ∼ π(•; X (n) ) and OPT ≜ min i∈[k] {F (θ i ; X (n) ) -F (θ ⋆ ; X (n) )}.Then, for every β ∈ (0, 1], we haveP F (θ î; X (n) ) -F (θ ⋆ ; X (n) ) ≤ OPT + 2∆ ε log(k/β) ≥ 1 -β.2. Let X(n) be a dataset of size n that differs in one sample from X (n) . Then, for every i ∈[k], we have exp(-ε)π(i; X(n) ) ≤ π(i; X (n) ) ≤ exp(ε)π(i; X(n) ).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 Θ 0 , defined in Line 4 of Algorithm 4, satisfies θ ⋆ ∈ Θ 0 . Ergo, the privacy guarantee of Algorithm 4 only satisfies approximate-DP.Theorem 3.3. Let LocDPCuttingPlane n denote Algorithm 4. Fix d ∈ N, R > 0, r > 0, ε > 0, δ ∈ (0, 1],and β ∈ (0, 1]. Then, for every n ∈ N and every datasetX (n) ∈ (B d (R)) n the output of LocDPCuttingPlane n satisfies (ε, δ)-DP.We also make the following assumption about the performance of Centre subroutine in Algorithm 4. Assumption 1. There exists some τ ∈ (0, 1] such that for all t ∈ {0, . . . , k ft -1}, the subroutine of Centre in Algorithm 4 satisfies vol(Θ t+1 ) ≤ (1 -τ )vol(Θ t ). Furthermore, the time for calling the routine Centre is T c .Using the John Ellipsoid [Joh14] as the Centre makes τ a dimension independent constant and T c = Õ(d 1+ω ) (by [LSW15] ). Now we are ready to state the utility guarantee of Algorithm 4.Theorem 3.4. Let LocDPCuttingPlane n denote Algorithm 4. For every d ∈ N, R > 0, r > 0, ε > 0, δ ∈ (0, 1], and β ∈ (0, 1], A = {LocDPCuttingPlane n } n≥1 satisfies the following: for every n ∈ N and every datasetX (n) ∈ (B d (R)) n , given n ≥ Ω max d log(⌈R/r⌉) √ ρ log log(⌈R/r⌉) β , 1 √ ρ log ⌈R/r⌉ β , where ρ = ε 2 16 log(2/δ)+8ε , we have the following: Let κ ≜ n √ ρ √ d + √ d and α = O d log(κ) τ ρ • log d log(κ) τ β. Then,P F θ; X (n) ≤ 1 + α n F (θ ⋆ ; X (n) ) + rα ≥ 1 -3β,Moreover, assuming that the datapoints satisfiesmax i∈[n] |X (n) ∩ B d (x i , r)| < 3n/4, we have P F θ; X (n) ≤ 1 + α n F (θ ⋆ ; X (n) ) ≥ 1 -3β,where θ is the output of Algorithm 4.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: In our problem setup, we completely discussed all the assumptions. Also, a 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 crossreferenced. • 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 to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
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 (n) . Before presenting the algorithm, we need a definition: For twosequences of a = (a 1 , . . . , a n ) ∈ (R d ) n and b = (b 1 , . . . , b n ) ∈ (R d ) n , we define the hamming distance as d H (a, b) = n i=1 1[a i ̸ = b i ].The proposed algorithm is shown in Algorithm 5, and its utility and privacy guarantees are presented in the following theorem. Theorem 4.1. Let SInvS n denote the algorithm in Algorithm 5. Fix d ∈ N, R > 0, r > 0, and ε > 0. Then, for every n ∈ N and every dataset X (n) ∈ (B d (R)) n the output of SInvS n satisfies ε-DP. Also, for every β ∈ (0, 1) and for every n > 2k ⋆ ≜ 2 2 ε (log(1/β) + d log(R/r)) , with probability at least 1 -β, we have:1. The value of the cost function satisfiesF ( θ; X (n) ) ≤ 1 + 4k ⋆ n -2k ⋆ F (θ ⋆ ; X (n) ) + nr. Algorithm 5 SInvS n 1: Input: dataset X (n) ∈ (B d (R)) n , privacy parameter ε-DP, discretization error r. 2: For every y ∈ B d (R) len r (X, y) ≜ min X∈(R d ) n {d H (X (n) , X(n) ) such that ∃z ∈ B d (y, r) with GM( X(n) ) = z} 3: Define density: dπ(y) = exp -ε 2 • len r (X, y) y∈B d (R) exp -ε 2 • len r (X, y) dy 1[y ∈ B d (R)] 4: Output θ ∼ π 2. In terms of distance, θ -θ ⋆ ≤ r + min γ∈(1/2,1]:γ> k ⋆ n + 1 2 ∆ γn (θ ⋆ ) 2(γ -k ⋆ /n) -(γ -k ⋆ /n) 2 .The proof of Theorem 4.1 is provided in Appendix F. The proof is based on showing that the outputθ = GM X(n) is such that X(n) and X (n) differ in at most k ⋆ = O(d log(R)/ε) datapoints with a high probability. Then, we use the properties of the geometric median to show that the sensitivity of GM to changing k < n/2 points can be bounded by the value of the optimal loss at θ ⋆ = GM(X (n) ). Lemma 4.2. For every n ∈ N and for every k < n 2 , and for every(x 1 , . . . , x n , y 1 , . . . , y k ) ∈ (R d ) n+k , define θ 0 = GM((x 1 , . . . , x n )) and θ k = GM((x 1 , . . . , x n-k , y 1 , . . . , y k )). Then, ∥θ k -θ 0 ∥ ≤ 2 n -2k F (θ 0 ; (x 1 , . . . , x n )).Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: In 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. 
lower bound on the sample complexity: 
 In this section we prove a lower bound on the sample complexity of any (ε, δ)-DP algorithm for the task of private geometric median with a multiplicative error. Theorem 5.1. Let ε 0 , α 0 , d 0 be universal constants. Then, for every ε ≤ ε 0 , α ≤ α 0 , and d ≥ d 0 and every (ε, δ)-DP algorithmA n : (R d ) n → M 1 (R d ) (with δ = Õ( √ d/n)) such that for every dataset X (n) ∈ (R d ) n its output satisfies E θ∼An(X (n) ) F θ; X (n) ≤ (1 + α) min θ∈B ∞ d (1) F (θ; X (n) ), we require n = Ω √ d ε .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. F( ;Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
numerical example: 
 X (n) )/F( ; X (n) ) d = 200, n = 3000, = 2, = 1/n Ours DPGDIn this section, we numerically compare LocDPGD n (Algorithm 3) and DPGD on a synthetic dataset. The dataset consists of two subsets: one tightly clustered at a random location on B d (R), and the other uniformly distributed over B d (R). We plot F (θ;X (n) )/F (θ ⋆ ; X (n) )for both algorithms as R varies. The results show that LocDPGD n 's performance degrades more gracefully than DP-GD with increasing R. See Appendix H for experimental details and more results.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 not include experiments.• The experimental setting should be presented in the core of the paper to a 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, or as supplemental material. 
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: we believe our warm-up algorithm has broader applications, and finding other problems where it can be used as a subroutine is interesting. Another direction is to characterize the optimal run-time: is it possible to develop a linear time algorithm, i.e. Θ(nd), with an optimal excess error?NeurIPS Paper ChecklistQuestion: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? 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, confidence intervals, or statistical significance tests, at 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 run with given experimental conditions).• 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: It is not applicable to our work.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses 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 our work.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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 our work.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as details about compensation (if any)?Answer: [NA] Justification: It is not applicable to our work.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: It 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 NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: • The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is 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 is a specific model and empirical evaluation, it 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 is 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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 to have some path to reproducing or verifying the results.A.1 Gradient of the Geometric LossEQUATIONA.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 DPGD1: Inputs: initialization point θ1 ∈ R d , dataset X (n) ∈ (R d ) (n) , privacy budget ρ, feasible set Θ, stepsize η, number of iterations T . 2: σ 2 = T 2ρn 2 3: for t ∈ {1, . . . , T } do θt+1 = ΠΘ(θt -η(∇F (θt; X (n) ) + ξt)),where ξt ∼ N (0, σ 2 I d ).1 T T t=1 θtLemma A.1. Let Θ ⊆ R d be a closed and convex set with a finite diameter diam. Let ℓ : Θ × Z → R be a loss function such that for every z ∈ Z, ℓ(•, z) is convex and L-Lipschitz. LetX (n) = (z 1 , . . . , z n ) ∈ Z n and Ln (θ) = 1 n i∈[n] ℓ(θ, z i ). Consider DP-Gradient descent algorithm θ t+1 = Π Θ (θ t -η(∇ Ln (θ t ) + ξ t )), where ξ t ∼ N (0, σ 2 I d ). Then, for every T ∈ N, by settingη = diam d 12L 2 ρn 2 , and σ 2 = L 2 T2ρn 2 , we have the following: {θ t } t∈[T ] satisfies ρ-zCDP. Also, for every β > 0, given T d ≥ log(4/β) and 1 ≤ 56 log(2/β), with probability at least 1 -β, we haveLn   1 T t∈[T ] θ t   -min θ∈Θ Ln (θ) ≤ L • diam 16 √ d n √ ρ log(2/β) + √ 2 √ T .Proof. The privacy proof is based on the zCDP analysis of the Gaussian mechanism and the composition property of zCDP [BS16] .Let g t ≜ ∇ Ln (θ t ) + ξ t and θ ⋆ ∈ arg min θ∈Θ Ln (θ). Note that we can replace ∇ Ln (θ t ) by any subgradient at θ t . By the convexity of ℓ and the first-order convexity condition we can writeLn   1 T t∈[T ] θ t   -Ln (θ ⋆ ) ≤ 1 T i∈[T ] Ln (θ t ) -Ln (θ ⋆ ) ≤ 1 T t∈[T ] ∇ Ln (θ t ), θ t -θ ⋆ .Then, by the contraction property of the projection, we can write∥θ t+1 -θ ⋆ ∥ 2 = ∥Π Θ (θ t -ηg t ) -θ ⋆ ∥ 2 ≤ ∥θ t -θ ⋆ -ηg t ∥ 2 = ∥θ t -θ ⋆ ∥ 2 + η 2 ∥g t ∥ 2 -2η⟨g t , θ t -θ ⋆ ⟩ ≤ ∥θ t -θ ⋆ ∥ 2 + 2η 2 ∇ Ln (θ t ) 2 + ∥ξ t ∥ 2 -2η⟨g t , θ t -θ ⋆ ⟩ ≤ ∥θ t -θ ⋆ ∥ 2 + 2η 2 L 2 + 2η 2 ∥ξ t ∥ 2 -2η⟨g t , θ t -θ ⋆ ⟩.Here, we have used for every a, b ∈ R d , ∥a + b∥ 2 ≤ 2∥a∥ 2 + 2∥b∥ 2 , and ∇ Ln (θ) ≤ L for every θ. Therefore, we conclude thatEQUATION)Define the following random variable for every t ∈ [T ]EQUATIONAlso, define the following filtrationEQUATIONwhich is the sigma-field generated by θ 0 , . . . , θ t .Lemma A.2. {Y t } t∈[T ] is a martingale difference sequence adapted to {F t } t∈[T ] .Proof. Notice that ∇ Ln (θ t ), θ t , and θ ⋆ are F t -measurable. Therefore, we can writeE[Y t |F t ] = E[⟨g t , θ t -θ ⋆ ⟩ -∇ Ln (θ t ), θ t -θ ⋆ |F t ] = ⟨E[g t |F t ], θ t -θ ⋆ ⟩ -∇ Ln (θ t ), θ t -θ ⋆ .By definition ξ t is independent of the history up to time t. Therefore,EQUATIONTherefore, E[Y t |F t ] = 0. Moreover, by Cuachy-Schwartz inequality and the boundedness of Θ we can writeE[|Y t |] = E[|⟨ξ t , θ t -θ ⋆ ⟩|] ≤ E[∥ξ t ∥∥θ t -θ ⋆ ∥] ≤ RE[∥ξ t ∥] < ∞. (8) Therefore, {Y t } t∈[T ]is a martingale difference sequence as was to be shown.Using Equation (4) and by the definition of Y t in Equation (5), we can write∇ Ln (θ t ), θ t -θ ⋆ ≤ 1 2η ∥θ t -θ ⋆ ∥ 2 -∥θ t+1 -θ ⋆ ∥ 2 + η∥ξ t ∥ 2 + ηL 2 + Y t .Summing it from 0 to T -1 givesEQUATIONAnalyzing (A) in Equation ( 9)Notice that t∈[T ] ∥ξ t ∥ 2 d = σ 2 ∥Y ∥ 2 .Therefore, for every β ∈ (0, 1) provided that T d ≥ log(4/β), with probability at least 1 -β/2, we haveEQUATION)Analyzing (B) in Equation (9) Lemma A.3 (Shamir [Sha11] ). Let m ∈ N. Let {Z m } m∈[M ] be a martingale difference sequence adapted to a filtration {F m } m∈[M ] , and suppose there are constants b > 1 and c > 0 such that for any m and any α > 0, it holds thatP(|Z t | ≥ α|F t ) ≤ b exp(-cα 2). Then for any β > 0, it holds with probability at least 1 -β that1 M m∈[M ] Z m ≤ 28b log(1/β) cM .We can rephrase Equation (5) asY t = ∇ Ln (θ t ), θ t -θ ⋆ -⟨g t , θ t -θ ⋆ ⟩ = ⟨ξ t , θ ⋆ -θ t ⟩.Notice that condition on F t , ⟨ξ t , θ ⋆ -θ t ⟩|F t ∼ N (0, σ 2 ∥θ t -θ ⋆ ∥ 2 ). Therefore,P(|⟨ξ t , θ ⋆ -θ t ⟩| ≥ α|F t ) ≤ 2 exp - α 2 2σ 2 ∥θ t -θ ⋆ ∥ 2 ≤ 2 exp - α 2 2σ 2 R 2 .Note that the bound holds for every t ∈ [T ]. Therefore, using Lemma A.3, with probability at least 1 -β/2, we haveEQUATIONFrom Equation (9), Equation (10), and Equation ( 11), we have with probability at least 1 -βLn   1 T t∈[T ] θ t   -min θ∈Θ Ln (θ) ≤ R 2 2ηT + ηL 2 + ησ 2 d 1 + 4 log(4/β) T d + 2σR 28 log(2/β) T , (12) provided that T d ≥ log(4/β). Let σ 2 = L 2 T 2ρn 2 , η = R L √ T • 1 2 + 5dT ρn 2.Using these parameters, we obtain thatEQUATIONwhere the last step is by assuming that 1 ≤ 56 log(2/β).Algorithm 7 AboveThreshold1: Inputs: Queries {f0, . . . , f k-1 }, Privacy Budget ρ-zCDP, Threshold T . 2: ξtresh ∼ Lap 6 √ 2ρ 3: T = T + ξtresh 4: for i ∈ [k] do 5: ξi ∼ Lap 12 √ 2ρ 6: if fi + ξi > T : then 7:Output ∆ = i. 8: Halt 9: Output Fail.Lemma C.1. Let σ > 0. Let Y be a random variable with the distribution N (0, σ 2 ). Then, for everyβ ∈ (0, 1], we have P |Y | > σ 2 log(2/β) ≤ β.). Let m ∈ N. Consider random vector Y ∼ N (0, I m ). Then, for every t ≥ 0,P ∥Y ∥ 2 ≥ m + 2 √ tm + 2t ≤ exp(-t) Corollary C.3. Let β ∈ (0, 1), m ∈ N, and m ≥ log 2 β . Consider Y ∼ N (0, I m ), then P m 1 -2 log( 2 /β) m ≤ ∥Y ∥ 2 ≤ m 1 + 4 log( 2 /β) m ≥ 1 -β, Lemma C.4. Let n ∈ N and n ≥ 4. Let X (n) ∈ (R d ) n and X(n) ∈ (R d) n be two datasets that differ in one sample. Let θ ⋆ ∈ GM(X (n) ) and θ ⊛ ∈ GM( X(n) ). Let ∆ 3n/4 (θ ⋆ ) be the radius of the ball around θ ⋆ that contains at least 3n/4 of X (n) . Then,θ ⊛ -θ ⋆ ≤ 3 2 ∆ 3n/4 (θ ⋆ ).Proof. The proof is by contrapositive. In particular, we show that for everyθ ∈ R d such that ∥θ -θ ⋆ ∥ > 3 2 ∆ 3n/4 (θ ⋆ ), we have, θ / ∈ GM( X(n) ). Let I = {i ∈ [n] : x i ∈ B d (θ ⋆ , ∆ 3n/4 (θ ⋆ )) and x i ∈ X(n) }. Using the variational representation of ∥•∥ 2 , we can write ∇F (θ; X(n) ) ≥ ∇F (θ; X(n) ), θ -θ ⋆ ∥θ -θ ⋆ ∥ = i∈I θ -x i ∥θ -x i ∥ , θ -θ ⋆ ∥θ -θ ⋆ ∥ + i∈[n]\I θ -x i ∥θ -x i ∥ , θ -θ ⋆ ∥θ -θ ⋆ ∥ ≥ i∈I θ -x i ∥θ -x i ∥ , θ -θ ⋆ ∥θ -θ ⋆ ∥ -(n -|I|)where the last step follows from Cauchy-Schwarz inequality. Then, we can writeEQUATIONTherefore ∥θ ⊛ -θ ⋆ ∥ ≤ 3/2∆ 3n/4 (θ ⋆ ).Lemma C.5. For every n ∈ N and for every X (n) = (x 1 , . . . , x n ), we have GM (X (n) ) lies in the convex hull of {x 1 , . . . , x n }.Lemma C.6. Let (x 1 , . . . , x n ) ∈ (R d ) n be a dataset and θ ⋆ = GM((x 1 , . . . , x n )). Let B ⊆ [n] such that |B| < n/2. Then, for every θ, we have∥θ -θ ⋆ ∥ ≤ 2n -2|B| n -2|B| max i / ∈B ∥θ -x i ∥.Proof. It is a simple modification of [CLMPS16, Lemma. 24 ].Proof of Lemma 2.2. The proof follows closely [NSV16, Lemma 4.5]. Let X and X ′ are two neighboring datasets of size n that differ in the first sample. For a fixed ν and i ∈[n], if i ̸ = 1, N i (ν)can 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 ((m -1) + n) ≤ 1 + n m ≤ 1 + 1 γ ≤ 3 where the last step follows from γ ≥ 1/2.Proof of Lemma 2.3. Let ν be such that N (ν) ≥ ⌈γ 1 n⌉, by definition of N (•) it means that there exists a datapoint x i such that the ball of radius ν around it contains at least ⌈γ 1 n⌉ datapoints. Let B = {j ∈ [n] : ∥x i -x j ∥ > ν}. By the described argument, we have |B| ≤ (1 -γ 1 )n. Then, we invoke Lemma C.6 with the described B and θ = x i to obtain∥θ ⋆ -x i ∥ ≤ 2n -2(1 -γ 1 )n n -2(1 -γ 1 )n ν = 2γ 1 2γ 1 -1 ν.The first step follows because function h : R → R, h(z) = 2n-2z n-2z is increasing for z < n/2. In the next step, we use the triangle inequality to write∆ γ1n (θ ⋆ ) ≤ ∆ γ1n (x i ) + ∥x i -θ ⋆ ∥ ≤ ν + 2γ 1 2γ 1 -1 ν = 4γ 1 -1 2γ 1 -1 ν, where ∆ • (•) is defined in Definition 1.1.Next, we turn into proving the upperbound on ν. By assumption N (ν/2) < ⌈γ 2 n⌉. For the sake of contradiction, assume that ν > 4∆ γ2n (θ ⋆ ). Then, consider the setG = {i ∈ [n] : ∥θ ⋆ -x i ∥ ≤ ∆ γ2n (θ ⋆ )}.By definition, |G| ≥ ⌈γ 2 n⌉. Consider an arbitrary subset of G with the size of ⌈γ 2 n⌉. The main observation, which follows from the triangle inequality, is that a ball of radius 2∆ γ2n (θ ⋆ ) around every point in G contains at least ⌈γ 2 n⌉ datapoint. Therefore, N (ν/2) ≥ N (2∆ γ2n (θ ⋆ )) ≥ ⌈γ 2 n⌉ which contradicts with the assumption that N (ν/2) < ⌈γ 2 n⌉.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 2R r ⌉. It is simple to see thatP ∆ = Fail ≤ P N (2 k r) + ξ k ≤ m + ξ thresh = P(n -m ≤ ξ thresh -ξ k ) ≤ P((1 -γ)n ≤ ξ thresh -ξ k )where the last step follows from the assumption that max xi,xj ∈X (n) ∥x i -x j ∥ ≤ 2R, which gives us N (2 k r) = n by the definition of N (•). By a simple tail bound on the Laplace distribution, wehave P |ξ thresh | ≥ 6 √ 2ρ log(4/β) ≤ β/4 and P |ξ k | ≥ 12 √ 2ρ log(4/β) ≤ β/4. Therefore, given n > 1 1-γ 18 √ 2ρ log(4/β), P(n -m ≤ ξ thresh -ξ k ) ≤ β/2.Part 2: Lemma C.6 implies that for every ν such that N (ν) ≥ ⌈γn⌉, we have, ∆ γn (θ ⋆ ) • 2γ-1 4γ-1 ≤ ν. Therefore, we can writeEQUATION)Under the event that ∆ ̸ = Fail, there exists i ∈ {0, . . . , k -1}, such thatN ( ∆) + ξ i ≥ m + 18 √ 2ρ log(2(k + 1)/β) + ξ threshBy a simple tail bound and union bound, we haveEQUATION)where k = ⌈log 2R r ⌉. We further upperbound the first term in Equation ( 15) as follows P N ∆ < ⌈γn⌉ and ∆ ̸ = Fail ≤ P N ∆ < ⌈γn⌉ and ∆ ̸ = Fail and B c + P(B).We claim that the first term in this equation is zero. Recall that m = ⌈γn⌉. Under the event B c , ξ thresh -ξ i ≥ -18 √ 2ρ log(2(k + 1)/β) and as a result, m + 18 √ 2ρ log(2(k + 1)/β) + ξ thresh -ξ i ≥ m. Therefore, it shows that the probability of the first term is zero. Also, as showed above, P(B) ≤ β/2. Therefore, P N ∆ < ⌈γn⌉ ≤ P(B)+P ∆ = Fail . Combining it with P ∆ = Fail ≤ β/2 concludes the proof.Part 3: Assume that N (r) < m. Let k = ⌈log 2R r ⌉. Let γ = γ + 1 n 18 √ 2ρ log(2(k + 1)/β).In Part 2, we showed that given n > 18 √ 2ρ log(4/β), we haveP ∆ γn (θ ⋆ ) 2γ -1 4γ -1 ≤ ∆ ≥ 1 -β.We only focus on the upperbound. From Lemma 2.3, we have where the last step follows from the union bound. For the first term, we haveEQUATIONEQUATIONwhere î = log ∆/2r -1. The last step follows from the following observation: under the event that ∆ / ∈ {r, Fail}, during the execution of Algorithm 7, both N ( ∆) and N ( ∆/2) are compared to the noisy threshold. Using the tail bounds in Equation ( 16), we have under the event B c , with probability at least1 -β/2, m + 18 √ 2ρ log 2 β • log 2R r + ξ thresh -ξ î ≤ m + 18 √ 2ρ log 2 β • log 2R r + 18 √ 2ρ log(2(k + 1)/β) ≤ m + 36 √ 2ρ log(2(k + 1)/β).This shows that we haveP N ∆/2 > ⌈γn⌉ and ∆ / ∈ {r, Fail} and N ( ∆/2) + ξ î < m + 18 √ ρ log 2 β • log 2R r + ξ thresh ≤ β/2.In the next step, we bound P ∆ = r . Notice thatP ∆ = r = P N (r) + ξ 1 > m + 18 √ 2ρ log 2 β • log 2R r + ξ thresh .Using simple tail bound, we haveP ξ thresh -ξ 1 ≤ -18 √ 2ρ log 2 β • log 2R r≤ β/2 which shows that P ∆ = r ≤ β/2 since we assume that N (r) < m. Therefore, combining all the pieces together, we provedP ∆ γn (θ ⋆ ) 2γ -1 4γ -1 ≤ ∆ ≤ 4∆ γn (θ ⋆ ) ≥ 1 - 5β 2 .Part 4: In Part 2, we showed that given n >18 (1-γ) √2ρ log(4/β), we haveEQUATIONConsider the following event E = ∆ ≤ 4∆ γn (θ ⋆ ) or ∆ = r . We haveP(E c ) = P ∆ > 4∆ γn (θ ⋆ ) and ∆ ̸ = r ≤ P ∆ > 4∆ γn (θ ⋆ ) and ∆ ̸ = {r, Fail} + P ∆ = Fail ≤ P N ∆/2 > ⌈γn⌉ and ∆ ̸ = {r, Fail} + P ∆ = 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 as most β/2. We also have that P ∆ = Fail ≤ β/2 from Part 1. Therefore, P(E c ) ≤ β. Combining it with Equation (19) concludes the proof.Proof of Lemma 2.6.Let I = {i ∈ [n] : ∥θ 0 -x i ∥ ≤ ∆ γn (θ 0 )}.For every i ∈ I, we have ∥x i -θ 0 ∥ ≤ ∆ γn (θ 0 ). Using the triangle inequality, for every i ∈ I, we can writeEQUATION) Then, for every i / ∈ I, by an application of the triangle inequality ∥θ 1 -EQUATIONThen, by adding both sides of Equation (20) and Equation (21), we haveF (θ 1 ; X (n) ) -F (θ 0 ; X (n) ) ≥ |I|∥θ 1 -θ 0 ∥ -(n -|I|)∥θ 1 -θ 0 ∥ -2|I|∆ γn (θ 0 ).EQUATIONLet γ ′ n = |I|. We know that γ ′ ≥ γ. Using this representation we can write∥θ 1 -θ 0 ∥ ≤ ζ + 2γ ′ ∆ γn (θ 0 ) 2γ ′ -1 .For a fixed a, b > 0 define h(x) ≜ a+2xb 2x-1 . For x > 1/2, dh(x) dx = -2(a+b) (2x-1) 2 . This shows that h(x) is decreasing for x > 1/2. Therefore using this observationζ + 2γ ′ ∆ γn (θ 0 ) 2γ ′ -1 ≤ ζ + 2γ∆ γn (θ 0 ) 2γ -1 ,as was to be shown.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 ρ-zCDP.For the claim regarding utility, in the first step, consider the recursion in Line 12 of Algorithm 2, i.e., rad t+1 = 1 2 rad t + 12 ∆ initialized at rad 0 = R. It can be easily shown that rad m = 1 2 m rad 0 + 12 ∆ m-1 i=0 (1/2) i for m ≥ 1. In particular, let k wu = 1 log(2) log R/ ∆ , then, we obtain that rad kwu ≤ 25 ∆.Let γ = 3/4 and γ = γ + 1 n 36 √ 2 √ 2ρ log 2 log 2R r + 1 2 β ≤ 0.75 + 0.05 = 0.8,where the last step follows because n ≥ Ω 1 √ ρ log((⌈log(R/r)⌉ + 1)/β) . Then, define the following eventG 1 = ∆ 0.75n (θ ⋆ ) ≤ 4 ∆ and ∆ ≤ 4∆ 0.8n (θ ⋆ ) or ∆ = r .In the next step, we analyze the probability that θ ⋆ ∈ Θ loc . We claim thatP θ ⋆ ∈ Θ loc G 1 ≥ (1 -β/(2k wu )) kwu .We prove this by induction. In particular, we claim that for every m ∈ {0, . . . , k wu } we haveP θ ⋆ ∈ Θ m G 1 ≥ (1 -β/(2k wu )) m . Note that we Θ loc = Θ kwu .For the base case, by the assumption that the datapoints are in B d (R), we have P(θ ⋆ ∈ Θ 0 |G 1 ) = P(θ ⋆ ∈ Θ 0 ) = 1 since Θ 0 is trivially independent of every random variable. Then, we show the claim for m ∈ {1, . . . , k wu } assuming the claim holds for m -1. We can writeEQUATIONWe claim thatP ∥θ ⋆ -θ m ∥ ≤ rad m θ ⋆ ∈ Θ m-1 and G 1 ≥ P 2 F (θ m ; X (n) ) -F (θ ⋆ ; X (n) ) n ≤ 1 2 rad m-1 θ ⋆ ∈ Θ m-1 and G 1 .To show this lets instantiate Lemma 2.6 with θ 0 = θ ⋆ and γ = 3/4 to obtain that for everyθ ∈ R d , ∥θ ⋆ -θ∥ ≤ 2 F (θ; X (n) ) -F (θ ⋆ ; X (n) ) n + 3∆ γn (θ ⋆ ).Notice that conditioned on G 1 , we have 3∆ γn (θ ⋆ ) ≤ 12 ∆. This shows that2(F (θm;X (n) )-F (θ ⋆ ;X (n) )) n ≤ 1 2 rad m-1 implies that ∥θ ⋆ -θ m ∥ ≤ rad m conditioned on G 1by the definition of rad m in Line 12. In the next step, we invoke Lemma A.1. Conditioned on θ ⋆ ∈ Θ m-1 and G 1 , with probability at least 1 -β 2kwu , we haveF (θ m ; X (n) ) -F (θ ⋆ ; X (n) ) ≤ 2rad m-1 • 16 √ 2dk wu n √ ρ log(4k wu /β) + √ 2 √ T wu .Notice k wu ≤ 1 log(2) log(R/r) a.s. By setting T wu = 128 and the bound on the sample size, we haveF (θ m ; X (n) ) -F (θ ⋆ ; X (n) ) ≤ radm-1 2. Also, notice that the randomness in DPGD is independent of history. Therefore,EQUATIONTherefore, combining Equations ( 23) and (24), we obtainP θ ⋆ ∈ Θ m G 1 ≥ 1 - β 2k wu m ,as was to be shown. From Theorem 2.4, given n ≥ Ω 1 √ ρ log((⌈log(R/r)⌉ + 1)/β) , we haveP(G 1 ) ≥ 1 -β. Therefore, P(θ ⋆ ∈ Θ loc and G 1 ) = P θ ⋆ ∈ Θ loc G 1 P(G 1 ) ≥ 1 - β 2k wu kwu • (1 -β) ≥ (1 -2β). (25)This proves the first claim.Regarding the second claim, define the following eventG 2 = ∆ 0.75n (θ ⋆ ) 1 4 ≤ ∆ ≤ 4∆ 0.8n (θ ⋆ ) .Notice that in the proof of P(θ ⋆ ∈ Θ loc ) we only used the fact that with a high probability∆ γn (θ ⋆ ) 1 4 ≤ ∆. Since G 2 ⊆ G 1 , we can write P(θ ⋆ ∈ Θ loc and G 2 ) = P θ ⋆ ∈ Θ loc G 2 P(G 2 ) ≥ (1 - β 2k wu ) kwu • (1 -5β/4) ≥ 1 -2β,where the last step follows from Part 3 of Theorem 2.4 which states that P(G 2 ) ≥ 1 -5β/4.Proof of Theorem 3.1. For the privacy proof, notice that Algorithm 3 uses the training set in Line 2 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 ρ-zCDP.Next, we prove the utility properties. Define the following eventG 1 = θ ⋆ ∈ Θ loc and ∆ 0.75n (θ ⋆ ) ≤ 4 ∆ and ∆ ≤ 4∆ 0.8n (θ ⋆ ) or ∆ = r .Also, by the non-negativity of ∥•∥ 2 , we haveF (θ ⋆ ; X (n) ) = n i=1 ∥θ ⋆ -x i ∥ ≥ 0.2n∆ 0.8n (θ ⋆ ).Using this inequality, for every θ, we can writeEQUATIONUnder the event that θ ⋆ ∈ Θ 0 , we can invoke Lemma A.1 to writeP F θ; X (n) -F θ ⋆ ; X (n) ≤ O √ d √ ρ log(1/β) • ∆ G 1 ≥ 1 -β/2,where it follows because the internal randomness of DPGD is independent of the randomness in Localization step.By the definition of event G 1 , either ∆ = r or ∆ ≤ 4∆ 0.8n (θ ⋆ ). Note that if ∆ ≤ 4∆ 0.8n (θ ⋆ ), we can use Equation (26) to provide a multiplicative guarantee. Therefore, conditioned on the event G 1 , we haveEQUATIONThe first statement then follows because, from Theorem 2.7, we have P(G 1 ) ≥ 1 -β.For the second statement, under the condition that max i∈[n] |X (n) ∩ B d (x i , r)| < 3n/4, we can define the following high probability event:G 2 = θ ⋆ ∈ Θ loc and ∆ 0.75n (θ ⋆ ) ≤ 4 ∆ and ∆ ≤ 4∆ 0.8n (θ ⋆ ) .The argument then proceeds in the same way as the argument for the first claim.Proof of Lemma 3.2. We can write π(•; X (n) ) asEQUATIONIt follows because F (θ ⋆ ; X (n) ) is a constant independent of i. 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 (θ i ;X (n) )-F (θ ⋆ ; X (n) ) for every i ∈ [k].Note that θ ⋆ is a data dependent quantity. Let X(n) be a dataset that differ in one sample from X (n) . Also, let θ ⊛ ∈ GM( X(n) ) and assume, without loss of generality, that X(n) = (x 1 , . . . , x ′ n ) and X (n) = (x 1 , . . . , x n ). For a fixed θ ∈ {θ 1 , . . . , θ k }, we can writeEQUATIONHere, the last two steps follow from the triangle inequality. Note that θ ⊛ is the geometric median of Xn . Therefore by the first-order optimally condition, we haveEQUATIONUsing the first-order convexity condition applied to the function h(θ) = ∥θ -x∥ for a fixed x, we can writeEQUATIONwhere the second step follows from Equation (30) and the last step follows because ∥∇(∥θ ⊛ -x n+1 ∥)∥ ≤ 1. Therefore, using Equation (29) and Equation (31), we haveF (θ; X (n) ) -F (θ ⋆ ; X (n) ) -F (θ; X(n) ) -F (θ ⊛ ; X(n) ) ≤ 2∥θ -θ ⋆ ∥ + 2 θ ⋆ -θ ⊛ .In the next step of the proof, we invoke Lemma C.4 to upperbound the sensitivity as follows2∥θ -θ ⋆ ∥ + 2 θ ⋆ -θ ⊛ ≤ 2diam + 3∆ 3n/4 (θ ⋆ ) ≤ ∆,where the last step follows because ∥θ -θ ⋆ ∥ ≤ diam by the assumption. Notice that the sensitivity analysis in the reverse direction is also the same. Therefore, the second claim follows from the standard analysis of the privacy of the exponential mechanism.Proof of Theorem 3.3. The privacy proof of Algorithm 4 is relatively non-standard. Let A 1 X (n) = ∆, {θ i } i∈{0,...,kft-1} . Also, let A 2 X (n) ; ∆, {θ i } i∈{0,...,kft-1} = t. In particular, A 1 X (n) can be viewed as the first part of Algorithm 4 before Line 10. Also, A 2 (•; •) denotes the exponential mechanism in 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 1 (•) satisfies (ε/2, δ/2)-DP.Define the following eventG = {θ ⋆ ∈ Θ 0 and ∆ 0.75n (θ ⋆ ) ≤ 4 ∆}.Let µ be a measure on M 1 (R × (R d ) kft ) that satisfies the following: for every dataset X (n) , P A 1 X (n) ∈ • ≪ µ(•). Let P 1 denote the density. Since A 1 satisfies approximate-DP, we assume for every z ∈ R × (R d ) kft , we have P 1 (z;X (n) ) ≤ exp(ε/2)P 1 (z; X(n) ) + δ/2.To prove the requirement of privacy, let S ⊆ R × (R d ) kft × {0, . . . , k ft -1}. Also, let X(n) be dataset of size n that differs in one sample from X (n) . Then, we can writeP A1(X (n) ),A2(•;X (n) ) ∆, {θ i } i∈{0,...,kft-1} , t ∈ S = t 1[S]P 1 ∆, {θ i } i∈{0,...,kft-1} |X (n) • π t| ∆, {θ i } i∈{0,...,kft-1} , X (n) dµ = t 1[S]P 1 ∆, {θ i } i∈{0,...,kft-1} |X (n) • π t| ∆, {θ i } i∈{0,...,kft-1} , X (n) 1 ( ∆, θ 0 ) ∈ G dµ + t 1[S]P 1 ∆, {θ i } i∈{0,...,kft-1} |X (n) • π t| ∆, {θ i } i∈{0,...,kft-1} , X (n) 1 ( ∆, θ 0 ) ∈ G c dµ = t 1[S]P 1 ∆, {θ i } i∈{0,...,kft-1} |X (n) • π t| ∆, {θ i } i∈{0,...,kft-1} , X (n) 1 ( ∆, θ 0 ) ∈ G dµ + P(G c ).Notice that under the event that ( Θ, θ 0 ) ∈ G, we can invoke Lemma 3.2 to reason about the privacy properties of A 2 . Under the event G, we can see that 3∆ 3n/4 (θ ⋆ ) + 2diam(Θ 0 ) ≤ 112 ∆. Therefore, by Lemma 3.2, we haveπ t| ∆, {θ i } i∈{0,...,kft-1} , X (n) ≤ exp(ε/2) • π t| ∆, {θ i } i∈{0,...,kft-1} , X(n) .Moreover, by Theorem 2.7, we have P(G c ) ≤ δ/2. Therefore,t 1[S]P 1 ∆, {θ i } i∈{0,...,kft-1} |X (n) • π t| ∆, {θ i } i∈{0,...,kft-1} , X (n) dµ ≤ exp(ε/2) t 1[S]P 1 ∆, {θ i } i∈{0,...,kft-1} |X (n) • π t| ∆, {θ i } i∈{0,...,kft-1} , X(n) dµ + δ/2.Then, we use the fact that A 1 X (n) satisfies (ε/2, δ/2):exp(ε/2) t 1[S]P 1 ∆, {θ i } i∈{0,...,kft-1} |X (n) • π t| ∆, {θ i } i∈{0,...,kft-1} , X(n) dµ + δ/2 ≤ exp(ε) t 1[S]P 1 ∆, {θ i } i∈{0,...,kft-1} | X(n) • π t| ∆, {θ i } i∈{0,...,kft-1s} , X(n) dµ + δ.It concludes the proof.Proof of Theorem 3.4. Define the following eventEQUATIONBy Theorem 2.7, and the assumption on the minimum number of samples, we have P(G) ≥ 1 -β. ≤ P ∃t ∈ {0, . . . , k ft -1} : ⟨ξ dir,t , θ ⋆ -θ t ⟩ > 50 ∆ • 3k ft ρ log(10k ft /β) G 1 + β,where the last step follows because P(G c 1 ) ≤ β. Conditioned on G 1 , for all t ∈ {0, . . . , k ft-1 }, we have ∥θ t -θ ⋆ ∥ ≤ 50 ∆ since θ ⋆ ∈ Θ 0 , θ t ∈ Θ 0 , and the diameter of Θ 0 is 50 ∆. Also, notice that ξ dir,t ⊥ ⊥ (θ t , Θ 0 ). Using these observations, conditioned on the event G 1 , using the standard tail bound on Gaussian random variable (as outlined in Lemma C.1), we can writeP ∃t ∈ {0, . . . , k ft -1} : ⟨ξ dir,t , θ ⋆ -θ t ⟩ > 50 ∆ • 3k ft ρ log(10k ft /β) G 1 ≤ β/5.Therefore, we concludeEQUATIONTo prove the claim regarding the suboptimality gap, we consider two cases:1. There exists t ∈ {0, . . . , k ft -1} such that θ ⋆ ∈ Θ t and θ ⋆ / ∈ Θ t+1 , 2. θ ⋆ ∈ Θ kft .Note that these two events are mutually exclusive and their union covers all the space. In what follows, we show that in both cases there exists t ∈ {0, . . . , k ft -1} such that F (θ t ; X (n) ) has a small excess loss.For the first case, suppose t be such that θ ⋆ ∈ Θ t and θ ⋆ / ∈ Θ t+1 . Therefore, we can writeEQUATIONNotice that using the first-order convexity condition, we have F (θ t ; X (n) ) -F (θ ⋆ ; X (n) ) ≤ ∇F (θ t ; X (n) ), θ t -θ ⋆ . Therefore, by Equation (35), we haveEQUATIONUnder the events G 1 and G n,2 , defined in Equations ( 32) and (34), we haveEQUATIONFor the second case, i.e., θ ⋆ ∈ Θ kft , we have the following geometric fact [Nes98] : there exists t ∈ {0, . . . , k ft -1} such that the distance of θ ⋆ and the separating hyperplane at time t satisfiesEQUATION)Here ν is a constant such that ν d ≥ exp(-τ k ft )(25 ∆) d . The values of ν and k ft will be determined later. Using the first order convexity, we can writeF (θ ⋆ ; X (n) ) -F (θ t ; X (n) ) ≥ ∇F (θ t ; X (n) ) + ξ dir,t ∇F (θ t ; X (n) ) + ξ dir,t ∇F (θ t ; X (n) ) + ξ dir,t , θ ⋆ -θ t -⟨ξ dir,t , θ ⋆ -θ t ⟩ ≥ -ν ∇F (θ t ; X (n) ) + ξ dir,t -⟨ξ dir,t , θ ⋆ -θ t ⟩ ≥ -ν 2 ∇F (θ t ; X (n) ) + 2∥ξ dir,t ∥ -⟨ξ dir,t , θ ⋆ -θ t ⟩≥ -ν(2n + 2∥ξ dir,t ∥) -⟨ξ dir,t , θ ⋆ -θ t ⟩, where the second step follows from the well-known inequality ∥a + b∥ ≤ 2∥a∥ + 2∥b∥ for every a, b ∈ R d . Then, the last step follows because for every θ ∈ R d , ∇F (θ; X (n) ≤ n. Therefore, under the events G 1 , G n,1 , and G n,2 , defined in Equations ( 32) to (34), we have the following bound on the suboptimality gapF (θ t ; X (n) ) -F (θ ⋆ ; X (n) ) ≤ ν(2n + 2∥ξ dir,t ∥) + ⟨ξ dir,t , θ ⋆ -θ t ⟩ ≤ ν(2n + 2∥ξ dir,t ∥) + O ∆ k ft ρ log(k ft /β) ≤ ν • O   n + dk ft ρ 1 + log(k ft /β) d   + O ∆ k ft ρ log(k ft /β) .(39) Recall that ν satisfies ν d ≥ exp(-τ k ft )(25 ∆) d . It can be easily seen that by settingk ft = Θ d τ log n √ ρ √ d + √ d ,under the events G 1 , G n,1 , and G n,2 , we can further upperbound Equation (39) as followsEQUATIONTherefore, from Equations (37) and (40), under the event G 1 ∩ G n,1 ∩ G n,2 , for both cases we showed that there exists t such thatEQUATIONBy the non-negativity of ∥•∥ 2 , we haveEQUATIONTherefore, we conclude that for both cases there exists t such thatEQUATIONwhere κ ≜n √ ρ √ d + √ d.Let us define OPT ≜ min t∈{0,...,kft-1} F (θ t ; X (n) ) -F (θ ⋆ ; X (n) ) . 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 is close to OPT. Using the properties of the exponential mechanism in Line 10 as outlied in Lemma 3.2, we have with probability at least 1 -β/3 over the randomness of the exponential mechanismEQUATIONNotice that under the event G 1 and using Equation (42), we have 448 ∆ ε log(3k ft /β) ≤ F (θ ⋆ ; X (n) ) nε • O(log(k ft /β)) or 448 ∆ ε log(3k ft /β) ≤ r ε O(log(k ft /β)) (45) Moreover, under the event G 1 ∩ G n,1 ∩ G n,G 2 = θ ⋆ ∈ Θ loc and ∆ 0.75n (θ ⋆ ) ≤ 4 ∆ and ∆ ≤ 4∆ 0.8n (θ ⋆ ) .The argument then proceeds in the same way as the argument for the first claim.Proof of Lemma 4.2.For i ∈ [n -k], we can write ∥θ k -x i ∥ ≥ ∥θ k -θ 0 ∥ -∥θ 0 -x i ∥ = ∥θ k -θ 0 ∥ -2∥θ 0 -x i ∥ + ∥θ 0 -x i ∥. Also for every j ∈ [k], we have ∥θ k -y j ∥ ≥ ∥θ 0 -y j ∥ -∥θ 0 -θ k ∥.n-k i=1 ∥θ k -x i ∥ + k j=1 ∥θ k -y j ∥ ≥ (n -2k)∥θ 0 -θ k ∥ -2 n-k i=1 ∥θ 0 -x i ∥ + n-k i=1 ∥θ 0 -x i ∥ + k j=1 ∥θ 0 -y j ∥ (⇔) n-k i=1 ∥θ k -x i ∥ + k j=1 ∥θ k -y j ∥ -   n-k i=1 ∥θ 0 -x i ∥ + k j=1 ∥θ 0 -y j ∥   ≥ (n -2k)∥θ 0 -θ k ∥ -2 n-k i=1 ∥θ 0 -x i ∥ Since n-k i=1 ∥θ k -x i ∥ + k j=1 ∥θ k -y j ∥ - n-k i=1 ∥θ 0 -x i ∥ + k j=1 ∥θ 0 -y j ∥ ≤ 0 by the assumption that θ k = GM(x 1 , . . . , x n-k , y 1 , . . . , y k ), we obtain (n -2k)∥θ 0 -θ k ∥ -2 n-k i=1 ∥θ 0 -x i ∥ ≤ 0 ⇔ ∥θ 0 -θ k ∥ ≤ 2 n -2k • n-k i=1 ∥θ 0 -x i ∥ ⇒ ∥θ 0 -θ k ∥ ≤ 2 n -2k • n-k i=1 ∥θ 0 -x i ∥ + n i=n-k+1 ∥θ 0 -x i ∥ ⇔ ∥θ 0 -θ k ∥ ≤ 2 n -2k • F (θ 0 ; (x 1 , . . . , x n )).Proof of Theorem 4.1. We claim that for every neighbouring datasets X ∈ (B d (R)) n and X ′ ∈ (B d (R)) n and for every y ∈ B d (R), we have |len r (X, y) -len r (X ′ , y)| ≤ 1.This follows from the fact that for every X, we have d H (X, X) ≤ d H (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 k ∈ N be a constant that determined later. Define the following two sets:A 1 = {y ∈ B d (R) : len r (X, y) ≥ k} A 2 = {y ∈ B d (R) : len r (X, y) = 0}Then,EQUATION)We can use the following simple facts:y∈A1 dy ≤ y∈B d (R) dy = V 1 R d where V 1 is the volume ofthe ball of radius one in R d . For A 2 notice that, for all y ∈ B d (GM(X), r), we have len r (X, y) = 0. Thus, y∈A2 dy ≥ V 1 r d . Putting these two pieces together,EQUATIONwhere the last step follows from the fact that P θ∼π ( θ ∈ A 2 ) ≤ 1. Therefore, we obtain that for every β ∈ (0, 1) with probability at least 1 -β we haveEQUATIONwhere θ ∼ π.Under the above event, let θ ∈ B d (R) be such that len r (X, θ) ≤ k ⋆ . This is equivalent to the following: there exists z ∈ B d ( θ, r) and X ∈ (R d ) n such that z = GM( X) and d H (X, X) ≤ k ⋆ . Using this observation, we can writeEQUATIONSuboptimality Gap: Let θ ⋆ ∈ GM(X), thenF ( θ; X) -F (θ ⋆ ; X) = n i=1 θ -x i -∥θ ⋆ -x i ∥ ≤ n i=1 (∥z -x i ∥ + r -∥θ ⋆ -x i ∥) = nr + n i=1 GM( X) -x i -∥θ ⋆ -x i ∥ .Define I ⊆ [n] be the indices of the points that X and X differs. We know that |I| ≤ k ⋆ . Then, we can writeEQUATIONBy triangle inequality, we can writeEQUATIONFor i ∈ I, let ( X) i = x ′ i where ( X) i denote the i-th data point in X. Since GM( X) is a geometric median of X, by the first-order optimality condition∇ θ F (GM( X); X) = 0 ⇔ i∈[n]/I ∇ θ GM( X) -x i = - i∈I ∇ θ GM( X) -x ′ i . (52)To control A 2 , notice that ∥θ -x i ∥ is a convex function in θ for every x i . By the first-order convexity condition, for every θ 1 and θ 2 , we have ∥θEQUATIONThen, by Equation (52),A 2 = i∈[n]/I ∇ GM( X) -x i , GM( X) -θ ⋆ = - i∈I ∇ θ GM( X) -x ′ i , GM( X) -θ ⋆ .Finally notice that by Equation (3), for everyEQUATION)By Equations ( 51) and (54), we obtainF ( θ; X) -F (θ ⋆ ; X) ≤ nr + 2k ⋆ GM( X) -θ ⋆ .Then, we invoke Lemma 4.2 which states that GM( X) -GM(X) ≤ 2 n -2k ⋆ • F (GM(X); X). Putting all the pieces together,EQUATIONas was to be shown. Distance to θ ⋆ : From Equation (49), we know that θ -GM(X) ≤ GM( X) -GM(X) + r where X is a dataset of size n such that d H (X, X) ≤ 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 (n) , recall that θ ⋆ = GM X (n) . Also, recall the definition of∆ γn (θ ⋆ ) from Definition 1.1. Let θ ∈ R d be such that ∥θ -θ ⋆ ∥ > ∆ γn (θ ⋆ ). Define m = | X ∩ B d (θ ⋆ , ∆ γn (θ ⋆ ))|.By the variational representation of ∥•∥, we can writeEQUATIONwhere the last step follows from Cauchy-Schwarz inequality. Then, we claim that for every x ∈ X ∩ B d (θ ⋆ , ∆ γn (θ ⋆ )), we haveEQUATIONTo gain the intuition behind it see Figure 1 . Therefore, from Equation (56),∇F (θ; X) ≥ m 1 - ∆ γn (θ ⋆ ) ∥θ -θ ⋆ ∥ 2 -(n -m).We are interested on characterizing the condition under which ∇F (θ; X) > 0. A sufficient condition is that given n < 2mm 1 - ∆ γn (θ ⋆ ) ∥θ -θ ⋆ ∥ 2 -(n -m) > 0 (⇔) ∆ γn (θ ⋆ ) 1 2 m n -m n 2 < ∥θ -θ ⋆ ∥.This shows that the distance of GM( X) and θ ⋆ has to satisfyGM( X) -θ ⋆ ≤ ∆ γn (θ ⋆ ) 2 m n -m n 2 . The function h(x) = 1 √ 2x-x 2 is decreasing in the range of x ∈ (0, 1]. Also, notice that m = | X ∩ B d (θ ⋆ , ∆ γn (θ ⋆ ))| ≥ γn -k ⋆ . Therefore, GM( X) -θ ⋆ ≤ ∆ γn (θ ⋆ ) 2 γ -k ⋆ n -γ -k ⋆ n 2 ,as was to be shown.Proof of Theorem 5.1. The proof is based on the reduction provided in Lemma G.1 and the lowerbound on the sample complexity of the mean estimation of Gaussian distribution with known covariance matrix in [KLSU19, Thm. 6.5].Lemma G.1. Let ε ≤ 49 × 10 -5 , α ≤ 49 × 10 -5 , δ ≤ 10 -4 , and d ≥ 22500 be constants. Let A n be an arbitrary (ε, δ)-DP algorithm such that for every dataset X (n) , its output satisfiesEQUATIONF (θ; X (n) ).Let µ ∈ B ∞ d (1) and let X (n) = (X 1 , . . . , X n ) ∼ N (µ, I d ) ⊗n . Let θ ∼ A n (X (n) ). Then, with probability at least 2/3 over X (n) and the internal randomness of A n , we haveθ -µ ≤ 0.2 √ d.Proof. The proof consists of several steps:Step 1: Bound on the Empirical Error. Let A n be an arbitrary (ε, δ)-DP algorithm such that for every dataset X (n) , its output satisfiesF ( θ; X (n) ) ≤ (1 + α) min θ∈B ∞ d (R)F (θ; X (n) ).Let µ ∈ B ∞ d (R) and X (n) = (X 1 , . . . , X n ) ∼ N (µ, I d ) ⊗n . The utility guarantee of the algorithm implies that E F ( θ;X (n) ) ≤ (1 + α)E min θ∈B ∞ d (R) F (θ; X (n) )≤ (1 + α)E F (µ; X (n) ) .To further upperbound the last step, we can use Jensen's inequality to write1 n • E F (µ; X (n) ) = E[∥X 1 -µ∥] ≤ E ∥X 1 -µ∥ 2 = √ dTherefore, in-expectation over X (n) ∼ N (µ, I d ) ⊗n and the internal randomness of A n , we haveEQUATIONStep 2: Relating Empirical Error to Population Error. Let (X 0 , X 1 , . . . , X n ) ∼ N (µ, I d ) ⊗(n+1) . With an abuse of notation, let θ = A n ((X 1 , . . . , X n )), and, for every i ∈ [n], let θ (i) = A n ((X 1 , . . . , X i-1 , X 0 , X i+1 , . . . , X n )). Let T be a constant that will be determined later. We can writeEQUATION)Consider the first term in Equation (59). Since A n satisfies (ε, δ)-DP, P θ (i) -X i ≥ t = E P θ (i) -X i ≥ t (X 0 , . . . , X n ) ≤ E exp(ε)P ∥θ -X i ∥ ≥ t (X 0 , . . . , X n ) + δ = exp(ε) • P(∥θ -X i ∥ ≥ t) + δ.(60)Therefore, the first term can be upperbounded asT t=0 P θ (i) -X i ≥ t dt ≤ exp(ε) • T t=0 P(∥θ -X i ∥ ≥ t)dt + T δ ≤ exp(ε) • E[∥θ -X i ∥] + T δ.In the next step, we upperbound the the second term in Equation (59). Notice that (θ (i) , X i ) :EQUATIONwhere the first step follows from the triangle inequality and the last step follows because µ and θ (i) are in B ∞ d (R). Using this, we can writeEQUATIONwhere the last step follows from the change of variable u = t -(2R + 1) √ d. In the next step, we use the concentration bounds for the norm of multivariate Guassian random variable. Using Lemma C.2, we can write (64)EQUATIONIn the last step, we claim that E[∥θ -X 0 ∥] = E θ (i) -X i for every i ∈ [n]. It is because θ (i) d = θ, X i d = X 0 , and θ (i) ⊥ ⊥ X i . Ergo, combining and summing over i ∈ [n], we obtainE[∥θ -X 0 ∥] ≤ exp(ε) 1 n n i=1 E[∥θ -X i ∥] + (4R + 2) √ dδ + 1 (4R + 2) √ d exp -2(2R + 1) 2 dThis bound implies thatE[∥θ -X 0 ∥] -E[∥µ -X 0 ∥] ≤ exp(ε) 1 n n i=1 (E[∥θ -X i ∥] -E[∥µ -X 0 ∥]) + (exp(ε) -1)E[∥µ -X 0 ∥] + (4R + 2) √ dδ + 1 (4R + 2) √ d exp -2(2R + 1) 2 d .This equation can be rephrased as followsEQUATIONwhere β = exp(ε)α + (exp(ε) -1) + (4R + 2)δ + 1 (4R + 2)d exp -2(2R + 1) 2 d .(66)Step 3: Relating Population Error to Distance In Step 2, we showed that in-expectation over (X 0 , . . . , X n ) ∼ N (µ, I d ) ⊗(n+1) and θ ∼ A n (X (n) ) where X (n) = (X 1 , . . . , X n ), we have Since µ is the minimizer of h(θ), for every θ ∈ R d we have that h(θ) ≥ h(µ). Therefore, h( θ) -h(µ) is a non-negative random variable. We can invoke Markov's inequality to writeEQUATIONEQUATION)In the next step, we provide a deterministic argument: For every θ ∈ R d such that h(θ) -h(µ) ≤ 3β √ d, we provide an upperbound on ∥θ -µ∥. By subtracting µ, we can write EQUATIONThe value of γ will be determined later. For instance, by setting ε ≤ 49 × 10 -5 , α ≤ 49 × 10 -5 , δ ≤ 2 3 × 10 -4 and d ≥ 2, we obtain β ≤ 0.1. Finally, we need to set d such that Equation (73) holds. We can see that d ≥ 7050 satisfies this condition.Our goal in the experiments is to evaluate the impact of increasing the radius of the initial feasible set, i.e. R, on the performance of our proposed algorithm and compare it with DPGD. Also, we 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 µ ∈ R d be a uniformly random vector within S d-1 (50). We then sample 0.9n of the data points from N (µ, (0.01) 2 • I d ). The remaining 0.1n of the points are sampled uniformly at random from B d (100).Hyperparameters. We set the discretization parameter to r = 0.05 in Algorithm 2 and failure probability to 5%. Additionally, we repeat each algorithm 10 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.1, and in particular, we choose T such that  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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$?

Numerical setting is relatively simple but I don't really mind that since the greatest merit of this paper is in the theory.
questions: 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.

For others, see the weakness part.
limitations: limitations: Yes.
paper_summary: paper_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. 

The 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. 

The 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.

In 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).
strength_weakness: strength_weakness: 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.  

The writing can be improved. There are many places where clarification and definition will be helpful to readers. Some examples are mentioned below.

On DP-SGD, may you explain what is the definition of "excess error" (line 23)? Is this the same as excess risk (line 45)?

Equation (2), what is A_n? the DP -SGD algorithm? It is never defined.

Line 63, effective diameter of the data points -- it will be good to explain what effective diameter means.

Table 1, define lower case r? Again r does not appear until much later in the paper.
questions: questions: See above.
limitations: limitations: N/A
paper_summary: paper_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. 

The 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. 

This 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.
strength_weakness: strength_weakness: -
questions: questions: -
limitations: limitations: Yes.
paper_summary: paper_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. 

The 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. 

The 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.

This paper also provides the lower bound to demonstrate the optimality of the sample complexity of their algorithm.
strength_weakness: strength_weakness: 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.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_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.

Additionally, 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.
strength_weakness: strength_weakness: 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.
questions: 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. 

I am also wondering what part is the bottleneck if someone wants to improve this to a linear run-time.
limitations: limitations: N/A

Comments: title: Thank you for your response
comment: Thank you for your reply! We will incorporate all the suggested revisions into the final version of the paper.
Thank you for the reply! We will update the paper based on your suggestions.
Thank you for your helpful feedback! We will include a discussion on the robust notions of radius and update the introduction based on your suggestions.
Thank you very much for your reply. We will revise our paper according to the constructive comments in your reviews.
Thanks for the response. Please include these revision items in the paper.
Thank you for your response! My questions have been addressed.
Thank you for your response! Nice work!
I've read the authors' response and my questions have been addressed adequately. I will keep my current score at 7. Thank you!