Asymptotic Variance in the Central Limit Theorem for Multilevel Markovian Stochastic Approximation
2025
Read Asymptotic Variance in the Central Limit Theorem for Multilevel Markovian Stochastic Approximation (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-06603.txt.
Introduction
Ajay Jasra and Abylay Zhumekenov study the asymptotic variance in a limit theorem for multilevel stochastic approximation with Markovian noise, in a 2025 note. The work sits in parameter estimation for inverse problems. In that work, the aim is to find the best value of a marginal likelihood. That value is tied to a differential equation.
Two hard points stand out. The equation at the heart of the work has no closed form, and the same holds for the likelihood tied to it. Work done by computer to solve the equation adds bias. The step-by-step chance method deals with the likelihood side. Layered schemes pair layers of numerical solutions with gradient methods, and this pairing cuts cost. The note works out the spread that sets how close results land when samples grow large, for this layered Markovian setting.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-06603
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymptotic Variance in the Central Limit Theorem for Multilevel Markovian Stochastic Approximation Abstract In this note we consider the finite-dimensional parameter estimation problem associated to inverse problems. In such scenarios, one seeks to maximize the marginal likelihood associated to a Bayesian model. This latter model is connected to the solution of partial or ordinary differential equation. As such, there are two primary difficulties in maximizing the marginal likelihood (i) that the solution of differential equation is not always analytically tractable and (ii) neither is the marginal likelihood. Typically (i) is dealt with using a numerical solution of the differential equation, leading to a numerical bias and (ii) has been well studied in the literature using, for instance, Markovian stochastic approximation (e.g. [ 1 ] ). It is well-known, e.g. [ 5 , 7 , 9 ] , that to reduce the computational effort to obtain the maximal value of the parameter, one can use a hierarchy of solutions of the differential equation and combine with stochastic gradient methods. The approaches of [ 5 , 7 ] do exactly this. In this paper we consider the asymptotic variance in the central limit theorem, associated to estimates from [ 7 ] and find bounds on the asymptotic variance in terms of the precision of the solution of the differential equation. The significance of these bounds are the that they provide missing theoretical guidelines on how to set simulation parameters in [ 5 , 7 ] ; that is, these appear to be the first mathematical results which help to run the methods efficiently in practice. Key words : Central Limit Theorem; Markovian Stochastic Approximation; Multilevel Monte Carlo. AJAY JASRA & ABYLAY ZHUMEKENOV School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen, CN. E-Mail: [email protected], [email protected] 1 Introduction We consider the problem of finding the root of the function h(\theta)=\int_{\mathsf{X}}H(\theta,x)\pi_{\theta}(x)dx where for each \theta\in\Theta\subseteq\mathbb{R} , \pi_{\theta} is a probability density on the space (\mathsf{X},\mathscr{X}) , dx is a \sigma- finite measure and H:\Theta\times\mathsf{X}\rightarrow\Theta is, for each \theta\in\Theta , a \pi_{\theta}- integrable function. We assume that there exists a unique \theta^{\star}\in\Theta which such that h(\theta^{\star})=0 . In the kind of problems that we are interested in, H(\theta,x) is the gradient w.r.t. \theta of the log of an un-normalized probability density; examples can be found in [ 9 ] . The problem given here can be solved using Markovian stochastic approximation (MSA) (e.g. [ 1 ] ) especially if \pi_{\theta} cannot be sampled from exactly. We review the MSA method in the next Section. In many applications \pi_{\theta} and H(\theta,x) is associated with the solution of a partial or ordinary differential equation and in such scenarios one replaces the exact solution with a provably convergent numerical solution. Then one can proceed by trying to solve the approximated problem using MSA; this is detailed in the next Section. It is well-known (see for instance [ 10 ] ) that one can reduce the computational effort to compute the root (maximizer) associated to the approximated h(\theta) . Instead of considering simply one MSA algorithm with a numerical solution of the differential equation of a given accuracy, one considers several solutions simultaneously. This leads to multilevel Markovian stochastic approximation algorithms as was developed originally in [ 5 ] and applied directly to partial/ordinary differential equation problems in [ 7 ] . The articles [ 5 , 7 ] focus on developing new methodology and proving that unbiased estimates of \theta^{\star} can be obtained, but critically, rely on mathematical conjectures in order to set certain simulation parameters. The optimal setting of said simulation parameters is often key to ensuring a reduction in computational effort, of using multilevel MSA versus MSA on its own. In this note we intend to fill in the theoretical gap from [ 7 ] . In this note we consider the asymptotic variance expression from the central limit theorem (CLT) proved by [ 8 ] for MSA. The expression is adapted for the estimators that are under study in this work, i.e. of multilevel type (explained in the next Section). In particular and under mathematical assumptions, we provide a non-trivial upper-bound for the asymptotic variance in the CLT, in terms of the accuracy of the numerical solver of the differential equation. This upper-bound is critical in providing a mathematical justification of how to set the simulation parameters in [ 7 ] . It should be noted that our approach is limited to \theta\in\Theta\subseteq\mathbb{R} . The reason for this is because the general ( d- dimensional) case in [ 8 ] has the asymptotic (co)variance in the form of a solution to Lyapunov’s equation. Whilst under fairly general assumptions one has a unique to solution to Lyapunov’s equation, the general solution is analytically intractable, at least in a form that could be used to bound it in an appropriate norm. Thus we consider only the one-dimensional case. We also remark that we rely on asymptotics such as the CLT, instead of finite time (algorithm time) bounds as the latter do not appear to be in the literature and is more general problem than the one that we seek to address in this note. This note is structured as follows. In Section 2 we give details of the problem of interest and the algorithm which we study. Section 3 gives the mathematical set-up for our main result, including notations and assumptions. In Section 4 our main result is given along with some implications. Appendix A features several technical results used the prove the theorem in Section 4 . 2 Setting 2.1 Approach In many applications in practice, obtaining \theta^{\star} can be solved by using MSA as in e.g. [ 1 ] . For any \theta\in\Theta let K_{\theta}:\mathsf{X}\times\mathscr{X}\rightarrow[0,1] be a \pi_{\theta}- invariant Markov kernel and let (\gamma_{n})_{n\in\mathbb{N}} be a sequence of non-negative numbers such that \sum_{n\geq 1}\gamma_{n}=\infty , \sum_{n\geq 1}\gamma_{n}^{2}<\infty , \log(\gamma_{n}/\gamma_{n-1})=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{\scalebox{.7}{$\scriptscriptstyle\mathcal{O}$}}(\gamma_{n}) ; this latter assumption is [ 8 , Condition 4a] , which we use later on. Then given (\theta_{0},x_{0})\in\Theta\times\mathsf{X} one can run the following procedure, for n\geq 1 : 1. Simulate X_{n}|(\theta_{0},x_{0}),\dots,(\theta_{n-1},x_{n-1}) using K_{\theta_{n-1}}(x_{n-1},\cdot) . 2. Update \theta_{n}=\theta_{n-1}+\gamma_{n}H(\theta_{n-1},X_{n}) and set n=n+1 and go to the start of 1.. In many cases one employs the idea of reprojection (e.g. [ 1 , 8 ] ) and we also do this. Let (\mathscr{K}_{n})_{n\geq 0} be a sequence of compact subsets of \Theta such that for each n\geq 1 , \mathscr{K}_{n-1}\subseteq\mathscr{K}_{n} and \bigcup_{n\geq 0}\mathscr{K}_{n}=\Theta. Then we modify the above procedure as follows: set (\theta_{0},x_{0},\psi_{0})\in\mathscr{K}_{0}\times\mathsf{X}\times\{0\} then we consider the procedure or n\geq 1 : 1. Simulate X_{n}|(\theta_{0},x_{0},\psi_{0}),\dots,(\theta_{n-1},x_{n-1},\psi_{n-1}) using K_{\theta_{n-1}}(x_{n-1},\cdot) . 2. Set \theta_{n-1/2}=\theta_{n-1}+\gamma_{n}H(\theta_{n-1},X_{n}). 3. Update: (\theta_{n},\psi_{n})=\left\{\begin{array}[]{ll}(\theta_{n-1/2},\psi_{n-1})&\text{if}\penalty\ \theta_{n-1/2}\in\mathscr{K}_{\psi_{n-1}},\\ (\theta_{0},\psi_{n-1}+1)&\text{otherwise}\end{array}\right. and set n=n+1 and go to the start of 1.. 2.2 Approximation In several applications, such as [ 5 , 7 ] working with the exact model is not possible. Instead, one has a scalar parameter l\in\mathbb{N}_{0} , a sequence of functions H_{l}(\theta,x) and sequence of probability densities \pi_{\theta,l} on (\mathsf{X},\mathscr{X}) such that for each \theta\in\Theta : h_{l}(\theta):=\int_{\mathsf{X}}H_{l}(\theta,x)\pi_{\theta,l}(x)dx\penalty\ \text{and}\penalty\ \lim_{l\rightarrow\infty}h_{l}(\theta)=h(\theta). We shall assume that there exists a unique \theta^{\star}_{l}\in\Theta such that h_{l}(\theta^{\star}_{l})=0 and note that, we have \lim_{l\rightarrow\infty}\theta^{\star}_{l}=\theta^{\star} . It should be understood that • h_{l}(\theta) is closer, in terms of L_{1}- distance than h_{l-1}(\theta) to h(\theta) . •