데이터를 결합해야 할까? 개인 정보 보호를 위한 데이터 공유 평가 알고리즘 및 한계

본 논문에서는 두 당사자가 기계 학습 모델을 훈련하기 위해 데이터를 통합해야 하는 경우를 연구합니다. 두 에이전트인 Alice와 Bob은 각각 민감한 레이블이 지정된 데이터셋을 보유하고 있으며, 주어진 가설 클래스 $\mathcal{H}$로부터 분류기(classifier)를 훈련하고자 합니다. 각 당사자의 데이터셋이 자체적으로 완벽하게 분류될 수 있더라도, 두 당사자는 서로 다른 상충되는 레이블링 표준을 따르거나 특징 및 레이블 세트에 영향을 미치는 선택 편향(selection biases)을 가질 수 있어, $\mathcal{H}$ 내의 단일 분류기가 결합된 데이터에 적합하지 않을 수 있습니다. 따라서 Alice와 Bob은 데이터를 공유하기 전에, 개별 데이터 포인트를 서로에게 노출하지 않으면서도, $\mathcal{H}$ 내의 단일 분류기가 두 데이터셋 모두에 공동으로 적합할 수 있는지 테스트하고자 합니다. 우리는 이 문제를 학습 이론적 관점에서 $\operatorname{opt}\mathcal{H}$, 즉 통합된 데이터에서 $\mathcal{H}$ 내 임의의 가설이 범하는 최소 오류 횟수(minimum number of mistakes)를 통해 공식화합니다. 에이전트들은 상호 작용 통신을 통해 순수한 $\varepsilon$-양자 차분 프라이버시(pure $\varepsilon$-two-party differential privacy) 하에서 $\operatorname{opt}\mathcal{H}=0$ (호환 가능한 데이터셋)과 $\operatorname{opt}_\mathcal{H}\geq t$ (상충되는 데이터셋)을 구별해야 합니다. 신뢰할 수 있는 큐레이터(trusted curator)는 $t=O(1/\varepsilon)$로 이를 수행할 수 있으며, 우리는 큐레이터 없이 얼마나 작은 $t$가 가능한지 질문합니다. 크기 $m$의 영역에 대한 실수 선상의 임계값(thresholds)의 경우, 최적의 $t$는 $\tildeΘ(\log\log m/\varepsilon)$로 나타나며, 이는 심지어 큐레이터가 있는 경우에도 개인적으로 임계값을 학습하는 데 필요한 $Θ(\log m/\varepsilon)$ 샘플보다 지수적으로 작습니다. $\mathbb{R}^d$에서의 반공간(halfspaces)의 경우, $m$에 대한 의존성은 $\log(m)$으로 증가합니다: 우리는 $t=\tilde{O}(d^3\log m/\varepsilon)$인 프로토콜을 제시하고, 일부 영역은 $t=\Omega(d\log(m/d)/\varepsilon)$를 요구한다는 것을 보여줍니다.