Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems
Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems
复制标题
DOI：
10.1007/s10107-023-01953-5
复制
发表时间：
2021-04
影响因子：
2.7
通讯作者：
Digvijay Boob;Crist'obal Guzm'an
中科院分区：
文献类型：
--
作者：
Digvijay Boob;Crist'obal Guzm'an
本文首次系统地研究了微分隐私约束下的随机变分不等式和随机鞍点问题。我们提出了两种算法：噪声随机外梯度（NSEG）和噪声不精确随机邻近点（NISPP）。我们表明，这些算法的随机近似变量达到风险界消失的数据集大小的函数，相对于强间隙函数;和替换变量的采样实现最佳风险界相对于弱间隙函数。我们还证明了弱间隙函数的同阶下界。因此，我们的算法是最优的。我们分析的关键是算法的稳定性界限，这两个是新的，即使在非私人的情况下，调查。对于NSEG和NISPP，具有替换的采样算法的运行时间相对于数据集大小的依赖性。
In this work, we conduct the first systematic study of stochastic variational inequality (SVI) and stochastic saddle point (SSP) problems under the constraint of differential privacy (DP). We propose two algorithms: Noisy Stochastic Extragradient (NSEG) and Noisy Inexact Stochastic Proximal Point (NISPP). We show that a stochastic approximation variant of these algorithms attains risk bounds vanishing as a function of the dataset size, with respect to the strong gap function; and a sampling with replacement variant achieves optimal risk bounds with respect to a weak gap function. We also show lower bounds of the same order on weak gap function. Hence, our algorithms are optimal. Key to our analysis is the investigation of algorithmic stability bounds, both of which are new even in the nonprivate case. The dependence of the running time of the sampling with replacement algorithms, with respect to the dataset sizen, isfor NSEG andfor NISPP.