Project Topics
Get Complete Project Material File(s) Now! »
A Multi-step Richardson-Romberg extrapolation method for stochastic approximation.
Stochastic approximation (SA) algorithms are simulation based procedures to approximate the zeros of a function h : Rd ! Rd which writes h() = E[H(; U)], for some Rd-valued random vector U. The function, H is assumed to be known by the experimenter, and it is implicitly supposed that the computation of h is more costly (in terms of computational time) than the simulation of U and the computation of H.
For simplicity, we assume that h has only one zero , even though the theory extends to the case of multiple zeros.
Robbins and Monro in [RM51] proposed the following recursive algorithm to approximate . Let (Up)p1 be an i:i:d: sequence of random variables with the same law as U, and 0 independent of the sequence (Up)p1 with E[j0j2] < +1. We consider the following recursive scheme: p+1 = p p+1H(p; Up+1); p 0.
Proof of Theorem 1.1: Uniqueness to the Martingale Problem
We are now in position to prove the uniqueness to the martingale problem. Our approach is largely inspired by [Men11]. It relies on the smoothing properties, of the Parametrix kernel H.
Proof. We focus on uniqueness. Indeed, the existence stems from Theorem 2.1 in Bass [Bas88]. It relies on compactness arguments, in the lines of those developed in the diffusive case in Chapter 6 in Stroock and Varadhan [SV79], or Stroock [Str75] for a Lévy process with a Brownian part. The main idea consists in proving that the measures (Pn)n2N induced by the Euler-Maruyama schemes are tight. We also mention the semigroup-based approach to existence of Komatsu [Kom84].
Continuity techniques : the Frozen equation and the parametrix series.
For density estimates, a continuity technique consists in considering a simpler equation as proxy model for the initial equation. The proxy will be significant if it achieves two properties:
– It admits an explicit density or a density that is well estimated.
– The difference between the density of the initial SDE and the one of the proxy can be well controlled.
For the last point a usual strategy consists in expressing the difference of the densities through the difference of the generators of the two SDEs, using Kolmogorov’s equations. This approach is known as the parametrix method. In the current work, we will use the procedure developed by Mc Kean and Singer [MKS67], which turns out to be well-suited to handle coefficients with mild smoothness properties. We first introduce the proxy model in Section 3.1, and give some associated density bounds. We then analyze in Sections 3.2, 3.3 how this choice can formally lead through a parametrix expansion to a density estimate, exploiting some suitable regularization properties in time. These arguments can be made rigorous provided that the initial SDE admits a Feller transition function. The uniqueness of the martingale problem will actually give this property.
The Frozen Process.
In this section, we give results that hold in any dimension d, and for any fixed number of oscillators n. Let T > 0 (arbitrary deterministic time) and y 2 Rnd (final freezing point) be given. Heuristically, y is the point where we want to estimate the density of (1.1) at time T provided it exists. We introduce the frozen process as follows: d ~X T;y s = As ~X T;y s ds + B(s;Rs;T y)dZs:
In this equation, Rs;T y is the resolvent of the associated deterministic equation, i.e. it satisfies d dsRs;T = AsRs;T , with RT;T = Indnd in Rnd Rnd. Let us emphasize that the previous choice can seem awkward at first sight. Indeed, a very natural approach for a proxy model would consist in freezing the diffusion coefficient at the terminal point, see e.g. Kolokoltsov [Kol00b]. In our current weak Hörmander setting we need to take into account the backward transport of the final point by the deterministic differential system. This particular choice is actually imposed by the natural metric appearing in the density of the frozen process, see Proposition 3.3. This allows the comparison of the singular parts of the generators of (1.1) and (3.1) applied to the frozen density, see Proposition 3.6 and Lemma 3.10.
Table of contents :
Résumé détaillé
1 Résumé en français
1.1 Estimées de densité pour des EDS dirigées par des processus stables tempérés
1.2 La méthode parametrix pour des EDS dégénérées dirigées par des processus stables
1.3 Richardson-Romberg pour les Algorithmes Stochastiques
2 Summary in English
2.1 Density Estimates for SDEs Driven by Tempered Stable Processes
2.2 A Parametrix Approach for some Degenerate Stable Driven SDEs
2.3 A Multi-step Richardson-Romberg extrapolation method for stochastic
approximation
1 Introduction
1 The Problem
2 The Parametrix Setting
2.1 The Parametrix Technique for PDEs
2.2 The Parametrix for Density Estimates
2.3 Convergence of the Series
2.4 Parametrix and Martingale Problem
2.5 Parametrix and Numerical Probabilities
2.6 Conclusion and Perspectives
3 The stable process
4 The Tempered case
5 The degenerate Case
6 Richardson-Romberg for stochastic approximation
2 Tempered Stable SDE
1 Introduction
2 The Parametrix Setting
3 Proof of the estimates
3.1 Estimates on the Frozen Density
3.2 The Smoothing Properties of H(t; x; y)
3.3 Proof of Theorem 1.1: Uniqueness to the Martingale Problem .
3.4 Proof of Lemma 3.10
3.5 Proof of the Lower Bound
3 Degenerate Stable SDE
1 Introduction
2 Assumptions, and Main Result
3 Continuity techniques
3.1 The Frozen Process
3.2 The Parametrix Series
3.3 Controls on the iterated kernels
4 Uniqueness to the Martingale Problem
5 Proof of the results involving the Frozen process
5.1 Analysis of the Resolvent
5.2 Estimates on the frozen density
5.3 Estimates on the convolution kernel H
6 Controls of the convolutions
6.1 Proof of Lemma 3.8
7 Diagonal Lower Bound For the Frozen Density
8 Off-diagonal Estimates on the Kernel H
9 Theorem 2.1 in the nonlinear case
4 Richardson Romberg for Stochastic Approximation
1 Statement of the Problem
2 Main results
2.1 Expansion of the implicit discretization error
2.2 Multi-step Richardson-Romberg extrapolation for stochastic approximation
2.3 Comparison with the crude stochastic approximation estimator .
3 Quantile Estimation for SDEs
3.1 Notations and Hypotheses
3.2 Expansion for the densities
4 Numerical illustration
5 Technical results
