Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915398215008256 |
|---|---|
| author | Garrigos, Guillaume Cortild, Daniel Ketels, Lucas Peypouquet, Juan |
| author_facet | Garrigos, Guillaume Cortild, Daniel Ketels, Lucas Peypouquet, Juan |
| contents | Most results on Stochastic Gradient Descent (SGD) in the convex and smooth setting are presented under the form of bounds on the ergodic function value gap. It is an open question whether bounds can be derived directly on the last iterate of SGD in this context. Recent advances suggest that it should be possible. For instance, it can be achieved by making the additional, yet unverifiable, assumption that the variance of the stochastic gradients is uniformly bounded. In this paper, we show that there is no need of such an assumption, and that SGD enjoys a $\tilde O \left( T^{-1/2} \right)$ last-iterate complexity rate for convex smooth stochastic problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_14122 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems Garrigos, Guillaume Cortild, Daniel Ketels, Lucas Peypouquet, Juan Optimization and Control Most results on Stochastic Gradient Descent (SGD) in the convex and smooth setting are presented under the form of bounds on the ergodic function value gap. It is an open question whether bounds can be derived directly on the last iterate of SGD in this context. Recent advances suggest that it should be possible. For instance, it can be achieved by making the additional, yet unverifiable, assumption that the variance of the stochastic gradients is uniformly bounded. In this paper, we show that there is no need of such an assumption, and that SGD enjoys a $\tilde O \left( T^{-1/2} \right)$ last-iterate complexity rate for convex smooth stochastic problems. |
| title | Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2507.14122 |