# Nearly Optimal Sample Complexity for Learning with Label Proportions

arXiv: https://arxiv.org/abs/2505.05355 · HTML: https://mlsanity.com/paper/2505.05355/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 45 references that are in the map.
- First posted on arXiv 8 May 2025.

## Builds on (most cited first, 13 of 13)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [On the Minimal Supervision for Training Any Binary Classifier from Only Unlabeled Data](https://mlsanity.com/paper/1808.10585/) (2018)
- [Learning from Label Proportions with Consistency Regularization](https://mlsanity.com/paper/1910.13188/) (2019)
- [Deep multi-class learning from label proportions](https://mlsanity.com/paper/1905.12909/) (2019)
- [Learning from Label Proportions by Learning with Label Noise](https://mlsanity.com/paper/2203.02496/) (2022)
- [Learning from Label Proportions with Generative Adversarial Networks](https://mlsanity.com/paper/1909.02180/) (2019)
- [Weakly Supervised Classification in High Energy Physics](https://mlsanity.com/paper/1702.00414/) (2017)
- [Easy Learning from Label Proportions](https://mlsanity.com/paper/2302.03115/) (2023)
- [Deep Learning from Label Proportions for Emphysema Quantification](https://mlsanity.com/paper/1807.08601/) (2018)
- [Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification](https://mlsanity.com/paper/2102.00678/) (2021)
- [PAC Learning Linear Thresholds from Label Proportions](https://mlsanity.com/paper/2310.10098/) (2023)
- [Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation](https://mlsanity.com/paper/2310.08056/) (2023)
- [Optimistic Rates for Learning from Label Proportions](https://mlsanity.com/paper/2406.00487/) (2024)

## Built on by (most cited first, 4 of 4)

- [Optimal Learning from Label Proportions with General Loss Functions](https://mlsanity.com/paper/2509.15145/) (2025)
- [Statistical Learning from Attribution Sets](https://mlsanity.com/paper/2602.06276/) (2026)
- [Learning Conditional Averages](https://mlsanity.com/paper/2602.11920/) (2026)
- [Learning from Label Proportions with Dual-proportion Constraints](https://mlsanity.com/paper/2603.21153/) (2026)

## Abstract (arXiv)

We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags, and only aggregate label values in each bag are available. Despite the partial observability, the goal is still to achieve small regret at the level of individual examples. We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal. From an algorithmic viewpoint, we rely on carefully designed variants of Empirical Risk Minimization, and Stochastic Gradient Descent algorithms, combined with ad hoc variance reduction techniques. On one hand, our theoretical results improve in important ways on the existing literature on LLP, specifically in the way the sample complexity depends on the bag size. On the other hand, we validate our algorithmic solutions on several datasets, demonstrating improved empirical performance (better accuracy for less samples) against recent baselines.