Research map / Learning theory and algorithms / Sample complexity
PAC Learning Linear Thresholds from Label Proportions
Anand Paresh Brahmbhatt, Rishi Saket, Aravindan Raghuveer
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 |
|---|---|---|---|
| use A2 instead of random LTF baseline | LLP LTF learner · N(0,Sigma), d=10, q=2, k=1 | test accuracy: 78.26 -> 98.12 | Improved |
| use A2 instead of SDP algorithm for q=2 | LLP LTF learner · N(0,Sigma), d=10, q=2, k=1 | test accuracy: 88.40 -> 98.12 | Improved |
| use A2 instead of SDP algorithm for q=3 | LLP LTF learner · N(0,Sigma), d=10, q=3, k=1 | test accuracy: 67.31 -> 98.27 | Improved |
| use A2 instead of SDP algorithm at higher dimension | LLP LTF learner · N(0,Sigma), d=50, q=2, k=1 | test accuracy: 57.83 -> 95.64 | Improved |
| use A2 instead of SDP algorithm on general Gaussian | LLP LTF learner · N(mu,Sigma), d=10, q=2, k=1 | test accuracy: 90.10 -> 98.18 | Improved |
| use A2 instead of SDP algorithm on general Gaussian, d=50 | LLP LTF learner · N(mu,Sigma), d=50, q=3, k=1 | test accuracy: 62.39 -> 95.6 | Improved |
| use A2 instead of random LTF at large bag size | LLP LTF learner · N(0,Sigma), d=50, q=50, k=25 | test accuracy: 55.76 -> 95.16 | Improved |
| use A2 instead of random LTF on general Gaussian | LLP LTF learner · N(mu,Sigma), d=10, q=50, k=35 | test accuracy: 62.86 -> 97.6 | Improved |
| increase dimension from 10 to 50 | Algorithm A2 · N(0,Sigma), q=2, k=1 | test accuracy: 98.12 -> 95.64 | Hurt |
| increase bag size q from 2 to 50 (balanced-ish bags) | Algorithm A2 · N(0,Sigma), d=10 | test accuracy: 98.12 -> 97.87 | No clear effect |
| increase bag size q from 2 to 50 at d=50 | Algorithm A2 · N(0,Sigma), d=50 | test accuracy: 95.64 -> 95.16 | Hurt |
| use non-centered general Gaussian instead of centered Gaussian | Algorithm A2 · d=50, q=10, k=8 | test accuracy: 94.34 -> 94.44 | No clear effect |
Closest papers by meaning
- Rethinking Learning from Label Proportions via Moment Matching (NeurIPS 2026 · similarity 0.90)
- Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation (ICLR 2024 · similarity 0.90)
- Forming Auxiliary High-confident Instance-level Loss to Promote Learning from Label Proportions (CVPR 2025 · similarity 0.87)
- Nearly Optimal Sample Complexity for Learning with Label Proportions (ICML 2025 · similarity 0.87)
- Learning from Noisy Labels via Conditional Distributionally Robust Optimization (NeurIPS 2024 · similarity 0.83)
- Hypothesis Testing for Class-Conditional Noise Using Local Maximum Likelihood (AAAI 2024 · similarity 0.82)
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.
