{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T22:21:35Z","timestamp":1776982895816,"version":"3.51.4"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"11-12","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007156","name":"Innovation and Technology Commission - Hong Kong","doi-asserted-by":"publisher","award":["ITS\/173\/22FP"],"award-info":[{"award-number":["ITS\/173\/22FP"]}],"id":[{"id":"10.13039\/501100007156","id-type":"DOI","asserted-by":"publisher"}]},{"name":"CUHK Direct Grant for Research"},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["N_CUHK 415\/19"],"award-info":[{"award-number":["N_CUHK 415\/19"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["14300219, 14302920, 14301121"],"award-info":[{"award-number":["14300219, 14302920, 14301121"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider stochastic convex optimization for heavy-tailed data with the guarantee of being differentially private (DP). Most prior works on differentially private stochastic convex optimization for heavy-tailed data are either restricted to gradient descent (GD) or performed multi-times clipping on stochastic gradient descent (SGD), which is inefficient for large-scale problems. In this paper, we consider a one-time clipping strategy and provide principled analyses of its bias and private mean estimation. We establish new convergence results and improved complexity bounds for the proposed algorithm called AClipped-dpSGD for constrained and unconstrained convex problems. We also extend our convergent analysis to the strongly convex case and non-smooth case (which works for generalized smooth objectives with H<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ddot{\\text {o}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mover>\n                    <mml:mtext>o<\/mml:mtext>\n                    <mml:mo>\u00a8<\/mml:mo>\n                  <\/mml:mover>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>lder-continuous gradients). All the above results are guaranteed with a high probability for heavy-tailed data. Numerical experiments are conducted to justify the theoretical improvement.<\/jats:p>","DOI":"10.1007\/s10994-024-06617-9","type":"journal-article","created":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T20:27:36Z","timestamp":1727728056000},"page":"8487-8532","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient private SCO for heavy-tailed data via averaged clipping"],"prefix":"10.1007","volume":"113","author":[{"given":"Chenhan","family":"Jin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaiwen","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tieyong","family":"Zeng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,30]]},"reference":[{"key":"6617_CR1","doi-asserted-by":"crossref","unstructured":"Abadi, M., Chu, A., Goodfellow, I., et\u00a0al. (2016). Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp 308\u2013318.","DOI":"10.1145\/2976749.2978318"},{"key":"6617_CR2","unstructured":"Asi, H., Feldman, V., Koren, T., et\u00a0al. (2021). Private stochastic convex optimization: Optimal rates in l1 geometry. InInternational Conference on Machine Learning, PMLR, pp 393\u2013403."},{"key":"6617_CR3","doi-asserted-by":"crossref","unstructured":"Bassily, R., Feldman, V., Talwar, K., et\u00a0al. (2019). Private stochastic convex optimization with optimal rates. Advances in Neural Information Processing Systems.","DOI":"10.1145\/3357713.3384335"},{"key":"6617_CR4","unstructured":"Bassily, R., Guzm\u00e1n, C., & Nandi, A. (2021). Non-euclidean differentially private stochastic convex optimization. arXiv preprint arXiv:2103.01278."},{"key":"6617_CR5","doi-asserted-by":"crossref","unstructured":"Bassily, R., Smith, A., & Thakurta, A. (2014). Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, IEEE, pp 464\u2013473.","DOI":"10.1109\/FOCS.2014.56"},{"issue":"6","key":"6617_CR6","doi-asserted-by":"publisher","first-page":"2507","DOI":"10.1214\/15-AOS1350","volume":"43","author":"C Brownlees","year":"2015","unstructured":"Brownlees, C., Joly, E., Lugosi, G., et al. (2015). Empirical risk minimization for heavy-tailed losses. Annals of Statistics, 43(6), 2507\u20132536.","journal-title":"Annals of Statistics"},{"key":"6617_CR7","unstructured":"Bun, M., & Steinke, T. (2019). Average-case averages: Private algorithms for smooth sensitivity and mean estimation. arXiv preprint arXiv:1906.02830."},{"issue":"3","key":"6617_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1961189.1961199","volume":"2","author":"CC Chang","year":"2011","unstructured":"Chang, C. C., & Lin, C. J. (2011). Libsvm: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3), 1\u201327.","journal-title":"ACM Transactions on Intelligent Systems and Technology (TIST)"},{"issue":"4","key":"6617_CR9","doi-asserted-by":"publisher","first-page":"1495","DOI":"10.1088\/0266-5611\/23\/4\/008","volume":"23","author":"C Chaux","year":"2007","unstructured":"Chaux, C., Combettes, P. L., Pesquet, J. C., et al. (2007). A variational formulation for frame-based inverse problems. Inverse Problems, 23(4), 1495.","journal-title":"Inverse Problems"},{"key":"6617_CR10","doi-asserted-by":"crossref","unstructured":"Cohen, J.E., Davis, R.A., & Samorodnitsky, G. (2020). Heavy-tailed distributions, correlations, Kurtosis and Taylor\u2019s law of fluctuation scaling. In Proceedings of the Royal Society A 476(2244):20200,610.","DOI":"10.1098\/rspa.2020.0610"},{"key":"6617_CR11","unstructured":"Das R, Kale S, Xu Z, et\u00a0al (2023) Beyond uniform lipschitz condition in differentially private optimization. In International Conference on Machine Learning, PMLR, pp 7066\u20137101."},{"key":"6617_CR12","unstructured":"Ding, B., Kulkarni, J., & Yekhanin, S. (2017). Collecting telemetry data privately. arXiv:1712.01524."},{"issue":"1","key":"6617_CR13","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s10957-016-0999-6","volume":"171","author":"P Dvurechensky","year":"2016","unstructured":"Dvurechensky, P., & Gasnikov, A. (2016). Stochastic intermediate gradient method for convex problems with stochastic inexact oracle. Journal of Optimization Theory and Applications, 171(1), 121\u2013145.","journal-title":"Journal of Optimization Theory and Applications"},{"key":"6617_CR14","doi-asserted-by":"crossref","unstructured":"Dwork, C., McSherry, F., Nissim, K., et\u00a0al. (2006). Calibrating noise to sensitivity in private data analysis. TCC.","DOI":"10.1007\/11681878_14"},{"issue":"3\u20134","key":"6617_CR15","first-page":"211","volume":"9","author":"C Dwork","year":"2014","unstructured":"Dwork, C., Roth, A., et al. (2014). The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3\u20134), 211\u2013407.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"issue":"1","key":"6617_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0304-4149(00)00086-7","volume":"93","author":"K Dzhaparidze","year":"2001","unstructured":"Dzhaparidze, K., & Van Zanten, J. (2001). On Bernstein-type inequalities for martingales. Stochastic Processes and their Applications, 93(1), 109\u2013117.","journal-title":"Stochastic Processes and their Applications"},{"key":"6617_CR17","doi-asserted-by":"crossref","unstructured":"Feldman, V., Koren, T., & Talwar, K. (2020). Private stochastic convex optimization: optimal rates in linear time. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp 439\u2013449.","DOI":"10.1145\/3357713.3384335"},{"key":"6617_CR18","doi-asserted-by":"crossref","unstructured":"Freedman, D.A. (1975). On tail probabilities for martingales. Ihe Annals of Probability pp 100\u2013118.","DOI":"10.1214\/aop\/1176996452"},{"issue":"4","key":"6617_CR19","doi-asserted-by":"publisher","first-page":"1469","DOI":"10.1137\/110848864","volume":"22","author":"S Ghadimi","year":"2012","unstructured":"Ghadimi, S., & Lan, G. (2012). Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4), 1469\u20131492.","journal-title":"SIAM Journal on Optimization"},{"issue":"4","key":"6617_CR20","doi-asserted-by":"publisher","first-page":"2061","DOI":"10.1137\/110848876","volume":"23","author":"S Ghadimi","year":"2013","unstructured":"Ghadimi, S., & Lan, G. (2013). Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii: Shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23(4), 2061\u20132089.","journal-title":"SIAM Journal on Optimization"},{"key":"6617_CR21","unstructured":"Gorbunov, E., Danilova, M., Shibaev, I., et\u00a0al. (2021). Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy-tailed noise. arXiv preprint arXiv:2106.05958."},{"key":"6617_CR22","first-page":"15042","volume":"33","author":"E Gorbunov","year":"2020","unstructured":"Gorbunov, E., Danilova, M., & Gasnikov, A. (2020). Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33, 15042\u201315053.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6617_CR23","unstructured":"Holland, M.J. (2019). Robust descent using smoothed multiplicative noise. In The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, pp 703\u2013711."},{"key":"6617_CR24","doi-asserted-by":"crossref","unstructured":"Hu, L., Ni, S., Xiao, H., et\u00a0al. (2022). High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp 227\u2013236.","DOI":"10.1145\/3517804.3524144"},{"key":"6617_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16877-7","volume-title":"Heavy-tailed distributions and robustness in economics and finance,","author":"M Ibragimov","year":"2015","unstructured":"Ibragimov, M., Ibragimov, R., & Walden, J. (2015). Heavy-tailed distributions and robustness in economics and finance, (Vol. 214). Springer."},{"key":"6617_CR26","unstructured":"Jin, C., Netrapalli, P., Ge, R., et\u00a0al. (2019). A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.03736."},{"issue":"9","key":"6617_CR27","doi-asserted-by":"publisher","first-page":"121","DOI":"10.7551\/mitpress\/8996.003.0007","volume":"30","author":"A Juditsky","year":"2011","unstructured":"Juditsky, A., Nemirovski, A., et al. (2011). First order methods for nonsmooth convex large-scale optimization, i: General purpose methods. Optimization for Machine Learning, 30(9), 121\u2013148.","journal-title":"Optimization for Machine Learning"},{"key":"6617_CR28","unstructured":"Kamath, G., Liu, X., & Zhang, H. (2022). Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In International Conference on Machine Learning, PMLR, pp 10,633\u201310,660."},{"key":"6617_CR29","unstructured":"Kamath, G., Singhal, V., & Ullman, J. (2020). Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory, PMLR, pp 2204\u20132235."},{"key":"6617_CR30","unstructured":"Kasiviswanathan, S.P., & Jin, H. (2016). Efficient private empirical risk minimization for high-dimensional learning. In International Conference on Machine Learning, PMLR, pp 488\u2013497."},{"key":"6617_CR31","unstructured":"Lowy, A., & Razaviyayn, M. (2023). Private stochastic optimization with large worst-case lipschitz parameter: Optimal rates for (non-smooth) convex losses and extension to non-convex losses. In International Conference on Algorithmic Learning Theory, PMLR, pp 986\u20131054."},{"issue":"5","key":"6617_CR32","doi-asserted-by":"publisher","first-page":"1145","DOI":"10.1007\/s10208-019-09427-x","volume":"19","author":"G Lugosi","year":"2019","unstructured":"Lugosi, G., & Mendelson, S. (2019). Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19(5), 1145\u20131190.","journal-title":"Foundations of Computational Mathematics"},{"key":"6617_CR33","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on convex optimization","author":"Y Nesterov","year":"2018","unstructured":"Nesterov, Y. (2018). Lectures on convex optimization (Vol. 137). Springer."},{"key":"6617_CR34","doi-asserted-by":"crossref","unstructured":"Papernot, N., Thakurta, A., Song, S., et\u00a0al. (2021). Tempered sigmoid activations for deep learning with differential privacy. In Proceedings of the AAAI Conference on Artificial Intelligence, pp 9312\u20139321.","DOI":"10.1609\/aaai.v35i10.17123"},{"key":"6617_CR35","unstructured":"Song, S., Steinke, T., Thakkar, O., et\u00a0al. (2021). Evading the curse of dimensionality in unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, PMLR, pp 2638\u20132646."},{"key":"6617_CR36","unstructured":"Talwar, K., Thakurta, A., & Zhang, L. (2015). Nearly-optimal private lasso. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 2, pp 3025\u20133033."},{"key":"6617_CR37","unstructured":"Tang, J., Korolova, A., Bai, X., et\u00a0al. (2017). Privacy loss in apple\u2019s implementation of differential privacy on macos 10.12. arXiv preprint arXiv:1709.02753."},{"key":"6617_CR38","doi-asserted-by":"crossref","unstructured":"Tao, Y., Wu, Y., Cheng, X., et\u00a0al. (2022). Private stochastic convex optimization and sparse learning with heavy-tailed data revisited. IJCAI, pp 3947\u20133953.","DOI":"10.24963\/ijcai.2022\/548"},{"key":"6617_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2440-0","volume-title":"The nature of statistical learning theory","author":"VN Vapnik","year":"1995","unstructured":"Vapnik, V. N. (1995). The nature of statistical learning theory. Springer."},{"key":"6617_CR40","unstructured":"Wang, D., Ding, J., Xie, Z., et\u00a0al. (2020a). Differentially private (gradient) expectation maximization algorithm with statistical guarantees. arXiv preprint arXiv:2010.13520."},{"key":"6617_CR41","unstructured":"Wang, D., Gaboardi, M., & Xu, J. (2018). Empirical risk minimization in non-interactive local differential privacy revisited. In Proc. 32nd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS 2018)."},{"key":"6617_CR42","unstructured":"Wang, D., Xiao, H., Devadas, S., et\u00a0al. (2020b). On differentially private stochastic convex optimization with heavy-tailed data. In International Conference on Machine Learning, PMLR, pp 10,081\u201310,091."},{"key":"6617_CR43","unstructured":"Wang, D., Ye, M., & Xu, J. (2017). Differentially private empirical risk minimization revisited: Faster and more general. In Proc. 31st Annual Conference on Advances in Neural Information Processing Systems (NIPS 2017)."},{"key":"6617_CR44","first-page":"1207","volume-title":"Estimating smooth glm in non-interactive local differential privacy model with public unlabeled data","author":"D Wang","year":"2021","unstructured":"Wang, D., Zhang, H., Gaboardi, M., et al. (2021). Estimating smooth glm in non-interactive local differential privacy model with public unlabeled data (pp. 1207\u20131213). PMLR: Algorithmic Learning Theory."},{"key":"6617_CR45","doi-asserted-by":"crossref","unstructured":"Zhang, J., Zheng, K., Mou W., et\u00a0al. (2017). Efficient private erm for smooth objectives. arXiv preprint arXiv:1703.09947.","DOI":"10.24963\/ijcai.2017\/548"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-024-06617-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-024-06617-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-024-06617-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,30]],"date-time":"2024-12-30T16:07:33Z","timestamp":1735574853000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-024-06617-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":45,"journal-issue":{"issue":"11-12","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["6617"],"URL":"https:\/\/doi.org\/10.1007\/s10994-024-06617-9","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,30]]},"assertion":[{"value":"22 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}