# PAC Learning Linear Thresholds from Label Proportions

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

## Key facts

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

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

- [On Learning from Label Proportions](https://mlsanity.com/paper/1402.5902/) (2014)
- [Deep multi-class learning from label proportions](https://mlsanity.com/paper/1905.12909/) (2019)
- [Learning from Label Proportions with Generative Adversarial Networks](https://mlsanity.com/paper/1909.02180/) (2019)
- [A PTAS for Agnostically Learning Halfspaces](https://mlsanity.com/paper/1410.7050/) (2014)
- [Weakly Supervised Classification in High Energy Physics](https://mlsanity.com/paper/1702.00414/) (2017)
- [Easy Learning from Label Proportions](https://mlsanity.com/paper/2302.03115/) (2023)
- [Learning from Aggregated Data: Curated Bags versus Random Bags](https://mlsanity.com/paper/2305.09557/) (2023)

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

- [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)
- [Optimal Learning from Label Proportions with General Loss Functions](https://mlsanity.com/paper/2509.15145/) (2025)
- [Weak to Strong Learning from Aggregate Labels](https://mlsanity.com/paper/2411.06200/) (2024)
- [Aggregating Data for Optimal and Private Learning](https://mlsanity.com/paper/2411.19045/) (2024)
- [Learning from Concealed Labels](https://mlsanity.com/paper/2412.02230/) (2024)
- [Statistical Learning from Attribution Sets](https://mlsanity.com/paper/2602.06276/) (2026)
- [Learning Conditional Averages](https://mlsanity.com/paper/2602.11920/) (2026)
- [BiTro: Bidirectional Transfer Learning Enhances Bulk and Spatial Transcriptomics Prediction in Cancer Pathological Images](https://mlsanity.com/paper/2603.14897/) (2026)
- [Learning from Label Proportions with Dual-proportion Constraints](https://mlsanity.com/paper/2603.21153/) (2026)

## Abstract (arXiv)

Learning from label proportions (LLP) is a generalization of supervised learning in which the training data is available as sets or bags of feature-vectors (instances) along with the average instance-label of each bag. The goal is to train a good instance classifier. While most previous works on LLP have focused on training models on such training data, computational learnability of LLP was only recently explored by [Saket'21, Saket'22] who showed worst case intractability of properly learning linear threshold functions (LTFs) from label proportions. However, their work did not rule out efficient algorithms for this problem on natural distributions. In this work we show that it is indeed possible to efficiently learn LTFs using LTFs when given access to random bags of some label proportion in which feature-vectors are, conditioned on their labels, independently sampled from a Gaussian distribution N(μ, Sigma). Our work shows that a certain matrix -- formed using covariances of the differences of feature-vectors sampled from the bags with and without replacement -- necessarily has its principal component, after a transformation, in the direction of the normal vector of the LTF. Our algorithm estimates the means and covariance matrices using subgaussian concentration bounds which we show can be applied to efficiently sample bags for approximating the normal direction. Using this in conjunction with novel generalization error bounds in the bag setting, we show that a low error hypothesis LTF can be identified. For some special cases of the N(0, I) distribution we provide a simpler mean estimation based algorithm. We include an experimental evaluation of our learning algorithms along with a comparison with those of [Saket'21, Saket'22] and random LTFs, demonstrating the effectiveness of our techniques.