차분 프라이버시 PCA를 위한 적응형 거듭제곱 반복법
Adaptive Power Iteration Method for Differentially Private PCA
한국어 초록
본 논문은 행렬 $A\in\mathbb{R}^{n\times d}$의 상위 특이벡터를 근사적으로 계산하는 문제에 대한 $\left(\epsilon,\delta\right)$-차분 프라이버시 알고리즘을 연구한다. 여기서 $A$의 각 행은 $\mathbb{R}^{d}$의 데이터 점이다. Dwork-Talwar-Thakurta-Zhang(STOC 2014)을 따라, 인접한 입력이 단일 행만 다른 프라이버시 모델을 고려한다. 본 논문은 i.i.d. 데이터를 비롯한 많은 응용에서 행렬의 구조적 특성인 낮은 코히어런스를 갖는 입력 행렬에 대해 최악의 경우를 넘어서는 보장을 달성하는 새로운 알고리즘을 제시한다. 본 알고리즘은 프라이빗 거듭제곱 반복법에 관한 방대한 문헌에 기여하며, 이 코히어런스 매개변수에 적응하는 새로운 필터링 기법을 도입한다. 본 연구는 인접한 입력이 단일 원소에서 최대 1만큼만 다른, 더 제한적인 프라이버시 모델에서 최악의 경우를 넘어서는 보장을 달성한 Hardt-Roth(STOC 2013)의 연구와 출발점을 달리하면서 이를 보완한다.
원문 초록
We study $\left(\epsilon,\delta\right)$-differentially private algorithms for the problem of approximately computing the top singular vector of a matrix $A\in\mathbb{R}^{n\times d}$ where each row of $A$ is a data point in $\mathbb{R}^{d}$. Following Dwork-Talwar-Thakurta-Zhang (STOC 2014), we consider the privacy model where neighboring inputs differ by one single row. We give a novel algorithm that achieves beyond-worst-case guarantees for input matrices with low coherence, which is a structural property of matrices in many applications, including but not limited to i.i.d. data. Our algorithm contributes to the extensive literature on private power iteration methods, where we introduce a new filtering technique which adapts to this coherence parameter. Our work departs from and complements the work by Hardt-Roth (STOC 2013) which achieves beyond-worst-case guarantees for the more restrictive privacy model where neighboring inputs differ in one single entry by at most 1.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2602.11454v4제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.