Research map / Learning theory and algorithms / Sample complexity
Fast Co-Training under Weak Dependence via Stream-Based Active Learning
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.
Gives a black-box reduction from stream-based active co-training under λ-weak dependence to mistake-bound online learning, plus VC-based and k-interval/homogeneous-halfspace co-training algorithms with error-independent label complexity.
Problem
Co-training is classical semi-supervised learning, but very few hypothesis classes are provably efficiently learnable via co-training under the weak dependence assumption, and agreement maximization is computationally hard (e.g., halfspaces).
Approach
Use label queries in the stream-based active model: run online learners on both views, query only when their predictions disagree (a guaranteed mistake), and stop when the pair agrees on many examples and is provably close to the target or a constant; this yields error-independent label complexity tied to the online mistake bound.
Key results
- Reduction makes Õ(M/α) label queries from an online learner with mistake bound M, independent of the accuracy ε; gives Õ(1/(γ²α)) label queries for γ-margin halfspaces via the perceptron.
- Any VC class of dimension d gets Õ(d log(1/(λε))/α) label queries, but the generic algorithm (Halving) is not computationally efficient.
- Efficient algorithms with Õ(k² log(1/(λε))/(λα)) label queries for k-unions of intervals and Õ(d² log(1/ε)) for homogeneous halfspaces under a reflective symmetry assumption.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive label queries and online learners under λ-weak dependence | Co-training for classes with mistake-bound online learners · λ-weakly dependent co-training | label queries: ˜O(M/α) versus ˜O(M/ϵ) | Helped |
| Use co-training for VC classes instead of passive supervised learning | VC classes with dimension d · λ-weakly dependent co-training | label complexity: ˜O(d log(1/(λϵ))/α) versus ˜O(d/ϵ) | Helped |
| Use interval-specific co-training updates | LEARNK-INTERVAL · k-unions of intervals | label queries: ˜O(k2 log(1/(λϵ)) + k/α) | Helped |
| Use the approximate reflective symmetry assumption | Homogeneous halfspace co-training · Homogeneous halfspaces | label queries: ˜O(d2 log(1/ϵ)) | Helped |
Surprising findings
- Generic VC-class co-training with the Halving algorithm achieves exponential label savings but is not computationally efficient.
Limitations
- Label complexity has a 1/α dependence on the bias of the target, which the authors note may not be necessary.
- Generic VC reduction via Halving is computationally inefficient.
- Homogeneous halfspace result requires an approximate reflective symmetry assumption on one marginal.
Experimental setup
Metrics: label complexity running time error
Baselines: Blum & Mitchell 1998 Blum & Mansour 2017 Wang & Zhou 2008
Builds on: co-training (Blum & Mitchell, 1998) Blum & Mansour 2017 weak dependence co-training Halving algorithm perceptron algorithm Forster's transform
Closest papers by meaning
- Online Active Learning with Surrogate Loss Functions (NeurIPS 2021 · similarity 0.88)
- Neural Active Learning with Performance Guarantees (NeurIPS 2021 · similarity 0.87)
- CoLAL: Co-learning Active Learning for Text Classification (AAAI 2024 · similarity 0.86)
- Universal Rates for Active Learning (NeurIPS 2024 · similarity 0.85)
- Instance-wise Supervision-level Optimization in Active Learning (CVPR 2025 · similarity 0.84)
- A Cross-Domain Benchmark for Active Learning (NeurIPS 2024 · similarity 0.84)
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.