Pure ε-차분 프라이버시(DP) 하에서 연속 카운팅에 쓰이는 하삼각 프리픽스합 행렬 T_n의 임의 실수 행렬 분해 비용을 분석한 논문. c_F(T_n)와 c_2(T_n) 모두 Θ((log(n+1))^{3/2})임을 증명해, 부호·희소성·정사각 제약 없이 임의의 유한 내부 차원에서도 최적화된 평균·최대 제곱오차가 Θ(ε^{-2}log^3(n+1))임을 보였다. p-핵 장애물과 Pietsch/Hinrichs-Pietsch 근사공간 변환을 이용한 하한 증명과 Fenwick 구간 분해를 통한 상한 증명으로 Arkhipov-Kalinin이 0/1 원소 제한에서 증명한 결과를 임의 실수 인자로 확장했다. 이는 순수 DP 행렬 메커니즘의 이론적 한계를 명확히 규명해, 차분 프라이버시 기반 연속 카운팅 시스템 설계의 성능 하한을 제시한다는 의의가 있다.
- •하삼각 프리픽스합 행렬 T_n의 인수분해 비용이 부호·희소성 제약 없이 Θ((log(n+1))^{3/2})임을 증명
- •순수 ε-DP 행렬 메커니즘의 최적화된 평균·최대 제곱오차가 Θ(ε^{-2}log^3(n+1))로 확정됨
- •p-핵 장애물과 Pietsch-Hinrichs 근사공간 변환을 이용한 하한 증명 기법 제시
- •Fenwick 구간 분해로 하한과 일치하는 상한 구성
- •Arkhipov-Kalinin의 0/1 원소 제한 결과를 임의 실수 인자로 확장
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting
본문 미리보기
arXiv:2607.28703v1 Announce Type: new Abstract: Let \(T_n\) be the lower-triangular prefix-sum matrix and let \(\cfrob(T_n)\) and \(\ctwo(T_n)\) be the factorization costs that govern mean and maximum per-coordinate squared error of the Laplace matrix mechanism under pure \(\eps\)-differential privacy, for \(\eps>0\). We prove \(\cfrob(T_n),\ctwo(T_n)=\Theta\bigl((\log(n+1))^{3/2}\bigr)\) with no sign, sparsity, or squareness restriction and with arbitrary finite inner dimension. Consequently,
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 10:58AI 초안
