Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise

Authors: sebastian  allmeier
nicolas  gast
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 20:09:01

Abstract: We study stochastic approximation algorithms with Markovian noise and constant step-size $\alpha$. We develop a method based on infinitesimal generator comparisons to study the bias of the algorithm, which is the expected difference between $\theta_n$ ---the value at iteration $n$--- and $\theta^*$ ---the unique equilibrium of the corresponding ODE. We show that, under some smoothness conditions, this bias is of order $O(\alpha)$. Furthermore, we show that the time-averaged bias is equal to $\alpha V + O(\alpha^2)$, where $V$ is a constant characterized by a Lyapunov equation, showing that $E[\bar{\theta}_n] \approx \theta^*+V\alpha + O(\alpha^2)$, where $\bar{\theta}_n$ is the Polyak-Ruppert average.  We also show that $\bar{\theta}_n$ converges with high probability around $\theta^*+\alpha V$. We illustrate how to combine this with Richardson-Romberg extrapolation to derive an iterative scheme with a bias of order $O(\alpha^2)$.

Main paper: 
 introduction: 
 Stochastic approximation (SA) is a widely used algorithmic paradigm to solve fixed-point problems under noisy observations. While SA was introduced in the 1950s [30, 6] , it is still widely used today in many applications to solve optimization problems, or to implement machine learning or reinforcement learning algorithms [23, 5] . A typical SA is a stochastic recurrence of the form θ n`1 " θ n `αn pf pθ n , X n q `Mn`1 q,where θ n P R d is a vector of parameters, X n and M n`1 are sources of randomness, and α n is the step-size. The step-size might be decreasing to 0 as n grow or can be fixed to a small constant (in which case we simply call it α).The goal of running a SA algorithm is to obtain a sequence θ n that gets close to the root θ ˚of the function f pθq " E rf pθ, Xq `M | θs, the expectation of the iterate (1), as n goes to infinity. The SA procedure described in (1) models many algorithms that are used in machine learning, like first-order optimization and stochastic gradient descent [24, 16] , and Q-learning or policy gradient algorithms [5, 35] .The theory of stochastic approximation has been studied extensively and is covered by a lot of textbooks, e.g., [4, 8, 23] . This theory shows that the limit points of θ n as n grows are similar to the limit points of the ODE 9x " f pxq [3, 9] . In particular, one can show that if all solutions of the ODE converge to θ ˚, then θ n gets close to θ ˚as n grows large (under technical conditions on f , the step size α n , and the noise X n or M n`1 ). The asymptotic behavior of θ n depends on the nature of the step-size: When the step-size α n depends on n and converges to 0 as n goes to infinity, then θ n generally converges almost surely to θ ˚. When α n is kept constant and does not depend on n, then θ n will in general not converge to θ ˚but keeps oscillating around θ ˚, with fluctuation amplitudes of order Op ? αq. In this work, we focus on the latter case and propose a method to quantify these fluctuations.We consider a SA algorithm with Markovian noise. That is, θ n evolves as in (1) where the random variable X n evolves as a Markov chain that depends on θ n , and the random variable M n`1 is a Martingale difference sequence. One thing that sets this paper apart from others is that we allow the Markovian noise to be dependent on θ n . This is particularly valuable in reinforcement learning application such as Q-learning where the exploration policy might depend on θ n (this would for instance be the case for ε-greedy). It is known that when the step size α is constant, then the expectation of the iterates, E rθ n s, does not converge to θ ˚as n goes to infinity but has a bias [41, 20] . The goal of our paper is to provide a framework to characterize and compute this bias.Our main contribution is to provide a framework based on semi-groups, to quantify the convergence rate of θ n to θ ˚. This framework is similar to Stein's method, that has been recently popularized to obtain accuracy results and refinement terms for fluid limits [10, 17, 18, 40] . It allows us to quantify the distance between the stochastic recurrence (1) and its deterministic counterpart (8) as a function of the distance between the infinitesimal generators of the stochastic and deterministic systems. By using this framework, we obtain two main results. Our first result (Theorem 1) states that, under smoothness conditions on f , there exists a constant C ą 0 such that for all small enough α: This guarantees that that the bias and variance of θ n are of order at most α.A classical way to reduce the variance of SA is to use Polyak-Ruppert tail averaging [28, 31] ,i.e., to look at the convergence of θn " p1{nq ř n k"1 θ n instead of θ n . In this paper, we show that, for the constant step-size case, the use of Polyak-Ruppert averaging removes the variance (i.e. lim nÑ8 var " θn ‰ " 0), but not the bias: Theorem 2 shows that there exists a vector V and a constant C 1 ą 0 such that:lim sup nÑ8 ˇˇE " θn ‰ ´θ˚´V α ˇˇď Cα 2 .This shows that the bias of the averaging is exactly of order α. We also show in Theorem 3 that θn converges in probability to a point in θ ˚`V α `Opα 2 q as n goes to infinity.We also provide numerical simulation on a synthetic example that illustrates how to combine the Polyak-Ruppert averaging with a Richardson-Romberg extrapolation [19] to construct a stochastic approximation algorithm whose bias is of order Opα 2 q. This leads to an algorithm that enjoys both a small bias and a fast converge rate, compared to using a time-step of order α 2 .Roadmap. The rest of the paper is organized as follows. We describe related work in Section 2. We introduce the model and give assumptions and notations in Section 3. We state the main results and provide numerical illustrations in Section 4. We give the main ingredients of the proofs in Section 5.The appendices contain technical lemmas and additional numerical examples.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The purpose of the paper is to obtain bounds on the accuracy of constant step-size stochastic approximation. This is directly reflected by the title and abstract. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 Stochastic approximation algorithms were first introduced with decreasing step-size [30, 6] . Since these seminal papers, there has been a considerable amount of work aiming at characterizing the asymptotic properties of SA, by relating the asymptotic behavior of θ n with the one of the ODE 9 θ " f pθq [3, 9] . These topics are today well covered by textbooks such as [4, 8, 23] .In this original theory, the goal was to show that θ n is close to the behavior of an ODE but not necessarily to obtain tight rates of convergence. This lead to the development of a new line of research focussing on non-asymptotic properties of SA [27] . This paper derives a unified framework to study the rate of convergence of stochastic gradient descent by relating it to SA with decreasing step-size, and martingale noise (i.e., where the function f does not depend on X k in (1)). This framework has been extended by a series of papers for applications in reinforcement learning, see for instance [11, 15, 29, 26] , still in the decreasing step-size case, with the goal of understanding the fluctuations of the algorithm around the equilibrium.For the decreasing step size, the fluctuations of θ n around θ ˚vanish as n goes to infinity. This is not the case for constant step-size SA, for which understanding the magnitude of the fluctuations is therefore important. To bound the fluctuations, a part of the literature seeks to obtain bounds on the mean squared error (MSE), E " pθ n ´θ˚q2 ‰ as a function of the problem's parameter and the stepsize α. These papers show that the MSE is generally of order Opαq, see for instance [33] for the case of linear model plus Markovian noise, or [13, 15, 14] for contractive stochastic approximations (with Markovian or martingale noise).The case of constant-step size is also interesting because the θ n has a bias that does not vanish as n goes to infinity. In particular, the Polyak-Ruppert averaging does not converge to θ ˚: generally lim nÑ8 θn ‰ θ ˚. It is shown in particular in [16, 20, 25, 32, 41, 42 ] that a constant step-size SA has an asymptotic bias of order α, which shows that lim nÑ8 θn " θ ˚`V α `Opα 2 q. Some of these papers, and in particular [16, 20] , show that this bias characterization can be coupled with a Richardson-Romberg extrapolation to obtain a more accurate algorithm. In our paper, we also study the case of constant-step size SA with Markovian noise and use the same Polyak-Ruppert and Richardson-Romberg analysis. One of the distinguishable property of our model is that we allow the evolution of the Markovian noise X n to depend on θ n , whereas most of the cited paper consider X n has an external source of noise. This dependence is particularly interesting when studying asynchronous Q-learning algorithms [37, 36] , for which the navigation policy is often derived from the current values of the parameter (a popular example is to use an ϵ-greedy policy).A second distinguishable feature of our paper is the methodology that we use. Our main tool is to relate the distance between the expectation of θ n and θ ˚as a distance between the infinitesimal generators of the stochastic recurrence (1) and of the deterministic recurrence (8) . The method that we develop is tightly connected to Stein's method [34] and in particular with the line of work that use this method to obtain accuracy bounds for mean-field approximation [17, 22, 39, 40] . In particular, the start of our proof, which is to study a hybrid system composed of a stochastic and a deterministic recurrence in equation ( 9), can be seen as a discrete-time version of what is termed as a "classical trick" in [17, 22] . Apart from this difference between discrete and continuous time, one of the major features of our model is to have a Markovian noise. Our model can be viewed as a discrete-time version of the recent paper [1] . Some of our results (like our Theorem 1) are analogous to the results of [1] but others (like Theorem 2) are different and require time-averaging, mostly because of the possible periodicity of the discrete-time Markov chains. Also, the model of the current paper is slightly more general than the one of [1] . The fact that our methodology directly studies the expectation of θ n makes it different from convergence results that use concentration equalities [12] .Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The limits of the assumptions are discussed in a separate subsection 3.3. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
model and first assumptions: 
 Throughout the paper pθ n , X n q ně0 is a discrete-time stochastic process adapted to a filtration pF n q ně0 . This stochastic process has two components of different nature. The first component θ, that we call the parameter, is continuous and lives in a compact subset Θ Ă R d : for each n: θ n P Θ Ă R n . The second component X lives in a finite set X , i.e., X n P X .The evolution of θ and X are coupled in the following way. The parameter θ evolves according to the recurrence equation given by (1) . At every time-step n, the process X makes a Markovian transition according to a Markovian kernel Kpθ n q. More precisely, for all x, x1 P X and θ P Θ:P `Xn`1 " x 1 | X n " x, θ n " θ, F n ˘" P `Xn`1 " x 1 | X n " x, θ n " θ ˘": K x,x 1 pθq. (2)To obtain our results, we will make the following assumptions: (A1) The process M is a martingale difference sequence (that is: for all n:E rM n`1 | F n s " 0) and its conditional covariance is E " M n`1 M T n`1 | F n ‰ :" Qpθ n , X n q. Moreover, we assume that E " M n`1 M T n`1 | F n ^Xn`1 ‰ " Rpθ n , X n , X n`1 q. (A2)The functions f , K, Q and R are four times differentiable in θ. (A3) For any given θ P Θ, the matrix Kpθq is unichain 1 .In addition to these three assumptions, we later add an assumption (A4) about the stability of the ODE around its fixed point. We do not state this assumption here as it needs extra definitions.Assumption (A3) implies that a Markov chain with kernel Kpθq has a unique stationary measure πpθq, and we denote by π x pθq the stationary probability of x P X for such a Markov chain. For any function g defined on Θ ˆX , we call ḡ its averaged version, i.e., the function that associates to θ P Θ the value ḡpθq, defined as:EQUATIONIt is shown in [1, Lemma 4] , that under Assumption (A3), for each θ P Θ, the kernel Kpθq has a unique stationary distribution πpθq. The value ḡpθq is equal to E rgpθ, Xqs where X is distributed according to the stationary distribution associated to Kpθq.Following our notation introduced in (3), we denote by f the averaged version of f . By [1, Lemma 4] , the function θ Þ Ñ πpθq is twice differentiable under assumptions (A2) and (A3), which implies that the function f is also twice differentiable. This implies, for an initial ϑp0q " θ, the ODE 9 ϑ " f pϑq has a unique local solution, and we denote the value of this solution at time t by ϕ t pθq. In order to prove this result, we will need that this ODE has a unique fixed point to which all trajectories converge and that this fixed point is an exponentially stable attractor. This is summarized in the following asusmption: (A4) There exists a θ ˚such that for any θ, the solution of the ODE 9ϑ " f pϑq is defined for all t ą 0 and converges to θ ˚: lim tÑ8 ϕ t pθq " θ ˚for all θ P Θ. Moreover, the derivative of f at θ ˚is Hurwitz (i.e., the real parts of all of its eigenvalues are negative).By classical results on the stability of ODES, this assumption implies that the convergence to θ occurs exponentially fast, that is, there exists a, b ą 0 such that for all θ P Θ: }ϕ t pθq ´θ˚} ď ae ´bt }θ ´θ˚} . To prove that, one can use [21, Theorem 4.13] , that shows that θ ˚is an exponentially stable point of the ODE, i.e., }ϕ t pθq ´θ˚} ď a 1 e ´bt }θ ´θ˚} in a neighborhood N of θ ˚, because D f pθ ˚0q is Hurwitz. Then, as Θ is compact, there exists T such that ϕ T pθq P N for all θ P Θ. The result then follows by choosing a " a 1 e T b sup θPΘ }θ ´θ˚} { sup θPN }θ ´θ˚} .Most of the assumptions used in the paper are classical when studying stochastic approximation algorithms with Markovian noise. In this section, we discuss the limits of each assumption (from the most classical one to the most original one). Assumption (A3) is necessary to define the notion of average dynamics f pθq and is therefore present in virtually all papers about Markovian noise stochastic approximation. The originality of our assumption is that we allow the transition kernel to depend on θ. For assumption (A1), we add to the classical result the existence of a co-variance matrix Q, which is needed as it appears in the expression of V . Assumption (A4) imposes that the stochastic approximation has a unique exponentially stable attractor. Our results could probably be adapted to a model with multiple attractors (by using large deviation techniques similar to the one of [2, 38] for a two time-scale setting as ours) but this would be another paper.One important assumption we make is that θ lives in a compact set Θ. The bounded condition on Θ simplifies greatly the proofs because it allows us to use uniform bounds that do not depend on θ (for instance, the identity function hpθq " θ is bounded thanks to this assumption. Similarly, the time taken by the solution of the ODE ϕ t pθq to reach θ ˚is also uniformly bounded independently on θ). This assumption could be relaxed by imposing high probability bounds (for instance, a large deviation result like [2] that would guarantee that θ n stays close to θ ˚), or a bound on the higherorder moment or exponential moments of θ n . We left this result for future work as it would greatly impact the readability of the proofs.The most questionable of our assumption is Assumption (A2) that imposes that all parameters of the problem are four times differentiable in θ. While this assumption might seem as technical, the fact that the parameters are twice differentiable is crucial in our analysis. In particular, the constant V does depend on the first two derivatives of the function f . In general, if the parameters of the systems are not differentiable, then the bias will not be of order Opαq but of order Op ? αq. Treating a non-differentiable f would need a completely different methodology. Our assumption of having four times differentiable functions and not just twice has two reasons: it guarantees that the error › ›θ n ´pθ ˚`αV q › › is Opα 2 q, and it simplifies the proof by allowing us to reuse Theorem 1 to obtain the bound Opα 2 q in Theorem 2. We believe that if we only impose twice differentiability, this error would be opαq (and in fact probably α 3{2 as long as all derivatives are Lipschitz-continuous).Recall that Θ is a compact subset of R d . We suppose that it is equipped with a norm }¨}. For a function h : E Ñ R, where E Ă R d 1 , we denote by }h} " sup ePE }hpeq} the supremum of this function. If h is i times differentiable, we denote by D i h its ith derivative. Its value evaluated in e P E is denoted by D i hpeq. It is a multi-linear map and we denote by D i hpeqa bi its value applied to pa, . . . , aq for a given a P R d 1. We denote by › › D i h › › the operator norm of its ith derivative, defined as› › D i h › › " sup ePE,aPR d 1 › › D i hpeqa bj › › { }a} j .By Taylor remainder theorem, for all e P E and a P R d 1 , we have:› › ›hpe `aq ´hpeq ´ři´1 j"1 D j hpeqa bj › › › ď › › D i h › › }a} i .We define by› › D ďi h › › " maxp}h} , max jďi › › D j h› › q the maximum of the norm of the first ith derivatives of h. We denote by C i pE, Rq the set of functions whose first i derivatives are bounded and by C i ď1 pE, Rq the set of functions whose first i derivatives are bounded by 1:› › D ďi h › › ď 1.As X is a discrete set, the above notions extend to functions h : E ˆX Ñ R. For such a function, by abuse of notation, we call D i h the ith derivative with respect to the continuous variable only.In the paper, the value at time t of the solution of the ODE 9ϑ " f pϑq starting in θ is denoted by ϕ t pθq. We will introduce later a quantity φ n pθq that corresponds to a Euler discretization of the ODE with constant step-size α. To lighten notations, we will omit the dependence on α in the notation φ but it should be clear that φ depends on α. To help distinguishing between the solutions of the the ODE ϕ t and the discrete-time recurrence φ n , we will reserve the index t for a continuous time variable and the indices n, k or N for discrete-time indices.To ease notations in some part of the proofs, we will sometimes use big-O notations, like Op1q or Opαq. When using this, we allow the hidden constants to depends on all parameters of the problems defined in Assumptions (A1) to (A4) but they cannot depend on varying quantities likes an index k, n or α or norm of functions, like }g} or }h} that are introduced in the proofs. Note that in all of our lemmas, we always consider functions whose norm is bounded by 1. This can, of course, be readily extended to functions not bounded by 1 by adding an extra factor like › › D ďi h › › . We avoid doing this to lighten the notations.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: The proofs of the main results are given in the main body of the paper while some more technical lemmas are give in the appendix. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
main results and illustrations: 
 This section presents the main theorems and illustrate their consequence. The proof of the theorems are postponed to the next Section 5.Our first result is Theorem 1 that shows that the expected value of θ n is at distance at most Opαq of the solution of the ODE. This shows that the bias of stochastic approximation is of order α with respect to the ODE. Theorem 1. Assume (A1)-(A4). Then, there exists a constant C ą 0 and α 0 such that for all n, α ď α 0 and all h P C 3 ď1 pΘ, Rq: |E rhpθ n q ´hpϕ αn pθ 0 qqs| ď αC.Note that the bound of Theorem 1 is valid independently of n. As we will see in the proof, this is a consequence of Assumption (A4). Without the latter assumption, one would naturally obtain a constant C that grows exponentially with n. As C does not depend on time, a direct consequence of Theorem 1 is to show that the asymptotic bias of θ n is of order Opαq as n goes to infinity, that is:EQUATIONOur second result is Theorem 2, that shows that the inequality of ( 4) is essentially an equality. This theorem provides an asymptotic expansion of the bias term in α. Theorem 2. Assume (A1)-(A4). Then, there exists a constant C 1 ą 0 and α 0 such that for all α ď α 0 and h P C 5 ď1 pΘ, Rq:EQUATIONAn important difference between Theorem 1 and 2 is that the former studies the convergence of the iterates θ n whereas the latter provides a refinement term for the average of the iterates, i.e., θn :"1 n ř n k"1 E rθ k s, byshowing that θn is essentially equal to hpϕ 8 q plus a bias term V α. One may wonder if Theorem 2 would be true for the (non-averaged) iterates θ n . The answer is no and a counter-example is provided in Appendix A. This example illustrates that when the Markovian component X n can be periodic, the Opαq term of E rθ n s does not necessarily stabilize to a constant V but can be periodic as well.Theorem 2 concerns the convergence of the expectation of θn but not the value of θn itself. As we will see in Section 5, this is mostly due to our proof techniques that works with generators and therefore is most suitable to obtain precise convergence results for the expectation. In fact, we will prove in Section B.2 that we can obtain a high-probability convergence result as an almost-direct consequence of Theorem 2, as expressed by the following Theorem.Theorem 3. Assume (A1)-(A4). Then, there exists a constant C2 ą 0 and α 0 such that for all α ď α 0 :lim nÑ8 P `ˇθ n ´pθ ˚`αV q ˇˇě C 2 α 2 ˘" 0.This result is illustrated on a synthetic example whose parameters are given in Appendix A.2, and for which θ ˚" 1. We run the stochastic approximation algorithm for various values of α and report the results in Figure 1 . In all cases, we use the same source of randomness (the values of the Markov chain X n and of the the Martingale noise M n`1 are the same for all trajectories). We plot a sample trajectory of θ n , θn , and θn{2:n defined 2 as:θn{2:n " Q n 2 U n ÿ k"tn{2u`1 θ k ,for α P t0.001{4, 0.001{8, 0.001{16u (more values of α are displayed in Appendix A). We observe that if θ n is quite noisy, the Polyak-Ruppert averaging θn or θn{2:n are much closer to θ ˚" 1, which is a clear advantage for θn{2:n in terms of rate of convergence, especially for small values of α. As we will see in the proof, the constant V of Theorem 2 can be expressed as a function of the problem's parameters, which allows one to construct a quantity θ ˚`V that is a tight approximation ř n k"1 θ k for various values of α " 0.02 ˆ2´k with k P t0 . . . 5u and of the error of the extrapolation (6) for α " 0.01 and α " 0.005. of θn . Yet, stochastic approximation algorithms are most used when one does not have access to the problem's parameter. Here, we illustrate how we can run two algorithms with two different step-sizes in order to obtain an algorithm that has both a fast convergence rate and a high precision.Let θp2αq n{2:n and θpαq n{2:n be two trajectories of the stochastic recurrence (1) each with respective stepsize 2α and α. By Theorem 2, for large n we have:θp2αq n{2:n " θ ˚`2V α `Opα 2 q θpαq n{2:n " θ ˚`V α `Opα 2 qWe see that we can suppress the term in 2V α and V α by using a linear combination of θp2αq n{2:n and θpαq n{2:n , which leads to an equation that has a distance to θ ˚that is of order Opα 2 q:EQUATION)To explore the benefit of using the extrapolation (6), we plot in Figure 2 the error of the averaged iterate3 ˇˇθ n{2:n ´θ˚ˇ, and the error of the extrapolation (6) for various values of α " 0.01 ˚2´k , with k " t´1 . . . 4u. The parameters are the same as the one of Figure 1 and the various αs use the same source of randomness. As we expect by the statement of the theorems, the error θn{2:n ´θ˚i s approximately equal to V α (the stars on the right are the theoretical values of lim nÑ8 ˇˇθ n{2:n ´θ˚ˇ) . On the right panel, we observe that 2 θpαq n ´θ p2αq n is closer to θ ˚than the corresponding θpαq n (the scale of the y-axis is the same for both panels). Note that even for n " 10 5 , the valus of α are still noisy.5 Proof overview and generator methodQuestion: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: The paper does not contain important experimental results but only numerical illustrations of the theorems (with small synthetic examples). All parameters of the examples are provided in the appendix and the code of all simulation is available at https://github.com/ngast/paper_bias_stochastic_approximation2024. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
proof overview: 
 The first idea of our proof is to construct new random variables φ k pθ n´k q that corresponds to a system where we apply the stochastic recurrence (1) for k steps and then apply the deterministic recurrence (8) up to time n. By introducing these new variables and comparing their expectation for k and k `1, we reduce our problem to a comparison of the generators of the stochastic and of the deterministic system. This step is done in Section 5.2. In an independent lemma, we use Assumption (A4) to show that the derivatives of the function φ n converge exponentially fast to 0 as n goes to infinity. This leads to Lemma 6 whose proof is technical and postponed to Section C. Once these two basic points are obtained, we will use them to prove Proposition 4 which shows that the expectation of θ n is close to the solution of the deterministic ODE. More precisely, this proposition shows that there exists a bounded sequence of constants V pαq n and a constant C ą 0 such that for all n P N: ˇˇE rhpθ n q ´hpϕ nα pθ 0 qqs ´αV pαq n ˇˇď Cα 2 . A main difficulty is to show that V pαq n is bounded. For that we will use Lemmas 7 and 8 that use properties of the Poisson Equation (21) to show that if the functions g k do not vary too much with k, then they can be replaced by their averaged versions:EQUATION)Theorem 1 is a direct consequence of Proposition 4. by using that V pαq n are bounded.The next step is to show that the time average versions ofV pαq n , V pαq n " n ´1 ř n k"1 Vpαq n , converges (as n goes to infinity) to a term V pαq . Here, the main technical difficulty is to obtain a refinement of the averaging property of (7) , which is done in Lemmas 9 and 10. We then use Theorem 1 and Lemma 11 to show that V pαq « V `Opαq where V is given in Proposition 5. This gives Theorem 2. As a side-product, Lemma 11 also shows that the constant V can be computed by solving a linear system. The high-probability bound (Theorem 3) is a consequence of Theorem 2.The proof structure is illustrated in Figure 3 that shows the dependencies between the lemmas. Generator method (Section 5.2)Exponential decay of› › › B i pBθq i φ n › › › as n grows (Lemma 6) Telescopic sums (Lemma 7)Refined averaging (Lemmas 9 and 10)Derivation of V pαq n (Proposition 4) lim nÑ8 V pαq n « V (Proposition 5) Bias is Opαq (Theorem 1) Bias is V α `Opα 2 q (Theorem 2)High probability bound (Theorem 3)V is the solution of a linear system (Lemma 11)and averaging (Lemma 8)Figure 3 : Overview of the proof. The dashed rectangles indicate the lemmas that are proven in Appendix C.To compare the stochastic variable θ n and the solution of the ODE 9 ϑ " f pϑq, we introduce a deterministic recurrence equation, that is a first-order discretization of the ODE. This recurrence equation is obtained by replacing the sources of randomness of (1) by their expectation. The stochastic approximation (1) contains two sources of randomness: M n`1 and X n . In our analysis, we will use a deterministic counterpart of (1) that corresponds to setting the noise M n`1 to 0 and to using f pθq instead of f pθ n , X n q. More precisely, for an initial value θ P Θ and k P Z `, we define φ n pθq as:EQUATIONwith the convention that φ 0 pθq " θ.Let h : Θ Ñ R be an arbitrary function. By using the definition of the deterministic recurrence, for any k P t0 . . . nu, we introduce the variableEQUATIONThe quantity z n,k is the expected value of a recurrence at time n if one starts by applying the stochastic recurrence for the first k steps and then the deterministic recurrence for the remaining n´k steps. Our proof method consists in obtaining precise bounds on the difference E rθ n s ´E rφ n pθ 0 qs. By using the notation z n,k , this quantity is equal to z n,n ´zn,0 . To obtain a bound on this quantity, we will use a trick, that essentially consists in comparing z n,k`1 ´zn,k . This quantity is simpler to analyze because the only modification between the two is to replace one stochastic transition by one deterministic transition. We can then recover the original bound by using that:EQUATION)This method is illustrated in Figure 4 on a synthetic example whose parameters are given in Appendix A.3. In the right panel, plot two functions (for two different values of k) that are equal to θ n for k ď n and to φ n´k pθ k q for k ą n. n k( k) if n > k or k for n < k n k( k) for k = 75 n k( k) for k = 100 (a) Stochastic vs deterministic recurrences (b) Impact of changing k in φ n´k pθ k qFigure 4 : Illustration of the behavior of θ n , φ n pθ 0 q and φ n´k pθ k q.pαq n and of V by comparing the generators Using the above notations, we are now ready to prove the first proposition.Proposition 4. Assume (A1)-(A4). Then, there exists a constant C ą 0 and α 0 such that for all n, α ď α 0 and all h P C 3 ď1 pΘ, Rq: ˇˇE rhpθ n q ´hpϕ nα pθ 0 qqs ´αV pαq n ˇˇď Cα 2 ,where the quantity V pαq n is given by:V pαq n :" n´1 ÿ k"0 E " Dph ˝φn´pk`1q qpθ k qpf pθ k , X k q ´f pX k qq ´D2 ph ˝φn´pk`1q qpθ k q `pf pθ k , X k q ´f pX k qq b2 `Qpθ k , X k q ˘ı. Moreover, V pαq nis bounded independently of α and n.Proof. Following the definition of the stochastic and deterministic recurrences, the difference z n,k źn,k`1 that appears in (10) is equal toEQUATIONIf g : R d Ñ R is a thrice differentiable function whose third derivative is bounded by › › D 3 g › › , by using a Taylor expansion, we have that gpx`aq´gpx`bq " Dgpxqpa´bq`D 2 gpxqpa´bq b2 `R, where R is a remainder term that is smaller than c 6 }a ´b} 3 . In our proof, we use this Taylor expansion with the function g " h˝φ n´pk`1q , x " θ k , a " αpf pθ k , X k q`M k`1 q and b " α f pθ k q.Applying this to (11) shows thatEQUATIONwhere A n,k and B n,k are equal toA n,k :" E " Dph ˝φn´pk`1q qpθ k qpf pθ k , X k q `Mk`1 ´f pX k qq ‰ B n,k :" E " D 2 ph ˝φn´pk`1q qpθ k qpf pθ k , X k q `Mk`1 ´f pX k qq b2 ‰ , and R n,k is a remainder term.By assumption (A1), the conditional expectation and variance of the martingale term are equal toE rM k`1 | F k s " 0 and E " M b2 k`1 | F k ‰ " Qpθ k , X k q.By using the total law of expectation, this shows that A n,k and B n,k can be simplified as:A n,k :" E " Dph ˝φn´pk`1q qpθ k qpf pθ k , X k q ´f pX k qq ‰ B n,k :" E " D 2 ph ˝φn´pk`1q qpθ k q `pf pθ k , X k q ´f pX k qq b2 `Qpθ k , X k q ˘‰ .By definition, V pαq n " ř n´1 k"0 pA n,k `αB n,k {2q. Hence, combining this with (10) shows thatE rhpθ n q ´hpϕ nα pθ 0 qqs " V pαq n `n´1 ÿ k"0 R n,k .To complete the proof, it remains to be shown that there exists a constant such that ř n´1 k"0 R n,k ď Cα 2 and that V pαq n is bounded independently of α and n. There are three terms, corresponding to R, B, andř n k"1 A n,k : Case of R.In Lemma 6, we show that the norm of the derivatives of h ˝φn´k are smaller than c 1 e ´c2αpn´kq . As the derivatives of h are bounded by 1, this implies there exists c independent of α and n such that › › D 3 ph ˝φn´k q › › ď ce ´c2αpn´kq . Hence, there exists c 1 ą 0 such that:n´1 ÿ k"0 }R n,k } ď c 1 α 3 n´1 ÿ k"0 e ´c2αpn´kq ď c 1 α 3 8 ÿ k"0 e ´c2αk ď c 1 c 3 α 2 .Case of B. The proof that ř n k"1 αB n,k is bounded independently of n and α is similar since the factor α cancels out with the factor 1{α that comes out of ř 8 k"0 e ´c2αk . Case of A Showing that ř n k"1 A n,k is bounded independently of n and α is more subtle and uses the fact that f is the "averaged" version of f with respect to the transition kernel K. The proof of this is a consequence of the first point of Lemma 8 that is stated in Section C.The proof of the main results is then a consequence of the next proposition, whose proof is given in Appendix B. This proposition shows that the Cesaro limit of V pαq n is approximately equal to a term V that does not depend on α plus a term of order Opαq. Proposition 5. Assume (A1)-(A4). Then, there exist a constant C ą 0 and α 0 ą 0 such that for all h P C 5 ď1 pΘ, Rq, there exists a vector V such that for all n, α ď α 0 :ˇˇV pαq n ´V ˇˇď Cpα `1 nα q, where V pαq n :" n ´1 ř n k"1 V pαq k with V pαq kas in Proposition 4. 
conclusion / discussion: 
 In this paper, we presented an analysis of the bias of constant-step size algorithms with Markov noise. We developed a novel technic, based on generator comparison, that allows to obtain a very fine comparison between the expectation of the stochastic trajectory and the value of its deterministic counterpart. This methodology is quite generic and we believe that it could easily be adapted to obtain more general results. We are in particularly targeting: relaxing the bounded of Θ, and obtaining non-asymptotic results.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA]Justification: The paper does not contain numerical experiments but only small numerical illustrations of theorems.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [NA] Justification: The numerical illustration are very limited (less than a few minutes of computation time in total). This is mentioned in the text. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: The paper is a theoretical paper and its direct ethical implications seem limited.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: The paper is a theoretical paper and there is no direct broader impact. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? 
 
 Appendix: All parameters given in this section should suffice to reproduce all figures. The total computation time to obtain all figures of the paper does not exceeds a few minutes (on a 2018 laptop, all implementation being done in Python/Numpy/Matplotlib). To ensure reproducibility, the code necessary to reproduce the paper (including latex, code to run the simulations and code to plot the figures) is available at https://github.com/ngast/paper_bias_stochastic_approximation2024.A.2 Parameters for the example of Figure 1 and Figure 2 For Figure 1 and 2, the state space of the Markovian part is X " t0, 1u, and the transition matrix isKpθq " ˆsinpθq 2 cospθq 2 cospθq 2 sinpθq 2 ˙.The drift is f pθ, xq " θ ´2x. The martingale noise M n`1 is a sequence of i.i.d. random variables with P pM n`1 " 1 | F n q " P pM n`1 " ´1 | F n q " 0.5. One can show that θ ˚" 1. The initial value of the algorithm is set to θ 0 " 3, X 0 " 0.In Figure 5 , we complete the results of Figure 1 by showing more values of α. We observe that in all cases, the averaged values θn and θn{2:n are much close to θ ˚" 1 than the original θ n that is very noisy. This explain why using a Polyak-Ruppert averaging is important. Also, if for large values of α P t0.02, 0.01, 0.005u, the two quantities θn and θn{2:n have similar behavior, the situation is quite different when α gets smaller. In the latter case, the convergence of θn{2:n is much faster than the one of θn because of the transient behavior of θ n at the beginning. This is why we use θn{2:n in our simulations. A.3 Parameters for Figure 4 For Figure 4 , the state space of the Markovian part is X " t0, 1u and the transition matrix is Kpθq " ˆ0.5 0.5 0.5 0.5The drift is f pθ, xq " 1 ´p1 `θqx. The initial state is θ 0 " X 0 " 0 and there is no martingale noise 4 . The step-size is set to α " 0.05.A.4 Why is Theorem 1 for θ n and Theorem 2 and 3 for θn ?Note that compared to (4) of Theorem 1, the result of ( 5) in Theorem 2 is stated for the averaged iterates 1 N ř N n"1 E rθ n s and not directly for θ n . In fact, there are many cases for which ( 5) is also valid for θ n . In particular, if E rhpθ n qs converges as n goes to infinity, then one necessarily has:lim sup nÑ8 |E rhpθ n qs ´hpθ ˚q ´αV | ď α 2 C 1 .This is for instance the case if pθ n , X n q is an ergodic Markov chain. Yet, there are cases for which the result of (5) only holds for the averaged iterates. This occurs typically when X n has a periodic behavior, in which case the averaged iterates eliminate eventual oscillations caused by periodic noise sequences. To illustrate this, we consider a one-dimensional model with f pθ, xq " 2x ´θ, X n`1 " 1 ´Xn and M n`1 " 0. This model satisfies all assumptions of the problems and θ ˚" 1. The initial conditions are set to θ 0 " 0.85, and X 0 " 0. The system is therefore deterministic. In Figure 6 we plot the trajectories of θ n and of θpαq N :" 1 N ř N n"1 θ n for two stepsize values: α " 0.05 and α " 0.1. We observe that, as stated by Theorem 1, the smaller is α, the closer is lim nÑ8 θ n from θ ˚. One can also observe that pθ n ´1q{α oscillates and does not converge as n goes to infinity, contrary to p θn ´1q{α that does converge (to 0 here). In this section, we prove Proposition 5 that states, that under(A1)-(A4), there exist a constant C ą 0 and α 0 ą 0 such that for all h P C 5 ď1 pΘ, Rq, there exists a vector V such that for all n, α ď α 0 :ˇˇV pαq n ´V ˇˇď Cpα `1 nα q, where V pαq n :" n ´1 ř n k"1 V pαq k with V pαq kas in Proposition 4.This proposition shows that the Cesaro limit of the constants V pαq n defined in Proposition 4 converges to a limit that is equal to V `Opαq. In particular, this result implies thatE « 1 k n ÿ k"1hpθ n q ff " hpθ ˚q `αV `Opα 2 `1 nα q.Proof of Proposition 5. Recall from the proof of Proposition 4 thatV pαq n " ř n´1 k"0 E rA n,k `αB n,k {2s.We first treat the term ř n´1 k"0 B n,k that is the easiest (essentially because it is multiplied by a factor α).Applying Lemma 8 to the function gpθ, Xq :" pf pθ, Xq ´f pXqq b2 `Qpθ, Xq shows that:n´1 ÿ k"0 E rB n,k s " n´1 ÿ k"0 E " D 2 ph ˝φn´pk`1q qpθ k qgpθ k , X k q ‰ " n´1 ÿ k"0 E " D 2 ph ˝φn´pk`1qq qpθ k qḡpθ k q ‰ `Op1q.By applying Theorem 1, this shows thatEQUATIONwhere ḡpθq "ř xPX π x pθq `pf pθ, xq ´f pxqq b2 `Qpθ, xq ˘.The treatment of A n,k requires more work, and in particular one can show that ř n´1 k"0 A n,k does not necessarily converge as n goes to infinity 5 . This is why we study the convergence of ĀN " ř N n"1 ř n´1 k"0 A n,k and not the one of A n,k . By applying Lemma 10 with g " f and then applying Theorem 1, it holds that lim N Ñ8 ˇˇĀ N `αmpθ ˚qˇď Cα, with mpθ ˚q equal tompθ ˚q " ÿ x,x 1 PX 8 ÿ n"0DpDph ˝ϕn qpθ ˚qG f pθ ˚, x 1 qqpf pθ ˚, xq `Rpθ ˚, x, x 1 qqK x,x 1 pθ ˚qπ x pθ ˚q Note that to apply Theorem 1, we need m to be three times differentiable which is why we need h to be four times differentiable. Let V pαq " αp ř 8 k"0 D 2 ph ˝φk qpθ ˚qḡpθ ˚q `mpθ ˚qq. By using Lemma 11, there exists a vector V such that › › V pαq ´V › › ď Cα.Fix some i P t1 . . . du and let Y n :" pθ n ´θ˚´α V q i , be the ith component of the vector where the constant V is the one defined in Proposition 5 when applied to the function hpθq " θ ´θ˚. By Proposition 4 and Proposition 5, there exists C ą 0 such that for n large enough:1 n n ÿ k"1 E rY k s ď Cpα 2 `1 αn qIt is easy to modify the proofs of those propositions (by adding a conditioning on F mK and starting the summation at mK `1) to show that for all K and for m large enough:1 K pm`1qK ÿ k"mK`1 E rY k | F mK s ď Cpα 2 `1 αK q. Let Z m " 1 K ř pm`1qK k"mK`1 Y m .The above result shows that ř M m"1 Z m ´CM pα 2 `1 αK q is a supermartingale. Moreover, as Θ is bounded, there exists C 1 ą 0 (independent of C and α) such that |Z n ´Cpα 2 `1 αK q| ď C 1 (almost surely). Hence, by using Azuma-Hoeffding inequality, for all ε:P ˜1 M M ÿ m"1 Z m ě Cpα 2 `1 αK q `ε¸ď e ´M ϵ 2 {C .By setting K " 1{α 3 , ε " Cα 2 , and taking the limit as M goes to infinity, this implies that:lim M Ñ8 P ˜1 M M ÿ m"1 Z m ě 3Cα 2 ¸" 0. By using that 1 n ř n k"1 Y k " 1 M ř M m"1 Z m `Op1{Mq, with M " tM {Ku, it follows that for all P t1 . . . du:lim nÑ8 P `pθ n ´pθ ˚`αV qq i ě 3Cα 2 ˘" 0.A symmetric proof shows that lim nÑ8 P `pθ n ´pθ ˚`αV qq i ď ´3Cα 2 ˘" 0. The theorem then follows by using a union bound on all i.This shows that the constant of Theorem 3 can be chosen as C 2 " 3C where C is the constant of Theorem 1. By choosing more carefully the values of K and ε, this constant can be reduced to C 2 " p1 `δqC for all δ ą 0.This section contains the technical lemmas that are used in the proof of the main theorems. This section is divided in two parts. We first show in Lemma 6 that the derivatives of φ n are exponentially small as n goes to infinity. Using this exponential convergence, we then prove Lemma 7 that provides bound for an almost telescopic sum that appears in the proof of Lemma 8. The latter shows how to bound the difference between f pθ n , X n q and f pθ n q by using a Poisson approach.The first lemma is at the core of our analysis. It shows that if the ODE has a unique attractor (as imposed by (A4)), then for α small enough, the derivatives of the discrete-time recurrence φ n are exponentially small as n goes to infinity.. There exist α 0 ą 0 and constants c 1 , c 2 , c 3 , c 4 ą 0 such that for all α ă α 0 , i P t1, 2, 3u and n, (i) ř 8 n"0 e ´c2αn ď c 3 {α. (ii) For all h P C i ď1 pΘ, Rq, the ith derivative of h ˝φn satisfies:› › D i ph ˝φn q › › ď c 1 e ´c2αn ,Proof. The proof of (ii) is just a comparison between a sum and an integral. Indeed, as x Þ Ñ e ´x is decreasing, one have:1 c 2 " ż 8 0 e ´c2x dx " 8 ÿ k"1 ż kα pk´1qα e ´c2x dx ě 8 ÿ k"1 αe ´c2αk .This shows that:8 ÿ k"0 e ´c2αk " 1 `8 ÿ k"1 e ´c2αk " 1 `1 c 2 α " pα `1 c 2 qα.This concludes the proof by setting c 3 " pα 0 `1{c 2 q.To prove (ii), let us first prove the result for the first derivative (i " 1). By Assumption (A4), all trajectories of the ODE 9 ϑ " θ converge to the fixed point θ ˚and the Jacobian H :" D f pθ ˚q is Hurwitz. By classical results [7] on the discretization of ODE 6 , this implies that, for α small enough, the discretization φ n pθq converges exponentially fast to θ ˚, that is: there exists α 0 ą 0 and a, b such that for all α ă α 0 and θ P Θ: }φ n pθq ´θ˚} ď ae ´c2αn . Using this and the fact that f is twice continuously differentiable in θ ˚implies the existence of a 1 such that:EQUATION)Recall that the definition of φ n in Equation ( 8) implies that φ n`1 pθq ´φn pθq " α f pφ n pθqq with φ 0 pθq " θ. Hence, as f is differentiable with respect to its initial condition, by using the chain rule, the derivative of φ n`1 exists and satisfies:EQUATION)To simplify notation, let use denote by X n`1 :" Dφ n`1 pθq (the above equation is X n`1 ´Xn " αX n D f pφ n pθqq), and let us compute7 X n`1 pI `αHq ´pn`1q . By adding a substracting the term X n pI `αHq ´n, it holds that:X n`1 pI `αHq ´pn`1q " X n`1 pI `αHq ´pn`1q ´Xn pI `αHq ´n `Xn pI `αHq ´n " pX n`1 ´Xn pI `αHqqpI `αHq ´pn`1q `Xn pI `αHq ´n " αX n pD f pφ n pθqq ´HqpI `αHq ´pn`1q `Xn pI `αHq ´n,where we used (15) for the last line.By using that the last term X n pI `αHq ´n corresponds to the X n`1 pI `αHq ´pn`1q where we replace n `1 by n, a direct induction shows thatX n`1 pI `αHq ´pn`1q " α n ÿ k"1 X k pD f pφ k pθqq ´HqpI `αHq ´pk`1q .Multiplying this equation by pI `αHq n`1 implies that:EQUATION)By using (15) , and denoting x n`1 :" }X n`1 }, it holds thatx n`1 ď α n ÿ k"1x k a 1 e ´c2αk a 1 e ´c2αpn´kq " αpa 1 q 2 e ´c2αn n ÿ k"1EQUATION)To conclude, let y n`1 :" αpa 1 q 2 ř n k"1 y k e ´c2αk with y 0 :" x 0 . It can be shown by induction on k thatx n ď e c2αk y k . Moreover, we have: y n`1 " αpa 1 q 2 y n e ´c2αn `yn " y n p1 `αpa 1 q 2 e ´c2αn q " n ź k"1 p1 `αpa 1 q 2 e ´c2αk q.By using the concavity of the log, we have that:log n ź k"1 p1 `αpa 1 q 2 e ´c2αk q " n ÿ k"1 logp1 `αpa 1 q 2 e ´c2αk q ď n ÿ k"1 αpa 1 q 2 e ´c2αk .By using the point (i), the last quantity is bounded by some quantity d. This shows that x n ď de ´c2αn .The proof of the higher derivatives (case i ě 2) are very similar to the proof for the first derivative i " 1 and we only give an overview. For the second derivative, differentiating (15) with respect to θ gives:D 2 φ n`1 pθq ´D2 φ n pθq " αD 2 φ n pθqD f pφ n pθqq `αpDφ n pθq, Dφ n pθqq ¨D2 f pφ n pθqq.For a given g : Θ ˆX Ñ R, we say that the function G g : Θ ˆX Ñ R is a solution of the Poisson equation if it satisfies ÿ yPX K x,y pθqpG g pθ, xq ´Gg pθ, yqq " gpθ, xq ´ḡpθq,with ḡpθq " ř x π x pθqgpθ, xq as before. It is shown in [1, Lemma 4 ] that under assumption (A3), for each g, there exists such a function G g . Moreover, under the regularity assumption (A2), this same lemma shows that the function G g can be chosen to be four times differentiable and that is derivatives satisfy› › D ďi G g › › " Op › › D ďi g › › q. Lemma 8. Assume (A1)-(A4).Then, there exists a constant C ą 0 and α 0 such that for all n, α ď α 0 and all i P t1, 2, 3u, h P C i ď1 pΘ, Rq and g P C 0 ď1 pΘ, Rq:EQUATIONProof. To lighten the notations, we consider the case i " 1, the proof holds for i ą 1 by replacing Dph ˝φq by D i ph ˝φq. By adding and subtracting some terms, the quantity ( 22) is equal to the expectation ofEQUATIONEQUATIONWe examine the three lines separately:• By using the fact that X k`1 makes a Markovian transition (2), and by using the definition of G h px, yq, we get:E rG g pθ k , X k q ´Gg pθ k , X k`1 q | F k s " ´ÿ y 1 Kpθ k q X k ,y 1 G g pθ k , y 1 q " ´pgpθ k , X k q ´ḡpθ k qqfrom which follows that the expectation of ( 23) is equal to zero.• To bound Equation ( 24), we use the definition (1) of θ k`1 to implies that there exists a constant C ą 0 such that |θ k`1 ´θk | ď Cα. By using that G g is Lipschitz-continuous (see [1, Lemma 4] ) and that the norm of the derivative of h ˝φn´k is bounded by c 1 e ´c2pn´kqα (Lemma 6), this shows that there exists c 1 ă 8 such that:E « n´1 ÿ k"0 }Dph ˝φn´k´1 qpθ k q pG g pθ k , X k`1 q ´Gg pθ k`1 , X k`1 qq} ff ď c 1 α 8 ÿ k"0 e ´c2kα ď c 3 c 1 .• The fact that the expectation of ( 25) is bounded is a direct consequence of Lemma 7 applied with g " G g and the fact that }DG g } " Op}Dg}q.This conclude the proof.The next two lemmas prove properties of the average sums that refine the analysis of Lemma 8.They are used to study the term A n in the proof of Proposition 5.Lemma 9. Assume (A1)-(A4). Then, there exists a constant C ą 0 and α 0 such that for all n, α ď α 0 :EQUATION@ℓ P C 2 ď1 pΘ, Rq :EQUATIONwhere m " ř x,x 1 PX DG ℓ pθ, x 1 qpf pθ, xq `Rpθ, x, x 1 qqK x,x 1 pθqπ x pθq.Proof. By applying the same trick as for ( 23)-( 25) in the one of Lemma 8 but replacing D i ph φn´pk`1q qpθ k q by 1{n, the left-hand-side of ( 26) is equal to the expectation ofEQUATION)where there is no equivalent of ( 23) because we already use that the expectation of this term is 0.In (28) , each element of the first sum is Opαq by using a Taylor expansion of G ℓ and using that }DDG ℓ } " Op}Dℓ}q. Hence the first term is of order Opαq. The second sum is telescopic. As it is multiplied by 1{n, this leads to the term Op1{nq of (26) . Combining both leads to (26) .To obtain (27) , we refine the analysis of the first term of (28) . By using a Taylor expansion on theEQUATION)By definition, }θ k`1 ´θk } 2 is of order α 2 .Let mpθ, xq " ř x 1 PX DG ℓ pθ, x 1 qpf pθ, xq `Rpθ, x, x 1 qqK x,x 1 pθq. By using the law of total expectation,E rDG ℓ pθ k , X k`1 qpθ k ´θk`1 qs " ´αE rDG ℓ pθ k , X k`1 qpf pθ k , X k q `Mk`1 qs " ´αE rE rE rDG ℓ pθ k , X k`1 qpf pθ k , X k q `Mk`1 q | F k ^Xk`1 s | F k ss " ´αE rmpθ k , X k qs .By using (26) with the function m instead of ℓ, we obtain that 1 n ř n´1 k"0 E rmpθ k , X k q ´mpθ k qs ď Cpα `1{nq. This shows that the first term of ( 28) is equal to α ř n´1 k"0 mpθ k q plus a term of order Cpα 2 `α{nq. As the term Op1{nq from the telescopic sum of the second term of (28) dominates the term α{n, this implies (27) .Lemma 10. Assume (A1)-(A4). Then, there exists a constant C ą 0 and α 0 such that for all n, α ď α 0 , h P C 4 ď1 pΘ, Rq and g P C 3 ď1 pΘ, Rq:ˇˇˇˇ1 N N ÿ n"1 n´1 ÿ k"0 Dph ˝φn´pk`1q qpθ k qpgpθ k , X k q ´ḡpθ k qq ´N´1 ÿ k"0 mpθ k q ˇˇˇˇď C ˆα `1 N α 2 ˙,where the function m is equal tompθq " ÿ x,x 1 PX 8 ÿ n"0 D `Dph ˝ϕn qpθqG g pθ, x 1 q ˘`f pθ, xq `Rpθ, x, x 1 q ˘Kx,x 1 pθqπ x pθq.with H p2q ¨pI `αH p1q q j OpI `αpH p1q q T q j " ř m,n H p2q i,mn `pI `αH p1q q j OpI `αpH p1q q T q j ˘m,n . Consequently, for ř 8 k"0 D 2 φ k ¨O the above yieldsα 8 ÿ k"0 k ÿ j"1pI `αH p1q q k´j αH p2q ¨pI `αH p1q q j OpI `αpH p1q q T q j " α8 ÿ j"1 8 ÿ k"jpI `αH p1q q k´j αH p2q ¨pI `αH p1q q j OpI `αpH p1q q T q j " α 8 ÿ j"1 8 ÿ k"0 pI `αH p1q q k αH p2q ¨pI `αH p1q q j OpI `αpH p1q q T q j " α 8 ÿ j"1 pαH p1q q ´1αH p2q ¨pI `αH p1q q j OpI `αpH p1q q T q j " pαH p1q q ´1αH p2q ¨pI `αH p1q q ´α 8 ÿ j"0 pI `αH p1q q j OpI `αpH p1q q T q j ¯pI `αpH p1q q T q " pαH p1q q ´1αH p2q ¨pI `αH p1q qW pαq pI `αpH p1q q T q " pH p1q q ´1H p2q ¨W pαq `αC 1 , with C 1 " `pH p1q q ´1H p2q ¨`H p1q W pαq `W pαq pH p1q q T `αH p1q W pαq pH p1q q T ˘˘which is bounded by assumption. Using the previously discussed difference between W and W pαq , we conclude that pH p1q q ´1H p2q ¨W is an approximate solution to ř 8 k"0 D 2 φ k ¨O with error of order α.Justification: There is no dataset used.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material.Justification: There are no models or data released.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Justification: There is no significant code, data or model used.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.38th Conference on Neural Information Processing Systems (NeurIPS 2024).We call a probability matrix unichain if the corresponding Markov chain has a single recurrent class and, possibly, some transient states.Note that if our theoretical results are presented for θn, they can be readily extended to θn{2:n .We only plot the error of θn{2:n because it has the same limit as θn but converges faster.Note that because of the form of the matrix Kpθq, the process Xn is memoryless. Hence, one could build the same model with a martingale noise instead of the variable X.This is illustrated by FigureTo see why this is true, one should remark that, because H is Hurwitz, there exists c ą 0 and α ˚0 such that for all α ď α0, the eigenvalues of I `αH have a modulus smaller than 1 ´αc. This implies that the recurrence equation θn`1 " θn `α f pθnq is exponentially stable around θ ˚. The uniform bound for all θ P Θ comes from the fact that Θ is compact.We compute this quantity to solve (15) by using a technique similar to the change of variable method. 


Decision: This paper considers stochastic approximation (SA) under Markovian noise and constant step-size, which is commonly employed in practice. Authors rely on
the generator of the process to study the bias of SA algorithm, and derive its order
under smoothness conditions. Authors also provide bias orders for the Polyak averaged iterates, and extensions involving Richardson-Romberg extrapolation.


This paper was reviewed by three expert reviewers w/ the following Scores/Confidence: 5/3, 7/4, 5/4. I think the paper is studying an interesting topic and the results are relevant to NeurIPS community. The following concerns were brought up by the reviewers:

- The main results in this paper are asymptotic. The non-asymptotic versions should be clearly stated in discussion/conclusion section as future work.
  
- Better discussion connecting this work to the existing literature is needed.
  
- Authors should discuss how restrictive their conditions are.


Authors should carefully go over reviewers' suggestions and address any remaining concerns in their final revision. Based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend including this paper to the NeurIPS 2024 program.

Reviews: review: paper_summary: paper_summary: The paper studies non-linear stochastic approximation scheme ($\theta_n$) driven by a uniformly geometrically ergodic MC $(X_n)$. Moreover, it is allowed the evolution of the Markovian noise $X_n$ to depend on $\theta_n$.  The authors study the asymptotic behaviour of the last iterate, Polyak-Ruppert and Richardson-Romberg procedures for differentiable test functions. The result generalizes recent result of Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and markov chains. The Annals of Statistics, 48(3):pp. 1348–1382, 2020.
strength_weakness: strength_weakness: - It would be good to provide non-asymptotic results rather than asymptotic
- I think that the result of theorem 3 is very weak since it is obtained using Chebyshev’s inequality. Could you please comment on $\alpha^{5/4}$ term?
questions: questions: - I think it is better to give a definition of a unichain.
- Is it possible to relax conditions of the theorems? For example, what will be if we reduce the number of derivatives in Th 2? Is it true that in this case one will obtain \alpha^{3/2} in the remainder term? Is it possible to achieve this using the suggested technique?
limitations: limitations: -
paper_summary: paper_summary: This paper studies the asymptotic bias in non-linear stochastic approximation algorithms with Markovian noise and fixed step-size. Upon applying the averaging technique of Polyak and Ruppert, the authors identify that, in general, the bias is of the same order of the step-size. The main source of bias is characterized, and an extrapolation technique is employed so that bias is attenuated. Finally, a few numerical studies are presented for illustration of the theoretical contributions.
strength_weakness: strength_weakness: In particular, there have been recent papers, achieving similar bias characterizations and higher order error bounds for stochastic approximation with Markovian noise (see for example [R1] and [R2] which both deal with linear recursions). The approach to analysis in [R2] is similar to the present paper in the sense that the bias characterization is also given in terms of solutions to Poisson's equations. Moreover, this is not the first time that Richardson-Romberg extrapolation is used for bias attenuation in stochastic approximation: it was previously proposed in [R1] to kill the dominant term of order O(\alpha) just like the present paper.

The authors do cite [R1] in the present work, but the reviewer feels that a deeper discussion is needed on how the present paper improves upon [R1] and [R2]. I encourage the authors to include a citation on previous uses of this technique as well.


[R1] Huo, Dongyan, Yudong Chen, and Qiaomin Xie. "Bias and extrapolation in Markovian linear stochastic approximation with constant stepsizes." Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. 2023.

[R2] Lauand, Caio Kalil, and Sean Meyn. "The curse of memory in stochastic approximation." 2023 62nd IEEE Conference on Decision and Control (CDC). IEEE, 2023.
questions: questions: - Is it possible to relax the assumption that the parameters remain within the compact set \Theta with probability one?   It seems likely that the authors can obtain their results subject to a moment bound, which I believe is more realistic based upon standard SA stability theory.

- One thing that sets this paper apart from others is that they allow Markovian noise that is parameter dependent.   This is extremely valuable in RL applications such as Q-learning (for example, epsilon-greedy policies induce such a model), and actor-critic methods.  Could the authors provide more discussion regarding applications in which the Markovian noise is parameter dependent?

-Could the authors clarify whether the experiments display in Figure 1 (a) and (b) pertain to the same run? It is hard to identify the improvement between RR exploration and the regular algorithm for the choice of \alpha =0.01. I encourage the authors to include sample paths for \alpha =0.01 and \alpha =0.005 instead of the \alpha =0.0025 for visualization.
limitations: limitations: The authors discuss the limitations of their work and assumptions in section 3.3.
paper_summary: paper_summary: This paper studies stochastic approximation with constant stepsize and Markovian noise. The authors provide a characterization of the bias (i.e., the difference between the expectation of the iterate and the desired limit), show that Polyak-Ruppert averaging can help reduce the variance but not the bias, and numerically demonstrate that Richardson-Romberg extrapolation helps reduce the bias.
strength_weakness: strength_weakness: (1) Assumption (A2) is relatively strong and difficult to verify in practice.

(2) The authors claim that Assumption (A4) implies the global exponential stability of the ODE, but did not provide a reference for the claim. Also, the claim in lines 466-471 needs formal justification.
questions: questions: Both theorems require $h$ to be uniformly bounded by a constant. This is not true even for $h(\theta)=\theta$, which corresponds to bounding the expectation of $\theta_n$. Am I missing something?
limitations: limitations: The results are mostly asymptotic. A characterization of the stochastic approximation algorithm behavior for a finite $n$ would be preferred for practical purposes.

Comments: title: Is there a rebuttal?
h(theta)=theta is ok
answers to comments
answer on hiw to obtain more general results
comment: Thank you for your comments. Our plan for the funak version is to:
- add a formal statement about unbounded theta. 
- add more numerical experiments as suggested.
I thank the authors for their response. I retain my current score.
I would like to thank the authors for their responses. 

**Bounded theta** Given that a moment bound on theta could replace the current assumption that theta lives in a compact set, I encourage the authors to modify that in the final version ( or at least provide some discussion on that) so that the assumptions of the paper are more realistic.

**Figure 1** I understand that a lower value of $\alpha$ might lead slower convergence, but I believe that the current plot is not helpful in showing the improvement between RR exploration and the regular algorithm. In encourage the authors to use a larger value of $\alpha$ so that a plot with $\alpha^2$ (without RR exploration) could be displayed and compared to the extrapolated estimates without much worry on convergence rates.
The rebuttal was kept very short and should be visible to all. There are answers to specific comments below each review (they were not visible to all before but they should be now).
I want to confirm if the authors have uploaded their rebuttal. I am not seeing it here.
In the question, the reviewer asks if using h(theta)=theta is ok because this function is not bounded. This function can indeed be used because we assume that theta remains bounded. Note that one could also replace this assumption by a weaker assumption on the moments (see the answer to rev 2).
- about bounded theta: the reviewer is correct by suggesting that we can replace the assumption of "bounded theta" by an assumption that would control the probability that theta is "far" from theta^*. For instance, a bound on the higher moment of theta would work. 

- about the markov noise being theta-dependent: thank you for your positive comments. We will discuss these motivating examples if the final version.

- Figure 1: yes, the runs of the two figures are the same (this is why the red curve is duplicated on the right panel, in order to have some comparison). Lower values of alpha tend to provide slower convergence rate, which is why they are not shown there.
Dear reviewer,

Thank you for your detailed ans positive review. Here are some answers to your comments / questions:

- yes, the bound of alpha^(3/4) of Theorem is probably not optimal. This Theorem could in fact be a called a corrolary of Theorem 2. Using a more advanced concentration inequality would probably require a bound on the exponential moment which are not direct from Theorem 2.

- unchain just means that the Markov component has a unique stationary for all parameter theta. We will precise that.

- the derivation of the bias term in alpha requires to have twice differentiable functions. Our proof could be adapted to show that if the functions are only twice differentiable, then the reminder term is a o(alpha). The alpha^(3/4) for 3 times differentiable functions is not direct from our analysis.

- about non asymptotic-results: some of our propositions are in fact non asymptotic but the main results are stated jn an asymptotically way to be cleaner.