A Sieve-Accelerated Quadrature Method for Exact Privacy Accounting in the 2020 U.S. Decennial Census

기술 요약: 2020년 미국 인구조사(U.S. Decennial Census)의 정밀한 프라이버시 회계를 위한 체(Sieve) 가속 적분법

문제 정의
미국 인구조사국은 2020년 인구조사 표본에 정수 값의 이산 가우시안 노이즈를 주입함으로써 차분 프라이버시(Differential Privacy, DP)를 채택했다. 현재 인구조사국은 zero-concentrated differential privacy (zCDP)를 사용하여 공식적인 프라이버시 보증을 제공하고 있으나, 이러한 보증은 정확한 프라이버시 손실에 대한 상한선(upper bounds)에 불과하다. 이러한 격차는 프라이버시 예산을 충족하기 위해 불필요한 과잉 노이즈를 주입하게 만들며, 이는 연방 자금 배분이나 정치적 선거구 획정과 같은 중요한 후속 애플리케이션을 위한 데이터의 통계적 유용성을 저해한다.

핵심 과제는 2020년 인구조사 인구 및 주거 특성(DHC) 파일의 정확한 프라이버시 프로파일을 평가하는 것이다. 수학적으로 이는 $f$-차분 프라이버시($f$-DP) 프레임워크 하에서 이질적인 이산 가우시안 분포들의 고차원 합성(high-dimensional convolutions)의 꼬리 확률(tail probabilities)을 계산하는 것을 요구한다. 이 작업은 다음 세 가지 요인으로 인해 계산적으로 매우 까다롭다:

1. 이질성(Heterogeneity): 노이즈 분산이 쿼리와 지리적 수준에 따라 다르기 때문에, 폐쇄형 해(closed-form solutions)를 가능하게 하는 대수적 구조가 파괴된다.
2. 차원성(Dimensionality): 이 합성은 지리적 경로를 따라 최대 80단계의 합성(compositions)을 포함하며, 이는 고차원 적분을 생성한다.
3. 정밀도 요구사항(Precision Requirements): 인구조사국은 결과적인 $(\varepsilon, \delta)$-DP 곡선의 정확성을 보장하기 위해 매우 엄격한 수치적 오차 허용 범위(예: $10^{-35}$)를 요구한다. 기존 방법들은 단일 프라이버시 예산 할당을 평가하는 데 약 1,000 CPU 시간을 소요했으며, 이는 DHC 파일의 946개 고유한 할당 쌍 전체를 계산하는 것을 불가능하게 만든다.

방법론
저자들은 문제를 수치 적분 과제로 재구성하는 계산 효율적이고 수학적으로 엄밀한 적분법을 제안한다. 이 방법은 네 단계로 진행된다:

1. 이산 푸리에 변환(DFT)을 통한 문제 재구성:
   독립적인 이산 가우시안 랜덤 변수들의 가중치 합의 꼬리 확률을 계산하는 문제는 수치 적분 문제로 변환된다. 역 이산 푸리에 변환을 활용함으로써, 누적 확률은 $[-\pi, \pi]$ 구간에 대한 특성 함수(characteristic functions)의 곱의 적분으로 표현된다.

2. 지수적 수렴 적분(Exponentially Convergent Quadrature):
   저자들은 적분을 근사하기 위해 사다리꼴 법칙(trapezoidal rule)을 사용한다. 그들은 복소 해석적이고 주기적인 적분 함수(특히 이산 가우시안의 특성 함수)에 대해 사다리꼴 법칙이 지수적 수렴을 달성함을 입증한다. 이를 통해 표준 다항식 수렴 방법보다 훨씬 적은 적분 노드(quadrature nodes)만으로도 요구되는 정밀도를 충족할 수 있다.

3. 이질적 가중치를 위한 격자 매핑(Lattice Mapping):
   노이즈 파라미터의 이질성(가중치가 유리수인 경우)을 처리하기 위해, 저자들은 베주 항등식(Bézout's identity)을 사용하여 통합된 스케일링 인자를 도출한다. 이는 이질적인 가중치 합을 공통 정수 격자(integer lattice)로 매핑하여, 정보 손실이 있는 빈닝(binning) 방식에 의존하지 않고도 이산 확률 질량 함수를 보존한다. 이 단계는 무한 급수의 절단 경계(truncation bounds)를 결정하기 위해 정밀한 서브 가우시안 집중 부등식(sub-Gaussian concentration inequalities)을 도출할 수 있게 한다.

4. 체 가속 적분(Sieve-Accelerated Integration):
   지수적 수렴에도 불구하고, 엄격한 허용 오차($10^{-35}$)가 있는 고차원 설정에서는 여전히 수백만 개의 노드를 평가해야 한다. 이를 극복하기 위해 저자들은 수론에서 영감을 받은 "체 알고리즘(sieve algorithm)"을 도입한다. 이 알고리차는 특성 함수의 주기적인 피크 구조를 활용하여 적분 함수가 무시할 수 있는 수준임이 보장되는 적분 노드를 엄격하게 식별하고 제거한다. 이 노드들을 제거함으로써, 방법론은 필요한 함수 호출 횟수를 $10^6$ 이상에서 약 203개로 줄인다.

주요 기여

• 정확한 프라이버시 회계: 본 논문은 zCDP의 상한 근사를 넘어, 2020년 인구조사 DHC 파일에 대한 최초의 정확하고 가정 없는(assumption-free) 프라이버시 회계를 제시한다.
• 계산 가속화: 제안된 방법은 기존의 최첨단 방법 대비 3개 차수 이상의 속도 향상을 달enc한다. 단일 프라이버시 예산 할당 평가 시간이 약 1,000 CPU 시간에서 0.5 CPU 시간으로 단축되었다.
• 확장성: 이 방법은 이전에 계산적으로 불가능하다고 여겨졌던 작업인 DHC 파일의 946개 모든 할당 쌍에 대한 정확한 프라이버시 프로파일을 성공적으로 계산한다.
• 이론적 통찰: 저자들은 에지워스 전개(Edgeworth expansions)를 사용하여 이산 가우시안 메커니즘과 연속 가우시안 메커니즘 사이의 괴리에 대한 이론적 설명을 제공하며, 근사 오차가 $O(m^{-3/2})$ (여기서 $m$은 합성 횟수)임을 증명한다.

결과

• 프라이버시-유용성 트레이드오프: 정확한 회계를 사용함으로써, 저자들은 현재 인구조사국의 zCDP 기반 접근 방식과 동일한 프라이버시 보증을 유지하면서 노이즈 분산을 15.08%에서 24.82%까지 줄일 수 있음을 입증한다. 이는 공개되는 데이터의 통계적 유용성을 크게 향상시킨다.
• 성능: 이 방법은 2020년 인구조사 DHC 파일에 대한 정확한 $f$-DP 및 $(\varepsilon, \delta)$-DP 곡선을 계산한다. 결과는 인구조사국의 현재 상한 접근 방식이 보수적이어서, 정확한 방법보다 엄격하게 열등한 프라이버시-유용성 트레이드오프를 생성함을 보여준다.
• 실무적 지침: 저자들은 서로 다른 합성된 메커니즘들 간의 프라이버시 보증이 매우 유사하다는 점을 관찰했다. 저자들은 프라이버시 예산 튜닝 단계 동안 반복적인 전체 규모 계산을 피하기 위해 하나의 대표적인 합성 메커니즘(구체적으로 $[f_{M_0}, f_{M_0}]$)을 대리물(proxy)로 사용할 것을 제안하며, 튜닝 후 최종적인 정확한 평가를 수행한다.

의의
본 논문은 느슨한 프라이버시 경계로 인한 하위 최적의 프라이버시-유용성 트레이드오프 문제를 해결하고자 하는 인구조사국의 핵심적인 과제를 해결한다고 주장한다. 정확하고 가정 없는 회계를 가능하게 함으로써, 정책 입안자들이 프라이버시 비용을 튜닝 가능한 자원으로 취급하여 데이터 유용성과 프라이버시 보호 사이의 균형을 최적화할 수 있도록 한다. 이 프레임워크는 인구조사에 국한되지 않으며, 이질적인 이산 메커니즘이 포함된 대규모 합성 환경에서 정확한 프라이버시 회계를 위한 일반적이고 빠르며 수치적으로 신뢰할 수 있는 접근 방식을 제공한다. 저자들은 자신들의 방식이 선거구 획정 및 경제 연구에 사용되는 연방 데이터 제품의 품질을 저하시키는 "불필요한 과잉 노이즈"를 피할 수 있음을 강조한다.