Research map / Optimization / Nonconvex and smooth optimization
Nearly Optimal Sample Complexity for Learning with Label Proportions
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 sample-complexity bounds for learning from label proportions under square loss using variance-reduced ERM and SGD, achieving near-optimal dependence on bag size k (linear in k rather than k^2 or k^3), and validates on MNIST, CIFAR-10, Higgs and UCI Adult.
Problem
Learning from label proportions (LLP), where training examples are grouped into bags and only bag-level label proportions are observed, while the goal is individual-level regret; prior bounds scale poorly with bag size k.
Approach
Debiased bag-level square loss built from the bag label proportion and centered per-example predictions, combined with clipping/variance reduction, yields ERM and SGD guarantees with sample complexity k/β² (non-realizable) and k/β (realizable), and a matching lower bound for the realizable case.
Key results
- Theoretical sample complexity of ERM/SGD under square loss is k/β² (non-realizable) and k/β (realizable), improving on prior k²/β² and k³/β bounds; a matching Ω(k/β) lower bound holds in the realizable case with Δ=0.
- Empirically, the proposed loss achieves the highest test accuracy at every bag size and epoch count tested on MNIST, CIFAR-10, Higgs and UCI Adult, with the advantage largest at large bag sizes and few epochs.
- In a synthetic variance study, the proposed estimator's variance stays roughly constant (about 0.034) as bag size grows to 256, while Li et al. and EasyLLP variance grows linearly with k.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed variance-reduced LLP loss instead of the tested aggregate-loss baselines | CNNs and fully connected networks on MNIST, CIFAR-10, Higgs, and UCI Adult · all tested datasets, bag sizes, and training durations | test accuracy | Helped |
| use the proposed variance-reduced LLP loss instead of the tested baselines | CNNs and fully connected networks on MNIST, CIFAR-10, Higgs, and UCI Adult · short training runs | training convergence speed | Helped |
| use the proposed loss instead of Li et al. or EasyLLP | loss estimation on the synthetic distribution · synthetic variance comparison, bag sizes 2 to 256 | loss-estimate variance | Helped |
| increase bag size from the tested range up to 256 | the proposed loss estimator · synthetic variance comparison | loss-estimate variance: 0.034 to 0.055 | Hurt |
| use the proposed method instead of the method from the cited prior work | CNN on CIFAR-10 · CIFAR-10, bag size k = 2^6 | test accuracy: around 0.65 to above 0.8 | Helped |
| use the tested methods instead of the method from the cited prior work | neural network on Higgs · Higgs, sufficiently large bag sizes | test accuracy: below 0.6 to above 0.65 | Helped |
| remove clipping from the proposed loss (ablation) | proposed LLP loss · learning experiments | test accuracy | No clear effect |
| reduce bag size dependence in the sample-complexity guarantee from quadratic to linear | ERM for square-loss LLP, realizable setting · realizable LLP | sample complexity: n = \widetilde O(k^2/\beta^2) -> n = \widetilde O(k/\beta) | Helped |
| reduce bag size dependence in the sample-complexity guarantee from quadratic to linear | SGD for square-loss LLP · non-realizable LLP | sample complexity: n = \widetilde O(k^2/\beta^2) -> n = \widetilde O(k/\beta^2) | Helped |
Surprising findings
- The paper notes that its earlier reported baseline (Li et al.) had a measurement bug that made it look better than it was, which was fixed in the revision.
Limitations
- Theory covers only the square loss and binary classification; extensions to log loss and multiclass are open.
- The realizable-case algorithm for two hypotheses does not extend easily to non-realizable settings or practical model classes.
- The main theorem applies only when bag size k is large enough (k = Omega(1/beta)).
Experimental setup
Datasets: MNIST CIFAR-10 Higgs UCI Adult
Benchmarks: MNIST CIFAR-10 Higgs UCI Adult
Metrics: test accuracy at individual-example level empirical variance of loss estimates
Baselines: VanillaSQ VanillaCE Li et al. debiased square loss EasyLLP
Builds on: Learning from label proportions debiasing (Busa-Fekete et al. / Li et al.) EasyLLP proportion matching
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.88)
- Forming Auxiliary High-confident Instance-level Loss to Promote Learning from Label Proportions (CVPR 2025 · similarity 0.88)
- Probably Approximately Precision and Recall Learning (NeurIPS 2025 · similarity 0.87)
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.86)
- Uncertainty Herding: One Active Learning Method for All Label Budgets (ICLR 2025 · 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.