{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:41:08Z","timestamp":1787330468591,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Journal on Mathematics of Data Science"],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>In this work we study high-probability bounds for stochastic subgradient methods under heavy tailed noise in Hilbert spaces. In this setting the noise is only assumed to have finite variance as opposed to a sub-Gaussian distribution for which it is known that standard subgradient methods enjoy high-probability bounds. We analyzed a clipped version of the projected stochastic subgradient method, where subgradient estimates are truncated whenever they have large norms. We show that this clipping strategy leads both to optimal anytime and finite horizon bounds for general averaging schemes of the iterates. We also show an application of our proposal to the case of kernel methods which gives an efficient and fully implementable algorithm for statistical supervised learning problems. Preliminary experiments are shown to support the validity of the method.<\/jats:p>","DOI":"10.1137\/22m1536558","type":"journal-article","created":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T07:12:19Z","timestamp":1728544339000},"page":"953-977","source":"Crossref","is-referenced-by-count":0,"title":["High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise"],"prefix":"10.1137","volume":"6","author":[{"given":"Daniela Angela","family":"Parletta","sequence":"first","affiliation":[{"name":"CSML at Istituto Italiano di Tecnologia, 16163 Genova, Italy, and Department of Mathematics at University of Genoa, 16146 Genoa, Italy."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1098-662X","authenticated-orcid":true,"given":"Andrea","family":"Paudice","sequence":"additional","affiliation":[{"name":"Department of Computer Science at University of Milan, 20122 Milan, Italy."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Massimiliano","family":"Pontil","sequence":"additional","affiliation":[{"name":"CSML at Istituto Italiano di Tecnologia, 16163 Genova, Italy, and Department of Computer Science at UCL, London NW1 2AE, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0494-9101","authenticated-orcid":true,"given":"Saverio","family":"Salzo","sequence":"additional","affiliation":[{"name":"CSML at Istituto Italiano di Tecnologia, 16163 Genova, Italy, and DIAG at Sapienza University of Rome, 00185 Rome, Italy."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,10,10]]},"reference":[{"key":"ref1","volume-title":"Nonlinear Programming","author":"Bertsekas D. P.","year":"1999"},{"key":"ref2","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s10208-006-0196-8","volume":"7","author":"Caponnetto A.","year":"2007","journal-title":"Found. Comput. Math."},{"key":"ref3","unstructured":"A. Cutkosky, Anytime online-to-batch, optimism and acceleration, in Proceedings of the 36th International Conference on Machine Learning, 2019, pp. 1446\u20131454."},{"key":"ref4","first-page":"49","volume":"22","author":"Davis D.","year":"2021","journal-title":"J. Mach. Learn. Res."},{"key":"ref5","doi-asserted-by":"crossref","first-page":"1363","DOI":"10.1214\/15-AOS1391","volume":"44","author":"Dieuleveut A.","year":"2016","journal-title":"Ann. Statist."},{"key":"ref6","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/BF01071091","volume":"5","author":"Ermol\u2019ev Y. M.","year":"1969","journal-title":"Cybernetics"},{"key":"ref7","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1214\/aop\/1176996452","volume":"3","author":"Freedman D. A.","year":"1975","journal-title":"Ann. Probab."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/110848876"},{"key":"ref9","unstructured":"E. Gorbunov, M. Danilova, and A. Gasnikov, Stochastic optimization with heavy-tailed noise via accelerated gradient clipping, in Proceedings of the 34th Annual Conference on Neural Information Processing Systems, 2020, pp. 15042\u201315053."},{"key":"ref10","unstructured":"E. Gorbunov, M. Danilova, I. Shibaev, P. Dvurechensky, and A. Gasnikov, Near-optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise, preprint, https:\/\/arxiv.org\/abs\/2106.05958, 2021."},{"key":"ref11","unstructured":"N. J. Harvey, C. Liaw, Y. Plan, and S. Randhawa, Tight analyses for non-smooth stochastic gradient descent, in Proceedinds of the 32nd International Conference on Computational Learning Theory, 2019, pp. 1579\u20131613."},{"key":"ref12","unstructured":"N. J. Harvey, C. Liaw, and S. Randhawa, Simple and Optimal High-Probability Bounds for Strongly-Convex Stochastic Gradient Descent, preprint, https:\/\/arxiv.org\/abs\/1909.00843, 2019."},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"M. J. Holland, Anytime guarantees under heavy-tailed data, in Proceedings of the 36th AAAI Conference on Artificial Intelligence, 2022, pp. 6918\u20136925.","DOI":"10.1609\/aaai.v36i6.20649"},{"key":"ref14","unstructured":"P. Jain, D. Nagaraj, and P. Netrapalli, Making the last iterate of SGD information theoretically optimal, in Proceedinds of the 32nd International Conference on Computational Learning Theory, 2019, pp. 1752\u20131755."},{"key":"ref15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-39568-1","volume-title":"First-order and Stochastic Optimization Methods for Machine Learning","volume":"1","author":"Lan G.","year":"2020"},{"key":"ref16","unstructured":"J. Lin, R. Camoriano, and L. Rosasco, Generalization properties and implicit regularization for multiple passes SGM, in International Conference on Machine Learning, PMLR, 2016, pp. 2340\u20132348."},{"key":"ref17","first-page":"1","volume":"18","author":"Lin J.","year":"2017","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref18","doi-asserted-by":"crossref","first-page":"1607","DOI":"10.1134\/S0005117919090042","volume":"80","author":"Nazin A. V.","year":"2019","journal-title":"Automat. Remote Control"},{"key":"ref19","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovskij A. S.","year":"1983"},{"key":"ref20","first-page":"5","volume":"3","author":"Poljak B. T.","year":"1978","journal-title":"Nonsmooth Optim."},{"key":"ref21","first-page":"593","volume":"8","author":"Polyak B. T.","year":"1967","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"ref22","unstructured":"P. Richt\u00e1rik, I. Sokolov, and I. Fatkhullin, Ef21: A new, simpler, theoretically better, and practically faster error feedback, in Proceedings of the 34th Annual Conference on Neural Information Processing Systems, 2021, pp. 4384\u20134396."},{"key":"ref23","unstructured":"O. Shamir and T. Zhang, Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes, in Proceedings of the 30th International Conference on Machine Learning, 2013, pp. 71\u201379."},{"key":"ref24","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-82118-9","volume-title":"Minimization Methods for Non-differentiable Functions","author":"Shor N. Z.","year":"1985"},{"key":"ref25","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-77242-4","volume-title":"Support Vector Machines","author":"Steinwart I.","year":"2008"},{"key":"ref26","unstructured":"I. Steinwart, D. R. Hush, and C. Scovel, Optimal rates for regularized least squares regression, in Proceedings of the 22nd Conference on Learning Theory, 2009, pp. 79\u201393."},{"key":"ref27","unstructured":"J. Zhang, S. P. Karimireddy, A. Veit, S. Kim, S. Reddi, S. Kumar, and S. Sra, Why are adaptive methods good for attention models? in Proceedings of the 34th Annual Conference on Neural Information Processing Systems, 2020, pp. 15383\u201315393."}],"container-title":["SIAM Journal on Mathematics of Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1536558","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:07:34Z","timestamp":1787328454000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1536558"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,10]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1137\/22M1536558"],"URL":"https:\/\/doi.org\/10.1137\/22m1536558","relation":{},"ISSN":["2577-0187"],"issn-type":[{"value":"2577-0187","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,10]]}}}