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.
| Type: | Article |
|---|---|
| Title: | High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1137/22M1536558 |
| Publisher version: | https://doi.org/10.1137/22m1536558 |
| Language: | English |
| Additional information: | This version is the version of record. For information on re-use, please refer to the publisher's terms and conditions. |
| Keywords: | stochastic convex optimization, high-probability bounds, subgradient method, heavy tailed noise |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10211859 |
Archive Staff Only
 |
View Item |
