SSTQ: 서브샘플링된 확률적 터보 양자화를 통한 개인 정보 보호 벡터 양자화

SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant

분산 최적화에서 낮은 통신 비용을 유지하면서 로컬 차등 프라이버시를 달성하는 것은 여전히 어려운 과제입니다. 기존의 벡터 양자화 방법인 vqSGD는 고차원 기하학적 구조를 사용하지만, 바람직하지 않은 차원에 의존적인 분산을 초래합니다. 본 연구에서는 서브샘플링된 확률적 터보 양자화(SSTQ)라는 프레임워크를 제안합니다. SSTQ는 과대포함된 동일 정규 프레임, 좌표 서브샘플링 및 개인 정보 보호를 고려한 1차원 양자화를 결합합니다. SSTQ에는 두 가지 변형이 있습니다. 하나는 플랫 랜덤 응답 버전이고 다른 하나는 메트릭 인지 라플라스 버전이며, 후자가 더 넓은 코드북 비트 폭 범위에 더 적합합니다. 우리는 SSTQ가 프레임 크기 $N = Θ(d)$인 경우 각 클라이언트당 $ ceil rac{ ext{log}_2 N}{ floor} + b$비트만 사용하면서 최적의 평균 제곱 오차 스케일링을 달성한다는 것을 보여줍니다. 또한, 코드북에 의존적인 MSE 스케일링을 $O(4^b)$에서 $O(2^b)$로 줄이는 개인 정보 보호를 고려한 대체 코드북 객관 함수를 유도합니다. 마지막으로, CIFAR-10 및 Fashion-MNIST 데이터셋을 사용한 연합 학습 작업에서 SSTQ를 기존 방법과 비교하여 우수한 성능과 통신 효율성을 입증했습니다.

Achieving local differential privacy in distributed optimization while maintaining low communication cost remains challenging. Existing vector quantization methods, such as vqSGD, use high-dimensional geometric constructions but incur unfavorable dimension-dependent variance. In this work, we propose Subsampled Stochastic TurboQuant (SSTQ), a framework that combines overcomplete equal-norm tight frames, coordinate subsampling, and privacy-aware one-dimensional quantization. SSTQ includes two variants: a Flat Randomized Response version and a Metric-Aware Laplace version, the latter being better suited to higher codebook bit-width regimes. We show that SSTQ achieves optimal mean squared error scaling while using only $\lceil \log_2 N \rceil + b$ bits per client, where $N = Θ(d)$ is the frame size. We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4^b)$ to $O(2^b)$. Finally, we empirically evaluate SSTQ against established baselines on federated learning tasks using CIFAR-10 and Fashion-MNIST, demonstrating favorable utility and communication efficiency. Some of the analytical derivations were first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified those derivations and edited them for clarity of presentation.