Multi-level stochastic approximation algorithms
From MaRDI portal
central limit theoremEuler schememulti-level Monte Carlo methodsRuppert-Polyak averaging principlestochastic approximation algorithmstochastic optimization
Existence of optimal solutions to problems involving randomness (49J55) Central limit and other weak theorems (60F05) Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Monte Carlo methods (65C05) Numerical solutions to stochastic differential and integral equations (65C30) Stochastic programming (90C15) Optimal stochastic control (93E20)
Abstract: This paper studies multi-level stochastic approximation algorithms. Our aim is to extend the scope of the multilevel Monte Carlo method recently introduced by Giles (Giles 2008) to the framework of stochastic optimization by means of stochastic approximation algorithm. We first introduce and study a two-level method, also referred as statistical Romberg stochastic approximation algorithm. Then, its extension to multi-level is proposed. We prove a central limit theorem for both methods and describe the possible optimal choices of step size sequence. Numerical results confirm the theoretical analysis and show a significant reduction in the initial computational cost.
Recommendations
Cites work
- A Stochastic Approximation Method
- Acceleration of Stochastic Approximation by Averaging
- Analyzing multi-level Monte Carlo for options with non-globally Lipschitz payoff
- Asymptotic error distributions for the Euler method for stochastic differential equations
- Central limit theorem for the multilevel Monte Carlo Euler method
- Computing VaR and CVaR using stochastic approximation and adaptive unconstrained importance sampling
- Concentration bounds for stochastic approximations
- CVaR hedging using quantization-based stochastic approximation algorithm
- Efficient Monte Carlo simulation of security prices
- scientific article; zbMATH DE number 3723610 (Why is no real title available?)
- scientific article; zbMATH DE number 48727 (Why is no real title available?)
- scientific article; zbMATH DE number 1972910 (Why is no real title available?)
- scientific article; zbMATH DE number 2000348 (Why is no real title available?)
- scientific article; zbMATH DE number 3227597 (Why is no real title available?)
- Improved multilevel Monte Carlo convergence using the Milstein scheme
- Multilevel Monte Carlo algorithms for Lévy-driven SDEs with Gaussian correction
- Multilevel Monte Carlo Path Simulation
- On mixing and stability of limit theorems
- Rates of convergence to the local time of a diffusion
- Recursive computation of value-at-risk and conditional value-at-risk using MC and QMC
- Shortfall risk minimization in discrete time financial market models
- Statistical Romberg extrapolation: a new variance reduction method and applications to option pricing
- Stochastic algorithms
- Transport-entropy inequalities and deviation estimates for stochastic approximation schemes
- Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing
Cited in
(19)- Experiences with the multi-level algorithm
- Weighted multilevel Langevin simulation of invariant measures
- General multilevel adaptations for stochastic approximation algorithms of Robbins-Monro and Polyak-Ruppert type
- Multi-level arc combination with stochastic parameters.
- General multilevel adaptations for stochastic approximation algorithms. II: CLTs
- Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization
- Multilevel Monte Carlo approximation of functions
- A multi-step Richardson-Romberg extrapolation method for stochastic approximation
- A multi-level procedure for enhancing accuracy of machine learning algorithms
- Unbiased MLMC stochastic gradient-based optimization of Bayesian experimental designs
- Multidimensional stochastic approximation
- Multilevel nested simulation for efficient risk estimation
- Stochastic approximation with discontinuous dynamics, differential inclusions, and applications
- (Non)-penalized multilevel methods for non-uniformly log-concave distributions
- Multi-index antithetic stochastic gradient algorithm
- Estimation of systemic shortfall risk measure using stochastic algorithms
- Unbiased parameter estimation for partially observed diffusions
- A multilevel stochastic approximation algorithm for value-at-risk and expected shortfall estimation
- Asymptotic error analysis of multilevel stochastic approximations for the value-at-risk and expected shortfall
This page was built for publication: Multi-level stochastic approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q292915)
