Distribution Learnability and Robustness
Authors: Shai Ben-David
Alex Bie
Gautam Kamath
Tosca Lechner
Venue: NeurIPS 2023 poster (2023)
Keywords: robustness
distribution learning

Abstract: We examine the relationship between learnability and robust learnability for the problem of distribution learning.
We show that learnability implies robust learnability if the adversary can only perform additive contamination (and consequently, under Huber contamination), but not if the adversary is allowed to perform subtractive contamination. 
Thus, contrary to other learning settings (e.g., PAC learning of function classes), realizable learnability does not imply agnostic learnability. 
We also explore related implications in the context of compression schemes and  differentially private learnability.

Distribution Learnability and Robustness"
Shai Ben-David
Alex Bie University of Waterloo yabie@uwaterloo.cc ca
University of Waterloo, Vector Institute shai wwwiteraoooroocooomommo ca
Gautam Kamath University of Waterloo, Vector Institute gocsail.mit.ed. mit.edu
Tosca Lechner University of Waterloo
clechner@uvaterloo.
Abstract
We examine the relationship between learnability and robust (or agnostic) learn- ability for the problem of distribution learning. We show that learnability of a distribution class implies robust learnability with only additive corruption, but not if there may be subtractive corruption. Thus, contrary other learning settings (e.g.. PAC learning function classes), realizable learnability does not imply agnostic learnability. We also explore related implications in the context of compression schemes and differentially private learnability.
Introduction
Distribution learning (sometimes called density estimation) refers to the following statistical task: given i.i.d. samples from some (unknown) distribution p. produce an estimate of p. This is one the most fundamental and well-studied questions in both statistics [LO1]] and computer science [Dialō], often equivalent classic problems of parameter estimation (e.g., mean estimation) in parametric settings. It is easy to see that no learner can meaningfully approximate any given p without having some prior knowledge. The problem then becomes: assuming the sample generating distribution p belongs to given class of distributions C, and given parameters E, (0, 1). output some distribution such that with probability at least employ total variation distance, the most studied metric in density
8, the statistical distance between p and p
is at most Specifically, estimation [DLO Dia16], using drv (p, 9) to denote the distance between distributions and This case, when p E C, is often called the realizable setting. If, for with a finite number samples 5), then we say the distribution class is (e, -eearrnale A class is learnable if it is (e, -learmable for every (c (0. 1)?. A significant amount of work has focused on proving bounds on n²(, 6) for a number of classes C of interest for example, one can consider the class C of all Gaussian distributions [H, Σ) in some Euclidean space Rdd.
particular class C, this is doable
However, this framework is restrictive in the sense that it requires the unknown distribution to be exactly a member of the class interest. This may not be the case for a variety of possible reasons, including some innocuous and some malicious. As one example, while it is a common modelling assumption to posit that data comes from a Gaussian distribution, Nature rarely samples exactly from Gaussians, we consider this only to be convenient approximation. More generally, the class C that the learner assumes can thought of as reflecting some prior knowledge about the task hand. Such prior knowledge is almost always only an approximation of reality. Alternatively, we may be in an adversarial setting, where a malicious actor has the ability to modify an otherwise well-behaved
Authors listed in alphabetical order.
For the sake of exposition, we defer formal definitions of our learnability notions to Section
1.1
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

distribution, say by injecting datapoints of their own (known in the machine learning literature as data poisoning attacks [BNL12 SKL17 DKK + 19 GTX 20 GFH 21 LKY23
More formally, the classic problem of agnostic learnability is generally described as follows: given (known) class of distributions C, and (finite) set of samples drawn i.i.d. from some (unknown) distribution find a distribution á whose statistical distance from p is not much more than that of the closest member of C. It is not hard see that this is equivalent to a notion of robust learnability, where the distribution p is not viewed as arbitrary, but instead an adversarial corruption of some distribution within c Given their equivalence, throughout this work, we will use agnostic and robust leamaaility interchangeably.
The difference between robust setting and the previous realizable one is that now, instead of assuming p E C and asking for an arbitrarily good approximation of p. we make no prior assumption about the data-generating distribution and only ask approximate as well as (or close to) what the best member of some "benchmark" class C can do.
We address the following question: Assuming class of distributions is learnable, under which notions of robustness guaranteed to be robustly learnable? We focus entirely on information thhoorrtcccc learnability, and eschew concerns of computational efficiency. Indeed, our question of interest is so broad that computationally efficient algorithms may be too much to hope for.
We shall consider few variants of robust learnability. Specifically, we will impose requirements on the nature of the difference between the data aata-generating distribution p and members of the class Obviously, such requirements can only make the task of robust learning easier.
One such model considers additive robustness. The underlying distribution is restricted to be mixture of distribution from C, and some 'contaminating' distribution In this Statistics community, this celebrated model is known Huber's contamination model [Hub64]. Analogously, one can consider subtractive robustness. It includes the case where the starting point is a distribution in the class C, but a fraction of the probability mass is removed and samples are drawn from the resulting distribution (after rescaling). These two models are related to ad adversaries who can add or remove points from a sampled dataset, see discussion at the end of Section T.2
significant line of work focuses on understanding the sample complexity of agnostic distribution learning (see examples and discussion in Section 1.3) Most study restricted classes of distributions, with analyses that are only applicable in certain classes. Some works have found quantitative separa- tions between the different robustness models. For instance, in the specific case of Gaussian mean estimation, [DKK 16 LRVI6 DKS17 DKK give strong evidence that efficient algorithms can achieve better error if they must only be additively robust, rather than robust in general. However, such findings are again restricted to specific cases, and say little about the overall relationship between learnability in general and these various robust learning models.
Current results leave open a more comprehensive treatment of robustness in distribution learning. Specifically, what is the relative power of these different robustness models, and what is their impact on which types of distributions are learnable? Are there more generic ways to design robust learning algorithms?
Our two main contributions are the following:
We give a generic algorithm which converts a learner for a distribution class into a learner for that class which is robust to additive corruptions.
We show that there exist distribution classes which are learnable, but are longer learnable after subtractive corruption.
Stated succinctly: we show that learnability implies robust learnability when adversary make additive corruptions, but not subtractive corruptions. Other results explore implications related to compression schemes and differentially private learnability.
A related notion of robust learnability instead imagines the adversary modifies the samples from a distribution in C, rather than the distribution itself. This adaptive model is discussed further in Section 1.2

---

1.1 Definitions of Learnability
In order more precisely describe our results, we define various notions of learnability. We start with the standard notion of PAC learnability for distribution class. We get samples from a distribution belonging a distribution class C, and the goal is output distribution similar p.
Definition 1.1 (Learnability). We say that a class C of probability distributions is learnable (or, realizably learnable) if there exists a learner A and a function ne (0, 1)² + N, such that for every probability distribution p E C, and every (e, 6) E (0, 1)2. n 2 ne(e, () the probability over samples S of that size drawn i.idd. from the distribution p that drv (p. A(S)) S is least 1 6.
We next introduce the more challenging setting of robust, or agnostic, learning. In this setting, the sampled distribution is within bounded distance to the distribution class C, rather than being in C itself. For technical reasons, we introduce two closely-related definitions. Roughly speaking, the latter definition assumes the distance from the sampling distribution to C is fixed, whereas the former (more commonly considered the agnostic learning literature) doesn't. tt Note that many cases, robust algorithms designed with knowledge of the distance v to C can be modified to do without [JO222] Definition 1.2 (Robust learnability).
1. For a O, we say that a class C of probability distributions is a-robustly learnable (also referred to as a-agnostically learnable) if there exists a learner A and a finction
ne : (0, 1)2 -> M, such that for every probability distribution p. and (e.8) E (0. (0,1)2, for n 2 ne(E, 6) the probability over samples S of that size drawn i..dd from the distribution that dr (p, A(S)) S a min min(dry (drv(p (p.p) p') p E CC} + E at least 5.
When a = 1 we omit it and say that the class is robustly (or agnostically) learnable.
2. For 0 < n S. and a > O, we say that a class C of probability distributions is n-a-rrbustly learnable if there exists a learner A and function nc (0, 1) - N, such that for every probability distribution such that min min(dry(s (dr((p (1.yw(,,p (p.p') p E C} S Lj and (s, E (0, 1)2, for n 2 nele, 5) the probability over samples S of that size drawn i.i.d. from the distribution p 6.
that (p, A(S)) S an + E at least
Finally, we introduce notions of robust learnability which correspond to only additive or subtractive deviations from the distribution class C. These more stringent requirements than standard (realizable) learnability, but more lenient than 7--x-robust learnability: the adversary in that setting can deviate from the distribution class C with both additive and subtractive modifications simultaneously.
Definition 1.3 (Additive robust lcarnability). Given parameters 0 S rj S 1 and a > O, we say that class C of probability distributions is n-additive a-robustly learnable if there exists learner A and a function ne (0, 1)2 > N, such that for every probability distribution q, every p E C, and ne(e, 5) the probability over samples S of that size drawn i..d from the
(c, 6) E (0, 1)² for distribution 17q + - n)p, that dry (A(S).P) S on + E is at least
Definition 1.4 (Subtractive robust learnability). Given parameters 0 S SnS1 1 and a > 0, we say that a class C of probability distributions is y-subtracttvv a-robustly learnable if there exists a learner A and function ne (0, 1) + N, such that for every probability distribution p for which there exists a probability distribution q such that rạq + (1 - n)p E C, and for every (5, E (0, 1)², for 2 ne(e.8) 8) the probability over samples S of that size drawn i.i.d. from the distribution p. that drv (A((), & an) + E is at least 1 5.
1.2 Results and Techniques
We explore how different robustness models affect learnability of distributions, showing strong separations between them. Our first main result shows that learnability implies additively robust learnability.
Theorem 1.5. Any class of probability distributions Q which is realizably learnable, is also ry- additively 2-robustly learnable for every 1 E (0, 1/4).
Note that, since additively robust lcarnailiity trivially implies learnability, this shows an equivalence between learnability and additively robust learnability.
Our algorithm enumerates over all subsets of the dataset of an appropriate size, such that at least one subset contains no samples from the contaminating distribution. A realizable learner is applied to
3

---

each subset, and techniques from hypothesis selection Y DL%6 DL97 DLOI are used to pick the best of the learned distributions. Further details appear Section 2
We also note that since our robust learning algorithm enumerates all large subsets of the training dataset, it is not computationally efficient. Indeed, for such broad characterization, this would be too much to ask. Efficient algorithms for robust learnability are an exciting and active field of study, but outside the scope of this work. For further discussion see Section 1.3
Our other main result shows that a distribution class being learnable does not imply that it is subtractive robustly learnable.
Theorem 1.6. For every a > 0, there exists a class that is learnable, but not n-subtractively a-robustly learnable for any 0 S 17 7 16a'
An immediate corollary is that learnability does not imply robust (or agnostic) learnabilitt, since this is a more demanding notion than subtractive robust learnability.
Our proof of this theorem proceeds by constructing a class of distributions that is learnable, but classes obtained by subtracting light-weight parts of these distributions are not a-robustly learnable with respect to the original learnable class. More concretely, our construction works as follows. We start by considering a distribution class that, by itself, is not Iearnable with any finite number of samples. We map each distribution in that class to new distribution, which additionally features a point with non- trivial mass that "encodes" the identity of the distribution, thus creating a new class of distributions which is learnable. Subtractive contamination is then able to "erase" this point mass, leaving a learner with sample access only to the original (unlearnable) class. Our construction is inspired by the recent construction of Lechner and Ben-David [LBD23], showing that the learnability of classes of probability distributions cannot be characterized by any notion of combinatorial dimension. For more details, see Section S
Thus far, we have only considered additive and subtractive robustness separately. General robust- ness, where probability mass can be both added and removed, is more powerful than either model individually. However, if class is additive robustly Iearnable and subtractive robustly learnable, is it robustly learnable? Though this is intuitively true, we are not aware of an immediate proof. Using a similar argument as Theorem 1.5 we derive a stronger statement: that subtractively robust leamability implies robust learnability.
Theorem 1.7. If a class C is n-subtractive o-robusslly learnable, then it is also 9- + 40-robustly learnable.
Adjacent to distribution learning is the notion of sample compression schemes. Recent work by Ashtiani, Ben-David, Harvey, Liaw, Mehrabian, and Plan [ABDH*18] expanded notions of sample compression schemes to apply to the task of learning probability distributions. They showed that the existence of such sample compression schemes for a class of distributions imply the learnability of that class. While the existence of sample compression schemes for classification tasks imply the existence of such schemes for robust leaning, the question if similar implication hold for distribution learning schemes was not answered. We strongly refute this statement. We use a construction similar to that of Theorem [.6] see Section 3.1 for more details.
Theorem 1.8. The existence of compression schemes for class of probability distributions does not imply the existence of robust compression schemes for that class.
Finally, natural question is whether other forms of learnaiility imply robust learnability. We investigate when differentially private (DP) lcarnability does or does not imply robust learnability. We find that the same results and separations as before hold when the distribution class is learnable under approximate differential privacy (i.e., (e, 6)-D), but, perhaps surprisingly, under pure differential privacy (i.e., (c, DDP)), private learnability implies robust learnability for all considered adversaries
Theorem 1.9 (Informal). (e, 0)-DP learnability implies robust (c, DD learnability. For any 5 > O. (c, ()D learnability implies additively robust learnability, but not subtractively robust learnability.
'Differential privacy is popular and rigorous notion of data privacy. For the definition of differential privacy. Section 4
'In the context of differential privacy, we diverge slightly from the established notation. Specifically, we align ourselves with common notation in the DP literature, using e and 5 for privacy parameters, and use (in place of e) and & (in place of d) for accuracy parameters.

---

For pure DP learnability, we employ an equivalence between learnability under pure differential privacy and packing [BKSWI9. Existence of such packing in turn implies learnability under both pure differential privacy and with both additive and subtractive contamination. For approximate DP learnability, we note that the corresponding version of Theorem 1.5 automatically holds, since private learnability implies learnability. We show that our construction for Theorem [T.6] is still learnable under approximate differential privacy, and thus the corresponding non-implication holds. See Section for more details.
To summarize the qualitative versions of our findings:
Learnability and additively robust learnability are equivalent (Theorem
1.5
Learnability does not imply subtractively robust learnability (Theorem 1.6)
Subtractively robust learnability implies robust learnability (Theorem 1.7
Pure DP learnability is equivalent to robust pure DP learnability (Theorem 1.9
Approximate DP learnability implies additively robust learnability but not subtractively
robust learnability (Theorem 1.9h;
Existence of sample compression schemes does not imply the existence of robust sample compression schemes (Theorem L88.
Quantitative versions of these statements can be found in their respective theorems.
Adaptive Adversaries. Our definition of robustness allows an adversary to make changes to the underlying distribution. Equivalently, it corresponds to an adversary who can add or remove points from dataset, but must commit to these modifications before the dataset actually sampled. A stronge/fadversayy adversary would be able to choose which points to add or remove after seeing the sampled dataset. Such an adversary is referred to as adaptive. Since adaptive adversaries are stronger than the ones we consider, any impossibility result that we show also holds in this settings (c.g., learnability does not imply subtractive robust learnability when the adversary is adaptive). It is an interesting open question to understand whether algorithms can be strengthened to work in this setting. Some positive evidence in this direction is due to Blanc, Lange, Malik, and Tan [BLMT22], who show that adaptive and non-adaptive adversaries have qualitatively similar power in many settings.
1.3 Related Work
Robust estimation is classic subfield of Statistics, see, for example, the classic works (uk660 Hub64], Our work fits more into the Computer Science literature on distribution estimation, initiated by the work of [KMR+94] which was in turn inspired by Valiant's 's PAC learning model [Va184] Since then, several works have focused on algorithms for learning specific classes of distributions,
see, e.g., [CDSS13] CDSS14a CDSS14b) LS17] ABDH 20). A recent line of work, initiated
by [DKK 16 LRV16 focuses on computationally efficieet robust estimation of multivariate distri-
butions, see, e.g.. DKKK SCV18 DKK+ KSS18 HL.8 19K+19 LM2 LM22] BD]+22
JKV23 and (DK22 for a reference. In contrast to all of these works, we focus on broad and generic
connections between learnability and robust learnability, rather than studying robust learnability of a particular class of distributions.
Some of our algorithmic results employ tools from hypothesis selection, problem which focuses on agnostic learning with respect to a specified finite set of distributions. The most popular approaches are based on ideas introduced by Yatracos [Yat85] and subsequently refined by Devroye and Lu- gosi [D96 DL97 [LO1] DLOI). Several others have studied hypothesis selection with an eye for several considerations, including running time, approximation factor. robustness, privacy. parallelization.
and more MS08 DDS12 DK14 SOAJ14 DKK+ * 16. ABDH + 18
AFJ+ BKSW19
BKM19
GKK 20
BBK 22 AAK21..
Distribution learning under the constraint of differential privacy (DMNS06) has been an active area of research, see, e.g., [VV88 KLSU19 BS19 ASZ21 CWZ21 KMS 22b, KMS22a), and
'A natural open question is whether approximate DP leamability implies additively robust approximate- learnability.
And in the case of removals, much natural
5

---

KU20
for survey, A number of these works have focused on connections between robustness and
privacy DL09 BKSWI9 KSU20 AM20 BGS [KKO21 LK022 KMV22 RIC22 SM22]
2 Again, these results either focus on specific classes of distributions, or give implications that require additional technical conditions, whereas we aim to
HKM22
GH22 HKMN23
give characterizations of robust learnability under minimal assumptions.
The question whether learnability under realizability assumptions extends to non-realizable setting has a long history. For binary classification tasks, both notions are characterized by the finiteness of the VC-dimension, and are therefore equivalent [VC7T VC74 BEHW89 [au92]] [PPS09 show a similar result for online learning. Namely, that agnostic (non- non--realizable) learnability is characterized by the finiteness of the Littlestone dimension, and therefore equivalent to realizable learnability.
Going beyond binary classification, recent work [HKLM22 shows that the equivalence of realizable and agnostic learnability extends across wide variety of settings. These include models with no known characterization of learnability such as learning with arbitrary distributional assumptions and more general loss functions, as well as a host of other popular settings such as robust learning, partial learning, fair learning, and the statistical query model. This stands in contrast to our results for the distribution learning setting. We show that realizable learnability of class of probability distributions does not imply its agnostic learnability. It is interesting and natural to explore the relationship between various notions of distribution learnability, which we have scratched the surface of in this work.
2 Learnability Implies Additive Robust Learnability
We recall Theorem
1.3 which shows that any class that is realizably learnable is also additive robustly
learnable.
Theorem 1.5. Any class of probability distributions Q which is realizably learnable, is also additively 2-robustly learnable for every n E (0, 1/4).
We prove this theorem by providing an algorithm based on classical tools for hypothesis selec- These methods take as input set of samples from an unknown
tion |Y [1.66 DL97 distribution and a collection of hypotheses distributions. one of the hypotheses, then, given enough samples, the algorithm will output close hypothesis. Roughly speaking, our algorithm looks at all large subsets of the dataset, such that at least one will correspond to an uncontaminated set of samples. A learner for the realizable setting (whose existence we assumed) is applied to each to generate a set of hypotheses, and we then use hypothesis selection to pick one with sufficient accuracy. The proof of Theorem 1.7 (showing that subtractively robust learnability implies robust learnability) follows almost the exact same recipe, except the realizable learner is replaced with a learner robust to subtractive contaminations. We recall some preliminaries in Section A We then prove Theorem 1.5 in Section B and we formalize and prove a version of in Section 2.1
the unknown distribution is close to
Theorem 7
We note that a = 2 and a = 3 are often the optimal factors to expect in distribution learning settings, even for the case of finite distribution classes. For example, for proper agnostic learning the factor = 3 is known to be optimal for finite collections of distributions, which holds for classes with only 2 distributions [KMM19] Similarly the factor of a = 2 is optimal if the notion of learning is relaxed to improper learners [KMM99 CDSS14b). While we are not aware of lower bounds for the additive setting, small constant factor such 2 is within expectations for these problems.
For the proof of Theorem 1.5
we refer the reader to Section in the appendix.
2.1 Subtractive Robust Learnability Implies Robust Learnability
Similarly, we can show that robustness with respect to a subtractive adversary implies robustness with respect to general adversary. We note that this theorem requires a change in constants from to (2a+ + +4).
Theorem 1.7. Ifa class C is n-subtractivv o-robustly learnable, then it is also (20 + 4) robrruuy learnable.
The proof follows a similar argument as the proof of Theorem 1.5 and can be found in Section C in the appendix.

---

3 Learnability Does Not Imply Robust (Agnostic) Learnablity
In this section we show that there are classes of distributions which are realizably learnable, but not robustly learnable.
Theorem 3.1. There are classes of distributions Q. such that Q is realizably learnable, but for every E I. Q is not a-robustly learnable. Moreover, the sample complexity of learning Q can be arbitrarily close to (but larger than) linear. Namely, for any super-lineat function g, there is a class Og. with
2g is realizable learnable with sample complexity n'5, (E, 8) S Log(L/0)g(1/e):
. for every E IR, 2g is not o-robustly learnable.
Note that this statement appears slightly weaker than Theorem T.6 in that it holds for a-robust learnability rather than //subbractivv a-robust learnability. In fact, the two statements are incompara- ble, due to the order of quantifiers in the construction. Here we provide a single class which is not a-robustly learnable for every a, whereas in the proof of Theorem 1.6 we give a different class for each a (though the two constructions are similar). For simplicity we focus here on Theorem 3.1 whereas the proofs of Theorem 1.6 and other claims appear in Section D
The key idea to the proof to construct a class which is easy learn in the realizable case, by having each distribution of the class have a unique support element that is not shared by any other distributions the class. Distributions on which this "indicator element" has sufficient mass will be easily identified, independent of how rich the class is on other domain elements. That richness makes the class hard learn from samples that miss those indicators. Furthermore, we construct the class in way that its members are close in total variation distance to distributions that place no weight on those indicator elements.
This is done by making the mass on these indicator elements small, so that the members of a class of distributions that results from deleting these indicator bits are close the initially constructed class, 2g In order to make this work for every target accuracy and sample complexity, we need to have union of such classes with decreasingly small mass on the indicator bits. order for this to not interfere with the realizable learnability, we let the distributions with small mass on the indicator bits have most of their mass on one point (0, 0) that is the same for all distributions in the class. This ensures that distributions for which the indicator bit will likely not be observed because their mass smaller than some 1) are still easily e-approximated by a constant distribution (o1o.0)). Lastly we ensure the impossibility of agnostic learnability, by controlling the rate at which 7 approaches zero to be faster than the rate at which e approaches zero. With this intuition in mind, we will now describe the construction and proof of this theorem.
Proof. We first define the distributions in 2g. Let {A, c NNiE N} be an enumeration of all finite subsets of N. Define distributions over N x N as follows:
1 Gi.j. (1- ((000) + +1 - UAX((141) + 01122542)
(I)
where, for every finite set W, Uw denotes the uniform distribution over W. For a monotone, super- linear function g : N + N, we now let 2g {9: i, E N). The first bullet point of the theorem (the class is learnable) follows from Claim 3.2 and the second bullet point (the class is not robustly learnable) follows from Claim 3.3
Claim 3.2. For monotone function g N- + N, let 2, - (1. ;i,j E NJ. Then, the sample complexity of 2g in the realizable case is upper bounded by
n (e. 8) < log(L/))g(1/E).
This claim can be proved by showing that the following learner defined by
A(S) = (1...o
if (i. 2)) E ((0.0) otherwise
7

---

is successful learner in the realizable case. Intuitively, this learner is successful for distributions (.j-o(s) for which j large (i.e., j > }), since this will mean that (rv(9....0))) (o.n)) is small. Furthermore, it is successful for distributions {.jي(j)) for which j is small (i.e., upper bounded by some constant dependent on E), because this will lower bound the probability 1/g(i) of observing the indicator bit on (i,2j + 2). Once the indicator bit is observed the distribution will be uniquely identified.
Claim 3.3. For every function E w(n) the class 2g is not a-robustly learnable for any >> O.
This claim can be proven by showing that for every a, there is 17, such that the class of distributions @' such that for every q' E Q' there is q 2g with drv(g, (g, < which is not ax) an7-weakly learnable In particular, those for every q' Q' there is q E 2g and p such that q = (1 17)y' + 1/g. We construct this class and show that it is not learnable by using the construction and Lemma 3 from LBD23]
3.1 Existence of sample compression schemes
Sample compression schemes are combinatorial properties of classes that imply their learnability. For a variety of learning tasks, such as binary classification or expectation maximization class has sample compression scheme if and only if it is leamable [MY16] BHM 171. For classification tasks, sample compression for realizable samples implies agnostic sample compression. 1ABDH*20 used compression schemes show learnability of classes of distributions in the realizable case, but left open the question if for learning probability distributions, the existence of realizable sample compression schemes implies the existence of similar schemes for the non-realizable (agnostic, or robust) settings. We provide a negative answer to this question.
More concretely, let Q be class of distributions over some domain X. A compression scheme for Q involves two agents: an encoder and a decoder.
The encoder knows distribution q and receives sample S generated by this distribution. The encoder picks a bounded size sub-sample and sends it, possibly with a few additional bits to the decoder.
The decoder receives the message and uses an agreed upon decoding rule (that may depend on Q but not on q or 5) to constructs a distribution p that is close to q.
Of course, there is some probability that the samples are not representative of the distribution q. in which case the compression scheme will fail. Thus, we only require that the decoding succeed with constant probability.
We say that a class Q has a sample compression scheme (realizable or robust) if for every accuracy parameter >> 0, the minimal required size of the sample S, and upper bounds on the size of the sub-sample and number of additional bits in the encoder's message depend only of Q and (and are independent of the sample generating q and on the sample S).
realizable compression scheme is required to handle only g's in Q and output p such that drv (p. q) < E, while robust compression scheme should handle any q but the decoder's out- put p is only required to be minge (p. 9) E close to q.
Theorem 3.4 (Formal version of Theorem 1.8p. For every a E R, the existence of realizable compression scheme, does not imply the existence of c-robust compression scheme. That is, there a class Q that has a realizable compression scheme, but for every a E R, Q does not have an a-robust compression scheme.
We note that this class has a compression scheme of size 1. However, from [ABDH+ we know that having a a-robust compression scheme implies a-agnostic learnability. We showed in Theorem T.6 that for every a and for every superlinear function g, the class 2, is not a-agnostically learnable. It follows that 2g does not have an a-robust compression scheme.
Proof. Consider the class Q = Q, from Section 3
"e provide definition for e-weak learnability as Definition D.2 is what would usually be referred to as (1/2- e) we-k learnability in the supervised learning literature. For simplicity, because e is our parameter of interest, reparameterized the definition to be more intuitive.
We note that the definition we provide

---

In Section E
we present a precise quantitative definition of sample compression schemes, as well as the proof that the class 2g has a sample compression scheme of size
Implications of Private Learnability
Qualitatively speaking, differentially private algorithms offer form of "robustness" the output distribution of differentially private algorithm insensitive to the change of a single point in its input sample. The relationship between privacy and notions of "robustness" has been studied under various settings, where has been shown that robust algorithms can be made private and vice versa [D09 GH22 HKMN233.
For distribution learning, we find that: (1) the requirement of approximate differentially private learnability also does not imply (general) robust learnability; and (2) the stronger requirement of pure differentially pirvate learnability does imply robust learnability.
Definition 4.1 (Differential Privacy (DMNS06)). Let X be input domain and Y to be output domain. randomized algorithm : X + is (e, ddffferrretl private (DP) if for every I, I, X that differ in one entry.
P[A(x) E B) -(A(Z')) E +
for all BYY.
If is (s, 8)-DP for 8 > O, we say it satisfies approximate DP. If it satisfies (e. 0)-DP, we say it satisfies pure DP.
Definition 4.2 (DP learnable class). We say that class C of probability distributions is (approximate)
DP learnable if there exists a randomized learner A and a function ne : (0, 1)a - N, such that for every probability distribution p C, and every (a,, B, E, E (0, 1),, for 2 B,e,,
1. is (e,8)-DP; and
2. The probability over samples of size n drawn ii.d. from the distribution p, as well as over the randomness of A that
drv(p, a
is at least 1 B.
We say C is pure DP learnable if a learner can be found that satisfies (c, 0)-DP, which case the sample complexity function ne: (0, 1)3 - N does not take 5 as a parameter.
Theorem 4.3 (Approximate DP learnability vs. robust learnability).
1. If class Q is approximate DP learnable, then Q is n-additive 2-robustly learnable for any 1) E (0, 1/4).
2. There exists an approximate DP learnable class Q that is not a-robustly learnable for any 1.
Note that the first claim is immediate from Theorem 1.5 learnability. To prove the second claim, we show that the learner for the class Q described in Theorem 3.T be made differentially private by employing stability-based histograms (BNS16). The proof appears in Section F
since approximate DP learnability implies
Theorem 4.4 (Pure DP learnable vs. robustly learnable). Ifa class Q is pure DP learnable, then Q 3-robustly learnable.
The proof relies on the finite cover characterization of pure DP learnability.
Proposition 4.5 (Packing lower bound, Lemma 5.1 from BKSWI9). Let C be a class of distributions, and let > O. Suppose Pa is a-packing of C, that is, Pa S C. such that for any * 9 E
Pas d (p. q) a.
Any &DDP algorithm A that takes n i..dd. samples S from any E and has drv (p. A(S)) < a/2 with probability 2 9/10 requires
log Pal
log 10
n1
E

---

Proof of Theorem 4.4 Let a, 3 > 0. Pure DP learnability of Q implies that there exists 1-DP algorithm App and n n / 12. 1/10, 1) such that for any p E Q. with probability 2 9/ over the sampling of n i..dd samples S from as well as over the randomness of the algorithm Apr, we have drv (p, Apr(S)) S a/12. By Proposition 4.5 any az /6-pacckng Pa/o of Q has
iPajll S exp (m) (10/9)-
Let Q be such a maximal o 6--pkkkiig. By maximality, 2 also an a/6-cover of Q. Hence, running Yatracos' 3-robust finite class learner (Theorem A.1 A over Q with
n n = log 0 + log(1/3)
(a/2)²
samples drawn i.i.d. from p yields, with probability 2 1
drv(p, A(S)) s min : ②) + a/2
s 3(min(drv :' E Q) a/6) + a/2
= =3 (min(drv(p. p/ E Q +
Note that Yatracos' algorithm for hypothesis selection can be replaced with pure DP algorithm for hypothesis selection (Theorem 27 of [AAK2I]) in order to achieve the following stronger implication.
Theorem 4.6 (Pure DP learnable vs. robustly learnable). Ifa class Q is pure DP learnable, then Q is pure DP 3-robustly learnable.
Conclusions
We examine the connection between learnability and robust learnability for general classes of probability distributions. Our main findings are somewhat surprising that, in contrast to most known leaning scenarios, learnability does not imply robust learnability. We also show that learnability does imply additively robust learnability. We use our proof techniques to draw new insights related to compression schemes and differentially private distribution learning.
Acknowledgments
Thanks to Argyris Mouzakis for helpful conversations in the early stages this work. AB was supported by an NSERC Discovery Grant and David R. Cheriton Graduate Scholarship. GK was supported by a Canada CIFAR Chair, an NSERC Discovery Grant, and an unrestricted gift from Google. TL supported by Vector Research Grant and Waterloo Apple PhD Fellowship in Data Science and Machine Learning.
References
[AAK21] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high nigh-dimensional gaussians. In Proceedings of the 32nd International Conference Algorithmic Learning Theory, ALT '21, pages 185-216. JMLR, Inc., 2021.
[AAL21] Ishaq Aden-Ali, Hassan Ashtiani, and Christopher Liaw. Privately learning mixtures of axis-aligned gaussians. In Advances in Neural Information Processing Systems 34, NeurIPS 21. Curran Associates, Inc., 2021.
(ABDH+18) Hassan Ashtiani, Shai Ben-David, Nicholas Harvey, Christopher Liaw, Abbas Mehra- bian, and Yaniv Plan. Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes. In Advances in Neural Information Processing Systems 31, NeurIPS '18 pages 3412-3421. Curran Associates, Inc., 2018.
[ABDH+20] Hassan Ashtiani, Shai Ben-David, Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learn- ing of gaussian mixtures via compression schemes. Journal of the ACM, 67()):2:1 32:42, 2020.
10

---

[AF]* 18] Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Maximum selection and sorting with adversarial comparators. Journal of Machine Learning Research, 19(1):247722577 2018.
[3KT*23] Daniel Alabi, Pravesh K Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang. Privately estimating a Gaussian: Efficient, robust and optimal. In Proceedings of the 55th Annual ACM Symposium on the Theory of Computing, STOC '23, New York, NY, USA, 2023. ACM.
[AM20] Marco Avella-Medina. The role of robust statistics in private data analysis. Chance 33 2020.
[AS721] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Proceedings of the 32nd International Conference on Algorithmmc Learning Theory, ALT '21, pages 48-78. JMLR, Inc., 2021.
[BBK+22] Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, and Shay Moran. Statistically near-optimal hypothesis selection. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, FOCS '21, pages 909-919, IEEE Computer Society, 2022.
[BDJ+22] Ainesh Bakshi, Hiis Diakonikolas, He Jia, Daniel M Kane, Pravesh K Kothari, and Santosh Vempala. Robustly learning mixtures arbitrary Gaussians. In Proceed- ings of the 54th Annual ACM Symposium on the Theory of Computing, STOC '22, pages 1234-1247, New York, NY, USA, 2022. ACM.
[BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapmik-Chervonenkis dimension. Journal of the ACM, 36(4):929- 965, 1989.
[BGS+21] Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthi- nou. Covariance-award private mean estimation without private covariance estimation. In Advances in Neural Information Processing Systems 34, NeurIPS '21. Curran Associates, Inc., 2021.
[BHM+17] Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, and Amir Yehuday- off. A learning problem that is independent of the set theory ZFC axioms. CoRR, abs/1711.05195 2017.
[BKM19] Olivier Bousquet, Daniel M. Kane, and Shay Moran. The optimal approximation factor in density estimation. In Proceedings of the 32nd Annual Conference Learning Theory, COLT '19, pages 318-341, 2019.
[BKSW19] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothe- sis selection. In Advances in Neural Information Processing Systems 32, NeurIPS '19, pages 156-167. Curran Associates, Inc., 2019.
[LMT222] Guy Blanc, Jane Lange, Ali Malik, and Li- Yang Tan. On the power of adaptivity in statistical adversaries. In Proceedings of the 35th Annual Conference Learning Theory, COLT '22, pages 5030-5061, 2022.
[BNL12] Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In Proceedings of the 29th International Conference on Machine Learning, ICML 12, pages 1467-1474. JMLR, Inc., 2012.
[BNS16] Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning of multiple concepts. In Proceedings of the 7th Conference on Innovations in Theoretical Computer Science, ITCS 16, pages 369-380, New York, NY, USA, 2016. ACM.
[BPS09] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In COLT 2009 The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
11

---

[BS19] Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. In Advances in Neural Information Processing Systems 32, NeurlPS '1, pages 181-191. Curran Associates, Inc., 2019.
[CDSS13] Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun. Learning mixtures of structured distributions over discrete domains. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 11, pages 1380-1394, Philadelphia, PA, USA, 2013. SIAM.
[CDSS14a] Siu On Chan, Iiaas Diakonikolas, Rocco A. Servedio, and Xiaorui Sun. Efficient density estimation via piecewise polynomial approximation. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing, STOC' '14, pages 604-613, New York, NY, USA, 2014, ACM.
[CDSS144] Siu On Chan, Iai Diakonikolas, Rocco A. Servedio, and Xiaorui Sun. Near-optimal density estimation in near-lineat time using variable-widee histograms. In Advances in Neural Information Processing Systems 27, NIPS '14, pages 1844-1852. Curran Associates, Inc., 2014.
[CWZ21] T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825-288) 2021.
[DDS12] Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. Learning Poisson binomial distributions. In Proceedings of the 44th Annual ACM Symposium on the Theory of Computing, STOC 12. pages 709-728, New York, NY, USA, 2012. ACM.
[Dia16] Ilias Diakonikolas. Learning structured distributions. In Peter Bühlmann, Petros Drineas, Michael J. Kane, and Mark J. van der Laan, editors, Handbook of Big Data, pages 267-2833 Chapman and Hall/CRC, 2016.
[DK14] Constantinos Daskalakis and Gautam Kamath. Faster and sample near-optimal algo- rithms for proper learning mixtures of Gaussians. In Proceedings of the 27th Annual Conference on Learning Theory, COLT 14, pages 1183-1213, 2014.
[DK22] Ilias Diakonikolas and Daniel Kane. Algorithmic figh-DDimnssonal Robust Statistics. Cambridge University Press, 2022.
[DKK+16] Iliss Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 16,, pages 655-664, Washington, DC, USA, 2016. IEEE Computer Society.
[DKK+17] Iliss Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning, ICML. '17, pages 999-1008. JMLR, Inc., 2017.
[DKK 18] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robustly learning a Gaussian: Getting optimal error, efficiently. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18 Philadelphia, PA, USA, 2018. SIAM.
[DKK+19] Ilis Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. Sever: A robust algaraago for stochastic optimization. In Proceedings of the 36th International Conference on Machine Learning, ICML '19, pages 1596-1606. JMLR, Inc., 2019.
[DKS17] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of tigh-dimensiooal Gaussians and Gaussian mixtures. In Proceedings of the 58th Annual IEFE Symposium on Foundations of Computer Science, FOCS 17, pages 73 73-84, Washington, DC, USA, 2017. IEBE Computer Society.
12

---

[DL96] Luc Devroye and Gábor Lugosi. A universally acceptable smoothing factor for kernel density estimation. The Annals of Statistics, 24(6):2499-2514 1996.
[DL97] Luc Devroye and Gábor Lugosi. Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes. The Annals of Statistics, 25(6):2626-286 26377 1997.
[DL01] Luc Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer, 2001.
[DL09] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the 41st Annual ACM Symposium on the Theory of Computing, STOC '09, pages 371-380, New York, NY, USA, 2009. ACM.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography. TCC '06, pages 265-284, Berlin, Heidelberg, 2006. Springer.
[GFH+21] Jonas Geiping. Liam Fowl, W Ronny Huang, Wojciech Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein. Witches' brew: Industrial scale data poisoning via gradient matching. In Proceedings of the 9th International Conference on Learning Representations, ICLR 221, 2021.
[GH22] Kristian Georgiev and Samuel B Hopkins. Privacy induces robustness: Information- computation gaps and sparse mean estimation. In Advances Neural Information Processing Systems 35, NeurIPS '22. Curran Associates, Inc., 2022.
[GKK+20] Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhi- wei Steven Wu, and Huanyu Zhang. Locally private hypothesis selection. In Proceed- ings of the 33rd Annual Conference on Learning Theory, COLT '20, pages 1785-1816, 2020.
[GTX+20] Micah Goldblum, Dimitris Tsipras, Chulin Xie, Xinyun Chen, Avi Schwarzschild, Dawn Song, Aleksander Madry, Bo Li, and Tom Goldstein. Dataset security for machine learning: Data poisoning, backdoor attacks, and defenses. arXiv preprint 1rXiv:2012.10544, 2020.
[Hau92] David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78-150, 1992.
[HKLM22] Max Hopkins, Daniel M Kane, Shachar Lovett, and Gaurav Mahajan. Realizable learning is all you need. In Proceedings of the 35th Annual Conference on Learning Theory, COLT '22, pages 3015-3069, 2022.
[HKM22] Samuel B Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via sum-of-squares exponential mechanism. In Pro- ceedings of the 54th Annual ACM Symposium on the Theory of Computing, STOC '22, pages 1406-1417, New York, NY, USA, 2022. ACM.
[HKMN23] Samuel B Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robust- ness implies privacy statistical estimation. Proceedings of the 55th Annual ACM Symposium on the Theory of Computing, STOC '23, New York, NY, USA, 2023. ACM.
(HL18) Samuel B. Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM Symposium on the Theory of Comput- ing, STOC 18, pages 1021-1034, New York, NY, USA, 2018. ACM.
[Hub64] Peter J. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73-101 1964.
[JV23]] He Jia, Pravesh K Kothari, and Santosh S Vempala. Beyond moments: Robustly learning affine transformations with asymptotically optimal error. arXiv preprint 1222299.02.12289, 2023.
13

---

[JOR22] Ayush Jain, Alon Orlitsky, and Vaishakh Ravindrakumar. Robust estimation algorithms don't 't need know the corruption level. arXiv preprint SeXiv:2202..04553, 2022.
[KBG04] Daniel Kifer, Shai Ben-David, and Johannes Gehrke. Detecting change in data streams. In Mario A. Nascimento, M. Tamer Özsu, Donald Kossmann, Renée J. Miller, José A. Blakeley, and K. Bernhard Schiefer, editors, (e Proceedings of the Thirtieth Interna- tional Conference Very Large Data Bases, VLDB 2004, Toronto, Canada, August 31 September 3 2004, pages 180-191, Morgan Kaufmann, 2004.
[KMN099] Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In Proceedings of the 18th International World Wide Web Conference, WWW '09, pages 171-180, New York, NY, USA, 2009,
ACM.
[KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high- nigh-dimensional distributions. In Proceedings of the 32nd Annual Conference Learning Theory, COLT 19, pages 1853-19022 2019.
[KMR+94] Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie. On the learnability of discrete distributions. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, STOC '94, pages 273-282. New York. NY, USA, 1994, ACM.
[KMS22a] Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for private estimation and a generalized fingerprinting lemma. In Advances in Neural Information Processing Systems 35, NeurlPS '22. Curran Associates, Inc., 2022.
[KMS+ 22b] Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. A private and computationally--ffeeees estimator for unbounded gaussians. In Proceedings of the 35th Annual Conference on Learning Theory, COLT '22, pages 544-572 2022.
[KMV22] Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. In Proceedings of the 35th Annual Conference Learning Theory, COLT '22, pages 723-777, 2022.
[KSS18] Pravesh Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM Symposium on the Theory of Computing, STOC '18, pages 1035-1046, New York, NY, USA, 2018. ACM.
[KSU20] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Proceedings of the 33rd Annual Conference on Learning Theory, COLT '20, pages 2204-2235, 2020.
[KU20] Gautam Kamath and Jonathan Ullman. primer on private statistics. arXiv preprint arXiv:2005.000/0 2020.
[KV18] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science, ITCS 18, pages 44:1 14:99, Dagstuhl, Germany, 2018. Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik.
[LBD23] Tosca Lechner and Shai Ben- Impossibility of characterizing distribution learn- ing a simple solution to a long-standing problem, 2023.
[LKKO21] Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. In Advances in Neural Information Processing Systems 34, NeurIPS '21. Curran Associates, Inc., 2021.
[LKO22] Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. Proceedings of the 35th Annual Conference on Learning Theory, COLT '22, pages 1167-1246, 2022.
14

---

[LKY23] Yiwei Lu, Gautam Kamath, and Yaoliang Yu. Exploring the limits of model-targetee indiscriminate data poisoning attacks. In Proceedings of the 40th International Confer- ence on Machine Learning, ICMI. '23, pages 22856-22877 JMLR, Inc., 2023.
[LM21] Allen Liu and Ankur Moitra. Settlin the robust learnability of mixtures of gaussians. In Proceedings of the 53nd Annual ACM Symposium on the Theory of Computing, STOC '21, pages 518-531, New York, NY, USA, 2021. ACM.
[LM22] Allen Liu and Ankur Moitra. Learning GMMs with nearly optimal robustness guaran- tees. In Proceedings of the 35th Annual Conference on Learning Theory, COLT '22, pages 2815-2895, 2022.
[LRV16] Kevin A. Lai, Anup B. Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 16, pages 665-674, Washington, DC, USA, 2016. IEEE Computer Society.
[LS17] Jerry Li and Ludwig Schmidt. Robust proper learning for mixtures of Gaussians via systems of polynomial inequalities. In Proceedings of the 30th Annual Conference Learning Theory, COLT 17, pages 1302-1382, 2017.
[MS08] Satyaki Mahalanabis and Daniel Stefankovic. Density estimation in linear time. In Proceedings of the 21st Annual Conference Learning Theory, COLT "08, pages 503-512, 2008.
[MY16] Shay Moran and Amir Yehudayoff. Sample compression schemes for VC classes. J. ACM, (3(3):21:1-21:11 2016.
[RJC22] Kelly Ramsay, Aukosh Jagannath, and Shoja' eddin Chenouri. Concentration of the exponential mechanism and differentially private multivariate medians. arXiv preprint arXiv:2210.06459, 2022.
[SB14] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning- From Theory to Algorithms. Cambridge University Press, 2014.
[SCV18] Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: A criterion for learning in the presence of arbitrary outliers. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science, ITCC '18, pages 45:1-45:21, Dagstuhl, Germany, 2018 Schloss Dagtuhh--LcibnizzZeentrr fuer Informatik.
[SKL17] Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. In Advances in Neural Information Processing Systems 30, NeurlPS 17, pages 3520-3532. Curran Associates, Inc., 2017.
[SM22] Aleksandra Slavkovic and Roberto Molinari. Perturbed M-estimation: A further inves- tigation of robust statistics for differential privacy. In Alicia L. Carriquiry, Judith M. Tanur, and William F. Eddy, editors. Statistics the Public Interest: In Memory of Stephen E. Fienberg, pages 337-361. Springer, 2022.
[SOAJ14] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. Near- optimal-sampi estimators for spherical Gaussian mixtures. In Advances in Neural Information Processing Systems 27, NIPS '1, pages 1395-1403. Curran Associates, Inc., 2014.
[Tuk60] John W. Tukey. A survey of sampling from contaminated distributions. Contributions to Probability and Statisties: Essays in Honor of Harold Hotelling, pages 1960.
[Va184] Leslie Valiant, theory of the learnable. Communications of the ACM, 27(11):1134 1142, 1984.
[VC71] Vladimir Naumovich Vapnik and Alexey Yakovlevich Chervonenkis. On the uni- form convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264-280, 1971.
15

---

[VC74] Vladimir Vapnik and Alexey Chervonenkis. Theory of Pattern Recognition. Nauka, 1974.
[Ya855] Yannis G. Yatracos. Rates of convergence of minimum distance estimators and Kol- mogorov's entropy. The Annals of Statistics, 13(2):768-774, 1985.
16

---

A Additional Preliminaries
We recall a classic theorem for the problem of hypothesis selection. Given a set of candidate hypothesis distributions, the algorithm selects one which is close to an unknown distribution (to which we have sample access). The requisite number of samples from the unknown distribution is logarithmic in the size of the set of candidates.
Theorem A.1 (Yatracos' 3-robust learner for finite classes (Theorem 4.4 of LABDH based on Theorem of [Yat85])). Let be a finite class of distributions over a domain X. There exists an algorithm A such that for any (ax, (3) E 1)² and for any distribution over X, given sample S size
m = O log [C| 1og((1/)
g2
drawn i.idd from p. we have that with probability 2 8,
(p A(S)) < min(drv(0, p') p' E EC) +
We also use the following form of the Chernoff bound. Proposition A.2 (Chernoff bounds). Let X Ee X; X; from Bernoulli(p)- For any (0, 1), PpX/mm (1 t)p] exp(-Impp/2)
where Xm... are independent draws
B Learnability Implies Additive Robust Learnability
In this section, we provide the proof for Theorem 1.5
Theorem 1.5. Any class of probability distributions Q which is realizably learnable, is also ry- additively 2-robustly learnable for every 1 E (0, 1/4).
Proof. Recall that Q is a class of probability distributions which is realizably learnable. We let AD be a realizable learner for 2, with sample complexity noo Let accuracy parameters E, 6 >> be arbitrary. 162( (((2+ 25 )ny log( +og)) (R)))
We will define 2 max ( (g. 3) 162(1++ogg())
and 2
162(1+log(3)) and n4 + n2 be their sum. 22
Our additive robust learner will receive sample (ng (1 1)p) of size n. We can view subset S' C S as the "clean" part, being i.i.d. generated by The size of this clean part |S"| is distributed according to binomial distribution Bin(n, n)) By a Chernoff bound (Proposition A.2
we get
P
n'
1
E m]
<P n' <
n
n
P
5) 9
(1 17)
S exp
2
n (1 1) /2) exp
6²
1)
exp
s² 162
1
3
162
Thus, given that n = + n2 > 2( 162(1+log( ()
with probability at least 1 S. we have n' 2 1 )) For the rest of the argument we will now assume that we have indeed n' - G). The learner now randomly partitions the sample S into S1 and S2 of sizes m and 122, respectively. Now let S
2²
nS' and S S be the intersections of these sets with the clean set 5", and ní and ní be their respective sizes. We note that ni ~ Hypergeometric((, n' n and 1/2 Hypergeometric(n, n', n2) Thus, assuming m' 2 m(1
5) using Proposition A.2
we have that
Pr S < (1 1-
28
m S =
'Recall that Hypergeometric(N K, n2) is the random variable of the number of "successes" when n draws made without replacement from of size N, where K elements of the set considered be successes.
17

---

and
Pr |S
1 (1-7
2$
S
# =
9
where the probability over the random partition of We note that by our choices of ni and n2, with probability 1
28 the clean fractions of S and S2 (namely 5.
Si S
are each at least and
(1 ).
Let
H = A7((")) c S1 with |S"|
25
77
9 n1
be the set of distributions output by the realizable learning algorithm A when given as input all possible subsets of S1 of size exactly (1
2e
90 we know that this set 9 n1- For < 2
of distributions | is of size (11 (1- 17 nn
S ni 2 By the guarantee of the realizable
learning algorithm A if there exists a "clean" subset S C Si where S/] 2 (1 - 7 - )) (i.e., there exists a candidate distribution q" E H with
i pm )) then with probability dTv(P. = 5
We now define and consider the Yatracos sets
For every 4s 4s.9j E H. define the Yatracos set between
and to be Asj = {x g (x) 2 (x)) We let
((H) {A., c X 9. E H}
denote the set of all pairwise Yatracos sets between distributions in the set M.
We now consider the A-distance [KBG04] between distributions with respect to the Yatracos sets, i.e., we consider
dyca (') sup ( (B)) (E)(H)
This distance looks at the supremum of the discrepancy between the distributions across the Yatracos sets. Consequently, for any two distributions p' we have drv (p', g') 2 d (p', g'), since total variation distance is the supremum of the discrepancy across all possible sets. Furthermore, if d'.p' / E H. then drv (p', g') dy(R) (v/ q'), since either of the Yatracos sets between the two distributions serves set that realizes the total variation distance between them.
Suppose there is some 9º E H with drv (p. 5- Then for every q H:
drv(p.g) g) I (p.(p."") + drv(a",
e
IA
+ dyyn)(( (4",4)
9
+ dyr (q",p) + d (p.9)
9
IA IA
+ drvly', ,p) + dy(R) (v,
9
28
9 + du
Lastly, we will argue that we can empirically approximate dyyee (p, which we can then use select hypothesis. We note that, since V(H) finite set of size
)m
25 )m ) < ((1) (g+ 3))}²
(17 711
2 2n )m we have uniform convergence with respect to n1
9These sets are also sometimes called Scheffé sets in the literature.
Note that this definition asymmetric: A., # Ag,i.
A collection of sets W has the uniform convergence property if for every (e, E (0, 1)² there is number mw(e, 8) such that for every probability distribution p, with probability 2 6) over samples S of size
18

---

((H). Recall that, we assumed that there is "clean" subsample S C S2, which is i.idd. distributed according to p and of size (1 3े 7)), We also note that the clean samples S and S2 are drawn independently from each other. Thus with probability respect to (H). For sample Sp and set C X, let us denote SBBB) [8aBBl Because of the [So]
6 St is 5-representative of p with 5
-rrepresentativensss of 5% we have for every B E y(H):
Ip(B) (y 9*
Thus,
Ip(B) (B(
1Sp n B|
(B)
|52
P(B) 1S n B]
pBB) 15 0 B + (1) + )112
$ max
S2
p(B) ( (S)
p(B) (B) S + (17 + 22 )n2
max
9
122
72
((B) (1 (1- 17 9
23
(B) (1
2r
9 12 + (1+ 9 n2
< max
5% (B) p(B))
12
< max
IB(B) (B)] + (B) (1 (1-
23
S B)
p(B) (8)
(1-
25
)
9
38
77 BBB (B) 11 23
23
max
35 7/ p(B) SK + (B(
-+ 2:
25
< max
17 +
9
35
17 (BB) (B)) + (B) 7 2:
+ 2:
|
max
35
+ [B - 1 n 2:
}
< mmxx
17: 9
max
33
17 9
ε +
1 2g
}
38
9 + 1]
Let the empirical A-distance with respect to the Yatracos sets be defined by
dy(r)(g,5)=
sup BEdy(K)
Ia(B) S(B))-
n > nw 6) generated i.i.d. by p. a sample is s-representative for W with respect to p. Namely, for every
4 E W. [AnS]
p(4) <. If W is finite then ww(ss, ō) < bog(1)))) For more details see Chapter
4 in SSB14.
19

---

Now if the learner outputs / arg migmin, we get that with probability 1 1
9ER (yA (g. S), then putting all of our guarantees together,
2=
dTv(g.P) -
+ dycis (..p)
9
55
+ dy(R) (1,
9
55
+ + dycR) (4 .2)
9
85
+ 2n + dy(t) (q" .))
9
85
+ 2n + +
9
C Robust Learnability with Subtractive Contamination Implies Robust Learnability with General Contamination
In this section we will provide the proof for Theorem 1.7
Theorem 1.7. If class C is n-subtractive a-robustly learnable, then it is also 7-(2ax + 4) rooustly learnable.
Proof. Let be a concept class that is v-subtractively a-robust learnable. Then there exists successful n-subtractive a-robust learner Asuh with sample complexity nayh for the class C. Let 91 and 5 and be arbitrary.
2
S max 2n ( / 11 25), 162(1+1og($))
Let
and 112
(din+ mn ( (B)) 162(1+log(
Lastly let m1 712
Let p E be arbitrary. The a-rj-robust learner receives a sample S ~ pm such that there is E such that drv (p. 9) n. Thus there exists distributions 9ı, Q2, gs. such that (1 1))1 + 1792 p and (1 7)41 + 43 = q. We now use the same learning strategy as Theorem 1.5: We split the sample randomly into two subsamples S1 and 52, where we use S1 to learn candidate sets and then use S2 to select the hypothesis from the candidate set. The goal both settings to find as close an approximation 91 possible. The candidate based on S₁ is created by feeding subsamples of S into the subtractively robust learner in such a way that with high probability one of the subsamples is guaranteed be i.i.d. generated by qi and thus (with high probability) yield good hypothesis. More precisely, the learner randomly splits the sample S into S and S2 with [S] = n. and |Si] = n2. We now define the "clean" part of S' S. i.e. the part of S' that is i.i.d. distributed according ς1- We note that the size of this "clean" sample SS"| = n' is a random variable and distributed according to the binomial distributions Binom(n, 1- 17). Now applying Chernoff bound, with the same argument in the proof of Theorem 1.5 we get that with probability 1 1- S we have n' 2 n(1 - 7) }.. Now let S S n S' and S% S2 S' be the "clean parts" of the subsamples S1 and S₂ respectively. The sizes SS = Te and SS = n² We note that ní ~ H Hyper gpperreemtriii n(1 17), n,) and
n/g H Hypergeometric(f n11 n), n2). Thus,
||S|| S
(1
1 (1-
31 2
Preandom split
n
S ee-
9
and
2s
Pr Trandom split
| <
1 1-
12
S e
9
20

---

Taking together the guarantees on our random splits and the size of n', we note that by our choices of vi and 122 with probability
38 the fractions of the parts that are i.i.d. generated by @i (namely 5.
18
and
are at least (1 - 1 )) Going forward we will assume that this is indeed the case. [SqT
TSTT
Let
i A (a) C Si with [$| (1 77
2s
n1 s.
Using our assumption that [S1 (1-1) 25 1n we know that there is SY C Sj with with Ag e H'.
As Sy 4i (1-7- )ms by the learning guarantee of Aga with probability 1 ÿ. there is candidate distribution q² E H with drv(p, (") S drv(p, Q1) + drv(qng)) .²") + (an + () (a + 1) 1 + 5-
We now consider the Yatracos sets. For every qi, Oj E H. let Arg = fx: g;(x)) 2 (3)} and let
((A) Ass X qr E R}
We now consider the A-distance KBG044 between distributions with respect to the Yatracos sets, i.e., we consider
d dscod(d'1))
sup BEX(H)
(p'(B) - (B))
We note, that for any two distributions p' d have drv d)) (f g'). Furthermore,
if d'pp' E H. then drv ,') dy(r)(('.')) Assume there is q² H with drv(p.q") s (a 1)n + 5. then for every q H.:
drv(p.g) < drv(p,
+ drv(d' ε
s (a + 1)m
+
+ dy(p)(9" ())
9
8
s (a 1)m
+
+ d dyr (q" p) + y (p. 4)
9
{a 1)m +
+ drv(a", p) + dyrro (p.9)
9
28
2 - 1)n +
+ (P
9
Lastly, we will argue that we can empirically approximate dyy( (p. q). which we can then use to
select hypothesis. We note that, since )'(H2 is finite set of size [J(AA) ((1-1 mmm)) ) s nig and by our
2 Jn, have uniform convergence with respect to ((H)). Recall that S/22 41 previous assumption vig n2 (1 1)
2=.. Thus by our choice of nı with probability 1 1- g there is 5% C S C S2 with |S|| (1
2x) nz such that S g-representative of : with respect to ((A)). For sample So and set B C X, let us denote (B) s-representativeness of S2 have for every B ((H):
[8,0B| Because of the [So]
(B) <
Thus.
21

---

(B) S2()] S 1 (B)
+ (B)) (B)
SSa 0 BI
ISS BB
9
S
|S
9 11
|S2 0 B
|S n
722
(2 - 1j )
|S2 n ( - 2)) - | nB)
m
+
9
(1 17 22 |nz
[155 n B + (17 +
23 )12)(
-1 - 29 - SS 0 B1
max
9
9
11-1-
25
)m²
9
10150 0 BB - 1] 2:
- S B1|
9
(1 1--1 17 9 n2
IA
0
K(SS n B3 + (17 + )22) 17 - ()) ((1 77
23 IS n B + (17 + > n BI)
+ max
n2 17
25
9
(1 + 24
g
122 17
[ + 23 m)2211
1) 25) 15 n (1) + 2F
(1 + 25
+ max
(1- 1| 25 )
(1 - 17
2r 9
1 +
25 g
(n2(1 (1 -7 ))
28
+ max
.7 +
9
(1 - 11
25
9 )m12
9
28
9
17
+
9
+
Let us remember that the empirical A-distance with respect to the Yatracos is detined by
BEY (1. sup (q( S(B)
Now if the learner outputs E arg gin gEn dycn (g, S2), then putting all of our guarantees together, with probability ö we get
28 + dy(Å.p)
drv(2.p) 2( + 1)n
28
2 + 1)n
+ dy(ी (1)) + dy(g1,)) p)
28
+ n + (n+ + 31
2((a + 1)m +
+ dy S2)
9
2((a + 2)n +
+ dy(9. Sz)
58
<2(a + 2)n
+ dy(9" 82)
58
(n+ + 38
<2 + 2)n
+
g dy(ą" .1)
8c
< (2a + 3)n +
+ p)
9
< (2a + +
22

---

D Learnability Does Not Imply Robust Learnability
We start with an upper bound, showing that our class 2, is realizably learnable.
Claim 3.2. For monotone function g: N - N, let 2g (B.iatt) : E NJ. Then, the sample complexity of 2g in the realizable case is upper bounded by
n (E. - (og())))((//E)
Proof. Let the realizable learner A be
A(S) gi.iss
if (i, + E S
((0.0)
otherwise
Note that for all -errealizable samples this learner is well-defined. Furthermore, we note that in the realizable case, whenever A outputs distribution different from δ(o,0). then A(S) outputs the ground-truth distribution, i.e., the output has TV-distance 0 to the true distribution. Lastly, we note, that for an i.dd sample 5 K(5 have the following upper bound for the learner identifying the correct distribution:
IP I' g a()
(A(S) = 9() = Ps [ii,2j + 2) E 5) 1 -1-10(11000))) 1/9(i)""
We note, that since is monotone function, if I 5,then g(i) s 9( and therefore,
(1 (1-1/) S (1/1/((1/=)))
Furthermore for (b)-o())> we have that drv (6(0,0) (o.)))))
Putting these two observations together, we get
( (1 1/9((///=))
if S
P (drv(A(() 9.5.0))) 2 E
if ] >
Thus, for every q 2gg
P P (AT((A())))) 2 (1/1/((1))) exp
n
((/E))
Letting the left-hand side equal the failure probability d and solving for n, we get,
n log 5 >
g(1/E) log(6)g(1/E) 2 n n Z log(6)g(1/e) -og log(1/0)g(1/s)
Thus, we have sample complexity bound of
no, ( (1g()))(o
Now, we show lower bound, that our class 2, is not robustly learnable. Before we do that, we require few more preliminaries. For distribution class and distribution p, let their total variation distance be defined by
drv 2) = inf dp
gEQ
We also use the following lemma from LBD23
Lemma D.1 (Lemma 3 from (LD23)). Let P n = {(1 1)8 + +nUAx (x : C [4M]] For
PRA we have n . 4) 2 k.
23

---

Finally, we recall the definition of weak learnability, which says that distribution class is learnable only for some particular value of the accuracy parameter.
Definition D.2. A class 2 is e-weakly learnable, if there is a learner A and sample complexity function n : (0, 1) + N, such thatfor ever ò E (0, 1) and every E Q and every n 2 n()).
Paupr [dr (A(S), - < 6.
Learnability clearly implies e-weak learnability for every : (0, 1). While in some learning models (e.g., binary classification) learnability and weak learnability are equivalent, the same is not true for distribution learning [BD22]
We are now ready to prove that 2g is not robustly learnable.
Claim 3.3. For every function g E w(n) the class 2g not a-robustly learnable for any a > 0.
Proof. Consider
th.j - (1- ((0,0) + (UXx(e511)
Note that drv ( 2g) = abi Therefore, in order to show that 2g is not a-robustly learnable, it is sufficient show that there are and E, such that the class 2j {9h i E N} is not (G) + -)weakly learnable.
We will now show that for any y < 1 the class 0 = [hh : N) is not y-weakly learnable.
85+
Recalling notation from Lemma D.1 we note that that for every N the class P3.4s j.4 C 2j. By
monotonicity of the sample complexity and Lemma D.I we have no; 3 #) 2 P .5 #) 2 n
proving that this class is not weakly learnable.
Lastly, need to show that for every a, there and such that this claim holds for y S a +e). That is, we need show that there are and j. such that
9(3)
a + 5 <
1 8j
9
Let I. Now let g be any superlinear function, i.c., for every E IR, there te N. such that 1éj for every 2 te. gtt 2 ct. This implies that, for any a E R, there is j E N such that g(j) > 16ja. Thus for any super-linear function g and any R, the class Q, is not a-robustly learnable.
D.1 Proof of Theorem
The result of Theorem 1.6 follows directly from the construction of class 2g for Theorem 3. the
Claim 3.2 that shows this class realizable learnable, and an adapated version for Claim 3.3 which
states the following:
Claim D.3. For every a, there is g(t) E O(t)), such that for every 0 S S Iba the class Q, is not
sp-subtractvve ax-robuslly learnable.
Proof. Let be arbitrary. Let g: N + N be defined by g(t) 32at² for all E N. Now for every 0 S 7 S T there exists some j. such that i
a(3) S 1) S 16oj
such j. we consider the distributions
(1-1)) 6.0.0 + UALX(25+1))
th.5
as in the proof of Claim 3.2 Recall that the element of 2,, are of the form
gi.i.9()) = (1-1) ) 610.0) + ( - g(i) )--1)) UAxx(2511) + g(1) 6
24

---

Then we have,
8(0.0) (
1
1 U1ix125+11 +
1 -
U
(1.2++2)
9(i)
g(i)
1 5]
(0,0)
(3g(T) jo(i)
(9(i) -j
UAix(22+11
j
8 (1.2)+2)
j9(l)
9(5) (5))-1)
-1 1) ((1-
1 810.0) + -
j
1 (11 (1-1 ((000) -
+ g(i)
g(i)
i. ((1-3) 810,0) + +
des + g(t)
g(i)
Thus for every element Kh of the class 2 = foh : E N}. there a distribution p. such that (1 - n)gh, + 1p E Qg. That is, every element of Q results from the n-subtractive contamination of some element in Qg. Thus, for showing that 2, is not n-subtractive a-robustly learnable, it is sufficient to show, that 2 is not (an +e)- learnable for 16j As have seen in the proof of Claim 3.3 we can use Lemma D.1 to show that for every n, we have noy (g)) 4) 2 n. Lastly, we need that 87 an + E. or after replacing E, we need of g-
16j 2 an. This follows directly from the choice
E Existence of sample compression schemes
We adopt the [ABDH** + 20 definition of sample compression schemes. We will let C be class of
distribution over some domain X. A compression scheme for C involves two parties: an encoder and decoder.
The encoder has some distribution g E and receives n samples from q. They send succinct message (dependent q) the decoder, which will allow the decoder to output distribution close to q. This message consists of subset of size T of the n samples, as well t additional bits.
The decoder receives the samples and t bits and outputs distribution which is close to g.
Since this process inherently involves randomness (of the samples drawn from q). we require that this interaction succeeds at outputting a distribution close to with only constant probability.
More formally, we have the following definitions for decoder and (robust) compression scheme. Definition E.1 (decoder, Definition 4.1 20)) decoder for a deterministic function J U X" (0 1)" + C, which takes finite sequence of elements of X and a finite sequence of bits, and oulputs a member of
The formal definition of a compression scheme follows.
Definition E.2 (robust compression schemes, Definition 4.2 of ABDH 201). Let Let,, n t,t, (0. 1) +
Zzo be functions, and let 2 0. We say C admits (T, (r,t,n) r-robust compression if there exists decoder I for C such that for any distribution q E and any distribution on X' with (rv(p, q) S the following holds:
For any E E (0, 1), if a sample S is drawn from (=()) then, with probability at least 2/3, there exists sequence of at most TEE) elements of S, and sequence of at most t(E) bits, such that (L, Sr
Note that S and L are sequences rather than sets, and can potentially contain repetitions.
Theorem E.3 (Compression implies learning, Theorem 4.5 of [ABDH 20)). Suppose admits (T, f, n) r-robust compression. Let r'(s)((E) t(e). Then C can be max(3, -learedd in the agnostic setting using
(m/ (n( (5) log (6)
(o(n(())) log, log(1/0) = (n((()) (
(<//6) log n(e/6)
(5)
g2
g2
25

---

samples. If Q admits (T, n.) non-robust compression, then Q can be learned in the realizable setting using the same number of samples.
Theorem E.A. The class Q 2g from Section has compression scheme of message size (i.e., using just single sample point).
Proof. Let nee) be 10/g(E) and, give sample S of at least that size, let the encoder pick subset L(S) S be
{ [(i,2++2) (()
if (i,2j+ E otherwise
L(S)
Let the decoder output
if (i,2j + 2) E T. otherwise
J(L)
((000)
With this construction established, the analysis follows very similarly to the analysis in the proof of Claim 3.2
We note that the claim of Theorem 1.8 (and Theorem
3.4 follows directly.
F
Approximate DP learnability vs robust learnability
We prove the second claim in Theorem 4.3 by showing that the learner for the class Q described in Theorem 3.1 can be made differentially private by employing stability-based histograms [KKMN09
BNS16
Proposition F.1 (Stability-basee histograms [KMN09 BNSI6), Lemma 4. from (AL21 Let X be domain of examples. Let K be a countable index set, and let (ha) be a sequence of disjoint histogram bins over X. For every (a. e, 5) (0,1)*, 1)*, there is an (E, () algorithum that takes dataset S of size and with probability 2 1 B, outputs bin frequency estimates (fı) such that
1x E S:DE hKll
fv
S a
for all ls E K, so long as
log(1 log(1/38)
Ω
as
Proof of Theorem 4.3 Recall the realizably-buut-notrrbuuuyy learnable class of distributions 2g = ((i.ig(() i,j E N} over N² from Theorem 3.1 where : N. + N is a monotone, super-linear function and qi.j. is as defined in (T.
Fix (a, 3,c, (0, 1)a. We define our DP learner App for 2, as follows: we take sample S of size
n 22n log(L/(9/2)0) (1/4g(1/a))
+ 32 (o2goo(((//2))
and run the stability-based histogram from Proposition F.1 targeting (c, 5)-DP, with singleton histogram buckets (h.,,))). each h(.)) {(a,0) This yields frequency estimates (a..EE) with [((a,)) Hx E S: (a) < 1/4g(1/a) for all (a,b) E N² with
probability 2 - 8/2.. Then let
if f62212) 1/2g(1/a) otherwise.
ADr(S)=
180
Note that by post-processing App is indeed (8, 5)-DP. Now suppose (b.1-00) our unknown distri- bution. There are two cases:
26

---

If 1/j S a, conditioned on the success of the histogram algorithm, the only possible outputs of ADP og and (... so dTv (...a())) S a with probability 2 21-8/22
If j > we have 1/g(1/a) < 1/g(s). By the second term in and Chernoff bounds (Proposition we can conclude that
P (r E S +422j+2))
4g(1/a) 8/2.
7
If the above event does not and if the histogram algorithm does not fail, App outputs (.J.G) exactly. So drv (ADp(S), (ija())) 0 with probability B.
27


Reviews:
[{"review_id": "qrTFV1Ivla", "reviewer": "Reviewer_Xv71", "summary": "This paper study the connection between learnability and robust (agnostic) learnability for general classes of distributions in the framework of distribution learning. Differ from the PAC learnablity, they show that in the distribution learning setting the learnability does not always implies agnostic learnablity. They also explore related implications in the context of compression schemes and differentially private learnability.", "questions": "* I am a little confused about the definitions of adaptivity. In Definition 1.4 (1) and (3), what distribution does the new $\\eta m$ examples follow? If they follow $p,$ these definitions seem to make no sence. If these examples are drawn from some unkown distriburtion, how should I understand the definition of **adaptive robust** learnablity?\n\n* I would be very appreciated it if the authors can give some intuition about the contradiction between their findings and the results presented in [1].\n\nReference:\n[1] Max Hopkins et al. Realizable learning is all you need. Colt 2022.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* This paper is well organized and easy to follow, I enjoy reading it.\n* The result that learnability does not imply robust learnability is somewhat surpring.\n* The proofs are solid, by my judgement.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the kind review! Regarding your questions:\n\n**On the definitions of adaptivity:**\n\nIn Definition 1.4 (1), the sample $S'$ of size $\\eta m$ is arbitrary. Similarly, the sample $S’$ in (3) of the same definition is obtained by arbitrarily replacing a fixed fraction of instances in the sample with other arbitrary instances. \nIndeed, in both cases, one could more accurately replace “samples $S'$” with “arbitrary dataset $S’$”. We do not make any distributional assumptions on these manipulations (they do not arise from i.i.d. samples). Thus the adversary in this model is stronger than the one in definitions 1.1., 1.2 and 1.3, where we do make distributional assumptions on the added/replaced sample points.\n\n**On *Realizable Learning is All You Need*:**\n\nThe biggest difference between our setting and that of [1] is that we consider learning classes of distributions, whereas [1] considers learning classes of functions. In general, these two settings are incomparable, and thus there is no contradiction.  \n\nThe main idea of [1] is to learn a finite “cover” $\\mathcal H'$ (i.e., a set of hypotheses that is guaranteed to contain an epsilon-approximation for each hypothesis of the class) of possible labelings by the predefined hypothesis class $\\mathcal H$ on an unlabelled sample $S_U$; this is possible since there is a only a finite set of possible labelings. They then use ERM on a labeled sample $S_L$ and the class $\\mathcal H’$ to get a classifier with an agnostic learning guarantee. \n\nWe note that in the distribution learning setting, cover-learning is not possible, since there is no analogue of “a sample being consistent with a hypothesis”: there can be an infinite number of possible generating distributions of $S_U$ in the class (that cannot be covered by a finite set of distributions). Basically, we give an example of a class which has no finite epsilon-cover (in terms of TV distance), but realizable learning is still possible (using mass on points that uniquely defines a distribution the the class).\n\n—--------------\n\nIf you have any additional concerns, questions, or clarifications -- we would be happy to discuss further in the discussion phase.\n"}, {"review_id": "il8EQ0BH6y", "reviewer": "Reviewer_1ajk", "summary": "This paper studies distribution learnability, with a focus on the relationship between the realizable and the agnostic/robust settings. This relationship is also studied in the context of sample compression schemes and differential privacy.\n\nIn particular, the authors show separation results: learnability in the realizable setting implies learnability when an adversary can modify the training data by adding training samples. They show however that this does not hold when the adversary can remove part of training data. In fact the authors identify that an adversary having subtractive power implies robust learnability in the more general case where data can be replaced. In terms of connection to sample compression schemes, the main result is that the existence of sample compression schemes in the realizable setting does not guarantee the existence of robust sample compression schemes. Finally, they show that pure DP learnability implies pure DP learnability when the adversary can replace data, but if one considers approximate DP, the implication breaks for adversaries that can subtract data to the training set (but not for adversaries that can add data).\n", "questions": "- Terminology: robust and agnostic learnability are used interchangeably (e.g., l.32), which is in contrast to other set ups (e.g. binary classification), for which the two terms have vastly different meanings. The set up described on l.32-37 (and Defs 1.2 and 1.3) sounds more like the agnostic setting in spirit, where we want to compare the algorithm's output with the best possible one from the class $\\mathcal{C}$. In my mind, robustness implies the presence of an adversary which modifies data (at training or testing time), so more in line with definition 1.4. I think using robust and agnostic interchangeably is a bit confusing and I would appreciate some clarification on the matter (here and on a future version of the paper), perhaps a distinction like suggested above.\n \nGeneral comments:\n- Perhaps provide references for poisoning attacks on l.28, as it is particularly related to \"adaptative robustness\" (though this is in the context of classification).\n\n", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Good presentation, well written, big picture is given for most proofs and the paper easy to follow. The introduction is particularly thorough \n- The impact is quite broad, with applications to sample compression schemes and differential privacy\n- I believe these results would be of interest to the learning theory community \n- The technical contributions seems appropriate for NeurIPS, given the significance of the conceptual contributions \n\nDisclaimer: I am not very familiar with DP, so my assessment for the contributions is mainly based on Sections 1-3.\n", "weaknesses": "- Constant $\\alpha$ (Thm 1.5): do you have a sense whether $\\alpha=4$ the best one could hope for? This high constant seems to be a limitation of the work, in the sense that the only guarantee is that we are roughly at multiplicative factor of 4 away from the optimal distribution in the class $\\mathcal{C}$. It's a bit difficult to get a sense of the significance and the text could use some clarification.\n\nGeneral comments/things to fix:\n- p.2: \"total variance distance\" -> \"total variation distance\" (maybe include the mathematical definition too? No need for a new definition environment, just $d_{TV}(p,q)=...$) \n- Section 6.6 in the appendix does not have any text below it\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the kind review! We are glad the reviewer believes that our results would be of interest to the learning theory community – highlighting the breadth of settings considered and the significant conceptual contribution.\n\nIn the following, we address specific points raised by the reviewer.\n\n—---------------------\n\nRegarding the constant $\\alpha =4$ in Theorem 2.1 (6.3 in the supplementaries): \n\nWe thank the reviewer for this question. We carefully examined our proof again and were able to improve the bound to $\\alpha=2$. We did this by tightening the upper bound (page 16 of the supplementaries) on $|p(B) -S_2(B)|$ to $\\frac{2\\epsilon}{9} + \\eta$, instead of$ \\frac{3\\epsilon}{9} + 2\\eta$.\n\nThis was possible by bounding the second part of the max by using triangle inequality in the following way:\n\\begin{align*}\n|p(B) - ( S_2''(B)(1-\\eta - \\tfrac{\\epsilon}{9}) + (\\eta + \\tfrac{\\epsilon}{9}) )| &\\leq |p(B) - S_2''(B) + S_2''(B)(\\eta+\\tfrac{\\epsilon}{9}) - (\\eta + \\tfrac{\\epsilon}{9}) | \\\\\\\\\n&\\leq |p(B) - S_2''(B)| + |S_2''(B)(\\eta+\\tfrac{\\epsilon}{9}) - (\\eta + \\tfrac{\\epsilon}{9}) | \\\\\\\\\n&\\leq \\tfrac{\\epsilon}{9} +|S_2’’(B)-1| (\\eta + \\tfrac{\\epsilon}{9}) \\leq \\tfrac{2\\epsilon}{9} + \\eta.\n\\end{align*}\n\n\nThe last inequality holds  as $0 \\leq S_2’’(B) \\leq 1$.\n\nFurthermore, we note that $\\alpha=2$ and $\\alpha=3$ are often the optimal factors to expect in distribution learning settings, even for the case of finite distribution classes. For example, for proper agnostic learning the factor $\\alpha=3$ is known to be optimal for finite collections of distributions  (see [1], which holds for classes with only 2 distributions). Similarly the factor of $\\alpha=2$ is optimal if the notion of learning is relaxed to improper learners (see [2], also [1]). While we aren’t aware of lower bounds for the additive adaptive setting,  a multiplicative constant factor such as 2 is within expectations for these problems.\n\n**Regarding the terminology of robust vs. agnostic:**\n\nAs we mention in Definition 1.1 we use $\\alpha$-robust learning and $\\alpha$-agnostic learning interchangeably. The “robustness” we are considering is with respect to corruptions to the training data, and is referred to as such in work on algorithmic statistical estimation [3], as opposed to test-time corruptions as considered in the adversarially robust learning literature [4]. The agnostic setting in distribution learning indeed corresponds to robustness with respect to corruptions in training data; as agnostic learning is defined as follows: there exists some underlying class of distributions, but an adversary instead selects an arbitrary distribution from within a TV ball of the class to draw samples from. This is more frequently used to capture model misspecification, but could also be used to capture adversarial contamination of the distribution. \n\nThis is our non-adaptive setting (Definitions 1.2 and 1.3), though we note that this is also called the Huber contamination model in the robust statistics area of statistics. We thus emphasize that both “agnostic” and “robust” have been used to refer to this setting, depending on the community (where our paper is at their intersection). On the other hand, the adaptive version in Definition 1.4 is almost exclusively referred to in the algorithmic statistical estimation literature. Due to the overlapping terminology, we choose to use agnostic and robust interchangeably for all definitions, and differentiate between Definitions 1.2/1.3 and 1.4 using the terms adaptive and non-adaptive. We will clarify that we use these two terms interchangeably and why in the final version of the paper. \n\nThank you for the idea of including references to poisoning attacks. We will do so in the final version.\n\n—--------------------------------\n\nThanks also for pointing out some typos. We'll address those in the revised manuscript.\n\nIf you have any additional concerns, questions, or suggestions, we would be happy to discuss further in the discussion phase.\n\n**References**\n\n[1] Olivier Bousquet, Daniel Kane, Shay Moran. The Optimal Approximation Factor in Density Estimation. COLT’19.\n\n[2] Siu-On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun. Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms NIPS’14.\n\n[3] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust Estimators in High Dimensions without the Computational Intractability. STOC’16.\n\n[4] Omar Montasser, Steve Hanneke, and Nathan Srebro. VC Classes are Adversarially Robustly Learnable, but Only Improperly. COLT’19.\n"}, {"review_id": "36kOcayx8H", "reviewer": "Reviewer_2DNr", "summary": "This paper studies the interaction between learnability and several notions of \"robust\" learnability, wherein candidate distributions can be corrupted in various ways.  The authors show an equivalence between learnability and a robust version of learnability in which a contaminated distribution can be added to the nominal distribution.  The authors study how differential privacy interacts with learning, showing that DP can imply learnability under certain contamination models, but not others.  Sample compression schemes are also explored.\n\n**Overall assessment.**  This paper is strong on several fronts.  It considers a wide selection of problems related to distribution learnability.  And the technical quality of the paper is high.  On the negative side, I think the biggest drawback is the writing.  The clarity with which a paper like this is written is crucial, as the results are of a technical nature, thus requiring careful, clear explanations so that the reader can follow along.  In its current form, I think this paper falls short of the mark.  If the authors can demonstrably improve the writing and presentation, I will raise my score accordingly.", "questions": "See above.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "**Breadth of settings.**  This paper considers numerous problem settings spanning additive (and subtractive) contamination, differential privacy, learnability (in the sense of PAC learning), and sample compression.  One imagines that the scope of this paper could have been reduced, i.e., to the interaction of DP and learnability, and the paper would still constitute a solid contribution.  In an age when it can be advantageous to increase one's throughput by spreading content over multiple publications, I appreciated that the authors endeavored to give the reader the full picture capturing how learnability manifests on all of these different axes.\n\n**Soundness.**  From what I can tell, the paper is quite sound.  The paper presents informal discussions and in some cases informal proofs in the main text.  The appendix is fully rigorous, with each main result proved in its own subsection.", "weaknesses": "**Motivation/Relevance to practice.**  There is little to no motivation for the problem under consideration.  The authors begin the introduction with a description of the problem of distribution learning without mentioning why one might be interested in this problem and/or what bearing this problem has on practical ML settings.  It's certainly worth noting that this is a more theoretical paper, but even still, I think that the paper would be stronger -- and would appeal to a wider audience -- if the authors motivated the problem in a more verbose way.  As written, this paper would only be accessible or feel relevant to those who are already familiar with why distribution learning is a well-studied problem, which is a narrow slice of the ML/statistics community.  \n\n**Definitions.**  I found the definitions on the first few pages hard to parse.  The three definitions contained in Def. 1.1 are all almost exactly the same; they each differ by at most a couple of words.  I think it would make much more sense to condense this by using some sort of meta-definition, and then listing the three definitions as special cases.  This also applies to Definition 1.4.  In the case of Definition 1.4, the only difference relative to Def. 1.1 seems to be that the learning algorithm is randomized, which could surely be summarized in a more concise way.\n\nAnother related point is that the authors state the definitions with relatively little context.  It would be help to illustrate each of these definitions with an example or a figure.  As I mentioned earlier, the differences between each of these definitions is relatively subtle, and it's asking a lot from the reader to keep all seven definitions on pages 2-3 in their heads at once, along with the fine distinctions that separate them.\n\n**Writing.**  Much of the prose is notably spare in a way that makes the paper more challenging to read.  Results (e.g., Theorem 2.1) are often without any preamble.  It would be worth thinking about reorganizing the paper so that each result is accompanied by an intuitive explanation of the relevance of the result and how it fits into the broader context of the paper.  While I like the attempt to informally present the theorems before offering a more rigorous treatment after Section 1, I don't think that it works here.  This is in part because it asks the reader to consider each result at three levels of abstraction.  First, the results are stated informally in Section 1.  Then, in the remainder of the main text, the same results are stated formally, but the proofs are informal or sketched.  Finally, the full treatment is given in the appendix.  I think that asking the reader to jump around at these different levels of abstraction is, in this case, confusing.  Perhaps the authors could shorten the intro and stick to the results as stated from Section 2 onwards?\n\nRelatedly, the intro seems too long here.  The reader has to wait until page 5 to learn what the authors feel the contributions are.  This dilutes the standard linear flow of ideas that characterizes papers that are easy to follow.  To make the paper easier to follow, I would recommend rewriting the introduction so that (a) the problem of distribution learning is well-motivated, (b) the main results are discussed, but not stated, and (c) the contributions are listed by -- at the very latest -- the end of the second page.\n\n**How is this \"robust?\"**  One question that jumped out to me was as follows: How are the definitions in Definition 1.1 \"robust?\"  I.e., what are they robust against?  The authors claim that the name \"robust learnability\" is due to the fact that they are accounting for the ground truth distribution $p$ may not be an element of the class $\\mathcal{C}$.  Would it not be more accurate to call these definitions \"agnostic\" rather than \"robust?\"  I can see how one would regard the corruption-based definitions in Def. 1.2 and Def. 1.3 as robust, because the distribution $p$ is mixed with a corrupted distribution.  However, in the sense of Definition 1.1, I don't understand the use of the word \"robust.\"\n\n**Miscellaneous.**\n\n* It looks like a some points the authors write $(\\alpha,\\eta)-robustly learnable and $\\alpha-\\eta$-robustly learnable (c.f. Def. 1.1(3) vis-a-vis Def 1.4(3)).  It seems like it would be good to pick on notation and stick with it. \n* Why is the TV distance chosen here?  The authors assert that this distance metric makes sense, but they give no argument, leaving the reader with some confusion.\n* It would be worth adding a discussion section after the main results but before the conclusion.  After reading through the results, it would be useful if the authors could piece them together in the broader context of distribution learnability.  The authors could also discuss how these results could lead to future research on this problem, and/or whether this could lead to new algorithms that would be of practical use.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed and positive review! We are glad to hear the reviewer appreciates the breadth and technical quality of the results we present. We acknowledge the fair criticisms made regarding writing, and appreciate the many concrete suggestions offered by the reviewer to remedy these issues. We will take them into account in future revisions of our manuscript.\n\nIn the following, we address specific concerns raised by the reviewer.\n\n—------------------------------------\n\n**On presentation:**\n\nThe main critique of the paper is related to the presentation and organization of the paper, rather than the results themselves. These comments are well-received, and we are happy to take them into account as best as we can. \n\nIndeed, stating the main results (even informally) within the first two pages is an excellent suggestion, and I think we can do that to communicate the story early on. We thank the reviewer for giving many concrete suggestions. Given the stringent page limit and the thoroughness of our set of results, it may be difficult to fit all the suggestions into the body, but we will try our best, and include a “full version” in the supplement which is maximally readable.\n\n**On motivations:**\n\nDistribution learning is a classical problem in both statistics and computer science, which has seen significant study at NeurIPS and related conferences (see [1,2,3,4,5], note that [5] received a best paper award at NeurIPS 2018). We will emphasize the tradition and relevance of this work to the community. \n\nLearning in TV distance is perhaps the most common and established problem in distribution learning, we will add discussion and references to this, as well as pointers to learning in other distances. \n\n**On the terminology of robust:**\n\nIndeed, robustness and agnostic learning are closely related, and we generally use the terms interchangeably. Consider first the agnostic setting from the CS literature, traditionally defined as follows: there exists some underlying class of distributions, but an adversary instead selects an arbitrary distribution from within a TV ball of the class to draw samples from. This is more frequently used to capture model misspecification, but could also be used to capture adversarial contamination of the distribution. \n\nThis is our non-adaptive setting (Definitions 1.2 and 1.3), though we note that this is also called the Huber contamination model in the robust statistics subfield of statistics. We thus emphasize that both “agnostic” and “robust” have been used to refer to this setting, depending on the community (where our paper is at their intersection). On the other hand, the adaptive version in Definition 1.4 is almost exclusively referred to in the algorithmic statistical estimation literature (i.e., [6]). Due to the overlapping terminology, we choose to use agnostic and robust interchangeably for all definitions, and differentiate between Definitions 1.2/1.3 and 1.4 using the terms adaptive and non-adaptive. We will clarify that we use these two terms interchangeably and why in the final version of the paper. \n\n**On the various definitions of robust learning:**\n\nOne criticism is that the definitions are not clear or too similar, making it hard to parse. We will put more effort into explaining the different aspects of the definition in the main text of the paper. \n\nWe also like the idea of a meta-definition and will take it into consideration. There are basically 3 types of adversaries: one who can add data, one who can remove data, and one who can do both. Now those adversaries either act on the distribution, giving rise to Definition 1.1, 1.2 and 1.3 respectively or they act on the sample, giving rise to Definition 1.4. While it is easy to state these intuitively, being formal is a bit more cumbersome, leading to the somewhat-clunky definitions. We will try to add an informal discussion to clarify, as well as add a table with these two axes to highlight the distinctions and give a clearer picture of the definitions.\n\n—--------------------------------\n\nWe hope that the proposed changes will help make the paper more accessible. We are looking forward to a fruitful discussion with the reviewers about how to best get our message across and appreciate the reviewer’s feedback.\n\n**References**\n\n[1] Ishaq Aden-Ali, Hassan Ashtiani, and Christopher Liaw. Privately Learning Mixtures of Axis-Aligned Gaussians. NeurIPS’21.\n\n[2] Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan, Krzysztof Onak, and Ludwig Schmidt. Communication-Efficient Distributed Learning of Discrete Distributions. NIPS’17.\n\n[3] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. Near-optimal-sample estimators for spherical gaussian mixtures. NIPS’14.\n\n[4] Siu-On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun. Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms NIPS’14.\n\n[5] Hassan Ashtiani, Shai Ben-David, Nicholas Harvey, Christopher Liaw, Abbas Mehrabian, Yaniv Plan. Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes. NeurIPS’18.\n\n[6] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust Estimators in High Dimensions without the Computational Intractability. STOC’16.\n"}]

Author rebuttal:

Meta-review: This paper explores the relationship between learnability and robust learnability in the unsupervised setting of learning classes of probability distributions. The focus is on sample complexity bounds. It is shown that if one considers only additive corruptions, learnability implies robust learnability. But this is not the case with subtractive corruptions. Overall, the reviewers agreed that this is an interesting contribution that merits publication at NeurIPS.
Decision: Accept (poster)