Convergence of Multi-Level Markov Chain Monte Carlo Adaptive Stochastic Gradient Algorithms
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918315593564160 |
|---|---|
| author | Godichon-Baggioni, Antoine Lang, Gabriel Corff, Sylvain Le Stoehr, Julien Surendran, Sobihan |
| author_facet | Godichon-Baggioni, Antoine Lang, Gabriel Corff, Sylvain Le Stoehr, Julien Surendran, Sobihan |
| contents | Stochastic optimization in learning and inference often relies on Markov chain Monte Carlo (MCMC) to approximate gradients when exact computation is intractable. However, finite-time MCMC estimators are biased, and reducing this bias typically comes at a higher computational cost. We propose a multilevel Monte Carlo gradient estimator whose bias decays as $O(T_{n}^{-1} )$ while its expected computational cost grows only as $O(log T_n )$, where $T_n$ is the maximal truncation level at iteration n. Building on this approach, we introduce a multilevel MCMC framework for adaptive stochastic gradient methods, leading to new multilevel variants of Adagrad and AMSGrad algorithms. Under conditions controlling the estimator bias and its second and third moments, we establish a convergence rate of order $O(n^{-1/2} )$ up to logarithmic factors. Finally, we illustrate these results on Importance-Weighted Autoencoders trained with the proposed multilevel adaptive methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_22799 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Convergence of Multi-Level Markov Chain Monte Carlo Adaptive Stochastic Gradient Algorithms Godichon-Baggioni, Antoine Lang, Gabriel Corff, Sylvain Le Stoehr, Julien Surendran, Sobihan Statistics Theory Stochastic optimization in learning and inference often relies on Markov chain Monte Carlo (MCMC) to approximate gradients when exact computation is intractable. However, finite-time MCMC estimators are biased, and reducing this bias typically comes at a higher computational cost. We propose a multilevel Monte Carlo gradient estimator whose bias decays as $O(T_{n}^{-1} )$ while its expected computational cost grows only as $O(log T_n )$, where $T_n$ is the maximal truncation level at iteration n. Building on this approach, we introduce a multilevel MCMC framework for adaptive stochastic gradient methods, leading to new multilevel variants of Adagrad and AMSGrad algorithms. Under conditions controlling the estimator bias and its second and third moments, we establish a convergence rate of order $O(n^{-1/2} )$ up to logarithmic factors. Finally, we illustrate these results on Importance-Weighted Autoencoders trained with the proposed multilevel adaptive methods. |
| title | Convergence of Multi-Level Markov Chain Monte Carlo Adaptive Stochastic Gradient Algorithms |
| topic | Statistics Theory |
| url | https://arxiv.org/abs/2601.22799 |