On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
Authors: Menachem Sadigurschi
Uri Stemmer
Venue: NeurIPS 2021 Poster (2021)
Keywords: differential privacy
statistical learning
axis-aligned rectangles

Abstract: We revisit the fundamental problem of learning Axis-Aligned-Rectangles over a finite grid $X^d\subseteq\mathbb{R}^d$ with differential privacy. Existing results show that the sample complexity of this problem is at most $\min\left\{ d{\cdot}\log|X| \;,\; d^{1.5}{\cdot}\left(\log^*|X| \right)^{1.5}\right\}$. That is, existing constructions either require sample complexity that grows linearly with $\log|X|$, or else it grows super linearly with the dimension $d$.  We present a novel algorithm that reduces the sample complexity to only $\tilde{O}\left\{d{\cdot}\left(\log^*|X|\right)^{1.5}\right\}$,  attaining a dimensionality optimal dependency without requiring the sample complexity to grow with $\log|X|$. The technique used in order to attain this improvement involves the deletion of "exposed" data-points on the go, in a fashion designed to avoid the cost of the adaptive composition theorems.
The core of this technique may be of individual interest, introducing a new method for constructing statistically-efficient private algorithms.


over On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
Menachem Sadigurschi'
Uri Stemmer
Abstract
We revisit the fundamental problem of learning Axis-Aligned-Rectanne finite grid X C IRd with differential privacy. Existing results show that the sample complexity of this problem is at most min { dd- log |X] dd.s. (log" IX))_ That is, existing constructions either require sample complexity that grows linearly with log |X), or else it grows super linearly with the dimension d. We present a novel al-
gorithm that reduces the sample complexity to only Ö (d (log" (x)))-6) attaining a dimensionality optimal dependency without requiring the sample complexity to grow with log X The technique used in order to attain this improvement involves the deletion of "exposed" data-points on the go, in a fashion designed to avoid the cost of the adaptive composition theorems. The core of this technique may be of individual interest, introducing new method for constructing cebisticalll-efficiie private algorithms.
Introduction
Differential privacy (Dwork et al. 2006] is mathematical definition for privacy, that aims to enable statistical analyses databases while providing strong guarantees that individual-level information does not leak. More specifically, consider a database containing data pertaining to individuals, and suppose that we have some data analysis procedure that we would like to apply to this database. We say that this procedure preserves differential privacy if no individual's 's data has a significant effect on the distribution of the outcome of the procedure. Intuitively. this guarantees that whatever is learned about an individual from the outcome of the computation could also be learned with her data arbitrarily modified (or without her data). Formally,
Definition 1.1
(wwork al. (2006)). A randomized algorithm A (e, (),0)-aa diffferrentt private for every two databases S" that differ on one row (such databases are called neighboring), and every of outcomes F, have Pr[A(S) F] e Pr(A((S)) E F] + 8. The definition referred to as pure differential privacy when = 0, and approximate differential privacy when å > 0.
Over the last decade, we have witnessed an explosion of research on differential privacy, and by now it is largely accepted as a gold-standard for privacy preserving data analysis. In particular, there has been of interest designing private learning algorithms, which are learning algorithms that guarantee differential privacy for their training data. Intuitively, this guarantees that the outcome of the learner (the identified hypothesis) leaks very little information on any particular point from the training set. Works in this vein include IKasiviswanathan et al. 2011 Beimel et al. 2014 2019b
2016 2020
Bun
2015 Feldman and Xiao| 2015] 5, Bun et al. 2019 Beimel et al. 2019a Kaplan
et al.
2019 2020a Alon et al. 2020 Kaplan al. 2020b Bun al. 2020 Alon et al. 2019 and
much more.
'Department Computer Science, Ben- Gurion University the Negev, sadigurs@post. ag..aa.stt........ii... il. Blavatnik School of Computer Science, Tel Aviv University and Google Research, u@uri. co. il.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

However, in spite of the dramatic progress made in recent years on the theory and practice of private learning, much remains unknown and answers to fundamental questions are still missing. In this work, we revisit one such fundamental open question, specifically,
Question 1.2. What is the sample complexity of learning axis-aligned rectangles with privacy?
Non-privately. learning axis aligned rectangles is one of the most simple and basic of learning tasks, often given as the first example for PAC learning in courses or teaching books. Nevertheless, somewhat surprisingly, the sample complexity of learning axis-aligned rectangles with differential privacy is not well-understood. In this work we make significant progress towards understanding this basic question.
1.1 Existing and New Results
Recall that the VC dimension of the class of all axis-aligned rectangles over Rd is (d)) and hence a sample of size ((d) suffices to learn axis-aligned rectangles non- privately (we omit throughout the introduction the dependency of the sample complexity in the accuracy, confidence, and privacy parameters). In contrast, it turns out that with differential privacy, learning axis-aligned rectangles over Rdd is impossible, even when d = (Feldman and Xiao, 2015 Bun al., 2015 Alon et al. 2019]. In more detail, let = (1, [ be a finite (one dimensional) grid, and consider the task of learning axis-aligned rectangles over the finite d-dimensional grid X C IRd, In other words, consider the task of learning axis-aligned rectangles under the promise that the underlying distribution is supported on (a subset of) the finite grid X
For pure-privee pure-private learning, Feldman and Xiao [2015] showed lower bound of 2 (d - log (x() on the sample complexity of this task. This lower bound is tight, as a pure-privatt learner with sample complexity θ (d log [X] can be obtained using the generic upper bound of Kasiviswanathhn et al. (201T) This should be contrasted with the non-private sample complexity, which is independent of [X]
For approximate-prinn complexity in X can be significantly reduced. This, however, came the cost of increasing the dependency in the dimension d. Specifically, the private learner of Beimel et al. (016) has sample
learning, Beimel et al. 2016 showed that the dependency of the sample
complexity Ô dd glog" Ix We mention that a dependency on log" XX] is known to be necessary
[Bun et al., 2015 Alon et al. 2019]. Recently, [Beimel et al. [2019a] and Kaplan al. [2000b) studied the related problem of privately learning halfspaces over a finite grid X", and presented algorithms with sample complexity Ô ( glog ixi). Their algorithms can be used to privately learn axis-aligned rectangles over X with sample complexity Ô (dl.. glor" Ixl). This can be further improved using the recent results of Kaplan et al. 2020a]. and obtain a differentially private algorithm for learning axis-aligned rectangles over X with sample complexity Ô (dl.5 (log" |x))) We consider this bound to be the baseline for our work, and we will elaborate on it later.
To summarize, our current understanding of the task of privately learning axis-aligned rectangles over X gives two kinds of upper bounds the sample complexity: Either d log |X] or d=. (log" IXI"..s 1.5 That is, current algorithms either require sample complexity that scales with log [.], or else it scales super linearly in the dimension d. This naturally leads to the following question.
Question 1.3. Is there differentially private algorithm for learning axis-aligned rectangles with sample complexity that scales linearly d and asymptotically smaller than log |
We answer this question in the affirmative, and present the following theorem.
Theorem 1.4 (informal). There exists a differentially private algorithm for learning axis-aligned rectangles over X with sample complexity (d. (log" IX1) (x)
1.2 Baseline Construction using Composition
Before we present the technical ideas behind our construction (obtaining sample complexity linear in d), we first elaborate on the algorithm obtaining sample complexity Ô (Q..5 (log" (xx)).)). which we consider to be the baseline for this work. This baseline algorithm is based on a reduction to (privately) solving the following problem, called the interior point problem.

---

Definition 1.5 (Bun et al. 2.13). An algorithm A is said to solve the Interior Point Problem for domain X with failure probability 3 and sample complexity n. for every m 2 n. and every database S containing elements from X it holds that: Pr(min(S) - A(S) S max( 2 3.
That is, given database S containing (unlabeled) elements from (one dimensional) grid X, the interior point problem asks for an element of X between the smallest and largest elements in S. The baseline we consider for privately learning axis-aligned rectangles as follows. Suppose that we have a differentially private algorithm A for the interior point problem over domain X with sample complexity n (let us ignore the failure probability for simplicity). We now use A construct the following algorithm B that takes a database S containing labeled elements from X For simplicity, we assume that S contains "enough" positive elements, as otherwise we could simply return the all-zero hypothesis.
1. For every axis i [d]:
(a) Project the positive points in onto the ith axis.
(b) Let A; and B; denote the smallest n and the largest n (projected) points, without their labels.
(c) Let a; < A(A)) and b; A(B.).
2. Return the axis-aligned rectangle defined by the intervals [a,, b,] at the different axes.
Now, recall that each application of algorithm A returns an interior point of its input points. Hence, for every axis i, it holds that the interval (a,, bi] contains (the projection) of all but most 2n of the positive examples in the ith axis. Therefore, the rectangle returned in Step [eep2[containg all but at most 2nd of the positive points (and it does not contain any of the negative points, because this rectangle is contained inside the target rectangle). So algorithm B errs on at most 2nd of its input points.
Assuming that |S] >> 2nd, we therefore get that algorithm B has small empirical error. As the VC dimension of the class of axis-aligned rectangles is (d), this means that algorithm for this class with sample complexity O(nd). The issue here is that algorithm B executes algorithm A many times (specifically, 2d times). Hence, in order to argue that B is (e. -)differrentially private, standard composition theorems for differential privacy require each execution of algorithm A to be done with privacy parameter of z e/ /2d. This, in turn, would mean that (the sample complexity of algorithm A) needs to be at least /2d, which means that algorithm B errs on 2nd d input points, which translates to sample complexity of [S] >> d
a PAC learner
The takeaway from this baseline learner is that in order to reduce the sample complexity be linear in d, we want to bypass the costs incurred from composition. That is, we still want to follow the same strategy (apply algorithm A twice every axis), but we want to do it without appealing to composition arguments in the privacy analysis. We now briefly survey two intuitive attempts that fail achieve this, but are useful for the presentation.
Failed A Attempt## #1. As before, let A denote algorithm for the interior point problem over domain X with sample complexity n. Consider the following modification to algorithm B (marked in red). As before, algorithm B takes database S containing labeled elements from Xd, where we assume for simplicity that contains "enough" positive elements.
1. For every axis i E [d]:
(a) Project the positive points in S onto the ith axis.
(b) Let A; and B, denote the smallest n and the largest n (projected) points, without their labels.
(c) Let ag < -AAA)) and b; + A(B:).
(d) Delete from S all points (with their labels) that correspond to A; and B;.
2. Return the axis-aligned rectangle defined by the intervals [a., b:] at the different axes.
The (incorrect) idea here is that by adding Step l we make sure that each datapoint from S is "used only once", and hence we do not need to pay in composition. In other words, the hope is that if every execution of algorithm A is done with a privacy parameter e, then the whole construction would satisfy differential privacy with parameter ((e).
The failure point of this idea is that by deleting one point from the data, we can create "domino effect" that effects (one by one) many of the sets A, B, throughout the execution. Specifically, consider
3

---

two neighboring datasets S and 8' = S U {()) for some labeled point (I', E X" x f0.1). Suppose that during the execution on S' it holds that x' E Ai. So the additional point x' participates "only" in the first iteration of the algorithm, and gets deleted afterwards. However, since the size of the sets A; B; is fixed, during the execution on (without the point x²) holds that a different point gets included in A₁ instead of z', and this point is then deleted from S (but it is not deleted from S" during the execution on S¹). Therefore, also during the second iteration we have that S and S are not identical (they still differ on one point) and this domino effect can continue throughout the execution. That is, a single data point can affect many of the executions of A, and we would still need to pay in composition to argue privacy.
Failed Attempt #2. In order to overcome the previous issue, one might try the following variant of algorithm B.
1. For every axis i E [d]:
(a) Project the positive points in S onto the ith axis.
(b) Let si = 2n + Noise and let size = 2n + Noise.
(c) Let A, and B₁ denote the smallest size and the largest sizep, (projected) points, respec- tively, without their labels.
(d) Let 0g + A(A,) and b; + A(B.).
(e) Delete from S all points (with their labels) that correspond to A; and B,.
2. Return the axis-aligned rectangle defined by the intersection of the intervals (as, by] at the different axes.
The idea now is that the noises we add to the sizes of the A,'s and the B;'s 's would "mask" the domino effect mentioned above. Specifically, the hope is as follows. Consider the execution of (the modified) algorithm B on S and on S" = SU [(x', 3/'), and let i be the first axis such that x' E A; U B; during the execution on S Suppose w.l.o.g. that x' B,. Now, the hope is that if during the execution on S we have that the noisy sizeB, is smaller by I than its value during the execution on S', then this eliminates the domino effect we mentioned, because we would not need to add another point instead of x'. Specifically, during time i, the point x' gets deleted from S', and every other point is either deleted from both S, S' or not deleted from any of them. So after time the two executions continue identically. Thus, the hope is that by correctly "synchronizing" the noises between the two executions (such that only the size of the "correct" set gets modified by 1) we can make sure that only one application of A is effected (in the last example only the execution of A(B,) is effected), and so we would not need to apply composition arguments.
Although very convincing, this idea fails. The (very subtle) issue here is that it is not clear how to synchronize the noises between the two executions. To see the problem, let us try to formalize the above argument.
Fix two neighboring databases S and S' = SU ((x' (('' Let us write A,, B, and A B¹ to denote these sets during the executions on S and on S", respectively. Aiming to synchronize the two execu- tions, let us define a mapping vectors during the execution on S (determining the values of sizc,,, sizc : sizc sizc such that throughout the execution we have that A, A and B, B¹ for all i except for a single pair, say Bj + Bj. of neighboring sets.
2dd - 2d from noise vectors during the execution on S' noise
The straightforward way for defining such a mapping is as follows: Let j be the first time step in which the additional point x' gets included in a set A', or By, and say that it is included in By. Then the mapping would be to reduce (by 1) the value of sizeB, (the noisy size of B, during the execution on S). This would indeed make sure that, conditioned on the noise vectors v' and executions differ only in single application of the interior point algorithm A, and hence the outcome distribution of these two (conditioned) executions are very similar (in the sense of differential privacy). That is, for any noise vector e and any event F.
TT'',, the two
Pr(B(S") E Fly) e Pr(B(S) E F| +
Furthermore, (assuming an appropriate noise distribution) we can make sure that the probability of obtaining the noise vectors v and (TV) are similar, with densities differing by at most an e factor (as

---

is standard in the literature of differential privacy). Therefore, had the mapping we defined was bijection, for any event F we would have that
Pr(B(S") E
Σ Pr[u] Pr(B((") Flu]
Σ ef Pr(m(()] (e Pr(B(S) FI 6)
Σ e Pr-F([[()] (e Pr(((() F| +
x())
= = Pr(B(S) E +
which would be great. Unfortunately, the mapping т we defined not a bijection, and hence the second-to-last equality above is incorrect. To see that it is not a bijection, suppose that d = 2 and consider a database S containing the following positively labeled points: Many copies of the point (0, O), well as 10 copies of the point (1,0) 0) and 10 copies of the point (0, 1). The neighboring database 5' contains, in addition to all these points, also the point (2 2. Now suppose that during the execution on S' we have that [B] = 5 and [B&] = 4. That is, the additional point is included in By. During the execution on S we therefore reduce (by 1) the size of BN and so B |By] Now suppose that during the execution on S' we have that [ = 4 and B 5. Here, during the execution on S we reduce the size of B- and so, again. |B = [B2l = This shows that the mapping we defined is not bijection. In general, in d dimensions, it is only a d-to-1 mapping, which would would break our analysis completely (it will not allow us to avoid the extra factor d).
1.3
Our Solution Technical Overview
We now present simplified version of our construction, that overcomes the challenges mentioned above. We stress that the actual construction is a bit different. Consider the following (simplified algorithm.
For every axis i e [d]
(a) Project the positive points in S onto the ith axis.
(b) Let sizca, 100n + Noise and let sizeg, 100n Noisc, where the standard deviation of these noises is, say, 10n.
(c) Let A; and B, denote the smallest s, and the largest sizen, (projected) points, respec- tively, without their labels.
(d) Let Ainer C A; be the n largest points in A; Similarly, let Binner C B; be the n smallest points in By.
(c) Let ag + A(Ajuner) and b, + A( A(Biuner)
(f) Delete from S all points (with their labels) whose projection onto the ith is not in the interval Ja,, b,].
2. Return the axis-aligned rectangle defined by the intersection of the intervals (a,, b.] at the different axes.
There are two important modifications here. First, we still add noise to the size of the sets As, B. but we only use the "inner" points from these sets. Second, we delete elements from S not based on them being inside A; or B,, but only based on the (privately computed) interval [a,, 6.]. We now elaborate these ideas, and present a (simplified) overview for the privacy analysis. Any informalities made herein are removed in the sections that follow.
Let S and S' = S U {a', yy)}} be neighboring databases, differing on the labeled point (z', v/). Consider the execution on S and on S'. The privacy analysis based on the following two lemmas.
Lemma 1.6 (informal). With probability at least 8, throughout the execution it holds that a' participates in most (llog(1/)) sets A;, B,.
This lemma holds because our choice for the noise magnitude. In more detail, given that x' As, there is constant probability that x' E A,, fnner, Since the interior point a, is computed from
5

---

Aftmer, in such case we will have that x' < a, and hence, x' is deleted from the data during this iteration. This means that every time x' is included in A,, there a constant probability that x' will be deleted from the data. Thus, one can show (using concentration bounds) that the number of times i such that x' E A; is bounded (w.h.p.). similar argument also holds for Bt-
Lemma 1.7 (informal). In iterations i in which x' is not included in A; or B;, we have that ag and by are distributed exactly the same during the execution on S and on S'.
Indeed, in such an iteration, the point r' has no effect on the outcome distribution of A (who computes a,, by). Overall, w.h.p.. there are at most (log })) axes the point x' effects. We pay in composition only for those axes, while in all other axes we get privacy "for free". This allows us to save factor of Vd in the sample complexity, and obtain an algorithm with sample complexity linear in d.
Note that the definition of privacy we work with is that of (e. (6.8)-da d)ffeerrrell privacy. In contrast to the case of (e. didfifferelta privacy, where it suffices to analyze the privacy loss w.r.t. every single possible outcome, with (E, 6) -diifferential privacy we must account for arbitrary events. To tackle this, we had to perform a more explicit and meticulous analysis than that outlined above. Our analysis draws its structure from the proof of the devvanced-composstion theorem [Dwork et al. 2010), but instead of composing everything we aim to preform effective composition, meaning that we incurr privacy loss only on a small fraction of the iterations. To achieve this, as we mentioned, we partition the iterations into several types- iteration do not. However, this partition must be done carefully, as the partition itself is random and needs to be different for different possible outcomes.
which we "pay" in privacy and iterations which we
We believe that ideas from our work can be used more broadly, and hope that they find new applica- tions in avoiding (or reducing) composition costs in other settings.
Remark 1.8. To simplify the presentation, in the technical sections of this paper we assume that the larget rectangle is placed at the origin. Our results easily extend to arbitrary axis-aligned rectangles.
Notations. Two datasets S, S' E X' are said to be neighboring if they differ exactly on one element, Given a number & E N and a dataset S containing points from an ordered domain, we use min(S, E) (or max(S, f)) to indicate the subset of É minimal (or maximal) values within S. When S contains points from dddiimnntionl domain, we write min; E) (or (S, f)) denote the subset of l minimal (or maximal) values within S w.r.t. the 2th axis. We write Lap(u, b) to denote the Laplase distribution with mean f and scale b, when the mean is zero we will simply write Lap(b). See the full version of this paper for additional preliminaries from learning theory.
formally, dir (S, S*)
2 The Algorithm
In this work we investigate the problem of privately learning the class of axis-aligned rectangles, defined as follows.
Definition 2.1 (Axis Aligned Rectangles). Let X' (0, domain. Every p (p1, (PI,....PPP) .Pa) E X, induces a classifier hp X - {0,1) s.1 for a given input x E X we have
(0.....X² xjd be a finite discrete d-dimensional
f1, h,(x)= = -{, o, otherwise
Vi [d] 1 S P:
Define the class of all axis-aligned and origin-placen rectangles as REC = (hp : p E X3.
Let A be an (E, didfffrrrenti private algorithm for solving the interior point problem over domain [O.....X] . with failure probability 33 and sample complexity IPA (e, 6,3). We propose Algorithm which we call HandMargins, and prove the following theorem.
Theorem 2.2. Let < 1,5 < 22, a, Algorithm i
is (a, B, (., learner, for the RECa
class, given a labeled sample of size O (IP L log (t) log ) 8 (d + 2)0, and غ = O (e log(1/6))
"Note that the use of the Laplace noise is different from the standard use in the literature of differential privacy. Unlike the standard use of the Laplace noise, we do not use it in order to obtain private estimation for some real-valued function of the data. We use it in order to mask the domino effect mentioned in the introduction. Hence, it is not proportional to the sensitivity, but rather to the output of the A algorithm.

---

Algorithm 1: RandMargins
Data C IRd of size n. and parameters & < & and ó < 1/E², Tool used: An (e, 6--rivate algorithm A for solving the interior point problem with failure probability 3 and sample complexity IPA (e, 6)
Input:
Denote A APA (5. 8,
Denote μ = 4A log(1 (1/3)
Initialize 5 f- { S i labeled 1}
for i
do
C: Lap(2AA
B, max [u+
D. min, (Bn, A)
P; - AD,
R, {y E.S: ylil pr}
$ 5 S R
end for
Return (P),...,
Remark 2.3. Kaplan et al. 22020a)
introduced an algorithm for the interior point problem with
sample complexity A (c, 6, within Algorithm proovdes the result of Theorem 1.4
log! 1.5 (?) (log" ((x1))1.5) Hence, using their algorithm
We analyze the privacy guarantees of Algorithm Tin Section and show the following lemma.
Lemma 2.4. Let and 8 < O IPA 8, B) d log (2) log (3)) Algorithml and á = O (s log(1/6))
given a labeled sample of size is (E, (E,f)-diifeereniaa))) private, for δ = (d (d+2)6.
We analyze the utility guarantees of Algorithm in Section and show the following lemma.
Lemma 2.5. Let a, 5, given a labeled sample of size O with probability at least 1 Algorithm iis a-accurate.
log (2) log (
Privacy Analysis
Proof of Lemma 2.4 Let S and S' = S ((x'x//)) be neighboring databases, differing on the labeled point (x v²) Consider the execution on and S¹.
denote by ind,(a) (x) the position of the point æ the remaining data S, when the data is sorted by the 7th coordinate.
Denote by i* the first iteration on which a'( > note that i* is a random variable. For an input set S, denote by S; the remaining set at the beginning of the 7th iteration and its size by n.
Partition the iterations in the following way: I., (i < it a E B)), Imns (i <<i 1 B.}. Lafter = ( }.
We first argue that Ienl is small (with high probability). Intuitively, this follows from the fact that conditioned z' E By, with constant probability, we get that x' B \ D, Note that in such case, projecting on the ith axis, x' is bigger (or equal) than any point in D.. Furthermore, as the interior point is computed from D:, w.h.p. we get that x'( 2 pi, and hence x' is removed from the data. To summarize, conditioned on x' B' there is a constant probability that x' is removed from the data, and hence the number of times such that x' E B' must be small (w.h.p.). We make this argument formal in the full version of this paper, obtaining the following claim.
Claim 3.1. Pr|[Zan| > 35 logg(11))) < 8.
Next, we will denote by B the inner steps of the loop in the algorithm. Meaning, the input 5,, which B uses, along with the random noise and the mechanism A. in order to output p.. We now argue,
7

---

briefly, that is (e. 8) differentiall private for every fixture of W. This, in particular, would mean that B is (s, diffferrentl private. So fix w,, and fix two neighboring inputs S, to algorithm B. Since S;, S/ are neighboring, we also have that B, and B/ are neighboring (the sets containing the top j + wy elements in S, and S% respectively). By the same reasoning, we also have that D; and D are neighboring, As result, the outcome distributions of the given mechanism A, on D; and on D are (e, -iiddistinguuihaalee showing that B is (c, 6) -differentially private.
For convenience, we will assume that the B's output includes the noise value wi, and that the final output of RandMargins includes the noise vector w = (Wi,..., Wa). As will proven below, algorithm RandMargins remains differentially private even when releasing this noise vector (in addition to the output (Pi)....P)).
Lemma 3.2 (Vadhan 2017). For every (e, --private algorithm M and every two neighboring datasets S, S", there exist an event G = G(M, S, S") such that (i) Pr[M(() G > 1 - 6, and (ii)
Pr[M(()) E G > 1 6, and (iii) Vx E G In Pr(M(())=))
(r(M)())=x)
) S..
Define the event G ((),w) Vj E [d] : (pj.wy) m/) E G(B, Sj, 83),. where S,.)5, S3) is the event guaranteed exist by applying Lemma 3.2 to B, Sy.
Note that by Lemma 3.2 and the union bound Pr[C] 2 dō.
We wish to prove that for any possible output set P, it holds that
Pr Pr[RandMargins(S) Pe S ef PrfBandMarginssS5)
PI
Define the set
R= (={12.0) (p:w) In PP(RM(S) = (y)
Pr(R.M(S)) (PHRRM(S)=(0) w] 28J.
where R.M is an abbreviation for RandMargins.
Now note that for every event P.
Pr(RM(() e P] & PH(RM(S) E R + P:[M((()) E P\RR
S PP(RM((S) E R| +é Pr(RM((')) E P\ I Pr(RM((S E R| PH(MM(S)) E P]
So it is down to show that Pr(R.M(S) E R] s 3. That is, we need to prove that
In Pr(RM(()= Pp
Pr RM(3)
> 0 50.
Pr(R)((S) P, w)
We calculate,
In Pr(RM(() = w)
p.me (MM()
Pr
Pr(RM((8)) = P. p)
>
=
PI(RM(() = w)
Pr(RM(S)= = =p
p.w) ) -Lp.wgG > $)
Pr
In
1p.EEG >
OR
In
PT(R.M(S') -p...)
PI(RM((') = P. w)
PI(RM(S)= = p,w) In
Pr
1p..EG
p.me RM(s)
Pi(RMM(S)) Ps w))
In PT(RM((S) = p, w)
Pr
Ap.weG >
RM(S)
(r(R)((S)) = p, w)
(T(RM(S) = p,w)
Pr
In
1 1...EG > E
+ (11-Pr(G]
D.W+-RM(S)
Pr(RM((S)) w)
(T(RM((S = p.W)
Pr
In
1 J.EEG > g
+ +6.
p.me RM(S)
Pr(RRM(S') w)
8

---

remains prove that PTp.we (M(() In
(r(RM(())==...) L..wEG >
P
S. We calculate,
In PH(RM(S) w) (P((RM(S') p.u) 4PEG >
Pr W.--RM(S)
PT(RM((); Pi, wi Pei; Wei)
Pr
1 p.eeG
(AF-R((S)
Pr(RM(()) = Pr, wi Pei, Wes)
d
Pr(RM(S); - Ps, w/ Peis We))
Pr
p.we >
RM(()
Pr(RM(S'): = Pi, - Peii Wei)
Pr(RM((); Ps, Wi |pei Wes)
<
(MM()
Pr
(r((RM(S'); = Ps; Wi Pect Wei) In
P (G,
Pr(RM((); = Ws Peci Peii,
Pr
1 1...
P. (MM(S
Pr(RMM(S)): w Pet Wei)
PEI
Pr(RM((); = Ps: p; Wei)
Σ
(..:EEG(BBB...533
Pr(RM((S)); Pi, Pei, wes)
(Pr(RM(S)) u. |Pc;
+
In PPI(RM(S)) us |Pe, Wei) 1 (...E0)(1BB888883
iETufter
We will prove the following
(i) Pr EieIoftor
In
(M(R Pi(RM(S") (eew))))
1 1,,.,E..(8,55553) =
(ii) Pr Eietoue In
P ppl Pr(RMM(5)) P4 P4. per:ee)))
P...EG.((88..55) =
(iii) Pr EiEI..
In P:(RM(S):=P...l Pcn Pi(RM(()); Pei.ee))
P.
2 1 8
Combining the above three claims implies bound and finishes the proof.
Proof (i). After i", by the algorithm definition, x' gets removed from S Hence, for every > i*, conditioning on &M Pei. it holds that B B. This implies that, for every i E Iafters
Pr(RMM(S): = Pt. w/ Per. wee) = Pr(RM((S) = Pr, 24 Pess wei)
which yields
Pr(RM((), = Ps; wi Pei: wes) Peii wei)
Pr(RM(('): = pi, wi
(P((RM(S): = Pi; Wi Pei, Wei)
+ Pr
Σ
Pr((RM((S): = Pi, W/ Peis Wes)
R.M.EG,(BB.....) =0 =1
VEInfter
Proof (ii). Recall that by the definition Tout for every Tout holds that x' & B/, and hence, conditioning on the previous outputs, B' B,. We therefore get that the distribution of the 5th output is also the same. Formally,
Pr(RMM(S): = Pt. w/ Per. we:) Pr(R.((S)) = we Pei, wee).
'Noe that the outer probability is over and This allows the partition of the iterations into Iin Lout Iofter to be well-defined, this partition depends p, w.

---

This results in
In Pr(RM((S); pr: wi peci (ei,
(P((RM(S") = PP. Pers wes)
P...EGG(BB3..83) =0
Pr Σ In (P((RM()); Pi. wi Peci Wei) LiEZou
(......( =0 1.
Pr(RM((S)) = Ps. Ws Per, wes)
Proof (ii). Note that, as we assume that the output of R.M includes the random Laplasian noise, then by fixing the past catput-poing pei, Wei we also fix S,, S%. So,
Pr(RM(()) = Pi, w/
Pess wei)
In
-1 (B..,E.
Pr(RM(S') = Pi, Pei, wee)
= =In Pr((((S)) = Pi, wi)
(B
Pr(B(()) Pi, w:)
Morcover, by the definition of the events G; it holds that
Pr(((S:) Pi, w:) Pr(B(S)) = pi, wi) 1 -1P...EG((BB88833)
Pr
28 =1
which yields
Pr(B((S) = Pt, wi)
Pr Σ In
1 I,
Pr(((()) Pt, w.)
LieZ
Pr
28 E Pr [in
2c
LieZ.n
where the last inequality follows from Claim 3.1 and from our choice of غ = 0 (s (=log(1/8))
4 Utility
First, must ensure that at every iteration, with high probability, have enough points left in At the same time we must ensure that the axillary algorithm A will output an inner point of the given subset. Denote a; wy + μ.. By the definition of the noise and the mean 14, we get that for every iteration
Proof of Lemma 2.5
Pria; > 6A log(1/3)] < B. Hence, with probability dB, holds that for every a; < 6A log(1/3) This means that the total number of removed point is at most 6dA 1og(1/3) Therefore, for a sample of size 6dA log(1 (og(133) /3) with high probability S will contain enough points.
Regarding the algorithm's 's accuracy, we notice that at every iteration j. A outputs a point which is least the -h largest point from the points left in the set. This means that, in the worst case, delete aj points from the data set at this iteration. Hence, again in worst case, we will output the Σj=1 ay-th largest point in the jth axis.
By the above reasoning, with high probability 6A (193). Mcaning that every Pj at least the Σj= a, I 6dd log(1/3) largest point the axis. This implies that, for sample of size O dA log(1/a) log (1)))) denoting the by hp the hypothesis induces by the output of Algorithm Prgwpp Jerrs (hp) 2 a/22 < 3/22. Since the VC-dimension of the class REC, is 2d, by the VC-theory bounds and the fact that the sample size is least as the sample complexity bound O (1 (d (2) log
say that for every it holds that ay S
)))) it holds that: errs(h,) + a/2] < 8/2, Combining the two bounds concludes the proof.
Prs-pn (err (hp) >
10

---

Acknowledgments
This research was partially supported by the Israel Science Foundation (grant 1871/19), by Len Blavatnik and the Blavatnik Family foundation, and by the Cyber Security Research Center at Ben-Gurion University of the Negev.
References
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestonee dimension. In STOC, pages 852-860. ACM, 2019.
Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. Closure properties for private classification and online prediction. In COLT, volume 125 of Proceedings of Machine Learning Research, pages 119-152. PMLR, 2020.
Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. Machine Learning, 94(3):401-437, 2014.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure approxi- mate differential privacy. Theory of Computing, 12(1):1-61, 2016. doi: 10.40866toc.2116.0011 URL httphttt://wwwt. http:/..w.hw........ to comput ing. org/ arti eel12ll/eeev01001111111
Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer. Private center points and learning of halfspaces. COLT, volume 99 of Proceedings of Machine Learning Research, pages 269-282. PMLR, 2019a.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of pure private 2019b. UtLp:/t:://mil wttpalr.rrrg/ppp///200000
learners. J. Mach. Learn. Res., 18-269.hte
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Learning privately with labeled and unlabeled examples. Algorithmica, pages 1-39, 2020.
Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In FOCS, pages 634-649, 2015.
Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning of multiple concepts.
Journal of Machine Learning Research, 20(94):1-34, 2019. URL http://mmm wwwpal..orgg/paeee oxgg/apers/ v20/18 1088559..1.. html
Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In FOCS, pages 389-402, IEEE, 2020.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, pages 265-284, 2006.
Cynthia Dwork, Guy Rothblum, and Salil Vadhan. Boosting and Differential Privacy. 2010 IEEE 51st Annual Symposium Foundations of Computer Science. pages 51-60, Las Vegas, NV, USA, October 2010. IEEE. ISBN 978- 12244-8555-3 doi: 10.1 (L09///CS.200..... URL http://ieeexploree ieee. http.//////ocmmmm///////....
Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. SIAM J. Comput., 44(6):1740-1764 2015.
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In SODA, pages 1106-1125, SIAM, 2010.
Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Differentially private learning of geometric concepts. In ICML., volume 97 of Proceedings of Machine Learning Research, pages 3233-3241. PMLR, 2019.
Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In COLT, volume 125 of Proceedings of Machine Learning Research, pages 2263-2285, PMLR, 2020a.
11

---

Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. Private learning of halfspaces: Simplifying the construction and reducing the sample complexity. In NeurIPS, 2020b.
Haim Kaplan, Yishay Mansour, and Uri Stemmer. The sparse vector technique, revisited. COLT, 2021.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM J. Comput., 40(3):793 2011.
Salil Vadhan. The Complexity of Differential Privacy. Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography, pages 347-450. Springer International Publishing, Cham, 2017. ISBN 915--339957744777177833339----19 wwt.:iii...innn..oooo wwt.://gr.....///....o//////0030
doi:
URL
Series Title: Information
Security and Cryptography.
12


Reviews:
[{"review_id": "oWeYgCLX-3y", "reviewer": "Reviewer_GhmR", "summary": "This paper considers the problem of learning axis-aligned rectangles in a differentially private way. It presents a simple and new technique to reduce the sample complexity down to $\\tilde{\\mathcal{O}}\\left(d \\cdot (\\log^* |X|)^{1.5} \\right)$, in contrast to the original result which either has a super-linear dependence in $d$ or grows linearly with $\\log |X|$.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper is clearly written and technically sound. The proposed solution follows the baseline works previously established by Kaplan et al. , that for each axis, it reduces to an one-dimensional Interior Point Problem. As samples could be repeatedly used for different axis, standard composition theorem from differential privacy would requires $\\Omega(d^{1.5})$ many samples. To overcome this issue, this paper tweaks the original reduction by making sure that each sample only participates in one iteration and removing the potential \"domino effect\", and performs a new theoretical analysis, the efficient composition.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No suggestions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "h4UokQoihqO", "reviewer": "Reviewer_Mzck", "summary": "This paper studies the problem of privately learning an axis-aligned rectangle. In private learning, the goal is to approximate an unknown target function while leaking little information about individual training samples. More formally, the learning algorithm is required to be differentially private in the sense that for any two training sets differing in a single training sample, the distributions of the output target functions on the two data sets are (eps,delta)-close in the standard differentially private notion.\n\nPrevious work on this problem includes a learning algorithm with sample complexity O(d^1.5 (log* X)^1.5) and one with O(d log X) when the rectangles comes from a d-dimensional grid X^d. Here the dependency on eps, delta and the accuracy of the learned hypothesis has been hidden from the bound, but is polynomial in eps and the accuracy and polylogarithmic in delta.\n\nIt is known from a lower bound side that the sample complexity must depend on log*X and grow linearly with d. The goal of this submission is to derive a learning algorithm with samples depending linearly on d and as o(log X). This is achieved by presenting an algorithm needing O(d (log*X)^1.5) samples, thus shaving a sqrt(d) factor (or a logX/log*X factor) from previous work.\n\nThe main idea in the algorithm is to use a subroutine for the Interior Point Problem to find a point close to the edges of the rectangle learned. Formally, the IPP asks to output a point lying between the minimum and maximum point in a one-dimensional data base with domain X. This can be done privately with O((log*X)^1.5) samples, ignoring the dependency on eps and delta. The basic idea is to pick the outermost 100n+noise points that lie inside the rectangle along each axis. From these, the n points closest to the interior of the rectangle are selected and the IPP algorithm is run on them to output a point with i'th coordinate inside the rectangle and close to the border.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is well-written, with a clear walk-through of the main ideas of the algorithm and an explanation of the pitfalls one has to avoid. The problem of learning a rectangle is pretty fundamental and the combination with privacy seems well-motivated. The algorithm is a quite simple reduction to IPP, with the tricky part being the analysis.\n\nImproving the sample complexity by a sqrt(d) factor is a nice theoretical contribution, although the many hidden factors depending on eps, delta etc. make the algorithm rather infeasible in practice. At least one has to care about the exact sample complexity of privately learning rectangles to enjoy the paper, as otherwise it feels a bit like parameter-pushing. All in all, I feel the paper helps understand the sample complexity of a fundamental problem, but it is not clear to me that the result will otherwise have much impact. As such, I find that the paper can be accepted at NeurIPS, but is not a clear accept.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "aORd4b_8nJJ", "reviewer": "Reviewer_wYvK", "summary": "The authors investigate the problem of differentially-privately learning Axis-Aligned Rectangles over a finite grid X of dimension d. They demonstrate the existence of a differentially private algorithm for learning axis-aligned rectangles with sample complexity that scales linearly in d and is asymptotically smaller than log |X|. The sample complexity bounds achieved by authors for this problem are better than existing DP works. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Given a sample S containing labeled points from a d-dimensional finite space X, a naive DP algorithm suggested by the authors projects positive points in S onto each axis i (i=1,...,d) and makes two black-box calls (per dimension) to the interior point algorithm of Kaplan,Ligett, Mansour, Naor, Stemmer [COLT’20] with sample complexity of \\tilde{O}((log^*|X|)^{1.5}), where the first call is made with the smallest n projected points outputting a_i and the second call is made with the largest n projected points outputting b_i, and the algorithm returns the rectangle defined by the interval [a_i,b_i]. Using composition theorems to analyse this algorithm would give a sample complexity of \\tilde{O}(d^{1.5}*(log^*|X|)^{1.5}). The authors reduce this sample complexity to \\tilde{O}(d*(log^*|X|)^{1.5}) by adding noise and deleting encountered points appropriately that helps bypass the costs incurred from composition. \n\nIn more details, given two neighboring databases S and S’ which differ on a point (x’,y’), the (\\eps,\\delta)-privacy analysis of the main algorithm only pays a privacy loss for those axes which the differing point x’ directly affects and this is bounded by O(log (1/\\delta)), for the rest of the axes, the output distributions of S and S’ are the same. The authors essentially refine the advanced composition theorem to only compose privacy over those iterations for which the differing point is actually present, and thus incur a privacy loss on a small fraction of interactions. This technique is a good technical contribution that can potentially be used in the analysis of other DP algorithms. \n\nIt would help to give more clarity on the actual amount of noise added at each step of the main algorithm. For example,  Laplace noise is usually added in proportion to the sensitivity of the function being computed, it is not clear why Laplace noise is added in proportion to the sample complexity of the IP algorithm to \\mu. \n\nClarity\n\nIt would help to explain a bit the proof strategy and analysis tools -- this gives  the PC members taking the decision more insight onto the novelty of the paper and elements of originality and difficulty.\n\nSection 1 is written very well and provides a good high-level description of the methods, but Sections 2, 3, 4 and 5 contain many typos and can be more clear. \n\nIn Section 2, Differential Privacy should be explained with respect to adding Laplace noise, since this is what is applied in the main algorithm. \n\nIn Section 3, the main theorem (Thm 3.2) has undefined variables, the Sample size includes a \\Delta parameter that has not been defined in the statement. I assume this is the sample complexity of the IP algorithm, but this should be made clear. \nSome typos: \nLine 250: typo, should be ``Laplace’’ distribution \nLine 295: typo, should be ``differentially’’-private in Lemma 3.4    \nLine 333: typo, should be ``auxiliary’’ algorithm A\n\n\nIn Sections 4 and 5, the actual proofs for privacy and accuracy can be more clear. For eg., lines 334 and 335, it would be helpful to expand on how the Pr[a_i>_]<\\beta is obtained. \n\nSignificance\n\nGiven the recent results on learning and privacy, this paper will be of interest to the privacy community. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Iw-x-VcVcMY", "reviewer": "Reviewer_qdue", "summary": "This paper studies the problem of PAC learning an axis-aligned rectangle in d-dimensions under the constraint of differential privacy (DP). The class of d-dimensional axis-aligned rectangles can be viewed as a generalization of threshold functions. Previous work have shown that the problem of privately learning thresholds is equivalent (up to constants) to the problem of privately selecting the interior point of a set of totally ordered points. A naive approach to extend this result to high-dimensional rectangles is to compute the threshold in each dimension separately and then use advanced composition. Unfortunately the dependence of the samples complexity of this approach on the dimension is $d^{1.5}$ (rather than $d$). Therefore, this problem captures one of the main technical challenges of designing DP methods, namely handling high-dimensional data. \n\nThe authors introduce a carefully constructed algorithm that applies the private interior point algorithm on each dimension, but at each step prunes some points in the dataset so that they are not used in future steps. Intuitively, this approach allows them to overcome the expensive advanced composition since not too many points will be reused. [and as a consequence, the resulting method has only linear dependence on $d$]", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This is an important and fundamental result in private PAC learning. The proof technique that the authors develop is interesting and will be of interest to the general DP community. The authors do a good job in explaining why extended existing solutions for the 1-dimensional case to d-dimensions introduces looseness in the sample complexity bounds. The introduction of the paper is well written. Beyond the introduction, the writing seems to be a bit rushed and that there is a lot of room for improvement in the presentation. Some places where the paper can use some improvement/clarification are highlighted in below (SUBMISSION refers to the line number in the main file, while SUPPLEMENT refers to the line number in the supplementary material)\n\n\nLine 260-262 (SUBMISSION): In definition 2.3, I believe it would be helpful to explicitly say that “it holds for any $n \\geq m$ that:” instead of “it holds that:” since the variable $n$ used in the probability statement at the end of the definition has not been introduced.\n\nLine 286-289 (SUBMISSION): It will be helpful to explain what $\\Delta$ is in the statement. The authors can perhaps modify the statement to say something like “Let IP be an algorithm for solving the interior point problem with sample complexity $\\Delta$.” Also, in this theorem and in many other Lemma statements, the bounds on some parameters like $\\alpha,\\beta, \\varepsilon$ etc are not explicitly stated.\n\nComments regarding proof of privacy (Lemma 3.4):\n\nLine 310-313 (SUBMISSION): The authors claim that the first part of the algorithm in the inner loop right before the interior point algorithm is used satisfies $(\\varepsilon,0)$-DP, and claim that the inner loop “can be seen as a composition of a Laplace mechanism (represented by the addition of Laplace noise) and the given mechanism $\\mathcal{A}$.” It is not immediately clear why this can be viewed as a Laplace mechanism and furthermore, it is not clear how the choice of the scale parameter for the Laplace noise guarantees $(\\varepsilon,0)$-DP. The authors should clarify this, as it is key to the correctness of the proof.\n\nLine 359-361 (SUPPLEMENT): Going from the inequality on line 359 to the inequality on line 361 is not immediately obvious to me, even after plugging in the value for z and trying to get the same upper bound as in the equation on line 361.\n\nLine 333 (SUPPLEMENT): (minor question) the authors prove the bound $Pr\\left[\\ln\\left(\\frac{\\mathcal{RM}(S)=p}{\\mathcal{RM}(S’)=p}\\right)\\cdot \\mathbb{I}_{p\\in G} \\geq \\widetilde{\\varepsilon}\\right] \\leq 2\\delta$, however I think the upper bound can be $\\delta$ without the factor of 2?\n\nComments regarding proof of accuracy (Lemma 3.5):\n\n1. This proof is relatively straightforward to follow, however I have a few concerns. I don’t see anywhere (neither in the proofs nor in the pseudocode) that explicitly states that the inputs to the algorithm are the positive points in the dataset. I assumed that this is the case since this is what makes the proof make sense to me and this was mentioned very briefly (and informally) in the introduction where the authors stated on Line 91-92 (SUBMISSION): “For simplicity, we assume that $S$ contains “enough” positive elements, as otherwise we could simply return the all-zero hypothesis.”. This statement was not made formal in the paper and I think it is important to explain why it is OK to make this assumption.\n2. When analyzing the probability that the empirical error is large, the authors used a union bound on each dimension. So, shouldn’t the term $6d\\Delta\\log(1/\\beta)\\log(1/\\delta)$ be $6d\\Delta\\log(2d/\\beta)\\log(1/\\delta)$ to ensure the empirical error is low with probability at least $1-\\beta/2$ ?\n3. Why did the authors choose $\\mu = 4\\Delta\\log^2(1/\\delta)$ instead of $\\mu = 4\\Delta\\log(1/\\delta)\\log(1/\\beta)$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives a differentially private algorithm for learning axis-aligned rectangles with a sample complexity that is linear in the underlying dimension improving the bound by a factor of \sqrt{d} on prior works. This is accomplished via a neat trick that might find further applications in the design of private learning algorithms. The reviewers thought that the writing was rushed and at times sloppy but the contributions were interesting and substantial. We recommend acceptance. 
Decision: Accept (Poster)