Biased stochastic approximation and applications

Stochastic gradient algorithms and their variants, such as AdaGrad and ADAM, have been extensively studied in recent years to address large-scale, high-dimensional optimization problems. Most theoretical analyses, however, rely on the assumption that unbiased gradient estimators are available.

 

We consider here the more challenging setting in which only biased gradient estimators can be computed, and we analyze the impact of this bias on convergence properties. Such situations arise naturally in several important applications, including Optimal Transport problems and the training of Variational Autoencoders (VAEs). A particularly relevant example occurs when gradients are approximated using Markov Chain Monte Carlo (MCMC) methods.

 

In this context, we demonstrate how computational cost can be significantly reduced while preserving convergence guarantees up to a controlled error, by leveraging Multi-Level Markov Chain Monte Carlo (ML-MCMC) techniques. Finally, we investigate the application of this methodology to the training of VAEs.