real (vector) valued queries 대한 차등 프라이버시를 제공하는 Laplace mechanism을 제시한다.
이는 exponential mechanism으로 이어지며, 개별적인 후보 출력 세트에서 차등적으로 사적인 선택을 위한 방법이다.
여러 차등 개인 메커니즘을 구성하여 발생하는 개인 정보 보호 손실을 분석한다.
차등 개인 정보 보호 메커니즘의 효과를 이해하고 증명하는 데 필수적인 기본 확률 도구를 제공한다.
3.1 Useful probabilistic tools
확률 이론에서, Chernoff 경계는 무작위 변수의 평균에서 확률의 상한을 구할 수 있게 하는 것을 목표로 한다.
Theorem 3.1 (Additive Chernoff Bound).
독립적인 확률 변수 X의 합에 대해, 각 변수가 0 이상 1 이하로 제한되고 기대 합이 μ인 경우, 합이 그 기대값에서 ∆ (ε) 만큼 벗어날 확률이 지수적으로 작다는 것을 설명한다.
각 변수는 \(0 \leq X_i \leq 1\)로 제한된다.
이 독립적인 확률 변수들의 평균 \(S=\frac{1}{m}\sum_{i=1}^m X_i\), 기대값 \(\mu = \mathbb{E}[S] = \sum_{i=1}^{m} \mathbb{E}[X_i]\)
\(\mathbb{E}[X_i]\): 단일 무작위 변수 \(X_i\)의 기대값
\(\mu\): S가 취할 수 있는 값들의 가중 평균
– S가 그 기대값에서 ∆ 이상 차이 나는 확률이 지수적으로 감소한다.
– S의 실제 값이 그 기대값(μ로부터 Δ만큼 위나 아래에서 얼마나 멀리 떨어질 수 있는지 측정)
상방(Overestimation): S가 기대값 μ로부터 Δ만큼 큰 경우의 확률은 \(e^{-2m\Delta^2}\) 이하
하방(Underestimation): S가 기대값 μ로부터 Δ만큼 작은 경우의 확률은 \(e^{-2m\Delta^2}\) 이하
Theorem 3.2 (Multiplicative Chernoff Bound).
상방(Overestimation): S가 기대값 μ로부터 Δ만큼 큰 경우의 확률은 \(e^{-2m\Delta^2}\) 이하
하방(Underestimation): S가 기대값 μ로부터 Δ만큼 작은 경우의 확률은 \(e^{-2m\Delta^2}\) 이하
Theorem 3.3 (Azuma’s Inequality).
확률 변수 함수에 대한 농도 부등식을 제공한다.
일련의 확률 변수가 주어졌을 때 각 \(X_i\)가 임의의 값 집합 \(A_i\)로부터 값을 취하고, 이러한 확률 변수들의 함수 f가 주어질 때 적용된다.
\(X_1, \cdots, X_{i-1} = a_i\)와 \(X_1, \cdots, X_i = a_i’\) 조건 하에 f의 기대값 차이가 \(c_i\) 이하이다.
\(f(X_1, \cdots, X_m)\)가 그 기대값 E[f]로부터 t 이상 차이날 확률을 제한하는데, 위의 Pr 수식 형태로 표현된다.
\(\sum_{i+1}^m c_i^2\)는 f에 대한 \(X_i\)의 최대 영향력 \(c_i\)의 제곱합이다.
Theorem 3.4 (Stirling’s Approximation).
팩토리얼 함수 n!을 근사하는 데 사용되는 공식 \(n! \approx \sqrt{2 \pi n}(\frac{n}{e})^n\)
유도 과정: 라플라스 방식
Reference
- Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 3. Basic Techniques and Composition Theorems