Optimistic Rates for Learning from Label Proportions

Gene Li, Lin Chen, Adel Javanmard, Vahab Mirrokni
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3437-3474, 2024.

Abstract

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 $\epsilon, \delta$, and VC dimension.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-li24b, title = {Optimistic Rates for Learning from Label Proportions}, author = {Li, Gene and Chen, Lin and Javanmard, Adel and Mirrokni, Vahab}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {3437--3474}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/li24b/li24b.pdf}, url = {https://proceedings.mlr.press/v247/li24b.html}, abstract = {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 $\epsilon, \delta$, and VC dimension.} }
Endnote
%0 Conference Paper %T Optimistic Rates for Learning from Label Proportions %A Gene Li %A Lin Chen %A Adel Javanmard %A Vahab Mirrokni %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-li24b %I PMLR %P 3437--3474 %U https://proceedings.mlr.press/v247/li24b.html %V 247 %X 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 $\epsilon, \delta$, and VC dimension.
APA
Li, G., Chen, L., Javanmard, A. & Mirrokni, V.. (2024). Optimistic Rates for Learning from Label Proportions. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:3437-3474 Available from https://proceedings.mlr.press/v247/li24b.html.

Related Material