On the Convergence of HalpernSGD
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917357561053184 |
|---|---|
| author | Colao, Vittorio Foglia, Katherine Rossella |
| author_facet | Colao, Vittorio Foglia, Katherine Rossella |
| contents | We study a stochastic anchored gradient scheme, namely HalpernSGD, which combines the classical Halpern iteration for finding a minimizer of a convex and $L$-smooth objective function with a stochastic {first-order} oracle. The algorithm is simple and does not require projections, line-search, or similar techniques. This provides, to the best of our knowledge, the first almost sure convergence guarantee for a Halpern-type stochastic gradient scheme, without requiring variance reduction or multi-point oracle mechanisms. Under standard stepsize assumptions, we prove that the iterates converge almost surely to the anchor-selected minimizer $x^*=P_S(u)$. In addition, for a natural choice of the step sequences, we derive a sublinear asymptotic estimate for the expected optimality gap, namely \( \liminf_{n\to\infty}\sqrt{n+1}\,\mathbb{E}\bigl[f(X_n)-f(x^*)\bigr]=0. \) As shown, a full last iterate rate estimate cannot be reached in the present setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_18906 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Convergence of HalpernSGD Colao, Vittorio Foglia, Katherine Rossella Optimization and Control 90C25, 62L20, 65K10, 47H09, 47J26, 47H10, 90C15 We study a stochastic anchored gradient scheme, namely HalpernSGD, which combines the classical Halpern iteration for finding a minimizer of a convex and $L$-smooth objective function with a stochastic {first-order} oracle. The algorithm is simple and does not require projections, line-search, or similar techniques. This provides, to the best of our knowledge, the first almost sure convergence guarantee for a Halpern-type stochastic gradient scheme, without requiring variance reduction or multi-point oracle mechanisms. Under standard stepsize assumptions, we prove that the iterates converge almost surely to the anchor-selected minimizer $x^*=P_S(u)$. In addition, for a natural choice of the step sequences, we derive a sublinear asymptotic estimate for the expected optimality gap, namely \( \liminf_{n\to\infty}\sqrt{n+1}\,\mathbb{E}\bigl[f(X_n)-f(x^*)\bigr]=0. \) As shown, a full last iterate rate estimate cannot be reached in the present setting. |
| title | On the Convergence of HalpernSGD |
| topic | Optimization and Control 90C25, 62L20, 65K10, 47H09, 47J26, 47H10, 90C15 |
| url | https://arxiv.org/abs/2601.18906 |