Research map / Learning theory and algorithms / Sample complexity
More Supervision, Less Computation: Statistical-Computational Tradeoffs in Weakly Supervised Learning
Xinyang Yi, Zhaoran Wang, Zhuoran Yang, Constantine Caramanis, Han Liu
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase degree of supervision alpha (fewer label flips) | information-theoretic minimax detection rate for weakly supervised sparse mean testing · theory: Gaussian model, s-sparse mean difference, known Σ | minimax signal strength γ*_n | Improved |
| increase degree of supervision alpha (fewer label flips) | computationally tractable (statistical query) detection rate · theory: statistical query model, known Σ | computational boundary γ*_n | Improved |
| unlabeled-regime comparison: alpha near 0 (no supervision) vs alpha small but nonzero | weakly supervised detection · theory: small alpha region | information-theoretic and computational rates | No clear effect |
Closest papers by meaning
- Labels, Information, and Computation: Efficient Learning Using Sufficient Labels (JMLR 2023 · similarity 0.88)
- Learning from weak labelers as constraints (ICLR 2025 · similarity 0.88)
- Losses over Labels: Weakly Supervised Learning via Direct Loss Construction (AAAI 2023 · similarity 0.88)
- A General Framework for Learning from Weak Supervision (ICML 2024 · similarity 0.87)
- Weak Supervision Performance Evaluation via Partial Identification (NeurIPS 2024 · similarity 0.87)
- Don’t Label Twice: Quantity Beats Quality when Comparing Binary Classifiers on a Budget (ICML 2024 · similarity 0.86)
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.
