General multilevel adaptations for stochastic approximation algorithms

Steffen Dereich

Abstract

In this article, we present and analyse new multilevel adaptations of stochastic approximation algorithms for the computation of a zero of a function $f: D \to \mathbb{R}^d$ defined on a convex domain $D \subset \mathbb{R}^d$, which is given as a parameterised family of expectations. Our approach is universal in the sense that having multilevel implementations for a particular application at hand, it is straightforward to implement the corresponding stochastic approximation algorithm. Moreover, previous research on multilevel Monte Carlo can be incorporated in a natural way. This is due to the fact that the analysis of the error and the computational cost of our method is based on similar assumptions as used in Giles (2008) for the computation of a single expectation. Additionally, we essentially only require that $f$ satisfies a classical contraction property from stochastic approximation theory. Under these assumptions, we establish error bounds in $p$-th mean for our multilevel Robbins-Monro and Polyak-Ruppert schemes that decay in the computational time as fast as the classical error bounds for multilevel Monte Carlo approximations of single expectations known from Giles (2008).

Introduction

Finding the root of a function is a fundamental task in numerical analysis. However, in many modern applications—particularly in quantitative finance and engineering—the function $f(\theta)$ is defined as an expectation: $f(\theta) = \mathbb{E}[F(\theta, U)]$. Solving for $\theta$ such that $f(\theta) = 0$ becomes computationally intensive when $F$ involves complex simulations, such as those requiring numerical discretization of Stochastic Differential Equations (SDEs).

Traditionally, this problem is addressed using Stochastic Approximation (SA), such as the Robbins-Monro algorithm. These methods update an estimate of the root iteratively using noisy samples. A significant hurdle arises when $F(\theta, U)$ cannot be sampled exactly; one must choose a discretization level that balances bias and variance. High precision requires fine discretization, which makes every step of the algorithm prohibitively slow. This paper introduces a "universal" framework that integrates the Multilevel Monte Carlo (MLMC) paradigm into SA to overcome this bottleneck.

The Multilevel Stochastic Approximation Framework

The core innovation presented by Steffen Dereich and Thomas Müller-Gronbach is a single-step SA algorithm where the complexity of the estimator is adapted dynamically. Unlike previous approaches that might use a sequence of separate, coupled algorithms, this framework uses a hierarchy of levels to estimate the function value at each iteration.

Adaptive Complexity

In the proposed multilevel schemes, the estimator $Z_n(\theta)$ at step $n$ is constructed as a telescoping sum of differences between successive approximation levels. Crucially, the number of levels and the number of samples at each level are not fixed. They increase as the algorithm progresses ($n$ increases). This ensures that the algorithm does not waste computational effort on high-precision estimates while the current iterate is still far from the actual root.

Algorithmic Variants

The authors adapt two primary schemes:

  1. Multilevel Robbins-Monro (RM): The standard iterative update adapted for multilevel estimators.
  2. Multilevel Polyak-Ruppert (PR) Averaging: This involves taking a weighted average of the RM iterates. PR averaging is particularly valuable because it often provides better stability and allows the algorithm to achieve optimal convergence rates without requiring precise knowledge of the function's contraction constant.

Theoretical Contributions

The paper establishes rigorous error bounds in $p$-th mean for both the RM and PR schemes. A key technical achievement is the development of a modified Burkholder-Davis-Gundy (BDG) inequality, which provides the probabilistic foundation for analyzing the convergence of these adaptive multilevel processes.

The most significant theoretical result is the achievement of efficiency parity. The authors demonstrate that the computational cost required to reach a specific error tolerance for the root of the expectation is asymptotically equivalent to the cost of computing a single expectation using standard MLMC. This suggests that the root-finding process adds no significant asymptotic complexity over the underlying estimation problem.

Numerical Validation: The Black-Scholes Case Study

To validate the theoretical findings, the authors applied the algorithms to a volatility estimation problem within the Black-Scholes model. The goal was to find the volatility $\theta^*$ that results in a specific European call option price, where the price process is simulated using an equidistant Milstein scheme.

Key observations from the numerical experiments include:

  • Convergence Rates: The Root Mean Squared Error (RMSE) decayed at a rate of $O(n^{-2})$ in the test case, matching the theoretical predictions.
  • Cost-Efficiency: The total computational cost was shown to be $O(n^4)$, aligning with the theoretical bounds where cost relates to error as $cost \approx e_n^{-2}$ (for the case where the variance decay rate $\beta > 1/2$).
  • Robustness: The use of Polyak-Ruppert averaging confirmed that the algorithm remains effective even when the contraction constant of the underlying function is not known a priori.

Conclusion

This research provides a robust and universal framework for applying multilevel techniques to stochastic approximation. By allowing the precision of the multilevel estimator to grow alongside the algorithm's iterations, the authors have bridged the gap between efficient expectation estimation and root-finding. This framework is highly extensible; any problem currently solvable via MLMC can be naturally transitioned into this SA framework to solve associated inverse problems or optimization tasks with optimal computational efficiency.

Summary updated

Abstract

In this article we present and analyse new multilevel adaptations of stochastic approximation algorithms for the computation of a zero of a function $f\colon D \to \mathbb R^d$ defined on a convex domain $D\subset \mathbb R^d$, which is given as a parameterised family of expectations. Our approach is universal in the sense that having multilevel implementations for a particular application at hand it is straightforward to implement the corresponding stochastic approximation algorithm. Moreover, previous research on multilevel Monte Carlo can be incorporated in a natural way. This is due to the fact that the analysis of the error and the computational cost of our method is based on similar assumptions as used in Giles (2008) for the computation of a single expectation. Additionally, we essentially only require that $f$ satisfies a classical contraction property from stochastic approximation theory. Under these assumptions we establish error bounds in $p$-th mean for our multilevel Robbins-Monro and Polyak-Ruppert schemes that decay in the computational time as fast as the classical error bounds for multilevel Monte Carlo approximations of single expectations known from Giles (2008).
BibTeX
@article{dereich2019general,
  author = {Steffen Dereich},
  title = {{General multilevel adaptations for stochastic approximation algorithms}},
  journal = {Numerische Mathematik},
  year = {2019},
  doi = {10.1007/s00211-019-01024-y},
}
Figure