Convergence and concentration properties of constant step-size SGD through Markov chains
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911279004778496 |
|---|---|
| author | Merad, Ibrahim Gaïffas, Stéphane |
| author_facet | Merad, Ibrahim Gaïffas, Stéphane |
| contents | We consider the optimization of a smooth and strongly convex objective using constant step-size stochastic gradient descent (SGD) and study its properties through the prism of Markov chains. We show that, for unbiased gradient estimates with mildly controlled variance, the iteration converges to an invariant distribution in total variation distance. We also establish this convergence in Wasserstein-2 distance under a relaxed assumption on the gradient noise distribution compared to previous work. Our analysis shows that the SGD iterates and their invariant limit distribution \emph{inherit} sub-Gaussian or sub-exponential concentration properties when these hold true for the gradient. This allows the derivation of high-confidence bounds for the final estimate. Finally, under such conditions in the linear case, we obtain a dimension-free deviation bound for the Polyak-Ruppert average of a tail sequence. All our results are non-asymptotic and their consequences are discussed through a few applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_11497 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Convergence and concentration properties of constant step-size SGD through Markov chains Merad, Ibrahim Gaïffas, Stéphane Machine Learning Optimization and Control We consider the optimization of a smooth and strongly convex objective using constant step-size stochastic gradient descent (SGD) and study its properties through the prism of Markov chains. We show that, for unbiased gradient estimates with mildly controlled variance, the iteration converges to an invariant distribution in total variation distance. We also establish this convergence in Wasserstein-2 distance under a relaxed assumption on the gradient noise distribution compared to previous work. Our analysis shows that the SGD iterates and their invariant limit distribution \emph{inherit} sub-Gaussian or sub-exponential concentration properties when these hold true for the gradient. This allows the derivation of high-confidence bounds for the final estimate. Finally, under such conditions in the linear case, we obtain a dimension-free deviation bound for the Polyak-Ruppert average of a tail sequence. All our results are non-asymptotic and their consequences are discussed through a few applications. |
| title | Convergence and concentration properties of constant step-size SGD through Markov chains |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2306.11497 |