RECORD
Priv'IT: Private and Sample Efficient Identity Testing
Data Structures and Algorithms · Submitted 29 Mar 2017
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We show that differential privacy may come for free in some regimes of parameters, and we always beat the sample complexity resulting from running the $\chi^2$-test with noisy counts, or standard approaches such as repetition for endowing non-private $\chi^2$-style statistics with differential privacy guarantees.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We develop differentially private hypothesis testing methods for the small sample regime. Given a sample $\cal D$ from a categorical distribution $p$ over some domain $\Sigma$, an explicitly described distribution $q$ over $\Sigma$, some privacy parameter $\varepsilon$, accuracy parameter $\alpha$, and requirements $\beta_{\rm I}$ and $\beta_{\rm II}$ for the type I and type II errors of our test, the goal is to distinguish between $p=q$ and $d_{\rm{TV}}(p,q) \geq \alpha$. We provide theoretical bounds for the sample size $|{\cal D}|$ so that our method both satisfies $(\varepsilon,0)$-differential privacy, and guarantees $\beta_{\rm I}$ and $\beta_{\rm II}$ type I and type II errors. We show that differential privacy may come for free in some regimes of parameters, and we always beat the sample complexity resulting from running the $\chi^2$-test with noisy counts, or standard approaches such as repetition for endowing non-private $\chi^2$-style statistics with differential privacy guarantees. We experimentally compare the sample complexity of our method to that of recently proposed methods for private hypothesis testing.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We develop differentially private hypothesis testing methods for the small sample regime. | contribution 1.00 | 0.95 | 0.08 | asserted 1.00 |
| s1 | Given a sample $\cal D$ from a categorical distribution $p$ over some domain $\Sigma$, an explicitly described distribution $q$ over $\Sigma$, some privacy parameter $\varepsilon$, accuracy parameter $\alpha$, and requirements $\beta_{\rm I}$ and $\beta_{\rm II}$ for the type I and type II errors of our test, the goal is to distinguish between $p=q$ and $d_{\rm{TV}}(p,q) \geq \alpha$. | background 0.95 | 0.14 | 0.04 | asserted 0.77 |
| s2 | We provide theoretical bounds for the sample size $|{\cal D}|$ so that our method both satisfies $(\varepsilon,0)$-differential privacy, and guarantees $\beta_{\rm I}$ and $\beta_{\rm II}$ type I and type II errors. | contribution 0.70 | 0.96 | 0.16 | asserted 1.00 |
| s3 | We show that differential privacy may come for free in some regimes of parameters, and we always beat the sample complexity resulting from running the $\chi^2$-test with noisy counts, or standard approaches such as repetition for endowing non-private $\chi^2$-style statistics with differential privacy guarantees. | result 0.96 | 0.94 | 0.57 | asserted 0.87 |
| s4 | We experimentally compare the sample complexity of our method to that of recently proposed methods for private hypothesis testing. | contribution 0.59 | 0.94 | 0.05 | asserted 0.85 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We develop differentially private hypothesis testing methods for the small sample regime. Given a sample $\cal D$ from a categorical distribution $p$ over some domain $\Sigma$, an explicitly described distribution $q$ over $\Sigma$, some privacy parameter $\varepsilon$, accuracy parameter $\alpha$, and requirements $\beta_{\rm I}$ and $\beta_{\rm II}$ for the type I and type II errors of our test, the goal is to distinguish between $p=q$ and $d_{\rm{TV}}(p,q) \geq \alpha$. We provide theoretical bounds for the sample size $|{\cal D}|$ so that our method both satisfies $(\varepsilon,0)$-differential privacy, and guarantees $\beta_{\rm I}$ and $\beta_{\rm II}$ type I and type II errors. We show that differential privacy may come for free in some regimes of parameters, and we always beat the sample complexity resulting from running the $\chi^2$-test with noisy counts, or standard approaches such as repetition for endowing non-private $\chi^2$-style statistics with differential privacy guarantees. We experimentally compare the sample complexity of our method to that of recently proposed methods for private hypothesis testing.
Human review
How the literature uses it
4 arXiv papers cite this in 6 sentences
Papers citing it · 2 sentences without a confident label
Uses its method or tool 1 paper
-
That is, for algorithms whose output distribution is close in statistical distance to that of a pure differentially private algorithm, we construct an algorithm satisfying pure differentially privacy by mixing it with random output inspired by similar techniques in [ref] .
Differential Privacy on Finite Computers · A General Framework for Implementing Differential Privacy · 0.98
Cites it as background 2 papers
-
Goodness-of-fit testing has been studied extensively under a global differential privacy constraint in [ref] , [ref] , [ref] , [ref] and [ref] .
Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint · Introduction · 1.00
-
Further research directions of interest include obtaining instance-optimal algorithms, which depend on further properties of the distributions $a,b$ [ref] , quantum algorithms [ref] , as well as algorithms whose output is differentially-private [ref] .
Two Party Distribution Testing: Communication and Security · Introduction · 0.97
What it cites
Cites as background 2 papers
-
A number of recent works [ref] (and a simultaneous work, focused on independence testing [ref] ) investigate differential privacy with the former set of goals.
Revisiting Differentially Private Hypothesis Tests for Categorical Data · Introduction · 0.84
-
In the past twenty years, this problem has enjoyed significant interest in the theoretical computer science community (see, i.e., [ref] , and [ref] for a survey), where the focus has instead been on the finite sample regime, rather than asymptotics.
Testing Ising Models · Introduction · 0.98
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.