×

Differentially private accelerated optimization algorithms. (English) Zbl 07534674

Summary: We present two classes of differentially private optimization algorithms derived from the well-known accelerated first-order methods. The first algorithm is inspired by Polyak’s heavy ball method and employs a smoothing approach to decrease the accumulated noise on the gradient steps required for differential privacy. The second class of algorithms are based on Nesterov’s accelerated gradient method and its recent multistage variant. We propose a noise dividing mechanism for the iterations of Nesterov’s method in order to improve the error behavior of the algorithm. The convergence rate analyses are provided for both the heavy ball and the Nesterov’s accelerated gradient method with the help of the dynamical system analysis techniques. Finally, we conclude with our numerical experiments showing that the presented algorithms have advantages over the well-known differentially private algorithms.

MSC:

68P27 Privacy of data
90C30 Nonlinear programming
90C25 Convex programming

Software:

PrivateLR
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, Deep learning with differential privacy, in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, ACM, 2016, pp. 308-318.
[2] N. S. Aybat, A. Fallah, M. Gürbüzbalaban, and A. Ozdaglar, A universally optimal multistage accelerated stochastic gradient method, in Advances in Neural Information Processing Systems, 2019, pp. 8525-8536.
[3] N. S. Aybat, A. Fallah, M. Gürbüzbalaban, and A. Ozdaglar, Robust accelerated gradient methods for smooth strongly convex functions, SIAM J. Optim., 30 (2020), pp. 717-751, https://doi.org/10.1137/19M1244925. · Zbl 1461.62145
[4] B. Balle, G. Barthe, and M. Gaboardi, Privacy amplification by subsampling: Tight analyses via couplings and divergences, in Advances in Neural Information Processing Systems, 2018, pp. 6277-6287.
[5] R. Bassily, A. Smith, and A. Thakurta, Private empirical risk minimization: Efficient algorithms and tight error bounds, in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, IEEE, 2014, pp. 464-473.
[6] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183-202, https://doi.org/10.1137/080716542. · Zbl 1175.94009
[7] M. Bun and T. Steinke, Concentrated differential privacy: Simplifications, extensions, and lower bounds, in Proceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 9985, Springer-Verlag, New York, 2016, pp. 635-658. · Zbl 1406.94030
[8] B. Can, M. Gürbüzbalaban, and L. Zhu, Accelerated linear convergence of stochastic momentum methods in Wasserstein distances, in Proceedings of the 36th International Conference on Machine Learning, 2019.
[9] K. Chaudhuri and C. Monteleoni, Privacy-preserving logistic regression, in Advances in Neural Information Processing Systems, 2009, pp. 289-296.
[10] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, Differentially private empirical risk minimization, J. Mach. Learn. Res., 12 (2011), pp. 1069-1109. · Zbl 1280.62073
[11] C. Dwork, Differential privacy, in 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), Part II, 2006, Springer-Verlag. · Zbl 1133.68330
[12] C. Dwork, Differential privacy: A survey of results, in International Conference on Theory and Applications of Models of Computation, Springer, 2008, pp. 1-19. · Zbl 1139.68339
[13] C. Dwork and A. Roth, The algorithmic foundations of differential privacy, Found. Trends Theor. Comput. Sci., 9 (2014), pp. 211-407. · Zbl 1302.68109
[14] C. Dwork and G. N. Rothblum, Concentrated Differential Privacy, preprint, https://arxiv.org/abs/1603.01887, 2016.
[15] C. Dwork, G. N. Rothblum, and S. Vadhan, Boosting and differential privacy, in 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2010, pp. 51-60.
[16] M. Fazlyab, A. Ribeiro, M. Morari, and V. M. Preciado, Analysis of optimization algorithms via integral quadratic constraints: Nonstrongly convex problems, SIAM J. Optim., 28 (2018), pp. 2654-2689, https://doi.org/10.1137/17M1136845. · Zbl 1406.90089
[17] O. Fercoq and Z. Qu, Adaptive restart of accelerated gradient methods under local quadratic growth condition, IMA J. Numer. Anal., 39 (2019), pp. 2069-2095. · Zbl 07130820
[18] N. Flammarion and F. Bach, From averaging to acceleration, there is only a step-size, in Proceedings of the 28th Conference on Learning Theory, PMLR 40, 2015, pp. 658-695.
[19] J. Foulds, J. Geumlek, M. Welling, and K. Chaudhuri, On the theory and practice of privacy-preserving Bayesian data analysis, in Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, UAI’16, Arlington, VA, 2016, AUAI Press, pp. 192-201.
[20] S. Gadat, F. Panloup, and S. Saadane, Stochastic heavy ball, Electron. J. Stat., 12 (2018), pp. 461-529. · Zbl 1392.62244
[21] B. Hu and L. Lessard, Dissipativity theory for Nesterov’s accelerated method, in Proceedings of the 34th International Conference on Machine Learning-Volume 70, JMLR.org, 2017, pp. 1549-1557.
[22] S. L. Hyland and S. Tople, On the Intrinsic Privacy of Stochastic Gradient Descent, preprint, https://arxiv.org/abs/1912.02919, 2019.
[23] B. Jayaraman, L. Wang, D. Evans, and Q. Gu, Distributed learning without distress: Privacy-preserving empirical risk minimization, in Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, Curran Associates Inc., Red Hook, NY, 2018, pp. 6346-6357.
[24] D. Kifer, A. Smith, and A. Thakurta, Private convex empirical risk minimization and high-dimensional regression, in Proceedings of the 25th Conference on Learning Theory, PMLR 23, 2012, pp. 25.1-25.40.
[25] G. Lan, First-order and Stochastic Optimization Methods for Machine Learning, Springer, 2020. · Zbl 1442.68003
[26] L. Lessard, B. Recht, and A. Packard, Analysis and design of optimization algorithms via integral quadratic constraints, SIAM J. Optim., 26 (2016), pp. 57-95, https://doi.org/10.1137/15M1009597. · Zbl 1329.90103
[27] N. Loizou and P. Richtárik, Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods, Comput. Optim. Appl., 77 (2020), pp. 653-710. · Zbl 1466.90065
[28] I. Mironov, Rényi differential privacy, in 2017 IEEE 30th Computer Security Foundations Symposium (CSF), 2017, pp. 263-275.
[29] H. Mohammadi, M. Razaviyayn, and M. R. Jovanović, Robustness of accelerated first-order algorithms for strongly convex optimization problems, IEEE Trans. Automat. Control, 66 (2021), pp. 2480-2495. · Zbl 1467.93334
[30] Y. Nesterov, A method of solving a convex programming problem with convergence rate \(O(1/k^2)\), Soviet Math. Dokl., 27 (1983), pp. 372-376. · Zbl 0535.90071
[31] M. Park, J. Foulds, K. Chaudhuri, and M. Welling, Variational Bayes in private settings (VIPS), J. Artificial Intelligence Res., 68 (2020), pp. 109-157. · Zbl 1452.62986
[32] V. Pichapati, A. T. Suresh, F. X. Yu, S. J. Reddi, and S. Kumar, AdaCliP: Adaptive Clipping for Private SGD, preprint, https://arxiv.org/abs/1908.07643, 2019.
[33] B. T. Polyak, Some methods of speeding up the convergence of iteration methods, U.S.S.R. Comput. Math. and Math. Phys., 4 (1964), pp. 1-17. · Zbl 0147.35301
[34] B. T. Polyak, Introduction to Optimization, Vol. 1, Optimization Software, Publications Division, New York, 1987. · Zbl 0708.90083
[35] A. Ramezani-Kebrya, A. Khisti, and B. Liang, On the Stability and Convergence of Stochastic Gradient Descent with Momentum, preprint, https://arxiv.org/abs/1809.04564, 2018.
[36] B. I. P. Rubinstein, P. L. Bartlett, L. Huang, and N. Taft, Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning, preprint, https://arxiv.org/abs/0911.5708, 2009.
[37] M. Schmidt, R. Babanezhad, M. Ahmed, A. Defazio, A. Clifton, and A. Sarkar, Non-uniform stochastic average gradient method for training conditional random fields, in Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38, 2015, pp. 819-828.
[38] R. Shokri and V. Shmatikov, Privacy-preserving deep learning, in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, ACM, 2015, pp. 1310-1321.
[39] S. Song, O. Thakkar, and A. Thakurta, Characterizing Private Clipped Gradient Descent on Convex Generalized Linear Problems, preprint, https://arxiv.org/abs/2006.06783, 2020.
[40] V. Vapnik, The Nature of Statistical Learning Theory, Springer Science & Business Media, 2013. · Zbl 0833.62008
[41] D. Wang, M. Ye, and J. Xu, Differentially private empirical risk minimization revisited: Faster and more general, in Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, Red Hook, NY, Curran Associates Inc., 2017, pp. 2719-2728.
[42] L. Wang and Q. Gu, Differentially private iterative gradient hard thresholding for sparse learning, in Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI’19, AAAI Press, 2019, pp. 3740-3747.
[43] Y. Yan, T. Yang, Z. Li, Q. Lin, and Y. Yang, A Unified Analysis of Stochastic Momentum Methods for Deep Learning, preprint, https://arxiv.org/abs/1808.10396, 2018.
[44] T. Yang, Q. Lin, and Z. Li, Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization, preprint, https://arxiv.org/abs/1604.03257, 2016.
[45] L. Yu, L. Liu, C. Pu, M. E. Gursoy, and S. Truex, Differentially private model publishing for deep learning, in 2019 IEEE Symposium on Security and Privacy (SP), IEEE, 2019, pp. 332-349.
[46] J. Zhang, Z. Zhang, X. Xiao, Y. Yang, and M. Winslett, Functional mechanism: Regression analysis under differential privacy, Proc. VLDB Endow., 5 (2012), pp. 1364-1375.
[47] J. Zhang, K. Zheng, W. Mou, and L. Wang, Efficient Private ERM for Smooth Objectives, preprint, https://arxiv.org/abs/1703.09947, 2017.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.