Gaussian Approximation and Concentration of Constant Learning-Rate Stochastic Gradient Descent
Authors: Ziyang Wei
Jiaqi Li
Zhipeng Lou
Wei Biao Wu
Venue: NeurIPS 2025 poster ()
Keywords: stochastic gradient descent
constant step size
Gaussian approximation
concentration
Primary area: optimization

Abstract: We establish a comprehensive finite-sample and asymptotic theory for stochastic gradient descent (SGD) with constant learning rates. First, we propose a novel linear approximation technique to provide a quenched central limit theorem (CLT) for SGD iterates with refined tail properties, showing that regardless of the chosen initialization, the fluctuations of the algorithm around its target point converge to a multivariate normal distribution. Our conditions are substantially milder than those required in the classical CLTs for SGD, yet offering a stronger convergence result. Furthermore, we derive the first Berry-Esseen bound -- the Gaussian approximation error -- for the constant learning-rate SGD, which is sharp compared to the decaying learning-rate schemes in the literature. Beyond the moment convergence, we also provide the Nagaev-type inequality for the SGD tail probabilities by adopting the autoregressive approximation techniques, which entails non-asymptotic large-deviation guarantees. These results are verified via numerical simulations, paving the way for theoretically grounded uncertainty quantification, especially with non-asymptotic validity.

Gaussian Approximation and Concentration of Constant Bearning-Rate Stochastic Gradient Descent
Ziyang Wei Department of Statistics University of Chicago Chicago, IL 60637 bayyang@uuchicago... edu
Jiaqi Li Department of Statistics University of Chicago Chicago, IL 60637 jqli Sqli@uchicago. edu
Zhipeng Lou Department of Mathematics University of California, San Diego
La Jolla, CA 92093 zl clouuccddd edu
Wei Biao Wu Department of Statisties University of Chicago Chicago, IL 60637 abwu@uchicago. edu
Abstract
We establish a comprehensive finite-sample and asymptotic theory for stochastic gradient descent (SGD) with constant learning rates. First, we propose a novel linear approximation technique to provide a quenched central limit theorem (CLT) for SGD iterates with refined tail properties, showing that regardless of the chosen initialization, the fluctuations of the algorithm around its target point converge to a multivariate normal distribution. Our conditions substantially milder than those required the classical CLTs for SGD, yet offering a stronger convergence result. Furthermore, derive the first Besre-Esseen bound the Gaussian approximation eтror - for the constant lcarning-rate SGD, which is sharp compared to the decaying learning-rate schemes in the literature. Beyond the moment convergence, also provide the Nagaev-type inequality for the SGD tail probabilities by adopting the autoregressive approximation techniques, which entails non-asymptotic large- deviation guarantees. These results are verified via numerical simulations, paving the way for theoretically grounded uncertainty quantification, especially with non-asymptotic validity.
Introduction
In large-scale optimization and streaming-daie data applications, online learning has played a crucial role, where stochastic approximation serves fundamental ingredient to improve computational efficiency and save memory. However, to facilitate trustworthy Al and reliable decision-making based stochastic approximation, it is important to understand its inherent variability, especially in finite-sample settings.
This paper considers popular recursive algorithm in online learning - Stochastic Gradient Descent (SGD), also known as the Robbins-Monro algorithm [Robbins and Monro [951]. which is widely used due its memory efficiency, computational simplicity, and algorithmic stability. The con- vergence and distributional theory SGD and its variants have been extensively studied [Fabian 1968. Woodroofe 1972 Pfuu 1986 Polyak and Juditsky 1992] Kushner and Yin 1997| Shamir and Zhang] 2013]. Nevertheless. the uncertainty quantification of constant learning- rate SGD remains partially understood. Though central limit theorems (CLT) have been explored in literature (Pflug) 1986 Dieuleveut et al. 2020). refined theoretical properties such as non-asymptotic Gaussian approx-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

imation rate and sharp concentration inequalities are lacking. To fill in this gap, we provide the first Berry-Esseen bound and the first Nagaev-type tail probability for constant learning-rate SGD.
Specifically, we are interested in the following optimization problem:
0" = arg min G(Ø) _ arg min E (xx BERd
BEB4
where G is the objective function from Rd to R, and g(0, X) is the noise-perturbed loss function. With sequentially arriving i..d. random data X; ~ for some unknown distribution II, SGD updates the estimated model parameter
= 01-1-1191 Vo(0.11, 12
(2)
where Vg is the gradient of g(0, with respect to the first argument 0, and y 0 is the fixed learning rate.
Asymptotic normality of the SGD iterates {6e heN has been investigated in many works. For example, Pilug [9866 proved the first CLT of SGD with constant learning rate, where the SGD iterates were viewed as time-homogee -mme-ooogeenouu Markov chain. This provides traditional framework to address the non-stationarity of constant learning-rate SGD. Under certain regularity conditions, such a Markov chain has been shown to converge to a stationary probability measure TI geometrically fast as the iteration n grows to infinity (Dieuleveut et al. 2020 Merad and Gaiffas) 2023]. Building on this asymptotic stationarity, the more recent works focus the scaling of this stationary distribution in regard to the learning rate y, and establish the CLT as y - [Chen et al. 2022 Wei et al. 2025) Since the constant learning-rate SGD will not converge 0* but oscillates around with stochastic order of v7 (Dieuleveut et al. 2020), we denote by 6x0 E R the random vector following the stationary measure. The diagram below illustrates the key ingredients of classical analysis.
On n-000
00 0"
7-+0
NO,
As can see from the diagram, all the aforementioned works cannot avoid one critical problem: they require the iterations n - oo before 7 - O. In other words, their asymptotic normality result only holds for the stationary SGD sequence, which, however, is unrealistic in practice, since practitioners usually arbitrarily fix the initialization On that yields a non-stationary sequence 0,, while the stationary sequence is unattainable in finite time. In contrast, the actual procedure of stochastic approximation is to first determine a small learning rate, then update the algorithm with a large sample size, which means + oc and 7 - have to perform concurrently and dependently. Under this circumstance, it remains unclear whether CLT still holds for the SGD iterate itself and, if it does, what constraints between n and y are required. To address the issue, we directly approximate the SGD sequence with iterative linear random functions, skipping the intermediate stationary process. Our methodology exhibits superiority in the sense that, with weaker assumptions, it reveals the simple yet essential relationship between the number of iterations and learning rate sufficient for quenched version of CLT that holds for any initialization 6u, and also demonstrates how standardized SGD sequences converge to the normal distribution despite the ordering of limitation on and 7. Furthermore, with slightly stronger condition, linear approximation leads to another powerful finite-sample Gaussian approximation the Berry-Esseen inequality [Chen and Shao 2001] Korolev and Shevisova 2010 Raid [019] - which characterizes the explicit order of distance between SGD and the Gaussian distribution with the number of iterations and learning rate.
Beyond the asymptotic theory, the existing literature on non-asymptotic uncertainty quantification has primarily focused on the linear model [Durmus et al. 2021 Zhu et al. 2022 Agrawal la et al. 2023
Samsonov et al. 2024] or the power-law decaying learning rate [Anastasiou et al.] [2019 9 [hha and Zhang 2022; Sheshukova et al. 2025). which introduces additional tuning parameters and suffers from surged sensitivity to hyperparameters and slow convergence [Nemirovski et al. 2009 Chee and Toulis 2018). Nevertheless, fixed learning rate has recently gained popularity for its simpler tuning requirements and rapid forgetting of the initial value. Moreover, also enables parallelization of multiple SGD runs to accelerate convergence and one employ extrapolation techniques for bias

---

correction [Dieuleveut et al. 2020]. However, establishing non-asympiotic theoretical guarantees for constant learning-rate SGD poses greater challenges due its persistent oscillations around stationary region induced by non-diminishing step sizes [Dieuleveut et al. 2020; Cardot et al. 2013 2017]. To grasp the recursive nature of SGD and comprehend nonlinear dependence structure, we present a systematic and sophisticated framework based on coupling and dependence measure theory established in Wu [2005]. The high-level idea throughout this paper is to reveal the intrinsic complexity of time series by slight modifications of input data or the iteration mechanism.
1.1 Contributions
This paper advances the theoretical understanding of constant learning-rate SGD by introducing novel approximation techniques and deriving sharp finite-sample guarantees. Our main contributions are:
A iinexr-aprroximation CLT for constant-step SGD. We develop a new linearization framework that captures the drift and noise dynamics of SGD iterates. Under substantially weaker smoothness and moment conditions than those in Pflug (986) and Dieuleveut et al. [2020]. we prove central limit theorem showing that, as the step size 7 + O, the properly scaled SGD iterate converges in distribution to Gaussian law.
Non-asymptotic p-th moment bounds for 2 2. Going beyond weak convergence, we derive explicit finite-sample upper bounds on EE, (-]r for any integer p The moment convergence rate quantifies how quickly all higher moments of the eπror decay in n, which provides more refined theoretical guarantee compared the weak convergence in the probability measure.
First Berry-Esseen bound in the Gaussian approximation. We first provide quenched version CLT of the last-iterate SGD. Under mild regularity conditions, if - oo and y with ny 2 y log for some v 2 1/(27), then for any initialization Pg E R2 the scaled iterate satisfies
Pn 0" (0,0),,
where the matrix I is later defined in type rate (up logarithmic factors) for the distributional distance between the scaled SGD iterate and its Gaussian limit. We quantify how rapidly the convergence to normality occurs in finite samples and fixed by providing the rate for
(6) Furthermore, we also obtain the Berry-Essee
On
0- E E P(N(O,)) E D)
sup IP DEV
where V is the collection of all convex sets in IRd, This is the first Gaussian approximation bound for constant-learmingraat SGD in general settings, which allows one assess the accuracy of statistical inference with finite samples.
Nagaev-type large-deviation inequalities. By approximating the SGD recursion with an autoregressive process, we derive sharp Nagaev-style tail bounds that control the probability of large deviations beyond the CLT regime. These results yield explicit sub-Gaussian and polynomial terms in the convergence rate for P([0, 0*1 <) for any >> which relates to tight sample complexity bounds significant for statistical learning theory and applications [Valiant 1984.
1.2 Other related works
Stochastic Gradient Descent. The large-sample behavior of SGD and its extensions dates back the foundational analyses by BBum [1954] (aacs (1988). who first investigated its asymptotics
and has since been elaborated upon by succession of studies [ijng 1977 Lail 2003 Wang and
Gao (2010) Gandikota et al.) [022]] Zhong al. 2024 Li et al., 2024 In particular, Fabian [968 characterized the limiting law of the final iterate. Robbins and Siegmund [1971] then leveraged martingale arguments to establish almost-sure convergence of the procedure. Subsequent research has quantified the algorithm's 's convergence rates under a variety of assumptions (ouuls and Airoldi 2017, Pillaud- Vivien et al. 2018 Muecke et al., 2019: Duchi and Ruan 2021]. See more recent
works by Zhu et al. 2022 Hu and Fu 2024 Lauand and Meyn (2024] among the others.
3

---

Convergence with different learning rates, The learning- choice in SGD, either fixed or
decaying, critically shapes convergence, Pilug [986] first studied the stationary behavior under a
constant step size via a Markov-chain framework: Dieuleveut Drauleork,Deeelleeeuu et al. [2020] : Huo et al. [023 Merad
and Gaïffas [023] later refined this with Wasserstein-disaacee ynalyses and high-confidence bounds.
For diminishing steps, Rakhlin et al. [012] showed the linear decaying case attains the optimal rate,
and Ge et al. 2019] extended the results to polynomial decays. Burn-in strategies were proposed by Gower al. [019 and Nguyen et al. [2019]. Adaptive schemes include Polyak's method for
wver-parameterized models [Loizou et al. 2021 and a bandwidth-based family studied by Wang
and Yuan (2023). See Jiang and Stich (024] for comprehensive overview. However, in practice, constant learning rates are favored due to the simplicity of training, which is also the focus of this study.
(Non)-ssymptotic normality. In addition to convergence guarantees, performing real-time inference with SGD--ttyle estimators is vital for uncertainty quantification. Classical bootstrap-based M- estimation methods [Fang et al. 2018 Fang 2019 /Zhng et al.) 2024] are computationally prohibitive in streaming contexts. Instead, Ruppert averaging [Ruppert 1988 Polyak and Juditsky [992] offers statistical efficiency and enables inference: the averaged SGD (ASGD) sequence [Györfi and Walk 1996 Defossez and Bach, 2015] admits an asymptotic normality result at the optimal rate Moulines and Bach 2201 Dieuleveut and Bach, 2016 Dieuleveut et al. 2017: et al. 2018]. By contrast, inference on the final iterate under constant step size has seen little treatment. We close this gap by proving a quenched central limit theorem for the SGD estimator as the learning rate y + O, valid from any initialization (Dahlhaus and Rao 2006 Dahlhaus et al. 2019]. Additionally, blocking- based variance estimators [Chen et al.J 2020; Zhu et al., [023] and recursive kernel approaches
(Huang et al.,, [2014] achieve optimal mean- saaa---urre--rror rates under dependence, yielding practical, theoretically sound online inference for SGD.
1.3 Notation
For vector v == (.1....,.a)) va)T E Rd and > O, we denote |p|g = EE 10/1 and [0] = |o|2- For any > 0 and random vector X, we say X E L if |X||, = (B < x.. For two positive number sequences (an) and (bn), we say dn = O(b,) or an S bn (resp. an x b,) if there exists C' > 0 such that an/bn I C' (resp. I/C < an/bn I C)) for all large n. and write a, = o(b,)) if a,, /b, + 0 n + Do. Let (X,,) and (Y,) be two sequences of random variables. Write X,, oY,, if X, + 0 in probability product in the finite dimensional Fuclidean space Rdd
co. Let (, denote the canonical inner
2 Moment convergence
We first introduce the following assumptions the objective function G(O)) and the stochastic gradients ()) Assumption 2.1 (u-strong convexity). The function G is twice differentiable and u-strongly convex, i.e. for a μ > and for all 0,0' 0'0'= E IRd, it holds that
(VG(0) - VG(0", 0¹) 2 n1/ -
Since Assumption 2.1 requires that G is twice differentiable, the Hessian matrix V²G((") exists. Note that for the T.P convergence in Theorem 2.3] we only need G to be continuously differentiable. The existence of Hessian is only necessary derive the CLT and Gaussian approximation in Theorem 3.4 and 3.5
Assumption 2.2 (Stochastic Lipschitz continuity). The function g(0.x) x) is continuously differentiable w.r.t. 8 for any æ. Moreover, for some p 2 2, assume ([ ,XII, =: Mp < co, 110 - 0" 1lp Pp < oo, and the stochastic Lipschitz continuity,
(V x) Fg(02,X)l S Lp 021. for all 0,, B2 E Rd
Here, the condition |0g - 11 < oo trivially holds in the sreed-iitiializatinn setting. Both strong convexity and Lipschitz continuity conditions are commonly adopted in the literature; see for example, Diculeveut et al. [2020]: ; Zhu et al. [2022]: : Merad and Gaiffas [2023.. J. Notably, Assumption 2.2 also
implies the L-smoothness of the gradient of objective function G. that is
[V(())) - vG(02) < 1p101 021. for all 02, 0g gd

---

should be satisfied to ensure convergence, i.e., the total length of steps needs to be sufficiently large such that SGD can move on. This relationship is quite natural and required by most of the literature SGD (Polyak and Juditsky 1992 Kushner and Yin 1997. Sheshukova et al. well-known that o We refer to Li et al. [024] for detailed discussion. Now we are ready to present the L moment convergence of constant learning-rate SGD.
Theorem 2.3 (LP Convergence). Suppose that Assumptions 2.7 and 2.2 hold.
Let be some
constant satisfying
{- (7.24 (6p 5)
0 < S min
(3)
Then, for any and satisfying
2/1
0 0<9< - (6
(4)
we have,
(5) Remark (Rate of moment convergence). The right-hand side of (5) demonstrates that SGD with a constant learning rate forgets its initial condition with exponential pace. Besides, if we determine the learning rate "( based on the knowledge of the total sample size or number of iterations n, a constraint nry
1 -07) 0g 3 1)3001
2.25y. For example, consider the decaying learning rate schedule 1h x n1 can not exceed 1 for the sake of Ei=1 1K OC
3 CLT and Berry-Esseen theorem
In this section, we introduce how to approximate SGD sequences with recursive linear random func- tions. Consequently, we establish asymptotic normality and finite-sample Gaussian approximation directly on the SGD iterations.
3.1 Dependency of SGD iterates
In recursive algorithms, each new updated estimator depends the last update and the new-coming random sample, which involves an intricate dependency structure that poses a challenge to nor- mality analysis. To address this issue, leverage the theory of functional dependence mea- sure introduced in Wu 2005 to quantify the dependence structure of the SGD algorithm. De- X for some measurable function Tn that vary for different and of-) = T (X,, 1X1, X2, X,-1, X,,,,,, Xn), where X; is an i.i.d. copy of Xx. The functional dependence measure is defined
fine 8, Tn (X,, X2,
(n, (n,t,p) 1|0, 0
We denote (n, (n) for simplicity. In particular, (m1, t. p) quantifies the effect of the random sample X, on the n-th SGD iterate 0,, By utilizing this tool, we can derive exact Gaussian approximation and tail probability rates. We first provide an essential bound of this dependence measure, which will be heavily used in the proofs.
Theorem 3.1 (Functional dependence measure). Suppose the same conditions of Theorem hold. The functional dependence measure satisfies
(n,, t) < 22/2(1 (o 1)/2 / M3 (07(1-0)))--03-- + 1333--1)M3a0j 1)M3a. 77.
Remark (Rate of dependence measure). Theorem 3.7 encapsulates the temporal dependence of constant learning rate SGD, which decays at an exponential rate as the time lag increases.
3.2 Refined linear approximation and asymptotic normality
We first introduce another assumption only required for the rest of this section.
Assumption 3.2 (Local Smoothness). There exists some constants 2 and k > 0 such that for all
| - 0+| <
(2 v²G(0") L/0 0%).
5

---

The local smoothness of the Hessian is standard in the literature statistical inference and normal approximation of online learning algorithms [Anastasiou et al. 2019 Shao and Zhang, 2022 [i et 2022 Sheshukova et al. 2025). Assumption in [Anastasiou et al. 2019] requires stronger global Lipschitz smoothness. We only need this condition to ensure the validity of Taylor's expansion of the gradient, i.e.,
[V((0) - ( 10-
which is also commonly imposed [Ruppert 1988 Polyak and Juditsky 1992 and necessary for Assumption H6 in [Moulines and Bach 2011
Define A == G(0") as the Hessian matrix of the objective function G(O) at 0 0", and $ = V[Vg(0", ) ).,)
gg(0", X.) 'I as the covariance of the stochastic gradients, also at the true parameter 0". Denote the estimation error by A,, On 0" We have
D An 7AAn-1 + RRn yD,, VVg(0" Xx,),
where we define the Taylor expansion remainder and the martingale difference noise term respectively by
R. 1
D, VG((n-1) Vg(On-1, X,)) + Vg(l", X,).
Recursively updating the formula, we get
An (Ia - 7A) Do - Ln + in, + 12
where
n
Ln =7 Y [Ia gA)"~>Vg(8""... Xt),
1n = (La n> Rg and Iz,n = = (I. - > Dg. Due stochastic Lipschitz continuity and [5 the terms In, and 12,n are infinitesimal of higher order, and the estimation error of SGD can be well approximated by the linear sequence L,. Let X X, 0 denote the largest and smallest eigenvalue of A, and À = min(),, on). We have the following result,
Lemma 3.3 (Linear approximation). Under Assumption 3.2 and same conditions of Theorem 2.3 for
1 y < minf x- (6p 53
/
we have
(3CbM2 Aoo
2 2/3L2M2
) ++ 2L2p2
|A, Lnlla 5
V Vi(1- xy) + Copšny(1 27)n-1
Vdcr
where Co = max 21
We will show in the appendix that the scaled limiting covariance of the linear sequence L,, can be obtained from the Lyapunov equation. Specifically, let I be the unique solution of
AI + PA 1TA = S,
which can also be written as
T
6 -A - Atdl.
(6)
R+
Then the following limitation holds
Cov(Ln)
T= lim ny
This asymptotic covariance is in accordance with results PPllug 1986 Chen al. 2022 Wei et al.) 2025). In the theorem below, we present refined CLT result via the linear approximation technique.

---

Theorem 3.4 (Quenched Central Limit Theorem). Under same conditions of Lemma 3.3 let n + co and y - 0 such that ny 2 vlog n for some constant > 1/22. Then, for an SGD sequence {OnINEN with arbitrarily initialization 0g Ed, we have
0n 0r D N(,T)
Remark (Quenched version of asymptotic normality). In most classical CLT-type results for SGD, one assumes that the iterate sequence (0n) heN is stationary, which means choosing the initialization 9o exactly following the limiting stationary distribution of 9, |Pfuug 1986] Dieuleveut et al. [2020] Chen et al. 2022y. Instead, our quenched CLT yields stronger result which guarantees the asymptotic normality of SGD sequences with any arbitrarily initial point Og E R".
Notably, the relationship ny Z log n is minimal condition for SGD in most settings discussed before. Consider the decaying learning rate schedule x n n taking a 1, the minimal rate of the total step size Ex=1 7/ is also Ologg)) n)).
3.3 Non-asymptotic Gaussian approximation
The central limit theorem 3.4 establishes a weak convergence of SGD to the Gaussian distribution. However, it does tell how close the SGD iterates are Gaussian, and how fast converges when the number of iterations grows the learning rate is turned down. For example, it is natural to ask how small the following distance could be
-
E
for some confidence interval of concern, but the CLT can not help due to its asymptotic essence. Consequently, the effectiveness statistical inference still questionable with finite sample and fixed learning rate.
This restriction motivates us investigate the non-asymptotic convergence rate to normality. The Berry-Esscen theorem is powerful tool to quantify the maximum approximation error. In the original groundbreaking work [Berry 1941; Esseen 1942], the Kolmogorov Hoinnogoroo-Smmmov Smirnov distance between the empirical distribution and the Gaussian is specified as
sup (x) ((x) < 0.33554E X - 0.4748 zERt
(EX?)2/3
where F2 is the cumulative distribution function (cdf) of i..d. average X1, Xi,... Xn with a finite third moment, and d is the standard normal cdf.
Taking advantage of the linear recursion and functional dependence measure, we develop the following optimal Gaussian approximation result for constant learning rate SGD.
Theorem 3.5 (Berry-Esseen bound). Suppose that Assumptions 2.1 and 2.2 hold with p 2 4, and
the same conditions of Lemma 3.3 hold. Let V = (D Rd D is convex. and Yr be mean normal vector in R with covariance T. Then, we have the following Berry- Esseen inequality:
sup IP E D) - -P(PE
DEV
SC + (1- Xx) " + - + (1 -m7)
where a constant independent of n, 7 and 6n.
Remark (Rate of Gaussian approximation). The first term comes from the third moment of linear approximation sequence. The second and third terms come from the dependence structure of SGD and the error of linear approximation. The last two terms are due to the difference between finite- sample and asymptotic covariance. To the best of our knowledge, Theorem is the first Gaussian approximation result for constant leurning-rate SGD that explicitly bounds the distance between distributions with specific order of y and n. The dominant term . can not be improved, since the bios of SGD is O(7) which can not be eliminated Dieuleveut et al. 2020 As a result, Dn! / /7 is at least O (7) away from the centered Gaussian vector.
7

---

Suppose we know the number of iterations priori. To choose appropriate 7 scaling with the right-hand side can be nearly optimized by setting y x vlog n/n for some 1/x. Then the order of Gaussian approximation becomes
vlog n vn
sup P DEV
E - P(Y D)
similar result of ASGD with decaying learning rate schedule 7/n x n is developed by (Shao and Zhang 2022 Samsonov al., 2024), where the optimal approximation rate O(n (n11)/). In
comparison, the normal approximation rate is sharper with constant learning rate SGD.
4 Sharp concentration of tail probability
In addition to Lp convergence, CLT, and Gaussian approximation, another vital concern is the tail behavior of the estimation enror, the expected error rate not be achieved by a one-time implementation. Practitioners want to ensure an ideal performance the algorithm in a single trial, especially under non-linear and heavy-tailed noisy settings. To this end, we generalize the method developed in Nagaev 1979] to provide a high probability guarantee the estimation accuracy without the requirement of bounded or uub-Gaussian gradient noise.
4.1 Non-linear autoregressive approximation
We use the following non-lineat autoregressive sequence to approximate the SGD sequence. Let 30 0 and
Bn = 3 - -iG----VVGB--) - ~Vg(00" X.))
The sequence Bn can be viewed as the gradient descent iteration with i.i.d noise. The following lemma characterizes the convergence of B, and the approximation error rate.
Lemma 4.1. Under same conditions of Theorem 2.3
3(p
1)M2 an
1I, - 10 -1 <
and for some constant 0₁ such that
on S min 71l
we have
11),-1,) ao7) + 3(p- - 1) 72
3(p
||0, Bnll S (1-aa0 a17)"
+ 4 (11a))))
ayai
Remark. Compared to Lemma 3.3 the non-linear autoregression sequence can approximate the SGD in space for p 2 2. which is more useful for precise derivation of tail probability.
4.2 Nagaev-type inequality of tail probability
To analyze the concentration property SGD with fixed learning rates, we first focus on the linear functional of the estimation error, i.e., v. (0., 0²) for all v Sd, the unit sphere in Rd. The probability bounds directly from the Lp convergence or Gaussian approximation rate are too conservative. Simply applying the Berry-Esseen incquality [35]] for instance, will result in sub- Gaussian tail plus an inevitable / term. Another naive way is to use the Markov inequality on If we set the degree of tolerance as it yiclds
Theorem 2.3
P(2 (0,, 8¹) c) S
e0 [11 aur) nD/ Pf Maa 2/300122013)
(7)
where the polynomial term 7/2 is far from optimal. As result, for some credible level with probability ö, one can only have
<
|v (0,. 0*)l 0(6 1/8 /7).
8

---

According to 2 y- the resulting estimate of sample complexity [[c, 6) (i.e., the minimum number of iterations such that the MSE satisfies the given credible level and degree of tolerance e).
N(e 6) = 2/P
grows rapidly for any tolerance level å E (0,
The next theorem provides a Nagaev-type high-contidence bound that is substantially tighter than existing results by incorporating functional dependence measures, non-linear autoregressive approxi- mation and the moment- generating function.
Theorem 4.2 (Nagaev inequality). Under same conditions of Theorem 2.3 for any 0, we have
C17 +2expf e²
C2c²
y } 2F-1 P (0(1-07))mp) mp/2
(14(0-1)L,,00 1/2
sup vE84
cP
where C1 and C2 are some positive constants independent of n, Y and 0g-
Remark (Rate of tail probability). The polynomial term in Theorem 4.2 is -p much sharper than those obtained from Gaussian approximation or Markov inequality when > The sub-Gaussian term exp(-C2e² /7) is optimal in the sense that Dal V is asymptoticully normal. With high degree of tolerance e, the polynomial term dominates, and the estimate of sample complexity can be greatly improved to O6 1/(p-1) (0/l-1)e-///111100 p//(p-11) 1) in this case. With low degree of tolerance, the Sabb-Gaussinn term dominates.
O05-1/(p-11
We directly obtain the same result of the uniform distance between On and 0* by the union bound. Taking u over the standard basis (O...., 0, 1,1,0....,)) 0)T yields
Cid7
+ +2dexp( -22²²
C2E2
P(I| Am > () S
2 dpp(1 - mp7)
[1+ + 1(p 1)
e²
5 Numerical studies
5.1 Simulation setting
We conduct simulation demonstrate that our Nagaev-type incquality in Theorem 4.2 is indeed valid and tight. Consider the following data generating mechanism for the logistic regression model: X, (a., b,), 1, 2, are i.i.d. random vectors where a; are generated from a 5-dimensional independent t distribution with degrees of freedom df = 3. b, E (1.-1} follows a Bernoulli distribution with the probability given by P(byla,) = 1/(1 + exp((-bccc 0*)). The loss function is defined as the negative log-likelihood,
g(0, X.) log(1 + exp((b;a), 0)).
We investigate logistic regression for its non-linearity. The distribution with df y only has finite p-th moments with < This property enables us to study the performance of different tail probability bounds with specific values of p. Elementary calculation shows that
ba
Vg(e, x) Fg(0,a,b)
exp(ba 0)
and therefore ( X)) only has finite p-th moment with p in our setting. Theoretically, can choose p arbitrarily close to 3 and apply the inequalities discussed in Section[4.2 For simplicity, take p = 3 since the results report in the simulation are continuous with respect p.
We run 1000 independent trials with n = 500000 and 7 = 0.005, 0.001, 0.0002. Since the number of iterations is large enough, the main contribution in the tail probability bounds are the polynomial terms and the sub-Gaussian term, i.c.,
p/2
1I
eP

---

Proberity
36-05
26-24
26-08
320
0.29
0.50
0.75
0.10
2.15
0.500
00225
0050
0072
D100
Figure 1: Comparison of different tail probability bounds against the empirical probability. The learning rate 0.005, 0.001, 0.0002 from left to right.
in the Markov-type bound, and
70-1 EP
C2c²
112
-2 eexp
in the Nagaev-type bound. In our simulation, we set C2 2, because Theorem 3.4 provides the equation that the asymptotic covariance I' satisfies. Elementary calculation Chen et al. 2020 shows that for the logistic model, S, and the unique solution AT + IA becomes La/2, so we accordingly scale the sub-Gaussian term.
5.2 Numerical results
We compare the concentration inequality (7) and our Nagaev-type bound, Theorem 4.2 both with the empirical probability: II, Avg. (P((e (e,. (8, 8*) <)), where ranges the standard basis vectors .O...., 0, 1,0,.... O)T. For more transparent visualization,
multiply these quantities by e" and plot the results against the degree of tolerance e. Figure [ the x-axis is the degree of tolerance. The green, red, and black curves are c I22,, and e² I[3, respectively. They represent the e--scaled Markov bound, Nagaev bound, and empirical probability.
Figure D clearly indicates that the tail probability bound from Markov inequality is excessively conservative. contrast, our Nagaev-type inequality from 4.2lees a much sharper upper bound for SGD across different learning-rate scales. The shape of empirical probability closely matches the dichotomous phenomenon theory: the dominance transits from the polynomial term to the
term as decreases. The experiment results confirm that Nagaev-type bound is both valid and tight, precisely describing the tail behavior of constant learning rate SGD.
Acknowledgments and Disclosure of Funding
We sincerely thank the program chair, senior area chair, area chair, and the five reviewers for their constructive feedback and involved discussion, which has greatly improved the clarity of our paper. Jiaqi Li's research is partially supported by the NSF (Grant NSE/DMS NSF/DMS-2511922,, Wei Biao Wu's research is partially supported by the NSF (Grant ASF/DMS-23111299 We would like to thank Johannes Schmidt-Hiehhe for helpful discussions.
References
Agrawalla, B., K. Balasubramanian, and P. Ghosal (2023). High-dimensional central limit theorems for linear functionals of online least-squares sgd. arXiv e-prints, arXiv-2302
Anastasiou, A., K. Balasubramanian, and M. A. Erdogdu (2019). Normal approximation for stochastic gradient descent via non-asymptotic rates of martingale In Conference on Learning Theory, pp- 115-137. PMLR.
10

---

Berry, A. C. (1941), The accuracy of the gaussian approximation to the sum of independent variates. Transactions of the American Mathematical Society 49(1), 122-136.
Blum, J. R. (1954). Approximation methods which converge with probability one. The Annals of Mathematical Statisties 25(2), 382 386.
Cardot, H., P. Cénac, and A. Godichon- Bagggioni (2017). Online estimation of the geometric median in Hilbert spaces: Nonasymptotic confidence balls. The Annals of Statistics 45(2), 591 614.
Cardot, H., P. Cénac, and P.-A. Zitt (2013). Efficient and fast estimation of the geometric median in Hilbert spaces with averaged stochastic gradient algorithm. Bernoulli 19(1), 18 43.
Chee, and P. Toulis (2018). Convergence diagnostics for stochastic gradient descent with constant learning rate. In Proceedings of the Twenty-First International Conference Artificial Intelligence and Statistics, pp. 1476 1485. PMLR.
Chen, L. H. and Q-M. Shao (2001). A non-uniform berry-esseen bound via stein's method. Proba- bility Theory and Related Fields 120, 236-254.
Chen, X., J. D. Lee, X. T. Tong, and Y. Zhang (2020). Statistical inference for model parameters in stochastic gradient descent. The Annals of Statistics 48(1), 251-273.
Chen, Z., S. Mou, and S. T. Maguluri (2022). Stationary behavior of constant stepsize sgd type algorithms: An asymptotic characterization. Proceedings of the ACM on Measurement and Analysis of Computing Systems 6(1), 1-24.
Dahlhaus, R. and S. Rao (2006). Statistical inference for time-varying ARCH processes. The Annals of Statistics 34(3), 1075-103 1114.
Dahlhaus, R., S. Richter, and W. B. Wu (2019). Towards general theory for nonlinear locally stationary processes. Bernoulli 25(2), 1013-1044.
Defossez, A. and F. Bach (2015). Averaged least-mean-squares Bias-variance trade-offs and optimal sampling distributions. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, pp. 205-20 213.
Devroye, L., A. Mehrabian, and Reddad (2018). The total variation distance between high- dimensional gaussians with the same mean. arXiv preprint arXiv:1810.09699..
Dieuleveut, A. and F. Bach (2016). Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics 44(4), 1363-1399.
Dieuleveut, A., Durmus, and F. Bach (2020). Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics 48(3), 1348-1323 1382.
Dieuleveut, A., N. Flammarion, and F. Bach (2017). Harder, better, faster, stronger convergence rates for least-squares regression. The Journal of Machine Learning Research 18(1), 33700.
Duchi. J. C. and Ruan (2021). Asymptotic optimality in stochastic optimization. The Annals of Statistics 49(1), 21 48.
Durmus, A., F. Moulines, A. Naumov, S. Samsonov, K. Scaman, and H.-T. Wai (2021). Tight high probability bounds for linear stochastic approximation with fixed stepsize. Advances in Neural Information Processing Systems 34, 30063-30074.
Esseen, C.-G. (1942). On the liapunov limit error in the theory of probability. Ark. Mat. Astr. Fys. 28, 1-19.
Fabian, V. (1968). On asymptotic normality in stochastic approximation. The Annals of Mathematical Statistics 39(4), 1327-1332.
Fang, (2019). Scalable statistical inference for averaged implicit stochastic gradient descent. Scandinavian Journal of Statistics 46(4), 987-1002.

---

Fang, Y. J. Xu, and L. Yang (2018). Online bootstrap confidence intervals for the stochastic gradient descent estimator. Journal of Machine Learning Research 19, 1-21.
Gandikota, V., D. Kane, R. K. Maity, and A. Mazumdar (2022). vqsgd: Vector quantized stochastic gradient descent. IEEE Transactions Information Theory 68(7), 4573 4587.
Ge, R., S. M. Kakade, R. Kidambi, and Netrapalli (2019). The step decay schedule: near optimal, geometrically decaying learning rate procedure for least squares. arXiv preprint. arXiv:19044 Sklv:1904.128388
Gower, R. M., N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtarik (2019). SGD: General analysis and improved rates. Proceedings of the 36th International Conference on Machine Learning 97, 5200-5209.
Györfi, and H. Walk (1996). On the averaged stochastic approximation for linear regression. SIAM Journal on Control and Optimization 34(1), 31-61.
Hu, J. and M. C. Fu (2024). Technical note-on the convergence rate of stochastic approximation for gradient-base based stochastic optimization. Operations Research. To appear.
Huang, Y., X. Chen, and W. B. Wu (2014). Recursive nonparametrie estimation for time series. IEEE Transactions on Information Theory 60(2), 1301-1312.
Huo, D., Chen, and Q Xie (2023). Bias and extrapolation in markovian linear stochastic approxi- mation with constant stepsizes. arXiv preprint. arXiv:2210.00953.
Jain, P. S. M. Kakade, R. Kidambi, Netrapalli, and A. Sidford (2018). Parallelizing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecification. Journal of Machine Learning Research 18(223), 1-42.
Jiang, X. and S. U. Stich (2024). Adaptive SGD with polyak stepsize and line-search: robust convergence and variance reduction. In Proceedings of the 37th International Conference Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, pp. 26396-26424. Curran Associates Inc.
Korolev, V. Y. and I. G. Shevtsova (2010). On the upper bound for the absolute constant in the berry-esseen inequality. Theory of Probability & Its Applications 54(4), 638 658.
Kushner, H. J. and G. G. Yin (1997). Stochastic approximation and recursive algorithm and applica- tions. Application of Mathematics 35(10).
Lai, T. L. (2003). Stochastic approximation: invited paper. The Annals of Statistics 31(2), 391 - 406.
Lauand, C. K. and S. Meyn (2024). Revisiting siep assumptions in stochastic approximation. arXiv preprint. arXiv:2405.17834
Li, J., W. Mou, M. Wainwright, and M. Jordan (2022). Root-sgd: Sharp nonasymptotics and asymptotic efficiency in single algorithm. In Conference Learning Theory, pp. 909-981. PMLR.
Li, J., Z. Lou, S. Richter, and W. B. Wu (2024). The stochastic gradient descent from nonlinear time series persective. Manuscript.
Li, J., J. Schmidt-Hieber, and W. B. Wu (2024). Asymptotics of stochastic gradient descent with dropout regularization in linear models. arXiv preprint. 0744444
Ljung, (1977). Analysis of recursive stochastic algorithms. IEEE Transactions on Automatic Control 22(4), 551-575.
Loizou, N., S. Vaswani, I. H. Laradji, and S. Lacoste-Julien (2021). Stochastic polyak step-size for SGD: An adaptive learning rate for fast convergence. In Proceedings The 24th International Conference on Artificial Intelligence and Statistics, pp. 1306-1314. PMLR.
Merad, I. and Gaiffas (2023). Convergence and concentration properties of constant step-size SGD through Markov chains. arXiv preprint. arXiv:2306.1144 1497. 14997.
12

---

Moulines, E. and F. Bach (2011), Non-asympiotic analysis of stochastic approximation algorithms for machine learning. In Proceedings of the 23rd International Conference on Neural Information Processing Systems, pp. 856-864.
Muecke, N., G. Neu, and L. Rosasco (2019). Beating sgd saturation with tail-averaging and mini- batching. In Advances in Neural Information Processing Systems, Volume 32. Curran Associates, Inc.
Nagaev, S. V. (1979). Large deviations of sums of independent random variables. The Annals of Probability, 745-789.
Nemirovski, A., A. Juditsky, G. Lan, and A. Shapiro (2009). Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization 19(4), 1574-1609.
Nguyen, P. H., L. Nguyen, and M. van Dijk (2019). Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD. In Advances in Neural Information Processing Systems, Volume 32. Curran Associates, Inc.
Pflug, G. C. (1986). Stochastic minimization with constant step-size: asymptotic laws. SIAM Journal on Control and Optimization 24(4), 655-666.
Pillaud- Vivien, L., A. Rudi, and F. Bach (2018). Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Advances in Neural Information Processing Systems, Volume 31. Curran Associates, Inc.
Polyak, B. and A. B. Juditsky (1992). Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization 30(4), 838 855.
Raič, M. (2019). A multivariate berry-esseen theorem with explicit constants. Bernoulli 25(4A), 2853.
Rakhlin, A., O. Shamir, and Sridharan (2012). Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint, arXiv: 109.5677.
Rio, E. (2009). Moment inequalities for sums of dependent random variables under projective conditions. Journal of Theoretical Probability 22(1), 146-163.
Robbins, H. and S. Monro (1951). A stochastic approximation method. The Annals of Mathematical Statistics 22(4), 400-407.
Robbins, H. and D. Siegmund (1971). A convergence theorem for non-negative almost supermartin- gales and some applications. In J. S. Rustagi (Ed.), Optimizing Methods in Statistics, pp. 233 257. Academic Press.
Ruppert, D. (1988). Efficient estimations from slowly convergent Robbins-Monen process. Technical report, Cornell University Operations Research and Industrial Engineering.
Sacks, J. (1958). Asymptotic distribution of stochastic approximation procedures. The Annals of Mathematical Statistics 29(2), 373 - 405.
Samsonov, S., E. Moulines, Q.-.. Shao, Z.-S Zhang, and A. Naumov (2024). Gaussian approx- imation and multiplier bootstrap for polyak-ruppert averaged linear stochastic approximation with applications to td learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems.
Shamir, O. and T. Zhang (2013). Stochastic gradient descent for non smoohh optimization: Conver- gence results and optimal averaging schemes. In International Conference on Machine Learning. pp. 71-79. PMLR.
Shao, Q.- and Z.-S. Zhang (2022). Berry-Essent bounds for multivariate nonlinear statistics with applications to M-estimators and stochastic gradient descent algorithms. Bernoulli 28(3), 1548- 1576.
13

---

Sheshukova, M., S. Samsonov, D. Belomestny, E. Moulines, Q.-M. Shao, Z.-S. Zhang, and A. Naumov (2025). Gaussian approximation and multiplier bootstrap for stochastic gradient descent. arXiv preprint 1rXiv:2502.06719.
Toulis, P. and E. M. Airoldi (2017). Asymptotic and lample properties of estimators based on stochastic gradients. The Annals of Statistics 45(4), 1694 1727.
Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM 27(11), 1134-1142.
Wang, X. and N. Gao (2010). Stochastic resource allocation over fading multiple access and broadcast channels. IEEE Transactions on Information Theory 56(5). 2382-2391.
Wang, X. and Y.-x. Yuan (2023). On the convergence of stochastic gradient descent with bandwidth- based step size. Journal of Machine Learning Research 24(48), 1-49.
Wei, Z., J. Li, L. Chen, and W. B. Wu (2025). Online inference for quantiles by constant learning-rate stochastic gradient descent. arXiv preprint urXiv:2503.02178
Woodroofe, M. (1972). Normal approximation and large deviations for the robbins-monro process. Zeitschrift für Walrsscheinlichketttthhee und Verwandte Gebiete, 329-338.
Wu, W. B. (2005). Nonlinear system theory: Another look at dependence. Proceedings of the National Academy of Sciences 102(40), 14150-14154.
Zhong, Y., J. Li, and S. Lahiri (2024). Probabilistic guarantees of stochastic recursive gradient in non-convex finite sum problems. In Advances in Knowledge Discovery and Data Mining, Singapore, pp. 142-154. Springer Nature Singapore.
Zhu, W., X. Chen, and W. B. Wu (2023). Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statistical Association I 1/8(51)), 393-404.
Zhu, W., Z. Lou, and W. B. Wu (2022). Beyond sub- gaussian noises: Sharp concentration analysis for stochastic gradient descent, Journal of Machine Learning Research 23(46), 1-22.
14

---

A Technical Appendices and Supplementary Material
All theoretical results are proved in the appendix. We first introduce some technical lemma.
Lemma A.1 (Rio's inequality Rio 2009)). ). Let X I and Y R& be two random vectors such that [| < oo and Y < 0c for some 2. Then we have
X + Y 1 -
X (p 1)1
(8)
Lemma A.2. Under Assumption 2.7 and 2.2 have
[V((0) VG((2)) S 1p10 021.
Proof. By Assumption 2.2
[VVg(0,, X) Vg((2, x)1 S L,10, 0213, for all 0,, 02 Rd.
By the convexity of 1113 and Jensen's inequality,
[VG(0)) 2 |Ex (Vx(1,0 X) Vg(02, x))1
Ex|Vg(O,,,X) V9(0,,))1
1210 - 0212.
A.1 Proof of Moments Convergence of SGD
Lemma A.3. Consider the SGD iterates {01)22 in 22. Under the same conditions of Theorem 2.3 for some universal constant Ogg such that
{
ar min
1 2p (6p 5)
we have, for all 2 1,
| 11 < (1 (00))llnnn1) 3(p M).2
(10)
Proof of Lemma A.3 Since &,, for 2 1, are i.i.d. random samples, it follows from the tower rule that
g (,) VG(On-1) 0n-1] 0. Therefore, by applying Rio's inequality in Lemma A.I for p 2, we have
(11)
A 1| < 0 - -VG(00-1)) (p 1)n ( (n)) VG((n-1)]]
11 12.
(12)
We shall bound the two parts 1, and To separately. For the first part T1, note that VG(0*) 0 and by the triangle inequality, we have
I = |1m--1 - -VG
= |K - 0-, 0,,00111 0*) 27 (7 -G(0
+
- VG(0"), VG(B,-1)) VG p/2
< (0 - 8" 0-, - 8*) -2 0- VG VG(O')
p/2
+ 7 VC(On-1 VG(O")>? I|
(13)
By applying Assumption 2.1 to the first term and Assumption 2.2 to the second term, we can obtain
1 - (1 - 27p4 + >2 L3)) 10, 0-1
(14)
15

---

Regarding the second part I,, since VG((*) 0, we have
Vg(( VG 1)l
- (V
"0(00"..))l + |VVG(0,-1) - + " (15)
Hence, by Assumption 2.2 can achieve
[Vg(On-1. E.) VG((n-1)lIB - 00 1-11, 3 .
(16)
Combining results from II, and 11,, we can obtain
1 S (1 2yp + (6p 2 10,-1 00 3(p 1) V9(00,
This can directly lead the desired inequality.
Proof of Theorem 2.3 By recursively applying Lemma A.3 we have
A 1 < II a0))ao)))4001;+++ 3(p - 1)M3
(1 - an7).
(17)
k=1
k=j+1
By elementary calculations,
Am S -00))" pz 3(p 1)M3raa"
(18)
A.2 Proof of the Bound for Functional Dependence Measure
Recall that the SGD sequence On can represented by O, = Tn .,.,,,,, and 0 To (X1,.... ".-...,,-,,, X₁, Xt+1.... ...,, Xn) for some measurable function that can vary for differ- ent n, where X an i..dd copy of X,. The functional dependence measure was defined as (lnn,,,) t.p) = ||O, 0!0 lp- We prove the bound for (in, p) as stated in Theorem 3.1 which is fundamental to the proofs of CLT, Berry-Esseen inequality and Nagaev-type inequality.
Proof. By applying Rio's inequality, for each S n 1, we have
0(4) 1| & (1 27pu + (6p 5)> L - 10 01.0112
|0,,
I (1 a07) - 0¹¹) 1|2
(19)
follows from Assumption 2.2 that for all / 1,
(V9(0.1,,X))Il
2
< 22,7101111 13, 2M2
(20)
As direct consequence, we can achieve
||0 - o! 112 7 2111 10(0,11,x)111
< g2 X,)1 x2)
< < (1,
M2)
(21)
This along with expression (19) and Theorem
2.3 provides the desired result.
A.3 Proof of Quenched CLT
Here and in the sequel, we will repeatedly use basic property that IL. - 7 S 7d. $1 7-72. We denote Z, Vg(0", Xx)) the gradient noise.
16

---

Proof of Lemma 3.3 We first show that 1.n and I2,n vanish. Define Fo 0 and a; = - as the filtration generated by the data. It clear that {D,, martingale difference sequence w.r.t. the filtration {Fr), and we have
2, 12 < 7
II 22
$ 4h L3
[I - --4)1 10112n22211000 20110 - -0-12
k=1
n
n
S < L3
[1(Ia - 7A)) (1)
P2 02++
12L31 Σ
(I1a - ->AIl' 2n-2x 24
(1 --2))-11 -(1 (1 -2)22n11
-1 1 (1 72)2n
S 44 L3p2
71
2 72
(1- (1>1))=-1 12L3?2M3
472
00(22 - -723)
1-))-11
A + 1
S 4422257
aud
Here we use the fact that [D,] S 2n due Assumption 2.2 Lemma A.2 and the triangular
inequality. The last inequality comes from S 1/a0 and S 1 /x.. By Taylor expansion around 6*, since VG((0)= = 0, we have
R2 AAn (VG(On-1) -VC())
L. V2G + 1(000111111-1 07)) - G²((0')[(0n1 )dl.
when 10m-1 1 S K, we have R,, < L - For 10 0* > the Lipschitz continuity of the gradient implies R, I 2L fn 8-1 S 2L2 -1 10 0¹ So we finally have [Ra] S Co where Co- max L, 2L2x 1.. As result,
By Assumption 3.2
11 S CoT Σ
[1 All- n *
-0112
-1 172 1 (1 7A)" S 5ny0 7A)=-1 + 33 ag
7d
I 11 - -7)=-11111---1 + 3C
(22)
Aaoa
We also have La -4>-AA"Aoll S (1 (1- - 7>>)"pp p1. Combining these inequalities will lead to the bound
in Lemma 3.3
Proof of Theorem 3.4 As 7 + 0 and ny 2 vloo n for some constant v > 1/2X, elementary calculation shows that the difference between An//T and Ln/ goes to 0, i... by Lemma 3.3 we have || an/VT- Ln/ /Fll + Then it suffices to prove that
Ln V
N(,,T.
(23)
Notice that Ln/ V is linear combination of i.idd. random vectors, the covariance matrix of which is
(7 LLa > S(IL 7
We introduce the following auxiliary lemma.
Lemma A.4. The minimum eigenvalue of In)), denoted as Xn (,))), satisfies
Xa(2) 2 As(1 - (1 )2)
2X-
where Àg is the smallest eigenvalue S. S.
17

---

This lemma is easy to prove since (Ig -44) is positive definite with the minimum eigenvalue 1 1-yX". So have
An (7)
- Xs
k=1
and elementary calculation leads the conclusion. The lemma implies that (?) is bounded by some constant. As + and ny + oc, we have
S (T) 7A)" S(La -A)
max
By the multivariate Lindeberg-Feller CLT, is clear that
T (n) 1/2 Ln & (.
(24)
To determine the closeness between r (7) and r, notice that
Tn+1 (7) (Ia - ,. - -A) + YSS.
Minus I on both sides and plug AT A S into the formula above, we
Tn+1 (7) = (I. - 7 7A)
- 72 AT
Hence, there exists a universal constant C such that
(n+1 r S (1
-I Ch2
Let ro(n) Oaxd- Recursively updating the inequality we get
[n(1) - r (11-)))((0))
(1 - -1) [o(?) - rl
(25)
1=1
Cy
$ 2A - 7X2 + (1 7\) r + O.
(26)
Since the eigenvalues of (7) are bounded and bounded away from O, and I' is a fixed positive definite matrix, we have r-1//r,,00 (7) 2 Ia. By Slustky's theorem,
r 1/2 Ln
-- 1-111/2 (T) 1/2 Ln 2 1(),
and we proved 23
Remark on the multivariate Lindeberg-Feller CLT
Suppose triangular sequence Un,k E Rdd are independent with means Eyn., 0 and covariance matrices Vn,* EEyo,. Set
Un
Vn 1 Amin(Un)
v and for all > 0
lim
E ElIyn,i 22 1( EV?)) = 0,
k=
then as n -> 00
n
1-2
Σ Yr.k N(0,
Above is the statement of the multivariate Lindeherg- -Fller CLT. We apply the theorem to the standardized sum
T,(r)
(Ia -A)" *
k=1
18

---

Denote
= ( Villa -AA)=E
Then
Yn = BBnx U, = La, 1 = 1.
Let Mn(r) be the maximum norm of the matrix prefactor of Un i.e.
Ma(+) = max IskSn
[Bn,(>)]
(Tx( - 77))2n2HH, 1sksn
max
We have shown that "1 is bounded by some constant. As result, Mn S - 0. This is sufficient for the Lindeberg condition and CLT. To this end, notice that
[(Vnn.|P1(Vnnn 22))
B (AL 2x))
By the dominated convergence theorem, we have
((Zz)2((M,,)))) 2 +0
due (>)l 2 2 c) + 0. By elementary caleulation, Ek= |Bn, (7)) is bounded. As result, the Lindeberg condition is justified.
A.4 Proof of the Berry-Esseen Inequality
begin with refined analysis of the linear approximation.
An = (Ia 7 - In + J1,n + 12,0
where JIn >> I ~ RR. 1, = (Ia -gA)~=DDr
DR. R2 AAn-1
VG(On-1). and D, VG((n-1) - (n)(1) invertible, and
X.,) + Vg(0", ...). By Lemma A.4 the matrix
VTrn(1)-112 S V7.
We further have the following decomposition:
n -1-))--1,,,01 P.(()) (La 7A)" Ln + 11,1 12.
The Gaussian approximation error will be assessed via those terms. Define
In = VT Σ
as auxiliary sequence. Define I (C), and (4 in the same way as 0 and
vD(n, t) = ||2, (0 la
as the functional dependence measure of J2,.. The next Lemma investigates the behavior of thp- Lemma A.S. For 1 < stnm n,
vbn(n, 1)a S 21 2n- + ---
Proof. Notice that
k << L
DR (
Vg X/) - - (G Vo(0
& = t:
k> t
19

---

it is clear that that D3- - D is also martingale difference sequence. Due to stochastic Lipschitz continuity,
(0(m,,1²=-70
LIa >A)= 1p
= Σ [Id >A) 7-)22
2k 2k Dx
D2
k=1
S (1 7
2n
21 Dj - 12 + 442n²
(1 (1-2A)3n-2BB))
(1)) -
k-1
k=1+1
By Theorem 2.3 and 3.1 we have
E|D, - 12 - < Vg(0(-11, Vg(00' xx)]? s 4 ~ (1-1111am) a07) (1-
and
F10+11 - (04) 1- == <b - 1,10= 1,1))=>>20 722(1 -00)
2
By elementary calculation,
2-1 uD(n,1) S 71 72)2 2t + 71) 2-1 + -
x x 72)2n- + 70(1 72)n-t-1
Now we are ready to prove the Berry-Esseen incquality.
Proof of Theorem 3.5 We apply Theorem 2.1 in Shao and Zhang 2022 Since we use Lnd V7
v7 Ek=1 (Id 7A) n
Z to approximate An/ v7, with
|
-A)" 7
3/2 27)a 2 V7,
Theorem 2.1 in Shao and Zhang 2022
states that
sup [P([n(n) 1/2 D) P(N(O, EDI DEV
<c <o (((T+EIIR L. / Σ BIJ - VT(L- 74)mm(z111 Zil)).
(27)
where I and (() are some quantities such that
J (T(())) 1/2 An Ln
-1/2 V7
(28)
and f(t) is independent of X, Ze We define
J = 1 1/2 (T(La - 7A) + +1 1/21 (1)))
(7) 112 12.1l + ČIn,
with some universal constant Ò such that ČIn 2 by 10--1, (7) ( Such Ö exists because of the construction of I, and Taylor's expansion. Then 28 holds by the triangle inequality. We further define
j(t) = [7,(7)- 1/2 VTLL - 7A)"
+ + 1
2,n + ČT(()) n
such that 70h] is independent of X, and Z,, and decompose the difference between I and its copula perturbation (() as
J(1 < II - -I(()] + 11/TT -1/22 I,, 1//////7100///1
-1/2 (() 2,n
$ I I + 1 1,)) -1 11, I(42)11
(29)
20

---

We will control each enror term decomposed above. We first investigate the following quantity:
B - - [T
Vi(La 7A)"
-1 Σ 11 - 10-
14 2411)) =
k=
which can be further controlled by
Ta, S 7(1 -11)))))
- (1- - k- |11)
km1
S 17(1-aa) (2)"-1 Σ (1 - 11->>>=>=EB (201100 12 001 11 001 }
We apply the Hölder inequality, for 1: 2 +
E Z
- +0 (10k
88}
- 221 1,1)
(1- (t0)--
where the last inequality if from Theorem 2.3 and 3.1 we have
For k S l, the expectation above is 0. Hence
Th. X -111-11--
Σ (1 (1- (1->2))~<(V7++ (1- (k- (1)0) 1--0
k=
772(1 - Az)
Σ
[1 - 1/22-11211 + v5(1 - -71) -
k=t+1
S 2 - ()(1 - Xr)) 22-31/2-11 + 5/2 (1 (7)(m-
- v1 11-7
(n - - A7) 27)22-31/221
301-3122-111 1-1 + 3/2 Xn)
Here the fact that v1 - bo < 1 22/2 By elementary calculations,
BlL - 1/2 V 7 - Σ
Tas S 2r) + V7. (30)
1=1
Similarly, by Cauchy inequality,
(7))) ((t) ([( 1/2 -V(La=1A)aa)) -Z,
(1 71)"~ | 1,(0/1
< (1 - 11)
< Xr) 1)/2 + 3/2 Xx) 33n-
Summing the quantity above from 1= to /. = n yields an upper bound
n
Eh 1h--1/2f,,07
1600 -10 VT 1/2 - -
(1- 1y) V7.
(31)
Then consider the following ertor terms due to linear approximation:
1/1 1/2 VLL ". /7)),
21

---

[(( 1/2 Vil2mll/Tn() 1122 Lnd VTI,.
and
BA
V-
We use the Cauchy inequality to bound them. Notice that by definition of T,((),, the sequence (a(1) Ln/ /7 standardized with fixed covariance matrix La. For the first term,
E(Ir(() 7.)) Ao Ln/ V7l L,// / (1))-))
(32)
For the second term,
Ln v < 2 122 1111))))lllll1x,,()))>>--),,, / 2 7 v5(1 (7)
(33)
For the third term,
Σ (1 72) (1A -1/2 I,. /71) 1=1
S 7)) 1
7))m -00) + +7]
- (1 - -
(34)
Combining all upper bounds of 29 and plugging them into the inequality 27 yields
(1) 1/2 An E D) - P( D)
sup DEV
S +
+ -
for some constant C' independent of and fg. By the discussion of Remark in Samsonov et al. 2024),, since (1/211/22 is non-degenerate, and an image of convex set under non-degenerate linear mapping convex set, we have
sup 112 An E D) - P(N(O,L)) e D)I = sup P DEV
E D) - -(N(O,,,())) e D)).
DEV
To complete the proof, Theorem 1.1 Devroye et al. 2024)), ), which bounds the total variation distance two Gaussian measures by the distance between their covariance matrix. Here we only need to bound the convex distance, i.e..
2018 (or Lemma 13 in Samsonov et al.
sup (P(((O, e D) ((N(0,)) D)1 r 1/21 111-1/1,,,)))) (7) Iallr. DEV
which trivially holds by Theorem 1.1 in Devroye et al. 2018
Since matrix norms are equivalent, by The last step is to use the triangular inequality the convex distance, and the proof completed.
(25) we have |||[-|//[,, (y)) I.l F + - 2n
A.5 Proof of Nagaev-type Inequality
We first prove the results non-lineat auto-regressive approximation.
Proof of Lemma
4.1 Similar to the argument of the proof of Theorem 2.3
1m
8" 13 < [| 0 - -VG + (p 1)>?
< (1 - 27p (6p- 56 0-113
3(p 1)
(35)
22

---

Recursively updating it, we get
3(p 1)M3
1 - 0011 S
000
For the second result,
10on - Bal1p
$ 10 - - 1G(
(36)
+ (p- 1)7211/((()n-) Vg
Xn) + 1
< (8h-1 - Bn- 8 - - 2y(0n-1 - Bn-1, VG((nn-) - VG( p/2
+^2 +=(|/V((On-))) - VC(Bn- 1)1 + +4pp 1) 1)>22,,100, 12110m11 0-11
(37)
$ - 27p + +,21,)110~11 11 + 4(p - 1)y² 1 -07)" 1100 0-
+ +3(p 1)MBa0''10
(38)
< (1 - (11))110060 10 - p 11 + 4(p - 131(1 - (100) 0-1
+ 3p 1)M3,00 -1 78/
(39)
(40)
where a1 S 2p -Lم and 01 s Without loss of generality, we can choose ag I 01 since the upper constraint of ogo is more stringent. Recursively updating the inequality, we get
3(p M)
|00, 3,11 = [11-a17)" + 4(p 10)_1122( (100)))]]1A
+
72
agai
Now we are ready to prove the sharp concentration inequality.
Proof of Theurem 4.2 Denote E, = EX as the centralized random variable X. Without loss
of generality, we let og I on in the following proof. Applying Markov inequality on Lemma have
we
P(|An (3n 0¹) x)
(41)
P(1O,, Brl > c)
(42)
100, Ball
(43)
eP
2F 1 pL - 20/2
2 2p - -3)p/2M3 MP
11+46p 1)
(44)
e²
c(aaa)) po/2
Then we consider the tail probability of EofuT (Bn, )² Define (A(E) Fx( Fx((F-11)
as the projection operator. Let Z = Vg(0", XX) be the i.dd copy of Z,. Similar to the proof of Theorem 3.1 we can show that for 1 < k S n,
iP&(o" (Pa(uT(3, +*)) S (1 au7)" "-a))~>>> >E(e 2xlFFa).
(45)
Let y pep (p+ 2). Define the following sequence
7 7 VVG(n-1) - x min (1, 2-(1 ) 11,1 ). 100 = 0
y1
(46)
Then we have
P( T (Bn - -0'}} 2)
(47)
TP (lZy) >
2y(1 am0))-i))
+ P([ (mn -0")}| > c),
(48)
1=1
2 MB
n
70"
(1 p(n-t) + P((Bofo Tm - 80)}] > c)
(49)
y
i=1
Cyp-1
+ P(EEo(V (m - -8'} > c).
(50)
eP
23

---

for some constant C' 'ndeeeedenn of and 7. The next step is to investigate the tail behavior of Eofv' (Th (m 8r) 8² We consider its moment generating function: for x >
Mn(x) == exp (n 0²)
E exp Σ Pa(u (m -0'}
Due to definition (46) and a similar argument to 45 result, we can leverage Lemma 1.4 in [Nagaev
we have sup.ess [Ps(u (Mm - 8*) 1 y. As
1979
to obtain
(Mm E { cxp (I (1) -0))) FR-13
$ + exp(p)a² {1Px (v (m +))) [|
2
exp(xy) xy (IPA(1 T (n
x 11 x p
yp
207) M3 exp(xy) - 1 zy (1 a07))(nn
7) PM
p
11 exp(p)x²
x>
yp
2
y
Since the final upper bound does not depend on FR-1, we have
Mn(x)
n-1
II
ev
1
zy
22 (0 MB 11x p/u)
yp
t=0
C,xa M37 (x-(1-1)) 3 1 - zy
Mg x 11x > p/ul p/u3)
S exp
y
for some constant Cp independent of and 7. We use the Chernoff-type bound:
P( (m - 00)}|
and find an such that
2y + C2>(D-1) " - xy q
Cr.²²
M2T Cnr2M3
MD
I( p/v}
xy
y
is small. The calculation is identical to the proof of Theorem 1.3 in Nagaev 1979
which leads to
2
Cpe2 yM3
C17p-1
C262
(( (m - )²) 2) C,c + 2exp(
+ 2exp(
(51)
for some constant C1 and C2 independent of e, and 7-
Finally, we use union bound on 44 (50). and (5T) to finish the proof of the tail probability inequality in Theorem 4.2 Notice that from Lemma 4.1 we have
3(p 1)
[{Bn - 0*) s 11,, - 1- S May
V-
Ou
As long as Mp 33(-1)
0g V < C, this expectation term can be ignored in the tail probability bound. If
not, i..,, 22/7 S 3M² (p-1)/op, we can choose C2 S log 20gg /3M//3 1) such that the probability
bound trivially holds in this case. As a result, the expectation term does not affect the validity of our result, and the proof is completed.
A.6 Additional Experiment Details
We conducted the experiments in R version 4.3.1 (2023-06-16 16) MacBook Air with a GPU Apple M1, 4 performance and 4 efficiency cores, and 8 GB LPDDR4 memory, equipped with macOS Big Sur version 11.5.1.
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly stressed our contributions and scope in the abstract and introduction to list our key innovations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We talked about the limitations and constraints in the remarks on the results.
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 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 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
We provide rigorous proof's for all the theoretical results in the supplementary
material.
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 cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's 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 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 properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We disclose all the information in the paper and supplementary material.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, 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 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 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 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 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 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?

---

Answer: [Yes]
Justification:
We provide them our supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
pessionnooccyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuiu wwwiiicgguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all details in the final section of the paper.
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 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.
7. 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: [Yes]
Justification: They are reported in the supplementary material.
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, confi- dence intervals, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation 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 96% CI, if the hypothesis of Normality of enrors 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 range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide sufficient information on the computer resources in the supple- mentary material.
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, 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 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
We followed the NeurIPS Code of Ethics instructed.
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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper discusses potential positive societal impacts, particularly through advancing the theoretical understanding of modern statistical learning, which can inform the development of uncertainty quantification and trustworthy AI. As the work mostly focuses on theoretical aspects and does not propose or evaluate any deployable systems, we do not anticipate any direct negative societal impacts.
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 particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper has no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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?
Answer: [NA]
Justification:
We do not such assets.
Guidelines:
The answer NA means that the paper does 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
5

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.


Reviews:
[{"review_id": "I87TnI3UZQ", "reviewer": "Reviewer_AvJc", "summary": "This paper derives a variety of quantitative statistical properties of SGD iterates when the averaged loss is strongly convex and the step size is constant. In particular, it gives variations on the $p$-th moment bounds, the central limit theorem, Berry-Esseen bounds, and large-deviation inequalities. The Berry-Esseen bounds and large deviation inequalities give quantitative bounds on the deviation of the iterates from Gaussian random variables.", "questions": "- Can the constants on the theorems be quantified? \n- Would it be possible to modify the methods to handle non-strongly convex problems?\n- In the simulation, values of constants associated with the asymptotic distribution are used, and this is also remarked earlier to suggest that part of the Nagaev-type bounds are tight. Could the use of the constants from the asymptotic distributions be justified rigorously?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "# Strengths\n- The results give a more more detailed statistical analysis of SGD than currently available. While basic convergence properties are well-understood, the results in this paper give precise quantitative bounds on the deviation from Gaussian random variables. \n- The writing is well-structured and precise. \n\n# Weaknesses\nThe only minor weakness is that the writing is highly terse, and some parts end up appearing unmotivated or not quite justified. Some examples:\n- In the proof of Theorem 3.4. It isn't obvious why the quantity in (27) is being bounded until much later, when a result from Shao and Zhang is invoked.\n- The use of the Lindeberg-Feller CLT to prove Theorem 3.3 could be explained more thoroughly. It seems that it would follow from Assumption 2.2 and the construction of L, but more  details would be nice. (Namely, justifying the Lindeberg condition.)\n\nA bit of restructuring to help the reader (and this reviewer!) understand the ideas behind of the proofs would be helpful.", "was_revised": true, "final_justification": "The paper was good, and I already had given the highest possible rating. I am keeping my score after the rebuttal.", "rebuttal": "Thank you very much for your thoughtful evaluation and for recognizing the contributions of our work! Please see our point-to-point responses to your concerns below.\n\n$\\textbf{Responses to Weaknesses}$\n\n$\\textbf{1:}$ Thank you for your helpful and constructive suggestion! We totally agree that it is better to first invoke the result from Shao and Zhang, and to discuss some high-level ideas of each step. We will carefully rearrange the proof and the remark in our updated version. \n\nFor instance, we would like to explain some motivations behind the functional dependence measure (Theorem 3.1) and the proofs of the main theorems.\n\nIn the context of SGD, the functional dependence measure quantifies the contribution of the $t$-th training sample $X_t$ to the $n$-th SGD iterate $\\theta_n$. In other words, it measures the degree of dependence of outputs $\\theta_n$ on inputs $X_t$. Theorem 3.1 indicates that this degree of dependence decays exponentially fast for the constant learning rate SGD. \n      \nThe derivation of the Berry-Esseen inequality (Theorem 3.4) for SGD relies on the idea of linear approximation and coupling. Theorem 3.1 plays a vital role in the calculation of the dependence measure of the error terms from linear approximation, which constitute the final bound.\n\nThe proof of Theorem 4.2 is inspired by (Nagaev 1979), who establishes a sharp concentration inequality of independent sums relying on the multiplicativity of moment generating functions (MGF). However, the non-linearity and dependence structure of SGD becomes a roadblock, where the MGF can not be explicitly computed. To address this issue, we leverage an autoregressive coupling idea, i.e., approximate the SGD iterates with a gradient descent iteration with i.i.d. noises (Lemma 4.1). The MGF of the coupling sequence is tractable, based on which we apply a Chernoff-type bound to obtain the result.\n\n$\\textbf{2:}$ The multivariate Lindeberg-Feller CLT states the following:  Suppose \n\n$y_{nk} \\in \\mathbb{R}^d$ \nare independent with means \n\n$\\mathbb{E}(y_{nk})=0$ and variance matrices \n\n$$\nV_{nk} = \\mathbb{E} ( y_{nk}y _{nk}^T ).\n$$\n\nSet \n$$U_n =  \\sum_{i=1}^n V_{nk}, \\nu_n^2 = \\lambda\\_{\\min}(U_n).\n$$\nIf $\\nu_n^2 > 0$ and for all $\\varepsilon > 0$\n$$\n\\lim_{n \\to \\infty} \\frac{1}{\\nu_n^2} \\sum_{k=1}^n \\mathbb{E} \\left( |y_{nk}  |^2 \n\\cdot \\mathbf{1}\\left( |y_{nk}  |^2 \\geq \\varepsilon \\nu_n^2 \\right) \\right) = 0 \n$$\nthen as $n \\to \\infty$\n$$\nU_n^{-1/2}  \\left( \\sum_{k=1}^n y_{nk}  \\right) \\Rightarrow \\mathcal{N}(0, I_d).\n$$\nWe apply the theorem on the standardized sum \n$\\Gamma\\_n(\\gamma)^{-1/2}\\sqrt{\\gamma} \\sum_{k=1}^n (I_d-\\gamma A)^{n-k}\\ Z_k$. \nDenote \n\n$$B\\_{nk}(\\gamma)=\\Gamma_n(\\gamma)^{-1/2}\\sqrt{\\gamma} \\sum_{k=1}^n ({\\bf I}_d-\\gamma A)^{n-k}.$$\n\n\nThen $y_{nk}=B_{nk}(\\gamma) Z_k$, $U_n = I_d$ and $\\nu_n^2=1$. Let $M_n(\\gamma)$ be the maximum norm of the matrix prefactor of $y_{nk}$, i.e., \n\n$$ M_n(\\gamma)= \\max\\_{1\\leq k \\leq n}|B_{nk}(\\gamma) |=\\max\\_{1\\leq k \\leq n} | \\Gamma_n(\\gamma)^{-1} \\gamma ({\\bf I}_d-\\gamma A)^{2n-2k}|. $$\n\nAt the end of page 16, we show that $ | \\Gamma_n(\\gamma)^{-1}|$ is bounded by some constant. As a result, $M_n(\\gamma) \\lesssim \\gamma \\rightarrow0$. This is sufficient for the Lindeberg condition and CLT. To this end, notice that\n$$\n\\sum_{k=1}^n \\mathbb{E} ( |y_{nk}  |^2 \n\\cdot \\mathbf{1}  (|y_{nk}  |^2 \\ge \\varepsilon ))  \\leq  \\sum_{k=1}^n |B_{nk}(\\gamma)|^2 \\mathbb{E} ( |Z_k  |^2 \n\\cdot \\mathbf{1} ( M_n(\\gamma) |Z_k |^2 \\ge \\varepsilon )).\n$$\n\nWe have \n\n$\\mathbb{E} \\left( |Z_k  |^2 \n\\cdot \\mathbf{1}\\left( M_n(\\gamma) |Z_k |^2 \\geq \\varepsilon  \\right) \\right) \\rightarrow 0$ due to $\\mathbf{1}\\left( M_n(\\gamma) |Z_k |^2 \\geq \\varepsilon  \\right) \\rightarrow 0$ \n\nand dominated convergence theorem. By elementary calculation, $\\sum_{k=1}^n |B_{nk}(\\gamma)|^2$ is bounded. As a result, the Lindeberg condition is justified.\n\n$\\textbf{Responses to Questions}$\n\n$\\textbf{Q1:}$ Yes, constants can be quantified. In our Theorem 2.3, Theorem 3.1 and Lemma 4.1, we specified all the constants. Lemma 3.2, Theorem 3.4 and Theorem 4.2 are based on those preliminary results, and the constants can be computed in a similar way. Since this paper mainly focuses on the convergence rate w.r.t. learning rate $\\gamma$ and sample size $n$, and the expression of some constants could be tedious, we did not specify some of them in our theorems. We will provide explicit forms in our updated version of the appendix. \n     For example, in Lemma 3.2, we can take the constant as \n     $$ C_0 = \\max\\{\\sqrt{\\frac{3}{\\alpha_0\\lambda}}M_2\\gamma+\\frac{6L_2M_2^2}{\\alpha_0\\lambda} , \\ \\sqrt{\\frac{2}{\\lambda}}L_2\\rho, \\ 2L_2\\rho_2^2 \\}.$$\n     Here $\\rho_2$, $M_2$ and $L_2$ are constants from Assumption 2.1 and 2.2.\n\n$\\textbf{Q2:}$ Yes, it is possible. For example, [R1] proposes a piecewise Lyapunov function method to analyze SGD for non-strongly-convex problem. With stronger assumption on the tail behavior, our Theorem 2.3 can be extended to the non-strongly-convex setting following their idea. Other results are also extendable and will be an interesting future direction.\n\n$\\textbf{Q3:}$ The constant in our Nagaev inequality can be rigorously justified by lengthy elementary calculations, as discussed in the reply to your second question. Our Nagaev-type bound is tight in the sense that the polynomial term $\\gamma^{p-1}$ is much sharper than the Markov-type bound or other results in the literature. In this paper, we do not focus on optimizing these constants. However, we agree that it is an interesting and challenging future work. \n\n\n$\\textbf{References}$\n\n[1] Zhang, Y., D. Huo, Y. Chen, and Q. Xie (2025). “A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression”. In: ACM SIGMETRICS Performance Evaluation Review\n53.1, pp. 85–87"}, {"review_id": "ZFQHhweJUT", "reviewer": "Reviewer_5tvP", "summary": "This paper develops a detailed finite-sample and asymptotic theory for constant learning-rate SGD. By leveraging linear approximations and functional dependence techniques, it derives a quenched central limit theorem, a Berry-Esseen bound, and Nagaev type tail inequalities.", "questions": "1. What is the implication of the bound in Theorem 3.1? Furthermore, how does Theorem 3.1 contribute to the main results?\n\n2. What is the definition of $\\beta^*$  on page 7?\n\n3. Expanding the current experiments to include more diverse scenarios, additional step sizes, and higher dimensional cases would strengthen the practical validation of the tail bound.\n\n4. The Berry-Esseen bound in Theorem 3.4 is valuable and novel. However, its practical usefulness remains somewhat unclear. The paper does not discuss how the bound scales with dimension, nor does it provide numerical experiments to illustrate how tight or meaningful the bound is in practice. Including explicit dimension dependence, practical guidance on estimating the constants involved, and empirical validation would significantly strengthen the impact and applicability of this result.\n\n5. The theoretical contributions of this work are valuable and novel, but the lack of explanatory context and practical examples significantly reduces readability and impact. With improvements in exposition and additional experiments, the paper could be a strong contribution.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:** This work introduces novel approximation techniques and establishes sharp finite sample guarantees, providing the first Berry–Esseen bound and non-asymptotic tail bounds for constant step size SGD. It advances our understanding of the non-stationary behavior of SGD beyond the classical results.\n\n\n**Weaknesses:** The paper primarily lists various techniques and results, but it leaves much of the intuition and practical usefulness of these tools insufficiently explained. Moreover, the experimental section is quite limited, focusing only on verifying the Nagaev type tail inequality through synthetic logistic regression experiments in low dimensions, and testing just three learning rates. It does not explore higher-dimensional scenarios or examine other theoretical results, such as the Berry-Esseen bound or the central limit theorem.", "was_revised": true, "final_justification": "The paper is solid with strong, novel theoretical contributions. However, the lack of explanatory context and practical examples limits its clarity and impact, and the experimental validation remains narrow in scope. Based on these considerations, I will maintain my current score.", "rebuttal": "Thank you very much for your thoughtful comments and for raising these insightful questions! We truly appreciate your careful review. Below, we have addressed all your questions and will revise the paper accordingly. We warmly welcome any additional suggestions to further enhance our work. If our rebuttal has satisfactorily addressed your concerns, we would be grateful if you would consider increasing your score. Please see our point-to-point responses to your concerns below.\n\n**1. The paper primarily lists various techniques and results, but it leaves much of the intuition and practical usefulness of these tools insufficiently explained. Moreover, the experimental section is quite limited, focusing only on verifying the Nagaev type tail inequality through synthetic logistic regression experiments in low dimensions, and testing just three learning rates. It does not explore higher-dimensional scenarios or examine other theoretical results, such as the Berry-Esseen bound or the central limit theorem.**\n\n**Answer:** Thank you for your constructive comments! We indeed conduct simulations to validate the central limit theorem and Gaussian approximation results. In particular, we conduct multiple independent trials of SGD on the linear, logistic, and expectile regression models and varying dimensions. In each scenario, the vanilla SGD distributes close to Gaussian, which empirically validates the CLT of constant learning rate SGD. We will include this part in our updated manuscript.\n\n**2. What is the implication of the bound in Theorem 3.1? Furthermore, how does Theorem 3.1 contribute to the main results?**\n\n**Answer:** In the context of SGD, the functional dependence measure quantifies the contribution of the $t$-th training sample $X\\_t$ to the $n$-th SGD iterate $\\theta\\_n$. In other words, it measures the degree of dependence of outputs $\\theta\\_n$ on inputs $X\\_t$. Theorem 3.1 indicates that this degree of dependence decays exponentially fast for the constant learning rate SGD. The derivation of the Berry-Esseen inequality for SGD relies on the idea of linear approximation and coupling. Theorem 3.1 plays a vital role in the calculation of the dependence measure of the error terms from linear approximation, which constitute the final bound. \n\n**3. What is the definition of $\\beta^*$ on page 7?**\n\n**Answer:** Thank you for pointing this out. This is a typo. Here $\\beta^{*}$ should be $\\theta^{*}$.\n\n**4. Expanding the current experiments to include more diverse scenarios, additional step sizes, and higher dimensional cases would strengthen the practical validation of the tail bound.** \n\n**Answer:** Thank you for the suggestion, and we will expand the experiments section in our updated version, as we replied before.\n\n**5. The Berry-Esseen bound in Theorem 3.4 is valuable and novel. However, its practical usefulness remains somewhat unclear. The paper does not discuss how the bound scales with dimension, nor does it provide numerical experiments to illustrate how tight or meaningful the bound is in practice. Including explicit dimension dependence, practical guidance on estimating the constants involved, and empirical validation would significantly strengthen the impact and applicability of this result.**\n\n**Answer:** We fully acknowledge that an explicit dimension dependence result will enhance the current result. This paper mainly focuses on the convergence rate w.r.t. learning rate $\\gamma$ and the sample size $n$. Based on other results and techniques related to the Gaussian approximation of SGD (e.g., Sheshukov et al. 2025, Theorem 2), we expect our Berry-Esseen bound to scale as $\\sqrt{d}$.  It is an interesting future work to optimize the dimension dependence result for SGD, as the best order of dimension for independent sum in $d^{1/4}$ (Raic 2019). \n\nTo illustrate the sharpness of our Berry-Esseen bound in Theorem 3.4, let $X\\_{1}, X\\_{2}, \\ldots$ be i.i.d. centered random variables with $\\mathbb{E} (X\\_{1}^{2}) = 1$ and $\\mathbb{E} |X\\_{1}|^{3} < \\infty$. We consider estimating $\\theta^{\\*} = \\mathbb{E} (X\\_{1})$ using the SGD algorithm with $\\theta\\_{0} = \\theta^{\\*}$ and $\\theta\\_{i} = \\theta\\_{i - 1} - \\gamma (\\theta\\_{i - 1} - X\\_{i})$ for $i \\geq 1$. Then $\\theta\\_{n}$ admits the linear expansion $\\Delta\\_{n} = \\gamma \\sum_{i = 1}^{n} (1 - \\gamma)^{n - i} (X\\_{i} - \\theta^{\\*})$ which is a weighted sum of independent centered random variables. Consequently, for any $z \\in \\mathbb{R}$, the classical Edgeworth expansion yields \n    \\begin{equation}\n        \\mathbb{P} (\\frac{\\Delta\\_{n}}{\\sqrt{\\gamma/2}} \\leq z) = \\Phi(z) + \\frac{\\sqrt{2}\\mathbb{E} (X\\_{1}^{3}) (z^{2} - 1) \\phi(z)}{9} \\sqrt{\\gamma} + o(\\sqrt{\\gamma}),   \n    \\end{equation}\nwhere $\\phi(\\cdot)$ and $\\Phi(\\cdot)$ denote the probability density function and cumulative distribution function of the standard normal distribution, respectively. This expansion demonstrates that the leading $\\sqrt{\\gamma}$ term in our Berry-Esseen bound is tight and unimprovable in general. We will conduct experiments to provide more empirical evidence on this.\n\nPractical concerns of the Berry-Esseen inequality are discussed in the Remark after Theorem 3.4. The Gaussian approximation rate suggests a choice of learning rate $\\gamma = \\mathcal{O}(\\log n /n)$. It also enables nonasymptotic statistical inference, i.e., the validity of inference procedure with finite sample size and fixed learning rate. We agree that some guidance on estimating related parameters is a pertinent complement. \n\n**6. The theoretical contributions of this work are valuable and novel, but the lack of explanatory context and practical examples significantly reduces readability and impact. With improvements in exposition and additional experiments, the paper could be a strong contribution.**\n\n**Answer:** Thank you for your approval and valuable comments. We recognize it as being a bit dense, since it is more of a theoretical nature. However, we strive to make it more readable, and have included more explanations and remarks after your comment. We would also like to explain some high-level ideas behind the proof of the Nagaev inequality, Theorem 4.2. Nagaev (1979) establishes a sharp concentration inequality of independent sums relying on the multiplicativity of moment generating functions (MGF). However, the non-linearity and dependence structure of SGD becomes a roadblock, where the MGF can not be explicitly computed. To address this issue, we leverage a nonlinear autoregressive coupling idea, i.e., approximate the SGD iterates with a gradient descent iteration with i.i.d. noises (Lemma 4.1). The MGF of the coupling sequence is tractable, based on which we apply a Chernoff-type bound to obtain the result."}, {"review_id": "Bdo7YrrxyP", "reviewer": "Reviewer_ar9s", "summary": "This work studies the distribution of SGD iterates under a constant learning rate. They prove that under certain assumptions such as strong convexity and Lipschitz, fluctuations around its mean converge to a multivariate normal distribution. Then they find the error of convergence through Barry-Essen bound in Gaussian approximation, characterize the large tail deviation using Nagaev type inequalities and find condition for convergence of higher order moments. Deviating from past works, that require a stationary distribution, this works provides the results for a finite step-size reflecting practical behaviour.", "questions": "Please see points 2 and 3.", "limitations": "As I said, the assumptions on the loss function are too restrictive. The most basic loss to analyze the convergence is a quadratic, which the authors skipped to for a logistic regression loss. I would suggest l2 regularized logistic regression since it is strongly convex, as a better alternate experiment.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "This is an interesting paper that characterizes the converges of SGD iterates under certain conditions. Based on the research interest on practical deep learning such as finite-step size, I think this is a timely topic. \n\nStrengths:\n\n1) The paper is generally well written and the notations are explained carefully for ease of the reader. \n2) The remarks after every theroem explains the role of each hyperparameter. \n\nWeakness:\n\n1) *Lack of convincing experiments*: It would have made the paper stronger if the distribution was analyzed for more loss functions. It is well known that logistic regression is not strongly convex, although the theoritical assumption has strong convexity in it. I think the basic loss function is a quadratic where both the strong convexity parameter and the lipschitz parameter depend on the eigenvalues of the Hessian, which is easily calculated. If one can characterize the distribution is on a simple quadratic, then that would validate all the theorems. Currently this is missing. \n\n2) *What if stochastic noise is Gaussian*: If the noise in the gradient assumes a normal distribution and loss is quadratic, then the distribution of the SGD iterates I think should also be an exact normal distribution with 0 error in Barry Essen type inequality. Does the current theorem cover this case? For example in 3.4, will these two assumptions make the Barry-Essen bound go to zero?\n\n3) *Question on loss surface assumptions*: Although strong convexity and lipschitz assupmtions are slightly strong, yet necessary for a nice result, I assume what happens for general ovreparameterized deep neural networks where these conditions do not hold (consider a saddle near a minima). What will the distribution of SGD iterates look like? Will they still converge to a Gaussian distribution? This is not necessarily a weakness but I want to hear the author's comments. \n\nRegarding the originality, I am not aware of all the papers on characterizing the distribution convergence of SGD iterates, but I agree that a finite step-size is indeed an interesting result.", "was_revised": true, "final_justification": "I have read the rebuttal. Based on the merits, such as theoretical strength and empirical weakness, I stick to my score.", "rebuttal": "Thank you very much for your thoughtful comments and for raising these insightful questions. Please see our point-to-point responses to your concerns below.\n\n**1. Lack of convincing experiments: It would have made the paper stronger if the distribution was analyzed for more loss functions. It is well known that logistic regression is not strongly convex, although the theoretical assumption has strong convexity in it. I think the basic loss function is a quadratic where both the strong convexity parameter and the Lipschitz parameter depend on the eigenvalues of the Hessian, which is easily calculated. If one can characterize the distribution is on a simple quadratic, then that would validate all the theorems. Currently this is missing.**\n\n**Answer:**  We recognize the experiment section as you commented, since our paper is more of a theoretical nature. We totally agree that some experiments on quadratic loss functions will be a good ingredient, and will expand this part in our updated manuscript.\n\n**2. What if stochastic noise is Gaussian: If the noise in the gradient assumes a normal distribution and loss is quadratic, then the distribution of the SGD iterates I think should also be an exact normal distribution with 0 error in Barry Essen type inequality. Does the current theorem cover this case? For example in 3.4, will these two assumptions make the Barry-Essen bound go to zero?**\n\n**Answer:** You are absolutely right: when the stochastic noise is Gaussian and the objective function is quadratic, the Kolmogorov distance is exactly zero. Our Theorem 3.4 does cover this scenario; however, it provides a universal upper bound rather than the exact (zero) error. This is because Berry-Esseen-type bounds are designed to be general-purpose, worst-case estimates that apply broadly to a wide class of distributions. Therefore, while the bound in Theorem 3.4 remains valid, it may not be tight in this special Gaussian-quadratic case.\n\n**3. Question on loss surface assumptions: Although strong convexity and Lipschitz assumptions are slightly strong, yet necessary for a nice result, I assume what happens for general ovreparameterized deep neural networks where these conditions do not hold (consider a saddle near a minima). What will the distribution of SGD iterates look like? Will they still converge to a Gaussian distribution? This is not necessarily a weakness but I want to hear the author's comments.**\n\n**Answer:** Without convexity, the convergence behavior of SGD remains largely unexplored. Generally, we do not think the asymptotic distribution will be Gaussian. The iterates do not necessarily converge to a unique global optimum—let alone admit a well-defined asymptotic distribution or central limit theorem. However, under assumptions milder than global convexity, it is possible to extend the approach in this paper to obtain similar results. For example, if the objective has multiple local minimizers and is locally strongly convex around each minimum, we expect the asymptotic distribution of SGD to be a mixture of Gaussian distributions with centers at local minima. The case including a saddle is an even more challenging problem and is beyond the scope of this paper. We believe CLT does not hold in this setting, and will leave this as an interesting follow-up problem. \n\n**4. Regarding the originality, I am not aware of all the papers on characterizing the distribution convergence of SGD iterates, but I agree that a finite step-size is indeed an interesting result.**\n\n**Answer:** Thank you for your approval! This is the first work to establish non-asymptotic Gaussian approximation and sharp Nagaev-type inequalities for the constant learning rate SGD.\n\n**5. As I said, the assumptions on the loss function are too restrictive. The most basic loss to analyze the convergence is a quadratic, which the authors skipped to for a logistic regression loss. I would suggest l2 regularized logistic regression since it is strongly convex, as a better alternate experiment.**\n\n**Answer:**  Thank you for your constructive review! We fully acknowledge your suggestion and will expand the experiment section following it."}, {"review_id": "6mwUI9aKYN", "reviewer": "Reviewer_ZNkP", "summary": "The paper provides a Berry-Esseen bound for the last-iterate error of SGD, with an $\\tilde{\\mathcal O}(n^{-1/2})$ (dimension dependence suppressed) normal approximation error over all convex sets in $\\mathbb R^d$.", "questions": "- Can the authors spell out the dependence of $C$ on other problem parameters, in particular the dimension $d$, after Theorem 3.4?\n\n- Related, it is known in the i.i.d.\\ random vector case that by considering all closed balls instead of all convex sets in $\\mathbb R^d$, the Berry-Esseen bound's $O(d^{1/4})$ dependence on $d$ can be removed. Can the authors achieve the same via taking $\\mathcal V$ to be all closed balls?\n\n- Would the authors be able to say a few things about the BE analysis of the Polyak-Ruppert averaged iterate? The PR average has a smaller variance in its limiting Gaussian distribution, right? So its BE approx might be of more practical interest.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper is very crisply written, well structured, and bears a very elegant and important result. While it is long known that the last iterate of SGD is asymptotically normal, this paper's quantitative version of such asymptotically normality opens up numerous downstream inference/uncertain quantification tasks.\n\nI only have good things to say about this paper. A minor weakness might be that some potentially interesting dependences, in particular the one on $d$, are suppressed while directly porting the BE result by Shao & Zhang.", "was_revised": true, "final_justification": "We thank the authors for addressing these minor questions that I asked. I would like to keep my strong endorsement of this work unchanged.", "rebuttal": "We are extremely grateful for your strong endorsement and careful review of our proofs. Please see below our response to your questions.\n\n**1. I only have good things to say about this paper. A minor weakness might be that some potentially interesting dependence, in particular the one on $d$, are suppressed while directly porting the BE result by Shao \\& Zhang. Can the authors spell out the dependence of $C$ on other problem parameters, in particular the dimension $d$, after Theorem 3.4?**\n\n**Answer:** We fully acknowledge that an explicit form of the constant depending on $d$ and other parameters will enhance the current result. Based on other results and techniques related to the Gaussian approximation of SGD (e.g., Sheshukov et al. 2025, Theorem 2), we expect our Berry-Esseen bound to scale as $\\sqrt{d}$. It is an interesting open problem whether BE for SGD can achieve or approximate the order $d^{1/4}$. The expression of $C$ by other problem parameters requires more elementary calculation. We can derive it and give an explicit form in our updated manuscript.\n\n**2. Related, it is known in the i.i.d.\\ random vector case that by considering all closed balls instead of all convex sets in $\\mathbb{R}^d$, the Berry-Esseen bound's $O(d^{1/4})$ dependence on $d$ can be removed. Can the authors achieve the same via taking $\\mathcal{V}$ to be all closed balls?** \n\n**Answer: Thank you for your valuable comments and for raising this interesting question. Yes, the techniques we developed for deriving the Berry-Esseen bound over all convex sets can indeed be extended to the case of closed balls. Specifically, by combining our refined linear approximation result from Section 3.2 with either the classical Berry-Esseen theorem (Bentkus and Gotze (1996)) or modern $L^{2}$-type Gaussian approximation result (Xu, Zhang and Wu (2019)), we can derive Berry-Esseen bounds over all closed balls that do not involve the dimensionality $d$. We are currently actively working on deriving the explicit form of this Berry-Esseen upper bound. **\n\n**3. Would the authors be able to say a few things about the BE analysis of the Polyak-Ruppert averaged iterate? The PR average has a smaller variance in its limiting Gaussian distribution, right? So its BE approx might be of more practical interest.**\n\n**Answer:** Thank you for the insightful question. We agree that, in general, the variance of Polyak-Ruppert averaged SGD is smaller than that of the vanilla SGD iterate. We expect the Berry-Esseen bound will be sharper. The theoretical BE analysis of the Polyak-Ruppert averaged iterate differs from our paper only in some elementary calculations. Current arguments of proof will follow similarly with modest adjustments.\n\n**4. I have a minor concern that the primary area of this paper should be optimization instead.**\n\n**Answer:** Thank you for your observation. We appreciate your perspective and are open to reconsidering the primary area of the paper."}, {"review_id": "jWNCnoZAJF", "reviewer": "Reviewer_oyBA", "summary": "This paper presents a  theoretical analysis of stochastic gradient descent (SGD) with a constant learning rate. Unlike traditional analyses that require decaying step sizes or stationarity assumptions, the authors provide both finite-sample and asymptotic results under milder conditions. The key contributions include:\n\n1. The authors develop a new linear approximation technique that enables a CLT for SGD iterates starting from arbitrary initialization, without requiring convergence to stationarity. The fluctuations of the iterates around the target parameter converge to a multivariate Gaussian distribution as the step size \\\\(\\gamma \\to 0\\\\).\n  \n 2.  The paper derives the  Berry–Esseen-type bound for constant-rate SGD, quantifying the distance between the SGD distribution and its Gaussian limit. The bound shows the approximation error is of order $\\mathcal{O}(\\sqrt{\\gamma})$, which is optimal given the non-vanishing bias of the SGD iterates.\n  \n  3.  The authors provide explicit upper bounds for the $p$-th moments of the error $\\mathbb{E}[|\\theta_n - \\theta^*|^p]$, establishing how higher-order moments decay with the number of iterations.\n  \n  4.  By approximating the SGD dynamics with a nonlinear autoregressive process, the paper derives sharp large-deviation bounds that combine sub-Gaussian and polynomial decay terms, allowing high-probability guarantees even in heavy-tailed noise settings.\n  \n  5.  Numerical experiments on logistic regression with heavy-tailed data validate the theoretical bounds. The proposed Nagaev-type inequality closely matches the empirical tail probabilities and significantly outperforms Markov-type bounds in tightness.", "questions": "1. How do the assumptions in this paper (e.g., strong convexity, Lipschitz continuity) limit the applicability of the results to non-convex optimization problems commonly encountered in deep learning?\n\n2.  The paper presents a quenched central limit theorem that applies to non-stationary SGD. How does this differ from classical CLTs for SGD that require asymptotic stationarity? What practical advantage does this offer? \n\n3.  Why is the Berry--Esseen bound particularly important for understanding the behavior of SGD in finite-sample regimes? How does this bound compare to previous results for decaying learning rates?  The matrix $\\Gamma$ is typically unknown and should be estimated.  How are the authors going to estimate it. \n\n4.  The simulations focus on logistic regression with heavy-tailed inputs. Would the theoretical bounds hold or degrade for more complex, non-linear models (e.g., neural networks)?\n\n 5.  The authors claim their bounds are sharp. What empirical or theoretical evidence supports this, and under what conditions might the bounds be loose or overly conservative?\n\n 6.  The paper discusses optimal scaling of $\\gamma$ in terms of $n$ for convergence. How should practitioners choose $\\gamma$ in practice based on this theory, especially when $n$ is unknown?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1.  The paper establishes the first Berry--Esseen bound and Nagaev-type inequality for constant learning-rate SGD.\n 2. The central limit theorem applies to non-stationary SGD sequences with arbitrary initialization, which is more aligned with practical scenarios.\n 3. The work provides moment bounds and concentration inequalities that are valid for finite samples.\n 4. The use of linear and autoregressive approximations, functional dependence measures, and Lyapunov equations is mathematically rigorous and innovative.\n 5.  Numerical studies effectively support the theoretical claims, demonstrating the sharpness of the proposed tail bounds.\n\n  \n\nWeaknesses\n\n1. The simulations are confined to a single logistic regression setting, limiting insight into performance across diverse models or datasets.\n  \n 2.  Although milder than prior work, the assumptions (e.g., strong convexity, Lipschitz continuity) may still be restrictive for many non-convex or real-world scenarios.\n  \n 3. The focus is on theoretical analysis; no new algorithm or implementation technique is proposed, which may limit the paper’s immediate practical impact.\n  \n 4.  There is no discussion on computational efficiency or how the proposed bounds scale with dimensionality in practical settings.\n\n5. It is not clear how the authors estimate the covariance matrix $\\Gamma$ and how this would influence the final bounds.", "was_revised": true, "final_justification": "Thank you for the detailed clarifications. Although I remain unconvinced of the immediate practicality of the obtained results, the theoretical foundations laid here are important. Accordingly, I will maintain my high rating.", "rebuttal": "Thank you very much for your thoughtful comments and for raising these insightful questions. Please see our point-to-point responses to your concerns below.\n\n \n\n$\\textbf{Weakness}$\n\n $\\textbf{W1:}$ We recognize the experiment section as you commented, since our paper is more of a theoretical nature. We will add different model scenarios in our updated manuscript.\n\n\n\n $\\textbf{W2:}$ Without convexity, the convergence behavior of SGD remains largely unexplored. Generally, we do not think the asymptotic distribution will be Gaussian. The iterates do not necessarily converge to a unique global optimum—let alone admit a well-defined asymptotic distribution or central limit theorem. However, under assumptions milder than global convexity, it is possible to extend the approach in this paper to obtain similar results. For example, if the objective has multiple local minimizers and is locally strongly convex around each minimum, we expect the asymptotic distribution of SGD to be a mixture of Gaussian distributions with centers at local minima.\n\n $\\textbf{W3:}$ We agree that due to the theoretical nature of our paper, we did not propose new algorithm. However, we still discuss some implementation technique, for instance, the choice of learning rate $\\gamma = \\mathcal{O}(\\log n /n)$ suggested by the Gaussian approximation result. Our work sheds new light on important practical concerns, such as the validity of finite-sample statistical inference and sample complexity.\n\n   $\\textbf{W4:}$  We would like to clarify that, since we did not propose new algorithm, the only algorithm involved in our paper is the classical SGD, for which the computational efficiency is well-studied and does not belong to the scope of this work. \n\nWe fully acknowledge that how the bounds scale with dimensionality is a pertinent point. This paper mainly focuses on the convergence rate w.r.t. learning rate $\\gamma$ and the sample size $n$. In fact, we have discussed the dependence of the Nagaev inequality after line 255. For the Berry-Esseen bound, based on other results and techniques related to the Gaussian approximation of SGD (e.g., Sheshukova et al. (2025), Theorem 2), we expect our Berry-Esseen bound to scale as $\\sqrt{d}$. It is an interesting future work to optimize the dimension dependence result for SGD, as the best order of dimension for the independent sum is $d^{1/4}$ (Raivc 2019).\n\n $\\textbf{W5:}$ Thank you for raising this thoughtful question. The covariance and precision matrix estimation for stationary processes or SGD sequences has been extensively researched. For instance, if the Hessian information $\\nabla^2 g(\\theta_{n-1},X_n)$, we can use Plug-in estimator in [R1] to separately estimate $A$ and $S$ by $\\hat{A}$ and $\\hat{S}$, and numerically solve $\\Gamma\\hat{A}+ \\hat{A}\\Gamma=\\hat{S}$. Please refer to Section 4.1 in [R1] for detailed implementation. Another choice is to estimate $\\Gamma$ using only SGD iterates. Since constant learning rate SGD converges to its stationary distribution exponentially fast (Dieuleveut et al. 2020), we can leverage those developed estimation approaches for stationary processes, e.g., the thresholded estimator and graphical Lasso estimator in [R2]. These approaches can directly estimate $\\Gamma$ and its inverse.\n    \nWhen comparing the distribution of \n$\\Delta_{n}/\\sqrt{\\gamma}$ \nwith that of the multivariate Gaussian random vector \n$N(0, \\hat{\\Gamma})$, a key step is to establish a Gaussian comparison result that provides a sharp non-asymptotic upper bound for the Kolmogorov distance\n $\\sup_{\\mathcal{D} \\in \\mathcal{V}} |\\mathbb{P}(N(0, \\Gamma) \\in \\mathcal{D}) - \\mathbb{P} (N(0, \\hat{\\Gamma}) \\in \\mathcal{D})|$. \n\nSuch Gaussian comparison bounds have been recently derived in specific settings: for example, when $\\mathcal{V}$ is the class of rectangles in $\\mathbb{R}^{d}$ (Chernozhukov et al. (2015)), and when $\\mathcal{V}$ is the class of closed balls in $\\mathbb{R}^{d}$ (Gotze et al. (2019)). We believe that obtaining sharp upper bounds for $\\sup_{\\mathcal{D} \\in \\mathcal{V}} |\\mathbb{P}(N(0, \\Gamma) \\in \\mathcal{D}) - \\mathbb{P} (N(0, \\hat{\\Gamma}) \\in \\mathcal{D})|$ is both an interesting and important problem in probability theory, and also serves as a valuable tool for uncertainty quantification in stochastic algorithms. However, this question lies beyond the scope of the present work, and we would leave it for future work. \n\n$\\textbf{References}$\n\n[1] Chen, X., J. D. Lee, X. T. Tong, and Y. Zhang (2020). “Statistical inference for model parameters in\nstochastic gradient descent”. In: The Annals of Statistics 48.1, pp. 251–273\n\n[2] Chen, X., M. Xu, and W. B. Wu (2013). “Covariance and precision matrix estimation for high-dimensional\ntime series”. In: The Annals of Statistics 41.6, pp. 2994–3021. doi: 10.1214/13-AOS1182.\n\n\n\n\n\n$\\textbf{Questions}$\n\n$\\textbf{Q1:}$  Without convexity, the convergence behavior of SGD remains largely unexplored. Generally, we do not think the asymptotic distribution will be Gaussian. The iterates do not necessarily converge to a unique global optimum—let alone admit a well-defined asymptotic distribution or central limit theorem. However, under assumptions milder than global convexity, it is possible to extend the approach in this paper to obtain similar results. For example, if the objective has multiple local minimizers and is locally strongly convex around each minimum, we expect the asymptotic distribution of SGD to be a mixture of Gaussian distributions with centers at local minima.\n\n\n$\\textbf{Q2:}$ Thank you for the insightful questions. In one word, the classical CLT requires the starting point $\\theta_0$ to follow the stationary distribution, while the quenched central limit theorem is applicable to arbitrary initialization. In analyzing stochastic approximation algorithms, we find that the quenched central limit theorem (CLT), which characterizes the conditional distribution given any initialization $\\theta_{0}$, is more suitable than classical (annealed) CLTs that rely on the asymptotic stationarity. In particular, by conditioning on the initialization, the classical CLT becomes a direct corollary of the quenched CLT, which establishes the asymptotic normality of SGD iterates for arbitrary initializations. Practically, this allows greater flexibility in choosing initial estimates, as the quenched CLT guarantees asymptotic normality without imposing any restriction on initialization. \n\n\n  \n$\\textbf{Q3:}$ Thank you for the insightful questions. The key advantage of the Berry-Esseen bound lies in its non-asymptotic nature: it provides a quantitative bound on the Kolmogorov distance between the distribution of SGD iterates and the normal distribution. This is particularly valuable in finite-sample regimes, similar to sample complexity analysis, on how many training samples are needed to achieve a desired level of distributional approximation accuracy. \n\nAs we discussed from lines 220 to 223, the bound for the constant learning rate is sharper than the result for the decaying learning rate. By choosing $\\gamma = \\mathcal{O}(\\log n/n)$, the order of Gaussian approximation becomes $\\mathcal{O}(\\sqrt{\\log n/n})$, while the optimal approximation rate for decaying step size is $n^{-1/4}$. For the covariance estimation, please kindly refer to our reply above (to the weakness 5).\n\n\n\n $\\textbf{Q4:}$The theoretical bounds hold for any models satisfying Assumptions 2.1 and 2.2, including more complex, non-linear models. In general, neural networks do not satisfy the convexity, so our result is not applicable. However, as we mentioned before, it is possible to extend the approach in this paper to obtain similar results for non-convex loss functions.\n\n$\\textbf{Q5:}$ Thank you for your thoughtful comments and for raising this insightful question. To illustrate the sharpness of our Berry-Esseen bound in Theorem 3.4, let $X_{1}, X_{2}, \\ldots$ be i.i.d.~centered random variables with $\\mathbb{E} (X_{1}^{2}) = 1$ and $\\mathbb{E} |X_{1}|^{3} < \\infty$. We consider estimating \n\n$\\theta^{*} = \\mathbb{E} (X\\_{1})$ \n\nusing the SGD algorithm with \n$\\theta_{0} = \\theta^{*}$ \nand \n$\\theta_{i} = \\theta_{i - 1} - \\gamma (\\theta_{i - 1} - X_{i})$ \nfor $i \\geq 1$. \n\nThen $\\theta_{n}$ admits the linear expansion $\\Delta_{n} = \\gamma \\sum_{i = 1}^{n} (1 - \\gamma)^{n - i} (X_{i} - \\theta^{*})$ which is a weighted sum of independent centered random variables. Consequently, for any $z \\in \\mathbb{R}$, the classical Edgeworth expansion yields \n    \\begin{equation}\n        \\mathbb{P} (\\frac{\\Delta_{n}}{\\sqrt{\\gamma/2}} \\leq z) = \\Phi(z) + \\frac{\\sqrt{2}\\mathbb{E} (X_{1}^{3}) (z^{2} - 1) \\phi(z)}{9} \\sqrt{\\gamma} + o(\\sqrt{\\gamma}),   \n    \\end{equation}\n    where $\\phi(\\cdot)$ and $\\Phi(\\cdot)$ denote the probability density function and cumulative distribution function of the standard normal distribution, respectively. This expansion demonstrates that the leading $\\sqrt{\\gamma}$ term in our Berry-Esseen bound is sharp and unimprovable in general. \n\n\n$\\textbf{Q5:}$Thanks a lot for this great question. We strongly agree that $n$ is usually unknown. In practice, a small choice of $\\gamma$ ranging from $10^{-2}$ to $10^{-5}$ is very popular (see for example, Krizhevsky et al. (2012); Iiduka (2022) and the tutorial of PyTorch SGD ``torch.optim''), but the theoretical asymptotic behavior of constant learning-rate SGD as $\\gamma$ close to zero is rarely studied in the literature. Our work fills in this gap by providing rigorous (non)-asymptotic theory for the SGD iterates. For such small $\\gamma$, we expect the normal approximation works."}]

Author rebuttal:

Meta-review: This work develops a comprehensive theory for constant learning-rate SGD, establishing a quenched CLT with mild conditions, sharp Berry–Esseen bounds, and non-asymptotic large-deviation guarantees, thereby enabling rigorous uncertainty quantification.
Strength: The paper establishes an array of results for constant step-size SGD which are of interest to the broader machine learning community.

Weakness: The assumption of strong convexity is limiting. An important references [1], which establishes CLT for constant step-size SGD in the nonconvex setup, is completely missed in this work. 

[1] - Yu, Lu, et al. "An analysis of constant step size SGD in the non-convex regime: Asymptotic normality and bias." Advances in Neural Information Processing Systems 34 (2021): 4234-4248.

The paper is unanimously recommended for acceptance by all reviewers, a decision which the AC also agrees with.
Decision: Accept (poster)