基于梯度扰动和BB步长的迭代收缩阈值差分隐私算法
Iterative Shrink Threshold Differential Privacy Algorithm Based on Gradient Perturbation and BB Step Size
DOI: 10.12677/AAM.2023.121022, PDF, HTML, 下载: 186  浏览: 359  国家自然科学基金支持
作者: 苑文丽, 彭定涛*：贵州大学，数学与统计学院，贵州 贵阳
关键词: 差分隐私保护；梯度扰动；收缩阈值算法；MCP正则；Differential Privacy Protection； Gradient Perturbation； Shrinkage Threshold Algorithm； MCP Regularization
摘要: 本文研究隐私保护下带有非凸正则的经验风险极小化问题，其中损失函数是凸函数，正则项 为MCP函数。提出了基于梯度扰动和Barzilar-Borwein (BB)步长的迭代收缩阈值差分隐私算法(ISTDP)。 首先，基于算法每次迭代均对梯度添加高斯噪声，证明了该算法具有差分隐私保护性质。 其次，基于以BB步长做试探步进行线搜索的迭代收缩阁值算法，证明了该算法可以收敛于任意给定的精度。因此，ISTDP算法是一种可以满足隐私保护要求的机器学习优化算法。
Abstract: In this paper, we study the problem of empirical risk minimization with nonconvex regularization under privacy protection, where the loss function is a convex function and the regular term is the MCP function. An iterative shrinkage threshold difference privacy algorithm (ISTDP) based on gradient perturbation and Barzir-Borwein (BB) step size is proposed. First, ISTDP algorithm is proved to have the property of differential privacy protection since Gauss noise is added to the gradient for each iteration in the algorithm. Secondly, it is proved that the ISTDP algorithm can converge at any given accuracy due to the fact that ISTDP algorithm adopts an iterative shrinkage threshold algorithm together with a line search beginning with BB step size. Therefore, ISTDP algorithm is a kind of machine learning optimization algorithm which can satisfy the requirement of privacy protection.
文章引用：苑文丽, 彭定涛. 基于梯度扰动和BB步长的迭代收缩阈值差分隐私算法[J]. 应用数学进展, 2023, 12(1): 183-202. https://doi.org/10.12677/AAM.2023.121022

参考文献

[1] Li, N., Lyu, M., Su, D. and Yang, W. (2016) Differential Privacy: From Theory to Practice. In: Synthesis Lectures on Information Security Privacy and Trust, Springer, Cham, 1-138.
https://doi.org/10.1007/978-3-031-02350-7
[2] Dwork, C., McSherry, F., Nissim, K. and Smith, A (2016) Calibrating Noise to Sensitivity in Private Data Analysis. Proceedings of the Third Conference on Theory of Cryptography, 7, 17-51.
https://doi.org/10.29012/jpc.v7i3.405
[3] Jiang, B., Li, J. and Yue, G. (2021) Differential Privacy for Industrial Internet of Things: Opportunities, Applications, and Challenges. IEEE Internet of Things Journal, 8, 10430- 10451.
https://doi.org/10.1109/JIOT.2021.3057419
[4] El Ouadrhiri, A. and Abdelhadi, A. (2022) Differential Privacy for Deep and Federated Learn- ing: A Survey. IEEE Access, 10, 22359-22380.
https://doi.org/10.1109/ACCESS.2022.3151670
[5] Dwork, C., Rothblum, G. and Vadhan, S. (2010) Boosting and Differential Privacy. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, Las Vegas, NV, 23-26 October 2010, 23-26.
https://doi.org/10.1109/FOCS.2010.12
[6] Girgis, A., Data, D. and Diggavi, S. (2021) Shuffled Model of Differential Privacy in Federated Learning. International Conference on Artificial Intelligence and Statistics, PMLR, 130, 2521- 2529.
[7] Adnan, M., Kalra, S. and Cresswell, J. (2022) Federated Learning and Differential Privacy for Medical Image Analysis. Scientific Reports, 12, Article No. 1953.
https://doi.org/10.1038/s41598-022-05539-7
[8] Abadi, M., Andy, C. and Goodfellow, L. (2016) Deep Learning with Differential Privacy. Pro- ceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,Vienna, 24-28 October 2016, 308-318.
https://doi.org/10.1145/2976749.2978318
[9] Chaudhuri, K. and Monteleoni, C. (2011) Differentially Private Empirical Risk Minimization.Journal of Machine Learning Research, 12, 1069-1109.
[10] Zhang, J., Zheng, K., Mou, W. and Wang, L. (2017) Efficient Private ERM for Smooth Objec- tives. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence,Melbourne, 19-25 August 2017, 3922-3928.
https://doi.org/10.24963/ijcai.2017/548
[11] Chaudhuri, K. and Monteleoni, C. (2009) Privacy-Preserving Logistic Regression. Advances in Neural Information Processing Systems, 21, 289-296.
[12] Wang, Y., Wang, Y. and Singh, A. (2015) Differentially Private Subspace Clustering. Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Pro- cessing Systems, 28, 1000-1008.
[13] Bassily, R., Smith, A. and Thakurta, A. (2014) Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, 18-21 October 2014, 464-473.
https://doi.org/10.1109/FOCS.2014.56
[14] Beimel, A., Kasiviswanathan, S. and Nissim, K. (2010) Bounds on the Sample Complexity for Private Learning and Private Data Release. In Micciancio, D., Ed., Theory of Cryptography. TCC 2010. Lecture Notes in Computer Science, Vol. 5978, Springer, Berlin, Heidelberg, 437- 454.
https://doi.org/10.1007/978-3-642-11799-2 26
[15] Williams, O. and Mcsherry, F. (2010) Probabilistic Inference and Differential Privacy. Advances in Neural Information Processing Systems, 23, 2451-2459.
[16] Wang, D., Ye, M. and Xu, J. (2017) Differentially Private Empirical Risk Minimization Revis- ited: Faster and More General. 31st Advances in Neural Information Processing Systems, 30, 2722-2731.
[17] Fan, J. and Li, R. (2001) Variable Selection via Nonconcave Penalized Likelihood and Its Oracle Properties. Journal of the American Statistical Association, 96, 1348-1360.
https://doi.org/10.1198/016214501753382273
[18] 罗孝敏, 彭定涛, 两个绝对值优化问题解的等价性[J]. 重庆工商大学学报: 自然科学版, 2020, 37(5): 37-42.
[19] Zhang, C. (2010) Nearly Unbiased Variable Selection under Minimax Concave Penalty. Annals of Statistics, 38, 894-942.
https://doi.org/10.1214/09-AOS729
[20] Ong, C. and An, L. (2013) Learning Sparse Classifiers with Difference of Convex Functions Algorithms. Optimization Methods and Software, 28, 830-854.
https://doi.org/10.1080/10556788.2011.652630
[21] Peleg, D. and Meir, R. (2008) A Bilinear Formulation for Vector Sparsity Optimization. Signal Processing, 88, 375-389.
https://doi.org/10.1016/j.sigpro.2007.08.015
[22] Thi, H., Dinh, T., Le, H. and Vo, X. (2015) DC Approximation Approaches for Sparse Opti- mization. European Journal of Operational Research, 244, 26-46.
https://doi.org/10.1016/j.ejor.2014.11.031
[23] Zhang, T. (2013) Multi-Stage Convex Relaxation for Feature Selection. Bernoulli, 19, 2277-2293.
https://doi.org/10.3150/12-BEJ452
[24] 彭定涛, 唐琦, 张弦, 组稀疏优化问题精确连续Capped-L1松弛[J]. 数学学报, 2022, 65(2):243-262.
[25] Zhang, X. and Peng, D. (2022) Solving Constrained Nonsmooth Group Sparse Optimization via Group Capped-L1 Relaxation and Group Smoothing Proximal Gradient Algorithm. Com- putational Optimization and Applications, 83, 801-844.
https://doi.org/10.1007/s10589-022-00419-2
[26] Bian, W. and Chen, X. (2017) Optimality and Complexity for Constrained Optimization Problems with Nonconvex Regularization. Mathematics of Operations Research, 42, 1063-1084.
https://doi.org/10.1287/moor.2016.0837
[27] Chartrand, R. and Staneva, V. (2008) Restricted Isometry Properties and Nonconvex Com- pressive Sensing. Inverse Problems, 24, Article 035020.
https://doi.org/10.1088/0266-5611/24/3/035020
[28] Peng, D. and Chen, X. (2020) Computation of Second-Order Directional Stationary Points for Group Sparse Optimization. Optimization Methods and Software, 35, 348-376.
https://doi.org/10.1080/10556788.2019.1684492
[29] 罗孝敏, 彭定涛, 张弦, 基于MCP正则的最小一乘回归问题研究[J]. 系统科学与数学, 2021, 41(8): 2327-2337.
[30] Gong, P. and Zhang, C. (2013) A General Iterative Shrinkage and Thresholding Algorithm for Non-Convex Regularized Optimization Problems. Proceedings of the 30th International Conference on International Conference on Machine Learning, 28, 37-45.
[31] Jain, P. and Thakurta, A. (2013) Differentially Private Learning with Kernels. Proceedings of the 30th International Conference on Machine Learning, 28, 118-126.
[32] Barzilai, J. and Borwein, J.M. (1988) Two-Point Step Size Gradient Methods. IMA Journal of Numerical Analysis, 8, 141-148.
https://doi.org/10.1093/imanum/8.1.141
[33] Dwork, C. and Roth, A. (2014) The Algorithmic Foundations of Differential Privacy. Founda- tions and Trends in Theoretical Computer Science, 9, 211-407.
https://doi.org/10.1561/0400000042
[34] 刘浩洋, 户将, 李勇锋, 文再文. 最优化: 建模、算法与理论[M]. 北京: 高教出版社, 2021.
[35] 高岩. 非光滑优化[M]. 北京: 科学出版社, 2008.

为你推荐