On the fast convergence of minibatch heavy ball momentum
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918066855608320 |
|---|---|
| author | Bollapragada, Raghu Chen, Tyler Ward, Rachel |
| author_facet | Bollapragada, Raghu Chen, Tyler Ward, Rachel |
| contents | Simple stochastic momentum methods are widely used in machine learning optimization, but their good practical performance is at odds with an absence of theoretical guarantees of acceleration in the literature. In this work, we aim to close the gap between theory and practice by showing that stochastic heavy ball momentum retains the fast linear rate of (deterministic) heavy ball momentum on quadratic optimization problems, at least when minibatching with a sufficiently large batch size. The algorithm we study can be interpreted as an accelerated randomized Kaczmarz algorithm with minibatching and heavy ball momentum. The analysis relies on carefully decomposing the momentum transition matrix, and using new spectral norm concentration bounds for products of independent random matrices. We provide numerical illustrations demonstrating that our bounds are reasonably sharp. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_07553 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the fast convergence of minibatch heavy ball momentum Bollapragada, Raghu Chen, Tyler Ward, Rachel Machine Learning Data Structures and Algorithms Numerical Analysis Optimization and Control 65K05, 90C06, 90C30, 65F10, 68W20 Simple stochastic momentum methods are widely used in machine learning optimization, but their good practical performance is at odds with an absence of theoretical guarantees of acceleration in the literature. In this work, we aim to close the gap between theory and practice by showing that stochastic heavy ball momentum retains the fast linear rate of (deterministic) heavy ball momentum on quadratic optimization problems, at least when minibatching with a sufficiently large batch size. The algorithm we study can be interpreted as an accelerated randomized Kaczmarz algorithm with minibatching and heavy ball momentum. The analysis relies on carefully decomposing the momentum transition matrix, and using new spectral norm concentration bounds for products of independent random matrices. We provide numerical illustrations demonstrating that our bounds are reasonably sharp. |
| title | On the fast convergence of minibatch heavy ball momentum |
| topic | Machine Learning Data Structures and Algorithms Numerical Analysis Optimization and Control 65K05, 90C06, 90C30, 65F10, 68W20 |
| url | https://arxiv.org/abs/2206.07553 |