다중 스케일 FFT를 활용한 임의 할당 프라이버시 손실 계정(Accounting)

요약

본 논문은 임의 할당 샘플링 방식의 프라이버시 손실 분포(PLD) 회계기 효율성을 개선하는 'multiscale FFT' 알고리즘을 제시합니다. 이 알고리즘은 기존 $O(\alpha^{-2})$ 복잡도를 $O(\alpha^{-1}\log(1/\alpha))$로 획기적으로 줄여 계산 속도를 높입니다. 또한, 반올림 오차를 감소시켜 높은 정확도에서도 성능 향상을 입증했습니다.

핵심 포인트

• multiscale FFT 알고리즘을 통해 PLD 회계기의 효율성을 개선함.
• 실행 시간이 $O(\alpha^{-2})$에서 $O(\alpha^{-1}\log(1/\alpha))$로 단축됨.
• 반올림 오차를 줄여 프라이버시 손실의 평균 및 $\chi^2$ 발산을 감소시킴.
• DP-SGD 등 환경에서 높은 정확도로 속도 향상을 달성함.