The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915332663279616 |
|---|---|
| author | Azizian, Waïss Iutzeler, Franck Malick, Jérôme Mertikopoulos, Panayotis |
| author_facet | Azizian, Waïss Iutzeler, Franck Malick, Jérôme Mertikopoulos, Panayotis |
| contents | In this paper, we examine the time it takes for stochastic gradient descent (SGD) to reach the global minimum of a general, non-convex loss function. We approach this question through the lens of randomly perturbed dynamical systems and large deviations theory, and we provide a tight characterization of the global convergence time of SGD via matching upper and lower bounds. These bounds are dominated by the most "costly" set of obstacles that the algorithm may need to overcome in order to reach a global minimizer from a given initialization, coupling in this way the global geometry of the underlying loss landscape with the statistics of the noise entering the process. Finally, motivated by applications to the training of deep neural networks, we also provide a series of refinements and extensions of our analysis for loss functions with shallow local minima. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_16398 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations Azizian, Waïss Iutzeler, Franck Malick, Jérôme Mertikopoulos, Panayotis Optimization and Control Machine Learning Primary 90C15, 90C26, 60F10, secondary 90C30, 68Q32 In this paper, we examine the time it takes for stochastic gradient descent (SGD) to reach the global minimum of a general, non-convex loss function. We approach this question through the lens of randomly perturbed dynamical systems and large deviations theory, and we provide a tight characterization of the global convergence time of SGD via matching upper and lower bounds. These bounds are dominated by the most "costly" set of obstacles that the algorithm may need to overcome in order to reach a global minimizer from a given initialization, coupling in this way the global geometry of the underlying loss landscape with the statistics of the noise entering the process. Finally, motivated by applications to the training of deep neural networks, we also provide a series of refinements and extensions of our analysis for loss functions with shallow local minima. |
| title | The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations |
| topic | Optimization and Control Machine Learning Primary 90C15, 90C26, 60F10, secondary 90C30, 68Q32 |
| url | https://arxiv.org/abs/2503.16398 |