A Statistical Online Inference Approach in Averaged Stochastic Approximation
Authors: Chuhan Xie
Zhihua Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: stochastic approximation
functional central limit theorem
statistical inference

Abstract: In this paper we propose a general framework to perform statistical online inference in a class of constant step size stochastic approximation (SA) problems, including the well-known stochastic gradient descent (SGD) and Q-learning. Regarding a constant step size SA procedure as a time-homogeneous Markov chain, we establish a functional central limit theorem (FCLT) for it under weaker conditions, and then construct confidence intervals for parameters via random scaling. To leverage the FCLT results in the Markov chain setting, an alternative condition that is more applicable for SA problems is established. We conduct experiments to perform inference with both random scaling and other traditional inference methods, and finds that the former has a more accurate and robust performance.

A Statistical Online Inference Approach in Averaged Stochastic Approximation
Chuhan Xie School of Mathematical Sciences
Zhihua Zhang
School of Mathematical Sciences
Peking University Beijing, 100871, China
Peking University
Beijing, 100871, China zhzhang@math, pku edu. cn
ch ch_xie@pku.ent hewppuu.edd...om
Abstract
In this paper we propose a general framework to perform statistical online inference in a class of constant step size stochastic approximation (SA) problems, including the well-known stochastic gradient descent (SGD) and Q-learning. Regarding a constant step size SA procedure as homogenouss Markov chain, we establish a functional central limit theorem (FCLT) for it under weaker conditions, and then construct confidence intervals for parameters via random scaling. To leverage the FCLT results in the Markov chain setting, an alternative condition that is more applicable for SA problems established. We conduct experiments to perform inference with both random scaling and other traditional inference methods, and finds that the former has a more accurate and robust performance.
Introduction
Stochastic approximation (SA) is a class of fixed-point algorithms that enjoys a wide range of
applications and research 23
24
21 14]. In general, with the goal of solving underlying
deterministic equation =00") = 0, SA algorithms perform iterative updates based on random
approximations of =0).. An SA procedure has the following form
0.+1 = 0, Zi = 0,1,,,
(1)
where 77 is the constant step size and Z, Z(,,, (:41) is random realization satisfying
Ex,,, Z0,, 1 = x0,). Although SA algorithms are initially proposed for solving optimization
problems, a large variety of modern machine learning problems such as TD learning (55 and Q-
learning 28 can also be solved via stochastic approximation, and hence studies of such problems in
an SA perspective have emerged in recent years 6 15 20
The celebrated Polyak-Ruppert averaged estimator [22] is often used to stabilize and accelerate SA algorithms. Instead of using the last iterate of an SA procedure, the estimator takes average over all iterates. It is well-known and extensively studied that if the step size 7j in (T) is replaced by suitably decaying step sizes, the estimator converges almost surely the ground-truth solution 0-, and central limit theorem (CLT) with optimal covariance can be established for the averaged iterates. Examples include
which proposes the batch-mean means inference method for SGD-type estimator; and [4], which gives the very first asymptotic results and statistical inference framework for adaptively collected data. Recently, this result has been extended
functional central limit theorem (FCLT) in particular settings, such as SGD [16], Local SGD [17]. and Q-learning [18]. In these works, however, additional conditions such as (2 + 5)-th bounded moments of noises are required to obtain such stronger FCLT result, and proofs are based on elaborated decomposition on the partial sum, which leads to some cumbersome calculation.
This motivates us to consider whether the same results can be established in a simpler way. In many real applications, constant step size SA algorithms are often used for convenience, and in this case
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the SA algorithm can be seen as time- homogeneoss Markov chain because each iteration of the SA procedure is only based on the current state. Such perspective is also adopted by 2 which gives some nice theoretical results on the constant step size SGD. Meanwhile, FCLT results are well-established in the Markov chain setting 19 26 3 g. Due to the fine structure of such Markov chains, the FCLT may be established with weak conditions, i.e., with only second bounded moments noises.
Based on the established FCLT, statistical inference via the random scaling method can be imple- mented. First proposed in [3 for time series regression and recently adapted in the inference of SGD parameters [16], random scaling utilizes the whole trajectory of the partial sum of iterates to construct covariance- like matrix, and studentizes the averaged iterates using this matrix. This results in pivotal statistic whose limit distribution does not depend on any other redundant parameter that needs to be further estimated. Without the need of the additional estimation step, so random scaling turns out to be more robust and efficient compared with traditional methods, such as spectral variance and batch-means [Q].
The remainder of this paper is organized as follows. In Section we propose a general statistical inference framework that includes the establishment of the FCLT and random scaling. In Section 3 we present applications of the framework in three modern problems including linear stochastic approximation (LSA). stochastic gradient descent (SGD) and Q-learning. Generally, the Polyak- Ruppert averaged estimator does not converge exactly to the ground-trus solution 0" but we give bounds on the bias show such bias diminishes as the step size 1j converges zero. Numerical experiments are given in Section to illustrate the accuracy and efficiency of our inference framework.
2 A Statistical Online Inference Framework
In this section, we introduce general statistical inference framework for a class of constant step size stochastic approximation (SA) problems. The inference procedure contains three main steps: establishing a functional central limit theorem (FCLT) for the parameters to be estimated, constructing pivotal statistic via random scaling based on the previously established FCLT, and providing problem-dependent estimate on the bias between the ground-truth solution and the expectation the stationary distribution to which the SA process converges.
2.1 Functional Central Limit Theorem
We first state FCLT established under a Markov chain setting. Let (Xn)nza be an ergodic Markov chain on the measurable space (S, S), with transition probability P and stationary distribution æ. For any measurable function g E I define the operator Pg(x) g P(x, dy) = ([g) = x]. By Pr or P- we denote the probability law of (X,)x20 starting from or having я as its initial distribution; Ex, or E,, the corresponding expectations. Given f E L we define the additive functionals (a) = ΣR=1 f(Xx) and (t) = n ==(())==+s)a)((7 ((a)).)
In R the authors proved a FCLT for univariate functional of (X,)m20 started point x. With slight modification, we can obtain the following multivariate functional version.
f f(x)=(dz) 0. If there Theorem 2.1. Suppose f: + _ satisfies f [[f(z))] (dxx) < oo and
exists 0 < a < such that
Σ
ph = O(n"),
(2)
L2
then Eg : lim t (.. exists, and for T-almost every point I E S the se- quence n. -nis,, converges in distribution, under the probability measure P., to the d-dimensional Gaussian distribution (0 E,). Furthermore, the process (Yn(t)) converges weakly to (t))ssi) on the Skorokhod space DjO, 1), where B = (B(t)) is the d-dimensional stan- dard Brownian motion.
See Section A.1 for the detailed discussion and proof. In the sequel, we use L to denote "converge in distribution and = to denote "converge weakly D(O, 1)". Note that an SA procedure of the form II can be seen hom-hhomggeneous Markov chain, and therefore in order to establish a FCLT for

---

the parameter sequence (0.) suffices to prove the existence of its stationary distribution and verify the conditions Theorem for f Id = The condition 2 is a bit harder verify. so we attempt to ensure it with a stronger Wasserstein contraction condition. For p, q 2 1, we define the Wasserstein distance Wp.g induced from the (P((TR)) space by
ulldd -
inf TET(UNN)
where [(u, v) is the set of all couplings of ja and and denote Pr.g as its corresponding Wasserstein space. We have the following proposition.
Proposition 2.1. Suppose for some p, 1. there exists constant (0,1) such that for any H., V E P.... the Wasserstein contraction
Wp.a (uP.uP) S (P.a(u,))
holds. Suppose addition that pp. (.)), m) E L2 where 8(.) is the Dirac measure and π is the sta- tionary distribution. Then for any f: TR. + Th satisfying I [1f( xo, ((x))
and
llf(z) - foy)loo S (f)l( yllp for all x, R", for some constant (ff (i.e., each component of f is Lipsshiit in the || ll norm), the condition (2) holds.
The proof of Proposition 2.1 is deferred to Section A.2
As we will see later, many SA problems (e.g., linear SA, SGI and Q-learning) possess such Wasserstein contraction property, and hence the corresponding FCLT holds.
2.2 Random Scaling
Once the FCLT for an SA problem is established, we can use the random scaling method to carry out inference. For the sequence (0,)e20 which is supposed converge its stationary distribution and satisfy the FCLT
Int] 02
E,0) = B(), 0stsi,
(4)
we studentize it with matrix Vn constructed as follows
} vn
V
Σ 0 -
B..) Σ 0 0n)
(5)
where 0, 1 4 O2 is the Polyak-Rupppe Ruppert averaged estimator for the parameter 0. Such studentization leads to a pivotal statistic whose asymptotic distribution does not depend on the parameters of the problem.
Proposition 2.2. Suppose the sequence (0:) converges to its stationary distribution x and its FCLT 4 holds. For a matrix R E Rixd of rank S d. we have
(R(Ō.. - -EZO)) (RVAR
- -E,))))
$ B(() (BB()))) (L)C) ar) -1 B,(1),
where By is E-dimensional standard Brownian motion and V, is defined in (
Proposition 2.2 follows directly from the continuous mapping theorem. Statistical inference for E, can be carried out via Proposition 2.2 For example, by setting R La
construct (1-a) asymptotic ellipsoidal confidence region centered at O, for estimating the whole vector E,, 0. More often, set R e, (the j-th unit vector) construct a (1-a) asymptotic confidence interval for estimating the j-th component of the expectation (E, ) so as to avoid heavy computation from the matrix inverse (RV, )-1

---

Corollary 2.1. Under the same assumptions of Proposition 2.2 we have that
( s (E~0); S (0n); + 93 v Vnnssin) + +1
where Vnss is the j-th diagonal element of Vnn and 4g is the (1 a//2)-th quantile of the following random variable
-
t=:= C.=(,.BB00-
B1(1),
(6)
with (Bi(t))20 one-dimensional standard Brownian motion.
Table 1: Asymptotic critical values qa defined by 9a = min PP(t"
< 2 1
-a.
o))
1%
2.5%
5%
10%
50%
90%
95%
97.5%
99%
qa
-8.634
-6.753
-5.324
-3.877
0.000
3.877
5.324
6.753
8.634
The random variable t* is mixed normal with its distribution symmetric around zero. For easy reference, its critical values listed in Table 1
is crucial to explain why inference via random scaling takes advantage over traditional inference procedures (e.g., the spectral variance method and the batch-means method that will be introduced hereafter) in our SA problem. Traditional estimators are mostly constructed on top of the CLT
(Os 0) N0,
where Σ = lim, +00 Er
1 1 (0. 0)) Eh=, - E,0)) is the asymptotic covari-
ance. Because E is unknown, one attempts to first construct an estimate Σ for Σ based on parameter samples (0:):20 and then establish a confidence interval based on with Σ replaced by Σ. As consequence, the estimation error in Σ may cause significant impact on the inference efficiency, Meanwhile, during the estimation of Σ, additional hyper-parameters are likely to occur, and different choices of such hyper-parameters may affect the inference performance. Random scaling, on the other hand, studentize the sum J Σn Σx=1(4 (0, - 0) to obtain a pivotal statistic. does not need the additional estimation step and additional hyper-parameters, resulting in its higher accuracy over traditional estimators.
2.3 Problem-Dependert Bias
The random scaling method mentioned above has already provided an efficient way to carry out inference on (E,,0), (or more generally, any linear combination of the expectation E,, However, in most nonlinear SA problems there is often gap between the expectation E, 0 and the ground-truit solution 8*, This issue will be further illustrated by the examples discussed in Section 3 Therefore, is theoretically not valid to carry out inference on 0 with a confidence interval constructed following Corollary 2.1 However, in the following applications we try to upper bound the bias | 0" with quantity of order (1)))) for some > O. When the step size is small, such bias is negligible and thus the original inference procedure may still be reasonable.
Case Studies
In Section 2] have established general statistical inference framework for constant step size stochastic approximation problems. We now illustrate several specific applications that are well- known in optimization and reinforcement learning.
These critical values are quoted from 117 (Table 2, the 3 0 case). In that paper the authors used kernel density estimation to smooth the empirical density function before obtaining critical values. Critical values without smoothing data in advance can be found in [3.

---

3.1 Linear Stochastic Approximation (LSA)
The first example considers solving linear system of the form Ae b. where E R and b E R.. We assume that A is invertible, and there is unique solution 0 to the linear equation. Suppose we can observe a sequence of random variables of the form {(A,, (,),),))211 assumed to be independent and identically distributed, and unbiased in the sense that [E ((,()FF-i) A and F(b((FF-11) = b, where Fi-1 denotes the a-field generated by {(As, bb)) For a given initial vector 0, LSA is formulated as
01+1 0, 11177((4::)) (A b(+1),
where 7) > O is the constant step size. Before presenting our results, we make some assumptions.
Assumption 3.1. The matrix A Rdxd is Hurwitz, ie., À = minjsiga (R, (A)) where (A) is the i-th eigenvalue of A and RR(A(A)) is its corresponding real part.
Assumption 3.2 (Bounded second moment of noise). Denote E, = A, A and & = b - b. There exist u > 0 and u/ > O such that E S Moreover, =, and & are uncorrelated.
v and EE|, 2 S of for any 2 and S
Theorem 3.1. Suppose Assumptions 3.1 and 3.2 hold for the LSA procedure
8 Then there exists a
constant no such that for any 1) E (0, no).
1. the Markov process (0z) defined by 8 has a unique stationary distribution Tej
2. for 0 ~ Txp we have Ex,, 0 0":
3. the following FCLT holds
O2 (0) Ex, B(), 05151,
k=1
where (B(t))120 is the d-dimensional standard Brownian motion and E limn-soo ncov (, (0.)) ) the asymplotic covariance matrix.
Remark 3.1. we further suppose that (At)22 and (bete>1 have i...d. entries, then the asymptotic covariance matrix En,, has an explicit form (see Section A.3 for details). This matches the asymptotic results in (20g, where the same assumptions are needed and a central limit theorem (CLT) is established, based on an additional requirement that the noises E, and & have bounded (2 + 8)-th moments for some 8 > O. Theorem 3./ extends this CLT result into a functional version even without such an additional moment requirement.
Note that in the LSA problem, the expectation of the stationary distribution E.,, 0 exactly matches the unique solution 0", so that the problem- wreeeetddpendeet bias in this case vanishes. The established FCLT allows us to perform statistical inference directly on 0* via Corollary 2.1
3.2 Stochastic Gradient Descent (SGD)
Next, we consider the inference problem for a minimizer of an objective function, define by
:= argmin f(O),
OER
where f(0)= == [0 E)] and f(0, {) is an unbiased random variable for the objective function. The constant step size SGD iteratively updates the parameter in the following form
O = 0 (O..
In this case, we make the following assumptions to derive our results.
Assumption 3.3. f(-) is m-strongly convex, and for each &, f(:E) is L-smooth. Assumption 3.4 (Regularized gradient noise). Define e0f, () V (0, (V((0) as the gradient
noise at 0, and S = ())(("")))E(" [T) J. There exists some C > such that
1 S|| < C [1[0
0- || + | 0- [0]
(10)
5

---

Theorem 3.2. Suppose Assumptions 3.3 and 3.4 hold for the SGD iterates 9 constant To such that for any 17 E no.)
Then there exists
1. the Markov process (0z) defined by (9) has a unique stationary distribution Taj
2. for O Ty have Ex,, ||0 1- R., (E ()12 O
3. The following FCLT holds
2 Ex, Ei, B(), 0 05151,
(11)
where (B()))(20 is the d-dimensional standard Brownian motion and En, limn-toc ncOv (6.) the asymptotic covariance matrix.
Theorem 3.2 provides all ingredients for performing inference on E,, 0. In addition, the bias can be bounded
B 0-1 ET, 0 1- = V
1 m
[ (0.(
7 I (V)(,,)))))
that is, it of order 122)
3.3 Q-Learning
Finally we consider an application in Q-learning. An infinite-horizon MDP is represented by M = (S, A, P. R,r), where S is the state space and A is the action space, 7 (0, 1) is the discount factor, P: S x A + (SS) represents the probability transition kernel, R: 8 x A + [0, x)) the random reward, and r:
A + [0, oo) is the expectation of the reward. For given deterministic policy π: S + A, the expected long-term reward is measured by value function V and Q-function QT defined as follows:
(*((s = ETTT
Σ r'r(s), 1=
and Q7 = ET Σ rrr(s at) = ao
for any state-action pair (s, a) E E SSX x A. Here == {(s at) a Jiz is a trajectory of the MDP induced by the policy and the expectation Erwr (-) is taken with respect the randomness of the trajectory т. The optimal value function V* and optimal Q-function Q" are defined as V*(s) = max, V*((s) and (s, a) max, Q" (s, a), respectively. It is well known that Q" is the unique fixed point of the Bellman operator T, i.e., T(Q*) = Q", where
(s))(s.a) r(s, + -Eg-P()..) max Q(5 ( d'EA
Now assume access to generative model. In particular, in each iteration t O, collect independent samples of the reward r, a) and the next state sy(8, a) ~ P(-|s, a) for every state- action pair (s, a) S x A. The constant step size Q-learning maintains Q-function estimate, Q:: S x A R, for all 2 0 and updates its entries by the following update rule
Q+11 = (1 2 + T (Qt),
(12)
where 77 E (0, 1] is the step size and T, is the empirical Bellman operator constructed by samples collected in the 1-th iteration:
(.()))s a) = rs, a) + max Q(8,, where ()) ~ R(s, a) and (x, ~ P(+ss
d'EA
(13)
Clearly, T, is unbiased estimate of the Bellman operator T.
Assumption 3.5 (Uniformly bounded reward). The random reward R is non-negative and uniformly bounded, i.e., S R(s, a) < almost surely for all (s, a) E S A.
Theorem 3.3. Suppose Assumption 3.5 holds for the Q-learning update rule 12 and assume access to a generative model for each state-action pair (s,a) E S x A. Let Q E S|XA be the matrix form of the Q-function (s,, a). Then there exists constant no 0 such that for any n E (0, mo).

---

1. the Markov process (Q defined by 12
has a unique stationary distribution Q
2. for Q Qny we have e Q 10 12))
3. The following FCLT holds
nt Q= E2,
E B(), 05151,
(14)
k=1
where (B)))) is the d-dimensional standard Brownian motion and Eo, = lim RCOV 2, (Qn) is the asymptotic covariance matrix.
Experiments
In this section we conduct the empirical analysis of the random scaling method via Monte Carlo experiments. Two traditional inference methods, namely, the spectral variance method and the batch- means method, are also examined for comparison. These two methods are popular in estimating the asymptotic variance of Markov chain (10), and confidence intervals can be constructed based on the CLT with E replaced by estimator Σ. From on, represent the concerned parameter as 33 for clarity.
The spectral variance estimator is based on the fact that Ett cov (Gr, Be-s). It constructed as
SS
Wn (s)(()))),
(b., 1)
where (-) is the lag window, bn is the truncation point, and
(n( (3) (-)- Σ (B. B.)( - Ba) 0,
which is consistent estimator of the lag autocovariance 7(8) = cov (G,, Br+s). Under mild conditions on (-) and b.. Egv a consistent estimator of Σ [0]. In our experiments we choose (-) to the Tukey-Hanniin window ur, = cos (T /k|/b,)) 1 [IMKb,)) with bn = 3/1
The batch-means estimator is another consistent estimator of E. It first divides a total of n = br iterates into an batches, and calculate the mean of each batch B == 1 Ebn, Beb for k O..... On 1. The batch-means estimator is then defined as
Un Σ k=
-1
EBM =
(Bea+1 - 33 - BN)
When on and bn are allowed increase as n increases (e-g., by setting a, = b, LVn)), EBM is consistent estimator of Σ 12 our experiments we choose a, = b, = LVnl.
In the following, we consider the constant step size SGD on two baseline models: linear regression and logistic regression. Additional experiments for Q-learning on Grid World are included in Appendix D All experiments are run Intel Xeon 14-core CPUs. The performance of the spectral variance method, batch-means method, and random scaling method are compared in three aspects: the coverage rates for Ex,, G and 3*, and the lengths of confidence intervals. The nominal coverage rate is chosen as 95%. For brevity, we focus on the first coefficient 3 hereafter. The implementation code available in httptts::/// /ttp::////ittunn
www.baaggoo/aaaaaacccoooo sa- Sawaanggg//----feeeneee
Linear Regression
The data are generated from
= x._
3 + t21
(15)
where az a d-dimensional covariate following the multivariate normal distribution A/ Ta), & is the noise from (0, 1), and 3 is equi-spaced on the interval [0, 1]. The dimension of is set as

---

d = 50. The constant learning rate is set as 1/ 0.01, 0.05, 0.1. The initial value of So is set as zero. The simulation results are based on 1,000 replications. Our experimental design is the same as that of [29 [6]. except that our learning rates v are smaller than the initial learning rates in their settings, which are chosen to be foo = 0.5, 1. This is inevitable because constant step size SGD) requires smaller learning rates to ensure convergence. Note that SGD for linear regression is also a case of LSA, so the expectation of the stationary distribution is equal to the true parameter, i.c., En, 3 3
Table 2 summarizes partial simulation results for d = Full results for d 5, 20 can be found in Appendix C Overall, the random scaling method is satisfactory in that its coverage rates are the closest to the nominal one (95%) across all experimental settings. Nevertheless, the average lengths of confidence intervals (CI) constructed via random scaling are always larger than that of both the spectral variance method and the batch-means method. The batch-means method, on the contrary, shows the lowest coverage rates and the smallest average CI lengths, and its performance varies hugely when we choose different step sizes. When 1j = 0.01 it performs the worst, deviating from the nominal rate about 10% even at = 40, 000 (when d = 5) or at n 100, 000 (when d 20). Comparing our experiment results with that of [66, where the authors use SGD with decaying step sizes of the form 7/ not we find that average CI lengths in our settings are bit larger. Such observation is also reasonable, because SGD with particular decaying step sizes is shown to converge to the true parameter almost surely, and does its corresponding Polyak-Ruppers Ruppert averaged estimator [22] but in the case of constant step sizes, the iterates converge to a non-degenerate stationary distribution, and such non-degeneration adds to additional fluctuation of the Supyert averaged estimator.
Logistic Regression
The data are generated from
exp(-xx 33))
P(y+ =) I exp(-xx 3²)² P(y. 0) 1+ exp(-2x 3²))²
12 1.
(16)
All the settings are the same as in linear regression. Note that for logistic regression, the expectation of the stationary distribution is not necessarily equal to the true parameter, i.e., Ex,, & 3r. However, since the difference is diminishing as 7) - 0, the confidence intervals may still be useful for inference on S*. Therefore, we include the coverage rates for Bi in our results.
Table 3 summarizes partial simulation results for 5. Full results can be found in Appendix C These results are similar to those in linear regression. Coverage rates for / are generally smaller than coverage rates for Ex, 3i as expected, and their differences become larger as the step size gets larger. Nevertheless, coverage rates for 9i based on random scaling deviates within 5% of the nominal one in most settings, which indicates that such confidence intervals are still reasonable when the step size is small. The batch-means method is still not robust to different step sizes, because the coverage rates even fall below 60% when 17 = 0.01.
5 Conclusion
In this paper we have studied statistical inference on a class of constant step size stochastic approxi- mation (SA) problems. Based on a FCLT in the context of Markov chains, we have established the corresponding FCLTs for LSA, SGD, and Q-learning. A sufficient condition for the FCLT has been stated and proved for ease of application. Various inference methods including the random scaling method, spectral variance method and batch-means method have been conducted in experiments, based on the established FCLTs. We have shown that random scaling performs well in terms of coverage rates, and is also robust against different step sizes.
There are also limitations and issues that need to be further investigated. First, except in trivial cases, iterates converge to a stationary distribution whose expectation does not equal to the true parameter, and such systematic bias prohibits efficient inference procedures for the true parameter we are concerned about. It remains open whether there exist practical ways to mitigate the impact of such bias. Probabilistic tools such as the large deviation theory might help construct valid confidence intervals for the true parameter. Second, recent works considering SA problems with decaying step sizes, such as [16 17 18) prove the FCLT by manually dividing the estimator into several terms, applying martingale CLT to one term, and uniformly bounding other terms. It is
8

---

Table 2: Linear Regression, d
T 5, 000
n 10, 000
n == 20, 000
40, 000
== 0.01
Spectral Variance
88.6(10005)
91.1(0.900)
91.5(0.881)
92.4(0.837)
Cov. for Bi (%)
Batch Means
69.8(1.451)
77.8(1.314)
82.3(1.206)
86.7(1.073)
Random Scaling
92.8(0.817)
94.6(0.714)
95.0(0.689)
94.9(0.695)
Spectral Variance
0.050(0.011)
0.036(0.007)
0.026(0.004)
0.018(0.003)
Length
Batch Means
0.030(0.003)
0.024(0.002)
0.019(0.001)
0.015(0.001)
Random Scaling
0.074(0.033)
0.053(0.022)
0.036(0.014)
0.026(0.010)
7 0.05
Spectral Variance
91.9(0.862)
91.6(0.877)
90.8(0913))
91.6(0.877)
Cov. for 37 (%)
Batch Means
90.0(0.948)
93.6(0.773)
92.7(0.822)
92.0(0.857)
Random Scaling
94.9(0.695)
95.2(0.675))
95.4(0.662)
94.1(0.7455)
Spectral Variance
0.055(0.012)
0.039(0.007)
0.028(0.005)
0.020(0.003)
Length
Batch Means
0.050(0.004)
0.038(0.002)
0.027(0.001)
0.020(0.001)
Random Scaling
0.076(0.031)
0.055(0.023)
0.039(0.015)
0.027(0.010)
7=
Spectral Variance
89.5(0.969)
89.8(0.957)
92.1(0.852)
92.7(0.822)
Cov. for Bi (%)
Batch Means
92.9(0.812)
94.1(0.745)
94.0(0.750)
92.8(0.817)
Random Scaling
94.3(0.733)
94.6(0.714)
94.1(0.745)
93.0(0.806)
Spectral Variance
(0.61)).013)
0.043(0.008)
0,031(0.005)
0.022
Length
Batch Means
0.061(0.005)
0.045(0.003)
0.032(0.002)
0.02300.00))
Random Scaling
0.085(0.035)
0.060(0.025)
0.042(0.016)
0.030(0.012)
Table Logistic Regression, d=
5,000
100000 000
20, 000
40, 000
7 0.01
Spectral Variance
60.0(1.549)
75.7(1.356)
84.5(1.144)
89.9(0.952)
Cov. for B,,, Bi (%)
Batch Means
32.6(1.482)
45.4(1.574)
51.8(1.580)
57.8(1.561)
Random Scaling
86.9(1.066)
91.0(0.904)
94.1(0.745)
95.6(0.648)
Spectral Variance
59.4(1.552)
75.2(1.365)
84.4(1.147)
89.7(0.961)
Cov. for Bi (%)
Batch Means
27.8(1.416)
40.7(L.553)
47.9(1.579)
55.9(1.570)
Random Scaling
85.7(1.107)
89.8(0.957)
93.0(0.806)
95.1(0)682)
Spectral Variance
0.079(0.022)
0.068(0.016)
0.055(0.010)
0.042(0.006)
Length
Batch Means
0.033(0.007)
0.028(0.005)
0.023(0.003)
0.018(0.002)
Random Scaling
0.175(0.080)
0. 0.129(0.056)
0.092(0.040)
0.063(0.026)
7 7=
Spectral Variance
91.2(0.895)
91.9(0.862)
91.3(0.891)
92.3(0.843)
Cov. for IB,,, B1 (%)
Batch Means
76.8(1.334)
83.7(1.168)
85.9(1.100)
87.8(10034)
Random Scaling
95.1(0.682)
93.2(0.796)
95.2(0.675)
94.8(0.702)
Spectral Variance
88.2(1.020)
87.9(10031)
85.4(1.116)
80.1(1.262)
Cov. for Bi (%)
Batch Means
77.3(1.324)
80.6(1.250)
81.((1.200)
79.3(1.281)
Random Scaling
94.3(0.733)
92.8(0.817)
94.1(0.745)
91.3(0.891)
Spectral Variance
0.12900.028)
0.094(0.018)
0.067(0.012)
0.048(0.007)
Length
Batch Means
0.090(0.009)
(0001(0.006)
0.056(0.004)
0.042(0.002)
Random Scaling
0.180K0.079)
0.129(0.053)
0.092(0.039)
0.066(0.027)

---

interesting to consider whether such proofs can be simplified by regarding these SA problems as imeeinnomogeneous Markov chains and applying techniques in the Markov chain setting.
Acknowledgments and Disclosure of Funding
This work has been supported by the National Key Research and Development Project of China (No. 2020AAA0104000 and the National Natural Science Foundation of China (No. 12271011).
References
[1] Karim M Abadir and Paolo Paruolo. Two mixed normal densities from cointegration analysis. Econometrica: Journal of the Econometric Society, pages 671-680, 1997.
[2] Carolyn L Beck and Rayadurgam Srikant. Error bounds for constant step-size q-learning. Systems control letters, (1(1)):1203 1208, 2012.
[3] Kung Sik Chan and Charles Geyer. Discussion: Markov chains for exploring posterior distributions. The Annals of Statistics, 22(4):1747-1758, 1994.
[4] Haoyu Chen, Wenbin Lu, and Rui Song. Statistical inference for online decision making via stochastic gradient descent. Journal of the American Statistical Association, 116(534):088-19, 2021.
[5] Xi Chen, Jason D Lee, Xin T Tong, and Yichen Zhang. Statistical inference for model parameters stochastic gradient descent. The Annals of Statistics, 48(1):251-273, 2020.
[6] Gal Dalal, Gugan Thoppe, Balázs Szörényi, and Shie Mannor. Finite sample analysis of two- timescale stochastic approximation with applications to reinforcement learning. In Conference On Learning Theory, pages 1199-1233. PMLR, 2018.
[7] Yves Derriennic and Michael Lin. The central limit theorem for markov chains with normal transition operators, started at point. Probability theory and related fields, 11944))5085528 2001.
[8] Yves Derriennic and Michael Lin. The central limit theorem for markov chains started at a point. Probability theory and related fiels, 125(3):73-76, 2003.
[9] Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and markov chains. The Annals of Statistics, 1883);1348-1382, 2020.
[10] James M Flegal and Galin Jones. Batch means and spectral variance estimators in markov chain monte carlo. The Annals of Statistics, 38(2):1034-107) 2010.
[11] Galin L Jones. On the markov chain central limit theorem. Probability surveys, 1:299-320, 2004.
[12] Galin L Jones, Murali Haran, Brian S Caffo, and Ronald Neath. Fixed-width output analysis for markov chain monte carlo. Journal of the American Statistical Association, 101(476):1537- 1547, 2006.
[13] Nicholas M Kiefer, Timothy Vogelsang, and Helle Bunzel. Simple robust testing regression hypotheses. Econometrica, 68(3):695-714 2000.
[14] Tze Leung Lai. Stochastic approximation. The annals of Statistics, 31(2):391-400 2003.
[15) Chandrashekar Lakshminarayanan and Csaba Szepesvari. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In International Conference on Artificial Intelligence and Statistics, pages 1347-1355. PMLR, 2018
[16] Sokbae Lee, Yuan Liao, Myung Hwan Seo, and Youngki Shin. Fast and robust online inference with stochastic gradient descent via random scaling. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7381-7389,
10

---

[17] Xiang Li, Jiadong Liang, Xiangyu Chang, and Zhihua Zhang. Statistical estimation and online inference via local sgd. In Conference on Learning Theory, pages 1613-1661. PMLR, 2022.
[18] Xiang Li, Wenhao Yang, Zhihua Zhang, and Michael I Jordan, Polyak-ruppert averaged q-leaning is statistically efficient. arXiv preprint arXiv:2 14582, 2021.
[19] Michael Maxwell and Michael Woodroofe. Central limit theorems for additive functionals of markov chains. The Annals of Probability, 28(2):11-7724, 2000.
[20] Wenlong Mou, Chris Junchi Li, Martin Wainwright, Peter L. Bartlett, and Michael I Jordan, On linear stochastic approximation: Fine-grained polyak-ruppert and non-asymptotic concentration. In Conference on Learning Theory, pages 2947-2997. PMLR, 2020.
[21] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming, SIAM Journal on optimization, 19(4):1574- 1609, 2009.
[22] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization,, 30(4):838-8555 1992.
[23] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[24] David Ruppert. Stochastic approximation. Technical report, Comell University Operations Research and Industrial Engineering, 1988.
[25] Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning. 3(1):9444, 1988.
[26] Luke Tierney. Markov chains for exploring posterior distributions. the Annals of Statistics, pages 1701-1728, 1994.
[27] Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[28] Christopher JCH Watkins and Peter Dayan. Q-learning- Machine learning, 8(3):279-292, 1992.
[29] Wanrong Zhu, Xi Chen, and Wei Biao Wu. Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statistical Association, pages 1-12, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative socictal impacts your work? [No] Our work
is theoretical and has no potential negative social impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes]

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "qguOQOHYnd", "reviewer": "Reviewer_KDyo", "summary": "The paper suggests a procedure for constructing confidence intervals for constant step-size SA algorithms. The suggested procedure is based on FCLT and random scaling procedure. This technique might be viewed as an alternative to the methods based on estimations of the asymptotic variance of the Markov chain, such as batch mean or spectral variance. The method is tested on a constant step-size SGD procedure for low-dimensional linear and logistic regressions.", "questions": "1. I would be curious to see the empirical performance of the random scaling approach in RL applications. For example, I suggest the authors consider the grid-world type example and a Q-learning procedure on it. Another scenario could be TD-learning with linear functional approximation, studied e.g. in the paper [17] (cited in the paper);", "limitations": "The authors addressed the limitations correctly. Yet the main limitation is that only the constant step-size SA problems are considered, which lowers the potential applicability of the result. ", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality.\n\nResults similar to Theorem 2.1 are well-known in the Markov chain literature (see e.g. [Douc et al, 2018], sections 21.2-21.3). It is also typical that there are no additional requirements for the moments of order $(2+\\delta)$. It is also possible to mention the paper [Atchade, 2013]. Generalizations of these results to the multidimensional scenario are rather straightforward. CLT for the Markov kernels which are W-uniformly geometrically ergodic (the scenario considered in Proposition 2.1) is also well-known in MCMC literature. \nMoreover, CLT results in theorems 3.1--3.3 do not require novel methods and easily follow from obtaining the Wasserstein contractility of the corresponding transition kernels. So the theoretical findings of the paper are limited.  In the empirical evaluation, the authors also consider only model examples of low-dimensional logistic and linear regressions. \n\nClarity\nThe paper is quite well-written, and the suggested methodology and theoretical derivations are clear.  I would suggest to fix the statement of Theorem 3.3 in order to mention explicitly the access to generative model $P(\\cdot | s,a)$ for each state-action pair $(s,a)$.\n\nSignificance.\nConstant step-size SGD and $Q$-learning with constant step size are of moderate interest. Q-learning without bonuses and with constant step size makes sense only with access to generative model, which is of limited practical interest. More interesting scenarios invoke the decreasing step size in SA and/or the Markovian noise dynamics, which require much more sophisticated analysis. Another problem concerns the bias of constant SA scheme. For example, in theorem 3.2 the covariance matrix $\\Sigma_{\\pi_{\\eta}}$ scales as $\\|\\|\\Sigma_{\\pi_{\\eta}}\\|\\| \\lesssim \\eta$, which is of the same order as the bias term in th.3.2.2. Thus bounding the bias as $O(\\eta^{1/2})$ is not enough. \n\nReferences:\n[Douc et al, 2018] - R. Douc, E. Moulines, P. Priouret, and P. Soulier. Markov chains. Springer Series in Operations Research and Financial Engineering, 2018.\n[Atchade, 2013] Y.F. Atchad´e (2016), Markov Chain Monte Carlo confidence intervals. Bernoulli 22(3), 1808–1838.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9z8yFqfjK_", "reviewer": "Reviewer_2ACX", "summary": "This paper considers the online statistical inference problem under a constant step size stochastic approximation setting. The authors first present a functional central limit theorem type result. Then given the FCLT result for the stochastic approximation problem, they further propose an online statistical inference framework using random scaling. They also illustrate their theoretical results in three cases, i.e., linear stochastic approximation, stochastic gradient descent, as well as Q-learning. Some numerical experiments are given to further support their findings.\n\n\n", "questions": "I have just one question for the authors: under the constant step SGD setting, the bias ( $\\mathbb{E}_{\\pi} \\beta - \\beta^*$) is not negligible, and in practice, the statistical inference cannot be done. The authors state that when $\\eta \\rightarrow 0$, the bias term is diminishing as well, but wouldn't that becomes the case where we have a diminishing step size and where traditional Polyak-Judisky type estimator and inference will be used instead?", "limitations": "None", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- This paper is overall well written, and the authors present their theoretical findings clearly. \n- In the literature, there is much work established on the diminishing step-size SGD and its corresponding statistical inference, from Polyak and Juditsky (1992). On the contrary, the constant step size SGD (and its parameter inference) is rarely studied, this paper enriches the theoretical results in this area. \n- The authors also have a theoretical contribution to relaxing the $2+\\delta$  moment condition. \n- In Section 3, the authors also give theoretical results on three useful examples.\n\nIn summary, I would like to emphasize this paper's theoretical contribution to the constant step size stochastic approximation problem, both the asymptotic distribution part and the online statistical inference part.\n\n**Weakness**\n\nThis paper is very good in general, I have a few concerns that are stated below,\n\n1. Some related work should be cited properly, e.g.,  [1] present an online statistical inference framework for SGD-type estimator; \n[2] gives the very first asymptotic results and a statistical inference framework for adaptively collected data; [3] gives some nice theoretical results on the constant step-size SGD.\n2. The assumption (strong convexity) in Theorem 3.2 is a little bit strong, and cannot be applied to the logistic regression case that the authors used in the experiment section. The authors could find an extension to the locally strong convexity in [4], under which the logistic regression satisfies the assumption.\n\n[1] Chen, Xi, Jason D. Lee, Xin T. Tong, and Yichen Zhang. \"Statistical inference for model parameters in stochastic gradient descent.\" The Annals of Statistics 48, no. 1 (2020): 251-273.\n\n[2] Chen, Haoyu, Wenbin Lu, and Rui Song. \"Statistical inference for online decision making via stochastic gradient descent.\" Journal of the American Statistical Association 116, no. 534 (2021): 708-719.\n\n[3] Dieuleveut, Aymeric, Alain Durmus, and Francis Bach. \"Bridging the gap between constant step size stochastic gradient descent and Markov chains.\" The Annals of Statistics 48, no. 3 (2020): 1348-1382.\n\n[4] Su, Weijie J., and Yuancheng Zhu. \"Uncertainty quantification for online learning and stochastic approximation via hierarchical incremental gradient descent.\" arXiv preprint arXiv:1802.04876 (2018).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5Q20Yn9Tlis", "reviewer": "Reviewer_hS9V", "summary": "This paper considers a statistical inference problem for which parameters are estimated by stochastic approximation (SA) with a constant step size. The main theoretical results are derivations of functional central limit theorems (FCLTs) under a Markov chain setting. Three important cases are analyzed: linear stochastic approximation (LSA), stochastic gradient descent (SGD), and Q-learning. The inference method is based on random scaling that has been recently proposed in the literature. The numerical experiments involve SGD in the context of linear and logistic regression with a large sample but a small number of covariates.   ", "questions": "(1) The nonzero bias problem is unfortunate, as the confidence interval does not center around the true parameter value. It is nice to have an upper bound on the bias at the order of the square root of the learning rate.  Is there any way to develop lower bounds on the bias? It would be interesting to know what type of nonlinearity matters for the bias.\n\nHere are some minor suggestions.\n\n(a) References 13 and 14 are now in the conference proceedings, 13 in AAAI-22 and 14 in COLT-22, respectively.\n\n(b) In line 205, what is \"i\" in collected i the $t$-th iteration; perhaps \"in\"?\n\n\n\n ", "limitations": "Generally speaking, the authors addressed the limitations. A few things, which can be mentioned (additionally or in more detail), are as follows:\n\n(1) SGD with a constant step size leads to an inefficient estimator and as a result, the resulting confidence interval with random scaling will be wider than that with a decreasing step size. \n\n(2) How to choose the learning rate (step size) in applications is not discussed; furthermore, there is no real data application which would provide a more difficult environment for choosing the step size.\n\n(3) No replication files are provided in the supplementary material.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality: Recent work has applied random scaling to SGD with a decreasing step size for the purpose of inference. This paper is new in the sense that it applies random scaling to SGD with a constant step size. \n\n- Quality: The theoretical work is of high quality. Assumptions are clearly stated and the results are impressive. The numerical work is of medium quality. The experimental design is simple but adequate to make the point that random scaling works for SGD with a constant step size in the linear regression model. \n\n- Clarity: The paper is very clear.\n\n- Significance: The results in the paper are non-trivial and useful. The inference method is incomplete when the bias is nonzero but the results in this paper may lead to a new line of research that can estimate or bound the bias. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept