Stochastic privacy-preserving methods for nonconvex sparse learning
Stochastic privacy-preserving methods for nonconvex sparse learning
复制标题
DOI：
10.1016/j.ins.2022.09.062
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Guannan Liang;Qianqian Tong;Jiahao Ding;Miao Pan;J. Bi
中科院分区：
文献类型：
--
作者：
Guannan Liang;Qianqian Tong;Jiahao Ding;Miao Pan;J. Bi
稀疏学习是挖掘高维数据的关键。迭代硬阈值（IHT）方法是优化稀疏学习非凸目标的有效方法。然而，IHT方法容易受到推断敏感数据的攻击者的攻击。虽然开创性的工作试图缓解这种脆弱性，但他们面临着大规模问题的高计算成本问题。提出了基于随机梯度下降法（DP-SGD-HT）和基于随机控制随机梯度法（DP-SCSG-HT）的两种差分私有随机梯度法。DP-SGD-HT方法用小高斯噪声扰动随机梯度，而不是用计算量大的全梯度。因此，计算复杂度从O （n log (n)）降低到更低的O (b log (n))，其中n是样本量，b是用于计算随机梯度的小批量大小。DP-SCSG-HT方法进一步扰动大批量快照梯度控制的随机梯度，减小随机梯度方差。我们证明了这两种算法都保证了差分隐私，并且在估计偏差下具有线性收敛速率。效用分析检验了收敛速度和扰动水平之间的关系，得出了最著名的非凸稀疏优化的效用界。大量实验表明，我们的算法优于现有的方法。
Sparse learning is essential in mining high-dimensional data. Iterative hard thresholding (IHT) methods are effective for optimizing nonconvex objectives for sparse learning. However, IHT methods are vulnerable to adversary attacks that infer sensitive data. Although pioneering works attempted to relieve such vulnerability, they confront the issue of high computational cost for large-scale problems. We propose two differentially private stochastic IHT: one based on the stochastic gradient descent method (DP-SGD-HT) and the other based on the stochastically controlled stochastic gradient method (DP-SCSG-HT). The DP-SGD-HT method perturbs stochastic gradients with small Gaussian noise rather than full gradients, which are computationally expensive. As a result, computational complexity is reduced from O (n log (n)) to a lower O (b log (n)), where n is the sample size and b is the mini-batch size used to compute stochastic gradients. The DP-SCSG-HT method further perturbs the stochastic gradients controlled by large-batch snapshot gradients to reduce stochastic gradient variance. We prove that both algorithms guarantee differential privacy and have linear convergence rates with estimation bias. A utility analysis examines the relationship between convergence rate and the level of perturbation, yielding the best-known utility bound for nonconvex sparse optimization. Extensive experiments show that our algorithms outperform existing methods.