On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians

Introduction

Given samples from a distribution $P$, can we estimate the underlying distribution? This problem has a long and rich history, culminating in a mature understanding for many settings of interest. However, in many cases the dataset may consist of sensitive data belonging to individuals, and naive execution of classic methods may inadvertently result in private information leakage. See, for instance, privacy attacks described in such estimation settings including [DN03, HSR+08, BUV14, DSS+15, SSSS17], and the survey [DSSU17].

To address concerns of this nature, in 2006, Dwork, McSherry, Nissim, and Smith introduced the celebrated notion of differential privacy (DP) [DMNS06], which provides a strong standard for data privacy. It ensures that no single data point has significant influence on the output of the algorithm, thus masking the contribution of individuals in the dataset. Differential privacy has seen practical adoption in many organizations, including Apple [Dif17], Google [EPK14, BEM+17], Microsoft [DKY17], and the US Census Bureau [DLS+17]. At this point, there is a rich body of literature, giving differentially private algorithms for a wide array of tasks.

There has recently been significant interest in distribution and parameter estimation under differential privacy (see Section 1.1.2 for discussion of related work). Most relevant to our investigation is the work of Bun, Kamath, Steinke, and Wu [BKSW19], which provides a generic framework that, given a cover for a class of distributions, describes a private algorithm for learning said class with sample complexity logarithmic in the size of the cover. There, the privacy guarantee is the strongest notion of pure $(\varepsilon,0)$-differential privacy.

An obvious drawback of this approach is that it fails to provide sample complexity upper bounds for estimating classes of distributions which do not possess a finite cover. The canonical example is the set of all Gaussian distributions. It turns out that this is inherently impossible – “packing lower bounds” imply that no finite sample algorithm exists for such cases under pure differential privacy. This theoretical limitation can have significant practical implications as well, as it forces the data analyst to choose between having good accuracy and preserving privacy. It turns out that, under pure differential privacy, the only way to avoid this issue is to assume the underlying distribution belongs to a more restricted class – such as Gaussian distributions with bounded mean and covariance.

On the other hand, stronger results are possible if one relaxes the privacy notion to the weaker guarantee of approximate differential privacy [DKM+06]. In particular, it is known that this relaxation permits “stability-based” approaches, which can avoid issues associated with infinite covers by pinpointing the area where “a lot of the data lies,” see, e.g., the classic example of the stability-based histogram [KKMN09, BNS16].

We resolve these issues by providing a simpler method for proving existence of locally small covers. These lead to our main results, sample complexity upper bounds for semi-agnostically learning Gaussian distributions under approximate differential privacy.

The sample complexity of semi-agnostically learning a $d$-dimensional Gaussian distribution to $\alpha$-accuracy in total variation distance under $(\varepsilon,\delta)$-differential privacy is

This is the first sample complexity bound for privately learning a multivariate Gaussian with no conditions on the covariance matrix. The first and third terms are known to be tight, and there is strong evidence that the second is as well, see Section 1.1.1. The previous best algorithm was that of [KLSU19], which provided the stronger guarantee of concentrated differential privacy [DR16, BS16] (which is intermediate to pure and approximate DP). However, it required the true covariance $\Sigma$ to be bounded as $I\preceq\Sigma\preceq KI$ for some known parameter $K$, and the third term in the sample complexity is instead $O\left(\frac{d^{3/2}\log^{1/2}K}{\varepsilon}\right)$, which is prohibitive for large (or unknown) $K$. In contrast, our result holds for unrestricted Gaussian distributions.

We also provide a better upper bound for the case when the covariance matrix is known.

The sample complexity of semi-agnostically learning a $d$-dimensional Gaussian distribution with known covariance to $\alpha$-accuracy in total variation distance under $(\varepsilon,\delta)$-differential privacy is

This is the first bound which achieves a near-optimal dependence simultaneously on all parameters, see Section 1.1.1. In particular, it improves upon previous results in which the third term is replaced by $O\left(\frac{\log(1/\delta)}{\alpha\varepsilon}\right)$ [BKSW19] or $O\left(\frac{\sqrt{d}\log^{3/2}(1/\delta)}{\varepsilon}\right)$ [KV18, KLSU19, BKSW19].

While we apply our approach to multivariate Gaussian estimation, it should more broadly apply to other classes of distributions with no finite-sized cover.

As mentioned before, we build upon the approach of Bun, Kamath, Steinke, and Wu [BKSW19] to provide methods better suited for estimation under the constraint of approximate differential privacy. Their work focuses primarily on pure DP distribution estimation for classes of distributions with a finite cover. Specifically, given a class of distributions with an $\alpha$-cover of size $\mathcal{C_{\alpha}}$, they give a pure DP algorithm for learning said class in total variation distance with sample complexity $O(\log|\mathcal{C_{\alpha}}|)$. Naturally, this gives vacuous bounds for classes with an infinite cover – indeed, packing lower bounds show that this is inherent under pure DP [HT10, BBKN14, BKSW19]. To avoid these lower bounds, they show that learning is still possible if one relaxes to approximate DP and considers a “locally small” cover: one that has at most $k$ elements which are within an $O(\alpha)$-total variation distance ball of any element in the set. The sample complexity of the resulting method does not depend on $|\mathcal{C}_{\alpha}|$, and instead we pay logarithmically in the parameter $k$. They apply this framework to provide algorithms for estimating general univariate Gaussians, and multivariate Gaussians with identity covariance. However, their arguments construct explicit covers for these cases, and it appears difficult to construct and analyze covers in situations with a rich geometric structure, such as multivariate Gaussians. Indeed, it seems difficult in these settings to reason that a set is simultaneously a cover (i.e., every distribution in the class has a close element) and locally small (i.e., every distribution does not have too many close elements).

We avoid this tension by taking a myopic view: in Lemma 3.1, we show that if we can construct a cover with few elements for the neighbourhood of each individual distribution, then there exists a locally small cover for the entire space. This makes it significantly easier to reason about locally small covers, as we only have to consider covering a single distribution at a time, and we do not have to reason about how the elements that cover each distribution overlap with each other. For example: to cover the neighbourhood of a single Gaussian with (full rank) covariance $\Sigma$, we can transform the covariance to the identity by multiplying by $\Sigma^{-1/2}$, cover the neighbourhood of $N(0,I)$ (which is easier), and transform the cover back to the original domain. This is far simpler than trying to understand how to simultaneously cover multiple Gaussians with differently shaped covariance matrices in a locally small manner. Our results for covering are presented in Section 3.

We then go on to apply these locally small covers to derive learning sample complexity upper bounds in Section 4. As mentioned before, this is done in [BKSW19], though we refine their method to achieve stronger bounds. While this refinement is simple, we believe it to be important both technically (as it allows us to achieve likely near-optimal sample complexities) and conceptually (as we believe it clearly identifies what the “hard part” of the problem is). To elaborate, our approach can be divided into two steps;

Coarse Estimation. Find any distribution which is $0.99$-close to the true distribution, using the approximate DP GAP-MAX algorithm in [BKSW19].

Fine Estimation. Generate an $O(\alpha)$-cover around the distribution from the previous step, and run the pure DP private hypothesis selection algorithm in [BKSW19].

We are not the first to use this type of two-step approach, as such decomposition has been previously applied, e.g., [KV18, KLSU19, KSU20]. However, it was not applied in the context of the GAP-MAX algorithm in [BKSW19], preventing them from getting the right dependencies on all parameters – in particular, it was not clear how to disentangle the dependencies on $\log(1/\delta)$ and $1/\alpha$ using their method directly.

Other beneficial features of this two-step approach, which have also been exploited in the past, include its modularity and the fact that the first and second steps involve qualitatively different privacy guarantees. However, we additionally comment how coarse an estimate required in the first step – while the description above states that we require a $0.99$-close distribution, we may actually only need one with total variation distance bounded by $1-\zeta$, where $\zeta$ may be exponentially small in the parameters of the problem! See Remark 4.1. We hope that shining a light on this somewhat unconventional regime for private distribution estimation, which only requires a “whiff” of the true distribution, will inspire further investigation.

As a final contribution, in Section 5, we revisit the generic private hypothesis selection problem. The main result of [BKSW19] is an algorithm for this problem which requires knowledge of the distance to the best hypothesis. They then wrap this algorithm in another procedure which “guesses” the distance to the best hypothesis, resulting in a semi-agnostic algorithm. However, this loses large factors in the agnostic guarantee and is rather indirect. We instead analyze the privatization of a different algorithm, the minimum distance estimate, which gives a semi-agnostic algorithm directly, with an optimal agnostic constant (i.e., providing a tight factor of 3 [DL01]). In our opinion, the algorithm and proof are even simpler than the non-agnostic algorithm of [BKSW19].

It is folklore that the non-private sample complexity of estimating a single $d$-dimensional Gaussian to accuracy $\alpha$ in total variation distance is $\Theta(d^{2}/\alpha^{2})$, or, in the case when the covariance is the identity, $\Theta(d/\alpha^{2})$. Therefore the leading terms in the sample complexity bounds of Theorems 1.1 and 1.2 are tight.

Lower bounds for private statistical estimation are comparatively less explored. Karwa and Vadhan [KV18] showed a lower bound of $\Omega(\log(1/\delta)/\varepsilon)$, even for the simple case of estimating the mean of a univariate Gaussian with known variance, thus matching the third terms in Theorems 1.1 and 1.2.

[KLSU19] also proves a lower bound of $\Omega(d^{2}/\alpha\varepsilon)$ for general Gaussian estimation under pure differential privacy. Using the aforementioned invariance of the complexity of estimation with identity covariance under pure and approximate DP, we take this as strong evidence that there exists a lower bound of $\Omega(d^{2}/\alpha\varepsilon)$ for estimation of general Gaussians under approximate DP as well.

1.2 Additional Related Work

The work of Bun, Kamath, Steinke, and Wu [BKSW19] is built upon classic results in hypothesis selection, combined with the exponential mechanism [MT07]. The underlying non-private approach was pioneered by Yatracos [Yat85], and refined in subsequent work by Devroye and Lugosi [DL96, DL97, DL01]. After this, additional considerations have been taken into account, such as computation, approximation factor, robustness, and more [MS08, DDS12, DK14, SOAJ14, AJOS14, DKK+16, ABDM18, ABDH+18, AFJ+18, BKM19, AAA20]. Notably, these primitives have also been translated to the more restrictive setting of local differential privacy [GKK+20]. Similar techniques have also been exploited in a federated setting [LSY+20].

Preliminaries

2 Distribution Learning

A distribution learning method is an algorithm that, given a sequence of i.i.d. samples from a distribution $P$, outputs a distribution $\widehat{H}$ as an estimate of $P$. The focus of this paper is on absolutely continuous probability distributions (distributions that have a density with respect to the Lebesgue measure), so we will refer to a probability distribution and its probability density function interchangeably. The specific measure of “closeness” between distributions that we use is the total variation distance:

Let $P$ and $Q$ be two probability distributions defined over $\mathcal{X}$ and let $\Omega$ be the Borel sigma-algebra on $\mathcal{X}$. The total variation distance between $P$ and $Q$ is defined as

Moreover, if $\mathcal{H}$ is a set of distributions over a common domain, we define $\TV(P,\mathcal{H})=\inf_{H\in\mathcal{H}}\TV(P,H)$.

Given $X\sim P$ and $Y\sim Q$, it is often useful for us to overload notation and define $\TV(X,Y)=\TV(P,Q)$. We say two distributions $P$ and $H$ are $\gamma$-close if $\TV(P,H)\leq\gamma$. We also say a distribution $P$ is $\gamma$-close to a set of distributions $\mathcal{H}$ if $\min_{H\in\mathcal{H}}\TV(P,H)\leq\gamma$. We can now formally define a distribution learner:

An algorithm is said to be a (realizable) PAC learner for a set of distributions $\mathcal{H}$ with sample complexity $n_{\mathcal{H}}(\alpha,\beta)$ if given parameters $\alpha,\beta\in(0,1)$ and any $P\in\mathcal{H}$, the algorithm takes as input $\alpha,\beta$ and a sequence of $n_{\mathcal{H}}(\alpha,\beta)$ i.i.d. samples from $P$, and outputs $\widehat{H}\in\mathcal{H}$ such that $\TV(P,\widehat{H})\leq\alpha$ with probability at least $1-\beta$. The probability is over the random samples drawn from $P^{n}$ and the randomness of the algorithm.

The following two definitions handle the case when we have model misspecification: we receive samples from a distribution $P$ which is not in the class $\mathcal{H}$. The difference between the two is that in the robust definition (Definition 2.4) the algorithm is provided with an upper bound on the distance between $P$ and $\mathcal{H}$, while it is not in the agnostic setting (Definition 2.5).

We will sometimes refer to a $C$-agnostic PAC learner as a semi-agnostic PAC learner for $C>1$, as is standard in learning theory. A useful object for us to define is the total variation ball.

The total variation ball of radius $\gamma\in$, centered at a distribution $P$ with respect to a set of distributions $\mathcal{H}$, is the following subset of $\mathcal{H}$:

In this paper we consider coverings and packings of sets of distributions with respect to the total variation distance.

For any $\gamma\in$ a $\gamma$-cover of a set of distributions $\mathcal{H}$ is a set of distributions $\mathcal{C}_{\gamma}$, such that for every $H\in\mathcal{H}$, there exists some $P\in\mathcal{C}_{\gamma}$ such that $\TV(P,H)\leq\gamma$.

A $\gamma$-packing of a set of distributions $\mathcal{H}$ is a set of distributions $\mathcal{P}_{\gamma}\subseteq\mathcal{H}$, such that for every pair of distributions $P,Q\in\mathcal{P}_{\gamma}$, we have that $\TV(P,Q)\geq\gamma$.

The following is a well known relation between covers and packings of a set of distribution. We defer the proof to Section B.1.

For a set of distributions $\mathcal{H}$ with $\gamma$-covering number $M(\mathcal{H},\gamma)$ and $\gamma$-packing number $N(\mathcal{H},\gamma)$, the following holds:

An important property of a set of distributions we will need to quantify in this paper is how small they are “locally”. The following definition formalizes this:

Fix some $\gamma\in$. We say a set of distributions $\mathcal{H}$ is $(k,\gamma)$-locally small if

3 VC Dimension and Uniform Convergence

An important property of a set of binary functions is its Vapnik-Chervonenkis (VC) dimension, which has the following definition:

Let $\mathcal{F}$ be a set of binary functions $f:\mathcal{X}\to\{0,1\}$. The VC dimension of $\mathcal{F}$ is defined to be the largest $d$ such that there exist $x_{1},\cdots,x_{d}\in\mathcal{X}$ and $f_{1},\cdots,f_{2^{d}}\in\mathcal{F}$ such that for all $i,j\in[2^{d}]$ where $i<j$, there exists $k\in[d]$ such that $f_{i}(x_{k})\neq f_{j}(x_{k})$.

The most important application of the VC dimension is the following celebrated uniform convergence bound:

Let $\mathcal{F}$ be a set of binary functions $f:\mathcal{X}\to\{0,1\}$ with VC dimension $d$. For any distribution $P$ defined on $\mathcal{X}$, we have

whenever $n=O\left(\frac{d+\log(1/\beta)}{\alpha^{2}}\right)$.

We can define the VC dimension of a set of distributions $\mathcal{H}$ by looking at the VC dimension of a set of binary functions that is defined with respect to $\mathcal{H}$. More precisely:

Let $\mathcal{H}$ be a set of probability distributions on a space $\mathcal{X}$. Define the set of binary functions $\mathcal{F}(\mathcal{H})=\{f_{H_{i},H_{j}}:H_{i},H_{j}\in\mathcal{H}\}$ where $\forall x\in\mathcal{X}$, $f_{H_{i},H_{j}}(x)=1\iff H_{i}(x)>H_{j}(x)$. We define the VC dimension of $\mathcal{H}$ to be the VC dimension of $\mathcal{F}(\mathcal{H})$. To avoid measurability issues we assume the preimage of $0$ is measurable for any $f\in\mathcal{F}(\mathcal{H})$.

The set of location Gaussians $\mathcal{G}_{d}^{L}$ has VC dimension $d+1$. Furthermore, the set of Gaussians $\mathcal{G}_{d}$ has VC dimension $O(d^{2})$.

For location Gaussians, $\mathcal{F}(\mathcal{G}_{d}^{L})$ corresponds to linear threshold functions (i.e., half-spaces), which have VC dimension $d+1$. Similarly $\mathcal{F}(\mathcal{G}_{d})$ corresponds to quadratic threshold functions, which have VC dimension ${d+2\choose 2}=O(d^{2})$ [Ant95]. ∎

4 Differential Privacy

Let $X^{*}=\cup_{i=1}^{\infty}X^{i}$ be the set of possible datasets. We say that two datasets $D,D^{\prime}\in X^{*}$ are neighbours if $D$ and $D^{\prime}$ differ by at most one data point. Informally, an algorithm that receives a dataset and outputs a value in $\mathcal{R}$ is differentially private if it outputs similar values on (any) two neighboring datasets. Formally:

A randomized algorithm $T:X^{*}\rightarrow\mathcal{R}$ is $(\varepsilon,\delta)$-differentially private if for all $n\geq 1$, for all neighbouring datasets $D,D^{\prime}\in X^{n}$, and for all measurable subsets $S\subseteq\mathcal{R}$,

If $\delta=0$, we say that $T$ is $\varepsilon$-differentially private.

For any dataset $D$, score function $S$ and privacy parameter $\varepsilon>0$, the exponential mechanism $\mathcal{M}_{E}(D,S,\varepsilon)$ is an $\varepsilon$-differentially private algorithm, and with probability at least $1-\beta$, it selects an outcome $r\in\mathcal{R}$ such that

One of the most useful properties of differentially private algorithms is that they can be composed adaptively while promising a graceful degradation of privacy.

If $M$ is an adaptive composition of differentially private algorithms $M_{1},\dots,M_{T}$, then if $M_{1},\dots,M_{T}$ are $(\varepsilon_{1},\delta_{1}),\dots,(\varepsilon_{T},\delta_{T})$-differentially private then $M$ is $(\sum_{t}\varepsilon_{t},\sum_{t}\delta_{t})$-differentially private.

Another strength of differential privacy is that it is closed under post-processing:

If $M:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ is $(\varepsilon,\delta)$-differentially private, and $P:\mathcal{Y}\rightarrow\mathcal{Z}$ is any randomized function, then the algorithm $P\circ M$ is $(\varepsilon,\delta)$-differentially private.

We now define $(\varepsilon,\delta)$-DP learners.

An algorithm is said to be an $(\varepsilon,\delta)$-DP PAC learner for a set of distributions $\mathcal{H}$ with sample complexity $n_{\mathcal{H}}(\alpha,\beta,\varepsilon,\delta)$ if it is a PAC learner that satisfies $(\varepsilon,\delta)$-differential privacy.

An algorithm is said to be an $(\varepsilon,\delta)$-DP $C$-agnostic PAC learner for a set of distributions $\mathcal{H}$ with sample complexity $n_{\mathcal{H}}^{C}(\alpha,\beta,\varepsilon,\delta)$ if it is a $C$-agnostic PAC learner that satisfies $(\varepsilon,\delta)$-differential privacy.

The problem of hypothesis selection (sometimes called density estimation, the Le Cam-Birgé method, or the Scheffé estimator) is a classical approach for reducing estimation problems to pairwise comparisons. It provides a generic approach for converting a cover for a set of probability distributions into a learning algorithm, see [DL01] for a reference.

[BKSW19] translated these powerful tools to the differentially private setting, giving an $\varepsilon$-DP algorithm for hypothesis selection using the exponential mechanism with a carefully constructed score function. The following is a modified version where we decouple the accuracy parameter $\alpha$ from the robustness parameter $\xi$, and boost the success probability to be arbitrarily high. The proof follows immediately from the proof in [BKSW19]. For a set of distributions $\mathcal{H}$, we will denote $H^{*}$ as the distribution in $\mathcal{H}$ that is closest to the unknown distribution $P$.

Let $\mathcal{H}=\{H_{1},\dots,H_{m}\}$ be a set of probability distributions, $\xi,\alpha,\beta,\varepsilon,\delta\in(0,1)$ and $D\sim P^{n}$ where $P$ satisfies $\TV(P,\mathcal{H})\leq\xi$. $\emph{\text{PHS}}(\xi,\alpha,\beta,\epsilon,\mathcal{H},D)$ is an $\varepsilon$-DP $(\xi,3)$-robust PAC learner with sample complexity

Furthermore, when the algorithm succeeds it guarantees that $\TV(\widehat{H},H^{*})\leq 2\xi+\alpha$.

We note the guarantee that the algorithm gives with respect to $H^{*}$ in the theorem statement for technical reasons that will become apparent in the proofs of Section 4. Unfortunately the result above requires the number of hypotheses to be finite. Using a uniform convergence argument together with a GAP-MAX algorithm [BDRS18], Bun, Kamath, Steinke and Wu [BKSW19] showed that it may also be possible to get a similar guarantee when the number of hypotheses is infinite, provided that we relax the notion of privacy to approximate differential privacy. The following is an alternate version of [BKSW19, Theorem 4.1]. Again, in this version we decouple the accuracy parameter $\alpha$ from the robustness parameter $\xi$. The proof follows directly from the proof of Theorem 4.1 in [BKSW19].

Let $\mathcal{H}$ be a set of probability distributions, $\xi,\alpha,\beta,\varepsilon,\delta\in(0,1)$ and $D\sim P^{n}$ where $P$ satisfies $\TV(P,\mathcal{H})\leq\xi$. Furthermore, let $d$ be the VC dimension of $\mathcal{F}(\mathcal{H})$ and assume $|\mathcal{B}\left(3\xi+\alpha,H^{*},\mathcal{H}\right)|\leq k$. $\emph{\text{GAP-MAX}}(\alpha,\xi,\beta,\epsilon,\delta,k,\mathcal{H},D)$ is an $(\varepsilon,\delta)$-DP $(\xi,4)$-robust PAC learner for $\mathcal{H}$ with sample complexity

Furthermore, when the algorithm succeeds it guarantees that $\TV(\widehat{H},H^{*})\leq 3\xi+\alpha$.

Note that Theorem 2.23 requires knowledge of $|\mathcal{B}\left(3\xi+\alpha,H^{*},\mathcal{H}\right)|$, which we likely do not know a priori. We can bound this by finding an upper bound on the size of the largest total variation ball centered at any $H^{\prime}\in\mathcal{H}$, i.e. $\max_{H^{\prime}\in\mathcal{H}}|\mathcal{B}\left(3\xi+\alpha,H^{\prime},\mathcal{H}\right)|\leq k^{\prime}$. This directly translates to showing $\mathcal{H}$ is $(k^{\prime},3\xi+\alpha)$-locally small.

This lays the foundation for the strategy used in [BKSW19] to construct a private distribution learner for an infinite set of distributions $\mathcal{H}$: by using a $(k^{\prime},6\xi+\alpha)$-locally small Note that the guarantee we can get from any $\xi$-cover $\mathcal{C}_{\alpha}$ is $\TV(H^{*},\mathcal{C}_{\alpha})\leq\xi\implies\TV(P,\mathcal{C}_{\alpha})\leq 2\xi$. $\xi$-cover for $\mathcal{H}$ as the input to the GAP-MAX algorithm, given the right amount of samples (which depends on $k^{\prime}$), with high probability the algorithm outputs a distribution that is $(8\xi+\alpha$)-close to $P$.

which is exponentially worse than the PHS algorithm. As we will discuss shortly, [BKSW19] also show how to use this algorithm together with the PHS algorithm to get a $\varepsilon$-DP $18$-agnostic PAC learner, at the cost of some poly-logarithmic factors. This leads to the natural question of whether there exists an $\varepsilon$-DP semi-agnostic learner which achieves the same sample complexity as the PHS algorithm with a comparable agnostic constant. We answer this question in the affirmative and prove the following result:

We defer discussing the details of this result and its proof to Section 5, however we note that the above result can only handle finite sets of distributions. Recall that while the GAP-MAX algorithm can handle infinite sets of distributions, it is not a semi-agnostic learner. Thus, a natural question is whether we can learn from a set of infinite distributions using some $(\varepsilon,\delta)$-DP semi-agnostic PAC learner.

Fortunately, [BKSW19] gave a simple procedure that takes an $(\varepsilon,\delta)$-DP robust PAC learner and constructs an $(\varepsilon,\delta)$-DP semi-agnostic PAC learner, at the cost of some low order poly-logarithmic factors in the sample complexity bounds, and an increase in the agnostic constant. We can thus use the GAP-MAX algorithm together with this procedure to get an $(\varepsilon,\delta)$-DP semi-agnostic PAC leaner given an infinite set of distributions. The procedure [BKSW19] came up with works in the following way: run the $(\varepsilon,\delta)$-DP robust PAC learner with (a small number of) different values for $\xi$ to get a shortlist of candidates. Use the semi-agnostic NaïvePHS algorithm to select a good hypothesis from the short list. As we mentioned earlier, the guarantee of this approach (Theorem 3.4 in [BKSW19]) is stated specifically in terms of converting the PHS algorithm from Theorem 2.22 into an $\varepsilon$-DP semi-agnostic PAC learner, however it can be immediately generalized to construct $(\varepsilon,\delta)$-DP semi-agnostic PAC learners given any $(\varepsilon,\delta)$-DP robust PAC learner. Furthermore, we can replace the Naïve-PHS algorithm with the sample efficient algorithm from Theorem 2.24 to reduce the agnostic constant, and also remove some logarithmic factors in the sample complexity bound. This yields the following result:

Covering Unbounded Distributions

In this section, we demonstrate a simple method to prove that a set of distributions has a locally small cover. As an application, we use this result to show that the set of unbounded location Gaussians and scale Gaussians have locally small covers. We use these two results to give the first sample complexity result for privately learning unbounded high dimensional Gaussians in Section 4.

The biggest roadblock to using Theorem 2.23 is demonstrating the existence of a locally small cover for the set of distributions $\mathcal{H}$. Unfortunately, explicitly constructing a global cover (which is locally small) can be complicated, and may require cumbersome calculations even for “simple” distributions (see, e.g., Lemma 6.13 of [BKSW19]). We offer a conceptually simpler alternative to prove a set of distributions $\mathcal{H}$ has a locally small cover: we demonstrate that if for every $H\in\mathcal{H}$ the total variation ball $\mathcal{B}\left(\gamma,H,\mathcal{H}\right)$ has an $\frac{\xi}{2}$-cover of size no more than $k$, then there exists an $\xi$-cover for $\mathcal{H}$ that is $(k,\gamma)$-locally small.

Given a set of distributions $\mathcal{H}$ and $\xi\in(0,1)$, if for every distribution $H\in\mathcal{H}$ the total variation ball $\mathcal{B}\left(\gamma,H,\mathcal{H}\right)\subseteq\mathcal{H}$ has an $\frac{\xi}{2}$-cover of size no more than $k$, then there exists a $(k,\gamma)$-locally small $\xi$-cover for $\mathcal{H}$.

Fix some $H\in\mathcal{H}$. By assumption, we have that the set of distributions $\mathcal{B}\left(\gamma,H,\mathcal{H}\right)$ has an $\frac{\xi}{2}$-cover of size no more than $k$, which by definition implies that the $\frac{\xi}{2}$-covering number of $\mathcal{B}\left(\gamma,H,\mathcal{H}\right)$ is no more than $k$. By Lemma 2.9, the $\xi$-packing number of $\mathcal{B}\left(\gamma,H,\mathcal{H}\right)$ is also at most $k$.

Now consider an $\xi$-packing $\mathcal{P}_{\xi}$ for the set of distributions $\mathcal{H}$. We claim any such $\mathcal{P}_{\xi}$ must be $(k,\gamma)$-locally small, and we prove this by contradiction. Suppose to the contrary that there were a distribution $H^{\prime}\in\mathcal{P}_{\xi}$ such that $\left|\mathcal{B}\left(\gamma,H^{\prime},\mathcal{P}_{\xi}\right)\right|>k$. This would imply that there is an $\xi$-packing for $\mathcal{B}\left(\gamma,H^{\prime},\mathcal{H}\right)$ with size larger than $k$, which contradicts the above observation that the packing number of any $\mathcal{B}\left(\gamma,H^{\prime},\mathcal{H}\right)$ is at most $k$.

A $\xi$-packing for $\mathcal{H}$ is called maximal if it is impossible to add a new element of $\mathcal{H}$ to it without violating the $\xi$-packing property. We claim that any maximal packing $\mathcal{P}^{\prime}_{\xi}$ of $\mathcal{H}$ is also a $\xi$-cover of $\mathcal{H}$. We can prove this by contradiction. Suppose to the contrary that there were a distribution $P\in\mathcal{H}$ with $\TV(P,\mathcal{P}^{\prime}_{\xi})>\xi$. Then we could add $P$ to $\mathcal{P}^{\prime}_{\xi}$ to produce a strictly larger packing, contradicting the maximality of $\mathcal{P}^{\prime}_{\xi}$. Thus taking $\mathcal{P}_{\xi}$ to be a maximal packing gives us a $(k,\gamma)$-locally small $\xi$-cover. Therefore, it only remains to show that a maximal packing actually exists, which follows from a simple application of Zorn’s Lemma. Let $M$ be the set of all $\gamma$-packings of $\mathcal{H}$. Define a partial order on $M$ by the relation $\mathcal{P}_{1}\leq\mathcal{P}_{2}\Longleftrightarrow\mathcal{P}_{1}\subseteq\mathcal{P}_{2}$ where $\mathcal{P}_{1},\mathcal{P}_{2}\in M$. We claim that every chain in this partially ordered set has an upper bound in $M$; by Zorn’s lemma, this would imply that $M$ has a maximal element which concludes the proof. To see why every (possibly infinite) chain $\mathcal{P}_{1}\leq\mathcal{P}_{2}\leq\ldots$ has an upper bound in $M$, we consider the following upper bound $U=\cup_{i}\mathcal{P}_{i}$. Note that $U\in M$ since otherwise there would be an index $i$ such that $\mathcal{P}_{i}\notin M$. ∎

2 Locally Small Gaussian Covers

We now prove that both the set of $d$-dimensional location Gaussians and scale Gaussians can be covered in a locally small fashion. Our first result shows that the set of $d$-dimensional location Gaussians $\mathcal{G}^{L}_{d}$ has a locally small cover. Our second result is proving the existence of a locally small cover for the set of $d$-dimensional scale Gaussians $\mathcal{G}^{S}_{d}$.

Fix some $\mathcal{N}(\mu,I)\in\mathcal{G}^{L}_{d}$. From [DMR18, Theorem 1.2] we have

where the first inequality follows from (2). We now bound the size of this cover.

where the third last inequality follows from the standard solution to the stars and bars problem. ∎

Combining Lemma 3.1 with Lemma 3.2 immediately gives us the following corollary:

2.2 Covering Scale Gaussians

It is not a trivial exercise to come up with an explicit cover for the class of scale Gaussians due to the complicated nature of the geometry of $\mathcal{G}_{d}^{S}$. Fortunately for us, Lemma 3.1 simplifies things significantly. It turns out that if we want to cover the TV ball centered at any $\mathcal{N}(0,\Sigma)$, we can use a cover for $\mathcal{N}(0,I)$ and “stretch” the covariance matrices of every distribution in the cover (using $\Sigma$) so that the modified cover becomes a valid cover for the TV ball centered at $\mathcal{N}(0,\Sigma)$. The following lemma tells us that we can cover the total variation ball centered at $\mathcal{N}(0,I)$ with respect to $\mathcal{G}^{S}_{d}$ as long as the radius is not too large.

where $\lambda_{1}\dots\lambda_{d}$ are the eigenvalues of $\Sigma-I$, and it holds that $\sqrt{\sum_{i=1}^{d}\lambda_{i}^{2}}=\|\Sigma-I\|_{F}$.

For any $\gamma$ smaller than the universal constant $c_{2}^{\prime}$ , the lower bound in (3) implies two things: 1) for any $\mathcal{N}(0,\Sigma)\in\mathcal{B}\left(\gamma,\mathcal{N}(0,I),\mathcal{G}^{S}\right)$, $\|\Sigma-I\|_{F}\leq 100\gamma$ and 2) the minimum eigenvalue of $\Sigma$, $\lambda_{\text{min}}$, satisfies $\lambda_{\text{min}}\geq 1-100\gamma$. We thus propose the following cover:

where $\rho=\frac{\xi\sqrt{2\pi e}(1-100\gamma)}{d+\xi\sqrt{2\pi e}}$. First we will show that this is a valid cover. Consider an arbitrary $\mathcal{N}(0,\Sigma)\in\mathcal{B}\left(\gamma,\mathcal{N}(0,I),\mathcal{G}^{S}_{d}\right)$. We want to show that there is a distribution $\mathcal{N}(0,\hat{\Sigma})\in\mathcal{C}_{\xi}$ that is $\xi$-close to $\mathcal{N}(0,\Sigma)$. Let $\Delta=\Sigma-I$, let $\hat{\Delta}=\rho\lfloor\Delta/\rho\rfloor$ and let $\hat{\Sigma}=I+\hat{\Delta}$. Since $\|\Delta\|_{F}=\|\Sigma-I\|_{F}\leq 100\gamma$, $\mathcal{N}(0,\hat{\Sigma})$ is indeed in the cover.

Next we show that $\TV(\mathcal{N}(0,\Sigma),\mathcal{N}(0,\hat{\Sigma}))\leq\xi$. We use Proposition 32 in [VV10], which states for any two positive definite matrices $\Sigma$ and $\hat{\Sigma}$, if $\|\Sigma-\hat{\Sigma}\|_{\infty,\infty}\leq\rho^{\prime}$ and the smallest eigenvalue of $\Sigma$ satisfies $\lambda_{\text{min}}>\eta$, then we have

By the definition of $\mathcal{C}_{\xi}$, $\|\hat{\Delta}-\Delta\|_{\infty,\infty}\leq\rho$. Since any valid $\Sigma$ must satisfy $\lambda_{\text{min}}\geq 1-100\gamma$, our choice of setting $\rho=\frac{\xi\sqrt{2\pi e}(1-100\gamma)}{d+\xi\sqrt{2\pi e}}$ implies that

for any $\gamma$ smaller than the universal constant $c_{2}^{\prime}$. We now bound the size of the cover in a similar manner to the case of location Gaussians.

for any $\gamma$ smaller than the universal constant $c_{2}^{\prime\prime}$ we have,

Setting $c_{2}=\max\{c_{2}^{\prime},c_{2}^{\prime\prime}\}$ completes the proof. ∎

The following corollary is a direct consequence of Lemma 3.4 and Proposition A.1.

We can thus take the cover $\mathcal{C}_{\xi}$ in Lemma 3.4, and replace every distribution $\mathcal{N}(0,\Sigma_{1})\in\mathcal{C}_{\xi}$ with $\mathcal{N}(0,\Sigma^{1/2}\Sigma_{1}\Sigma^{1/2})$. Note that our modified cover will have the same size. From (5), our new cover will be a valid $\xi$-cover for $\mathcal{B}\left(\gamma,\mathcal{N}(0,\Sigma),\mathcal{G}^{S}_{d}\right)$ since the TV distance can not increase between any two distributions $\mathcal{N}(0,\Sigma_{1}),\mathcal{N}(0,\Sigma_{2})\in\mathcal{B}\left(\gamma,\mathcal{N}(0,I),\mathcal{G}^{S}_{d}\right)$ after applying the transformation above. ∎

We can now combine Lemma 3.1 with Corollary 3.5 to get the following:

Beyond GAP-MAX: Boosting Weak Hypotheses

As we mentioned before, by using a $(k,6\xi+\alpha)$-locally small $\xi$-cover for an infinite set of distributions $\mathcal{H}$, one can utilize Theorem 2.23 to privately learn a distribution to low error. Unfortunately, this approach will yield a sample complexity bound that has a term of order $O(\log(1/\delta)/\alpha\varepsilon)$. In the case of learning an unbounded univariate Gaussian in the realizable setting, it is known that the sample complexity is $O(1/\alpha^{2}+\log(1/\delta)/\varepsilon)$ [KV18], however the upper bound on the sample complexity achieved by Theorem 2.23 (together with an appropriate locally smaller cover) is $O(1/\alpha^{2}+\log(1/\delta)/\alpha\varepsilon)$ [BKSW19, Corollary 6.15]. In order to overcome the poor dependence on $\log(1/\delta)$, we can instead aim for a two step approach:

Use the GAP-MAX algorithm in Theorem 2.23 but with constant accuracy $C$ to learn a distribution $H^{\prime}$ that is roughly $C$-close to the true Gaussian for some appropriately selected constant $C<1$.

Build a finite cover for $\mathcal{B}\left(C,H^{\prime},\mathcal{H}\right)$ and use the private hypothesis selection algorithm (Theorem 2.22) to learn a distribution $\widehat{H}$ that is $\alpha$-close to the true Gaussian.

Running the GAP-MAX algorithm with constant accuracy $C$ thus removes the dependence on $\alpha$ in the $O(\log(1/\delta)/\varepsilon)$ term. Intuitively, this approach learns a “rough” estimate of the right distribution using approximate differential privacy. Since we know that we are roughly $C$-close to the true Gaussian, we can cover $\mathcal{B}\left(C,H^{\prime},\mathcal{H}\right)$ with a finite cover, and use the $\varepsilon$-differentially private hypothesis selection algorithm. This two step approach which we dub boosting gets us a much better dependence on the privacy parameter $\delta$ in our sample complexity bounds, and as we will see it holds more generally in the robust learning setting.

We note that the first step in the above approach may only need to produce an exceptionally coarse estimate to the true distribution – one to which it bears very little resemblance at all! We illustrate this with the simple problem of privately estimating a univariate Gaussian $\mathcal{N}(\mu,1)$ (in the realizable case).

We can see that the first step in the procedure truly requires an exceptionally coarse estimate of the distribution. The estimate of the mean described is significantly further from the true mean than any individual point will be. Interestingly, note that if one requires a more accurate final distribution, the distribution output in the first step is allowed to be less accurate.

As a first step, we can show that Algorithm 1 can achieve a slightly more general guarantee than a robust PAC learning sample complexity bound. We make Algorithm 1 more general than it needs to be to give a robust learning guarantee for $\mathcal{G}^{L}_{d}$ in order to make use of it as a subroutine in Algorithm 2 which robustly learns $\mathcal{G}_{d}$.

Let $b$ be a positive constant. For any $\beta,\varepsilon,\delta\in(0,1)$, $\alpha\in(0,c_{3})$ and $\xi\in(0,c_{4})$ where $c_{3}$ and $c_{4}$ are constants that depend only on $b$, given a dataset $D\sim P^{n}$ where $P$ satisfies $\TV(P,\mathcal{G}^{L}_{d})\leq b\xi+\alpha/4$, $\emph{\text{BOOST}}_{1}\left(b,\xi,\alpha,\beta,\varepsilon,\delta,\mathcal{C}_{\alpha},D\right)$ is an $(\varepsilon,\delta)$-differentially private algorithm which outputs some $\widehat{H}\in\mathcal{G}^{L}_{d}$ such that $\TV(\widehat{H},P)\leq 3(b+1)\xi+\alpha$ with probability no less than $1-\beta$, so long as

We first show Algorithm 1 satisfies $(\varepsilon,\delta)$-differential privacy. Line 1 of the algorithm is $(\varepsilon/2,\delta)$-differentially private by the guarantee of Theorem 2.23. Line 1 maintains $(\varepsilon/2,\delta)$-privacy by post-processing (Lemma 2.18). Finally, line 1 is $(\varepsilon/2,0)$-differentially private by Theorem 2.22. By composition (Lemma 2.17), the entire algorithm is $(\varepsilon,\delta)$-differentially private.

We now argue about the accuracy of the algorithm. By Lemma 2.14, Corollary 3.3 and Theorem 2.23, as long as $n=O\left(\frac{d+\log(1/\beta\delta)}{\varepsilon}\right)$, with probability no less than $1-\beta/2$ the GAP-MAX algorithm in line 1 outputs a distribution $H^{\prime}$ that is $\left(3b\xi+\frac{1}{200(600b+1)}\right)$-close to $H^{*}$, for any $\xi$ and $\alpha$ smaller than constants $c_{3}^{\prime}$ and $c_{4}$, respectively, that depend only on $b$. For the remainder of the proof we condition on this event.

as long as $n=O\left(\frac{d+\log(1/\beta)}{\alpha^{2}}+\frac{d+\log(1/\beta)}{\alpha\varepsilon}\right)$. Setting $n=O\left(\frac{d+\log(1/\beta)}{\alpha^{2}}+\frac{d)+\log(1/\beta)}{\alpha\varepsilon}+\frac{\log(1/\beta\delta)}{\varepsilon}\right)$ together with a union bound completes the proof. ∎

The following result can be derived from the $\text{BOOST}_{1}$ algorithm by taking the standard assumption in the robust setting of $\TV(P,\mathcal{H})\leq\xi$. The proof is nearly identical to the proof of Lemma 4.2.

Let $\alpha,\beta,\varepsilon,\delta\in(0,1)$ and $\xi\in(0,c_{5})$ where $c_{5}$ is a universal constant, and let $D\sim P^{n}$ where $P$ satisfies $\TV(P,\mathcal{G}^{L}_{d})\leq\xi$. Furthermore, let $\mathcal{C}_{\xi}$ be an appropriately selected locally small $\xi$-cover for $\mathcal{G}_{d}^{L}$. $\emph{\text{BOOST}}_{1}\left(1,\xi,\alpha,\beta,\varepsilon,\delta,\mathcal{C}_{\alpha},D\right)$ is an $(\varepsilon,\delta)$-DP $(\xi,6)$-robust PAC learner for $\mathcal{G}_{d}^{L}$ with sample complexity

We can now use Lemma 2.25 together with Lemma 4.3 to get a semi-agnostic algorithm.

2 Learning Gaussians

We can now show that Algorithm 2 achieves the following sample complexity bound for robust learning.

Let $\beta,\varepsilon,\delta\in(0,1)$, $\alpha\in(0,c_{6})$ and $\xi\in(0,c_{7})$ where $c_{6}$ and $c_{7}$ are universal constants, and let $D\sim P^{n}$ where $P$ satisfies $\TV(P,\mathcal{G}^{L}_{d})\leq\xi$. Furthermore, let $\mathcal{C}_{\alpha}^{1}$ and $\mathcal{C}_{\alpha}^{2}$ be appropriately selected locally small covers for $\mathcal{G}_{d}$ and $\mathcal{G}_{d}^{L}$ respectively. $\emph{\text{BOOST}}_{2}\left(\xi,\alpha,\beta,\varepsilon,\delta,\mathcal{C}_{\alpha}^{1},\mathcal{C}_{\alpha}^{2},D\right)$ is an $(\varepsilon,\delta)$-DP $(\xi,33)$-robust PAC learner for $\mathcal{G}_{d}$ with sample complexity

We first show Algorithm 2 satisfies $(\varepsilon,\delta)$-differential privacy. Line 2 of the algorithm is $(\varepsilon/4,\delta/2)$-differentially private by the guarantee of Theorem 2.23. Line 2 maintains $(\varepsilon/4,\delta/2)$-privacy by post-processing(Lemma 2.18). Line 2 is $(\varepsilon/4,0)$-differentially private by Theorem 2.22. Line 2 maintains privacy by post processing (Lemma 2.18). Finally, line 2 is $(\varepsilon/2,\delta/2)$-differentially private by the privacy of Algorithm 1 proved in Lemma 4.2. By composition (Lemma 2.17) the entire algorithm is $(\varepsilon,\delta)$-differentially private.

We now argue about the accuracy of the algorithm. Let $H^{*}=\mathcal{N}(\mu^{*},\Sigma^{*})$ be the hypothesis in $\mathcal{G}_{d}$ that satisfies $\TV(H^{*},P)\leq\xi$. By Lemma A.3 $Y_{i}\sim Q$ where $\TV(Q,\mathcal{N}(0,\Sigma^{*}))\leq 3\xi$, which implies that $\TV(\mathcal{N}(0,\Sigma^{*}),\mathcal{C}_{\xi}^{1})\leq 4\xi$. From Lemma 2.14, Corollary 3.6 and Theorem 2.23, as long as $n=O\left(\frac{d^{2}+\log(1/\beta\delta)}{\varepsilon}\right)$, with probability no less than $1-\beta/4$ the GAP-MAX algorithm in line 2 outputs a distribution $H_{1}^{\prime}=\mathcal{N}(0,\Sigma^{\prime})$ that is $\left(12\xi+\frac{1}{100(1201)}\right)$-close to $\mathcal{N}(0,\Sigma^{*})$, for any $\xi$ smaller than a universal constant $c_{6}^{\prime}$. We condition on this event.

It follows from the triangle inequality that $\TV(R,\mathcal{C}_{\xi}^{2})\leq 10\xi+\alpha/4$. This together with Lemma 4.2 implies that, with probability greater than $1-\beta/2$, $\text{BOOST}_{1}(10,\xi,\alpha,\beta/2,\varepsilon/2,\delta/2,\mathcal{C}_{\alpha}^{2},D^{\prime\prime})$ outputs $\widehat{H}_{2}=\mathcal{N}(\hat{\mu},I)$ satisfying $\TV(\widehat{H}_{2},\mathcal{N}(\mu^{*},I))\leq 33\xi+\alpha$ for any $\xi$ and $\alpha$ smaller than universal constants $c_{6}^{\prime\prime\prime}$ and $c_{7}$ respectively, as long as $n=O\left(\frac{d+\log(1/\beta)}{\alpha^{2}}+\frac{d+\log(1/\beta)}{\alpha\varepsilon}+\frac{\log(1/\beta\delta)}{\varepsilon}\right)$. Using the triangle inequality and Corollary A.2 it follows that $\TV(\mathcal{N}(\widehat{\Sigma}^{1/2}\hat{\mu},\widehat{\Sigma}),P)\leq 33\xi+\alpha$. Setting $n=O\left(\frac{d^{2}+\log(1/\beta)}{\alpha^{2}}+\frac{d^{2}+\log(1/\beta)}{\alpha\varepsilon}+\frac{\log(1/\beta\delta)}{\varepsilon}\right)$ and $c_{6}=\max\left\{c_{6}^{\prime},c_{6}^{\prime\prime},c_{6}^{\prime\prime\prime}\right\}$ together with a union bound completes the proof. ∎

Finally, we can combine the above result with Lemma 2.25 to get a semi-agnostic sample complexity bound for modest levels of model misspecification.

3 Bounds for the Realizable Setting

The following sample complexity bounds hold for $(\varepsilon,\delta)$-DP (realizable) PAC learning. The proofs are very similar to the proofs in Section 4.1 and 4.2 for $(\varepsilon,\delta)$-DP robust PAC learning, where the slight difference is that we can build the covers directly with accuracy $\alpha$ (instead of $\xi$) since we assume realizability. The first bound is tight and the second one is conjectured to be tight.

For any $\beta,\varepsilon,\delta\in(0,1)$ and $\alpha\in(0,c_{8})$ where $c_{8}$ is a universal constant, there exists an $(\varepsilon,\delta)$-DP PAC learner for $\mathcal{G}_{d}^{L}$ with sample complexity

For any $\beta,\varepsilon,\delta\in(0,1)$ and $\alpha\in(0,c_{9})$ where $c_{9}$ is a universal constant, there exists an $(\varepsilon,\delta)$-DP PAC learner for $\mathcal{G}_{d}$ with sample complexity

Agnostic Private Hypothesis Selection

In this section we present an $\varepsilon$-DP semi-agnostic PAC learner that achieves the same sample complexity as the PHS algorithm of Theorem 2.22. The PHS algorithm is based on the celebrated Scheffé tournament (see, e.g., Chapter 6 of [DL01]), where the distributions in $\mathcal{H}$ play a round robin tournament against one another. The winner of this tournament is then chosen as the output. One of the technical difficulties in constructing privatized versions of the Scheffé tournament via the exponential mechanism is that a single sample can quite drastically change the outcome of the tournament, which makes choosing score functions based on tournaments challenging. We sidestep this issue completely by considering another approach to hypothesis selection called the minimum distance estimate (MDE). The MDE approach is based on maximizing a particular function of the data and $\mathcal{H}$ as we will see shortly. Fortunately, this estimator is already in the form of a maximization problem and the function we aim to maximize has low sensitivity. Thus, using the exponential mechanism together with the MDE is a very natural way to privatize semi-agnostic hypothesis selection. The MDE requires $O(m^{3})$ computations, where $m$ is the number of hypotheses in $\mathcal{H}$. [MS08] presented a modified MDE that is very similar to the original MDE, but only requires $O(m^{2})$ computations. Fortunately, this modified algorithm maintains the guarantee of the original algorithm, so we will privatize the modified MDE instead of the original MDE. We formally state our result below.

Before we prove the result, we define a few things. For an ordered pair of distributions $(H_{i},H_{j})$ over a common domain $\mathcal{X}$, we define their Scheffé set as $A_{ij}=\{x\in\mathcal{X}:H_{i}(x)>H_{j}(x)\}$. A useful version of the TV distance between two distributions we will make use of is

We note that most of the analysis below is standard in proving the correctness of the MDE (e.g., see the proof of Theorem 6.3 in [DL01]), and is slightly adapted using the analysis of the modified MDE algorithm in Theorem 4 of [MS08]. The only difference here is the use of the exponential mechanism.

Let $\mathcal{X}$ be the common domain of the distributions in $\mathcal{H}$. For a dataset $D$ and set $A\subseteq\mathcal{X}$, we define $\widehat{P}(A,D)=\frac{1}{n}\cdot|\{x\in D:x\in A\}|$. For a distribution $H$ and a set $A\subseteq\mathcal{X}$, let $R(H,A)=H(A)-\widehat{P}(A)$. For any $H_{i}\in\mathcal{H}$, we define the score function

With this in place, the algorithm is simple: run the exponential mechanism [MT07] with this score function, on the set of candidates $\mathcal{H}$, with dataset $D$, and return whichever distribution it outputs.

It is not hard to see that the score function has sensitivity $2/n$. Let $H_{k}\in\mathcal{H}$ be any distribution that maximizes the score function. From Theorem 2.16, it follows that running the exponential mechanism with our dataset $D$, the set of distributions $\mathcal{H}$, privacy parameter $\varepsilon$ and the the score function above outputs a distribution $H_{k^{\prime}}\in\mathcal{H}$ that guarantees, with probability no less than $1-\beta/2$,

where the last line holds so long as $n=O\left(\frac{\log(m/\beta)}{\alpha\varepsilon}\right)$. We condition on this event, which can equivalently be stated as

We now look at the right most term in (7). By the definition of the total variation distance and an application of the triangle inequality we have

Using (6), the fact that $H_{k}$ maximizes the score function, and the triangle inequality all together yields,

Furthermore, notice that the term $\Delta(P)$ is small when the difference between the empirical and the true probability measures assigned by $P$ to the Scheffè sets is small. We can thus upper bound this term by $\alpha$ by using $2{{m}\choose{2}}$ standard Chernoff bounds together with a union bound to get,

with probability no less than $1-\beta/2$ so long as $n=O\left(\frac{\log(m/\beta)}{\alpha^{2}}\right)$. Putting (7) and (8) together gives us,

A union bound together with setting $n=O\left(\frac{\log(m/\beta)}{\alpha^{2}}+\frac{\log(m/\beta)}{\alpha\varepsilon}\right)$ completes the proof. ∎

Conclusion

We provide the first finite sample complexity bounds for privately learning Gaussians with unbounded parameters. We do this via a method for converting small local covers, to global covers which are locally small. In this paper, we only prove sample complexity upper bounds, and our methods are not computational in nature. One natural direction is to design polynomial time algorithms for learning unbounded Gaussians. Another direction is to explore applications of our method to other classes of distributions. The most immediate class that comes to mind is Gaussians mixture models (GMMs) – given upper and lower bounds on the total variation distance between GMMs based on their parameter distance, it should not be difficult to derive corresponding sample complexity bounds.

Acknowledgments

GK would like to thank Mark Bun, Adam Smith, Thomas Steinke, and Zhiwei Steven Wu for helpful conversations and suggestions which led to the results in Section 5.

References

Appendix A Useful Inequalities

Let $X$ and $Y$ be random variables taking values in the same set. For any function $f$, we have $\TV(f(X),f(Y))\leq\TV(X,Y)$.

Taking the supremum of the left hand side completes the proof. ∎

Let $X$ and $Y$ be random variables taking values in the same set. For any invertible function $f$, we have $\TV(f(X),f(Y))=\TV(X,Y)$.

By Proposition A.1, $\TV(f(X),f(Y))\leq\TV(X,Y)$ and $\TV(f^{-1}(f(X)),f^{-1}(f(Y)))\leq\TV(f(X),f(Y))$. ∎

For any $\xi\in(0,1)$, Gaussian $\mathcal{N}(\mu,\Sigma)$ and distributions $P$ that satisfies $\TV(P,\mathcal{N}(\mu,\Sigma))\leq\xi$, the following holds. If $X_{1},X_{2}\sim P^{2}$, and $Y=(X_{1}-X_{2})/\sqrt{2}\sim Q$, then $\TV(Q,\mathcal{N}(0,\Sigma))\leq 3\xi$.

Given $X\sim P$, the density $P$ is given by $P=\mathcal{N}(\mu,\Sigma)+\Delta$. Recall in this paper we define distributions by their densities so $\mathcal{N}(\mu,\Sigma)$ is the Gaussian density. It follows from the definition of the TV distance that $\|\Delta\|_{1}\leq 2\xi$. Given a sample $X\sim P$, we let $P^{-}$ be the distribution that satisfies $-X\sim P^{-}$. The density of $P^{-}$ is given by $P^{-}=\mathcal{N}(-\mu,\Sigma)+\Delta^{-}$ where $\|\Delta^{-}\|_{1}\leq 2\xi$. The sample $Y^{\prime}=X_{1}+(-X_{2})$ has density

We can now bound the TV distance between $P_{\text{conv}}$ and $\mathcal{N}(0,2\Sigma)$.

where the first inequality follows from the triangle inequality together with Young’s inequality. Since $\TV(P_{\text{conv}},\mathcal{N}(0,2\Sigma))\leq 3\xi$, the statement follows immediately from Corollary A.2 and equation (1). ∎

Appendix B Omitted proofs from Section 2

We first prove the inequality on the left hand side. Let $\mathcal{C}_{\gamma}$ be a $\gamma$-cover for $\mathcal{H}$ that has size $N(\mathcal{H},\gamma)$. If $N(\mathcal{H},\gamma)=\infty$, we are done. Otherwise, we claim there is no $2\gamma$-packing $\mathcal{P}^{\prime}_{2\gamma}$ of $\mathcal{H}$ of size at least $N(\mathcal{H},\gamma)+1$. We prove this by contradiction. Assume to the contrary that there exists a $2\gamma$-packing $\mathcal{P}^{\prime}_{2\gamma}$ of $\mathcal{H}$ such that $|\mathcal{P}^{\prime}_{2\gamma}|=N(\mathcal{H},\gamma)+1$. By the pigeonhole principle, there exists $Q\in\mathcal{C}_{\gamma}$ and two distributions $P,P^{\prime}\in\mathcal{P}^{\prime}_{2\gamma}$ such that $\TV(Q,P)\leq\gamma$ and $\TV(Q,P^{\prime})\leq\gamma$. By the triangle inequality it follows that $\TV(P,P^{\prime})\leq 2\gamma$ which is a contradiction, so $\mathcal{P}^{\prime}_{2\gamma}$ cannot be a $2\gamma$-packing of $\mathcal{H}$. This shows that $M(\mathcal{H},2\gamma)\leq N(\mathcal{H},\gamma)$.

We now prove the inequality on the right hand side. Let $\mathcal{P}_{\gamma}$ be a maximal $\gamma$-packing with size $M(\mathcal{H},\gamma)$. If $M(\mathcal{H},\gamma)=\infty$, we are done. Otherwise, we claim that $\mathcal{P}_{\gamma}$ is also an $\gamma$-cover of $\mathcal{H}$, and hence $N(\mathcal{H},\gamma)\leq M(\mathcal{H},\gamma)$. We can prove this by contradiction. Suppose to the contrary that there were a distribution $P\in\mathcal{H}$ with $\TV(P,\mathcal{P}_{\gamma})>\gamma$. Then we could add $P$ to $\mathcal{P}_{\gamma}$ to produce a strictly larger packing, contradicting the maximality of $\mathcal{P}_{\gamma}$. Therefore it only remains to show that a maximal packing actually exists, which follows from a simple application of Zorn’s lemma (See proof of Lemma 3.1).

B.2 Proof of Lemma 2.25

Fix accuracy and privacy parameters $\alpha,\beta,\varepsilon,\delta\in(0,1)$. Let $T=\lceil\log_{2}(1/\alpha)\rceil$ and define sequences $\xi_{1}=\alpha/12C,\xi_{2}=2\alpha/12C,\dots,\xi_{T+4}=2^{T+3}\alpha/12C$. Furthermore for all $t\in[T+4]$ set $\alpha_{t}=\alpha/12$, $\beta_{t}=\beta/2(T+4)$, $\varepsilon_{t}=\varepsilon/2(T+4)$ and $\delta_{t}=\delta/(T+4)$. For each $t$, let $H_{t}$ denote the outcome of a run of the $(\xi,C)$-robust algorithm using robustness parameter $\xi_{t}$ accuracy parameters $\alpha_{t},\beta_{t}$ and privacy parameters $\varepsilon_{t},\delta_{t}$. We then use the algorithm of Theorem 2.24 to select a hypothesis from $H_{1},\dots,H_{T+4}$ using accuracy parameter $\alpha/2$, $\beta/2$ and privacy parameter $\varepsilon/2$. By composition of DP (Lemma 2.17) it follows the output of the two step procedure is $(\varepsilon,\delta)$-DP.