Research map / Learning theory and algorithms / Sample complexity
Learnability of Linear Thresholds from Label Proportions
Rishi Saket
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 dimension d from 10 to 100 | Algorithm A · Uncorrelated random bags, m=50 | avg s/t: 2.162 -> 1.533 | Hurt |
| Increase dimension d from 10 to 100 | Algorithm A · Uncorrelated random bags, m=200 | avg s/t: 2.479 -> 1.297 | Hurt |
| Increase number of bags m from 50 to 200 | Algorithm A · Uncorrelated random bags, d=10 | avg s/t: 2.162 -> 2.479 | Improved |
| Increase number of bags m from 50 to 200 | Algorithm A · Uncorrelated random bags, d=100 | avg s/t: 1.533 -> 1.297 | Hurt |
| Use Algorithm A instead of best random linear threshold | Algorithm A · Uncorrelated random bags, d=10, m=200 | avg r/s: 0.688 | Improved |
| Use Algorithm A instead of best random linear threshold | Algorithm A · Uncorrelated random bags, d=100, m=200 | avg r/s: 0.994 | No clear effect |
| Use correlated bag geometry instead of iid points | Algorithm A · Correlated bags, d=100, m=50 | avg s/t: 1.533 -> 2.460 | Improved |
| Use correlated bag geometry instead of iid points | random linear threshold · d=10, m=50 | avg r/s: 0.847 -> 0.049 | Hurt |
| Use correlated bag geometry instead of iid points | Algorithm A · d=10, m=50 | min s/t: 1.714 -> 1.200 | Mixed |
| Algorithm A vs theoretical guarantee on synthetic instances | Algorithm A · Uncorrelated random bags, d=100, m=200 | avg s/t: 1.297 | Improved |
Closest papers by meaning
- Nearly Optimal Sample Complexity for Learning with Label Proportions (ICML 2025 · similarity 0.88)
- Rethinking Learning from Label Proportions via Moment Matching (NeurIPS 2026 · similarity 0.88)
- Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation (ICLR 2024 · similarity 0.86)
- Forming Auxiliary High-confident Instance-level Loss to Promote Learning from Label Proportions (CVPR 2025 · similarity 0.86)
- Taming the Sigmoid Bottleneck: Provably Argmaxable Sparse Multi-Label Classification (AAAI 2024 · similarity 0.85)
- A Trichotomy for List Transductive Online Learning (ICML 2025 · 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.
