Near-Optimal differentially private low-rank trace regression with guaranteed private initialization
<|reference_start|>Near-Optimal differentially private low-rank trace regression with guaranteed private initialization: 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.<|reference_end|>
@article{zha2024near-optimal,
    title={Near-Optimal differentially private low-rank trace regression with
  guaranteed private initialization},
    author={Mengyue Zha},
    journal={arXiv preprint arXiv:2403.15999},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.15999},
    primaryClass={stat.ML cs.CR cs.LG}
}