A Differentially Private Linear-Time fPTAS for the Minimum Enclosing Ball Problem
Authors: Bar Mahpud
Or Sheffet
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential Privacy
Minimum Enclosing Ball
fPTAS

Abstract: The Minimum Enclosing Ball (MEB) problem is one of the most fundamental problems in clustering, with applications in operations research, statistic and computational geometry. In this works, we give the first differentially private (DP) fPTAS for the Minimum Enclosing Ball problem, improving both on the runtime and the utility bound of the best known DP-PTAS for the problem, of Ghazi et al (2020). Given $n$ points in $\mathbb{R}^d$ that are covered by the ball $B(\theta_{opt},r_{opt})$, our simple iterative DP-algorithm returns a ball $B(\theta,r)$ where $r\leq (1+\gamma)r_{opt}$ and which leaves at most $\tilde O(\frac{\sqrt d}{\gamma\epsilon})$ points uncovered in $\tilde O(n/\gamma^2)$-time. We also give a local-model version of our algorithm, that leaves at most  $\tilde O(\frac{\sqrt {nd}}{\gamma\epsilon})$ points uncovered, improving on the $n^{0.67}$-bound of Nissim and Stemmer (2018) (at the expense of other parameters). In addition, we test our algorithm empirically and discuss future open problems.

A Differentially Private Linear-Time fPTAS for the Minimum Enclosing Ball Problem
Bar Mahpud
Or Sheffet
Faculty of Engineering Bar-Ilan University, Israel {mahpudb, or (biffet))biu.acc.e
Abstract
The Minimum Enclosing Ball (MEB) problem is one of the most fundamental problems in clustering, with applications in operations research, statistics and computational geometry. In this works, we give the first linear time differentially private (DP) IPTAS for the Minimum Enclosing Ball problem, improving both on the runtime and the utility bound of the best known DP-PTAS for the problem, of Ghazi et al [21]. Given n points in Rd that are covered by the ball B(Oopt Tope), our simple iterative al-algorithm returns ball (00,r) where r S (1 T)
and which leaves at most Ó vdd
points uncovered in ((*/-2)-tine We also give a 76
local-model version of our algorithm, that leaves at most Ö (/nd) points uncovered,
improving on the n 0.67 -boun of Nissim and Stemmer [31] (at the expense of other parameters). Lastly, we test our algorithm empirically and discuss open problems.
1 Introduction and Related Work
One of the fundamental problems in clustering the Minimum Enclosing Ball (MEB) problem, or the 1 1-Center problem, in which are given a dataset P Rd containing points, and goal is find the smallest possible ball B( Topt) that contains P. The MEB problem has applications in various areas of operations research, machine learning, statistics and computational geometry: gap tolerant classifiers [11], tuning Support Vector Machine parameters [12] and Support Vector Clustering [5, 6). k-center clustering [10], solving the approximate 1-cylinder problem [10], computation of spatial hierarchies (e.g., sphere trees [25]), and others [18]. The MEB problem NP-hard to solve exactly, but it can be solved in linear time in constant dimension [29, 19] and has several Hilly-Polynomial Time Approximation Schemes (IPTAS) [4, 27] that approximate it to any constant (1 + 7) in time O(n/7); as well as additive y approximation in sublinear time [13].
But in situations where the data is sensitive in nature, such as addresses, locations or descriptive feature- vvettoss single individual. Differential privacy [16, 15] (DP) alleviates such a concern as it requires that no single individual has significant effect the output. Alas, the MEB problem is highly sensitive in nature, since there exist datasets where a change to a single datum may affect the MEB significantly.
the risk that approximating the data's 's MEB might leak information about
In contrast, it is evident that for any fixed ball B(0, r) the number of input points that B contains changes by no more than one when changing any single datum. And so, in DP we give bi-criteria approximations of the MEB: ball (00,r) that may leave most few points of P uncovered and whose radius is comparable Topt The work of [32] returns O
'Consider a research hospital in which one first runs some regression on each patient's data, then looks for the spread of all regressors of all patients.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of the MEB while omitting as few as ((4))) points from P, and it was later improved to ((1)- approximation [31]. The work of [21] does give PTAS for the MEB problem. but their (1 + 7)- approximation may leave O(V4/c²") datapoints uncovered and it runs in n11(1/9)-tima where the constant hidden in the big-O notation is huge; it leverages on multiple tools that take exp(dim)- time to construct, such as almost-perfect lattices and list-decodable covers. It should be noted that all of these works actually study the related problem of 1-cluster in which one is given an additional parameter t and seeks to find the smallest MEB of a subset Q C P where [Q 2 t. Lastly (as was first commented in [21]. Section D.2.1.), a natural way to approximate the MEB problem through minimizing the convex hinge-loss L(O, x) = max(0, 0,, ||2 - 01| - r but its utility depends on r (as the utility of DP-ERM scales with the Lipfshitz constant of the loss [3]).²
By far, one of the most prominent uses of the DP-approximations of the MEB problem lies in range estimation, as O aiproxxpxxistsss of the MEB can assist in reducing an a-priori large domain to a ball whose radius is proportional to the diameter of P. This helps in reducing the L--sensitivity of problems such as the mean and other distance related queries (e.g. PCA). So for example, if we have á2 v points in a ball of radius oft then Dp-approximation of the data's mean using the Gaussian mechanism (see Section 2) returns point of distance < Toopt to the true mean (a technique that is often applied in Subsample-and-Aggret
7c
framework [30]). This averaging also gives an efficient (2 + apprroxximtaooonn of the MEB, But it is still unknown whether there exists a DP c-approximation of the MEB for c < 2 whose runtime is below, say, n 1000
Our Contribution and Organization. In this work, we give the first DP-IPTAS for the MEB problem. Our algorithm is very simple and so is its analysis. As imput, we assume the algorithm run after the algorithms of [31] were already run, and as "starting point" we have both (a) a real number which is 4-approximation of Topt. and (b) a 10-approximation of the MEB itself, namely a ball B such that P C B,* which is centered at point 6, satisfying ||0, - oope || S 10ropt. now our goal to refine these parameters to a (1 + approoximato of the MEB. In fact, we can assume that we have a (1 + 7) apprroximatoo of the value of Topt: we simply iterate over all powers: 4, 2 (1 + 7), (1 + 7)²
; ".......,,,,,,, To where for each guess of r we apply a privacy preserving procedure returning either a point satisfying P c B(0,r) r) or I. In our algorithm we simply use a binary-search over these O(2/7) possible values, in order to save on the privacy-budget.
Now, given G and some radius-guess r, our goal is to shift Gu towards papt- So, starting from 00 = 0o. we repeat this simple iterative procedure: we take the mean μs of the points uncovered by the current B(0", r) and update gz+1 + 8 3" (μ ('). We argue that, if 2 Tops then after T = O foy-2logt log((\)))-iterattoon we get 8T such that 1|0T - Oopell I ?Topt and therefore have that P C B(0", (1 + 7r)). The reason can be easily seen from Figure 1 1- any point æ E P which is uncovered by the current ((0'rr) r) must be closer to Dopt than to 0², and therefore must have a noticeable projection onto the direction Oope - 0². Thus, in a Perceptron-like style, making a -(sz)-size step towards this x must push us significantly in the Popt - 0' direction. We thus prove that if the distance of 0' from Oppt is large, this update step reduces our distance to O Note that our proof shows that in the non-private case it suffices to take any uncovered point order to make this progress, or any convex-combination of the uncovered points.
2
In the private case, rather than using the true mean of the uncovered points in each iteration, we have to use an approximated mean. So we prove that applying our iterative algorithm with a "nice" distribution whose mean has large projection the apt le direction also returns good 6" in expectation, and then amplify the success probability by naïve repetitions. We also give SQ-style algorithm for approximating the MEB under proximity conditions between the true- and the noisy- mean, a result which may be of interest by itself. After discussing preliminaries in Section 2, we present both the standard (non-noisy) version of our algorithm and its noisy variation in Section? 3.
Having established that our algorithm works even with a "nice" distribution whose mean approximates the mean of the uncovered points, all that is left is just set the parameters of a privacy preserving
"See Lemmas 59 & 60 in [21]
"In fact, there's more to this discussion, as we detail at the end of the introduction.
'We can always omit the few input points that may reside outside this ball.
'e comment that replacing these 4 and 10 constants with any other constants merely changes the constants in our analysis in very trrighht-fowwan way.
2

---

algorithm accordingly. To that end we work with the notion of zCDP [8] and apply solely the Gaussian mechanism. To obtain these nice properties, follows that the number of uncovered points must be 1(V0/e where eº is the privacy budget of the / or else we halt. And due to the composition theorem of DP it suffices to set e¹ = O(+/vT). This leads to a win-win situation: either we find in some iteration a ball that leaves no more than O(v5/7e) points uncovered, or we complete all iterations and obtain ball of radius I (1 + +r)r that covers all of P. The full details of this amalysis appear in Section 4. We then repeat this analysis but in the tocal-model where each user adds Gaussian noise to her own input point. This leads to similar analysis incurring vn-larger bounds, as detailed in Section 5.
While at the topic of local-model DP (LDP) algorithms, it is worth mentioning that the algorithms of [31], which provide us with a good initial "starting point", do have LDP-variant. Yet the LDP variants of these algorithms may leave as many as n n2.67 datapoints uncovered. So in Appendix A we give simple differentially private algorithms (in both the curator- and local-models) that obtain such good 0g and ro. Formally, our LDP-algorithm returns ball B(Oo, ro) s.t. by projecting all points in P onto r( we alter no more than Ö(Vd/c) points and obtain P' C B(0,, ro) where ro S Gropt (P)) Thus, combining our LDP algorithm for finding a good starting point together with the algorithm of Section 5 we get an overall (1 + -ppppooxinntoonnn of the MEB in the local model which may omit / alter as many ) We comment that while this improves on the previously best-known LDP algorithm's 's bound of n2.66,, our algorithm's 's dependency on parameters such as the dimension to the problem of 1-cluster (finding a cluster containing t I many points) and (ii) separates between the required cluster size and the number of omitted points (which much smaller and only logarithmic in d), two aspects that are not covered in our work.
grid-size is worse, and furthermore that the analysis of [31] (i) relates
Lastly, we provide empirical evaluations of our algorithm (which deferred in its entirety to the Supplementary Material, Section E) showing a rather ubiquitous performance across multiple datasets, and discuss open problems in Section 6.
Comparison with the ERM Baseline. Recall that the MEB problem, given a suggested radius r and a convex set θ can be formulated ERM problem using hinge-loss function el (0; max (0, diam( }. Indeed, when diain() >> r then privately solving this ERM problem gives no useful guarantee about the result, but much like our algorithm one can first find some 0g close up to, say, 10r Oppt and set θ as a ball of radius O(r). Since there exists Oopt for which E. ll (0; 0, then private SGD [3, 2] returns 0 for which 1 E. (0; S C vd for some constant C >> 0. This upper-bounds the number of points that contribute "yr to this loss at C and so IP B(0, (1+ (1+))r)] ( However, the caveat is that the SGD algorithm achieves such low loss using O(n2)-SGD iterations.? 7 In contrast our analysis can be viewed as proving that for the equivalent ERM in the square of the norm, ((0xx:)) max ||=-01²-,² [ ). it suffices to make
ey
only 2 non-zero gradient steps to have some 8T s.t. ||07 0ppl ll I yr so that B(OT, (1) covers all of the input. Thus, our result obtained in linear (
2 Preliminaries
Notation. Given a vector e E IRd we denote its I-z-orrm as [|ui], and also use (c. u) to denote the dot-product between two d-dimensional vectors u and v. A (closed) ball ((0,r) is the set of all points B(0,r) = {ar Rd ||2 - A|| S r}. We use Ö(-) / 52(-) to denote big-O / big-St dependency up to poly log factors. We comment that in our work we made no effort to optimize constants.
The Gaussian and 2 Distribbutis Given two parameters P E R and 0²
denote N(,, as the Gaussian distribution whose PDF at a point E IR is (2m02)0.5 exp( (a (m-w)² Standard concentration bounds give that for any x > 1 the probability Pix-Nimo ||x - 14| 2
xo] < 2 exp( - x²/ /2). It is well-known that given two independent random variable X ~ NN of)
'It is known [7] that DP MMBBapproximmatin requires the input points to lie on some prespecified finite grid. 7 Unfortunately, the hinge-loss isn't 't smooth, ruling out the linear SGD of [20].
3

---

and Y (u2,, σ2) their sum is distributed like Gaussian X +Y ~ ([ + p2, of tz). We also denote (v, o Ia) the distribution over d-dimensional vectors where each coordinate is drawn i.i.d. from Ni (() Given X ~ (0, o² it is known that ||x| 22 is distributed like x² di-iistribution; and known concentration bounds on the x. x--distribution give that for any > 1 the probability Prx~N((0.01a)) |||X|* > o + x) =) S exp( -2)
Differential Privacy. Given a domain X, two multi-sets P. P E X are called neighbors if they differ on a single entry. An algorithm (alternatively, mechanism) M is said be (e, 6) -iifferrential private (DP) [16. 15] if for any two neighboring P. P' and any set S of possible outputs we have: Pr[M(P) E S] = E" Pr[M(P') 6
An algorithm said to be p-zero concentrated differentially privacy (zCDP) [8] if for and two neighboring P and p' and any > 1, the a-Réyni divergence between the output distribution of M(P) and of M(P)) is upper bounded by ap, namely
((
= x ) ))
Ya 1, a-1
log
E (2-M(P))
PDF[M(P') =
S ap
is a well-known fact that the composition of two p-zCDP mechanisms 2p-zCDP. is also known
that given function f X - IR whose L2 12-global sensitivity is maxp~P" I S G then the Gaussian mechanism that returns (D) X where X NO, 2p
C² La) p-zCDP. Lastly,
is known that any p-zCDP mechanism is (c, 6)-DP for any 5 < and p / 4p (1/0)). This suggests that given < 1 and 8 < e it suffices to use a p-zCDP mechanis with p S (lm()
The Local-Model of DP: while standard algorithms in DP assume the existence of a trusted curator who has access the raw data, in the local-model of DP no such curator exists. While the formal definition of the local-model involves the notion of protocols (see [35] for a formal definition), for the context of this work it suffices to say each respondent randomized her messages so that altogether they preserve p-zCDP.
3 A Non-Private fPTAS for the MEB Problem
In this section we give our non-private algorithm. We first analyze it assuming no noise namely, in each iteration we use the precise mean of the points that do not reside inside the ball B r). Later, in Section 3.1 we discuss a version of this algorithm in which rather than getting the exact mean, we get a point which is sufficiently close to the mean.
Algorithm 1 Poi--tivate Minimum Enclosing Ball
Input: set of n points P C Rd an approximation parameter 7 (0, 1), an initial radius ro s.t. Topt S ro S 4ropt. and an initial center Oo s.t. |10 Oopell lI S 10r 10r
Set iiin + 0, imax + 111+= (4) 4). and 8 + 6o-
2: while (6min < (mmax) do
3:
dear = Emiu Sanas
2
4:
Teur (1 + (1 3 ro/4
5:
Peur +- MMEB (P, Feur: 0g)
6:
if P C B(Ocut, (1 reur) yeur) then
7:
Set mmax + heur. 8" t- feur and n +- (1 + y
8:
else
9:
Amin +- ieur +1 return B(8", r()),r))
10:
Theorem 3.1. For any P C. IRd, denote [80ppt ((0ppttTTppl Topt) as the MEB of P. Then Algorithm 1 returns ball ((0rr) r) where P C B(0,)) and r < (1 37)
At the core of the proof of Theorem 3.1 lies the following lemma. Lemma 3.2. Applying Algorithm/ with any r 2 Topt and any 0g where ||0p - 0opell S 10r we obtain a 0 where ||0 Ooptll ll S Toopt in at most T' iterations.

---

Algorithm 2 Margin based Minimum Enclosing Ball (MMEB)
Input: a set of n points P _ R an approximation parameter y E (0, 1), candidate radius r, and an initial center &n s.t. ||6u poptl] 10ropt-
1: Set T + + In( 7
100 and 0 Oo-
2: for 0,2 2....
do if (f : ((0 rr) () then return 6f
3:
4:
else
5:
Set n - (x P: E B(6", ((0',r)] and ph
Σ x
n
Update 8- t- 0r - -0 (0 -
6:
7:
return 0²
It is important to note that Lemma 3.2 holds even if in each iteration the update step isn't based on the mean J of the set of uncovered point, but rather any convex combination of the uncovered points. Specifically, even if we use in each iteration single point which is uncovered by B(0*, r), then the algorithm's convergence in T steps can be guaranteed.
Proof of Theorem 3.1. Suppose Lemma 3.2 indeed holds. Then it immediately implies whenever Algorithm 2 is run with r 2 Topt we obtain a point where P C B (fopt, Topt) ) C B(0, (1 + oppe)
Denote = min(i E N: 1 + 7)' 2 ]opt)- is simple to prove inductively that in each iteration of Algorithm I we have that i" 2 mmin Next, call an integer i successful if we obtain for its radius Teur(1) some point 0 where P C B(0, (1 ()rr (i)). Again, it is simple to argue inductively that mmx is always successful. It follows that when the binary search of Algorithm terminates,
mmin = dmax and we have successful i, and so we return ball of radius 1 (1 + 7 (1+ +) <
(1 11++ 7) I (1 + rypr which contains all points P, thus concluding our proof.
7
Thus, all that is left prove Lemma 3.2, Its proof, in turn, requires the following claim.
Claim 3.3. Given a set of n points P C Rdd let B (Oopt: Topt) denote the MEB of P. Let 0 E Idd be an arbitrary point, and let be any real number where r 2 Topt- Then for any x|| it holds that
s.t. 110-
10
0
x 0ept)
(0 (0- x Oopt) s 2
110 @ppel1
Proof. Let r E P be a point s.t. & B(O,r). as depicted in Figure 1. Let m be the mid- dle point 0+0apt and let H be the hyper- plane orthogonal through m. Denote H+ as the (open) half- space 7 {a Rdd ||=-0apel| < -|==- Therefore x E H+ which in turn implies that
Topt
0 8opt which passes
Figure I: For a point x uncovered by B(0,r) where Topt, must be that x's projection onto the 00op--line closer to Sept than to O.
1 - Oopell
(x Oopt, 0 Oppt) (m Oope, 0 Oops)
We are now ready prove our main lemma.
Proof of Lemma 3.2. First, we argue that in any iteration t of Algorithm 2 where for E P x é
B(0", r)) # @ holds that ||0t-1 Oopell2 (1 2² ||0 Oppt 1| +z²)2 r That is because by definition
@opel 03 ==(((a- 72 )0e
72 1/ - 1opt
22
2 (0' -opt)) + 22 (ui - 0ope)
|10
2
2
5

---

= -1- - 3/ -100 -Oopell' + +2
22
)(0 Oapt: Mort Oope) + (2)2 1lumo - -Oopel
2
Claim 3.3 gives that (0r Bope: utw )opt)
1
E
(0)
Bope: x sopt) S 2/1 - 9optl 10.00
=
n/w
x$B(6(.r)
s s - 2p 1100 Oopell + 2(
22
2
110 Oope 17+ (2/) I1lkwt - Oops! 112
2
2
Lastly note that the ball B(o ropt) convex and so
(1 (1 -²+ -100 Dopell
(
-1000 Oopell + -- r2
2 4
4
ropt
72 )110* eopel1 + 71 2
$ (1
4 opp
(I)
So now, consider any iteration of Algorithm 2 with r 2 Vopt and where 1 Oopel 2 Mopt and in which we make an update step. Due to Equation (1)
2²
7a + 4
72
7at 110- Opplll
|10+t1 8opt 122 S (1
2 )110- 0apel12
rop I (1
2 )110 Bopell2+ +
4
72
2
)110* - 0opel1 S - 110 Oopell
= (1 4
This suggests that after T = 7s In( 100) 7z
iterations where 1|0t - Oepell 2 Tropt we get that
110T Oppell 11 S se _-- 1100 Dopell 11
72 100r opt = 22
100
as required. Now, should it be the case that in some iteration update step. Again, Equation (1) asserts that
|00 Oopt
Toptt and we make an
22 O110 Dopell? + 24 2 < (1 2
72
2 2
opt + 2dt 4
||0 -oppell 1| s (1
-2 < 72
2
so once ||0- Oopell l| < "yoop then we have that 110T Oopt ll < Toot for all T 2 t.
3.1 The Noisy/SQ-Versionn of the IPTAS for the MEB Problem
Now, we consider a scenario where in each iteration I, rather than using the exact mean ple ExcPLerst.r) we obtain an approximated mean م" = م/ر + A We consider here two scenarios: setting we refer to the random
(P)
(a) where A is zero-mean bounded-variance random noise noise setting; and (b) where A is an arbitrary noise s.t. the constraint that | O(7r) - a setting we refer to as arbitrary noise. The latter isn't used in our algorithm and deferred to Appendix B.
The random noise setting. In this setting, our update step in each iteration is made not using a deterministically chosen uncovered point but rather by draw from a distribution D' whose mean is "as good"' as an uncovered point. This requires us to make two changes to the algorithm: (i) modify the update rate and (ii) repeat the entire algorithm R = (lo)(1/3)) times.
Claim 3.4. Consider an altered version of Algorithm 2 which (1) repeats the algorithm R 4096 In( (2) update-steps and [logy/ (1/3)1 times, (2) each repetition is composed at most = 72
(3) in each iteration where it doesn't it terminate it draws point ~ Dt and makes that update-step: 72
gt-1 0¹ + 2018 2. If it holds that for each iteration we have that D' satisfies the two properties
E [(ppt 0² |00 2 4 1100 0 -ppell
2~ Dc
(ii)
E D:
1 < 51272
(2)
then, provided that Topt. we have that w.p. 2 1 one of the R repetitions of the revised algorithm returns candidate center 0T where P C B(OT. (1 7)r).

---

Proof. To prove Prov the claim it suffices to show that in a single execution of the algorithm we have that Pr[li opt I yr| = Pr[] Opp I12 I ?2r=] 2 1/4. implying that in R repetitions of the algorithm the failure probability decreases to (3/4) f 3. To that end, denote the non-negative random
variables Y = ||0r llp for each iteration f. Note that if we show that E[y"T] I 3 2 then
Markov's s inequality implies that Pr[y 2 2 < 3/4. So our goal is to prove that E E S 7
We can now analyze the conditional expectation and observe that
72
E [[ - - 1=10] = E
0² Oppt +
2
0
2048
E
100 Oopt1 112
2-2
(2,
0' Popt) +
72
1211=11 100
2048
2048
SND1
272
1
Oope 7 512
72
7
10 -Oopell
110
)100
-0 pp 12
2048
20482
4096
8192
Since B[ 041 s (1
2 y
+
then it is easy to see that E|y
S
-²
)² y
1096
1096
8192 2
E6 (1 4096
72 )r $ (1 4096
x/2
(11r)²
3 r2 It follows that iteration T = 4096
In
121-4
7
we have that E|Y"" S _-2² = 7,2,22 as required.
Corollary 3.5. Suppose that in each iteration of the revised algorithm D' is a distribution that satisfies the required two properties of Claim 3.4 w.p. 2 8T- 51-11ogs;>(1/B]1 Then, repeating this algorithm R = [logs/7 (1/3)] many times we have that w.p. 2 1 - B it holds that for at least one repetition have P (B(07, (1 + 7))).
Proof. Using the union bound, it follows that in one of the R T repetition of the revised algorithm the probability that one draw isn't from good D' (that does satisfy these two properties) is at most 1/8. It follows that Pr[y I' 2 >" 2 1/4 1/s 1/8. Repeating this algorithm It reduces the failure
probability (7/s) R <
4 A Differentially Private IPTAS for the MEB Problem
We now turn our attention to the privacy-preserving versions of Algorithms and 2. In this section give their curator-model p-zCDP versions (Algorithms and resp.), whereas in the following section (Section 5) we detail their local-model zCDP versions. Due to space constraints, (i) the proof that Algorithm is p-zCDP, (ii) the the full proofs of the following two statements, and (iii) the application of Algorithm 3 to Subsample- -ndell--nn----gattttt are all deferred to the Supplementary Material, Section C.
Algorithm 3 Differentially Private Minimum Enclosing Ball (DP-MEB)
Input: set of n points P C Rd., an approximation parameter y E (0, 1), an initial radius To s.t. Topt To S. '4ropt, and an initial center 0, s.t. 110 Oopell S 10ropt. opt. error parameter 3 and privacy-parameter p.
1: Remove any x E P which doesn't belong to B(f. 11ro).
2: Set imin +- imax + (1))+x(4)(== +), and H* + Og-
3: Set B t- -loo
(4))
4: while (imin < ?mmax) do
5: ieur = Emmia Samaa
2
6: Teur - (1 + -o/4
7: Oenr +- -DP-MMEB(PPT) B B Feur, 0o)
3.
8:
if (Bour F L) then
9:
Set dmax + iour. Hr + Oeur and p" + (1 + y)ru
else
11:
imin + tcur + return B(8*,r*)
12:
7

---

Algorithm 4 DP-Margin based Minimum Enclosing Ball (DP-MMEB)
Input: a set of n points P S Rd an approximation parameter r E (0, 1), error parameter B (0, 1). privacy parameter
a candidate radius r, and an initial center 0o s.t. |10 Oopt S 10r
1: Set R + [log,,, (1/8)1. 0o + 80, T t 1096
7 In 184
Su = 16 o Poantt
R(T+1)
and
72
R&T (88r))
P
2: repeat
3:
for 1 = 0, 1,1, .
do Sample A count NO, oz )count).
4:
5:
Th + 1 E P: x & B(0 rT] + A count
6:
(n < SSVRT
Vd++ /2 ( //)) then
vp
7:
return Sample Aonm
8:
NO, 2umm Ia).
9:
Set M t Man
Σ
(x- -0- 0¹) + Asum
(0'
10:
Update gr-1 +- Hr +
+2 Bune
2018
Sample A Acoutt _O, o count).
12:
if (IP) B(O", (1 ))r)
Dcuntt S (oo
then return 0 and
halt
until repetitions return _.
14:
Lemma 4.1. W.p. 1 applying Algorithm 4 with 2 Topt and an initial center d, s.t. 1100
0 Oopell 10r opt returns point 0f where [P \ (00 (1 7)r) = 88
RT P
(vā+ / In 4221 13101/33)) /30)
2 (ng++)))g(RR((7111///
Proof. Given a repetition r and iteration f. denote the events
gr == in the (r, dddwss, eoourt & Ocount v Im(4n(++1//2)
E == in the (r,t)-draw, ||A S Jumm (Vd + (2
and denote also & Ur. -h for i = 1,2. Using standard bounds on the concentration of the Gaussian distribution and the xd-distribution together with the union-bound we have that Pr[Ei U Eg < R(T +1 2R(T+1) + RT 3e 2RT < Bo.
Be
Fix and Under ET n E t holding, the required conditions detailed in (2) hold, which using Corollary 3.5 yields the correctness of our algorithm. Under the same notation in Algorithm
denote the distribution of no +.cuun
Σ
(x 0²) + as D
First, observe that under gfit the condition ni.
SSVRT vP
(vd+ / 2lnn(4T)/3.) implies that
88VRT VP
2R(T + 1) I) 44 A coundl
and secondly, observe that Apum is drawn from spherically symmetric distribution, so for any > 0 we have that sum) ||Asum]] S a] = O. And so, if indeed Algorithm passes the if-condition and makes an update step have
Aou
Σ
(x - (x))
E [(oppt - 8²,2)1 0t, 10 ETd n = (Bopt 0², zn/Di
xEB
10 10, gT n ngg
n + Acount

---

independ.
(Popt 88,E
f¹, Er.
Σ
6¹))
niw + Dount
=EB(0 .))
E
(x 8*)
opp
O',EE 1E
0r -0,-"
xgBi0
n + count
Σ
E
1
100 ori!
(Oupt 0¹,
z4 Bir
0¹)
Clm 3.3
2 2/10²=
1
Oopell
1 Oopell
1100-
1
Avount/
n
1- 1/44
and also
(w-0')
||a||11
0r E n Eg =
=BB(0t,r)
sum
0c, ge g ne
ar/Dr
ni Acaunt
Nyw eount
2(Amu.
(x- (e-0"))+[Annull 11
E
n
0r
eg
10,8 Segnnnn ne
Doonne count
(ml + Acoune)
Σ x
Independ.
E
10',0" g
0r
+
0 + A sum
1 0c E..
1
Amgur n
(n
$ 1 - 1/11
(11r)²+
RT RT (88r))
(Vd+ 221n(44T/2.))
2
< 512
(n
since ii 2 88, / ReT Va 21++/22l(tt (1n(44T/20) in order for us make an update.
make all T updates then indeed ||@T Ooll S yr and so IP B(0", (1 +t) = O. So under & Algorithm returns 0²" Ottherwise, at some iteration we do not make an update step, which under & suggests that
Corollary 3.5 suggests that
RT P
(vā+ (2n((1RT/2o) + 2R(T 1) log(4R(( + 1)/8)
" IP ((O < 88
Corollary 4.2. Given ro where Tope S ro S opt and point 6g where 110 0" S 10ropt. w.p.
1 - Algorithm 3 is O(n log lo-)
(og( >ttime algorithm that returns ball B(0", rr) where
(Va+ (ogg(oo((/)))))) /lo((//)loo(//
r S (1 + Top and where JP B(0", r*) 0
7VP
The proof deferred to Supplementary Material, Section C. We comment that the amplification the success probability of the algorithm from 1/s to 1 - can be done using the amplification techniques of [28] which saves on the privacy budget: instead of naïvely setting the privacy budget per iteration p/ R, could use conversions to (e. 6DD and as result "shave-off" factor of R. But since R = (log((1))) this would merely reduce polyloglog factors, at the expense of readability.
5 A Local-DP IPTAS for the MEB Problem
In this section we give the local-model version of our algorithm. At the core of its utility proof is lemma analogous Lemma 4.1, in which we prove that w.h.p. in each iteration / the distribution of our update-step satisfies (w.h.p.) the requirements of (2). Again, due to space constraints, we merely state the LDP algorithm in this section, and defer both its privacy and utility analyses the Supplementary Material, Section D - where we prove that it is p-zCDP algorithm that returns ball
B(" r") such that S (1 + 37) and IP B(O r*) O 7'
(s5)
(vd + /log(1//))

---

Algorithm 5 LDP-Margin based Minimum Enclosing Ball (LDP-MMEB)
Input: a set of n points P S R an approximation parameter r E (0, 1), error parameter B (0, 1). privacy parameter p.
a candidate radius r, and an initial center 0o s.t. |10 Oopt S 10r
1: Set R + [loge,, (1/8)1- 9o + 80, T t 1096
184 7
In 72
Su = 16 o Poantt
R(T+1)
and
R&T (88r))
P
2: repeat
3:
for / - . do
4:
for each (x P) do
5:
Sample A count ~ N0000 couut))
6:
Sample Aram (O, sum Ld).
7:
if o B(0", r)) then
8:
Send Y 1 Acount: Z5
A sam
9:
else Send Y Acount, Zz
= Asam
Set n
Exep Y and iyy Ny. Exer Zz
11:
if (ni < SBvnRT Vp
Vd + /2 (nIn(K(//8)) then return 6
x2 5 Update gr + gr +
12:
2048
for each (x P) do
14:
Sample Acount ~ (O, o² count).
if (xr & B(O² (1 ))) then
16:
Send Y 11+ + count
else Send Y Acount
18:
Set T
Σ2 Y,
if (n²y S 21 (RR -1//o) then return 0 and halt
19:
until repetitions
21:
return
6
Discussion and Open Problems
This work is the first to give a DP-IPATS for the MEB problem, in both the curator- and the local- model, and it leads numerous open problems. The first the question of improving the utility guarantee. Specifically, the number of points our algorithm may omit from P has dependency of 0(1-) in the approximation factor, where this dependency follows from the fact that in each of our T= iterations. Thus finding either an iterative algorithm which makes << T iterations or variant of SVT that will allow the privacy budget to scale like (loggTT) will reduce this dependency Alternatively, it is intriguing whether there exists a lower-bound for any zCDP PTAS of the MEB problem proving polynomial dependency on 7. (The best we were able to prove via packing argument [23, 8] using grid of O((1=)²) many points, leading to a d log(1/) (2/)) bound.)
to only polylog(>-3
different open problem lies on the the application of this DP-MEB approximation to the task of DP-clustering, and in particular - on improving on the works of [24, 34, 14] for "stable" k- median/means clustering. One can presumably combine our technique with the LSH-based approach used in [31] to cover subset of points lying close together, however - it is unclear to what is the effect of using only some of each cluster's "core" on the approximated MEB we return and on the k-means/median cost. But it is possible that our work can be building block in first PTAS for the k-center problem low-dimensions, setting which k-center has a non-private PTAS [22].
Acknowledgments and Disclosure of Funding
O.S. is supported by the BIU Center for Research Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Ministers Office, and by ISF grant no. 2559/20. Both authors thank the anonymous reviewers for terrific suggestions and advice on improving this paper.
10

---

References
[1] A. Asuncion and D.J. Newman. UCI machine learning repository, 2007.
[2] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In NeurlPS, pages 11279-11288 2019.
[3] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight enror bounds. In FOCS, 2014.
[4] Mihai Batdoiu and Kenneth L. Clarkson. Smaller core-sets for balls. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 801-802, 2004.
[5] Asa Ben-Hur, David Horn, Hava T. Siegelmann, and Vladimir Vapnik. Support vector clustering.
J. Mach. Learn. Res., 2: 2:125137, mar 2002.
[6] Yaroslav Bulatov, Sachin R. Jambawalikar, Piyush Kumar, and Saurabh Sethia. Hand recognition using geometric classifiers. In ICBA, 2004.
[7] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In FOCS, pages 634-649. IEEE Computer Society, 2015.
[8] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In TCC, volume 9985 of Lecture Notes Computer Science, pages 635-658, 2016.
[9] Mark Bun, Thomas Steinke, and Jonathan Ullman. Make up your mind: The price of online queries in differential privacy, 2016.
[10] Mihai Bundefineddoiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In Proceedings of the Thiry- Fourthh Annual ACM Symposium Theory of Computing, STOC '02, page 250257, New York, NY, USA, 2002. Association for Computing Machinery.
[11] Christopher J.C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2):121-167, Jun 1998.
[12] Olivier Chapelle, Vladimir Vapnik, Olivier Bousquet, and Sayan Mukherjee. Choosing multiple parameters for support vector machines. Machine Learning, 46(1):131-159, Jan 2002.
[13] Kenneth L. Clarkson, Elad Hazan, and David P. Woodruff. Sublinear optimization for machine learning. J. ACM,
2012.
[14] Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. Differentially- private clustering of easy instances. JCML, volume 139, pages 2049 2059. PMLR, 2021.
[15] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, 2006.
[16] Cynthia Dwork, Frank Mesherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity private data analysis. In TCC, 2006.
[17] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In STOC, pages 715-724. ACM, 2010.
[18] D. Jack Elzinga and Donald W. Hearn. The minimum covering sphere problem. Management Science, 19(1):96-104 104, 2022/01/04/ 1972. Full publication date: Sep., 1972.
[19] David Eppstein and Jeff Erickson. Iterated nearest neighbors and finding minimal polytopes. Discret. Comput. Geom., 11:321-350, 1994.
[20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In STOC, pages 439-449. ACM, 2020.
[21] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. In NeurIPS, 2020.

---

[22] Sariel Har-peled. Geometric Approximation Algoritims. American Mathematical Society, 2011
[23] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, pages 705-714. ACM, 2010.
[24] Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering. In Proceedings of the 37th ACM SIGMOD-SIGA SE----IGATT---GAS Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 395-408. ACM, 2018.
[25] Philip M. Hubbard. Approximating polyhedra with spheres for time-critical collision detection. ACM Trans. Graph., 15(3):17220,, jul 1996.
[26] Jackson A. Killian, Kevin M. Passino, Arnab Nandi, Danielle R. Madden, and John D. Clapp- Learning to detect heavy drinking episodes using smartphone accelerometer data. In Proceedings of the 4th International Workshop on Knowledge Discovery in Healthcare Data co-located with the 28th International Joint Conference on Artificial Intelligence, KDH @ IJCAI 2019, Macao, China, August 10th, 2019, volume 2429 of CEUR Workshop Proceedings, pages 35-42 CEUR-WS.org 2019. Dataset available freely on archive. ics. uci edu/m//datasess/
[27] Piyush Kumar, Joseph S. B. Mitchell, E. Alper Yildirim, and E. Alper Yldrm. Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions. In ALENEX), Lecture Notes Comput. Sci, pages 45-55, 2003.
[28] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In STOC, pages 298-309, ACM, 2019.
[29] Nimrod Megiddo. The weighted euclidean 1-center problem. Math. Oper. Res., 8(4):498-504, 1983.
[30] K. Nissim, Raskhodnikova, and Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM Symposium on Theory of Computing, pages 75-84. ACM, 2007. Full version in: http:://ww. cse. psu. edu/-asmi taamitt//ae the tubs/ NRS07.
cse.psu
[31] Kobbi Nissim and Uri Stemmer. Clustering algorithms for the centralized and local models. ArXiv, 0abs/1707.04777 2018.
[32] Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Locating a small cluster privately. Proceedings of the 35th ACM SIGMOD-SIGACT-SIGN Symposium on Principles of Database Systems, Jun 2016.
[33] Ryan M. Rogers, Salil P. Vadhan, Aaron Roth, and Jonathan R. Ullman. Privacy odometers and filters: Pay-as-you-go composition. In NIPS, pages 1921-1929, 2016.
[34] Moshe Shechner, Or Sheffet, and Uri Stemmer. Private k-means clustering with stability assumptions. In Silvia Chiappa and Roberto Calandra, editors, AISTATS, volume 108, pages 2518-2528 PMLR, 2020.
[35] Salil Vadhan. The Complexity of Differential Privacy, pages 347-450. Springer, Ychuda Lindell, ed., 2017.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See lines 103-105
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
12

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See also Supplemen- tary Material Sections C and
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex-
perimental results (either in the supplemental material or as URL)? [Yes] In the Supplementary Material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See under 'Bar Crawl' in the experi- ment section E.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
As URL, see References
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "w1anQiDA1yn", "reviewer": "Reviewer_qMEV", "summary": "This paper studies the Minimum Enclosing Ball problem (aka 1-Center) in the Differential Privacy Setting. In this problem, you have a set of data points X, and you need to find a point p such that if all the points X fit in some ball of radius r, then the ball of radius (1+gamma)*r around p contains X. This paper provides the first private FPTAS for this problem, meaning that it (approximately) succeeds in the task with high probability, running in time roughly O(nd/gamma^2) time. The paper includes an algorithm that works in the central model of privacy, and another one in the local model of privacy. As in most privacy papers, their accuracy guarantee is not exact: the ball of radius (1+gamma)*r they find may omit up to roughly sqrt{d} points in the central privacy setting, and up to sqrt{n*d} points in the local privacy setting. Previous work of Ghazi-Kumar-Manurangsi provided a PTAS for this problem, meaning the runtime was poly(n, d) when gamma > 0 is a fixed constant. The previous work was applied as a subroutine for private clustering.\n\nFinally, there also appear to be some experiments: I didn't read this part as they are in the appendix and I was mainly interested in the theoretical aspect of this paper, but this is worth mentioning in case other reviewers are interested in them and didn't notice them.\n", "questions": "1) Is your algorithm for the non-private MEB different from the previous FPTAS algorithms? The algorithm is in fact remarkably simple so I am quite surprised this part is new. If it is in fact based on previous work you should mention this at the beginning of Section 3.\n2) Am I correct in saying that your LDP algorithm requires several rounds of interactivity? If so, you should explicitly mention this.", "limitations": "N/A (This work is almost entirely theoretical).", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) The question of 1-center is very interesting in my opinion as it is one of the simplest problems in computational geometry. This problem also has lots of applications (as the authors mention) to problems in clustering, tuning SVM parameters, etc. So, obtaining a FPTAS for this problem with differential privacy is a very nice result.\n2) The technique is extremely simple (especially in the non-private setting), which should make it very easy and beneficial to implement in practice. The private algorithm is of course more complicated than the non-private one, but overall is surprisingly simple.\n3) One downside of their method is that it doesn't work in the case of significant outliers (such as in the setting that Ghazi-Kumar-Manurangsi use to apply to private k-means). Indeed, the authors acknowledge this as a shortcoming, and obtaining an FPTAS for a k-means coreset appears to be a very interesting open problem.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jpFgQWSNRjz", "reviewer": "Reviewer_kQJZ", "summary": "This paper studies the minimum enclosing ball (MEB) problem under the differential privacy (DP) constraints. In MEB, we are given $n$ points in $\\mathbb{R}^d$ and the goal is to output a ball $B(\\theta, r)$ of smallest possible radius $r$ that contains all points. In the non-private setting, it is known that this problem is NP-hard and therefore approximation algorithms have been studied. On this front, it is known that there is a fully-polynomial time approximation scheme (FPTAS) for approximating $r$; in other words, there is a $(n/\\gamma)^{O(1)}$-time algorithm that outputs a ball of radius at most $(1 + \\gamma) * r_{OPT}$ that covers all points.\n\nDifferential privacy enforces that the distribution of the output of the algorithm remains \"similar\" when a single input point is changed. This similarity is paramterized by $\\epsilon, \\delta \\geq 0$. The smaller they are the more privacy protection the algorithm offers. Under DP, it is impossible to hope for a ball that covers all points, and we need to allow a certain number of points to be left out as well. Prior to this paper, the best known $(\\epsilon, \\delta)$-DP algorithm for MEB runs in time $n^{O(1/\\gamma^2)}$ and leaves out $\\tilde{O}(\\sqrt{d}/\\epsilon \\gamma^3)$ points (Ghazi et al., NeurIPS 2020). The main result of this paper is an improvement to this, where the running time is now $(n/\\gamma)^{O(1)}$ (i.e. the algorithm is an FPTAS) and the number of points left out is only $\\tilde{O}(\\sqrt{d}/\\epsilon \\gamma^2)$.\n\n## Non-Private Algorithm\n\nThe non-private version of the algorithm is as follows. First, note that we can easily binary search the radius at the cost of $O(\\log(1/\\gamma))$, so henceforth we will assume that we know $r \\approx r_{OPT}$. The algorithm starts with some initial guess for the ball $B(\\theta_0, r)$. At iteration $i$, the algorithm produces a new center $\\theta_i$ by taking a weighted average between $\\theta_{i - 1}$ and the average of the point that lie outside of $B(\\theta_{i - 1}, (1 + \\gamma) r)$. (This is a \"perceptron-like\" update.) The authors show that such an algorithm stops in $O(1/\\gamma^2)$ steps (meaning that there is no point out side $B(\\theta_i, (1 + \\gamma) r)$; the analysis is quite similar to the perceptron algorithm.\n\n## Central DP Algorithm\n\nNote that the above algorithm is not yet private. To make it private, the authors add appropriately calibrated Gaussian noise to the sum of points and the number of points outside of the ball $B(\\theta_{i - 1}, (1 + \\gamma) r)$. This makes the average private. In the actual analysis, Concentrated Differential Privacy (CDP) is used for composition across iteration.\n\n## Local DP Algorithm\n\nFinally, the authors also observe that the above algorithm can be made to work in the local differential privacy (LDP) setting, in which there is no trusted central server and each user has to send messages that are DP. In this setting, it is still possible to compute the sum of points and the number of points privately, by letting each user adds noise. This increases the error by a factor of $O(\\sqrt{n})$ and thus in this setting the algorithm may leave out as many as $\\tilde{O}(\\sqrt{nd}/\\epsilon \\gamma^2)$ points. Nonetheless, this is already an improvement on the previous bound of $O(n^{0.67})$ (Nissim-Stemmer, ALT 2018) when $d$ is not too large. Furthermore, Nissim-Stemmer work only achieves some (large) constant factor approximation whereas the current work has an approximation ratio arbitrarily close to one.", "questions": "## Questions\n\n- Although it is fine to consider approximate-DP, in some cases, pure-DP are still preferred. Can you please discuss whether you algorithms also work in the pure-DP setting and what the bounds are? (My guess is that there is an increase of $\\sqrt{d}$ factor in the points left out...)\n\n- It is mentioned (Line 42) that minimizing hinge-loss would not work because the utility gets worse with $1/r$. I'm not sure however whether I agree with this: if you already find an initial ball of size $r$, then isn't it true that you can always just project all the points into such a ball and rescale so that this ball has radius one? Now, you have the problem instance on $r = 1$, right? Can you please comment on why this does not work?\n\n## Other Comments for Authors\n\n- It might be worthwhile mentioning that the LDP algorithm is multi-round, with the number of rounds growing as the number of iterations i.e. $O(1/\\gamma^2)$. On the other hand, the algorithm of Nissim-Stemmer works in a fixed number of rounds.\n\n- Another pointer is the work \"Efficient Learning of Linear Perceptrons\" of Ben-David and Simon (NeurIPS 2000). This paper gives a reduction between the MEB and linear classification with margin. The latter of course can be solved by perceptron. It might be possible to indirectly derive your algorithm from their reduction?", "limitations": "No ethical concerns about this work as far as I can tell.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- The algorithm is simple and thus has more chance of being practical.\n- The paper is also written clearly and is easy to follow.\n- The bounds proved in the paper improve upon several recent works on the topic.\n\n## Weaknesses\n\n-  I think the paper should discuss the known non-private algorithms more clearly. For example, the simplest non-private algorithm is almost the same as the current algorithm, except that the update is not using all points outside of the ball, but rather just the furthest point. In that case, the algorithm converges in $O(1/\\epsilon)$ steps; it is unclear what is the relationship between this and the current result in the paper. Moreover, \"perceptron-like\" algorithms for MEB are also known, see e.g. (Clarkson-Hazan-Woodruff, FOCS'10). It is unclear how similar / different these algorithms are from the one given in the paper. \n- Another point is that, all previous works actually consider the more challenging 1-cluster problem, where the goal is only to find a ball that contains at least $t$ points (where $t$ is given as part of the input). MEB is a special case of 1-cluster when $n = t$. Therefore, the results are not directly comparable.  \n\n## Overall Evaluation\n\nOverall, I think the algorithm presented in this paper together with its analysis is a nice addition to the tools on clustering / data analytics in DP, even though the writing (especially discussion of previous works) can be improved. Nonetheless, I think the paper can be accepted to NeurIPS.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "iQBi2huyr8_", "reviewer": "Reviewer_nRv1", "summary": "\nThis paper presents a differentially private algorithm for approximating the ball with the smallest radius that encloses all the input points in an arbitrary dimension. The classical approximation algorithm for this problem runs iteratively. In each iteration, it picks the farthest point from the current center and moves it this direction by a certain “step size”. The step size is smaller for higher iteration and the algorithm runs in $O(n/\\gamma)$ time to compute a (1+\\gamma)-approximation. Unfortunately, the execution of this algorithm relies on the location of the farthest point and therefore it is non-private. \n\nTo overcome this difficulty, this paper modifies the non-private algorithm as follows. Instead of picking the farthest point, this paper takes the mean of all the points that are currently not covered by a ball of optimal radius (such a radius can be obtained by conducting O(\\log n) guesses) and then moves towards the center of the ball towards this mean. The authors show that after sufficient iterations, the estimated center comes $\\gamma$ close to the optimal center as desired.\nNext, given that the mean is sufficient, the authors are able to extend their algorithm to differentially private setting and the local DP setting (although they have to guarantee DP, they have to ignore a small number of points).  \n", "questions": "\n- The original paper for MEB approximation gave extension of their approximation methods to the k-center problem. Can your algorithm also be extended to the k-center problem? If not, why?\n\n- The best-known algorithm for MEB approximation is simply an instance of Frank-Wolfe gradient descent method. The authors result rely heavily on MEB properties and hence, the new DP algorithm does not give a modified FW-algorithm that is differentially private. Is this correct?\n", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strengths:\n- There is a substantial improvement in the execution time over the previous DP algorithm for the MEB problem. MEB problem is closely linked to several important problems in ML, for instance, SVM. \n- Although slower than the previous non-private algorithms, the non-private approximation algorithm presented here appears new and nice. \n\nweakness:\n- the authors have not presented an implementation of their algorithm. Perhaps, the constants make the algorithm impractical?\n- the authors have not considered extending these algorithms to the k-center clustering problem or the SVM problem both of which are of value to the ML community.\n- Presentation of the results can be better. For instance, instead of stating the very minor differences between algorithms 1 and 3, the authors basically repeat the whole algorithm which takes up a lot of space.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WeFXfrBk5l", "reviewer": "Reviewer_VWyJ", "summary": "This work studies the Minimum Enclosing Ball problem, where we are given a set P of n points in d-dimensional Euclidean space and the objective is to output a ball that contains all these points, such that the radius is minimized. This problem has various applications and is also related to the notion of core-sets in the clustering literature. Prior works have proposed fully polynomial time approximation schemes (fPTAS) with various guarantees. This work considers differentially private algorithms (DP) and obtains an DP-fPTAS, which seems to be the first DP-fPTAS guarantee for this problem. More precisely, the algorithm outputs a ball whose radius is a (1 + gamma) approximation in (n / \\gamma^2) time (ignoring log factors) while leaving out at most (sqrt(d) / (\\gamma^2 \\epsilon)) points (again ignoring log factors) where \\epsilon depends on the privacy-parameter. The idea is fairly simple: Start with a good initialization for the ball (using ideas from prior works) and iteratively improve it using a perceptron-style algorithm. This algorithm is also robust to noisy mean-estimation subroutines, therefore this can be exploited to give DP algorithms. This is done for both curator-model as well as local-model differential privacy. As the authors point out, the latter guarantee improves on prior works as far as the dependence on n goes but has worse dependence on other parameters. Finally, simple experiments are conducted to validate the theory. Experiments include synthetic datasets (Gaussian and product of biased Bernoulli distributions) and a dataset containing accelerometer data from a college bar crawl. The experiments plot the distance of the predicted ball center from the optimal center as a function of number of iterations and are meant to be a proof-of-sketch of the theory.", "questions": "Apart from the comments above, other suggestions are as follows\n\n1. In the first paragraph, it would be good to clarify what norm is being used for the balls\n\n2. In L33-36, what is the role of \\epsilon? How does it relate to the privacy parameter?\n\n3. In L38, \"a\" should be \"as\"\n\n4. In the third line of algorithm 4, \"raduis\" should be \"radius\"\n\n5. L380: \"have\" should be \"has\"\n\n6. L512: \"teach\" -> \"each\"", "limitations": "Limitations of the theoretical results are discussed (parameter dependence, assumptions, etc.), but negative societal aspects are not discussed.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I should add a disclaimer that although I work in theoretical computer science, differentially private algorithms are not my field of expertise. However, the theory and proofs seem correct as far as I can tell and the contributions are worth publishing.\n\n### Strengths:\n\n1. The paper is very well-written, the algorithms and proofs are easy to follow. Related work is well-cited, making it clear where the contributions lie.\n\n2. The algorithm is quite easy to describe. In fact, the authors do a great job sketching it to a decent extent in the introduction (L53-107).\n\n### Weaknesses:\n\n1. Code is not provided in the supplementary material, despite the checklist saying it's provided.\n\n2. The experiments are very simple and while they add support to the theory, they are not convincing enough to argue that this is a practical algorithm. However, as the authors mention, this is a theory paper and the experiments are just a proof-of-sketch.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept