Parletta, Daniela Angela; Paudice, Andrea; Pontil, Massimiliano; Salzo, Saverio; (2024) High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise. SIAM Journal on Mathematics of Data Science , 6 (4) pp. 953-977. 10.1137/22M1536558.

Preview

Text 22m1536558.pdf - Published Version Download (672kB) | Preview

Abstract

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.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as XMLCSVJSON

Downloads by country - last 12 months

Export as CSVXMLJSON

Archive Staff Only

View Item