Research map / Learning theory and algorithms / Sample complexity
Generation from Noisy Examples
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.
Characterizes which binary hypothesis classes can be generated from noisy example streams (negative examples inserted), introducing the Noisy Closure dimension and proving that all countable classes are noisily generatable in the limit.
Problem
Language/hypothesis-class generation in the limit assumes noiseless streams of positive examples; real data contains a finite number of erroneous examples. The paper asks when binary hypothesis classes remain generatable when an adversary inserts finitely many negative examples into the stream.
Approach
Extends the closure-dimension characterization of generation to noisy streams by defining a scale-sensitive Noisy Closure dimension NC_n(H) indexed by noise level n, and builds generators that adaptively pick a noise-level estimate from the number of distinct examples seen, without knowing the true noise level.
Key results
- Uniform noise-dependent generatability holds iff NC_n(H) is finite for every noise level n; the sample complexity at noise level n is Theta(NC_n(H)).
- All finite classes are uniformly noise-dependent generatable (NC_n(H) < nq + d + 1).
- Every countable class is non-uniformly noise-dependent generatable and hence noisily generatable in the limit; noiseless non-uniform generatability implies noisy generatability in the limit.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use finite Noisy Closure dimension at every noise level as the criterion | Binary hypothesis classes · Uniform noisy generation | uniform noise-dependent generatability | Helped |
| Allow the sample threshold to depend on the noise level | Finite hypothesis classes satisfying UUS · Noisy example streams | uniform noise-dependent generatability | Helped |
| Allow the sample threshold to depend on the hypothesis as well as the noise level | Countable hypothesis classes satisfying UUS · Noisy example streams | non-uniform noise-dependent generatability | Helped |
| Allow a single inserted negative example | Uniformly generatable countable class · Uniform noisy generation | uniform noise-dependent generatability: C(H) = 0; NC_1(H) = ∞ | Hurt |
| Require generation guarantees to be uniform over the noise level | Uniform noise-independent generation · Classes with finite common-support intersection | uniform noise-independent generatability | Hurt |
| Use noiseless non-uniform generation to construct a generator for noisy streams | UUS hypothesis classes · Noisy generation in the limit | noisy generatability in the limit | Helped |
Surprising findings
- Uniform noise-independent generatability is impossible even for two-hypothesis classes, so the generator must depend on the noise level's sample complexity.
- A countable class exists that is uniformly generatable without noise but not uniformly noise-dependent generatable even with a single perturbed example.
Limitations
- Non-uniform noise-dependent generatability lacks a complete characterization; necessary and sufficient conditions do not match.
- Generatability in the limit characterization is left open.
- Computable generators are not addressed; results are information-theoretic.
Experimental setup
Builds on: Language Generation in the Limit (Kleinberg and Mullainathan 2024) Li et al. 2024 generation characterization Closure dimension characterization of uniform generation
Closest papers by meaning
- Contrastive Identification and Generation in the Limit (NeurIPS 2026 · similarity 0.86)
- On Union-Closedness of Language Generation (NeurIPS 2025 · similarity 0.85)
- Generating in the Limit with Infinitely Many Hallucinations (NeurIPS 2026 · similarity 0.85)
- Using Noise to Infer Aspects of Simplicity Without Learning (NeurIPS 2024 · similarity 0.83)
- On the Learnability of Distribution Classes with Adaptive Adversaries (ICML 2025 · similarity 0.83)
- No Free Lunch: Fundamental Limits of Learning Non-Hallucinating Generative Models (ICLR 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.