Revisiting Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911523836788736 |
|---|---|
| author | Chen, Kang Feng, Yasong Wang, Tianyu |
| author_facet | Chen, Kang Feng, Yasong Wang, Tianyu |
| contents | Stochastic optimization via Stochastic Gradient Descent (SGD) is a fundamental problem in statistics and optimization. This paper revisits Stochastic Gradient Descent (SGD) for strongly convex objectives, establishing tight, uniform-in-time convergence bounds. We prove that, with probability at least $1 - β$, a convergence rate of order $\frac{\log \log k + \log (1/β)}{k}$ simultaneously holds for all $ k \in \mathbb{N}_+ $, and demonstrate this bound is tight up to constant factors. We also provide an improved last-iterate convergence rate for such objectives. While focused on strongly convex objectives, our results generalize to the Polyak-Łojasiewicz functions and indicate an $\mathcal{O}(k^{-1} \log \log k)$ convergence rate for contractive stochastic approximation with additive noise. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20823 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Revisiting Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds Chen, Kang Feng, Yasong Wang, Tianyu Optimization and Control Stochastic optimization via Stochastic Gradient Descent (SGD) is a fundamental problem in statistics and optimization. This paper revisits Stochastic Gradient Descent (SGD) for strongly convex objectives, establishing tight, uniform-in-time convergence bounds. We prove that, with probability at least $1 - β$, a convergence rate of order $\frac{\log \log k + \log (1/β)}{k}$ simultaneously holds for all $ k \in \mathbb{N}_+ $, and demonstrate this bound is tight up to constant factors. We also provide an improved last-iterate convergence rate for such objectives. While focused on strongly convex objectives, our results generalize to the Polyak-Łojasiewicz functions and indicate an $\mathcal{O}(k^{-1} \log \log k)$ convergence rate for contractive stochastic approximation with additive noise. |
| title | Revisiting Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2508.20823 |