Private data analysis faces a significant challenge known as the curse of
dimensionality, leading to increased costs. However, many datasets possess an
inherent low-dimensional structure. For instance, during optimization via
gradient descent, the gradients frequently reside near a low-dimensional
subspace. If the low-dimensional structure could be privately identified using
a small amount of points, we could avoid paying (in terms of privacy and
accuracy) for the high ambient dimension.
On the negative side, Dwork, Talwar, Thakurta, and Zhang (STOC 2014) proved
that privately estimating subspaces, in general, requires an amount of points
that depends on the dimension. But Singhal and Steinke (NeurIPS 2021) bypassed
this limitation by considering points that are i.i.d. samples from a Gaussian
distribution whose covariance matrix has a certain eigenvalue gap. Yet, it was
still left unclear whether we could provide similar upper bounds without
distributional assumptions and whether we could prove lower bounds that depend
on similar eigenvalue gaps.
In this work, we make progress in both directions. We formulate the problem
of private subspace estimation under two different types of singular value gaps
of the input data and prove new upper and lower bounds for both types. In
particular, our results determine what type of gap is sufficient and necessary
for estimating a subspace with an amount of points that is independent of the
dimension.

在这项工作中，我们在两种不同类型的输入数据的奇异值间隙下，对私有子空间估计的问题进行了数学建模，并证明了两种情况下的新的上下界。特别是，我们的结果确定了在估计子空间时所需的点数与维度无关的间隙类型。

无需分布假设的差分隐私子空间估计

On Differentially Private Subspace Estimation Without Distributional  Assumptions

Private data analysis suffers a costly curse of dimensionality. However, the
data often has an underlying low-dimensional structure. For example, when
optimizing via gradient descent, the gradients often lie in or near a
low-dimensional subspace. If that low-dimensional structure can be identified,
then we can avoid paying (in terms of privacy or accuracy) for the high ambient
dimension.
We present differentially private algorithms that take input data sampled
from a low-dimensional linear subspace (possibly with a small amount of error)
and output that subspace (or an approximation to it). These algorithms can
serve as a pre-processing step for other procedures.

该研究探讨了差分隐私算法如何应用于低维线性子空间，以发现数据的低维结构并尽可能避免在隐私或准确性方面的代价。

隐私学习子空间

Privately Learning Subspaces

We examine the combination of two directions in the field of privacy
concerning computations over distributed private inputs - secure function
evaluation (SFE) and differential privacy. While in both the goal is to
privately evaluate some function of the individual inputs, the privacy
requirements are significantly different. The general feasibility results for
SFE suggest a natural paradigm for implementing differentially private analyses
distributively: First choose what to compute, i.e., a differentially private
analysis; Then decide how to compute it, i.e., construct an SFE protocol for
this analysis.
We initiate an examination whether there are advantages to a paradigm where
both decisions are made simultaneously. In particular, we investigate under
which accuracy requirements it is beneficial to adapt this paradigm for
computing a collection of functions including binary sum, gap threshold, and
approximate median queries. Our results imply that when computing the binary
sum of $n$ distributed inputs then:
* When we require that the error is $o(\sqrt{n})$ and the number of rounds is
constant, there is no benefit in the new paradigm.
* When we allow an error of $O(\sqrt{n})$, the new paradigm yields more
efficient protocols when we consider protocols that compute symmetric
functions.
Our results also yield new separations between the local and global models of
computations for private data analysis.

研究如何同时应用 SFE 和差分隐私来计算分布式私人输入的函数，比较不同误差要求下计算二进制和、间隔阈值、近似中位数等函数的新模式和已有模式的效率，并发现新模式对于对称函数具有更好的效率，同时也提供了隐私数据分析的全局模型和局部模型的新分离结果。