Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2210.06591 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909916074082304 |
|---|---|
| author | Gerbelot, Cedric Troiani, Emanuele Mignacco, Francesca Krzakala, Florent Zdeborova, Lenka |
| author_facet | Gerbelot, Cedric Troiani, Emanuele Mignacco, Francesca Krzakala, Florent Zdeborova, Lenka |
| contents | We prove closed-form equations for the exact high-dimensional asymptotics of a family of first order gradient-based methods, learning an estimator (e.g. M-estimator, shallow neural network, ...) from observations on Gaussian data with empirical risk minimization. This includes widely used algorithms such as stochastic gradient descent (SGD) or Nesterov acceleration. The obtained equations match those resulting from the discretization of dynamical mean-field theory (DMFT) equations from statistical physics when applied to gradient flow. Our proof method allows us to give an explicit description of how memory kernels build up in the effective dynamics, and to include non-separable update functions, allowing datasets with non-identity covariance matrices. Finally, we provide numerical implementations of the equations for SGD with generic extensive batch-size and with constant learning rates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_06591 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Rigorous dynamical mean field theory for stochastic gradient descent methods Gerbelot, Cedric Troiani, Emanuele Mignacco, Francesca Krzakala, Florent Zdeborova, Lenka Mathematical Physics Information Theory Machine Learning We prove closed-form equations for the exact high-dimensional asymptotics of a family of first order gradient-based methods, learning an estimator (e.g. M-estimator, shallow neural network, ...) from observations on Gaussian data with empirical risk minimization. This includes widely used algorithms such as stochastic gradient descent (SGD) or Nesterov acceleration. The obtained equations match those resulting from the discretization of dynamical mean-field theory (DMFT) equations from statistical physics when applied to gradient flow. Our proof method allows us to give an explicit description of how memory kernels build up in the effective dynamics, and to include non-separable update functions, allowing datasets with non-identity covariance matrices. Finally, we provide numerical implementations of the equations for SGD with generic extensive batch-size and with constant learning rates. |
| title | Rigorous dynamical mean field theory for stochastic gradient descent methods |
| topic | Mathematical Physics Information Theory Machine Learning |
| url | https://arxiv.org/abs/2210.06591 |