Differentially Private Optimization with Sparse Gradients

本文的研究动机是应用于大型嵌入式模型，研究在个体梯度稀疏的情况下的差分隐私优化问题。我们从经典的均值估计问题入手，提出了新的近乎最优的界限，但是这些界限是基于稀疏数据的，相比于现有算法在高维情况下有所改进。在此基础上，我们得到了纯差分隐私算法和近似差分隐私算法，这些算法的速率几乎是最优的，适用于稀疏梯度的随机凸优化问题。前者是该问题的第一个近乎与维度无关的速率。最后，我们研究了近似差分隐私优化中经验损失的稳定点的逼近，并得到了依赖于稀疏性而不是维度的速率，只有对数因子。

本论文旨在解决在大型嵌入模型应用中的差分隐私优化问题，特别是在个体梯度稀疏的情况下。作者试图提出一种新的算法来提高现有算法的效率。

论文提出了一种新的算法，可以在个体梯度稀疏的情况下，实现隐私保护的随机凸优化，同时具有几乎最优的速率。

论文提出的算法在高维情况下具有几乎维度独立的速率，是目前为止该问题的首个算法。此外，论文还研究了近似差分隐私优化中的稳定点近似问题，并获得了基于稀疏性而非维度的速率。

在这个领域中，最近的相关研究包括：'Differentially Private Empirical Risk Minimization of Lipschitz Functions'，'Differentially Private Stochastic Gradient Descent with Improved Utility and Complexity'，'Differentially Private Convex Optimization with Non-Convex Constraints'等。