On the Learnability of Distribution Classes with Adaptive Adversaries
Authors: Tosca Lechner
Alex Bie
Gautam Kamath
Venue: ICML 2025 poster (2025)
Keywords: distribution learning
robustness
Primary area: theory->learning_theory

Abstract: We consider the question of learnability of distribution classes in the presence of adaptive adversaries -- that is, adversaries capable of intercepting the samples requested by a learner and applying manipulations with full knowledge of the samples before passing it on to the learner. This stands in contrast to oblivious adversaries, who can only modify the underlying distribution the samples come from but not their i.i.d.\ nature. We formulate a general notion of learnability with respect to adaptive adversaries, taking into account the budget of the adversary. We show that learnability with respect to additive adaptive adversaries is a strictly stronger condition than learnability with respect to additive oblivious adversaries.

On the Learnability of Distribution Classes with Adaptive Adversaries
Tosca Lechner
Alex Bie
Gautam Kamath 13
Abstract
tribution the learner's samples come from, with full knowledge of the learner's algorithm and p itself, but cannot change the i.i.d. nature of the samples.
We consider the question of learnability of distri- bution classes in the presence of adaptive adver- saries - that is, adversaries capable of intercepting the samples requested by a learner and applying manipulations with full knowledge of the samples before passing on to the learner. This stands in contrast oblivious adversaries, who can only modify the underlying distribution the samples come from but not their i..d. nature. We formu- late a general notion of learnability with respect to adaptive adversaries, taking into account the budget of the adversary. We show that learnability with respect to additive adaptive adversaries is a strictly stronger condition than learnability with respect to additive oblivious adversaries.
While all realizably learnable classes are agnostically learn- able in the PAC setting (Vapnik & Chervonenkis, 1971; Haussler, 1992), the recent study of Ben- Ben-David et al. (2023) demonstrates that there is separation in the distribution learning setting. They give an example of a realizably learn- able class that is not learnable in the presence of oblivous adversary. On the other hand, they also provide positive result: a realizable learner for a class can be converted to learner robust to oblivious adversaries restricted to only additive corruptions.'
It is a natural question to consider how the situation changes in the presence of an adaptive adversary:
An adaptive adversary receives i.i.d. samples drawn from the unknown distribution p. and can modify indi- vidual samples with full knowledge of the samples, the learner's algorithm, and p itself.
1. Introduction
In the distribution learning problem, learner receives i.i.d. samples from unknown distribution belonging to known class of distributions C, and is tasked with producing an accurate estimate of p. Distribution learning is one of the most fundamental and well studied problems in learning theory (Kearns et al., 1994; Devroye & Lugosi, 2001); see also the survey of Diakonikolas (2016).
Indeed, the study of robustness with respect to adaptive adversaries is increasingly relevant to modern settings that examine machine learning algorithms from a worst-case, security perspective (Chen et al., 2017; Carlini & Wagner, 2017; Diakonikolas al., 2019; Tramèr et al., 2020; Carlini et al., 2024). et al. (2023) focus entirely the oblivious set- ting, and do not investigate the implication of their results to the adaptive setting. First, it is trivial to observe that their negative result (learnability does not imply robust learnabil- ity with an oblivious adversary) carries over to the adaptive case? This is because adaptive adversaries can simulate oblivious adversaries, and are thus stronger (see Table 1 for full summary of the situation). The remaining unresolved question is whether their algorithmic results can be extended to the adaptive setting:
The above formulation of the problem is referred the realizable case where the learner can take advantage of the strong prior knowledge that indeed, the unknown distri- bution p they receive samples from is precisely a member of the distribution class This assumption is dropped in the agnostic setting, where the learner must be able to handle receiving samples from distribution outside of C, but must produce estimate close to the best approximation by member of C. An alternative formulation of this requirement is that the learner must be robust to an oblivous adversary:
An oblivious adversary can modify the unknown dis-
'ector Institute "Google University Waterloo. Correspon- dence to: Tosca Lechner <tosca.lechnere <tooaal.chher@eeoorrriinn......
'This model is sometimes called Huber contanination. "In the technical part of the paper we also show a slightly stronger version of this negative result for subtractive, which also holds for adversaries that only have access to S but not p. This result is shown via separate proof technique and does not imme- diately follow from previous work.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On the Learnability of Distribution Classes with Adaptive Adversaries
Subtractive
Additive
No (Ben-David et al., 2023, Theorem 2.1)
Yes (Ben-David et al., 2023, Theorem 1.7)
Oblivious
No c implied by above
No Answered by this work, Theorem 4.1
Adaptive
Table I. Does learnaillity imply learnability with respect to [oblivious[adaptive] (saiaapiiiillluuuurrrattvveeaaaa Suubrractive/additiiv
adversaries?
Are realizably learnable distributions learnable in the presence of an adaptive additive adversary?
To obtain this result, we first develop general technique for showing that class is not learnable with respect to adaptive manipulations from an adversary V. This technique, based on a recent result of Ben-David & Lechner (2025); says the following:
The present paper answers this question in the negative. We show that additive corruptions are strictly more powerful in the adaptive model than in the oblivious model.
Theorem 1.2 (Informal version of Theorem 5.2). If for a class of distributions C. there exists some p E C and a distribitti Q over elements of C, such that
To prove the result, we examine the relationship between subtractive and additive adversaries, and show that general sufficient condition for the existence of adaptive subtractive adversaries also implies the existence of adaptive additive adversaries. This close relation between the additive and subtractive adversaries stands in contrast to the oblivious setting, where there subtractive adversaries are strictly more powerful than additive. We show that given adaptive subtractive adversary, we can construct an adaptive additive adversary by inverting the subtractive adversary: instead of adding sample points that the subtractive learner would have deleted from a sample from a different distribution.
1. drv(p, q) is bounded below by some constant, for all q in the support of Q; and
2. A sample S ~ V(e"t) and sumple S' ~ V(g") where ~ Q cannot be reliably distinguished,
then learning C with respect to adversary V is hard.
This result holds even if adversary V does not have access to p and can be found in Section We use this result to show that in the adaptive case (in contrast to the oblivious case), additive and subtractive robustness are closely related (Section 6). In particular, we show that if the conditions (1.) and (2.) of Theorem 5.2 are satisfied by class C and subtractive adversary Vsub, then C is not robustly learnable with respect to adaptive additive adversaries (Theorem 6.1..
1.1. Results and techniques
We consider additive adversaries who can only add points, and subtractive adversaries can only remove points. 3
Informally, a class robustly learnable in the presence of an adversary if admits learner satisfying the following: given a sufficiently large (corrupted) sample, the learner is capable of driving error arbitrarily close to 17. where 1) is the fraction of samples added/removed by the adversary, and a is any absolute constant.
Next, in Theorem 7.1 we show that fulfilling this condition for subtractive adversary Veub and class C also implies the existence of single adaptive additive adversary Vadd that is successful against every learner for C; we refer to such an adversary as a universal adversary.
The following our main result.
Theorem 1.1 (Informal version of Theorem 4.1). There exists class of distributions C that is realizably learnable, yet the class is not robustly learnable in the presence of an adaptive additive (or subtractive) adversary.
The main result is first formally introduced in Section 4. We use a realizably learnable class C, which was used to show separation between agnostic and realizable learnability in (BendDavid al., 2023). We then construct subtractive adaptive adversary Vaub.n and show that it meets the condi- tions (1.) and (2.) for Theorem 5.2. We then use results from Section 6, to show that this also implies that Cy is not adaptively additively robustly Icarnable. In particular, we also show that there is both, a universal additive adversary Vada and a universal subtractive adversary Vsub., for Cy. We introduce both the class Cg and an adaptive subtractive
In contrast, recall that the main algorithmic result of Ben- David et al. (2023) says that every realizably learnalle class is also robustly learnable in the presence of oblivious additive adversary.
We defer more formal definition of adversary models to Section 3.2.
2

---

On the Learnability of Distribution Classes with Adaptive Adversaries
adversary Ve in Section 4, before delving into technical details.* We then motivate each of the subsequent sections, by the results we will get for Cg and the adversary Vaub,n within that section. We finally prove the main theorem at the end of the paper in Section 7.1.
Many subsequent works have studied algorithms for learn- ing particular classes of distributions, see, e.g., (Chan et al., 2013; 201:;;;; Li & Schmidt, 2017; Ashtiani et al., 2020), A recent line of work, initiated by (Diakonikolas et al., 2016; Lai et al., 2016), studies conputationally-efficien algorithms for robust estimation of particular classes of mul- tivariate distributions, see, e.g., (Diakonikolas et al., 2017; Steinhardt al., 2018; Diakonikolas et al., 2018; Kothari et al., 2018; Hopkins & Li, 2018; Diakonikolas et al., 2019; Liu & Moitra, 2021; 2022; Bakshi et al., 2022: Jia et al., 2023) and (Diakonikolas & Kane, 2022) for reference. We focus on understanding broad and generic connections be- tween learnability and robust/agnostic learnability, without consideration for computation, in contrast to those works that focus on computation and particular classes of distribu- tions.
2. Related work
As already mentioned, our work directly follows up on, and addresses open problem of, Ben-David et al. (2023). Their work shows that learnability implies robust learn- ability under an oblivious additive adversary but not under an oblivious subtractive adversary. They explicitly asked whether their algorithms which are effective under an oblivi- ous additive adversary can be extended to handle an adaptive additive adversary. We answer this question in the negative: learmability does not imply robust learnability under adap- tive additive adversary.
3. Setup
Recent works of Blanc, Lange, Malik, Tan, and Valiant (Blanc et al., 2022; Blanc & Valiant, 2024) also study the relationship of adaptive and oblivious adversaries. They show impressively generic results: for a broad range of statistical tasks, given an algorithm that works against an oblivious adversary, this can be converted to an algorithm that works against an adaptive adversary by simply drawing a larger dataset and randomly subsampling from it. This seems to suggest that any distribution which is learnable un- der an oblivious adversary should also be learnable under an adaptive adversary, which would contradict our main result. However, there is no contradiction: the size of the "larger dataset" their approach requires depends logarithmically the support size of the distribution, and we focus on distribu- tions with unbounded support. Thus our results imply that some dependence on the domain size is unavoidable for this reduction to go through for the task of distribution learning.
3.1. Preliminaries
We consider learning over a domain X. We denote the set of all distributons over X as A(X). We assume an i.i.d. generating process of sample sets S. If S is a sam- ple of size m i.i.d. drawn from a distribution p. we will denote this as S ~ pm Furthermore, consider samples S to be multi-sets, that is, consider samples to be randomly shuffled/ordr invariant, but assume that repeated elements are counted. For example, we as- sume that S = {0, 1, = {1, O, 1]. but (1,0,0) * {1,0). In a slight abuse of notation we will use set-operations on samples S, again assuming that elements are repeated. That is {a, b, b, c) {a, b, d, d] {a,a, e, d, d) and {a, b, b, c) \ (a, b, d, [b,c).
note that
We let X = -.000 X", where x is the set of multi-sets over X' of size m. We usually refer to learning with respect to a concept class of distributions C C AXX). Further- more, we consider distribution learning with respect to total variation distance drv A(X)= x A(X) + [o. 1] defined by
One recent work of Canonne et al. (2023) shows gap between the sample complexity of robust Gaussian mean testing with adaptive and oblivious adversaries: they show that the adaptive adversary is strictly more powerful, neces- sitating an increase in the sample complexity. Their focus is on a testing problem, whereas we study a distribution learn- ing problem. They show a polynomial gap in the sample complexity for a natural problem, whereas we show an infi- nite gap in the sample complexity of a somewhat contrived problem.
drv(p. = sup
Ip(B3 - ((A)-
BCX:B measurable
1
f (dp(x) - dg(x))-
2
2EX
We study the PAC learnability of distribution classes in the presence of adaptive adversaries. We start by giving the definition of PAC learnability of a class of distribution in the realizable case, i.e., without the presence of any adversary.
Robustness is traditional topic of study within the field of Statistics, see, for example, the classic works (Tukey, 1960;
Huber, 1964). Within Computer Science distribution learn- ing has been studied since the work of Kearns et al. (1994), inspired by Valiant's s PAC learning model (Valiant, 1984).
Definition 3.1 ((Ralizzalee) PAC Icarnability). A class of distributions C is (realizably) PAC learnable, if there exists a learner and a sample complexity function my (0,1)² + N. such that for every p E and every e, 8 E (0,1) and
"The adversary Vaub.,, does not require knowledge of the ground-truth distribution p-
3

---

On the Learnability of Distribution Classes with Adaptive Adversaries
every m 2 mē(e 0), with probability 6,
budget Xx2 N + [0, is defined by:
[VS)
(Tv(((()))) S
budget add (V, VV,))= = sup SE.t
m
where S pmm
Similarly, the budget for a subtractive adversary is defined by
| IV(S)
3.2. Adaptive adversaries
budget sub (V,
sup
SEX m
m
An adaptive adversary is function V X X from samples to samples. We allow this function to be random- ized. We refer to the probability measure of V(S) by (9))). When considering S to be generated by some distribution pm, we will sometimes refer to the distribution of V(S) by (i" in slight abuse of notation.
In this work, we only consider adversaries that have fixed budgets and furthermore that those budgets are constant. In particular, we will assume, that for both subtractive and additive adversaries V. for all m E N and all Si, S2 E x we have [V(S)) = |V Furthermore, we assume that for every adversary V there is a constant budget(VV = 7) such that for every m N:
We now introduce two main classes of adaptive adversaries, additive adversaries, who can only add additional sample points S to the sample, i.e., (S) SUS; and subtrac- live udversaries, who can only delete some sample points S/ from the input sample, i.c., (S) = S \ Shz We will also introduce a notion of budget, which limits the amount of manipulation of an adversary.
m 1 < m budget (V, S 1ym.
We can now define robust PAC learning with respect to a specific adaptive adversary.
Definition 3.2 (adaptive a-robust with respect to adversary
V). Let a 1. A class of distributions C' is adaptively robustly learnable w.r.t. adversary V, if there exists learner A and a sample complexity function me V.a (0, 1)2 + N, such that for every p E C, every E, E (0,1) and every sample size m 2 mm
Additive adaptive adversaries We say that adaptive ad- versary V is additive, if for every S E X², we have S c (S). We denote the class of all adaptive additive adversaries with Vadd-
V.a (s, 5) with probability 1 - 8,
drv p) S a budget(()) +
Subtractive adaptive adversaries We say that adaptive adversary V is subtractive, if for every S E X", we have (S) C S. We denote the class of all subtractive adaptive adversaries with Veub.
If class C not a-robustly learnable with respect to adver- sary V. we say that V is a universal a-adversary for as every learner for C fails against V.
In general, learners want to defend against more than one potential adversary, since a priori, they may not know the adversary's 's strategy. Thus in the next definition we define learnability with respect to a class of adversaries. One can also think of this as a strengthening of the adversary, as here the learner needs choose the learning rule first, and the adversary can adapt their strategy to the selected learning rule.
In the presence of an adversary, learner A does not have direct access an i.i.d. generated sample S ~ pd from ground-truth distribution p E C, but only indirect access via manipulated sample (SS).
In general, we can not hope to approximate the ground- truth distribution to a total variation distance up to any E > O, but rather, we have to figure in the budget of the adversary. The budget of an adversary is some function budget: x xN [0, 1] and models their manipulation capabilities.
Definition 3.3. Let 2 1. A class of distributions is adap- tively a-robustly learnable w.r.t. a class of adversaries V, if there exists learner A and sample complexity function me V.a (0,
N, such that for every p E C and every V E V and every s, 8 E (0, 1) and every m 2 m with probability 1 5,
In cases, where the power of the adversary amounts to either adding or deleting instances, but not changing instances in any other way, the budget amounts to the edit distance. In general, the budget for an adaptive additive adversary is thus defined by:
V.a (s,
drv(A(V( p) S a -budget +
We say a class C is adaptively additively a-robustly learn- able if C is a-robustly learnable with respect to the class of adversaries Vada- We say a class C is adaptively subtrac- rively a-robustlly learnable if C is a-robustly learnable with respect to the class of adversaries Veub-
'Adaptive adversaries may also make use knowledge of the underlying sample generating distribution p. We omit this option for simplicity. Indeed, our main result is slightly stronger than stated: show that adversaries that do not make use of knowledge of p suffice to prevent learning.

---

On the Learnability of Distribution Classes with Adaptive Adversaries
4. A realizable class with an adaptive adversary
Cg is realizably learnable. We first note that this class is realizably learnable, using results from Ben-David et al. (2023).
In this section, we formally introduce the main result of this paper: there are classes of distributions which are learnable in the realizable case but not learnable in the presence of either adaptive additive or adaptive subtractive adversaries. Since learnability in the realizable setting also implies learn- ability with an oblivious additive adversary (Ben-Daviz al., 2023), this result also implies separation between learnability with respect to oblivious and adaptive adver- saries in the additive case.
Lemma 4.2 (Claim 3.2 from Ben-David et al. (2023)). For every monotone function g N + N, the class Cg is learn- able with sample complexity
12 3 ())
m (E, 6) S log
The realizable learner is based on the idea, that for every dis- tribution the learner only needs to observe unique indicator bit in order to perfectly identify the distribution.
In this section, we give the formal statement of the main result (Theorem 4.1). We also describe Theorem 4.1's sub- ject distribution class Cg. and argue is realizably learnable. Finally, we introduce a subtractive adversary Vaub.n nn for the class. In subsequent sections we will use this adversary to prove the remaining parts of Theorem 4.1, which we now state.
Subtractive adversary Vaub., for Co We will now intro- duce a subtractive adversary Vaub., for Cg. The properties of this adversary will then be used in later sections of the paper to show that Cg is neither adaptive additive nor adaptive subtractive robustly learnable.
Theorem 4.1. For every superlinear finctiion g R + R, there is class Cy. such that
For sample S, partition S into the non-indicators constants(()) = {{0, 0) E S} and odds(S) = {(o, 2j + E) E N and indicators ind( = {ii, 2j + e $ : i.j E N}. i.e. S = constants(S) U odds(S) U ind(S). We further denote non-indicators noind(S) = constants(S) U odds(S). Note that S, constants(S)) odds(S), nSind(S), and in) are all multisets and thus repetitions of elements are counted.
Co is realizably learnable with sample complexity (E,(E,)) (E. log (o) g
For every a 2 1, Cg is not adaptively additive a- robustly learnable. Moreover, for every a 2 L, there is adaptive additive adversary Vadd. that is a universal a-adversary for Cg.
We now define the subtractive adversary Vsub.ry X > X as the adversary that removes from S as many elements belonging to ind(S) as possible while meeting the budget constraint budget(Vaub..)) S vj. If there are no elements in in)(5) left to remove, Vsub.n chooses to remove elements randomly to match the budget. Formally,
For every a 2 1, Cg is not adaptively subtractively a-robusttl learnable. Moreover, for every a 2 1, there is an adaptive subtractive adversary Vaubo that is universal a-adversary for Cy.
Introducing class Cg. Theorem 4.1 uses the class Cg from Ben-David al. (2023) that was used to show separation between realizable and agnostic learning."
choosc(noind(()) (1-))()))
if [ind(()) S n|S]
For this let [B, C N: B, is finite} be an enumeration of all finite subsets indexed by i E N. Now for constants j, k E N, we define the following distribution as a mixture of two point masses 00 and ((g,) centered at (0, 0) and (i, respectively, and a uniform distribution over the set B, denoted by Un,:
(Su nSin U
choose (indss /ind (S)) - -7| if (ind(S) > n/|5
where choose(S,n) n) is the random variable, which selects uniformly chosen random subset S' c S of size n. is easy see that Vsub., is subtractive adversary with "adgeet"h((Vuub.)) = 17. We note, that the definition of this adversary Vaub,n does not require any knowledge of the ground-truth distribution p. While this adversary is in idea similar to the subtractive oblivious adversaries that were shown to be successful against learners in (Ben-Davis et al., 2023), these past results do not yet show that Vaub. is a successful adversary for Cg. In the following section, we introduce the notion of an adversary successfully confusing
Pij.k
( (0000)
2 U B. ( + + 0112542))
1
k
Now for function y: NN- + N. we define the class
Cg (P:s.0)) j.NNj
This class is denoted 2, in (Ben-David et al., 2023).
5

---

On the Learnability of Distribution Classes with Adaptive Adversaries
samples generated from members of Cg show that an adversary is universal o-adversary. We then show that for every 2 1, there exists 7 (0, 1), such that Vuub.n satis- fies this notion, and hence is indeed a universal a-adversary for Cg. We then also show that this condition implies that Cg is not adaptive additive a-robustly learnable (Section 6). Moreover, using the same condition, we show that for every 2 I, there exists a universal additive a-adversary for Cg (Section 7). The proof of Theorem 4.1 can be found in Section 7 at the end of the paper.
every size m, then C is not robustly learnable with respect to those adversaries.
Theorem 5.2. Let C be a class of distributions and V D (V,, 1/) a set of adaptive adversaries with budgets budget = yn and budget(V2) - 1/2 Let E
and define
? 2a max {m, 72) + 2
for every m E N the pair of adversaries (V1. V2) success- fully (7, -coonfuse C-generated samples of size m, then is not a-robustly learnable with respect to V.
5. General technique for showing distribution classes cannot be learned adaptively
Furthermore, V1 Vz. then V1 is a universal a-adversary for C.
In this section, we will show general lower bound for learning in the presence of adaptive adversaries. We intro- duce the notion of an adversary V or a pair of adversaries (V1, V/2) successfully confusing samples generated from a class and show that this condition is sufficient to show a class C' cannot be learned in the presence of adversary V (or pair of adversaries (V1, V2), respectively). Essentially, the result shows that if adversaries can make samples from certain random distributions defined over C sufficiently in- distinguishable, the adversary can also fool any learner. To state the definition of successfuly confusing a C-generated sample, we introduce some notation.
We show this result by the following lemma which makes the same claim for a fixed sample size m.
Lemma 5.3. Let C be a class of distributions, let A be a
learner and (V1, V2) a pair of adversaries that successfully (y, -ooffuses C-generated samples of size m.
Then every learner A, there is E C, such that
1
5
PSwym (sV(
2
or
> Psumm [div(A((((S)),r)
1 2
5
For distribution Q over class of distributions C, let QQ|" denote the distribution over x that results from first sam- pling 9 ~ Q and then S ~ qth Furthermore, let supp(Q) denote the support of Q. In the following we will pick distributions p E C and Q E A(C) such that for every q E supp(Q) the total variation distances drv(p,g) g) are upper bounded by some constant.
2
2
2
Lemma 5.3 is corollary of result of Ben-David & Lechner (2025), which makes the connection between the indistin- guishability of the sample distributions IQ TM and pm,, and hardness of learning. For completeness, we include the full proof of Lemma 5.3 in Appendix A.I, but we note that it follows the exact same argument as the proof of the cited result.
If for such distributions p and Q there are adaptive adver- saries Vi, V/2 that can make the sample distributions Vi (pm) and Vi(I sufficiently hard to distringuish, then the class C is not robustly learnable with respect to (V1, V2J. To show this, we introduce the following notion:
Lemma 5.4 (Lemma of Ben-David & Lechner (2025)).
Let C2 be such that for all E C1 and all p E Cz we have drv(p. q) > 7. If there is a distribution Q over C1 and E C2 such that for Ç E (0, 1/2) we have drv "(Q"""p'"') < G. then for ever learner A, there is r E E,, UC, such that
Definition 5.1. Let C be a class of distributions. We say
pair of adversaries (V1, V/) successfully (7, ))confusess C- generated samples of size m if there is a distribution E C
Ps-mm (dTv(A(S),
2 2
C
and a meta-distribution Q E ACC) with
> 2 2
for all E sQp we have drv >>
The proof of both Lemma 5.3 and Theorem 5.2 can be found in the appendix. Furthermore, in Appendix B we give an example which illustrates how these lemmas can be applied. A similar intuition to that example is used in the next section to show that Vaub,, successfully confuses Cg.
drv (Vi(1Q)))) ) V2(p")) <C
If V-= = Vz, we also say Vi successfully (7, -ooofuuee C-generated samples of size m.
5.1. Vsub.n is universal adversary for C,
Successful adversaries have large 7 and small Ç. We now state the main theorem of this section which shows that if adversaries successfully confuse C-generated samples for
In this subsection we show that for every a 2 1 there is rj E (0, 1), such that Vanb.y is universal o-adversary for
6

---

On the Learnability of Distribution Classes with Adaptive Adversaries
Cg (recall the constructions of these objects as described in Section 4). We will first show that Vaub. successfully confuses -gggenrrtted samples and then apply Theorem 5.2. Lemma 5.5. For every 2 1, there is ni y (0,1), such that for the subtractive adversary Vanb. the following holds: For every m 2 1 there are distributions p E Cg and Q E A(C,) such that
can each be upper bounded by
PSpp" [[ind( 1) (||] + Fs- [ind(()]
>> 7|S|]
R Es-p [S)][
+ Bs-iQr [(n
2 kn
S
S/S|
17 S
using Markov's 's inequality.
Since we are considering distributions in Cg. we note that the distributions Dinn.jk need to be of the form Di.m...01)) We now want to argue that for appropriate choices of j and 1 (both independent of m). well for given m, the incqualities of the theorem are satisfied. First, note that since grows faster than linear, it is possible to pick j in such a way that it satisfies the inequality
for every q E supp(Q):
drv 4a budget + 47
ddv((sub. (p Vaub., ((Q) s 1 8'
Proof sketch. We first note that for p = Pi.j.k where [B:]
g 2 1024caj.
22" is arbitrary and Di,m.i.- {pr By C B [By]
)"), we have that for every 9 E Dinnjjk
Given such j, we then pick 1) 2(f) and 7 a This ensures, that for every n E N and every q E Dimmi.sti) we get
a(z)*
()
1
dTv(p.
drv (ev(UBxx2;UBB/ x2))
k
1 1
1
1 (1 2 2 ;
1
dlv(p.
2
= 4om + 47/.
Furthermore, consider Q = UD We note that the distributions (p"*., and Vaub (1Q)) (1)) are both distri- butions over multisets S' = constants(S U odds(S') U iS"). We further note that the distributions of the count of each of those subsets are the same for both S' (sut.,(p"")) and S' (lQi.)()Q|("), Furthermore, since all clements of constants(S)) are the same, we also have that the probability distributions of constants(S") are the same for both S" ~ (p") and S' ~ (QQ) We also observe that the distributions for odds(S') condi- tioned on S" ~ (p" and S ~ [ are the same, if odds(S') does not contain any repeated elements. Lastly, we note that while the indicators of samples from p and samples from differ, the adversary Vuub.y deletes all these elements, if (S)] does not exceed S|.
Then, for every m 2 1, if we choose n 2
1- (1 m
31/m we
get
drv (Vsub,n (p"),, (sub.n(((
2
+ (1 -11
m
)m))
<
32
2
9(5)
1
8"
The full proof with all the calculations can be found in the appendix.
Taking all of these observations together, we can bound the total variation distance terms of repeating elements in odds(S) and the probability that [ind(S) exceeds the budget of the adversary.
6. Subtractive versus additive adaptive adversaries
In this section, we will show that unlike in the oblivious case, additive and subtractive adaptive adversaries are closely re- lated. In particular, we show that if there is a universal subtractive adversary Vsub that successfully (7, C)-cofuuses C-generated samples of size m, then there is pair of addi- tive adversaries (Vadd,p"' Vadd, Q that also successfully (7, -)-oofuses C-generated samples of size m.
drv (Voub,n (),,,, (aQi),((Q))))
< P smpm (od contains repeated elements]
+ P s- (S) (odss(S) contains repeated elements]
+ P s= [indd > ||S]]
+ P -Ps- (ind:miliinns) [S) > s/]S]]
Theorem 6.1. Let C be a class of distributions. Let Vaub be an adaptive subtractive adversary. Let Ç E (0, 1) be a constant, p E C a distribution, and Q a distribution over elements such that dry (Veub (QQ)²) Vuub(p")) < Ç.
The first two terms can each be upper bounded by 1 2n using the birthday paradox. The last two terms
7

---

On the Learnability of Distribution Classes with Adaptive Adversaries
Then there are additive adversaries V Vddd.gm and Vidd. with drv pm (IQ[m)) Qi (pTh) )) S. Further-
every measurable subset B C X::
I Sw sub, in (Score) |s E B} =
more, if Vsub has a fixed constant budget of n < 2. then
both V 1 and Vudd.pm have fixed constant budgets of no more than T3.
Psupp (S E B (VVssub(S) = Score]
Similarly, we can make the same observations for !Q] and define the reversed adversary V 11 equivalently. The additive adversaries Quad, and undVaddd Vadd,p" are now defined by
In other words, we argue that, if there is an element p E C and a meta distribution Q over C that can be made hard to distinguish by subtractive adver- sary Vaub. i.e., (Venn( (") V)nb()")) < Ç. then this adversary can be used to construct additive ad- versaries Q and Vada,pm, such that the result- ing additive sample distributions are equally close, i.c., drv ((aadd)Q)) (p"*), Vadd, (1Q) ()) <C
Vadd..Q// (5) = sub.1Q m (Veub (S)) (S (S))
and
Vadd.p (S) Vaub.pm (Veub(S)) U (S)) Vaub(S)).
Now, since both Vsub (p*) and (((m) are close to Peores the distributions Vadd,iqi (p² and Vadd.pm (1Q) (*)
are both close in TV-distance the distribution of samples
Proof sketch. While adversaries act on samples drawn from two different distributions to make the manipulated sample distributions close, we will first give an illustration in terms of manipulating simple point-sets Spm pn and Siqi" 1Qmm
VQdd (Score) U Vadd,pm (Score) SSoore
where Score ~ Poore. In particular, the only difference between V=dd,IQ! (p")) and Vadd (IQ m) can be under-
stood as differences in the sampling of Scores as given Scores the distribution of additional samples is the same in both cases. Thus, drv @rv(Vadd, [q)d (p""), Vadd.pm (IQ)T))
Roughly speaking, a successful subtractive adversary can remove part of the first sample Spm and part of the sec- ond sample SiqI.. leave behind a common set Score Vaub (S,r)) = Vaub (anb(Siqq1 (S(q)m) C Spm n Siq We can view the generative process of Spm to be a sample Score com- bined with sample Spm Seore. and the generative process of SiQ!" to be a sample Score combined with a sample from Sig1m \. Score- Hence to confuse the learner, the ad- ditive adversaries just needs to add the "opposite piece," " i.e., Vada.qm Qm is mapping Spm = Score U (Spm \ (Score) to SearnU(S \Score) (S Soore) and Vudd,pp is map- ping Sqm = Score (Sq (Score) to ((oreU(SQq) /Soore (Spm \ Score). Thus, if a pair of samples Spm and Siq) could be made indistinguishable by subtractive adversary Vsub then they can also be made indistinguishable by a pair of adversaries V and Vadd.pm.
drv dVv(Vvub Vaub (IQI")) <.
This intuition is made rigorous in the full proof of Theo- rem 6.1 in the appendix.
As a corollary of the above theorem, we can state a simple condition for a class C and a subtractive adversary Veub. that implies hardness for both adaptive additive and adaptive subtractive robust learning.
Corollary 6.2. Let C be class of distributions and Vaub be an adaptive subtractive adversary with a budget with budget"ub (Vaub) = 17. If there are constants 0 < s 5 1, such that for every m E N, the adversary Vsub successfully (2om + 27/) -confuses C-generated samples of size m, then C is neither adaptively subtractive a-robustly learnable, nor adaptively additive a-robustly learnable.
Now we want to lift this intuition from samples to a more rigorous discussion of distributions. We note that if the subtractive adversary Vaub is successfully confusing distri- butions pd and !Q]m, then there is distribution Poore of common sets Score ~ Poore that is close to both Vaub ( and ()) in total variation distance. Now, due to Vsub (x and Poore being close, most samples in Spm ~ pm can successfully be generated in an alternative way by first sampling Score ~ Peore and then reversing the subtractive adversary Vsub to generate Spm = Score U (Sp' \ Score)= = Ve pmm. (Store). In order to successfully reverse Veub we also need access to prior distribution that generated the input samples for the adversary Vaub- If we have a prior distribution pm we can define V Veub,pm (Score) as the con- ditional distribution of S, given Vsub(S) = Score, i.e., for
Proof. This corollary directly follows from Theorem 6.1 and Theorem 5.2.
Corollary 6.3. For every a 1, the class Cg is not adap- tively a-robustly learnable.
Proof. This corollary follows directly from Corollary 6.2 and Lemma 5.5.
While this already shows a separation between adaptive and oblivious additive robustness, before finally proving Theo- rem 4.1, we first need to show the existence of a universal adaptive additive adversary.
8

---

On the Learnability of Distribution Classes with Adaptive Adversaries
7. Universal Additive Adversaries
is thus upper bounded by
In this section, address the existence of universal adaptive additive adversaries. We know from Theorem 5.2 that if single adaptive subtractive adversary Vaub successfully confuses C-generated samples of all sizes, then Vsub is universal adversary for C. Moreover, we have seen in The- orem 6.1 that the existence of such a single subtractive adversary also implies the existence of pair of adaptive additive adversaries that successfully confuses C-generated examples and thus also shows that C is not adaptively addi- tively learnable. However, these results do not yet show the existence of a universal adaptive additive adversary for C. In the following theorem, we will show that the existence of subtractive adversary Vaub that successfully confuses C- generated samples also implies the existence of an adaptive additive universal adversary for C, albeit one with a higher budget than Vaub.
drv drv(Vadax<(Q11") Vadd, (D
(Vav ( (QQ) )) Vaub (Fr
drv (U (o.
23., U (I......+++1))
s + k+1
The full proof can be found in the appendix.
As a result we obtain the following corollary.
Corollary 7.2. Let C be a class of distributions and Vsub be an adaptive subtractive adversary with constant budget budget (Vaub) = 17. If there are constants 0 << 7 < 2' such that for every mn N, Vsub successfully 44m++4/ 4)- ()- confuses C-generated samples of size m, then there is universal additive a-adversary Vadd, for C.
Theorem 7.1. Let be a class of distributions. Let Vaub be a adaptive subtractive adversary. Let Ç E (0.1) be constant, p E C a distribution and Q a distribution over elements in C such that: drv (Vsub ((Q)m) Vsub (p")
Proof. This corollary directly follows from Theorem 7.1 and Theorem 5.2.
< <.. Then for every & E N there an adaptive additive adversary & with Arrv(aas,, ([Q[(()) Vuda,x(p"*)
<++ R+1 Furthermore, if Vett has a fixed constant budget 1 < k.' then Vada, has a fixed constant budget of no more than krj.
7.1. Proof of Theorem 4.1
We can now prove the main theorem of this paper, Theo- rem 4.1. A separation between the power of adaptive and oblivious additive adversaries follows as corollary.
Proof. From Lemma 4.2 we know that Cg is realizably learnable with sample complexity function m (E, S log (1) g (t) From Lemma 5.5 and Corollary 6.2, we can infer that for every a 2 there is a universal subtractive adversary Vsub.r with budget 17, such that for every m E N, Vanb,r is successfully (4am) + 4n', ))-oofussing Cg gener- ated examples of size m. Finally, from Corollary 7.2, we get that the above implies that there is adaptive additive adversary that has budget 2n and is a universal a-adversary for Cy.
Proof sketch. Given a subtractive adversary Veub as before, the additive adversary obtains new samples by first applying Vaub obtain subset 5' (S) C S. We then again use the reverse mappings Ve and V--1 !q to obtain new sample points. However, now, in contrast to the previ- ous theorem, the idea is not to apply sub.p. or V. sub./qq mm just once for their respective distribution. Instead, the ad- versary makes use of both of these mappings a randomized number of times. That is, the adversary Vadd, picks num- ber from {0, ......RK k}} uniformly at random. Then, for every i E [K] it generates sample Sy = Vaub,pm (S') if i S u and S = V I (S") otherwise. All newly ob- tained samples are then concatenated with the original S to produce the output sample
Since has been shown that classes that are realizably learn- able are also learnable in the oblivious additive 3-robust case, this result shows a separation between learnability be- tween adaptive additive and oblivious additive learnability.
Corollary 7.3. There is a class C that is (obliviously) ad- ditive 3-robustly learnable, but for every a 2 1, Cg is not adaptively additive a-robustly learnable.
S" S' u' (SSSS) (ASYAS)UL (S)).....GG... S').
Now consider the number of different subsamples within this concatenation that are generated by V.=bbp... (S"). This number is +++1 if the initial sample S was generated by S ~ pd = smb.pm (S') and this number is u if the initial sample S was generated by S ~ !QI"" Vemb. "ii...qi..(S"" (S"). The result- ing total variation distance drv (Vada, (Q)1), Vada, (pm))
Proof. This result follows directly from Theorem 4.1 and Theorem 1.5 of Ben-David et al. (2023).
9

---

On the Learnability of Distribution Classes with Adaptive Adversaries
Acknowledgments
and Tramèr, F. Poisoning web-scale training datasets is practical. In IEEE Symposium Security and Privacy, SP 2024, San Francisco, CA, USA, May 19-23, 2024, pp. 407-425, IEEE, 2024.
We would like to thank Shai Ben-David for helpful discus-
sions.
Impact Statement
Chan, S. O., Diakonikolas, I., Servedio, R. A., and Sun, X. Learning mixtures of structured distributions over discrete domains. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 113 pp. 1380-1394, Philadelphia, PA, USA, 2013. SIAM.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chan, S. O., Diakonikolas, I., Servedio, R. A., and Sun, X. Efficient density estimation via piecewise polynomial approximation. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing, STOC '14, pp. 604 613, New York, NY, USA, 2014a. ACM.
References
Ashtiani, H., Ben-David, S., Harvey, N. J., Liaw, C.,, Mehra- bian, A., and Plan, Y. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via com- pression schemes. Journal of the ACM, 6::6::32 2020.
Chan, S. O., Diakonikolas, I., Servedio, R. A., and Sun, X. Near-optimal density estimation in near-linear time using variable-width histograms. In Advances Neural Information Processing Systems 27, NIPS '4, pp. 1844- 1852. Curran Associates, Inc., 2014b.
Bakshi, A., Diakonikolas, I,, Jia, H., Kane, D. M., Kothari, P. K., and Vempala, S. S. Robustly learning mixtures of k arbitrary Gaussians. In Proceedings of the 54th Annual ACM Symposium on the Theory of Computing, STOC '22 pp. 1234-1247, New York, NY, USA, 2022. ACM.
Chen, X., Liu, C., Li, B., Lu, K., and Song, D. Targeted backdoor attacks on deep learning systems using data poisoning, 2017. URL https: /ttp:://axxvvvvv abs/
Ben-David, S. and Lechner, T. Lower bounds for distribu- tion learning, 2025.
Devroye, and Lugosi, G. Combinatorial methods in density estimation. Springer, 2001.
Ben-David, S., Bie, A., Kamath, G., and Lechner, T. Distri- bution learnability and robustness. In Advances in Neural Information Processing Systems, volume 36, pp. 52732- 52758, 2023.
Diakonikolas, I. Learning structured distributions. In Bühlmann, P., Drineas, P., Kane, M. J., and van der Laan, M. (eds.), Handbook of Big Data, pp. 267-283. Chap- man and Hall/CRC, 2016.
Blanc, G. and Valiant, G. Adaptive and oblivious sta- tistical adversaries are equivalent. arXiv preprint arXiv:2410. 13548, 2024.
Diakonikolas, and Kane, D. Algorithmic High- Dimensional Robust Statistics. Cambridge University Press, 2022.
Blanc, G., Lange, J., Malik, A., and Tan, L.-Y. On the power of adaptivity in statistical adversaries. In Proceedings of the 35th Annual Conference on Learning Theory, COLT 222 pp. 5030-5061, 2022.
Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, A. Robust estimators in high dimensions without the computational intractability. In Proceedings of the 57th Annual IEEE Symposium Foundations of Computer Science, FOCS '16. pp. 655-664, Washington, DC, USA, 2016. IEEE Computer Society.
Canonne, C., Hopkins, S. B., Li, J., Liu, A., and Narayanan, S. The full landscape of robust mean testing: Sharp sep- arations between oblivious and adaptive contamination. In Proceedings of the 64th Annual IEEE Symposium Foundations of Computer Science, FOCS '21, pp. 2159- 2168. IEEE Computer Society, 2023.
Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, A. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning, ICML '17, pp. 999- 1008. JMIR, Inc., 2017.
Carlini, N. and Wagner, D. A. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pp. 39-57. IEEE Computer Society, 2017.
Diakonikolas, I., Kamath, G., Kane, D. M., Li, Moitra, A., and Stewart, A. 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.
Carlini, N., Jagielski, M., Choquette- Choo, C. A., Paleka, D., Pearce, W., Anderson, H. S., Terzis, A., Thomas, K.,
10

---

On the Learnability of Distribution Classes with Adaptive Adversaries
Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Stein- hardt, J., and Stewart, A. Sever: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36th International Conference on Machine Learning, ICML '19, pp. 1596-1606. JMLR, Inc., 2019.
Steinhardt, J., Charikar, M., and Valiant, G. Resilience: A criterion for learning in the presence of arbitrary out- liers. In Proceedings of the 9th Conference Innova- tions in Theoretical Computer Science, ITCS '18, PP. 45:1 15:1-4 Dagstuhl, Germany, 2018. Schloss Dagstuhl- Leibniz-Zentruns fuer Informatik.
Haussler, D. Decision theoretic generalizations of the PAC model for neural net and other learning applications. In- formation and Computation, 100(1): (00(1)78-150) 1992.
Tramèr, F., Carlini, N., Brendel, W. and Madry, A. On adap- tive attacks to adversarial example defenses. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Hopkins, B. and Li, Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM Symposium the Theory of Computing, STOC '18, pp. 1021-1034, New York, NY, USA, 2018. ACM.
Tukey, J. W. A survey of sampling from contaminated distributions. Contributions to Probability and Statistics: Essays in Honor of Harold Hotelling, pp. 448 188-485, 1960.
Huber, P. J. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):33-00, 1964.
Valiant, L. G. A theory of the learnable. Communications of the ACM, 27(11):133-1142, 1984.
Jia, H., Kothari, P. K., and Vempala, S. S. Beyond moments: Robustly learning affine transformations with asymptot- ically optimal error. arXiv preprint wiXv:2302..1228, 2023.
Vapnik, N. and Chervonenkis, A. Y. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264-800, 1971.
Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R. E., and Sellie, L. On the learnability of discrete distri- butions. In Proceedings of the 26th Annual ACM Sympo- sium on the Theory of Computing, STOC '94, pp. 273- 282, New York, NY, USA, 1994. ACM.
Kothari, P.. Steinhardt, J., and Steurer, D. 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, pp. 1035-1046, New York, NY, USA, 2018, ACM.
Lai, K. A., Rao, A. B., and Vempala, S. Agnostic estimation of mean and covariance. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 16, pp. 665 674, Washington, DC, USA, 2016. IEEE Computer Society.
Li, J. and Schmidt, L. Robust proper learning for mixtures of Gaussians via systems polynomial inequalities. Proceedings of the 30th Annual Conference on Learning Theory, COLT 17, pp. 1302-1382, 2017.
Liu, A. and Moitra, A. Settling the robust learnability of mixtures of gaussians. In Proceedings of the 53nd Annual ACM Symposium on the Theory of Computing, STOC '21, pp. 518-55 118-531, New York. NY, USA, 2021. ACM.
Liu, A. and Moitra, A. Learning GMMs with nearly optimal robustness guarantees. In Proceedings of the 35th Annual Conference on Learning Theory, COLT '22, pp. 2815- 2895, 2022.

---

On the Learnability of Distribution Classes with Adaptive Adversaries
A. Proofs
A.1. Proof of Lemma 5.3
Proof. By definition of (y, conofuusinn of C-generated samples of size m, there are distributions and [Q] E A(C), such that
for every q E Supp(Q), we have (pv g) > and
dIv((v((Q1"",, (2(x))) <.
Assume by way of contradiction that there is learner A such that for every E C,
PP P
(Tv(A((((S)).))
21 < 2 2
1 {
and
Pswnm (dv((A(V((S))))>
2
<
In particular, this means that for p E C, have
1
(
{
PSupm (dv((A(((S)))) S
2
21-
2
=
+ 2
and
21 1 PS-pmm (dTv(A(V(SS).p) -
5
1
(I)
2.
2
2
We note that for any P1, P2 with drv (p1,p2)) < d and any predicate F, we have
Pr-p [[()) d < P Tmp [F(x)] s Pa-ppll [F(x)] + d.
Thus, for meta-distribution Q with drv (Vi(Q V2(p"))] < we have,
PS-1QI" (S)), < 7 2
2 Paupm (dT)(A(((SS)).) S 21 - 22
1 C
C
(2)
2
2
2
2
2
Furthermore, we have
(Iv(A(((()))))) 21
max PS (Esupp(()
W
P Po~QPP S
(I)(A( 2
Definition of !Q]"
IP 1S
(S))
Ç
(2)
(3)
2
Let
Gmax = arg max Ps-am (TV((A( S 2 gEsupp(()
Recall that, for every q e supp(Q). we have (rv y. Thus triangle incquality yields
(Av(((V)(S),, lmaxx + drv (S))) 7.
Thus, (Tv( < implies (Tv(A(V((S), (max)) > z.8 yielding,
IP Singuax
ddw (A(v((S)) (max) >
2.
(dv((AVV(SS). - 71
IV
Snagmax
2
(
M(
2 2
This contradicts our assumption on A, which proves the claim.
12

---

On the Learnability of Distribution Classes with Adaptive Adversaries
A.2. Proof of Theorem 5.2
Proof. Assume by way of contradiction that there was successful a-robust learner A with sample complexity me for with respect to V C (Vi, V2).
Let
= min { 2
{--S 88}
and
min(t/,'' max m2)}.
Furthermore, let m me V.a
(c,
According to the assumptions of the theorem, we know that the pair (Vi, V2) successfully (7, ---oofuses C-generated samples of size m with
7 = 2a max(n); 12) + 2y.
Now consider
a 1/1 + m +
2
With the same argument, have 7/2 + < 3. Now using Lemma 5.3, infer that there is distribution such that either
Supm (VVV( a. +e]
dIv(A((((S)),r) 2 2
2 P P
1 2
2 6.
or
P Snym (d(v 2a-m+
> Ps |drv (VVV) 2 2
C
2
=
2
This is contradiction to the assumption that a a-robust learner of with respect to V with sample complexity m m.... Furthermore, if V1 Vz, then Vi is universal o-adversary.
A.3. Proof of Lemma 5.5
Proof. We will start by making observations for the adversary Vaub., for arbitrary 0, and later discuss how to choose for given a. Similarly, we first start by making observations for general n, i, 1 E N and then discuss appropriate choices for these numbers.
We first note that for p = Pi.j.k with [B = 22" and Dimnj.k = {Dr.jA By C B [B 2",, we have that for every q E Dimj.
1
1
drv(p.
2
drv (UB.xY,UUB,xU
1
1
Tr
Furthermore, consider Q U
13

---

On the Learnability of Distribution Classes with Adaptive Adversaries
We that the distributions Vu (p"h) and Vy (IQIm)) both distributions over multisets S' constants(S") odds(S)) (5") (dd Uindicators we have
). We note that for any two samples Sy X and Sy E x by definitions of constants, odds, ind,
S. O S
(constants(S.) n constants({))) U (odds(S")) n (odds(())) U (ind(S%) n ind()))). Where each of the three sets (constants(S") n cconstants($g) (odds(S') n (odds(S))), (ind(S)) n (nn())))) are pairwise disjoint. We can thus write the total variation distance between Vanb, (p") and Vaub.g ( [Q as
drv (Veb, (p"",, Veub. (IQ) ('))
drv (evnstnstantss (V (p"")) )), vonstantssVVuu.nn
+ drv (Vub,ds" odds(Vanb.
+ drv (ind(Vsub,, (ld((
For distribution P E A(X*) over sets, we define the distribution count(P) A(N) by
BB C N: count(P)(B) PPs~P[[S] E B).
We note that the distributions of the count of each of the subsets the same for both Veub, (p") and Vaub.n((Q1(m). That is,
drv (count (constants (aannstantttsaiiiiiii (p"))) (Co.oosstttttsaauso(e ()) = 0,
drv (count((odds(Vvuu.yy count(odds(V.mb.,(10 ))) = 0,
and
drv (count (indicatiinniittttss/eaaa...
= 0.
Furthermore, for two different samples S. and S,, constants(S.) = constants(S,) if and only if |constants (S.)l (S)) Thus,
drv Eev(constants/Vauur(""""" constants((Vau,,((([")) =
Furthermore,
I P Von (odds.oooom = and there are no repeated elements odds(S')) =
Ps (0
and there are no repeated elements in odds(S')),
since both |Q] m and p" give equal weights to all subsets of B, the same size. Lastly, we note that while the indicator of samples from p and samples from Q differ, the adversary Vaub., deletes all these elements, if [indicators(S) does not exceed the budget-count.
Taking all of these observations together, bound the total variation distance in terms of repeating elements in odds(S) and the probability that [ind(S) exceeds the budget of the adversary.
drv Now(Veuter (Vsub,n (p"), Veub, (IQI"))
drv (constantss (p"))) constants(Vuub../
drv (odds
odds(Veu...
drv (rrv(in((Vsaii (ind(VVub.rr("")) ind (VV(subr(((QI"""))
P P (odds(S) contains repeated elements]
PP>iQ/= (odds(S) contains repeated elements]
Pssspmliine (ind())))))))))))))))))))))))))) > S|]
F PP [indd [indd()] > S]]]]
14

---

On the Learnability of Distribution Classes with Adaptive Adversaries
The first terms can be bounded via a birthday paradox:
(1- (1
m 2
Psspp (odds(S) contains repeated elements] + (Ss-iq/m(odds(5 contains repeated elements] S 2
The last two terms can each be upper bounded by using Markov's inequality:
2 kn
IP S [[nd((S) > s/|1]] + (( > 7/S1] S
A 77m
Since we are considering distributions in Cy. we note that the distributions Di.m..k need to be of the form Da,nd. We now want to argue that for appropriate choices of j and 7) (both independent of m), as well as for an appropriate choice n given m, the inequalities the theorem are satisfied.
First, we note that since g grows faster than linear, it is possible to pick j in such way that it satisfies the inequality
g 2 max(1024aj]]
Given such j, we then pick 1j = 9(}
and 7 9(5) This ensures, that for every n and every q E Dam.s.ati) we get
1
drv(p,
2
2
9(5)
1
1024a
2
g(5)
9(6)
256a
g(j)
pom + 4yy-
Then, for every 2 1, if we choose
2 1-(1-
-t 1/m get
drv (Vauh,, (p") (aub..((Q11) (Q)
2
+
- 1
m
my
90)
32
2
20)
<
1
+ 2
- (1
[
mm
m m
16
c-
2
<
2xep
-2m
+2
1
g(î)
171
3
1
1
+
2
16
32
A.4. Proof of Theorem 6.1
Proof. While in the main part of the paper, we often use the same notation for random variable S ~ >- and a specific sample set S E X*, in order to make this proof more formal, we will now distinguish between random variables S ~ pm which we keep writing with capitalized notation and specific sample set E X for which we use non-capitalized notation.
We note, that since adversaries V are in general randomized, for every s E X", V(s) is a random variable with samples in E x For every adversary V. let us denote the distribution of random variable V(s) by Pv(a)-
15

---

On the Learnability of Distribution Classes with Adaptive Adversaries We note, that for random variable S ~ pm the distribution of the random variable V(S) defined for every B X by
PV) = /
J'EB JEX (pv(s)(s(ddr(s)
Accordingly, we have
dpv [ dpv(o)(('drrs))
JOEX-
We now want to formally define the reverse mapping fv.n.e' that, when given an input sample S' V(S) with ~ rm outputs sample S" pm That is, roughly, JV, (s) = P [S s(V(S) s'].
For distribution over X and an adversary V, let consider the random function Jv. that takes input sample s' E X and outputs element of X according to the probability distribution pv 1,,," which for every B C X is defined by
Seen (sp(s)
Pv (B) JSEN (s')d)
Similarly,
(s dpv 1n JOEX (pv(s)
Thus, if we consider the random variable S" = (V))) for some S ~ r, we get S" ~ r, as desired:
P (V. e B"1
MEEn JSEX [
dpv- (s" (s)))
JNEX
dpv(rn(( (d')dr(s")
JEB"" JSEX JEX JAMEX dpv (8' (r)ddr(("") (s (s))dr(s)
J J'BB" JS'E
SSEX dpv (s')dr(s) (sdddd(()cr)))))) (s')dr(ss))
S dpv(s"") (s') (s')dr(s")) (s"")
J I
Seex- dpv (8) dr((s) (pv(en)6')ddll Je dpv (s")dr(s"))
J'EB" JEE
I (p (s')r((s)
8"EB" SEER.
dr(s")
8"EB"
PS E B").
We note, that by the same argument, we can factorize in the following way:
r(B) f / dpv.r(s')dpu (s).
sEB J
Now consider subtractive adversary Since it is subtractive adversary, we know that for every n and every E supp(pv..x(e) C -1=(1-6)mm X', we have s' 8.
In particular, this means that for every s n and every s' supp(pran(()) we have = (s S'). Now let (s) (v) \ with the corresponding probability measure.
Py P (B) = Pv D,n
16

---

On the Learnability of Distribution Classes with Adaptive Adversaries
where B' Us 8 B).
Now consider the (randomized) additive adversary Vadd,r, defined by:
Vadd,r (s) SU (Vaub(()))) Yub
Thus for the corresponding probability measure for the random variable vadd,r is defined by
PVaaa, - (6) (B") = S I (s')pp-
(6")1(8" = -'
aubin.
Furthermore, for every probability distribution we have.
P s~ul (add,r(S) E B"1
{ dpv (s)""
J JOEX
{ I S JOEX" JOEX
S JSEX- dpvins(s) (dv wn (s") = s'' (d)(s(())
[ -eregr I I I Jrex. 118" s JEEX. JOEX-
WEX-
Now consider the additive adversaries pm and Qqi"..
drv (Vadd (IQI Qmdd.IQ! (p
1
{ SXE 1
/ J dp (on))
1exx dpvnaa (8
(( (s)
2
1
If Jeea I J 1s8" ss U s'U ( (s" \ q/ (s))dd))))))))) =00 (s)dpv pm pm
2
2
JOEX
SEeX JSE Sx 1is" = us((ss (s" (s')ddrsa. (1 1
[dpymt..1) (6') dpv (m''))
J JSEX.
I JarEx- 115" = s U(s (S) =00"
1
[ IdpVmn..Q/mm55) (5') dpvinb.mm (s'))
2
S'Ex
V1 [ JanEx 11s" s'u (s)))(ss")))ddvv- (s))ddv--..q mi (s)dpv o (s")
JIMEX
SEXM
1
- 2 /EEX Idprisb.lqpm (8") dpVaut.pmm (s'))
drv (PVauapn PVan. qmm) SC
where we get the second to last step by noticing that the last three integrals are a conditional probability distribution the additive adversary outputting s" conditioned on the subtractive adversary outputting s'. As such, these integrals equate to
17

---

On the Learnability of Distribution Classes with Adaptive Adversaries
Furthermore, note that if Vuu has fixed constant budget with ypm 1 < budget (Vsub, m) 1pm, then we have
vadd, |s|
budget add (Vaddr;; m) = sup 5
8
[s s + [s"|
sup Se
sup
sup
88]
sf supp (ouppppvvie (p) s" Esupp Premh. (0'))
mm (m (nm 1)) 1-
m
mm
(m
1pm) I-1
< max
m
+ m - T7m
max
14 +
1)
m(1
11
max
71) 11
m
+
77m7
In particular, this means, that
71 m budget. add (Vadd, m) S nm + (1-1) n)
We note that n T-n is strictly monotonically increasing in 1/. Thus, for v < 1/2 we thus get,
m- budget (Vadd,r, m) < 1pm + 2 = =mm + 1.
Thus, budget add (Vadd,r) S
A.5. Proof of Theorem 7.1
Proof. Let u be a random variable that uniformly distributed over [A: + 1] = -O,.... kJ. Now Vadd,a be defined by the probability distribution
-f Jeex- dpvzaste)(s')
dpvasa.cco (8")
k Eher
1
" Jeer (IT 2 i]dpy- yil ( + 1 < ildp pm am
w=ll u=0 nEx
U(sr (0))))0))
1 8" d-
18

---

On the Learnability of Distribution Classes with Adaptive Adversaries
We now note that
[ dpv (8" dp)
= JeE Lvex
(P)
I
(uf 2 ie + 1/u < y ,s (S:))
1:
a=0 SIEX
8 =
dpVaab. (5')
dpv dpvomb.umm..
sEx
m 1/u < ildpy va o (s:))
SEE
SLE
(Usr)) (o))))))
k
1 8" ="=
Similarly,
Je dpv (s ds")dp""
dpvant.iqim155 (5) Jsex- dpv 1m
w= MEE S
(IE 2ldp 1|u < i dddpy- pm pm (5:))
Ulss ((er).o)) 1o0)) \ot)
1
8" = u((ss)))
We now note that
/ NEX
(o)(( - / (ovm SC.
and
dp dpv (8) Inexx" " -SSex (T 2 ilddy- 1ld m + 1[u < ildp pm (8:))
k:
1m sEx
U (1ex1100)
11
8" - -U=sU(s)i
dpv (p I SSSex" - (uf=o(alu 2 ildp, ildpy.ttee ". (0)) + 1lu < ildp wm of (si))
k+1 u=0 NEX-
(Uler)ot) 100))0))
1 " = =s ==s'((s)ss)) (
1
dpy dpV (s SIEXi J (IP - s" = ='=((((s))
(Ule) !
ks JoEX.
(-)
dpv. dpv.at..m. (S) { SxEE "" (np
oub pm (8:) 1 s" s"=s' U1. |
k+1 JsEx
1+1
19

---

On the Learnability of Distribution Classes with Adaptive Adversaries
This means that
1
(/ (6 (o do
(evaVaaa.( Vadd, "Vad", ((Q))))
2 xxEx*
1
5< + (1 - 5) k: +11
Furthermore, we note that if Vub has a fixed constant budget with rym - 1 < m buddet (Vsub, m) S rym, then we have
Vadd, & (s)l - |s|
budget add (Vadd,, m) = sup SM
[s]
(nm 1) + (m - (1m - 1)) + A (m - (mm - 1)) 1 (m (1m - 1) m
max
m
sym + (m mmm) + k(m
sym)
( -1) 1)
m
S max { kn +
kn
kn
kn S kn + (1 7)m
(1 1) mm
In particular, this means, that
kn
budget add (Vadd, m) S kipm
(1 7))
" 1- We note that
is strictly monotonically increasing in 17. Thus, for v <
1
we thus get,
2k
1/2
m m- buddet (Vadd,r: m) < knm +
1mm + 1.
1- 1/2k
Thus, budget add (Vadd,r) S njk
B. Additional Example for Usefulness of Lemma 5.4
In this subsection we give a short illustration of why the lemmas in Section 5 can be helpful. We give known example for the hardness of PAC learning of distributions, which also fulfills the indistinguishability condition of Lemma 5.4. Example B.1. Let X N. Let Ç E (0, Furthermore, let = UB for some set and let C {Un, B. B and [Ba] 2 2-1 and q Un, with indices i E N. It is easy to that for every Z. we have drv q:) 2 p(supp(y) supp(a:)
N with [ =
2
(-(1-))-m
2-m However, if we consider the distribution Q = Ue. the distribution IQ" m generates a sample by first producing a distribution 4i which is uniform over some random subset set B₁ C B with [B:| 2- [3| and then sampling S yg"h Note that since B, was selected uniformly at random and q: UB, every point E B has the same probability of appearing in sample S ~ [Q] th Similarly, every point Æ E B has the same probability of appearing in sample S' p² Thus, pd and !Q| cannot be distinguished from samples with no repeating elements. While samples from IQ| are much more likely to contain repeated elements (as the subset B, from which they are selected is much smaller than the set B), the likelihood of repeated elements appearing in S ~ 1Q|m is still very small. In particular, the probability of there being repeated instances in ~ 9h is fn
| 2--
upper bounded by 1 (1 -1- -- ......111..............
(1 m- 2-
172
<
27
2-m
yot
1
<)
1 (1 4m = ( by the birthday problem. Thus, the probability of distinguishing !Q) from pd can be arbitrarily small, i.c., (p 1Q < despite the large TV-distance between p and every q. This suffices to show that any learner A there exists q E CU {p) such that A will not succeed output a distribution with (A(S) q) < 1 m on more 2
than 1 - & of the proportion of samples S ~ nt
20

---

On the Learnability of Distribution Classes with Adaptive Adversaries
C. Alternative proof for f-robust learning
now consider a more general version robust learning, namely a version that allows the impact of the budget 7 to impact the guarantee via general function f. rather than just being scaled linearly for some a 2 1.
In particular, considering, f meeting the following requirements.
f(0)=0
f is continuous
f monotonously increasing.
The guarantee for f-robust learning is then a generalization of a-robust learning, where we can think of a-robust learning as the version where f is linear function. That f f-robust learning considers the following learning guarantee:
(Tv((((())))) - f()) +
Hence, we get the following definition.
Definition C.1 (adaptive f-robust with respect to adversary V). Let f [0, + 10. A class of distributions C is adaptively f-robustly learnable w.r.t. adversary V, if there exists learner A and sample complexity function m (0, 1)2 N, such that for every p E C, every E, (0, 1) and every sample size m 2 m V.J (E, () with probability 1 1-d.
(rv(A(((S)))p) & {(buuget(V)) +
Theorem C.2. Let C be a class of distributions and V 3 (V1, V23 a set of adaptive adversaries with budgets budget (Vi) 7h and Audget(V2) = 1/2- Let y E (0, and define
Yf = 2 max (f(m), + 2//-
If for every m E N the pair of adversaries (V1, V22) successfully (71x -csonuusssssees C-generated samples of size m, then is not f-robustly learnable with respect to V.
Furthermore, if V1 Vz, then V1 is universal f-adversary for
will now state the alternative proof for this version.
Assume by way of contradiction that there was a successful a-robust learner with sample complexity me for with respect to V5 (V1, V2).
Proof.
Let
8 = 1-6 C
2
and
8 8=7.
Furthermore, let m mc (s, According to the assumptions of the theorem, we know that the pair (V1, V22) successfully (7,, -onofuuee C-generated samples of size with
YF 2 max ([(m). + 22
Now consider
((m)+e f(m) + +
If
21

---

On the Learnability of Distribution Classes with Adaptive Adversaries
With the same argument, have f(m) + z. Now using Lemma 5.3, we can infer that there is distribution such that either
S (drv(a(((()),r> f(h))
2 P (Tv(A(((())))) 2
1 =6.
2
2 2
or
PSnr ( (A(V2 (()))))))))))))))))))))))))))))) +
2 P (2v((((((()),r) 7f 2
--
2
This is a contradiction to the assumption that A is a f- learner of C w.r.t V with sample complexity me Furthermore, V1 = V2, then V1 is a universal a-adversary.
Theorem C.3. For every continuous, strictly monotoneously increasing function J: 10 [0, [0,1] with f(0) = 0. There
class C such thatC realizably learnable, but not adaptively additive f-robustly learnable, nor adaptively subtractive f-robustly learnable.
now give a more formal version of this statement using the class Cg from previous section and describing a relation between and g that is sufficient for C, be realizably learnable class that is not f-robustlly learnable (for both the adaptive additive and adaptive subtractive case).
Theorem C.4. Let f: [0, 1] + [0, 1]. For every function g R + I. for every monotone function - with lima-N for which there exists j e N such that
1
32
2
4f
2j
g(j)
g(j)
for there exists a class C, with
Cg is realizably learnable with sample complexity m,r (e, 8) log (t) (1)
Cg is not adaptively additive f-robustly learnable. Moreover, there is an adaptive additive adversary Vada, that is universal f-adversary for Cg-
For every a 2 Cg not adaptively subtractively f-robustly learnable. Moreover, there is an adaptive subtractive adversary Vaubs that is universal f-adversary for Cg.
Proof. We note, that it is sufficient to show that there exists 7) E [0, 1] such that there is an adversary Veub with budget 7). such that there are '', (0, 1), such that for every N, the adversary Vsub successfully (4f(r) + 4y, conffuse C-generated samples of size m. According our assumption g. there exists such that
1
32
2
2 f
2j
g(i)
90)
32 Now choose 7 [()) 7' = 4g(3) and Ç = 8-
1
As in the proof of Theorem 4.1 we consider the class Cg and the distribution p= Pij.ke E C with =2|=222 22" and a set of
distributions Dimidaats) = (pr By B; Bxl 2n). As in the previous proof, we note that for every g E Di
22

---

On the Learnability of Distribution Classes with Adaptive Adversaries
have
drv(p,9) 2 ; g(i)
2
g(i)
Using our assumption on the relation between and well as the definition of j, we can further infer that.
1
drv(p. 2
drv
(UX(B,X))UBBxx0))
9
2
g
32
2f
+
9(
g
= 4 + 47
Now if we pick the meta-distribution Q as the uniform distribution over the set D Din) with the same calculation as in the proof of Theorem 4.1, we get
1. By
1-
drv (Veu,, (p""), (1Q) -
Thus, for every m E N the adversary Vaub successfully (4f(m) + -conuuussusssss Co generated samples of size m. Using Theorem 7.1 and Theorem C.2, we get the claimed result.
Since for every monotonously increasing, continuous / : [0, + [0, with S(0) = 0 and every j E N, there exists some E [0, 1], such that f(n) Jz. it is furthermore possible to define a function N. - such that g(i) 2 max 32 4j}. follows that,
2j
4j
1
f())
9(
32
((())
g())
Thus, for every monotonoulsy increasing, continuous function f: [0, 1] + [0, 1] with f(0) 0, there exists class C, such that C is PAC learnable in the realizable case, but not adaptively additively f-robustly learnable, nor adaptively subtractively f-robustly learnable.
However, it might not be the case that there is a universal counterexample that holds true for all functions continuous, monotonously increasing functions f with (()) = simultaneously. Whether this is the case remains an open question (for each of the following versions of robustness: adaptive additive, adaptive subtractive and oblivious subtractive).
D. Oblivious Hardness implies Adaptive Hardness
In the introduction, we argued that oblivious subtractive hardness immediately implies adaptive subtractive hardness. In this section, we want to make this claims precise. The adaptive adversaries that we consider this section have access to both a sample and the ground-true truth distribution p. Thus, they differ from the adaptive adversaries that we discussed in the main body of the paper which only required access to
23

---

On the Learnability of Distribution Classes with Adaptive Adversaries
We want argue that every successful oblivious subtractive adversary also defines successful adaptive subtractive adversary. Intuitively, any oblivious adversary has only access the ground-truth distribution p can be viewed as adaptive adversary that does not use any knowledge of the sample S. However, in order to make this claim precise, we first need to formally define oblivious adversaries. We also need to address the fact that the outputs of oblivious and adaptive adversaries are of different types and thus not equivalent: Oblivious adversaries take as input ground truth distribution p and output a manipulated distribution p', while subtractive adaptive adversaries take as input a sample S and output a subset of S' C
Oblivious Adversary An oblivious adversary Vobi : A()) - ((X) is function that maps ground-truth distribution p
to some manipulated distribution. When learning in the presence of oblivious adversary Vasl the training sample is i.i.d. sampled from the manipulated distribution (p).
Budget The budget of an oblivious adversary Vabi is defined by budget((Vot)) suppea(x) drv (p, Vobi(p))
Additive Oblivious Adversaries An oblivious adversary Vadd is additive with fixed budget if for every E A obl there exists some distribution r E ( such that Vadd (p) = (1 7)p + mp. It is easy to see that using the budget definition from above, we indeed have budget (Vordd = (u) drv Voll (p)) S n..
Subtractive Oblivious Adversaries An oblivious adversary abl is subtractive with fixed budget y, if for every p A(X), there exists some distribution E A(2) such that p = (1 - n) Vanl (p) + mpr. Similar to above, we have budget ( Vsub) = (()) (p, Vaub (p)) S n).
Learnability with respect to Oblivious Adversaries class C of distributions is a-robustly learnable with respect to class of oblivious adversaries V if there is learner A X + A(X) and function m (0, 1)2 - N. such that for every 5, E (0, for every C and every V E V, for every m 2 my (5, with probability 1 - ô over S ~ V(p)" we have
drv P) a (uduudeee(V) +e.
If a class C is a-robustly learnable with respect to the class of all oblivious adversaries, it is said be a-robustly learnable. If class C is a-robustly learnable with respect to the class of all additive oblivious adversaries, it is said to be additive a-robustly learnable. If a class C is c--robuslly learnable with respect to the class of all subtractive oblivious adversaries, it is said to be subtractive a-robustly learnable.
We now argue, that given a successful subtractive oblivious adversary Vobi, it is possible to define a successful (ground-truit truth aware) subtractive adaptive adversary Vadp : X' x A(X) + X².
Theorem D.1. Given a subtractive oblivious adversary VoSI with budger budget = y,. constants e, E (0, a sample size m E N and a distribution E ((x) such that
P VasVan (p)m- ml) [drv (A(S),)) > a- bVdget(Vobs) + +e] > 6.
Then there is subtractive adaptive adversary Vadp : X x A(X) - X", with (adaptive) budget m
[meil
1,, such that
8 (S)), S a buddett (Vadp) + 2
P
Proof. Since Vobi is subtractive with budget 17, there is r E A(X) with p = (1- Vobi(p) + rp. We want to define a subtractive adaptive adversary Vadp that takes into account and r in such a way that fulfills the requirement. We thus need to specify way in which elements of a randomly drawn sample are deleted. Let denote an abstract element "deleted element". We now define an element-wise
that is not element of X. An instance of can be thought of X x A(X) x A(X) + X'U (1} that randomly deletes according
randomized subproceedure to its probability (or density in the continuous case) of p(x) and r(z) respectively:
with probability p(w)-p-((e) p(m)
x
Element RanieeeddnRandDDDeeeeeeeee
with probability
(r(()
p(x)
24

---

On the Learnability of Distribution Classes with Adaptive Adversaries
Now for sample S ( Jm). we define the corresponding operation SamplelaandomDeleee X A(2)
A(X) + (1) element-wise (and independent) application of Fllemen[RandomDeeee
SampleeeantomDellteSSS.
SampleRRandomDellee((i,,,,, Fmm) ,.m. p.,.)) p,r)
==
[ElemeennaaroonDDelle((a,,, r),,).... Element. RandomDeelee((mmm
Now consider sample ~ p" now want to understand the distribution of SauplelaandomDeeeee(SS11 we note that since SampleRandomDeiete applies DlenmmetRandomDelltte on elements independently. we have SampleGandoomDelet(SSS p. r) Uzes ElennentKandoomDelleeee,,, p.r., where every z E independently drawn for x p can be understood as follows for
First,
according p. Now, the distribution q of ElementRanddomDeel
x' E X, we have
((z') = p(x') p(a') - r..''"))) - p(x')
(1 Vo)a(
since Eleedont p, r) can only elvaluate to x' if = x. Furthermore, for g(L) we get
/ p(x)
11 ()r(s) p(x)
= { n7. (()(()) =
q(L)
JaEX
ZEX
Thus, DeleeeaaandDDDeeeeeeS is distributed according to q", where g the deterministic distribution with all its mass on {1}. The distribution q"h can alternatively be understood as Vom( n)) for a binomial random variable between [y7m] and [ym], with probability greater 1 we have I [qpn]. We now define the (randomized) subtractive adaptive adversary Vadp as follows.
Vati + nD where ودي is
Binom(m, 11). Since the median of binomial distribution Binom(m, 77) is
The adversary that first applies SampleRandomDDelete/ p, to S to generate some sample S'.
It then checks, whether (S' n /x <
[mm]] )[S].
m
Case I: JS' (1- [ ||| Then in order to match the desired budget, the adversary selects subset S" C S
m
uniformly at random, such that |S"| + S X ((1
[xm]]]
))|S| and outputs S" (S' (2)..
Case 2: |S xx 2 (1 [mm]]
||S). In this case, the adversary outputs a subset S C (S' 0 X') which uniformly
selected at random and has size |S = ((1
S|].
By definition, the adaptive ad adversary Vadp has a budget of budget sub (Vadp: m) = m- [am]] >)s|| Lastly, we need to argue that
[xyss] 2 17.
8 2
P (dTv(A((ada))) p) S a budget(Vaap) +
We note, that the number of initially deleted elements |S| |S n X') corresponds to the previously introduced binomial random variable n. As argued before |S|| - SS' n X = n S [ym] with prohability at least ] Thus with probability at least
Case occurs, i.e., |S' nx) 2 (1
[ym]] J[S]. Furthermore, conditioned on Case occuring, (Sa distributed
m
according to (p) mm The assumption that
P Ps~Vas() (mm) (dT)(( > a budget(Vob)) + E) > 6.
therefore implies
Psmpm (dvV(((Vaap(S)) S a (budge((Vadp + + > 8
2
Corollary D.2. Ifa class of distributions C is not subtractive a-robustly learnable (in the oblivious case), it is also not adaptively subtractive a-robustly learnable.
This result directly follow from the previous result.
25


Reviews:
[{"review_id": "PHEPv35aS5", "reviewer": "Reviewer_TGTy", "summary": "The paper investigates the problem of learning distributions under an adaptive adversary, i.e., adversary has full knowledge of sample and can apply noise to the samples before passing it to the learner.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review! We are glad that the reviewer found the ideas in the paper quite interesting and the problem studied to be quite relevant.\n\n>...the theorems are clearly written and intution is relatively easy to fallow. Although, more focus on natural language explanations or a running toy example can help a lot more…\n\n> I think the authors have provided a very clear presentation in terms of ordering and framing of the theoretical results. However, I feel some toy examples could further aid clarity.\n\nWe are happy to hear that overall, the reviewer finds our presentation of results to be clear, intuitive, and easy to follow. Indeed, we acknowledge the benefit of toy examples and more natural language explanations for improved accessibility –  we will incorporate them in the next revision. Please see the reply to the below reviewer for a natural language explanation of the proof ideas in the current discussion period.\n\n> How critical is the superlinear growth of g?\n\nThe fact that we need superlinearity comes from the fact that we need the relation between the manipulation budget and the effect on accuracy to scale larger than linear in order to meet the definition for “not learnable”.\n\n> Do you have any intuition about what minimal properties of a distribution class can make it more robust to adversaries as defined in your setting?\n\nClasses that are agnostically learnable should be more likely to be robust to adversaries. As such classes where the Yatracos sets have finite VC-dimension should be robust.\n\n> Do you think these results fundamentally rely on TV?\n\nOur paper only discusses PAC learning with respect to TV-distance, which is a well-established setting in the learning theory community. While some of these effects might transfer to different divergence measures between distributions, our current examples might not go through for measures like KL-divergence, as KL-divergence requires distributions to have the same support to not explode, which is not the case or TV-distance (and is a property that we in our construction exploit).", "claims_and_evidence": "Main result (MR): There is a class of distributions C that is not learnable in the realizable setting in the presence of adaptive adversaries. \n\nC1. In my understanding Theorem 4.1, formally captures the fact that if adverseries are powerful enough to make seperated distributions (w.r.t TV, first two conditions of the theorem), close to each other (third condition of the theorem) then learning is not possible.\n\nC2.  Theorem 5.1 proves that adaptive subtractive adversaries can be “translated” into the additive setting, thereby establishing that if robust learning fails against subtractive adversaries, it also fails against additive adversaries.\n\nC3. Theorem 6.1 shows that there exists a class of distributions that is learnable but becomes unlearnable under adaptive adversaries.\n\nThe paper provides quite intuitive proofs and on of the main strategies is explained in section 4.", "methods_and_evaluation_criteria": "The authors use a general (quite intuitive) existing strategy (Lemma 4.2). Given two distribution classes C_1 and C_2, such that all distribution (p and q respectively) in the two classes are far apart in TV. And two adversaries, V_1 and V_2 acting on a distribution over C_1  and p \\in C_2, then for any learner there is atleast one distribution in C_1 \\cup C_2 such that learning it is not possible.", "theoretical_claims": "See Claims and Evidences. \nI did not check all the proofs. \nBut the theorems are clearly written and intution is relatively easy to fallow. Although, more focus on natural language explanations or a running toy example can help a lot more.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The paper addresses an important problem of distribution learning. And clearly presents the broader connection to general work in distribution learning.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Clarity: I think the authors have provided a very clear presentation in terms of ordering and framing of the theoretical results. However, I feel some toy examples could further aid clarity.\n\nNovelty: I found the ideas in the paper quite interesting and the problem is also quite relevant and natural.", "other_comments_or_suggestions": "See above", "questions_for_authors": "- How critical is the superlinear growth of g? Are there classes with milder growth for which a similar separation might hold?\n\n- Do you have any intuition about what minimal properties of a distribution class can make it more robust to adversaries as defined in your setting?\n\n- Do you think these results fundamentally rely on TV, being somewhat of a strict distance? maybe achieving adversaries for Wasserstein Distance is harder?  --- just a curiosity.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bo01EB83J5", "reviewer": "Reviewer_grGP", "summary": "Post rebuttal: The authors addressed my main concerns, and so I have raised my score by one point.\n--\nThis paper studies the question of whether learnability, or realizable learnability, in the PAC sense implies learnability against an *adaptive adversary*. There are multiple notions of adaptive adversaries, and the notion studied in this paper is the one popular in robust statistics. The adversary here receives i.i.d. samples from the distribution to be learned, and then can add some $\\epsilon$-fraction of arbitrary samples (not constrained to being sampled from some distribution), or remove some $\\epsilon$-fraction of the samples. The first type of adversary is called an *additive* adversary whereas the second type is called a *subtractive* adversary.\n\nPrevious work of Ben-David, Bie, Kamath, and Lechner (NeurIPS'23) studied a similar question when the adversary is oblivious. An oblivious adversary is one that is able to change the distribution by some bounded amount (in TV distance) *before* samples are generated, without the ability to edit the samples after seeing them. The work of BBKL shows that learnability implies robust learnability (against the oblivious adversary) in the additive case, but not in the subtractive case. For adaptive adversaries, the non-learnability in the subtractive case is implied by BBKL, but they left open (and explicitly mentioned as an open question) the case of adaptive additive adversaries.\n\nThe current paper settles this case, showing that -- unlike in oblivious adversaries -- offline learnability *does not* imply learnability against adaptive additive adversaries. Along the way, the authors show that additive and subtractive adversaries are equivalent in the adaptive setting (this is not true in the oblivious setting). The construction showing the non-learnability is an adaptation/modification of the proof of BBKL.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review! We are glad to hear the reviewer appreciates the significance of our results (c.f. “if new and correct, are significant and worth publishing in a top tier ML venue”). \n\nWe acknowledge fair criticisms made regarding writing. Indeed, the main critique of the paper is related to the presentation and organization of the paper, rather than the results themselves. These comments are certainly well-received, and we are happy to take them into account in future revisions. Here is a brief overview of the main ideas, which we plan to add to the paper (along with proof descriptions).\n\n**The goal**\n\nShow that adaptive additive adversaries are strictly stronger than oblivious additive adversaries.\n\n**(A) Establish a sufficient criterion for an adversary to render a class of distributions unlearnable [Theorem 4.1]**\n\nWe state a condition for an adaptive adversary, that when satisfied, means that it will foil any successful learner for the class. Roughly speaking, the condition asks for an adversary that is capable of taking samples drawn from TV-seperated members of the class and rendering their samples indistinguishable. When class members are separated by large TV distance, any successful learner must distinguish them via the drawn sample. Making use of the idea of a meta-distribution over members of the class, we demonstrate the conflict of the above two statements.\n\n**(B) Unlearnability criterion met for subtractive adversary $\\implies$ Unlearnability criterion met for additive adversary [Theorem 5.1]**\n\nFormally, if there is an element $p\\in C$ and a meta distribution $Q$ over $C$ that can be made indistinguishable by a subtractive adversary $A_{sub}$, i.e. $d_{TV}(A_{sub}(|Q|^m,A_{sub}(p^m)) < c$, then this adversary can be used to construct additive adversaries $A_{add,p}$ and $A_{add,Q}$, such that the resulting additive sample distributions are close, i.e. \n$d_{TV}(A_{add,p}(|Q|^m),A_{add,Q}(p^m)) < c$. \n\nAdversaries act on samples drawn from two different distributions to make them indistinguishable. However to communicate the main idea, let us talk in terms of simple point-sets rather than distributions.\n\n\nRoughly speaking, the subtractive adversary can remove part of the first sample $A$ or part of the second sample $B$ to leave behind a common coreset $C$. We can view the generative process of $A$ to be a sample from $C$ combined with a sample from $A \\setminus C$, and the generative process of $B$ to be a sample from $C$ combined with a sample from $B \\setminus C$. Hence to confuse the learner, the additive adversary just needs to add the “opposing piece”: mapping $A \\to C + A\\setminus C + B \\setminus C$ and mapping $B \\to C + B\\setminus C + A \\setminus C$. This introduces indistinguishability with only additions. This intuition is made rigorous in the proof of Theorem 5.1.\n\n**(C) Putting it together: giving a learnable class and constructing a subtractive adversary for it that satisfies the unlearnability criterion [Theorem 6.1]**\n\nWe use the same class that Ben-david et al. (2023) used to separate realizable and agnostic learning. It is a class where every member distribution has a unique identifying support element: this makes learning easy if the mass on that support element is high enough to guarantee being observed. It is also constructed to be difficult to learn if those those elements are removed. For this class, we construct an adaptive subtractive adversary that satisfies the unlearnability criterion (A). Via (B), we have a successful adaptive additive adversary. Ben-david et al. (2023) show that realizably learnable classes are learnable in the presence of oblivious additive adversaries, thus completing the separation.\n\n> Oblivious and adaptive adversaries in PAC learning has a rich history… I encourage the authors to mention more work of this type.\n\nThank you for pointing that out. We reference Blanc & Valiant (2024) which studies the PAC setting and includes a detailed review, but mistakenly did not mention these works. We'll update:\n\nIn the PAC setting, the study of oblivious and adaptive adversaries has a rich history. The agnostic setting of Hausler (1992) is the PAC analogue to learnability in the presence of *oblivious adversaries* in our setting. Indeed, in the PAC setting, learnability implies oblivious-adversary-robust learnability. The PAC analogue of the *adaptive adversaries* of the present paper has been studied under the name \"nasty noise\" (Bshouty et al, 2002). The malicious noise model, introduced by Valiant (1985) and studied in more generality by Kearns and Li (1988), can be viewed as a partially adaptive adversary (see Blanc and Valiant (2024) for further elaboration); it has inspired significant follow-up work (Klivans et al. 2019, Aswathi et al. 2017). For a more careful treatment of learning in the presence of adversaries in the PAC setting, we refer the reader to the excellent review of Blanc & Valiant (2024).", "claims_and_evidence": "Yes, it is a theoretical paper and the claims are proved.", "methods_and_evaluation_criteria": "NA - theoretical paper", "theoretical_claims": "I did not check the proofs, and in fact the paper was hard for me to follow from a technical perspective. More below.", "experimental_designs_or_analyses": "NA - theoretical paper", "relation_to_broader_scientific_literature": "I do not know of any concrete prior results implying the ones in this paper, but am not an expert on this topic.", "essential_references_not_discussed": "This seems to be one weakness of the paper. The interaction between oblivious and adaptive adversaries in PAC learning has a rich history, for example in the online version of PAC learning it is known that the combinatorial parameter that captures learnability and agnostic learnability is the Littlestone dimension (rather than VC dimension). I encourage the authors to mention more work of this type.", "other_strengths_and_weaknesses": "The results of this paper, if new and correct, are significant and worth publishing in a top tier ML venue. The quality of writing is not yet good enough however, and has seemingly prevented me from understanding the main ideas despite trying to put some effort reading into the main ideas. The authors dive straight to the proofs of the results, without providing intuition to the reader, and given that the results are somewhat technical this makes them hard to follow.", "other_comments_or_suggestions": "See the above bullet. I suggest for the authors to add either a section describing the main ideas in an easier to understand high level description, or include a high level description of each proof at the beginning of the proof.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}, {"review_id": "83z6X7b0bM", "reviewer": "Reviewer_Xzyp", "summary": "In *robust distribution learning*, the goal is to learn a distribution p in some known class C given samples from p. The goal is to learn p up to some small total variation distance -- that is, find some hypothesis distribution q such that TV(p,q) is small. The twist is that a small fraction of the samples you receive have been modified by some malicious adversary. Robust learning and robust high-dimensional statistics have received extensive attention in machine learning and theoretical computer science in the last decade.\n\nA basic question is: how does the power of the adversary affect which distribution classes are learnable? A key distinction is between *oblivious* and *adaptive* adversaries. An oblivious adversary only gets to modify the distribution p itself, but the samples are still drawn iid from the modified distribution. An adaptive adversary sees the whole list of iid samples from p and then selects a small fraction of them to modify. It's clear that an adaptive adversary is at least as powerful as an oblivious one. This paper addresses the fundamental question: are adaptive adversaries strictly more powerful?\n\nThey answer this affirmatively, by constructing a class of distributions C and proving that C is learnable in the presence of an oblivious adversary but not in the presence of an adaptive one.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review! We are happy to hear that the reviewer appreciates the high quality of our writing and the significance of the open problem we resolve.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Did not check.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper has extensive connections to the literature on agnostic learning, distribution learning, and robust statistics. They are addressed capably in the paper and I will not repeat them here. The most salient connection is to a recent line of work directly addressing the difference between adaptive and oblivious adversaries for distribution learning. This paper answers a significant open question from that literature.", "essential_references_not_discussed": "none", "other_strengths_and_weaknesses": "The paper is very well written and addresses a fundamental question in robust learning.", "other_comments_or_suggestions": "none", "questions_for_authors": "none", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies distribution learning with adaptive adversaries in contrast to learning with oblivious adversaries. An adaptive adversary intercept samples and corrupt them before passing them to the learner, while an oblivious adversary can only modify the distribution the samples. Various theoretical results are presented, answering an important open question regarding equivalence of the adaptive and oblivious regimes.

The reviewers unanimously agree to accept this paper. For a camera-ready version, please take into the account the comments from all reviewers regarding for instance improving the writing and adding more references. In spite of this, the reviewers still support acceptance of this paper.
Decision: Accept (poster)