Research map / Label-efficient and robust learning / Recognition and long-tail

On the Learnability of Distribution Classes with Adaptive Adversaries

ICML 2025 · Label-efficient and robust learning › Recognition and long-tail · approach: Learning from unlabeled and positive-unlabeled data · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that realizably learnable distribution classes need not be robustly learnable against adaptive additive adversaries, answering an open question from prior oblivious-adversary work via a subtractive-to-additive reduction on a class C_g.

Problem

Whether distribution classes that are realizably learnable remain learnable when the adversary is adaptive (can inspect and manipulate the i.i.d. sample before the learner sees it), particularly under additive corruptions where oblivious adversaries are handled by prior work.

Approach

Introduces a general indistinguishability-based lower-bound technique for adaptive adversaries and shows that a successful adaptive subtractive adversary can be inverted into adaptive additive adversaries (including a universal one), yielding that a realizably learnable class C_g is not adaptively additively robustly learnable.

Key results

• Realizably learnable class C_g (sample complexity log(1/delta) g(1/eps)) is not adaptively additively alpha-robustly learnable for any alpha >= 1, via a universal additive adversary with budget about 2eta.
• A subtractive adaptive adversary V_sub,eta with eta = 32/g(j) successfully confuses C_g-generated samples of every size m, with TV at most 1/8 between manipulated sample distributions.
• This gives a separation: C_g is not adaptively additively robustly learnable, while oblivious additive 3-robust learnability holds for every realizably learnable class.

Measured effects reported in the paper

Surprising findings

• Adaptive additive and subtractive robustness are closely related, unlike the oblivious setting where subtractive adversaries are strictly stronger.

Limitations

• The separation uses a contrived class C_g with unbounded support; the authors note it is not a natural distribution class.
• The universal additive adversary has a higher budget (about 2eta) than the subtractive adversary.
• Results are purely information-theoretic and do not address computational efficiency.

Experimental setup

Builds on: Blanc et al. oblivious adversary robustness of realizable learners Lemma 4 indistinguishability-to-hardness argument from prior work Claim 3.2 realizable learner for C_g

Closest papers by meaning

• Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings (NeurIPS 2025 · similarity 0.87)
• Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.86)
• The Limits of Differential Privacy in Online Learning (NeurIPS 2024 · similarity 0.85)
• Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs (NeurIPS 2024 · similarity 0.85)
• Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.85)
• On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.85)