We study differentially private (DP) estimation of a rank-$r$ matrix $M \in
\mathbb{R}^{d_1\times d_2}$ under the trace regression model with Gaussian
measurement matrices. Theoretically, the sensitivity of non-private spectral
initialization is precisely characterized, and the
differential-privacy-constrained minimax lower bound for estimating $M$ under
the Schatten-$q$ norm is established. Methodologically, the paper introduces a
computationally efficient algorithm for DP-initialization with a sample size of
$n \geq \widetilde O (r^2 (d_1\vee d_2))$. Under certain regularity conditions,
the DP-initialization falls within a local ball surrounding $M$. We also
propose a differentially private algorithm for estimating $M$ based on
Riemannian optimization (DP-RGrad), which achieves a near-optimal convergence
rate with the DP-initialization and sample size of $n \geq \widetilde O(r (d_1
+ d_2))$. Finally, the paper discusses the non-trivial gap between the minimax
lower bound and the upper bound of low-rank matrix estimation under the trace
regression model. It is shown that the estimator given by DP-RGrad attains the
optimal convergence rate in a weaker notion of differential privacy. Our
powerful technique for analyzing the sensitivity of initialization requires no
eigengap condition between $r$ non-zero singular values.

我们在高斯测量矩阵下研究具有秩 - r 矩阵 M 的隐私保护估计问题。我们从理论上精确刻画了非隐私谱初始化的敏感性，并建立了在 Schatten-q 范数下对 M 进行估计的差分隐私约束下准确的极小极限下界。在方法上，我们引入了一个计算效率高的 DP 初始化算法，样本量为 n≥ ~O (r^2 (d_1 ∨ d_2))。在某些规则条件下，DP 初始化落在包围 M 的局部球内。我们还提出了一个基于 Riemannian 优化的差分隐私算法来估计 M（DP-RGrad），该算法在 DP 初始化和样本量为 n≥ ~O (r (d_1 + d_2)) 时达到接近最优的收敛速率。最后，本文讨论了在迹回归模型下低秩矩阵估计的极小极限下界和上界之间的差距。实验证明，DP-RGrad 给出的估计器在较弱的差分隐私概念下达到了最优的收敛速率。我们分析初始化敏感性的强大技术不需要 r 个非零奇异值之间的特征间隔条件。

保证私有化初始化的近似最优差分隐私低秩跟踪回归

Near-Optimal differentially private low-rank trace regression with  guaranteed private initialization

We provide a new algorithmic framework for differentially private estimation
of general functions that adapts to the hardness of the underlying dataset. We
build upon previous work that gives a paradigm for selecting an output through
the exponential mechanism based upon closeness of the inverse to the underlying
dataset, termed the inverse sensitivity mechanism. Our framework will slightly
modify the closeness metric and instead give a simple and efficient application
of the sparse vector technique. While the inverse sensitivity mechanism was
shown to be instance optimal, it was only with respect to a class of unbiased
mechanisms such that the most likely outcome matches the underlying data. We
break this assumption in order to more naturally navigate the bias-variance
tradeoff, which will also critically allow for extending our method to
unbounded data. In consideration of this tradeoff, we provide strong intuition
and empirical validation that our technique will be particularly effective when
the distances to the underlying dataset are asymmetric. This asymmetry is
inherent to a range of important problems including fundamental statistics such
as variance, as well as commonly used machine learning performance metrics for
both classification and regression tasks. We efficiently instantiate our method
in $O(n)$ time for these problems and empirically show that our techniques will
give substantially improved differentially private estimations.

我们提供了一个新的算法框架，用于差分隐私估计一般函数，该框架根据底层数据集的难度进行动态调整。我们构建在先前的工作基础上，通过接近逆过程的数据集，即称为逆敏感性机制的指数机制选择一个输出的范例。我们的框架稍微修改了接近度度量，并提供了稀疏向量技术的简单有效应用。我们打破这个假设，以更自然地处理偏差 - 方差平衡，这也关键地允许我们将方法扩展到无界数据。考虑到这种平衡，我们提供了强有力的直觉和实证验证，表明我们的技术在与底层数据集的距离是非对称的情况下尤为有效。我们以 $O (n)$ 的时间高效实现了这些问题，并通过实验证明我们的技术能够显著改进差分隐私估计。

差分隐私中的实例特定异质敏感度

Instance-Specific Asymmetric Sensitivity in Differential Privacy

We consider the differentially private estimation of multiple quantiles (MQ)
of a distribution from a dataset, a key building block in modern data analysis.
We apply the recent non-smoothed Inverse Sensitivity (IS) mechanism to this
specific problem. We establish that the resulting method is closely related to
the recently published ad hoc algorithm JointExp. In particular, they share the
same computational complexity and a similar efficiency. We prove the
statistical consistency of these two algorithms for continuous distributions.
Furthermore, we demonstrate both theoretically and empirically that this method
suffers from an important lack of performance in the case of peaked
distributions, which can degrade up to a potentially catastrophic impact in the
presence of atoms. Its smoothed version (i.e. by applying a max kernel to its
output density) would solve this problem, but remains an open challenge to
implement. As a proxy, we propose a simple and numerically efficient method
called Heuristically Smoothed JointExp (HSJointExp), which is endowed with
performance guarantees for a broad class of distributions and achieves results
that are orders of magnitude better on problematic datasets.

本文研究了从数据集中不考虑统计学的特性的情况下，利用非平滑逆灵敏（IS）机制估计分布的多个分位数（MQ）的问题，并将其应用于数据分析中。通过实验证明非平滑 IS 机制与 JointExp 算法在计算复杂度和效率方面非常相似，同时也证明了这两种算法在连续分布下是统计一致的。然而，在尖峰分布的情况下，这种方法存在表现不佳的问题，作者提出了一种称为启发式平滑 JointExp 的方法，它在问题数据集上的表现比原算法好了数个数量级。