On the Learnability of Distribution Classes with Adaptive Adversaries

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.

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”).

We 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).

The goal

Show that adaptive additive adversaries are strictly stronger than oblivious additive adversaries.

(A) Establish a sufficient criterion for an adversary to render a class of distributions unlearnable [Theorem 4.1]

We 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.

(B) Unlearnability criterion met for subtractive adversary $\implies$ Unlearnability criterion met for additive adversary [Theorem 5.1]

Formally, 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. $d_{TV}(A_{add,p}(|Q|^m),A_{add,Q}(p^m)) < c$.

Adversaries 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.

Roughly 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.

(C) Putting it together: giving a learnable class and constructing a subtractive adversary for it that satisfies the unlearnability criterion [Theorem 6.1]

We 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.

Oblivious and adaptive adversaries in PAC learning has a rich history… I encourage the authors to mention more work of this type.

Thank 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:

In 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).

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.

...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…

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.

We 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.

How critical is the superlinear growth of g?

The 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”.

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?

Classes 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.

Do you think these results fundamentally rely on TV?

Our 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).