# Simultaneous Private Learning of Multiple Concepts

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2015.

## Built on by (most cited first, 30 of 34)

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [Private Estimation with Public Data](https://mlsanity.com/paper/2208.07984/) (2022)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [Can Copyright be Reduced to Privacy?](https://mlsanity.com/paper/2305.14822/) (2023)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries](https://mlsanity.com/paper/2403.00028/) (2024)
- [Private learning implies quantum stability](https://mlsanity.com/paper/2102.07171/) (2021)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)
- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [Mean Estimation with User-level Privacy under Data Heterogeneity](https://mlsanity.com/paper/2307.15835/) (2023)
- [Instance-Optimal Differentially Private Estimation](https://mlsanity.com/paper/2210.15819/) (2022)
- [Dimension-free Private Mean Estimation for Anisotropic Distributions](https://mlsanity.com/paper/2411.00775/) (2024)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Algorithms with More Granular Differential Privacy Guarantees](https://mlsanity.com/paper/2209.04053/) (2022)
- [Confidential Federated Computations](https://mlsanity.com/paper/2404.10764/) (2024)
- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [On the Sample Complexity of Privately Learning Axis-Aligned Rectangles](https://mlsanity.com/paper/2107.11526/) (2021)
- [Differentially Private Nonparametric Regression Under a Growth Condition](https://mlsanity.com/paper/2111.12786/) (2021)
- [Hot PATE: Private Aggregation of Distributions for Diverse Task](https://mlsanity.com/paper/2312.02132/) (2023)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [The Correlated Gaussian Sparse Histogram Mechanism](https://mlsanity.com/paper/2412.10357/) (2024)
- [Differentially Private Multi-Sampling from Distributions](https://mlsanity.com/paper/2412.10512/) (2024)
- [Private Statistical Estimation via Truncation](https://mlsanity.com/paper/2505.12541/) (2025)

## Abstract (arXiv)

We investigate the direct-sum problem in the context of differentially private PAC learning: What is the sample complexity of solving k learning tasks simultaneously under differential privacy, and how does this cost compare to that of solving k learning tasks without privacy? In our setting, an individual example consists of a domain element x labeled by k unknown concepts (c1,ldots,ck). The goal of a multi-learner is to output k hypotheses (h1,ldots,hk) that generalize the input examples. Without concern for privacy, the sample complexity needed to simultaneously learn k concepts is essentially the same as needed for learning a single concept. Under differential privacy, the basic strategy of learning each hypothesis independently yields sample complexity that grows polynomially with k. For some concept classes, we give multi-learners that require fewer samples than the basic strategy. Unfortunately, however, we also give lower bounds showing that even for very simple concept classes, the sample cost of private multi-learning must grow polynomially in k.