Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.05355 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916766832132096 |
|---|---|
| author | Busa-Fekete, Robert Dick, Travis Gentile, Claudio Kaplan, Haim Koren, Tomer Stemmer, Uri |
| author_facet | Busa-Fekete, Robert Dick, Travis Gentile, Claudio Kaplan, Haim Koren, Tomer Stemmer, Uri |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05355 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nearly Optimal Sample Complexity for Learning with Label Proportions Busa-Fekete, Robert Dick, Travis Gentile, Claudio Kaplan, Haim Koren, Tomer Stemmer, Uri Machine Learning 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. |
| title | Nearly Optimal Sample Complexity for Learning with Label Proportions |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.05355 |