# Aggregating Data for Optimal and Private Learning

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

## Key facts

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

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

- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [Composition of Differential Privacy & Privacy Amplification by Subsampling](https://mlsanity.com/paper/2210.00597/) (2022)
- [On Learning from Label Proportions](https://mlsanity.com/paper/1402.5902/) (2014)
- [Co-training for Demographic Classification Using Deep Learning from Label Proportions](https://mlsanity.com/paper/1709.04108/) (2017)
- [Differentially Private k-Means Clustering](https://mlsanity.com/paper/1504.05998/) (2015)
- [Learning from Label Proportions with Generative Adversarial Networks](https://mlsanity.com/paper/1909.02180/) (2019)
- [Label differential privacy via clustering](https://mlsanity.com/paper/2110.02159/) (2021)
- [Easy Learning from Label Proportions](https://mlsanity.com/paper/2302.03115/) (2023)
- [Regression with Label Differential Privacy](https://mlsanity.com/paper/2212.06074/) (2022)
- [Local Differential Privacy: a tutorial](https://mlsanity.com/paper/1907.11908/) (2019)
- [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)
- [PAC Learning Linear Thresholds from Label Proportions](https://mlsanity.com/paper/2310.10098/) (2023)
- [PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responses](https://mlsanity.com/paper/2402.04987/) (2024)

## Abstract (arXiv)

Multiple Instance Regression (MIR) and Learning from Label Proportions (LLP) are learning frameworks arising in many applications, where the training data is partitioned into disjoint sets or bags, and only an aggregate label i.e., bag-label for each bag is available to the learner. In the case of MIR, the bag-label is the label of an undisclosed instance from the bag, while in LLP, the bag-label is the mean of the bag's labels. In this paper, we study for various loss functions in MIR and LLP, what is the optimal way to partition the dataset into bags such that the utility for downstream tasks like linear regression is maximized. We theoretically provide utility guarantees, and show that in each case, the optimal bagging strategy (approximately) reduces to finding an optimal clustering of the feature vectors or the labels with respect to natural objectives such as k-means. We also show that our bagging mechanisms can be made label-differentially private, incurring an additional utility error. We then generalize our results to the setting of Generalized Linear Models (GLMs). Finally, we experimentally validate our theoretical results.