Research map / Learning theory and algorithms / Sample complexity
Transductive Learning is Compact
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 transductive sample complexity of supervised learning is compact: a class is learnable iff all its finite projections are, exactly for proper metric and continuous losses on compact spaces, with a factor-2 gap for improper metrics, and transfers approximately to PAC learning.
Problem
Whether the sample complexity of learning a hypothesis class in the transductive model can be detected from its finite projections (compactness), across loss functions and realizable/agnostic settings.
Approach
Casts transductive learning as a variable-assignment problem (variables = leave-one-out completions, functions = per-sample error sums) and proves a compactness theorem for such problems via Zorn's lemma and compactness of finite-constraint solution sets, yielding exact compactness for proper metric and compact continuous losses, and a generalized M. Hall matching theorem.
Key results
- For proper metric losses (and continuous losses on compact spaces), a class is transductively learnable with sample function m iff all its finite projections are, in both realizable and agnostic settings.
- For realizable learning with improper metric losses, there exist classes where the error rate exceeds that of all finite projections by a factor of 2, and a matching upper bound of 2 holds.
- Via PAC-transductive equivalence, realizable PAC sample complexity is compact up to a log(1/delta) factor and constant rescaling of epsilon and delta.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Compare a hypothesis class with all its finite projections under a proper metric loss | Realizable transductive learning · Arbitrary domain and proper metric label space | transductive sample complexity | No clear effect |
| Use a continuous loss on a compact metric label space | Realizable transductive learning · Compact metric label space | transductive sample complexity | No clear effect |
| Use a discrete 0-1 loss, including over an infinite label set | Realizable transductive learning · Multiclass classification | transductive sample complexity | No clear effect |
| Use a proper metric loss | Agnostic transductive learning · Proper metric label space | transductive sample complexity | No clear effect |
| Use a continuous loss on a compact metric label space | Agnostic transductive learning · Compact metric label space | transductive sample complexity | No clear effect |
| Use a discrete metric in agnostic learning | Agnostic transductive learning · Discrete label space | transductive sample complexity | No clear effect |
| Use an arbitrary metric loss instead of a proper metric loss | Realizable transductive learning · Finite projections versus the full class | transductive error rate: ξ_H(n) ≥ 2 · ξ_H'(n) | Hurt |
| Allow arbitrary metric losses while comparing the full class with its finite projections | Realizable transductive learning · Finite projections versus the full class | transductive error rate: ξ_H ≤ 2 · ξ | Hurt |
| Transfer compactness from transductive learning to realizable PAC learning | Realizable PAC learning · Bounded metric or continuous loss on a compact metric space | PAC sample complexity: O\big( m(\frac{\epsilon}{4e}, \frac{\epsilon}{4e}) \log(1 / \delta) \big) | Mixed |
Surprising findings
- Compactness of sample complexity can fail strongly for proper learners, showing a structural gap between proper and improper learning.
- For improper metric losses, exact compactness fails: the error rate can be off by a factor of 2 from finite projections.
Limitations
- Exact compactness fails for improper metric losses (factor-2 gap), and agnostic case gap is only conjectured.
- PAC transfer is only approximate (log(1/delta) factor; constant rescaling), and agnostic PAC link is weaker (factor 1/epsilon).
- Theory only; no empirical evaluation.
Experimental setup
Builds on: one-inclusion graph Hall's marriage theorem PAC-transductive equivalence gamma-OIG dimension
Closest papers by meaning
- Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale (NeurIPS 2026 · similarity 0.87)
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.87)
- A New Concentration Inequality for Sampling Without Replacement and Its Application for Transductive Learning (ICML 2025 · similarity 0.87)
- Testably Learning Polynomial Threshold Functions (NeurIPS 2024 · similarity 0.86)
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.85)
- Realizable $H$-Consistent and Bayes-Consistent Loss Functions for Learning to Defer (NeurIPS 2024 · similarity 0.85)
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.