Multi-level stochastic approximation algorithms
From MaRDI portal
central limit theoremstochastic optimizationEuler schememulti-level Monte Carlo methodsRuppert-Polyak averaging principlestochastic approximation algorithm
Monte Carlo methods (65C05) Central limit and other weak theorems (60F05) Stochastic programming (90C15) Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Existence of optimal solutions to problems involving randomness (49J55) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Numerical solutions to stochastic differential and integral equations (65C30) 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
- 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?)
- 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
- CVaR hedging using quantization-based stochastic approximation algorithm
- 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
- Efficient Monte Carlo simulation of security prices
- Improved multilevel Monte Carlo convergence using the Milstein scheme
- Multilevel Monte Carlo Path Simulation
- Multilevel Monte Carlo algorithms for Lévy-driven SDEs with Gaussian correction
- 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
(17)- Weighted multilevel Langevin simulation of invariant measures
- Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization
- Unbiased parameter estimation for partially observed diffusions
- A multi-step Richardson-Romberg extrapolation method for stochastic approximation
- Multi-level arc combination with stochastic parameters.
- Multilevel Monte Carlo approximation of functions
- General multilevel adaptations for stochastic approximation algorithms. II: CLTs
- Estimation of systemic shortfall risk measure using stochastic algorithms
- Multilevel nested simulation for efficient risk estimation
- Multidimensional stochastic approximation
- 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
- General multilevel adaptations for stochastic approximation algorithms of Robbins-Monro and Polyak-Ruppert type
- Unbiased MLMC stochastic gradient-based optimization of Bayesian experimental designs
- A multi-level procedure for enhancing accuracy of machine learning algorithms
- Experiences with the multi-level algorithm
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)
