Private Geometric Median

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.

W1: dependency between parameters in Thm 3.1 and Thm 3.4.

Note 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. Due 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.

Q1: On comparison of LocDPGD and LocDP.

Both 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: Given $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.

Q2: Bottlenecks for improving runtime.

There are two bottlenecks in our algorithms:

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

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

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

[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).

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

We thank the reviewer for their positive and thorough review! We respond to the questions below.

W1: Presentation of the ideas behind the algorithms

Thanks 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:

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

W2: Comparison with prior work

Since 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

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

We thank the reviewer for all the positive comments!

We would like to thank the reviewer for their thorough review and valuable feedback. Below, we address each of the points raised.

Q1: Robust Notion of Radius and Our Contribution

We 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:

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

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

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

[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).

Q2: Excess Error and Excess Risk

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

Q3: $\mathcal{A}_n$ in Equation 2

Thank you for pointing this out. As you mentioned it is DP-SGD. We fixed this in the paper.

Q4: Effective Diameter

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

Q5: $r$ in Table 1

$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].

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

We thank the reviewer for their positive and thorough review. We respond to the main points below.

On Our Pure-DP Algorithm

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

W1: Oracle access to exact GM

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

W2: Computing $\text{len}_r$ function

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

[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).

[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).

W3: Benefit of r>0

Introducing $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.

Q1: Privacy definitions

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