꼬리 위험 학습의 프라이버시 비용: 차분 프라이버시 CVaR 최적화에서의 유효 꼬리 샘플 크기

차분 프라이버시 (Differential Privacy, DP)는 CVaR (Conditional Value-at-Risk) 학습을 지배하는 유효 샘플 크기를 변화시킵니다. 꼬리 질량 (tail mass) $\tau$에 대하여, 프라이버시와 관련된 샘플 크기는 $n$이 아니라 $n\tau$이며, 이는 곧 유효한 프라이버시 보호 꼬리 샘플 크기가 $\epsilon n\tau$임을 의미합니다. 프라이버시가 적용된 CVaR 초과 위험 (excess risk)은 일반적인 꼬리 위험 통계적 오차와 프라이버시 비용으로 분해됩니다. 이러한 분해는 스칼라 추정 (scalar estimation) 및 유한 클래스 (finite classes)에 대해 완결됩니다. 스칼라 추정의 수렴 속도는 $\Theta(B \min{1,(n\tau)^{-1/2}+(\epsilon n\tau)^{-1}})$이며, 크기가 $M$인 유한 클래스의 수렴 속도는 $\Theta(B \min{1,\sqrt{\log(2M)/(n\tau)}+\log(2M)/(\epsilon n\tau)})$입니다. 이러한 완결된 속도는 순수 DP (pure DP) 하에서 성립하며, 이들의 하한 (lower bounds)은 명시된 작은 $\delta$ 영역에서의 근사 DP (approximate DP)로 확장됩니다. 볼록 Lipschitz 학습 (convex Lipschitz learning)의 경우, 모듈형 상한 및 하한 축소 (modular upper and lower reductions)를 통해 CVaR 특유의 프라이버시 항이 반드시 $1/(\epsilon n\tau)$에 비례하여 스케일링됨을 보여주며, 차원 의존성은 프라이버시가 적용된 확률적 볼록 최적화 (private stochastic convex optimization)로부터 상속됩니다. 종합적으로, 이러한 결과들은 $\Theta(n\tau)$의 정보가 있는 꼬리 기록을 대상으로 하는 일반적인 프라이버시 학습이 프라이버시 CVaR 학습 내부의 전형적인 어려운 하위 문제 (hard subproblem)임을 식별합니다.