Not All Learnable Distribution Classes are Privately Learnable

기술적 요약: "모든 학습 가능한 분포 클래스가 사설 학습 가능한 것은 아니다"

문제 제기
본 논문은 통계적 학습 이론과 미분 프라이버시 (DP) 가 교차하는 영역에서 근본적인 질문에 답합니다: 표준 (비사설) 환경에서 학습 가능한 모든 분포 클래스가 $(\varepsilon, \delta)$-미분 프라이버시 제약 하에서도 학습 가능한가?

순수 미분 프라이버시 ($\delta=0$ 인 $\varepsilon$-DP) 는 학습 가능 클래스와 사설 학습 가능 클래스 사이에 엄격한 분리 (종종 덮기/패킹 수로 특징지어짐) 를 부과한다는 점은 확립되어 있으나, 근사 미분 프라이버시 ($( \varepsilon, \delta)$-DP) 의 상태는 여전히 열린 질문으로 남아 있었습니다. 최근 문헌은 사설 분포 학습을 위한 점점 더 일반적인 프레임워크를 제시해 왔으며, 이에 따라 Ashtiani [Ash22] 는 위의 질문에 대한 답이 긍정적일 것이라고 추측했습니다. 즉, 모든 학습 가능한 분포 클래스는 사설 학습 가능하다는 것입니다.

방법론 및 구성
저자들은 $\mathcal{H}_w$로 표기되는 특정 분포 클래스를 구성함으로써 이 추측을 반박합니다. 이 클래스는 반례 역할을 합니다. 이 구성은 분포의 혼합을 포함하는 "트랩도어" 메커니즘을 활용합니다:

1. 클래스 구조: 클래스 $\mathcal{H}_{w,d}$는 공통 매개변수 벡터 $\mathbf{p} \in [0,1]^d$를 공유하는 $d+1$개 성분들의 혼합으로 구성됩니다.
   • "키" 성분: $\{0,1\}^d$ 위의 이진 곱 분포로, 혼합 가중치 $w$를 가집니다. 이 성분에서 단일 샘플을 추출하면 전체 매개변수 벡터 $\mathbf{p}$에 대한 정보를 얻을 수 있습니다.
   • "어려운" 성분: $d$개의 추가 성분으로, 각각 $j \in \{1, \dots, d\}$에 대해 $\{\pm j\}$를 지지집합으로 가지며, 혼합 가중치는 $(1-w)/d$입니다. 이들 중 하나에서 샘플을 추출하면 $\mathbf{p}$의 단일 좌표에 대한 정보만 얻을 수 있습니다.
2. 트랩도어: 혼합 가중치 $w$는 목표 오차 $\alpha$에 대해 $1/(2\alpha)$로 설정됩니다. 이는 "어려운" 성분들이 혼합물에서 지배적이 되도록 (샘플링할 확률이 높음) 하면서, "키" 성분은 드물게 나타나도록 보장합니다.
3. 차원성 트릭: 클래스 $\mathcal{H}_w$는 모든 차원 $d \ge 2$에 대한 이러한 클래스들의 합집합으로 정의됩니다. 이 구성은 차원 $d$가 사전에 고정되지 않았음에도 불구하고 학습의 어려움이 $d$에 따라 증가하도록 보장합니다.

주요 결과 및 증명
본 논문은 총변동 (TV) 거리와 관련하여 클래스 $\mathcal{H}_w$에 대한 비사설 학습 가능성과 사설 학습 가능성 사이의 분리를 확립합니다:

1. 비사설 학습 가능성 (유한 샘플):
   저자들은 $\mathcal{H}_w$가 상수 오차까지 상수 개수 (차원 $d$에 무관한) 의 샘플로 학습 가능함을 보여줍니다.

   • 메커니즘: "키" 성분이 확률 $w$로 나타나므로, 비사설 알고리즘은 키 성분을 관찰할 만큼 충분한 샘플을 수집할 수 있습니다. 일단 관찰되면 차원 $d$가 식별되고, 이진 곱 분포의 표본 평균을 통해 매개변수 벡터 $\mathbf{p}$를 추정할 수 있습니다.
   • 복잡도: 샘플 복잡도는 $O(1/\alpha^3 \cdot \log(1/\beta)$)이며, 차원 $d$에 대해 상수입니다.

2. 사설 비학습 가능성 (무한 샘플 필요):
   저자들은 동일한 오차 보장을 유지하면서 유한한 수의 샘플을 사용하여 $(\varepsilon, \delta)$-DP 메커니즘이 이 클래스를 학습할 수 없음을 증명합니다.

   • 축소: 그들은 $\mathcal{H}_{w,d}$에 대한 밀도 추정 문제를 이진 곱 분포에 대한 $\ell_1$-매개변수 추정 문제로 축소하는 구성을 제시합니다.
   • 하한: 이진 곱 분포에 대한 사설 평균 추정의 알려진 하한 (특히 [KLSU19] 에서) 을 활용하여, DP 하에서 $\mathcal{H}_{w,d}$를 학습하는 데 필요한 샘플 복잡도가 $\Omega(\sqrt{d}/(\sqrt{\alpha}\varepsilon))$으로 증가함을 보여줍니다.
   • 모순: 클래스 $\mathcal{H}_w$는 임의의 $d \ge 2$에 대한 분포들을 포함하므로, 필요한 샘플 크기가 $\sqrt{d}$에 따라 증가함에 따라, DP 하에서 전체 클래스 $\mathcal{H}_w$를 학습하기에 충분한 유한한 샘플 크기 $n$은 존재하지 않습니다. $d \to \infty$일 때, 필요한 샘플 크기는 무한대에 접근합니다.

주요 기여

• 추측 반박: 본 논문은 Ashtiani 의 "모든 학습 가능한 분포 클래스가 $(\varepsilon, \delta)$-DP 하에서 사설 학습 가능하다"는 추측에 대한 명시적인 반례를 제시합니다.
• 학습 가능성의 분리: 클래스가 비사설적으로는 $O(1)$개의 샘플로 학습 가능하지만, 사설적으로는 무한한 수의 샘플이 필요하다는 엄격한 분리를 보여줍니다.
• 트랩도어 구성: 저자들은 드물지만 고차원 매개변수에 대한 열쇠 역할을 하는 성분과, 그렇지 않으면 지배적이면서 학습하기 어려운 성분으로 가려지는 구조를 가진 특정 "트랩도어" 구성을 도입합니다. 이 구조는 프라이버시 제약을 위반하거나 금지할 정도로 큰 샘플 크기를 요구하지 않고서는 "키"에 접근할 수 없도록 사설 메커니즘을 막습니다.

의의 및 주장
본 논문은 해당 추측을 "약하게 반박"한다고 주장합니다. 저자들은 "강한 반박"을 위해서는 임의의 목표 오차 (상수 오차가 아닌) 에 대해서도 유한한 샘플로 비사설 학습 가능함을 보여야 하지만, 이는 증명하지 않았다고 명시적으로 언급합니다. 그러나 그들의 결과는 상수 오차 보장조차도 사설 분포 학습의 지형이 비사설 학습과 근본적으로 다름을 보여주므로 중요합니다.

이 연구는 비사설 학습자로부터의 블랙박스 축소에만 의존해서는 사설 학습을 위한 일반적인 프레임워크를 구축할 수 없으며, 추가적인 구조적 가정이 필요함을 강조합니다. 드물지만 학습에 필수적인 "키" 성분의 존재가, 비사설 알고리즘이 효율적일지라도 사설 알고리즘에게는 극복할 수 없는 장벽을 만들 수 있음을 확립합니다.

결론
본 논문은 모든 학습 가능한 분포 클래스에 대해 작동하는 일반적인 사설 학습 알고리즘을 설계하려는 의제는 완전히 실현될 수 없다고 결론 내립니다. 특정 오차 허용 범위 (고려된 상수 영역 내) 에 관계없이, 프라이버시 제약이 샘플 복잡성을 유한에서 무한으로 근본적으로 변화시키는 학습 가능한 클래스들이 존재합니다.