Rethinking Learning from Label Proportions via Moment Matching

AI summary

Overview

Research area: Weakly supervised machine learning, specifically Learning from Label Proportions (LLP), with connections to distributional moment matching and the Poisson multinomial distribution.

Technical level: Advanced. The paper assumes familiarity with multi-class classification risk, surrogate losses, factorial moments and tensor products, Rademacher-complexity generalization bounds, and the LLP problem setting.

Scope: The paper proposes LLP via Moment Matching (LLP-MM), a training framework that matches classifier-induced multi-order factorial moments to empirical moments computed from bag-level label proportions, motivated by a Poisson multinomial distribution (PMD) view of label counts under a "structured-bag" data-generation assumption.

What This Paper Is About

In Learning from Label Proportions, training examples are grouped into "bags," and only the fraction of each class inside each bag is revealed, while the goal is still to predict labels for individual instances. Most recent LLP methods assume bags are assembled by grouping instance–label pairs uniformly at random, but the authors argue this is often false in practice, since bags are frequently formed by shared attributes such as region, demographic group, or platform grouping key. The paper's goal is to design a training objective that remains effective when bags are structured rather than random, and that does so at a practical computational cost.

Key Contributions

1. A more realistic data-generation assumption and a new statistical view. The authors adopt the structured-bag assumption: bags are drawn i.i.d., the grouping strategy may depend on the individual examples, and instance labels are conditionally independent given the bag. Under this assumption they show that bag-level label counts are a sum of independent but non-identically distributed categorical variables, and therefore follow a Poisson multinomial distribution (PMD), so observed label proportions are a normalized PMD.

2. A moment-matching framework for LLP. Motivated by the PMD structure, they propose LLP-MM, which trains a classifier by matching classifier-induced multi-order factorial moment tensors against empirical factorial moments computed purely from the observed proportions. They show that classical proportion matching (PM) is the special case using only first-order moments.

3. Theory on why higher-order moments help. Proposition 3.1 shows that for orders 1 ≤ s₁ < s₂ ≤ m, the minimizer set with more moment orders is contained in the minimizer set with fewer, i.e., more orders give a tighter solution space that still contains the Bayes-optimal classifier. Theorem 3.2 gives a generalization bound in terms of Rademacher complexity, and Proposition 3.3 bounds the cost of the state-compressed computation of all moments up to order s as O(mq·C(q+s, s)) time and O(C(q+s, s)) memory per bag.

4. Benchmark evidence across bag-construction strategies. Experiments on CIFAR-10, CIFAR-100, and miniImageNet with bag sizes 16, 32, 64, and 128 and three bag constructions (random, cluster, α-first) show LLP-MM ranking first in average accuracy in all nine dataset–bag-construction settings of Tables 1 and 2, at low computational cost.

Main Findings

• State-of-the-art average accuracy in every setting: LLP-MM ranks first in average accuracy across all nine dataset–bag-construction combinations reported in Tables 1 and 2, over three runs (mean ± std).
• CIFAR-10, random bags (Table 1): LLP-MM averages 84.21% versus LLP-PVC 82.68%, DSQ 81.67%, PM 79.70%, ROT 75.20%, FlowLLP 73.56%, LLP-FC 62.56%, GeneralUPM-ABS 47.30%, EasyLLP-ABS 45.87%, GeneralUPM 34.85%, and EasyLLP 29.36%. At bag size 128 it reaches 66.74% versus 64.44% for LLP-PVC.
• CIFAR-10, cluster bags (Table 1): LLP-MM averages 87.67% versus PM 85.96%, FlowLLP 84.47%, DSQ 84.37%, ROT 83.17%, LLP-PVC 83.04%, and LLP-FC 50.66%. EasyLLP and GeneralUPM collapse to a single class (marked with a dagger for severe overfitting caused by negative loss values).
• CIFAR-100, random bags (Table 1): LLP-MM averages 55.20% versus LLP-FC 52.77%, PM 52.44%, DSQ 52.11%, FlowLLP 50.49%, and LLP-PVC 46.79%. At bag size 128 LLP-MM reaches 23.82% versus 25.70% for DSQ, so DSQ wins that single cell.
• miniImageNet, random bags (Table 1): LLP-MM averages 44.74% versus LLP-FC 43.58%, PM 42.30%, DSQ 40.84%, FlowLLP 37.75%, and LLP-PVC 35.44%.
• α-first bags (Table 2) are the hardest setting: On CIFAR-10, LLP-MM averages 82.32% versus LLP-PVC 82.31% — a near-tie — while PM drops to 72.03% and FlowLLP to 69.87%. On CIFAR-100 LLP-MM averages 51.14% versus LLP-FC 50.20%, and on miniImageNet 43.67% versus LLP-FC 40.39%.
• Robustness to bag construction: The authors report that moment matching stays effective across random, cluster, and α-first bag constructions, while several baselines degrade sharply (for example PM on CIFAR-100 α-first bags falls to 5.23% at bag size 128, and ROT on miniImageNet α-first bags to 2.33%).
• Negative-loss instability in some baselines: EasyLLP and GeneralUPM can exhibit negative empirical losses during optimization; the paper notes this causes severe overfitting with predictions collapsing to a single class, and the -ABS variants take absolute values of the original loss to mitigate it.
• Proportion matching is a first-order special case: The widely used PM strategy corresponds to s = 1 in the LLP-MM objective, so higher orders add information that PM cannot use.
• Why not maximum likelihood: Exact PMD likelihood is impractical — the state-of-the-art method in computational statistics (Lin et al., 2023) has time complexity O(m^{q−1} log m), which is already astronomically large at typical settings such as m = 64 and q = 10.
• Theory: More moment orders shrink the set of minimizers (Proposition 3.1), and the gap between the multi-order matching risk and its empirical version is bounded via Rademacher complexity of the per-class hypothesis sets (Theorem 3.2).
• Practical configuration: LLP-MM uses s = 8 for CIFAR-10 and s = 3 for CIFAR-100 and miniImageNet, cross-entropy for each order's discrepancy L^(r), and weights λ_r = 1/s.
• Stated limitation: The analysis does not by itself deliver a full classifier-level consistency guarantee of the form f → f*; the authors note this remains challenging for real-world structured bags such as blood-cell detection with donor-specific correlations.

Methodology in Plain English

The starting point is a change of assumption. Instead of imagining that data arrive as individual labeled examples that are then shuffled uniformly into bags, the authors imagine that bags themselves are the unit drawn from the world, and that how instances land in a bag may depend on the instances' own features (for example, images sharing the same shape feature go into the same bag). Within a bag, labels are still assumed independent given the instances.

Under that assumption, the vector of class counts in a bag is a sum of independent categorical draws with different parameters. That is exactly a Poisson multinomial distribution, and the observed proportions are just these counts divided by bag size. Ideally one would fit the classifier by maximum likelihood under this distribution, but computing that likelihood is exponentially expensive in the number of classes, so the authors instead summarize the distribution through its moments.

Concretely, for each bag they compute empirical factorial moments — averages over ordered tuples of distinct instances — directly from the observed label proportions, without ever seeing individual labels. They also compute the same quantities from the classifier's predicted probability vectors for the bag's instances. Training minimizes the discrepancy between the two sets of moments, summed over orders r = 1 to s with weights λ_r. Because the moments are probability-like tensors (nonnegative, summing to one), a standard discrepancy such as cross-entropy or mean squared error works as the per-order loss.

The naive way to build an order-r moment tensor would need q^r entries, so the authors use a state-compressed dynamic programming scheme that exploits symmetry — in the second-order case, for instance, the tensor is a symmetric matrix and only its distinct entries need computing. Experimentally, they build synthetic LLP datasets from CIFAR-10, CIFAR-100, and miniImageNet under three bag-construction strategies and four bag sizes, and compare against ten baselines. They also report an evaluation on patient-grouped blood cell data in Section 4.3, though the excerpt provided here is truncated before those results.

Why This Matters

Impact on research. The paper challenges a near-universal modeling assumption in recent LLP work — that bags are random — and offers a drop-in alternative view (PMD plus factorial moments) that subsumes the classic proportion-matching objective as its first-order case. It connects LLP to the moment-matching literature and to PMD theory from computational statistics, and it provides both a tighter-solution-set argument and a generalization bound, giving the field a cleaner theoretical handle on why higher-order label-proportion statistics carry usable signal.

Real-world applications (as cited in the paper):

• Election polling, where individual voting preferences are confidential but regional support rates act as label proportions, and voters in a region share correlated behavior.
• Privacy-sensitive and privacy-preserving measurement deployments, where aggregators see only aggregate statistics.
• Online advertising, where instances are grouped by pre-defined categorical attributes or platform-defined grouping keys rather than random assignment.
• Image analysis tasks where instance-level annotation is difficult or costly, including blood-cell detection with patient-grouped data.

Industry relevance. Bags in production systems are almost always formed by structural keys (user segment, device, region, campaign, platform grouping key), so methods tuned to random bags are optimistically evaluated. LLP-MM's selling point for practitioners is that it needs no instance labels, adds only low-order moment computations, and explicitly targets these structured groupings — relevant to ad measurement, analytics with privacy constraints, and any pipeline where outputs are reported as rates per group.

Future Directions

• Classifier-level consistency. The authors explicitly flag that their analysis justifies matching Bayes-optimal moment tensors but does not yield a full guarantee that the learned predictor converges to the Bayes-optimal classifier f*; establishing this is left open.
• Dependence structures beyond conditional independence. Real structured bags, such as blood-cell detection where unobserved donor-specific physiological factors correlate cells within a bag, violate the within-bag independence assumption; characterizing such dependence is posed as future work.
• Scaling the moment order. The state-compressed cost still grows combinatorially with the maximum order s, and the best setting already differs by dataset (s = 8 for CIFAR-10, s = 3 for CIFAR-100 and miniImageNet), so choosing s adaptively and controlling its cost are natural next questions.
• Extending beyond the current benchmarks. The authors note existing LLP benchmarks are mainly binary, and their own evaluation uses synthetic bags built from standard image datasets; validating on genuinely structured real-world bag data (their Section 4.3 blood-cell setting points this way) would test the assumptions more directly.

Target Audience

Researchers and graduate students working on weakly supervised learning who already know the standard LLP formulation and want to understand why random-bag assumptions break down and what to replace them with. It is also useful for practitioners building models on aggregated or privacy-restricted data — ad measurement, polling, medical imaging grouped by patient — who need a method that does not presume random bag construction, and for theoretically minded readers interested in moment-based estimation and generalization bounds for bag-level supervision. Readers without background in tensor moments or Rademacher complexity should expect a steep climb through Sections 3.3 and 3.4.

Authors’ abstract

Learning from label proportions (LLP) is a weakly supervised setting where training data are grouped into bags with only bag-level label proportions observed, and the goal is to learn a classifier that predicts labels for individual instances. Recently, a large body of methods has emerged; however, most of them rely on the assumption that instance-label pairs are sampled i.i.d. and randomly assembled into bags, an assumption often violated in real-world scenarios. Our experimental results indicate that these methods perform suboptimally under non-random settings. In this work, we adopt a more realistic assumption: bags are sampled i.i.d., and instance labels are conditionally independent given the instances. Under this setting, we show that the label counts follow a Poisson multinomial distribution. Motivated by this observation, we propose LLP via moment matching (LLP-MM), a simple yet effective approach which leverages multi-order factorial moments as training objectives, encouraging the classifier predictions to match these moments and thereby more fully exploit the underlying statistical structure of the data. Extensive experiments on benchmark datasets under various bag construction strategies demonstrate the effectiveness of our approach while maintaining high computational efficiency. Our code is available at https://github.com/TianhaoMa5/LLP-MM.