We study $L_2$ mean estimation under central differential privacy and
communication constraints, and address two key challenges: firstly, existing
mean estimation schemes that simultaneously handle both constraints are usually
optimized for $L_\infty$ geometry and rely on random rotation or Kashin's
representation to adapt to $L_2$ geometry, resulting in suboptimal leading
constants in mean square errors (MSEs); secondly, schemes achieving
order-optimal communication-privacy trade-offs do not extend seamlessly to
streaming differential privacy (DP) settings (e.g., tree aggregation or matrix
factorization), rendering them incompatible with DP-FTRL type optimizers.
In this work, we tackle these issues by introducing a novel privacy
accounting method for the sparsified Gaussian mechanism that incorporates the
randomness inherent in sparsification into the DP noise. Unlike previous
approaches, our accounting algorithm directly operates in $L_2$ geometry,
yielding MSEs that fast converge to those of the uncompressed Gaussian
mechanism. Additionally, we extend the sparsification scheme to the matrix
factorization framework under streaming DP and provide a precise accountant
tailored for DP-FTRL type optimizers. Empirically, our method demonstrates at
least a 100x improvement of compression for DP-SGD across various FL tasks.

在本研究中，我们通过引入一种新的隐私账户方法，将稀疏高斯机制中的稀疏性所固有的随机性结合到差分隐私噪声中，解决了 $L_2$ 均值估计在中心差分隐私和通信约束下的两个关键挑战，并扩展了稀疏化方案到流式差分隐私的矩阵分解框架，为 DP-FTRL 类型的优化器提供了一个精确的账户方法。

流式差分隐私下 $L_2$ 均值估计的通信隐私权衡改进

Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under  Streaming Differential Privacy

Le Cam's method, Fano's inequality, and Assouad's lemma are three widely used
techniques to prove lower bounds for statistical estimation tasks. We propose
their analogues under central differential privacy. Our results are simple,
easy to apply and we use them to establish sample complexity bounds in several
estimation tasks. We establish the optimal sample complexity of discrete
distribution estimation under total variation distance and $\ell_2$ distance.
We also provide lower bounds for several other distribution classes, including
product distributions and Gaussian mixtures that are tight up to logarithmic
factors. The technical component of our paper relates coupling between
distributions to the sample complexity of estimation under differential
privacy.

本文使用中心差分隐私提出了 Le Cam 方法、Fano 不等式和 Assouad 引理的类似物，并且通过该方法在多个统计估计任务中建立了样本复杂性边界，包括离散分布估计和 l2 距离评估。我们还提供了针对几个其他分布类别的下界，包括产品分布和高斯混合分布，这些下界在对数因子上是精确的。我们的技术贡献在于将分布之间的耦合与基于差分隐私的估计的样本复杂度相关联。