Research map / Learning theory and algorithms / Sample complexity
Algorithms and Hardness for Learning 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 |
|---|---|---|---|
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] bags · small margin, d=10, m=50 | avg % bags satisfied: 6.3 -> 93.0 | Improved |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] bags · small margin, d=10, m=100 | avg % bags satisfied: 4.4 -> 97.1 | Improved |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] bags · small margin, d=40, m=50 | avg % bags satisfied: 4.8 -> 81.9 | Improved |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] bags · small margin, d=40, m=100 | avg % bags satisfied: 4.4 -> 83.0 | Improved |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] test · small margin, d=10, m=100 | instance-level test accuracy (%): 53.2 -> 98.6 | Improved |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] test · small margin, d=40, m=100 | instance-level test accuracy (%): 52.0 -> 90.1 | Improved |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] bags · large margin, d=10, m=50 | avg % bags satisfied: 46.3 -> 51.0 | Improved |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] bags · large margin, d=10, m=100 | avg % bags satisfied: 46.5 -> 55.9 | Improved |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] bags · large margin, d=40, m=100 | avg % bags satisfied: 40.9 -> 40.2 | No clear effect |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] test · large margin, d=40, m=50 | instance-level test accuracy (%): 53.2 -> 52.9 | No clear effect |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] test · large margin, d=10, m=100 | instance-level test accuracy (%): 63.1 -> 75.1 | Improved |
| use the SDP rounding algorithm instead of a random LTF | LLP-LTF[3] bags · large margin, d=40, m=50 | avg % bags satisfied: 41.2 -> 43.5 | Mixed |
Closest papers by meaning
- Learnability of Linear Thresholds from Label Proportions (NeurIPS 2021 · similarity 0.97)
- Nearly Optimal Sample Complexity for Learning with Label Proportions (ICML 2025 · similarity 0.89)
- Rethinking Learning from Label Proportions via Moment Matching (NeurIPS 2026 · similarity 0.87)
- Forming Auxiliary High-confident Instance-level Loss to Promote Learning from Label Proportions (CVPR 2025 · similarity 0.86)
- Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation (ICLR 2024 · similarity 0.86)
- Taming the Sigmoid Bottleneck: Provably Argmaxable Sparse Multi-Label Classification (AAAI 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.
