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 revisit the inductive matrix completion problem that aims to recover a
rank-$r$ matrix with ambient dimension $d$ given $n$ features as the side prior
information. The goal is to make use of the known $n$ features to reduce sample
and computational complexities. We present and analyze a new gradient-based
non-convex optimization algorithm that converges to the true underlying matrix
at a linear rate with sample complexity only linearly depending on $n$ and
logarithmically depending on $d$. To the best of our knowledge, all previous
algorithms either have a quadratic dependency on the number of features in
sample complexity or a sub-linear computational convergence rate. In addition,
we provide experiments on both synthetic and real world data to demonstrate the
effectiveness of our proposed algorithm.

本文提出了一种基于梯度的非凸优化算法，用于解决归纳矩阵补全问题，该算法收敛于真实矩阵，具有线性样本复杂度和对数环境维度。该算法的实验结果表明其有效性。

多阶段 Procrustes 流算法加速高效归纳矩阵补全

Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase  Procrustes Flow

We consider the non-square matrix sensing problem, under restricted isometry
property (RIP) assumptions. We focus on the non-convex formulation, where any
rank-$r$ matrix $X \in \mathbb{R}^{m \times n}$ is represented as $UV^\top$,
where $U \in \mathbb{R}^{m \times r}$ and $V \in \mathbb{R}^{n \times r}$. In
this paper, we complement recent findings on the non-convex geometry of the
analogous PSD setting [5], and show that matrix factorization does not
introduce any spurious local minima, under RIP.

本文探讨了基于受限等距性质（RIP）假设的非方阵矩阵感知问题，并关注了非凸形式化的矩阵分解，证明了矩阵分解不会在 RIP 下引入任何虚假的局部最小值。