Optimal Learning from Label Proportions with General Loss Functions

Motivated by problems in online advertising, we address the task of Learning from Label Proportions (LLP). We introduce a novel and versatile low-variance debiasing methodology to learn from aggregate label information, significantly advancing the state of the art in LLP. Our debiasing approach exhibits remarkable flexibility, seamlessly accommodating a broad spectrum of practically relevant loss functions across both binary and multi-class classification settings. By carefully combining our estimators with standard techniques, we improve sample complexity guarantees for a large class of losses of practical relevance. We also empirically validate the efficacy of our proposed approach across a diverse array of benchmark datasets, demonstrating compelling empirical advantages over standard baselines.

We explore how to train an AI when individual data labels are kept secret for privacy or anti-tracking reasons. Instead of knowing exactly what each person did, the AI only sees the label proportions—the percentage of people who performed an action within a large group (a "bag"). Previously, as these groups got larger, the "noise" (mathematical variance) in the data would increase, making the AI less accurate. This research introduces a debiasing technique that: - Keeps the estimation error low and stable, regardless of how many people are in a group, - Works with anything: It can be used with almost any type of mathematical "loss function" (the way an AI measures its own mistakes), including complex advertising and multi-category tasks. - Learns faster: It reaches the "optimal" learning speed, meaning it gets the most possible information out of the limited group data. This is a major win for online advertising, as major browsers (like Safari and Firefox) have blocked individual tracking to protect privacy, meaning advertisers now only get aggregated reports.