# Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation

arXiv: https://arxiv.org/abs/2310.08056 · HTML: https://mlsanity.com/paper/2310.08056/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 50 references that are in the map.
- First posted on arXiv 12 Oct 2023.

## Builds on (most cited first, 20 of 20)

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [Self-Training with Weak Supervision](https://mlsanity.com/paper/2104.05514/) (2021)
- [On Learning from Label Proportions](https://mlsanity.com/paper/1402.5902/) (2014)
- [Learning from Label Proportions with Consistency Regularization](https://mlsanity.com/paper/1910.13188/) (2019)
- [Learning from Label Proportions by Learning with Label Noise](https://mlsanity.com/paper/2203.02496/) (2022)
- [Co-training for Demographic Classification Using Deep Learning from Label Proportions](https://mlsanity.com/paper/1709.04108/) (2017)
- [Easy Learning from Label Proportions](https://mlsanity.com/paper/2302.03115/) (2023)
- [Two-stage Training for Learning from Label Proportions](https://mlsanity.com/paper/2105.10635/) (2021)
- [Shoring Up the Foundations: Fusing Model Embeddings and Weak Supervision](https://mlsanity.com/paper/2203.13270/) (2022)
- [Open Source Vizier: Distributed Infrastructure and API for Reliable and Flexible Blackbox Optimization](https://mlsanity.com/paper/2207.13676/) (2022)
- [Learning from Aggregated Data: Curated Bags versus Random Bags](https://mlsanity.com/paper/2305.09557/) (2023)
- [Label Propagation with Weak Supervision](https://mlsanity.com/paper/2210.03594/) (2022)
- [proptoSVM for learning with label proportions](https://mlsanity.com/paper/1306.0886/) (2013)
- [Decoding from Pooled Data: Phase Transitions of Message Passing](https://mlsanity.com/paper/1702.02279/) (2017)
- [Phase Transitions in the Pooled Data Problem](https://mlsanity.com/paper/1710.06766/) (2017)
- [PGMax: Factor Graphs for Discrete Probabilistic Graphical Models and Loopy Belief Propagation in JAX](https://mlsanity.com/paper/2202.04110/) (2022)
- [Label Propagation for Learning with Label Proportions](https://mlsanity.com/paper/1810.10328/) (2018)
- [Message passing methods on complex networks](https://mlsanity.com/paper/2211.05054/) (2022)

## Built on by (most cited first, 7 of 7)

- [Nearly Optimal Sample Complexity for Learning with Label Proportions](https://mlsanity.com/paper/2505.05355/) (2025)
- [Forming Auxiliary High-confident Instance-level Loss to Promote Learning from Label Proportions](https://mlsanity.com/paper/2411.10364/) (2024)
- [Label Differential Privacy via Aggregation](https://mlsanity.com/paper/2310.10092/) (2023)
- [Mapping Uncharted Symmetries: Machine Discovery in Combinatorics](https://mlsanity.com/paper/2605.19063/) (2026)
- [Exploiting Vision Language Model for Training-Free 3D Point Cloud OOD Detection via Graph Score Propagation](https://mlsanity.com/paper/2506.22375/) (2025)
- [Learning from Label Proportions with Dual-proportion Constraints](https://mlsanity.com/paper/2603.21153/) (2026)
- [Multi-Label Proportion Learning for Sea-Ice Type Prediction](https://mlsanity.com/paper/2609.16347/) (2026)

## Abstract (arXiv)

Learning from Label Proportions (LLP) is a learning problem where only aggregate level labels are available for groups of instances, called bags, during training, and the aim is to get the best performance at the instance-level on the test data. This setting arises in domains like advertising and medicine due to privacy considerations. We propose a novel algorithmic framework for this problem that iteratively performs two main steps. For the first step (Pseudo Labeling) in every iteration, we define a Gibbs distribution over binary instance labels that incorporates a) covariate information through the constraint that instances with similar covariates should have similar labels and b) the bag level aggregated label. We then use Belief Propagation (BP) to marginalize the Gibbs distribution to obtain pseudo labels. In the second step (Embedding Refinement), we use the pseudo labels to provide supervision for a learner that yields a better embedding. Further, we iterate on the two steps again by using the second step's embeddings as new covariates for the next iteration. In the final iteration, a classifier is trained using the pseudo labels. Our algorithm displays strong gains against several SOTA baselines (up to 15%) for the LLP Binary Classification problem on various dataset types - tabular and Image. We achieve these improvements with minimal computational overhead above standard supervised learning due to Belief Propagation, for large bag sizes, even for a million samples.