A multi-step Richardson-Romberg extrapolation method for stochastic approximation

DOI10.1016/J.SPA.2015.05.016MaRDI QIDQ491176zbMATHOpenAlexFDO

Authors Lorick Huang, Noufel Frikha

Publication date 24 August 2015

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.4748

zbMATH Keywords

stochastic approximationstochastic optimizationEuler schemediffusion processesweak errorRichardson-Romberg extrapolation

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Diffusion processes (60J60) 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: We obtain an expansion of the implicit weak discretization error for the target of stochastic approximation algorithms introduced and studied in [Frikha2013]. This allows us to extend and develop the Richardson-Romberg extrapolation method for Monte Carlo linear estimator (introduced in [Talay & Tubaro 1990] and deeply studied in [Pag{`e}s 2007]) to the framework of stochastic optimization by means of stochastic approximation algorithm. We notably apply the method to the estimation of the quantile of diffusion processes. Numerical results confirm the theoretical analysis and show a significant reduction in the initial computational cost.

Recommendations

• Multilevel Richardson-Romberg extrapolation
• Multi-step Richardson-Romberg Extrapolation: Remarks on Variance Control and Complexity
• Multi-level stochastic approximation algorithms
• Extrapolation Methods for the Weak Approximation of Ito Diffusions
• Statistical Romberg extrapolation: a new variance reduction method and applications to option pricing

Cites work

• 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 3233089 (Why is no real title available?)
• A Stochastic Approximation Method
• Approximation of quantiles of components of diffusion processes.
• Bounds for the fundamental solution of a parabolic equation
• Concentration bounds for stochastic approximations
• Edgeworth type expansions for Euler schemes for stochastic differential equations.
• Multi-step Richardson-Romberg Extrapolation: Remarks on Variance Control and Complexity
• On some non asymptotic bounds for the Euler scheme
• Some estimates of the transition density of a nondegenerate diffusion Markov process
• Stochastic algorithms
• Symmetric Stable Laws and Stable-Like Jump-Diffusions
• Transport-entropy inequalities and deviation estimates for stochastic approximation schemes
• Weak error for stable driven stochastic differential equations: expansion of the densities

Cited in

(5)

• A simple method for the existence of a density for stochastic evolutions with rough coefficients
• Multilevel Richardson-Romberg extrapolation
• On the effectiveness of Richardson extrapolation in data science
• Estimateur de Richardson à pas variable
• Multi-step Richardson-Romberg Extrapolation: Remarks on Variance Control and Complexity

This page was built for publication: A multi-step Richardson-Romberg extrapolation method for stochastic approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491176)