Nearly Optimal Sample Complexity for Learning with Label Proportions
This work addresses the challenge of learning with partial label information for machine learning practitioners, offering incremental improvements in sample complexity and empirical performance.
The paper tackles the problem of Learning from Label Proportions (LLP), where only aggregate label values in grouped training examples are available, aiming to minimize individual example regret under square loss. It shows that the proposed sample complexity is nearly optimal and validates algorithms with improved accuracy using fewer samples on several datasets.
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.