PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking Learning from Label Proportions via Moment Matching

Tianhao Ma, Wei Wang, Yivan Zhang, Dong-Dong Wu, Takashi Ishida, Gang Niu, Masashi Sugiyama

arXiv:2610.21262v1cs.LG

TL;DR

LLP seeks instance-level classification from bag-level label proportions, but common methods assume random bags despite real groupings that depend on examples. LLP-MM connects proportions to a Poisson multinomial distribution and matches multi-order factorial moments; it ranks first in average accuracy across nine dataset–bag-construction settings while retaining practical computational efficiency.

  • Problem

    LLP seeks instance-level classification from bag-level label proportions, while many existing methods assume randomly assembled bags despite real grouping mechanisms that depend on examples.

    Source: §1 · pp. 1–2

  • Method

    LLP-MM uses the Poisson multinomial perspective to train classifiers by matching classifier-induced multi-order factorial moments to empirical moments from observed proportions.

    Source: §1 · p. 2, §3.1 · p. 4, §5 · p. 10

  • Results

    LLP-MM ranks first in average accuracy across all nine dataset–bag-construction settings and achieves robust performance across settings with practical computational efficiency.

    Source: §4.2 · p. 7, §5 · p. 10

  • Takeaways & Limitations

    Higher-order moments impose stronger constraints on the solution space, providing richer statistical information for classifier training.

    Source: §1 · p. 2, §5 · p. 10

    The treatment assumes conditional independence of instance labels given their instances and leaves within-bag dependence structure difficult to characterize.

    Source: §2.2 · p. 3, §3.4 · p. 7

Abstract

from arXiv · show

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.

1 Introduction

LLP seeks instance-level classifiers from bag-level label proportions, but random bag assembly often mismatches real grouping; LLP-MM uses the Poisson multinomial structure to match higher-order moments.

  • LLP trains instance-level classifiers from bag-level proportions, a setting relevant where instance annotations are costly or privacy-sensitive.Source: §1 · p. 1
  • Prior LLP methods often assume i.i.d. instance-label pairs assembled uniformly at random, unlike real groups shaped by geography, demographics, or predefined keys.Source: §1 · pp. 1–2
  • Under the structured-bag assumption, instance-dependent grouping coexists with labels conditionally independent given instances, making bag counts PMD-distributed.Source: §1 · p. 2
  • LLP-MM matches classifier-induced multi-order factorial moments to empirical moments; proportion matching is its first-order special case.Source: §1 · pp. 2–3
  • LLP-MM achieves state-of-the-art performance across benchmark datasets, remains robust across bag-generation strategies, and retains low computational cost.Source: §1 · p. 3

2 Preliminaries

The preliminaries contrast ordinary multiclass prediction with LLP's bag-level supervision, then define the bag/proportion setup and a common matching objective.

2.1 Ordinary Multi-class Classification

  • Ordinary multiclass classification seeks a score predictor f:X→∆q−1; calibrated surrogate losses stand in for intractable empirical 0–1 risk, and proper losses recover class posteriors.Source: §2.1 · p. 3

2.2 Learning from Label Proportions

  • LLP keeps the instance-level prediction goal but observes bags and class proportions rather than individual labels; labels are conditionally independent given each instance.Source: §2.2 · pp. 3–4
  • Proportion matching averages predictions within each bag and encourages its predicted class proportions to match the observed proportions.Source: §2.2 · p. 4

3 Methodology

LLP-MM treats bag label counts as Poisson multinomial under conditional label independence, then trains by matching classifier-induced factorial moments to moments derived from observed proportions. Using higher-order moments adds constraints beyond classical proportion matching, while the analysis and computation have stated assumptions and limits.

3 Methodology

  • The methodology connects LLP to Poisson multinomial structure, develops first- and higher-order moment matching, and analyzes the resulting approach.Source: §3 · p. 4

3.1 Rethinking Label Proportions: A PMD Perspective

  • Conditionally independent categorical labels make bag counts Poisson multinomial, motivating moment matching instead of computationally impractical exact likelihood.The cited likelihood method has complexity O(mq^(q−1) log m).Source: §3.1 · p. 4

3.2 Label Proportions Beyond First-Order Moments: A Second-Order Illustration

  • Second-order targets derived from proportions distinguish ordered same-class pairs, mαc(mαc−1), from different-class pairs, mαc mαd.Source: §3.2 · pp. 4–5

3.3 Generalized Multi-Order Moment Matching

  • For any order r, factorial-moment targets can be computed from label proportions and matched to classifier-induced tensors; proportion matching is the s = 1 special case.Source: §3.3 · pp. 5–6

3.4 Theoretical Analysis

  • Under stated assumptions, adding moment orders progressively tightens the minimizer set while retaining the Bayes-optimal classifier.The assumptions include a hypothesis class containing the Bayes-optimal classifier and positive weights for the included orders.Source: §3.4 · p. 6
  • The generalization analysis assumes exchangeable bag coordinates and bounded Lipschitz losses, and does not establish classifier-level consistency for structured bags.Such consistency remains challenging when within-bag dependence is difficult to characterize.Source: §3.4 · pp. 6–7
  • State-compressed dynamic programming avoids constructing all q^r tensor entries, but complexity still grows combinatorially with maximum order; a few low orders suffice in practice.Source: §3.4 · p. 7

4 Experiments

Experiments compare LLP-MM with representative baselines across standard synthetic benchmarks and a semi-real-world blood-cell benchmark. LLP-MM leads the synthetic comparisons, performs strongly on the blood-cell data, and shows a performance–runtime trade-off as moment order increases.

4.1.1 Datasets and Bag Construction

  • On CIFAR-10, CIFAR-100, and miniImageNet, experiments compare random, cluster, and α-first bags at sizes m ∈ {16, 32, 64, 128}.The reported baselines include proportion matching, DSQ, LLP-PVC, LLP-FC, ROT, EasyLLP, and GeneralUPM.Source: §4.1.1 · p. 7, §4.1.2 · p. 7

4.2 Comparison with Baselines

  • EasyLLP and GeneralUPM can encounter negative empirical losses during optimization, while LLP-PVC has lower average accuracy on CIFAR-100 and miniImageNet than on CIFAR-10.The passage notes that LLP-PVC’s gap may partly reflect its one-vs-rest decomposition and lack of direct joint multiclass PMD modeling.Source: §4.2 · p. 7
  • LLP-MM ranks first in average accuracy across all nine dataset–bag-construction settings.The comparison covers Random Bag and Cluster Bag results in Table 1 and α-First Bag results in Table 2.Source: §4.2 · p. 7, Table 1 · p. 8, Table 2 · p. 9

4.3 Semi-Real-World Evaluation

  • On KU-Optofil PBC, LLP-MM with s = 8 leads in Macro-F1, Balanced Accuracy, and Weighted-F1, exceeding LLP-PVC by 11.33 Macro-F1 points; ROT has the highest Accuracy.Increasing s from 3 to 5 to 8 raises Macro-F1 from 51.79% to 66.40% to 69.75%.Source: §4.3 · p. 9, Table 3 · p. 9

4.4 Effect of the Order Parameter

  • As s increases, prediction performance generally improves before stabilizing, while computation grows, making moderate orders a practical balance.CIFAR-100 results are reported only up to s = 3 because fourth-order terms are prohibitively expensive with 100 classes.Source: §4.4 · p. 9, Figure 2 · p. 10

5 Conclusion

The conclusion presents LLP-MM as a moment-matching framework that uses factorial moments derived from observed proportions, with higher-order moments imposing stronger solution constraints. The appendix notes that first-order moment matching is proportion matching and that the paper provides tables of notation and abbreviations.

5 Conclusion

  • LLP-MM uses multi-order factorial moments from observed label proportions as supervision, and the analysis finds that higher orders impose stronger constraints on the solution space.The conclusion reports robust performance across settings with practical computational efficiency, while identifying scarce standardized real-world LLP datasets as a limitation and future benchmark development as a need.Source: §5 · p. 10

A Notation and Terminology

B First-Order Moment Matching

C Derivation of the Second-Order Moment from Label Proportions

The derivation computes entries of the bag-level second-order moment matrix directly from the observed label proportions. It concludes that the matrix is completely determined by those proportions.

C Derivation of the Second-Order Moment from Label Proportions

D Proof of Proposition 3.1

The proof shows that minimizing the multi-order objective matches the Bayes-optimal classifier’s moment tensors at every positively weighted order, almost surely over bags. It connects this result to conditional expectations of label tensors given each bag.

D Proof of Proposition 3.1

  • Every minimizer exactly matches the Bayes-optimal classifier’s moment tensors at all positively weighted orders for almost every bag.The theorem notes that including higher-order moments enforces agreement at correspondingly higher orders.Source: D Proof of Proposition 3.1 · p. 16
  • Conditioned on a bag, the expected tensor of distinct instance labels equals the tensor product of their Bayes-optimal class predictions.The proof uses conditional independence of labels given the bag and the conditional marginal identities for each instance.Source: D Proof of Proposition 3.1 · p. 17
  • Under the stated loss assumption, the conditional expected label tensor uniquely minimizes the order-specific risk for that bag.The proof identifies this conditional expectation with the Bayes-optimal classifier-induced moment tensor.Source: D Proof of Proposition 3.1 · p. 17

E Generalization Analysis

The analysis derives generalization bounds for LLP-MM using complexity measures of loss-composed hypothesis classes. Under exchangeability of bag coordinates, the complexity term can be simplified.

E Generalization Analysis

  • Theorem E.2 gives a generalization bound when each order’s loss is Lipschitz in its target tensor, and Corollary E.7 expresses the bound in terms of the base classifier class.The analysis treats the n entire bag-proportion pairs as the independent sample units.Source: E Generalization Analysis · pp. 18, 19, 21, 22
  • The moment map is r/√m-Lipschitz in the bag predictions, enabling a complexity bound for the loss-composed class via vector contraction.The proof applies the assumed Lipschitzness of each order’s loss and Maurer’s vector contraction inequality.Source: E Generalization Analysis · pp. 21–22
  • With exchangeable bag coordinates, each class-coordinate function has the same expected Rademacher complexity, simplifying the generalization-bound complexity term.The coordinates may remain dependent even though their marginals agree.Source: E Generalization Analysis · pp. 22–23

F Computation Analysis

This section establishes a correspondence between compressed coefficients of a generating polynomial and entries of the classifier-induced factorial moment tensor. The compressed coefficients determine the full tensor because entries with the same class-count profile are equal.

F.1 Coefficient-to-Tensor Correspondence

  • Expanding the polynomial amounts to selecting distinct instances and assigning class labels; each monomial records the resulting class-count profile.The coefficient of a monomial sums over selections and assignments with that profile.Source: §F.1 · pp. 23–24
  • For a fixed instance subset and label assignment, the corresponding ordered tensor tuples count permutations within each class, with the multiplicity factor given by the product of class-count factorials.This counting correspondence yields the relationship between compressed coefficients and tensor entries.Source: §F.1 · p. 24
  • Compressed generating-polynomial coefficients determine the full order-r classifier-induced moment tensor because entries with the same multiplicity vector are equal.The proof relates each coefficient to the ordered tensor entries sharing its class-count profile.Source: §F.1 · pp. 23–24

F.2 Time and Space Complexity Analysis

The computation analysis addresses the prohibitive size of materializing order-r moment tensors by exploiting permutation symmetry. It computes moments through compressed states indexed by class-count profiles.

F.2 Time and Space Complexity Analysis

  • Directly evaluating the order-r loss requires an order-r tensor with qr entries, which can be prohibitive for large class counts or moment orders.The section exploits permutation symmetry to reduce both time and memory costs.Source: §F.2 · pp. 24–25
  • Permutation symmetry reduces order-r computation from qr full tensor entries to Nr compressed states.The compressed states group tensor entries that depend on the class-count profile rather than the ordering of class indices.Source: §F.2 · p. 25
  • A truncated generating-polynomial recurrence computes the classifier-induced compressed states by processing instances and extending each state with class-count increments.The coefficient table stores aggregated terms for each degree and class-count pattern.Source: §F.2 · pp. 25–26

G.1 Datasets and Bag Construction

The experiments use Random, Cluster, and α-First bag construction strategies, with bag sizes from 16 to 128.

G.1 Datasets and Bag Construction

  • Bags use Random, Cluster, or α-First construction, with sizes m ∈{16, 32, 64, 128}.Cluster bags use feature-cluster sampling with Dirichlet mixing weights; α-First bags draw class proportions from a symmetric Dirichlet distribution with concentration 10 per class.Source: §G.1 · p. 26

G.2 Baselines and Implementation Details

The appendix compares LLP-MM with representative LLP baselines and describes the experimental configurations. It also evaluates replacing GAN-based proportion matching with moment matching.

G.2 Baselines and Implementation Details

  • The comparison includes proportion matching, debiased squared loss, one-vs-rest classification, label-noise methods, optimal transport, unbiased estimators, and particle flow.Experiments use ResNet-18 for CIFAR-10/CIFAR-100 and ResNet-34 for miniImageNet; LLP-MM uses s = 8 for CIFAR-10 and s = 3 for the other datasets.Source: §G.2 · pp. 26–27

G.3 Compatibility with GAN-Based Representation Learning

  • MM+GAN underperforms standalone LLP-MM in most settings, while LLP-GAN does not consistently outperform PM.Both GAN-based variants generally have larger standard deviations than their standalone counterparts, especially with large α-First bags.Source: §G.3 · p. 27
  • Replacing LLP-GAN’s proportion loss with order-eight moment matching improves mean accuracy in all 12 CIFAR-10 settings, with gains up to 13.37 percentage points.The table reports best test accuracy on CIFAR-10 with GAN-based representation learning, as mean ± standard deviation over three runs.Source: Table 6 · p. 27, §G.3 · p. 27

G.4 Semi-Real-World Implementation Details

The semi-real-world appendix describes bag construction, training, and evaluation, while the checklist records reproducibility and documentation disclosures alongside remaining resource and licensing gaps.

G.4 Semi-Real-World Implementation Details

  • Known-patient cells form bags, while 3,204 cells with unknown patient IDs are shuffled into 26 bags; the resulting 245 training bags have sizes 1–207.All 56 test bags remain unchanged, and only bag proportions are used for training.Source: §G.4 · p. 27
  • The semi-real-world experiments train ImageNet-pretrained ResNet-18 for 100 epochs and select each run’s checkpoint by highest test Macro-F1.Metrics include Accuracy, Balanced Accuracy, Macro-F1, and Weighted-F1; results are mean ± sample standard deviation over three runs.Source: §G.4 · pp. 27–28

NeurIPS Paper Checklist

  • The checklist says the paper documents datasets, baselines, evaluation protocols, training setup, and hyperparameters needed to reproduce the main experiments.It also reports publicly available datasets and repository code, setup, data-preparation instructions, and reproduction scripts.Source: NeurIPS Paper Checklist · pp. 30–31
  • The checklist notes that hardware and per-epoch runtime are reported, but complete per-experiment and total compute usage are not.This leaves the full resource requirements for reproducing the experiments unspecified.Source: NeurIPS Paper Checklist · p. 32
  • The checklist states that societal impacts are not discussed and that licenses for cited assets are not fully documented.The repository is reported to include an MIT license, but the checklist separately says licenses for existing assets are incomplete.Source: NeurIPS Paper Checklist · pp. 32–34
Loading 2610.21262v1…