Learning from Label Proportions with Dual-proportion Constraints
Learning from Label Proportions (LLP) trains instance-level classifiers using only bag-level class proportions, addressing privacy constraints and annotation costs. This paper introduces LLP-DC, which enforces dual constraints: bag-level mean predictions align with given proportions, while instance-level training uses hard pseudo-labels generated via minimum-cost maximum-flow to strictly satisfy proportion constraints. The method offers a novel formulation of LLP as a candidate label assignment problem, achieving state-of-the-art results across standard vision benchmarks.
The paper presents a well-engineered approach to LLP that combines bag-level proportion matching with instance-level pseudo-labeling via combinatorial optimization. The minimum-cost maximum-flow formulation ($O(m^2l^2)$) replaces costly enumeration ($O(m!)$) for generating hard pseudo-labels that strictly satisfy bag proportions. While the empirical results show consistent improvements over baselines across CIFAR-10/100, SVHN, Fashion-MNIST, and MiniImageNet with bag sizes ranging from 16 to 128, the theoretical analysis of why strict proportion constraints improve generalization remains underdeveloped. The method is practical and demonstrates robustness to hyperparameters, though some baseline results (particularly SoftMatch on SVHN and CIFAR-100) appear anomalously poor, raising questions about implementation fairness.
The core technical contribution—reframing pseudo-label generation as a minimum-cost maximum-flow problem—is both novel and efficient. As stated in Section 3.1.2, "To solve this problem, we replace the enumeration problem spending at worst $O(m!)$ time cost with an efficient minimum-cost maximum-flow problem spending $O(m^2l^2)$ time cost." The dual-loss formulation combining bag-level proportion alignment ($\mathcal{L}_{\mathrm{bag}}$) with instance-level supervision ($\mathcal{L}_{\mathrm{ins}}$) is well-motivated, and the sensitivity analysis (Figure 5) demonstrates that performance remains stable across a broad range of threshold ($\tau$) and loss weight ($\lambda$) values. The runtime analysis (Table 2) supports the claim that the method achieves favorable accuracy-efficiency trade-offs compared to optimal transport alternatives like ROT.
Several limitations warrant attention. First, the paper lacks theoretical guarantees regarding how strictly satisfying proportion constraints at the instance level affects generalization bounds or consistency, relying instead on empirical validation. Second, some baseline comparisons appear questionable: SoftMatch achieves only 2.40% on CIFAR-100 (bag size 32) and 22.39% on SVHN (bag size 16), results the authors do not explain despite these being far below expected performance for semi-supervised methods. This raises concerns about whether baselines were tuned fairly or if implementation details disadvantaged certain methods.
Additionally, the experiments are limited to image classification; the claim that the method "readily extends to settings with variable bag sizes" (Section 3) is stated but not empirically validated. The paper also lacks analysis of failure modes, such as when bag proportions are noisy or when class distributions are highly imbalanced.
The evidence broadly supports the primary claim that LLP-DC improves over previous LLP methods, with consistent gains across datasets and bag sizes (e.g., CIFAR-100 bag size 16: 80.32% vs 78.65% for L2p-ahil). However, the comparison is potentially skewed by the anomalously poor performance of SoftMatch and ROT on certain datasets. While the authors note that "All baseline results are taken directly from [35]" (Section 4.1), they do not investigate why SoftMatch fails catastrophically on SVHN and CIFAR-100 while succeeding on Fashion-MNIST. The paper would benefit from discussing these discrepancies or verifying baseline implementations. The runtime comparison (Table 2) is fair, showing LLP-DC occupies a middle ground between fast baselines (DLLP) and slower alternatives (LLP-VAT, ROT with 75 iterations).
Reproducibility is moderately strong. The authors provide a GitHub repository link and specify hyperparameters: $\lambda=0.5$, $\tau=0.6$, learning rate $\eta_0=0.03$ (0.05 for MiniImageNet), and architectures (WRN-28-2/8, ResNet-18). Standard datasets (CIFAR-10/100, SVHN, etc.) and augmentation protocols (RandAugment, weak/strong views) are used. However, critical details are missing: random seeds, exact data shuffle and bag construction code, and the specific min-cost max-flow solver implementation (only referencing "any off-the-shelf minimum-cost maximum-flow algorithm" with Google OR-Tools footnote). The bag generation process—"randomly shuffling the instances and then uniformly partitioning them into non-overlapping bags" (Section 4.1)—is described but not standardized, which could affect variance across runs.
Learning from Label Proportions (LLP) is a weakly supervised problem in which the training data comprise bags, that is, groups of instances, each annotated only with bag-level class label proportions, and the objective is to learn a classifier that predicts instance-level labels. This setting is widely applicable when privacy constraints limit access to instance-level annotations or when fine-grained labeling is costly or impractical. In this work, we introduce a method that leverages Dual proportion Constraints (LLP-DC) during training, enforcing them at both the bag and instance levels. Specifically, the bag-level training aligns the mean prediction with the given proportion, and the instance-level training aligns hard pseudo-labels that satisfy the proportion constraint, where a minimum-cost maximum-flow algorithm is used to generate hard pseudo-labels. Extensive experimental results across various benchmark datasets empirically validate that LLP-DC consistently improves over previous LLP methods across datasets and bag sizes. The code is publicly available at https://github.com/TianhaoMa5/CV PR2026_Findings_LLP_DC.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.