Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2410.00573 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916695235362816 |
|---|---|
| author | Parletta, Daniela Angela Paudice, Andrea Salzo, Saverio |
| author_facet | Parletta, Daniela Angela Paudice, Andrea Salzo, Saverio |
| contents | In this paper, we provide novel optimal (or near optimal) convergence rates for a clipped version of the stochastic subgradient method. We consider nonsmooth convex problems over possibly unbounded domains, under heavy-tailed noise that possesses only the first $p$ moments for $p \in \left]1,2\right]$. For the last iterate, we establish convergence in expectation for the objective values with rates of order $(\log^{1/p} k)/k^{(p-1)/p}$ and $1/k^{(p-1)/p}$, for anytime and finite-horizon respectively. We also derive new convergence rates, in expectation and with high probability, for the objective values along the average iterates--improving existing results by a $\log^{(2p-1)/p} k$ factor. Those results are applied to the problem of supervised learning with kernels demonstrating the effectiveness of our theory. Finally, we give preliminary experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_00573 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Improved Analysis of the Clipped Stochastic subGradient Method under Heavy-Tailed Noise Parletta, Daniela Angela Paudice, Andrea Salzo, Saverio Optimization and Control In this paper, we provide novel optimal (or near optimal) convergence rates for a clipped version of the stochastic subgradient method. We consider nonsmooth convex problems over possibly unbounded domains, under heavy-tailed noise that possesses only the first $p$ moments for $p \in \left]1,2\right]$. For the last iterate, we establish convergence in expectation for the objective values with rates of order $(\log^{1/p} k)/k^{(p-1)/p}$ and $1/k^{(p-1)/p}$, for anytime and finite-horizon respectively. We also derive new convergence rates, in expectation and with high probability, for the objective values along the average iterates--improving existing results by a $\log^{(2p-1)/p} k$ factor. Those results are applied to the problem of supervised learning with kernels demonstrating the effectiveness of our theory. Finally, we give preliminary experiments. |
| title | An Improved Analysis of the Clipped Stochastic subGradient Method under Heavy-Tailed Noise |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2410.00573 |