We study the problem of locally private mean estimation of high-dimensional
vectors in the Euclidean ball. Existing algorithms for this problem either
incur sub-optimal error or have high communication and/or run-time complexity.
We propose a new algorithmic framework, ProjUnit, for private mean estimation
that yields algorithms that are computationally efficient, have low
communication complexity, and incur optimal error up to a $1+o(1)$-factor. Our
framework is deceptively simple: each randomizer projects its input to a random
low-dimensional subspace, normalizes the result, and then runs an optimal
algorithm such as PrivUnitG in the lower-dimensional space. In addition, we
show that, by appropriately correlating the random projection matrices across
devices, we can achieve fast server run-time. We mathematically analyze the
error of the algorithm in terms of properties of the random projections, and
study two instantiations. Lastly, our experiments for private mean estimation
and private federated learning demonstrate that our algorithms empirically
obtain nearly the same utility as optimal ones while having significantly lower
communication and computational cost.

提出了一种新的算法框架 ProjUnit，用于保证局部隐私均值估计，该算法框架通过将随机器的输入投影到随机低维子空间并规范化结果，然后在低维空间中运行优化算法来实现计算效率高，通讯复杂度低，并且具有最优误差，同时，通过适当地对设备之间的随机投影矩阵进行相关性，可以实现快速服务器运行时间，最后，实验表明，该算法框架在保持优异的准确度的同时，具有显著较低的通讯和计算成本。

通过随机投影进行快速最优局部隐私均值估计

Fast Optimal Locally Private Mean Estimation via Random Projections

It is often desirable to reduce the dimensionality of a large dataset by
projecting it onto a low-dimensional subspace. Matrix sketching has emerged as
a powerful technique for performing such dimensionality reduction very
efficiently. Even though there is an extensive literature on the worst-case
performance of sketching, existing guarantees are typically very different from
what is observed in practice. We exploit recent developments in the spectral
analysis of random matrices to develop novel techniques that provide provably
accurate expressions for the expected value of random projection matrices
obtained via sketching. These expressions can be used to characterize the
performance of dimensionality reduction in a variety of common machine learning
tasks, ranging from low-rank approximation to iterative stochastic
optimization. Our results apply to several popular sketching methods, including
Gaussian and Rademacher sketches, and they enable precise analysis of these
methods in terms of spectral properties of the data. Empirical results show
that the expressions we derive reflect the practical performance of these
sketching methods, down to lower-order effects and even constant factors.

利用随机矩阵的谱分析最新进展，我们开发了一种新的技术，提供了随机投影矩阵的期望值的确切表达式，这些表达式可以用来表征多种常见的机器学习任务中的降维性能，包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法，包括高斯和 Rademacher 草图，结果表明，我们推导出的表达式反映了这些草图方法的实际性能，甚至体现了较低阶效应和恒定因子。