Stochastic approximation algorithms are a standard tool for the numerical computation of zeroes of functions $f:R^d \to R^d$ of the form $f(\theta)=E[F(\theta,U)]$ with $U$ denoting a random variable and $F$ an appropriate measurable function.

Robbins and Monro introduced in 1951 a dynamical system that converges to solutions and is based on independent realisations of $U$ (under appropriate assumptions). Research on this topic remained active and resulted in a variety of results. A natural question was whether the approach can be combined with the recently discovered multilevel paradigm in the case where $F(\theta,U)$ is not simulatable. Indeed, as shown by N. Frikha the combination bears potential and leads to new efficient schemes in the context of SDEs.

In this talk we provide new multilevel stochastic approximation algorithms and present complexity theorems on $L^p$-errors in the spirit of the original work of M. Giles on multilevel Monte Carlo. In contrast to previous work, our error analysis requires significantly weaker assumptions which makes it applicable in a wide variety of examples.