Differentially Private Chi-squared
Test by Unit Circle Mechanism
Kazuya Kakizaki*1 Kazuto Fukuchi *1 Jun Sakuma *1,2,3*1U. Tsukuba, *2JST CREST, *3RIKEN AIP(to appear in ICML 2017)https://bigdata.nii.ac.jp/eratokansyasai4/1

Estimating samples from statistics• Release of statistics is believed not to reveal information
on each sample• Samples might be inferred if the statistic dimension is highHard to infer

Easy to infer2
http://www.irasutoya.com/

GWAS case
• Finding disease related SNPs with chi-squared test
• #samples: 〜104
• #dimension: 〜106

• Privacy invasion caused by release of test statistics• Patient’s disease status could be inferred from aggregate
statistics collected for GWAS [Homer+ 2008]• NIH decided to stop releasing GWAS-related statistics
publicly• How can we release statistics securely?

3Releasing statistics securely• Plausible deniability and randomized response• Question “Have you ever tried marijuana in the past?”• Flip a coin. If tail, answer honestly. Else, flip again and answer
honestly if tail. Else, answer randomly.

p

Smokedmarijuana
last year…

1-p

Never tried…

http://www.irasutoya.com/

Yes

1/4+p/2

No4
Randomization preserves deniabilityDifferential Privacy (DP) [Dwork+ 2006]

http://www.irasutoya.com/

test for independence
SmokerNon-smoker

Lung cancerab

No lung cancer

cd• Chi-squared statistic• Is smoking related to lung cancer?
• If, associated6Related works• To achieve DP, the test statistic needs to berandomized in some sense
1. Output perturbation [Fienberg+ 2011, Yu+ 2014, Wang+ 2015]– Randomize test statistics– Type-I error is controllable– High type-I error w.r.t. sample size N– Type-II error/FWER is not controllable
2. Input perturbation [Johnson+ 2013]– Randomize counts– Type-I error is controllable– Type-II error/FWER is not controllable

7

Contributions
1. Investigate the type-II error of DP mechanisms
analytically
2. A novel DP mechanism with
type-II error
3. A novel DP mechanism that can control the family-wiseerror rate (FWER)

8

Contributions
1. Investigate the type-II error of DP mechanisms
analytically
2. A novel DP mechanism withtype-II error
3. A novel DP mechanism that can control the family-wiseerror rate (FWER)

9

Type-II error of DP chi-squared test
Theorem (Upper bound of type-II error of DP chi-squared test)
For any, the upper bound of the type-II error of DP chi-squared test mechanism is①:type-II error when one use threshold②:set of distributions of sample sets
: Threshold for mechanism
becomesthat is determined so that the type-I error of• ① measures how often the mechanism wrongly accepts( error)• ② is the type-II error of non-private test with threshold

A mechanismwith lower ① and ② achieves greater power

10Power analysis• Output perturbation• Theerror is upper-bounded by• Not decreases w.r.t. N• Input perturbation• Theerror cannot be appropriately derived• Can we design a randomization mechanism inwhich the gamma error is decreasing w.r.t. N?

11

Contributions
1. Investigate the type-II error of DP mechanisms
analytically
2. A novel DP mechanism withtype-II error
3. A novel DP mechanism that can control the family-wiseerror rate (FWER)

12

Test statistic

The test statistic is a function of c11 and c10
13

Geometrical interpretation ofstatisitcs• Chi-square test statistic(forms an ellipsoid)
Affine trans.
rejectedacceptedaccepted

rejected

14

Unit circle mechanism
Test result

is accepted if
is accepted otherwise

Randomize the distancefrom the origin and judge
the result

15

Analysis of upper bound of type-II error①① Gamma error②② Dependency on
Sensitivity

Input perturbation(IP)
Output perturbation(OP)
Unit circle mechanism(UCM)• The type-II error of UCM is expected to decrease faster rate
than OP16• The type-II error of IP cannot be analyzed

Why UCM has less gamma error?
• The cell of tablechanges– Then, the coordinate of cell move on

when-plane• If we fix, the interval between ellipse ofand coordinate becomes wider, as increases– The randomized test statistics by UCM becomes lesssensitive to noise as N increases
Same lengthInterval becomes widerInterval becomes wider

14

Contributions
1. Investigate the type-II error of DP mechanisms
analytically
2. A novel DP mechanism withtype-II error
3. A novel DP mechanism that can control the family-wiseerror rate (FWER)
skipped18

Experiment for single test
• We evaluate the significance and the power• Input perturbation• Output perturbation• Unit circle mechanism• Type-I error is controlled by using MC sampling
respectively• Data• We sample 1000 contingency table from multinomial
distribution• Parameter• Significance level• Privacy parameter19

Significance result

Number of samples

N

Number of samples

Number of samples• Data: sample from• Measure: significance = (1 - type-I error)
N

N
SignificanceInput perturbation

NSignificance

Output perturbation

NSignificanceN

Unit circle mechanism
All mechanisms can properly control thesignificance at 0.95 for any sample size

20

Power result

Power• Data: sample from• Evaluation: Power (1 – type-II error)

N

Number Nof Samples① UCM has a faster rate than OP- Because gamma error of UCM decreases as the sample size increases② UCM has similar power to that of the IP- However type-II error of UCM is analyzed unlike IP21

Conclusions and future work
We provide procedures for differential private chi-squared
test and multiple version• Contributions

1. Investigate the upper bound of type-II error of OP and UCM
2. A novel differentially private mechanism (unit circle mechanism)– Improve the dominated term of the type-II error fromto

3. Framework of differential private multiple chi-squared test
– Control the family-wise error rate (FWER) properly• Future work• Investigate the upper bound of type-II error of IP22