Stochastic approximation (SA) algorithms use stochastic updates to iteratively approximate the solution to fixed-point equations. SA has wide applications, such as the stochastic gradient descent (SGD) algorithm for loss minimization and the Temporal Difference (TD) learning algorithm in reinforcement learning (RL) (Sutton 1988). Classical works on SA typically assume the stepsize sequence α t is squaresummable and diminishing, i.e., t α t = ∞, t α 2 t < ∞, under which asymptotic almost-sure convergence is well studied (Robbins and Monro 1951;Blum 1954;Borkar and Meyn 2000). Constant stepsize has gained popularity recently, particularly among practitioners, due to its fast initial convergence and easy hyperparameter tuning. A growing line of works studies the convergence properties of SA under constant stepsize, establishing upper bounds on the meansquared error (MSE) (Lakshminarayanan and Szepesvári 2018;Srikant and Ying 2019;Mou et al. 2020Mou et al. , 2021) ) as well as weak convergence results (Dieuleveut, Durmus, and Bach 2020;Yu et al. 2021;Huo, Chen, and Xie 2023a).
Recent works have explored using SA and SGD iterates to perform statistical inference, e.g., constructing confidence intervals (CIs) around a point estimate (Li et al. 2018;Chen et al. 2020;Li et al. 2022;Lee et al. 2022;Liu, Chen, and Shang 2023). This approach is computationally cheap and scales well with the size and dimension of the dataset: SA updates are computed iteratively, without storing or multiple passes over the dataset. In comparison, classical inference techniques, such as bootstrapping, often require storing the entire dataset and repeating the estimation procedure, which may have prohibitive computational costs.
The aforementioned works on using SA for inference have focused on the diminishing stepsize paradigm, for which a mature convergence theory exists, ensuring the asymptotic correctness of the inference results. In contrast, constant-stepsize SA lacks last-iterate almost sure convergence: recent works have shown that the iterates converge only in distribution; moreover, the limit distribution may have a nonzero asymptotic bias due to the nonlinearity of the SA updates (Dieuleveut, Durmus, and Bach 2020) or the underlying Markovian data (Huo, Chen, and Xie 2023a), and this bias cannot be eliminated by iterate averaging. Partly due to these considerations, inference with constant stepsize SA iterates has been largely overlooked in the literature.
We study the effectiveness of statistical inference using constant-stepsize SA iterates. We focus on linear stochastic approximation (LSA), i.e., θ t+1 = θ t + α(A(x t )θ t + b(x t )), with a constant stepsize α and Markovian data (x t ) t≥0 . We first establish a Central Limit Theorem (CLT) for averaged Markovian LSA iterates. Built upon the CLT, we outline an inference procedure using averaged iterates and batch-mean covariance estimates. Our procedure leverages the fast mixing property of constant-stepsize updates for better covariance estimation and employs Richardson-Romberg (RR) extrapolation for bias reduction. We study two stepsize schemes in RR extrapolation. We further prove that with Markovian data, the asymptotic bias may vanish in several important settings, in which case inference with constantstepsize LSA iterates is effective even without RR extrapolation. We conduct extensive experiments to benchmark our procedure against conventional inference approaches. Our results demonstrate superior and robust performance of the constant stepsize paradigm, which enjoys fast convergence, good coverage properties, and easy parameter tuning.foot_0
Dating back to Robbins and Monro (1951), classical works on stochastic approximation typically assume i.i.d. data and a square-summable and diminishing stepsize sequence. Subsequent works propose what is now known as the Polyak-Ruppert iterate averaging (Ruppert 1988;Polyak 1990) and establish a CLT for the averaged iterates (Polyak and Juditsky 1992). Recent work in Borkar et al. (2023) establishes a CLT for scaled iterates for general contractive SA under diminishing stepsize and Markovian data.
Constant-stepsize SA and SGD have attracted growing attention recently. Several works study constant-stepsize LSA with i.i.d. data and establish finite-time MSE bounds and a CLT for the average iterates (Lakshminarayanan and Szepesvári 2018;Mou et al. 2020). A parallel line of work studies SGD for both convex (Dieuleveut, Durmus, and Bach 2020) and nonconvex (Yu et al. 2021) functions with i.i.d. data and identifies an asymptotic bias arising from the nonlinearity of the function. More recent works study LSA with Markovian data. The works in Srikant and Ying (2019) and Durmus et al. (2023) study convergence bounds for MSE, while the work in Huo, Chen, and Xie (2023a) establishes weak convergence of the LSA iterates and characterizes its asymptotic bias due to Markovian data.
Most related to this paper is a recent line of work on using SGD/SA iterates for statistical inference. The work in Chen et al. (2020) considers SGD with i.i.d. data and strongly-convex functions and proposes two covariance matrix estimators. This result is generalized to φ-mixing data in Liu, Chen, and Shang (2023). The work in Zhu, Chen, and Wu (2023) extends the batch-mean estimator in Chen et al. (2020) to a fully online version. The work in Lee et al. (2022) proposes a random scaling covariance estimator for robust online inference with SGD. Subsequent work in Li, Liang, and Zhang (2023) investigates online statistical inference using nonlinear SA with Markovian data. The above works all consider diminishing stepsizes. The work in Xie and Zhang (2022) extends the random scaling estimator for inference with SA under constant stepsizes but i.i.d. data. The work in Li et al. (2018) studies statistical inference with SGD and i.i.d. data, using a small stepsize whose value remains constant throughout the iterations but scales inversely with the total number of iterations. In contrast, we consider constant stepsizes whose values are independent of the total number of iterations and thus substantially larger than the typical stepsize values in Li et al. (2018).
RR extrapolation is a classical technique from numerical analysis to improve approximation errors. It has been used in Dieuleveut, Durmus, and Bach (2020) for SGD and Huo, Chen, and Xie (2023a) for LSA. See the survey by Bach (2021) for the use of RR extrapolation in other data science and machine learning problems.
In this section, we formally set up the problem and introduce the assumptions. Let (x t ) t≥0 be a time-homogeneous stochastic process on a Borel state space X with stationary distribution π. Define the target vector θ * as the solution to the steady-state equation
where A : X → R d×d and b : X → R d are deterministic functions on X . To approximate θ * , we consider the following linear stochastic approximation iteraion:
where (α t ) t≥0 is the stepsize sequence. We focus on using a constant stepsize, i.e., α t ≡ α for all t ≥ 0. (We omit the superscript (α) when the stepsize is clear from the context.) We emphasize that the constant stepsize considered here is independent of the total number of iterations. This is different from the work in Li et al. (2018), which pre-specifies the total number of iterations T and uses a small fixed stepsize of the form α t = T -β , ∀0 ≤ t ≤ T for some β > 0.
We make the following standard assumptions. Assumption 1. (x t ) t≥0 is a uniformly ergodic Markov chain with transition kernel P and a unique stationary distribution π.
Assumpiton 1 is common in the literature on Markovian SA (Bhandari, Russo, and Singal 2021;Durmus et al. 2023;Huo, Chen, and Xie 2023a). Uniform ergodicity ensures that the distribution of x t converges geometrically to π from any initial distribution. For example, all irreducible, aperiodic, and finite state space Markov chains are uniformly ergodic. Assumption 2.
The Hurwitz condition is again standard and ensures the stability of a dynamic system (Srikant and Ying 2019;Durmus et al. 2023;Huo, Chen, and Xie 2023a). This assumption is satisfied in, e.g., SGD for minimizing strongly convex quadratics and the linear TD algorithm in RL.
Our first result is a CLT for averaged LSA iterates, which lays the theoretical foundation for the inference procedure developed later. To state the CLT, we recall a known result for constant-stepsize Markovian LSA: the data-iterate pair (x t , θ t ) converge weakly to a unique limit distribution, denoted by (x ∞ , θ ∞ ) ∼ µ (Huo, Chen, and Xie 2023a). Theorem 1 (CLT). Under Assumptions 1-2, there exists a threshold α 0 ∈ (0, 1) such that for all α ∈ (0, α 0 ), we have
where θT :
The proof is deferred to the appendix. Theorem 1 extends existing CLT results, which focus on either LSA with i.i.d. data (Mou et al. 2020;Xie and Zhang 2022) or SA with diminishing stepsize (Borkar et al. 2023). When using Markovian data (x t ) t≥0 , the iterate sequence (θ t ) t≥0 is no longer a Markov chain on its own. Instead, we need to consider the joint process (x t , θ t ) t≥0 , which is a time-homogeneous Markov chain thanks to the use of a constant stepsize, and build the CLT accordingly. Moreover, a number of existing
The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)
Markov Chain CLT results require a one-step contraction property of the form W p,q (µQ, νQ) ≤ γW p,q (µ, ν), where Q is the Markovian transition kernel, γ < 1 and W p,q is an appropriate Wasserstein distance between distributions (Xie and Zhang 2022). Our Markov chain (x t , θ t ) t≥0 does not enjoy such a nice one-step contraction property, and hence proving our CLT requires additional work.
We next present a statistical inference procedure using the averaged LSA iterates with constant stepsize and Markovian data. This procedure can be combined with RR extrapolation to construct confidence intervals for the target vector θ * .
It has been shown in Huo, Chen, and Xie (2023a)
∞ ] is biased with respect to θ * and admits expansion: i) , where B (i) are vectors independent from the stepsize α. Theorem 1 guarantees that the averaged iterates θT are asymptotically normal, but E[θ
∞ ]-θ * scales with α. To construct CIs with good coverage properties, it is important to reduce the asymptotic bias.
In light of the bias expansion, we can employ Richardson-Romberg (RR) extrapolation to reduce the asymptotic bias to a higher order polynomial of the stepsize α (Dieuleveut, Durmus, and Bach 2020;Bach 2021;Huo, Chen, and Xie 2023a). Specifically, we run the LSA update (1) with M constant stepizes A = {α 1 , . . . , α M } and compute a linear combination of the resulting iterates:
We carefully choose the coefficients {h m } to satisfy
Using the aforementioned expansion, one sees that the bias
We now describe the inference procedure, which follows from the procedure in Li et al. (2018) originally designed for i.i.d. data and a small stepsize.
Point Estimation and Batching Given a trajectory of (x t ) t≥0 sampled from a Markov chain, we run LSA with constant stepsize α and obtain iterates (θ
t=0 are considered as initial burn-in and are not used in the inference procedure. For the remaining iterates, we divide them equally into K batches of size n. Within each batch, we discard the first n 0 (≥ 0) iterates and compute the average of the remaining iterates:
(b+n)+n0 , . . . , θ
Hence, for the k-th batch, we compute the point estimator θ(α)
l . As such, we obtain a total of K batch-mean estimators { θ(α) k }, which will be used for statistical inference. Note that we only need to save the running average of each batch-mean estimator without the necessity to store the entire trajectory (θ
Before delving into the construction of CIs, we briefly remark on several design choices. The initial b iterates are considered as burn-in and are omitted, as these iterates are far away from stationarity, and thus may have substantial optimization errors. The first n 0 iterates of each batch are also discarded, to reduce the correlation of the remaining iterates across batches, i.e., in the order of exp(-αn 0 ).
Confidence Interval Construction Now that the CLT for the average iterates of Markovian LSA with constant stepsizes has been established, we construct estimators for
For variance estimation, we adapt an estimator that has been considered in Flegal and Jones (2010); Chen et al. (2020), and Xie and Zhang (2022) to our problem. Given { θ(α) k }, the variance estimator is computed as
It has been shown in Flegal and Jones (2010) that Σ is a consistent estimator of Σ * in Theorem 1 as n, K → ∞, Hence, for inference with LSA with stepsize α, for q ∈ (0, 1), we construct the
In subsequent experiments, we focus on 95% CIs.
Next, we apply RR extrapolation in addition to the abovedelineated procedure to construct confidence intervals that have better coverage properties of θ * .
To apply RR extrapolation, we first select a set of M distinct stepsizes, i.e., A = {α 1 , α 2 , . . . , α M } and run LSA iterates with these stepsizes simultaneously by using the same underlying data stream (x t ) t≥0 . For each trajectory of iterates (θ (αm) t
) t≥0 , we follow the inference procedure and obtain K batch-mean estimators { θ(αm) k } K k=1 . To obtain the RR extrapolated estimator, we linearly combine the k-th estimates across the M trajectories and obtain
, with {h m } computed according to (2). We then conduct statistical inference using the iterates { θ A k } and build confidence intervals following the similar methodology described above for a single trajectory.
Next, we provide additional theoretical analysis that helps us achieve better statistical inference performance with RR extrapolated iterates. Please refer to the appendix for the proofs of propositions in this section.
As we discussed, one way to improve the coverage probability of θ * is to reduce the bias via RR extrapolation. However, RR extrapolation does not come for free, as the coefficients {h m } solving (2) may blow up, thus resulting in large variance and offsetting the benefits of bias reduction. {h m } values are uniquely determined by inverting a Vandermonde matrix, which is infamous for being ill-conditioned when the "roots" {α m } are positive real numbers. Therefore, when employing RR extrapolation, we need to carefully select M and {α m } to maximize the benefits of bias reduction.
We study two stepsize selection schedules, namely geometric decaying and equidistant sequences. We assume that α m decreases in value as m increases. We establish an upper bound to the variance of θ ∞ in each stepsize regime, which would offer some insight and guidance on stepsize selection.
The geometric decay schedule is not a conventional choice in numerical analysis, the field from which RR extrapolation originates, but it is frequently employed in machine learning. Proposition 2. Given unique stepsizes A = {α 1 , . . . , α M }. Assume α 1 < 1 and α m = α 1 /c m-1 with c ≥ 2. We observe the following properties.
) . It is noteworthy that the variance upper bound for geometric decaying stepsizes does not depend on the number of stepsizes M used in the extrapolation, suggesting that the variance will not blow up as M → ∞. Nonetheless, one problem with geometric decay is that the stepsize would decay too quickly to near zero as M increases. As such, RR iterates with a small constant stepsize mixes slowly and may need a much longer trajectory for the iterates to converge.
The equidistant decay schedule has been studied in numerical analysis (Gautschi 1990). We study the behavior of a generic equidistant decay schedule in RR exploration.
M -1 for m = 1, . . . , M. We observe the following properties.
). When the stepsize sequence decays in equidistance, stepsizes do not decrease as quickly to zero based on the choice of a, b. However, the upper bound of variance now is of order M M , which suggests that the variance could blow up quickly as M increases, potentially offsetting the benefits from reduced bias.
As discussed earlier, RR extrapolation reduces the asymptotic bias and hence increases the asymptotic coverage probability of θ * based on the CI constructed for E[θ ∞ ]. Hence, the Markovian underlying data and the presence of asymptotic bias should not discourage one from using constant stepsize LSA iterates for statistical inference.
In this section, we would like to highlight that Markovian data need not be a sufficient condition for the presence of asymptotic bias in LSA. That is, there are several commonly observed scenarios where no asymptotic bias is present, even when the underlying data is Markovian.
In this scenario, we expand our Markov chain state space to incorporate an independent bounded zero-mean random variable, i.e., x t = (s t , ξ t ), where (s t ) t≥0 is the uniformly ergodic Markov chain and (ξ t ) t≥0 is uniformly bounded, i.e., ξ t ≤ u, and i.i.d. sampled from distribution ξ with E[ξ] = 0. Consider the following Markovian LSA updates,
where A(s t , ξ t ) = Ā + ξ t and b(s t , ξ t ) = b(s t ). It can be easily verified that the above LSA iteration satisfies the required Assumptions 1-2. Proposition 4. Consider the LSA iteration of (3), there exists some threshold α 0 ∈ (0, 1) such that ∀α ∈ [0, α 0 ), (x t , θ t ) t≥0 converges weakly to a unique stationary distribution. Moreover,
The above proposition implies that when the Markovian noise is only additive, the limiting expectation of the iterates converges to θ * . Hence, our CLT on E[θ ∞ ] allows us to construct CI and perform statistical inference directly on θ * .
We consider an independent additive noise setting in linear regression, which has been previously discussed in Bresler et al. (2020) and Huo, Chen, and Xie (2023a).
In this linear regression problem, independent observations (s t ) t≥0 are sequentially generated from a uniformly ergodic Markov chain with stationary distribution ν and E ν [s t s t ] is positive definite. y t = s t w * + t , where t is an i.i.d. zero-mean noise with variance σ 2 . The SGD iterates to estimate w * are updated as w t+1 = w tαs t w t , s ty t .
Casting the problem under the LSA framework, we have w t+1 = w t + α(A(x t )w t + b(x t )) with x t = (s t , t ), A(x t ) = -s t s t and b(x t ) = s t (s t w * + t ). It has been shown in Huo, Chen, and Xie (2023a) that LSA under constant stepsizes has zero asymptotic bias in this setup.
Realizable Linear-TD Learning in RL In this section, we specialize our discussion on linear-TD learning in RL.
TD learning algorithm (Sutton 1988) is an important algorithm in RL for policy evaluation. Potentially equipped with linear function approximation, it is a special case of LSA.
We model the linear-TD problem with a Markov Reward Problem (MRP) (S, P S , r, γ). The value function V :
, where φ : S → R d is a known feature map of finite rank d and θ is the unknown weight vector to be estimated. The feature map is normalized such that φ max := sup s∈S φ(s) 2 ≤ 1 √ 1+γ . We consider the semi-simulator regime, in which the iterates are updated in the following fashion,
4) where (s t ) t≥0 is a Markov chain and s next t is sampled independently from P S (s t , •) conditioned on s t . Proposition 5. Assuming (s t ) t≥0 is a uniformly ergodic Markov chain on state space S with s 0 ∼ π S . Assuming the linear-TD is realizable, i.e., ∃v ∈ R d such that V (s) = φ(s) v for all s ∈ S. The linear-TD iterates of (4) converge without asymptotic bias, i.e.,
The realizability assumption is not particularly restricting, as there are a number of RL problems that satisfy this assumption, such as TD learning on tabular MDP or linear MDP. Hence, if we have such a structured linear-TD problem, we could use the iterates obtained in the semi-simulator setting to perform statistical inference on the weight vector θ estimation and subsequently the value function directly.
We conduct extensive numerical experiments to examine our proposed inference procedure and stepsize selection guidelines in RR extrapolation. We present our main results in this section. Additional sets of experiments and detailed experiment designs are included in the appendix.
We examine the empirical performance of our proposed inference procedure with constant stepsizes and RR extrapolation. We consider LSA problems in dimension d = 5 for a finite state, irreducible, and aperiodic Markov chain with N = 10 states. We generate the transition probability P , and the functions A and b randomly; see the appendix for details. We construct CIs using the LSA iterates. We examine the performance from three aspects, namely the ℓ 2 error of the point estimate to the target vector, i.e., θθ * 2 , the coordinate-wise CI width and coverage probabilities.
We mainly study under constant stepsizes α = 0.2 and α = 0.02. The two choices of constant stepsizes are of different scales, allowing us to demonstrate extreme effects in convergence and inference performance. RR extrapolation is conducted using the two constant stepsizes. For comparison, we also consider diminishing stepsizes with initial stepsize α 0 being 0.2 and 0.02 respectively, and a diminishing stepsize α t = α 0 t -0.5 for t ≥ 1. The diminishing rate t -0.5 is chosen as it is on the boundary of square-summable assumption and has often been observed with the best empirical performance among t -β with β ∈ [0.5, 1].
Baseline Comparison for I.I.D. LSA We first conduct a cross-study to examine the performance of inference with constant and diminishing stepsize under i.i.d. data. We notice that constant stepsizes slightly outperform the 0.2t -0.5 diminishing stepsize. Please refer to the appendix for detailed experiment design and results.
Performance Comparison for Markovian LSA We examine 100 different LSA problems of the same dimension |X | = 10 and d = 5. For each LSA setup, the parameters (P, A, b) are generated randomly, and we simulate 100 trajectories (x t ) t≥0 of length 10 5 , run LSA iterates with the above-described stepsize regimes, and perform inference. We summarize the distribution of the performance across the 100 cases in Table 1.
With Markovian data, the LSA with constant stepsize converges with nonzero asymptotic bias. The presence of bias is rather obvious when α = 0.2, evident from the large ℓ 2 error. Hence, CIs constructed with α = 0.2 iterates have the worst coverage probabilities. Reducing the stepsize to α = 0.02 will reduce the asymptotic bias, and hence CIs constructed with α = 0.02 iterates have significantly better performance.
When the RR extrapolation technique is employed, the confidence intervals constructed enjoy the best coverage properties, with the smallest ℓ 2 error, comparable CI width, and higher coverage probabilities of θ * . Moreover, the median coverage probability is around the targeted 95%. Table 2: Inference comparison of different batch numbers. ℓ 2 and "CI" values are of unit 10 -3 . Both CI width and coverage probability are for the 1-st coordinate estimate.
We further inspect the impact of the number of batches used in inference, i.e., the value K in the confidence interval construction procedure. We focus on one specific LSA problem with |X | = 10 and d = 5
Markovian data. The trajectory length is set at 10 6 and the number of batches varies. each combination of and number of batches we run independent runs and record the mean and standard error in Table 2.
For constant stepsizes, as we compare across different rows, the mean estimates are at the same scale, and not influenced much by the choice of batch number. However, for diminishing stepsizes, as the batch number increases, the CI widths decrease quickly, which drastically reduces the coverage probability and implies an underestimation of the variance. As the stepsize decays in the diminishing stepsize sequence, the iterates become increasingly correlated, and hence a longer batch size is needed to overcome the strong correlation. Therefore, the number of batches used in diminishing stepsize regime cannot arbitrarily increase. In contrast, iterates under constant stepsize mixes at the same rate and is more robust to the number of batches used.
Trajectory Length We next investigate the impact of increasing trajectory length with a range of stepsizes to better visualize the trend. For each trajectory length, we fix the number of batches as T 0.3 as recommended in Chen et al. (2020). The statistics are in Table 3.
We observe that inference with RR iterates consistently presenting the best results. When the trajectory length is at 10 3 , the iterates under various stepsize regimes would still be distant from θ * , which explains the mediocre coverage of θ * . As the trajectory length increases, the iterates gradually approach stationarity. Hence, the inference performance deteriorates for α = 0.2 with 0 coverage probability, as the iterates converge to E[θ ∞ ], which is asymptotically biased from θ * . On the other hand, as the trajectory length is longer, the iterates under diminishing stepsize converge closer to θ * . Therefore, the inference performance with diminishing stepsize improves. Inference with RR extrapolated iterates generally gives satisfactory performance. Hence, we would like to note that inference with constant stepsize might be especially useful when the simulation trajectory length budget is limited, as diminishing stepsize iterates struggle to output good inference results.
Comparison Against Bootsrapping In all previous experiments, we are comparing inference using SA iterates under different stepsize regimes. Here, we compare to bootstrapping, a more classical approach to statistical inference. Detailed experimental design can be found in the appendix.
While constant stepsize together with RR obtains 95.2% coverage with ℓ 2 error 1.0 × 10 -5 and CI width 0.00134, bootstrapping achieves 93.4% coverage with ℓ 2 error 2.0 × 10 -3 and CI width 0.00411. The large ℓ 2 error and wide confidence interval of bootstrapping suggest that it may not be able to handle correlated data efficiently.
Bootstrapping requires the entire data set to be stored, requiring O(T d ) memory, whereas inference with SA iterates can accommodate online data, hence O(d) memory. Inference with SA iterates only needs first-order information, while bootstrapping may need higher-order information, making it potentially computationally prohibitive.
Extending to Nonlinear SA Lastly, we examine the performance of our proposed technique in an example of logistic regression with unbounded Markovian data, to demonstrate that our proposed technique is robust in a wide range of settings, even if not currently addressed by our theory.
The categorical data (x t , y t ) arrives online, with x t sequentially sampled from a 2-dimensional Gaussian AR(1) process, and y t ∼ Bernoulli( 1 1+e -w * x t )) with w * ∈ R 2 being a random unit vector. This setting is non-Hurwitz, nonlinear, and with an unbounded underlying Markov chain, but our proposed inference procedure still exhibits similar performance as seen in Table 4.
In this section, we numerically examine the impacts of different stepsize selection decisions in RR extrapolation.
Comparing Different Regimes We first compare the geometric and equidistant regimes. To ensure a fair comparison, we keep the range of the stepsize selection the same across the two regimes, so the difference would come solely from how the stepsize decays within the range. The range is determined by a dyadic decaying stepsize sequence, i.e. the smallest stepsize across the two regimes is fixed at α M = α 1 /2 (M -1) . Under this setup, when the RR order is 2, there is no difference between these two schedules, so we start the comparison from the extrapolation with 3 stepsizes.
As depicted in Figure 1, when the order of extrapolation increases to around 5, the benefits of RR extrapolation have been mostly exploited. The difference between the two decaying schedules is more significant when the order is low.
Length Comparison table 0.2 0.15 0.1 0.05 0.02 RR 0.2 √ t 0.02 √ t 10 3 ℓ2 2.84 (0.06) 2.55 (0.06) 2.48 (0.05) 2.35 (0.05) 2.28 (0.05) 2.28 (0.05) 2.36 (0.05) 4.28 (0.07) CI 4.16 (0.07) 3.91 (0.06) 3.81 (0.06) 3.68 (0.06) 3.71 (0.06) 3.76 (0.06) 3.10 (0.05) 1.01 (0.02) Cov 82.2 (1.7) 84.0 (1.6) 83.0 (1.7) 83.6 (1.7) 83.6 (1.7) 83.4 (1.7) 76.8 (1.9) 24.8 (1.9) 10 4 ℓ2 1.15 (0.02) 0.99 (0.02) 0.89 (0.02) 0.79 (0.02) 0.73 (0.02) 0.72 (0.02) 0.73 (0.02) 1.14 (0.02) CI 1.44 (0.02) 1.38 (0.01) 1.34 (0.01) 1.31 (0.01) 1.29 (0.01) 1.30 (0.01) 1.12 (0.01) 0.67 (0.01) Cov 75.2 (1.9) 81.8 (1.7) 85.2 (1.6) 88.8 (1.4) 90.0 (1.3) 89.2 (1.4) 85.4 (1.6) 56.0 (2.2) 10 5 ℓ2 0.82 (0.01) 0.61 (0.01) 0.44 (0.01) 0.29 (0.01) 0.24 (0.01) 0.23 (0.01) 0.22 (0.01) 0.24 (0.01) CI 0.46 (0.00) 0.43 (0.01) (0.01) 0.41 (0.00) 0.41 (0.00) 0.38 (0.00) 0.29 (0.00) Cov 0.04 (0.9) 22.2 (1.8) 56.4 (2.2) 83.2 (1.7) 88.2 (1.4) 91.2 (1.3) 90.0 (1.3) 79.2 (1.8) 10 6
ℓ2 0.81 (0.00) 0.57 (0.00) 0.38 (0.00) 0.20 (0.00) 0.00 (0.00) 0.00 (0.00) 0.00 (0.00) 0.00 (0.00) CI 0.15 (0.00) 0.15 (0.00) 0.14 (0.00) 0.14 (0.00) 0.13 (0.00) 0.13 (0.00) 0.13 (0.00) 0.11 (0.00) Cov 0 (0) 0 ( 0) 0 (0) 19.0 (1.8) 80.2 (1.8) 95.2 (1.0) 92.8 (1.2) 90.2 (1.3) Table 4: Inference comparison of different trajectory lengths. ℓ 2 and "CI" values are of unit 10 -2 . Both CI width and coverage probability are for the 1-st coordinate estimate. As shown in Figure 2, the smaller b/(M -1) is, the worse the RR extrapolation performance is. This phenomenon is in line with Proposition 3, as b/(M -1) inversely scales with the variance upper bound. What is surprising is that when using small b/(M -1), increasing the number of the stepsizes used does not always reduce the ℓ 2 error of the extrapolated iterates. This may be due to the proximity of stepsizes, leading to large coefficients {h m }, increasing the variance and offsetting the reduction in bias. Hence, this suggests that for RR extrapolation to be effective, stepsizes should not be too close to each other, but should explore a range of values.
In this paper, we demonstrate the effectiveness of statistical inference with LSA iterates under Markovian data, constant stepsizes, and RR extrapolation. An immediate next step is to provide theoretical results to justify the validity of the CI constructed with Markovian LSA iterates with constant stepsize, as the CI is non-consistent. Further directions include: (a) develop an anytime variance estimator so that the proposed inference procedure can be fully online; (b) given a fixed simulation length, how one should decide the order of RR extrapolation to achieve decent inference performance.
An extended paper with appendix can be found at Huo, Chen, and Xie (2023b).The Thirty-Eighth AAAI Conference on Artificial Intelligence
The Thirty-Eighth AAAI Conference on Artificial Intelligence