Simultaneous Private Learning of Multiple Concepts

By Mark Bun, Kobbi Nissim, Uri Stemmer. 2015

92 citations recorded by the source corpus.

We investigate the {\em 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,...,ck). The goal of a multi-learner is to output k hypotheses (h1,...,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.

Subfields: Artificial Intelligence, Meta & Continual Learning, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Meta & Continual Learning

In Privacy & Security

Citations in the corpus

Privacy Amplification by Iteration (2018, background): “We note that in the context of PAC learning sample complexity of solving multiple learning problems with differential privacy was studied in [39].”
Separating Local & Shuffled Differential Privacy via Histograms (2019, neutral): “That is, instead of executing P hist ε,δ in the reduction (Claim 3.4), execute the central model algorithm, from [7], with simultaneous error O ((1 / ( εn )) · log(1 /δ )).”
Clustering Algorithms for the Centralized and Local Models (2017, methodology): “ork we use stability based techniques for the following task: Given a dataset S 2 U n and a partition P of U , nd a set p 2 P containing (approximately) maximum number of elements of S . Theorem 2.6 ([3, 5, 25]) . Fix ;;;n , and let t 12 ln( n ). There exists an (; )-dierentially private algorith”
Private Mean Estimation of Heavy-Tailed Distributions (2020, background): “(2017), and the US Census Bureau for the 2020 Census Dajani et al. (2017). In this vein, a recent line of work Karwa and Vadhan (2018); Kamath et al.”
Finite Sample Differentially Private Confidence Intervals (2017, methodology): “(ǫ, δ) Case: For the case that K > 2/δ, we will use an (ǫ, δ)-differentially private algorithm, called stabilitybased histogram (Bun et al., 2016) to estimate p̂k, which removes the dependence on K by allowing for K to be infinity.”
Differentially Private Histograms in the Shuffle Model from Fake Users (2021, methodology): “As an example, there exists an (ε, δ)-centrally private algorithm that computes d-bin histograms from n users up to maximum (`∞) error O( 1 εn log 1 δ ) [6].”