mlsanityData to 7 Oct 2026

Optimistic Rates for Learning from Label Proportions

arXiv 2406.00487 ↗First posted 1 Jun 2024cs.LG cs.AI stat.MLcited by 5

Not on the map. Why?

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.

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

Builds on

13 of 43 references.

References · 13

  1. 2014On Learning from Label Proportionscited by 38
  2. 2019Deep multi-class learning from label proportionscited by 33
  3. 2022Learning from Label Proportions by Learning with Label Noisecited by 30
  4. 2017Weakly Supervised Classification in High Energy Physicscited by 21
  5. 2023Easy Learning from Label Proportionscited by 20
  6. 2021Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regressioncited by 17
  7. 2016Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learningcited by 16
  8. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11
  9. 2023Learning from Aggregated Data: Curated Bags versus Random Bagscited by 11
  10. 2022Lessons from the AdKDD'21 Privacy-Preserving ML Challengecited by 4
  11. 2023Uniform Convergence with Square-Root Lipschitz Losscited by 2
  12. 2024Learning from Aggregate responses: Instance Level versus Bag Level Loss Functionscited by 2
1 more
  1. 2024PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responsescited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025Nearly Optimal Sample Complexity for Learning with Label Proportionscited by 4
  2. 2025Optimal Learning from Label Proportions with General Loss Functionscited by 1
  3. 2026Statistical Learning from Attribution Setscited by 0
  4. 2026Learning Conditional Averagescited by 0
  5. 2026Learning from Label Proportions with Dual-proportion Constraintscited by 0