# Hardness of Learning Boolean Functions from Label Proportions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 28 Mar 2024.

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

- [On Learning from Label Proportions](https://mlsanity.com/paper/1402.5902/) (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)
- [Deep Learning from Label Proportions for Emphysema Quantification](https://mlsanity.com/paper/1807.08601/) (2018)
- [Learning from Aggregated Data: Curated Bags versus Random Bags](https://mlsanity.com/paper/2305.09557/) (2023)
- [Challenges and approaches to privacy preserving post-click conversion prediction](https://mlsanity.com/paper/2201.12666/) (2022)
- [Fast learning from label proportions with small bags](https://mlsanity.com/paper/2110.03426/) (2021)

## Abstract (arXiv)

In recent years the framework of learning from label proportions (LLP) has been gaining importance in machine learning. In this setting, the training examples are aggregated into subsets or bags and only the average label per bag is available for learning an example-level predictor. This generalizes traditional PAC learning which is the special case of unit-sized bags. The computational learning aspects of LLP were studied in recent works (Saket, NeurIPS'21; Saket, NeurIPS'22) which showed algorithms and hardness for learning halfspaces in the LLP setting. In this work we focus on the intractability of LLP learning Boolean functions. Our first result shows that given a collection of bags of size at most 2 which are consistent with an OR function, it is NP-hard to find a CNF of constantly many clauses which satisfies any constant-fraction of the bags. This is in contrast with the work of (Saket, NeurIPS'21) which gave a (2/5)-approximation for learning ORs using a halfspace. Thus, our result provides a separation between constant clause CNFs and halfspaces as hypotheses for LLP learning ORs. Next, we prove the hardness of satisfying more than 1/2 + o(1) fraction of such bags using a t-DNF (i.e. DNF where each term has ≤ t literals) for any constant t. In usual PAC learning such a hardness was known (Khot-Saket, FOCS'08) only for learning noisy ORs. We also study the learnability of parities and show that it is NP-hard to satisfy more than (q/2q-1 + o(1))-fraction of q-sized bags which are consistent with a parity using a parity, while a random parity based algorithm achieves a (1/2q-2)-approximation.