# Optimistic Rates for Learning from Label Proportions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 43 references that are in the map.
- First posted on arXiv 1 Jun 2024.

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

- [On Learning from Label Proportions](https://mlsanity.com/paper/1402.5902/) (2014)
- [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)
- [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)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning](https://mlsanity.com/paper/1602.05916/) (2016)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)
- [Learning from Aggregated Data: Curated Bags versus Random Bags](https://mlsanity.com/paper/2305.09557/) (2023)
- [Lessons from the AdKDD'21 Privacy-Preserving ML Challenge](https://mlsanity.com/paper/2201.13123/) (2022)
- [Uniform Convergence with Square-Root Lipschitz Loss](https://mlsanity.com/paper/2306.13188/) (2023)
- [Learning from Aggregate responses: Instance Level versus Bag Level Loss Functions](https://mlsanity.com/paper/2401.11081/) (2024)
- [PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responses](https://mlsanity.com/paper/2402.04987/) (2024)

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

- [Nearly Optimal Sample Complexity for Learning with Label Proportions](https://mlsanity.com/paper/2505.05355/) (2025)
- [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 consider a weakly supervised learning problem called Learning from Label Proportions (LLP), where examples are grouped into ``bags'' and only the average label within each bag is revealed to the learner. We study various learning rules for LLP that achieve PAC learning guarantees for classification loss. We establish that the classical Empirical Proportional Risk Minimization (EPRM) learning rule (Yu et al., 2014) achieves fast rates under realizability, but EPRM and similar proportion matching learning rules can fail in the agnostic setting. We also show that (1) a debiased proportional square loss, as well as (2) a recently proposed EasyLLP learning rule (Busa-Fekete et al., 2023) both achieve ``optimistic rates'' (Panchenko, 2002); in both the realizable and agnostic settings, their sample complexity is optimal (up to log factors) in terms of ε, δ, and VC dimension.