On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
Year: 2022

Abstract:
We revisit the fundamental problem of learning Axis-Aligned-Rectangles over a finite grid X ⊆ R with differential privacy. Existing results show that the sample complexity of this problem is at most min { d· log |X| , d· (log∗ |X|) } . 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 Õ ( d· (log∗ |X|) ) , 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.

text: { d· log |X| , d1.5· (log∗ |X|)1.5 } . 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 Õ ( d· (log∗ |X|)1.5 ) , 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.

heading: 1 Introduction
text: Differential privacy [Dwork et al., 2006] is a mathematical definition for privacy, that aims to enable statistical analyses of 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 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 (Dwork et al. [2006]). A randomized algorithm A is (ε, δ)-differentially private if for every two databases S, S′ that differ on one row (such databases are called neighboring), and every set of outcomes F , we have Pr[A(S) ∈ F ] ≤ eε · Pr[A(S′) ∈ F ] + δ. The definition is 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 a lot of interest in 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 [Kasiviswanathan et al., 2011, Beimel et al., 2014, 2019b, 2016, 2020, Bun et al., 2015, Feldman and Xiao, 2015, Bun et al., 2019, Beimel et al., 2019a, Kaplan et al., 2019, 2020a, Alon et al., 2020, Kaplan et al., 2020b, Bun et al., 2020, Alon et al., 2019], and much more.
∗Department of Computer Science, Ben-Gurion University of the Negev. sadigurs@post.bgu.ac.il. †Blavatnik School of Computer Science, Tel Aviv University and Google Research. u@uri.co.il.
35th Conference on Neural Information Processing Systems (NeurIPS 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 a significant progress towards understanding this basic question.

heading: 1.1 Existing and New Results
text: Recall that the VC dimension of the class of all axis-aligned rectangles over Rd is O(d), and hence a sample of size O(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 Rd is impossible, even when d = 1 [Feldman and Xiao, 2015, Bun et al., 2015, Alon et al., 2019]. In more detail, let X = {1, 2, . . . , |X|} be a finite (one dimensional) grid, and consider the task of learning axis-aligned rectangles over the finite d-dimensional grid Xd ⊆ Rd. 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 Xd.
For pure-private learning, Feldman and Xiao [2015] showed a lower bound of Ω (d · log |X|) on the sample complexity of this task. This lower bound is tight, as a pure-private learner with sample complexity Θ (d · log |X|) can be obtained using the generic upper bound of Kasiviswanathan et al. [2011]. This should be contrasted with the non-private sample complexity, which is independent of |X|. For approximate-private learning, Beimel et al. [2016] showed that the dependency of the sample complexity in |X| can be significantly reduced. This, however, came at the cost of increasing the dependency in the dimension d. Specifically, the private learner of Beimel et al. [2016] has sample complexity Õ ( d3 · 8log∗ |X| ) . We mention that a dependency on log∗ |X| is known to be necessary [Bun et al., 2015, Alon et al., 2019]. Recently, Beimel et al. [2019a] and Kaplan et al. [2020b] studied the related problem of privately learning halfspaces over a finite grid Xd, and presented algorithms with sample complexity Õ ( d2.5 · 8log∗ |X| ) . Their algorithms can be used to privately
learn axis-aligned rectangles overXd with sample complexity Õ ( d1.5 · 8log∗ |X| ) . 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 Xd with sample complexity Õ ( d1.5 · (log∗ |X|)1.5 ) . 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 Xd gives us two kinds of upper bounds on the sample complexity: Either d · log |X| or d1.5 · (log∗ |X|)1.5. That is, current algorithms either require sample complexity that scales with log |X|, or else it scales super linearly in the dimension d. This naturally leads to the following question.
Question 1.3. Is there a differentially private algorithm for learning axis-aligned rectangles with sample complexity that scales linearly in d and asymptotically smaller than log |X|? 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 Xd with sample complexity Õ ( d · (log∗ |X|)1.5 ) .

heading: 1.2 Baseline Construction using Composition
text: Before we present the technical ideas behind our construction (obtaining sample complexity linear in d), we first elaborate on the algorithm obtaining sample complexity Õ ( d1.5 · (log∗ |X|)1.5 ) , 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. 2015). An algorithm A is said to solve the Interior Point Problem for domain X with failure probability β and sample complexity n, if for every m ≥ n and every database S containing m elements from X it holds that: Pr[min(S) ≤ A(S) ≤ max(S)] ≥ 1− β. That is, given a database S containing (unlabeled) elements from a (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 is 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 to construct the following algorithm B that takes a database S containing labeled elements from Xd. 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 S onto the ith axis.
(b) Let Ai and Bi denote the smallest n and the largest n (projected) points, without their labels.
(c) Let ai ← A(Ai) and bi ← A(Bi). 2. Return the axis-aligned rectangle defined by the intervals [ai, bi] 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 [ai, bi] contains (the projection) of all but at most 2n of the positive examples in the ith axis. Therefore, the rectangle returned in Step 2 contains 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 isO(d), this means that algorithm B is a PAC learner 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 (ε, δ)-differentially private, standard composition theorems for differential privacy require each execution of algorithm A to be done with a privacy parameter of ≈ ε/ √ 2d. This, in turn, would mean that n (the sample complexity of algorithm A) needs to be at least √
2d, which means that algorithm B errs on 2nd ≈ d1.5 input points, which translates to sample complexity of |S| d1.5. The takeaway from this baseline learner is that in order to reduce the sample complexity to 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 on 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 to achieve this, but are useful for the presentation.
Failed Attempt #1. As before, letA denote an 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 a database S containing labeled elements from Xd, where we assume for simplicity that S contains “enough” positive elements.
1. For every axis i ∈ [d]: (a) Project the positive points in S onto the ith axis.
(b) Let Ai and Bi denote the smallest n and the largest n (projected) points, without their labels.
(c) Let ai ← A(Ai) and bi ← A(Bi). (d) Delete from S all points (with their labels) that correspond to Ai and Bi.
2. Return the axis-aligned rectangle defined by the intervals [ai, bi] at the different axes.
The (incorrect) idea here is that by adding Step 1d 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 ε, then the whole construction would satisfy differential privacy with parameter O(ε).
The failure point of this idea is that by deleting one point from the data, we can create a “domino effect” that effects (one by one) many of the sets Ai, Bi throughout the execution. Specifically, consider
two neighboring datasets S and S′ = S ∪ {(x′, y′)} for some labeled point (x′, y′) ∈ Xd × {0, 1}. Suppose that during the execution on S′ it holds that x′ ∈ A1. 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 Ai, Bi is fixed, during the execution on S (without the point x′) it holds that a different point z gets included in A1 instead of x′, and this point z 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 ∈ [d]:
(a) Project the positive points in S onto the ith axis.
(b) Let sizeAi = 2n+ Noise and let sizeBi = 2n+ Noise.
(c) Let Ai and Bi denote the smallest sizeAi and the largest sizeBi (projected) points, respectively, without their labels.
(d) Let ai ← A(Ai) and bi ← A(Bi). (e) Delete from S all points (with their labels) that correspond to Ai and Bi.
2. Return the axis-aligned rectangle defined by the intersection of the intervals [ai, bi] at the different axes.
The idea now is that the noises we add to the sizes of the Ai’s and the Bi’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′ = S ∪ {(x′, y′)}, and let i be the first axis such that x′ ∈ Ai ∪Bi during the execution on S′. Suppose w.l.o.g. that x′ ∈ Bi. Now, the hope is that if during the execution on S we have that the noisy sizeBi is smaller by 1 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 i 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(Bi) 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′ = S ∪ {(x′, y′)}. Let us write Ai, Bi and A′i, B′i to denote these sets during the executions on S and on S′, respectively. Aiming to synchronize the two executions, let us define a mapping π : R2d → R2d from noise vectors during the execution on S′ to noise vectors during the execution on S (determining the values of sizeA1 , sizeB1 , . . . , sizeAd , sizeBd), such that throughout the execution we have that Ai = A′i and Bi = B ′ i for all i except for a single pair, say Bj 6= B′j , of neighboring sets. 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′j or B ′ j , and say that it is included in B ′ j . Then the mapping would be to reduce (by 1) the value of sizeBj (the noisy size of Bj during the execution on S). This would indeed make sure that, conditioned on the noise vectors v′ and v = π(v′), the two executions differ only in a single application of the interior point algorithmA, 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 v and any event F ,
Pr[B(S′) ∈ F |v] ≤ eε · Pr[B(S) ∈ F |π(v)] + δ.
Furthermore, (assuming an appropriate noise distribution) we can make sure that the probability of obtaining the noise vectors v and π(v) 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 a bijection, for any event F we would have that
Pr[B(S′) ∈ F ] = ∑ v Pr[v] · Pr[B(S′) ∈ F |v]
≤ ∑ v eε · Pr[π(v)] · (eε · Pr[B(S) ∈ F |π(v)] + δ)
= ∑ π(v) eε · Pr[π(v)] · (eε · Pr[B(S) ∈ F |π(v)] + δ)
= e2ε · Pr[B(S) ∈ F ] + eε · δ,
which would be great. Unfortunately, the mapping π we defined is 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, 0), as well as 10 copies of the point (1, 0) and 10 copies of the point (0, 1). The neighboring database S′ contains, in addition to all these points, also the point ( 1 2 , 1 2 ) . Now suppose that during the execution on S′ we have that |B′1| = 5 and |B′2| = 4. That is, the additional point is included in B′1. During the execution on S we therefore reduce (by 1) the size of B1 and so |B1| = |B2| = 4. Now suppose that during the execution on S′ we have that |B′1| = 4 and |B′2| = 5. Here, during the execution on S we reduce the size of B2 and so, again, |B1| = |B2| = 4. This shows that the mapping π we defined is not a 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 in d).

heading: 1.3 Our Solution - A Technical Overview
text: We now present a 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.
1. For every axis i ∈ [d]: (a) Project the positive points in S onto the ith axis.
(b) Let sizeAi = 100n+ Noise and let sizeBi = 100n+ Noise, where the standard deviation of these noises is, say, 10n.
(c) Let Ai and Bi denote the smallest sizeAi and the largest sizeBi (projected) points, respectively, without their labels.
(d) Let Ainneri ⊆ Ai be the n largest points in Ai. Similarly, let Binneri ⊆ Bi be the n smallest points in Bi.
(e) Let ai ← A(Ainneri ) and bi ← A(Binneri ). (f) Delete from S all points (with their labels) whose projection onto the ith is not in the interval
[ai, bi].
2. Return the axis-aligned rectangle defined by the intersection of the intervals [ai, bi] at the different axes.
There are two important modifications here. First, we still add noise to the size of the sets Ai, Bi, but we only use the n “inner” points from these sets. Second, we delete elements from S not based on them being inside Ai or Bi, but only based on the (privately computed) interval [ai, bi]. We now elaborate on 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 ∪ {(x′, y′)} be neighboring databases, differing on the labeled point (x′, y′). Consider the execution on S and on S′. The privacy analysis is based on the following two lemmas.
Lemma 1.6 (informal). With probability at least 1 − δ, throughout the execution it holds that x′ participates in at most O(log(1/δ)) sets Ai, Bi.
This lemma holds because of our choice for the noise magnitude. In more detail, given that x′ ∈ Ai, there is a constant probability that x′ ∈ Ai \ Ainneri . Since the interior point ai is computed from
Ainneri , in such a case we will have that x ′ < ai, and hence, x′ is deleted from the data during this iteration. This means that every time x′ is included in Ai, there is 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′ ∈ Ai is bounded (w.h.p.). A similar argument also holds for Bi. Lemma 1.7 (informal). In iterations i in which x′ is not included in Ai or Bi, we have that ai and bi are distributed exactly the same during the execution on S and on S′.
Indeed, in such an iteration, the point x′ has no effect on the outcome distribution ofA (who computes ai, bi). Overall, w.h.p., there are at most O(log 1δ ) 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 a factor of √ d 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 (ε, δ)-differential privacy. In contrast to the case of (ε, 0)-differential privacy, where it suffices to analyze the privacy loss w.r.t. every single possible outcome, with (ε, δ)-differential 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 advanced-composition theorem [Dwork et al., 2010], but instead of composing everything we aim to preform effective composition, meaning that we incurr a privacy loss only on a small fraction of the iterations. To achieve this, as we mentioned, we partition the iterations into several types – iteration on which we “pay” in privacy and iterations on which we do not. However, this partition must be done carefully, as the partition itself is random and needs to be different for different possible outcomes.
We believe that ideas from our work can be used more broadly, and hope that they find new applications 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 target rectangle is placed at the origin. Our results easily extend to arbitrary axis-aligned rectangles.
Notations. Two datasets S, S′ ∈ X are said to be neighboring if they differ exactly on one element, formally, dH(S, S′) = 1. Given a number ` ∈ N and a dataset S containing points from an ordered domain, we use min(S, `) (or max(S, `)) to indicate the subset of ` minimal (or maximal) values within S. When S contains points from a d-dimentional domain, we write mini(S, `) (or maxi(S, `)) to denote the subset of ` minimal (or maximal) values within S w.r.t. the ith axis. We write Lap(µ, b) to denote the Laplase distribution with mean µ 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.

heading: 2 The Algorithm
text: 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, . . . , X}d be a finite discrete d-dimensional domain. Every p = (p1, . . . , pd) ∈ X , induces a classifier hp : X → {0, 1} s.t for a given input x ∈ X we have
hp(x) = { 1, ∀i ∈ [d] : xi ≤ pi 0, otherwise
Define the class of all axis-aligned and origin-placed rectangles as RECXd = {hp : p ∈ X}. Let A be an (ε, δ)-differentially private algorithm for solving the interior point problem over domain {0, . . . , X} with failure probability β and sample complexity IPA (ε, δ, β). We propose Algorithm 1, which we call RandMargins, and prove the following theorem.
Theorem 2.2. Let ε < 1, δ < 1e2 , α, β. Algorithm 1 is (α, β, ε̃, δ̃)-PPAC learner, for the RECd class, given a labeled sample of size O ( IPA (ε, δ, β) · dα log ( 1 α ) log ( 1 β )) , for δ̃ = (d+ 2)δ, and ε̃ = O (ε log(1/δ)) . 3Note 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 a 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 Input: Data S ⊆ Rd of size n, and parameters β < 14 and δ < 1/e
2, ε Tool used: An (ε, δ)-private algorithm A for solving the interior point problem with failure probability β and sample complexity IPA (ε, δ, β).
Denote ∆ = IPA (ε, δ, β) Denote µ = 4∆ log(1/β) Initialize S̄ ← {x ∈ S | x is labeled 1} for i = 1 to d do wi ∼ Lap(2∆) 3 Bi = maxi(S̄, dµ+ wie) Di = mini(Bi,∆) pi ← A (Di, ε, δ, β) Ri = {y ∈ S̄ : y[i] ≥ pi} S̄ ← S̄ \Ri end for Return (p1, . . . , pd)
Remark 2.3. Kaplan et al. [2020a] introduced an algorithm A for the interior point problem with sample complexity IPA (ε, δ, β) = Õ ( 1 ε log 1.5 ( 1 δ ) (log∗ (|X|))1.5 ) . Hence, using their algorithm within Algorithm 1 provides the result of Theorem 1.4.
We analyze the privacy guarantees of Algorithm 1 in Section 3, and show the following lemma. Lemma 2.4. Let ε and δ < 1e2 , given a labeled sample of size O ( IPA (ε, δ, β) · dα log ( 1 α ) log ( 1 β )) , Algorithm 1 is (ε̃, δ̃)-differentially private, for δ̃ = (d+ 2)δ, and ε̃ = O (ε log(1/δ)) . We analyze the utility guarantees of Algorithm 1 in Section 4, and show the following lemma.
Lemma 2.5. Let α, β, ε, δ, given a labeled sample of size O ( IPA (ε, δ, β) · dα log ( 1 α ) log ( 1 β )) with probability at least 1− β Algorithm 1 is α-accurate.

heading: 3 Privacy Analysis
text: Proof of Lemma 2.4. Let S and S′ = S ∪ {(x′, y′)} be neighboring databases, differing on the labeled point (x′, y′). Consider the execution on S and on S′.
We denote by indi(x) the position of the point x in the remaining data S̄, when the data is sorted by the ith coordinate.
Denote by i∗ the first iteration on which x′[i] > pi, note that i∗ is a random variable. For an input set S, denote by S̄i the remaining set at the beginning of the ith iteration and its size by n̄.
Partition the iterations in the following way: Iin = {i ≤ i∗ | x′ ∈ B′i}, Iout = {i < i∗ | x′ /∈ B′i}, Iafter = {i | i > i∗}. We first argue that |Iin| is small (with high probability). Intuitively, this follows from the fact that conditioned on x′ ∈ B′i, with constant probability, we get that x′ ∈ B′i \ Di. Note that in such a case, projecting on the ith axis, x′ is bigger (or equal) than any point in Di. Furthermore, as the interior point pi is computed from Di, w.h.p. we get that x′[i] ≥ pi, and hence x′ is removed from the data. To summarize, conditioned on x′ ∈ B′i there is a constant probability that x′ is removed from the data, and hence the number of times such that x′ ∈ B′i 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[|Iin| > 35 log(1/δ)] ≤ δ.
Next, we will denote by B the inner steps of the loop in the algorithm. Meaning, the input is S̄i, which B uses, along with the random noise and the mechanism A, in order to output pi. We now argue,
briefly, that B is (ε, δ)-differentially private for every fixture of wi. This, in particular, would mean that B is (ε, δ)-differentially private. So fix wi, and fix two neighboring inputs S̄i, S̄′i to algorithm B. Since S̄i, S̄′i are neighboring, we also have that Bi and B ′ i are neighboring (the sets containing the top µ+wi elements in S̄i and S̄′i, respectively). By the same reasoning, we also have that Di and D ′ i are neighboring. As a result, the outcome distributions of the given mechanism A, on Di and on D′i are (ε, δ)-indistinguishable, showing that B is (ε, δ)-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 = (w1, . . . , wd). As will be proven below, algorithm RandMargins remains differentially private even when releasing this noise vector (in addition to the output (p1, . . . , pd)).
Lemma 3.2 (Vadhan [2017]). For every (ε, δ)-private algorithm M and every two neighboring datasets S, S′, there exist an event G = G(M,S, S′) such that (i) Pr[M(S) ∈ G] > 1− δ, and (ii) Pr[M(S′) ∈ G] > 1− δ, and (iii) ∀x ∈ G : ∣∣∣ln( Pr(M(S)=x)Pr(M(S′)=x))∣∣∣ ≤ ε. Define the event G = {(p, w) | ∀j ∈ [d] : (pj , wj) ∈ G(B, S̄j , S̄′j)}, where G(B, S̄j , S̄′j) is the event guaranteed to exist by applying Lemma 3.2 to B, S̄j , S̄′j .
Note that by Lemma 3.2 and the union bound Pr[G] ≥ 1− dδ. We wish to prove that for any possible output set P , it holds that
Pr[RandMargins(S) ∈ P ] ≤ eε̃ · Pr[RandMargins(S′) ∈ P ] + δ̃.
Define the set
R = { (p, w) ∣∣∣∣ln( Pr[RM(S) = (p, w)]Pr[RM(S′) = (p, w)] ) > ε̃ } ,
whereRM is an abbreviation for RandMargins. Now note that for every event P ,
Pr[RM(S) ∈ P ] ≤ Pr[RM(S) ∈ R] + Pr[RM(S) ∈ P \R] ≤ Pr[RM(S) ∈ R] + eε̃ Pr[RM(S′) ∈ P \R] ≤ Pr[RM(S) ∈ R|+ eε̃ Pr[RM(S′) ∈ P ]
So it is down to show that Pr[RM(S) ∈ R] ≤ δ̃. That is, we need to prove that
Pr p,w←RM(S)
[ ln ( Pr(RM(S) = p, w) Pr(RM(S′) = p, w) ) > ε̃ ] ≤ δ̃.
We calculate,
Pr p,w←RM(S)
[ ln ( Pr(RM(S) = p, w) Pr(RM(S′) = p, w) ) > ε̃ ] =
Pr [( ln ( Pr(RM(S) = p, w) Pr(RM(S′) = p, w) ) · 1p,w∈G > ε̃ ) OR ( ln ( Pr(RM(S) = p, w) Pr(RM(S′) = p, w) ) · 1p,w 6∈G > ε̃ )] ≤ Pr p,w←RM(S) [ ln ( Pr(RM(S) = p, w) Pr(RM(S′) = p, w) ) · 1p,w∈G > ε̃
] + Pr p,w←RM(S) [ ln ( Pr(RM(S) = p, w) Pr(RM(S′) = p, w) ) · 1p,w 6∈G > ε̃
] ≤ Pr p,w←RM(S) [ ln ( Pr(RM(S) = p, w) Pr(RM(S′) = p, w) ) · 1p,w∈G > ε̃ ] + (1− Pr[G])
≤ Pr p,w←RM(S)
[ ln ( Pr(RM(S) = p, w) Pr(RM(S′) = p, w) ) · 1p,w∈G > ε̃ ] + dδ.
It remains to prove that Prp,w←RM(S) [ ln ( Pr(RM(S)=p,w) Pr(RM(S′)=p,w) ) · 1p,w∈G > ε̃ ] ≤ δ. We calculate,
Pr p,w←RM(S)
[ ln ( Pr(RM(S) = p, w) Pr(RM(S′) = p, w) ) · 1p∈G > ε̃ ] = Pr p,w←RM(S) [ ln ( d∏ i=1 Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi | p<i, w<i) ) · 1p,w∈G > ε̃ ]
= Pr p,w←RM(S) [ d∑ i=1 ln ( Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi |= p<i, w<i) ) · 1p,w∈G > ε̃ ]
≤ Pr p,w←RM(S) [ d∑ i=1 ( ln ( Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi | p<i, w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) ) > ε̃ ]
= Pr p,w←RM(S) [ ∑ i∈Iin ( ln ( Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi | p<i, w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) ) + ∑ i∈Iout ( ln ( Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi | p<i, w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) )
+ ∑
i∈Iafter
( ln ( Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi | p<i, w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) ) > ε̃ ] .4
(1)
We will prove the following (i) Pr [∑ i∈Iafter ln ( Pr(RM(S)i=pi,wi|p<i,w<i) Pr(RM(S′)i=pi,wi|p<i,w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) = 0 ] = 1
(ii) Pr [∑ i∈Iout ln ( Pr(RM(S)i=pi,wi|p<i,w<i) Pr(RM(S′)i=pi,wi|p<i,w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) = 0 ] = 1
(iii) Pr [∑ i∈Iin ln ( Pr(RM(S)i=pi,wi|p<i,w<i) Pr(RM(S′)i=pi,wi|p<i,w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) ≤ ε̃ ] ≥ 1− δ
Combining the above three claims implies a bound on (1) and finishes the proof.
Proof of (i). After i∗, by the algorithm definition, x′ gets removed from S′. Hence, for every i > i∗, conditioning onRM(S)<i = p<i, it holds that B′i = Bi. This implies that, for every i ∈ Iafter,
Pr(RM(S)i = pi, wi | p<i, w<i) = Pr(RM(S′)i = pi, wi | p<i, w<i)
which yields
Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi | p<i, w<i) = 1
⇒ Pr  ∑ i∈Iafter ln ( Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi | p<i, w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) = 0  = 1 Proof of (ii). Recall that by the definition of Iout for every i ∈ Iout it holds that x′ /∈ B′i, and hence, conditioning on the previous outputs, B′i = Bi. We therefore get that the distribution of the i
th output is also the same. Formally,
Pr(RM(S)i = pi, wi | p<i, w<i) = Pr(RM(S′)i = pi, wi | p<i, w<i). 4Note that the outer probability is over p and w. This allows the partition of the iterations into
Iin, Iout, Iafter to be well-defined, as this partition depends on p, w.
This results in
ln ( Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi | p<i, w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) = 0
⇒ Pr [ ∑ i∈Iout ln ( Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi | p<i, w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) = 0 ] = 1.
Proof of (iii). Note that, as we assume that the output ofRM includes the random Laplasian noise, then by fixing the past output-point p<i, w<i we also fix S̄i, S̄′i. So,
ln ( Pr(RM(S)i = pi, wi | p<i, w<i) Pr(RM(S′)i = pi, wi | p<i, w<i) ) · 1pi,wi∈Gi(B,S̄i,S̄′i)
= ln ( Pr(B(S̄i) = pi, wi) Pr(B(S̄′i) = pi, wi) ) · 1pi,wi∈Gi(B,S̄i,S̄′i).
Moreover, by the definition of the events Gi it holds that
Pr [∣∣∣∣ln(Pr(B(S̄i) = pi, wi)Pr(B(S̄′i) = pi, wi) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) ∣∣∣∣ ≤ 2ε] = 1. which yields
Pr [∑ i∈Iin ln ( Pr(B(S̄i) = pi, wi) Pr(B(S̄′i) = pi, wi) ) · 1pi,wi∈Gi(B,S̄i,S̄′i) > ε̃ ]
≤ Pr [∑ i∈Iin 2ε > ε̃ ] ≤ Pr [ |Iin| > ε̃ 2ε ] ≤ δ,
where the last inequality follows from Claim 3.1 and from our choice of ε̃ = O (ε log(1/δ)) .

heading: 4 Utility
text: Proof of Lemma 2.5. First, we must ensure that at every iteration, with high probability, we have enough points left in S̄. At the same time we must ensure that the axillary algorithm A will output an inner point of the given subset. Denote aj = wj + µ. By the definition of the noise w and the mean µ, we get that for every iteration i: Pr[ai > 6∆ log(1/β)] < β. Hence, with probability ≥ 1− dβ, it holds that for every i ai ≤ 6∆ log(1/β). This means that the total number of removed point is at most 6d∆ log(1/β). Therefore, for a sample of size 6d∆ log(1/β) with high probability S̄ will contain enough points.
Regarding the algorithm’s accuracy, we notice that at every iteration j, A outputs a point which is at least the aj-th largest point from the points left in the set. This means that, in the worst case, we delete aj points from the data set at this iteration. Hence, again in worst case, we will output the∑i j=1 aj-th largest point in the j th axis.
By the above reasoning, with high probability we can say that for every i it holds that aj ≤ 6∆ log(1/β). Meaning that every pj is at least the ∑d j=1 aj ≤ 6d∆ log(1/β) largest point in the axis.
This implies that, for sample of size O ( d∆ α log(1/α) log(1/β) ) , denoting the by hp the hypothesis induces by the output of Algorithm 1 PrS∼Pn [errS(hp) ≥ α/2] ≤ β/2. Since the VC-dimension of the class RECd is 2d, by the VC-theory bounds and the fact that the sample size is at least as the sample complexity bound O ( 1 α ( d log ( 1 α ) + log ( 1 β ))) it holds that: PrS∼Pn [errP(hp) ≥ errS(hp) + α/2] ≤ β/2. Combining the two bounds concludes the proof.

heading: Acknowledgments
text: 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.

Review summaries:
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.   The 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$]

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