Statistical Guarantees for High-Dimensional Stochastic Gradient Descent
Authors: Jiaqi Li
Zhipeng Lou
Johannes Schmidt-Hieber
Wei Biao Wu
Venue: NeurIPS 2025 poster ()
Keywords: stochastic gradient descent
high dimension
constant learning rate
geometric-moment contraction
tail probability
Primary area: theory

Abstract: Stochastic Gradient Descent (SGD) and its Ruppert–Polyak averaged variant (ASGD) lie at the heart of modern large-scale learning, yet their theoretical properties in high-dimensional settings are rarely understood. In this paper, we provide rigorous statistical guarantees for constant learning-rate SGD and ASGD in high-dimensional regimes. Our key innovation is to transfer powerful tools from high-dimensional time series to online learning. Specifically, by viewing SGD as a nonlinear autoregressive process and adapting existing coupling techniques, we prove the geometric-moment contraction of high-dimensional SGD for constant learning rates, thereby establishing asymptotic stationarity of the iterates. Building on this, we derive the $q$-th moment convergence of SGD and ASGD for any $q\ge2$ in general $\ell^s$-norms, and, in particular, the $\ell^{\infty}$-norm that is frequently adopted in high-dimensional sparse or structured models. Furthermore, we provide sharp high-probability concentration analysis which entails the probabilistic bound of high-dimensional ASGD. Beyond closing a critical gap in SGD theory, our proposed framework offers a novel toolkit for analyzing a broad class of high-dimensional learning algorithms.

Statistical Guarantees for High-Dimensional Stochastic Gradient Descent
Jiaqi Li Department of Statistics University of Chicago Chicago, IL 60637 jqli@uchicago.ede
Zhipeng Lou Department of Mathematics University of California. San Diego La Jolla, CA 92093 zlou@ucsd.
Johannes Schmidt-Hieber Department of Applied Mathematics
Wei Biao Wu Department of Statistics University of Chicago Chicago, IL 60637 sbmu@uchicago. edu
University of Twente Enschede, Netherlands
a j. www.scttttt....c www.eeettweettteeee...m ml
Abstract
Stochastic Gradient Descent (SGD) and its Ruppert- Poppart-Polyak averaged variant (ASGD) lie at the heart modern large-scale learning, yet their theoretical prop- erties in sish-dimensional settings rarely understood. In this paper, we pro- vide rigorous statistical guarantees for constant learning-rate SGD and ASGD high-dimensional regimes. Our key innovation is to transfer powerful tools from high-dimensional time series to online learning. Specifically, by viewing SGD nonlinear autoregressive process and adapting existing coupling techniques, we prove the geometric-moment contraction of high-dimensional SGD for con- stant learning rates, thereby establishing asymptotic stationarity of the iterates. Building on this, we derive the q-th moment convergence of SGD and ASGD for any 2 in general -*-norms, and, in particular, the morm that fre- quently adopted in high- -igh-dimessional sparse or structured models. Furthermore, we provide sharp high-probability concentration analysis which entails the proba- bilistic bound of high-dimensional ASGD. Beyond closing a critical gap in SGD theory, our proposed framework offers novel toolkit for analyzing a broad class of high-dimensional learning algorithms.
Introduction
Stochastic gradient descent (SGD) has been a cornerstone in large-scale machine learning since the seminal work by Robbins and Monro [195]]. It is especially efficient in high-dimensional and overparameterized settings where the number of unknown parameters can exceed the number of training samples [Arpit et al. 2017 Zhang et al., 2017 He et al. 2016). SGD also be combined with regularization techniques such as dropout to prevent overfitting in large networks [Krizhessky al. 2012 Srivastava al. 2014). Despite the vast amount of theoretical work
SGD, generalization bounds of SGD in high-dimensional regimes remain limited [Garrigos and
Gower 2023 Considering strongly convex objective function, we provide statistical guarantees for constant learning-rate SGD and its Ruppert-Polyak averaged variant (ASGD) [Ruppert 1988
Polyak and Juditsky [992] in nigh-dimensional settings.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Specifically, we consider a general optimization problem
B arg min G(3), where ( + G(3) (B- E), BERd
(I)
g(-) is the noise-perturbed measurement of G(.,, and & denotes a random element sampled from some unknown distribution II. Given i.i.d. random samples E E,.... and some initialization (30 E R the k-th SGD iteration is
Bx B a ( k == 1.2....,
(2)
for some constant learning rate a O, and Vg(3. respect to B. For k 2 1, the ASGD variant is defined by
Vgg((3.E) the stochastic gradient with
B 3.
We are interested in the high-dimensional setting where the parameter dimension d can be very large. Here, a notable divide between empirical success and theoretical understanding is that practitioners often employ a large constant learning rate or in (2) to accelerate convergence in high-dimensional
problems [Wu et al. 2018 Cohen al. 2021 Cai al. 2024). However, such choices can induce pronounced -ottinatty in the SGD iterates { HEEN which will not converge to a point but oscillates around the mean of stationary distribution. In other words, Brg is non-stationary but asymptotically stationary, which converges only in distribution as k + oc. while the mean of this distribution differs from the exact minimizer 3 due to the non-diminishing bias of order (aa) Dieuleveut et al.) 2020, Merad and Gaiffas, 2023]. Classical theory mostly relies on decaying learning rates [Zhang 2004] Nemirovski et al. 2009 Jentzen and von Wurstemberger 2020 Shi et al. [023]. To address the non-stationarity issue, we apply powerful tools from nonlinear time series analysis [wu and Shao 2004) to online learning, particularly by adapting the coupling techniques to show the geometric-momen contraction of SGD for constant learning rates. Specifically, for any two SGD sequences keN and [,8g)ke that share the same random samples but have different initial vectors Bu and Sh we show in Theorem [ that for all sufficiently small constant learning rates a, the initialization is forgotten exponentially fast in the sense that
(E 1/11) S <rh rra.s.g18 100 Bols holds for all & N,
for contraction speed 0 S Ta,s. < 1, and |. 1 the -ormm,, that is,
1/8 8 12
(V va) T. = Ma
This asserts the existence of limiting stationary distribution of 33 as k + co, thereby facilitating systematic convergence theory of SGD even in nonlinear, overparameterized models.
Building on this new framework, we provide non-asymptotic bounds for higher-order moments of the SGD error in general 8 -ormms for any finite s 2 beyond the usual (-norm, extendable to max-norm for by choosing s R log(d). Notably, the goe-norm is frequently adopted in high- dimensional sparse or structured estimation [Wainwright, 2019]. See for instance, the max-norm convergence of the Lasso and Dantzig selector [Lounici] 2008]; the pivotal method for sup-norm bounds of the square-root Lasso [Belloni et al. 2011]; and the max-norm error control for confidence intervals in high- nigh-dimensional regression problems Javanmard and Montanari 2013]. In stochastic- approximation (SA). Wainwright [0199] derived [ po-norm bounds for Q-learning with decaying learning rates; Chen et al. 2023 derived maximal concentration bounds for SA under arbitrary norms with decaying learning rates and with contraction as an assumption; Agarwal et al. [012) considered high-dimensional SA for strongly convex objectives with sparse optimum, but using decaying learning rates and restricting the tails of stochastic gradients to be sub-Gaussian. To date, all the existing results are restricted to low-dimensional settings or decaying learning rates and do not carry over to overparameterized models with constant learning rates. To address this gap, we derive sharp high-dimensional moment inequality (see Lemma 2 valid for a broad class of learning problems, delivering explicit non-asymptotic bounds of E 3 and its ASGD variant for any q. s 2 2 with mild conditions, together with matching complexity guarantees, i.c., given some target error E > 0 (see Proposition 2). the required number of iterations l such that
E E|G
3 E.

---

Although moment bounds capture average- performance. a single execution of (A)SGD in
practice demands high probabibbbbbyyyy guarantees [Valiant 1984 Vapnik] 2000 Bach and Moulines
2013 Durmus et al., 2021 Zhong et al.) 2024]. Recent advances include generic high-probabilityy
framework for both convex and nonconvex SGD with sub-Gaussian gradient noises [Liu et al.
2023], high-probability rates for clipped-SGD with heavy-tailed noises (Nguyen et al. [023]] and
high-probability guarantees for nonconvex stochastic approximation via robust gradient clipping [Li and Liu 2022). However, these established high-probability bounds focus again on decaying learning
rates and low dimension. Moreover, early work primarily addressed light-tailed noises where the
gradients are bounded or have exponential-tye moments [Nemirovski et al. 20099] Rakhlin et al.
2012. Ghadimi and Lan 2013 Cardot et al. 2017 Harvey et al.) [019 Mou et al. 2020
Chen et al. 2022 were
2023 For the cases that only admit polynomial tail with fimite q-th moment, Lou al.
the first to derive a Nagaev-type inequality [Nagaev] 1979) for low-dimensional ASGD, The rate was shown to be optimal but their bound heavily relies on the linearity of gradients and is only suitable for decaying learning rates. By leveraging a dependency-adiug sunueeenyycdiusteeffniiiioooo dependence measure in high-dimensional time series (Zhang and Wu, 2017], we derive high-probbbility concentration bounds for high- nigh-dimensional ASGD with constant learning rates. Given a tolerance level 8 E (0, 1) and target error e > 0, we provide bounds for the required number of iterations to guarantee that
P( 3. I a) 2 1-
This tail-decay result (see Eq. (0 is proved via a new Tuk-Nagaev-type inequality (see Theorem 4 and complements our moment and complexity characterizations of large-step stochastic optimization.
1.1 Our Contributions
This paper contributes to theoretical ad advanemennts for understanding constant learning-rate SGD and its averaged variant (ASGD) in the challenging high-dimensional regime. Our main technical innovations and results include:
(1) Handling Constant Learning Rates in High Dimensions. In practice, large-scale machine learning models commonly deploy fixed, large learning rates to speed up optimization in high- dimensional settings. To address this, we introduce novel coupling techniques inspired by high- dimensional nonlinear time series and establish the asymptotic stationarity of the SGD iterates with arbitrary initialization (Section 2
(2) Generalized Moment Convergence in and -Norsms By deriving sharp high-dimensional moment inequality, we establish explicit, non-asymptotic g-th moment bounds for arbitrary e" -o-mosms of (A)SGD iterates for any q 2 and even integers generalizing previous theory primarily focusing on mean squared error (MSE) convergence with g = s = 2. Our results extend naturally to the max-norm case (i.e., ) by selecting log( d). that is essential for modern sparse and structured estimation in high-dimensions data (Section
(3) High-Probabiligg Tail Bounds. While average-case (moment) bounds are informative, single runs require tail guarantees. We derive the first high-probability concentration bounds for ASGD in high- dimensional settings with constant learning rates. By developing tight Fuk- aak--Nagavv-type inequality using the coupling techniques in nonlinear time series, we control the algorithmic complexity required to achieve targeted accuracy with high confidence (Section 4).
1.2 Related Works
Stochastic Gradient Descent and its Variants. The SGD algorithm can be traced back Robbins and
Monro 195T], Kiefer and Wolfowitz (1952). Popular SGD variants include Nesterov's 's accelerated
gradient [esterov|] 1983), AdaGrad DDuchi et al. 2011]. AdaDelta [Zeiler] 2012]. Adam [Kingma
and Ba| 2014). AMSGrad [Reddi et al. 2018 Adam [Loshchilov and Hutter 2018 1.18..00 SAG Schhidt
al. 2017 SVRG [Johnson and Zhang 2013. SARAH [Nguyen et al. 2017]. SPIDER [Fang
et al. 2018 and Katyusha [Allen- -hun 2017]. The theoretical foundations of SGD under decaying
learning rates were established in the early studies by [Blum] 1954 Dvoretzky 1956 Sacks, 1958].
with stronger almost-sure guarantees Fabian [1968). Robbins and Siegmund 1971]. Ljung 1977]
objectives with decaying step sizes include Ruppert [1988]. J. Polyak and Juditsky| [1992]. Nemirovski et al. [2009).
Lai [2003), Wang and Gao [2110]. Existing works for smooth, strongly-conee
Bach and Moulines 2013). Rakhlin et al.] [2012]. Mertikopoulos et al. (020) among others. Despite
the rich literature SGD, the theoretical understanding in high-dimensional settings remains limited.
3

---

Exceptions are Paquette et al. loss.
2021 2022 who study high-dimensione SGD for the least-squares
Constant Learning Rate. In high- high-dimensional scenarios, constant learning rates prevail due to simpler tuning procedures and faster convergence [Wang al. 2022]. More recent theoretical and empirical studies of large-step SGD include Wu et al. [2018], Cohen et al. 2021] and the very recent Caa
ct al. (2024), which formalize the resurgence of constant-step methods in modern machine learning. A useful way to analyze constant-step SGD is to treat its iterates as a tmmehhomggeneuus Markov chain [Pilug [986]. which makes it possible to characterize its long-run behavior and stationary law. However, previous works only derived convergence in Wasserstein distance [Dieuleveut et al. [2020] Merad and Gaiffas 2023]. Such convergence in probability measures can hardly provide refined -asmptooyoss such as higher-moment moment convergence and concentration inequalities, and seems nontrivial to extend to high-dimensional regimes.
Digh--Dimessioal Nonlinear Time Series. An alternative approach for constant learning-rate SGI) to view as an iterated random function (Dubins and Freedman, 1966 Barnsley and Demko
1985 Diaconis and Freedman 1999. Diaconis and Duflo 2000]. or nonlinear autoregressive (AR)
process. This interpretation facilitates the theory online learning with non-stationarity and complex dependency structures; see, for example, the recent work by Li et al. [024c] on SGD with dropout regularization building on the GMC framework (Wu and Shao 2004]. To extend this systematic theory to high- -igeeninnnsi settings, we adapt the coupling techniques in time series [Wul [2055] [2007]
2009 2011 Xiao and Wu 2012, Berkes et al.) 2014,] Wu and Wu| 2016 Karmakar and Wu (020).
especially the ones for high-dimensional regimes (Zhang and Wu 2017
2021
Li et al. 2024a to
online learning algorithms.
1.3 Notation
Denote column vectors in Rd by lowercase bold letters æ (I1, ..,,...,. s.)) and the (o-norm of by |æ|.- = (Ein 1r,l")//=, & 2 1. Write x Se (ri....,,2)) x²) The expectation and covariance of random vectors are respectively denoted by [E|-] and Cov()). For q > 0 and random variable X, 00. We denote matrices by uppercase letters. Given
we write X L iff ||X|1, [E([XX9)]1/ matrices and B of compatible dimension, their matrix product is denoted by juxtaposition. Write A for the transpose of A and La for d x d identity matrix. For two positive number sequences (a,)) and (6,)), we say a, = O(b,) (resp. an x b,,) if there exists c > such that an/b, S. c (resp. 1/c S an/b, I c) for all large Let (xx,) and (yn) be two sequences of random variables. Write In = OF(Y,)) ) if for Ve > 0, there exists e > O such that P( ynl s c) > - c for all large n.
Notation
Definition
Reference
Index Range
8
minimizer of the loss function G(B)
Eq.
3x
SGD iterates
Eq.
k N
3%
stationary SGD iterates
Thm.
2
k e
3x
ASGD iterates
Eq.
k E N
3
stationary ASGD iterates
Eq. k E
Table I: List of the sequences defined the paper.
2 Convergence of SGD to a Stationary Distribution
In this section, establish the GMC property of high-dimensional SGD with constant learning rates. Our technique is to construct a smooth surrogate for the non-differentiable exx -nom via the go-norm, so that standard gradient-base tools become available. We defer the technical details Section 6. Furthermore, we provide a novel high-dimensional moment inequality (see Section 6.2) and use it to derive the dimension-dependent range of the constant learning rate that guarantees the contraction.
We first impose the following assumptions on the objective function and the stochastic gradients.
Assumption 1 (Coercivity). Assume that for any sequence BI, P2,... with 1,3.ls -> oo the loss function G(-) in ① satisfies lim G(B,)

---

Assumption 2 (Strong Convexity f" norm). Let 2 2 be an even integer and write v =
(ui..... 2g) for a vector (U......ua) Assume there exists μ such that
(18- 1) VG(3)- 2 p1 Bl for all B, R
In Lemma 3 in the supplementary materials, show that under Assumptions [ and unique global minimizer 3 exists for the optimization problem ( When 2, Assumption reduces to the regular strong convexity frequently adopted in the literature (Polyak and Juditsky, 1992 Moulines and Bach 2011 Dieuleveut et al., 2020 Mies and Steland 2023]. For general and the linear regression model, Section 8.2 in the supplementary material interprets the f*-type strong convexity assumption via the (*-morm induced matrix norm. As different norms are involved, there does not seem to be an apparent relationship between the classical strong convexity and the case $ >
Assumption 3 (Stochastic Lipschitz Continuity -nrrm) Let f be the global minimizer. For some and an even integer s 2 2, assume that
Ma. == (ElV +)
1/4 < 00.
Further assume there exists constant Ls.q O such that
1/9 S L. Bl,s, for all B. E Rd. V "o((S,,)11))
Later we will choose s = (d)g to bound the max-norm. The above defined Lipschitz constant Lx.g and the moments Ms.9 will then grow increases. Taking linear regression example, we investigate the dimension dependence L..q and Ma.q in Section 8.2 All bounds in this work will contain the explicit dependence on (Ls.g. M..g).
We now state the first main result this paper, which plays crucial role in establishing moment convergence and tail probability results in the following sections. The statement quantifies the exponential rate at which the initialization Bo will be forgotten and the SGD iterates Br converges to stationary distribution Ta.
Theorem 1 (Convergence of SGD to stationary distribution). Suppose that Assumptions 7 hold for some μ > 0. q 2 2 and even integer 2 2. Given a constant learning rate
2p
0 de. max L3
(5)
for any two d-dimensional SGD sequences {Bx(a))keN and (3) (a))kE sharing the same i.i.d. noise injections {Ex]222 but possibly different initializations Bo, B IR, the geometric-moment contraction (GMC)
|| - B/lello S r gr...1300 - -Blo. for all k = 0,1,...
holds with contraction constant
Ta,s. =1 - 2 8) L) 02 <1.
(6)
Moreover, there exists unique stationary distribution with finite q-th moment, that is. J [(ll)a < oo, such that
BR Tai + oc. Equivalently, for any continuous function f E C(Rd) with fl < oc.
/ f(u) (du), as k + 0o.
B[f(Be)]
The result generalizes Li et al.
2024b to large dimension and extends the &-tyye GMC based on Lemma to general / norms. Moreover, choosing s 5a with
Sa = 2 minff e N: 28 log(d)},
(7)
and using the inequality
x S | < d d < <l/xloc
(8)
shows the equivalence of the (d4_ and -o -orms. Consequently, by choosing 8a; the previous theorem can also be used to derive the GMC property with respect to the -ormm.
5

---

3 Convergence of High-Dimensional SGD and ASGD
In this section, derive convergence rates for the moments of the last iterate BB -1% and the moments of the averaged SGD.
3.1 Convergence of SGD
Proposition 1. If Assumptions 7 hold for some 2 2, an even integer & 2 2, and constant Ma.g.
then.
max 8/aa M 1113 11,,11 S (1 - 2ay + max (g, 8)a² [2 111a-11 - 1=1,,, 1000-11----111
for all k 2 1. The same inequality holds if B3 is replaced by the stationary SGD iterates B% To.
Theorem 2 (Moment convergence of SGD). Let0 < a < 0s.g/ with a.. as defined in (5) Suppose
that Assumptions 3 hold for 2 2 and even integer 2 2. Then for the stationary SGD iterates
3 ~ Ta.
|| 1 0 (Me. (g s}a)
for all 2 1
for the SGD iterate By with arbitrary initialization So.
||Be /81ell, = 0 (M..a max(g, s + ra...qll 11l Bolella) for all k 2
Choosing sa in yields bound with respect to the enrm.
3.2 Convergence of Ruppert-Polyak Averaged SGD
Consider now the Ruppert-Polyak Averaged SGD (ASGD) Bg = - Σ Br as defined in the initialization Bi Ta. define the stationary ASGD sequence
3 For
B
8 k21.
Theorem Consider the ASGD sequence 1/21R21. Suppose that Assumptions 3 hold with some q 2 2 and even integer sa in (7). the conditions of Theorem 8 hold and the learning rate satisfies a E (0, dea.g) with asa.q defined (5. For any k 2 1 and some universal constants C2, C3 0,
|||3 - 30 bol1, 11 Si
SySd
Masi (Laa / ma sal + +1)
stochastic variance
+ C2 k(1 To,549i
|11Bo 38 lla
Oaf M max(g, Badad= 11-0111111 3
bias of constant learning rate
initialization bias
Proposition 2 (Complexity bound). Under the assumptions of Theorem
3 let Ao = 11130 12l
V T.sa.g M V mmxx(g,a) + Mssg: B = M2 sin9
max mexx(q.e 8d) d (1 (1-
Given tolerance e > O,
min
E
Osag f
and A 2 max
9CPcysaV2
3C2
62
we have |||3, - 3 loc 8.
A proof outline is given in Section 6.3 and the full proof is deferred to the supplementary material. The sharpest complexity bound of SA for gorm known date was derived by Wainwright [2019] proving that the number of iterations required to obtain an e-accurate solution of Q-learnin scales as (1 (1-7)-4.- with the discount factor 7. Proposition 2 our complexity bound for SGD is also of the order of 0(1/²²) if the dimension d is fixed, which is consistent with the degenerate Q-learning case in Wainwright 2019). The derived result allows determine the dependence on the dimension
d.

---

Sharp Concentration and Gaussian Approximation
Via the following tail probability inequality for the averaged SGD estimator Br. one can further derive high-probability concentration bound of | - Recall that 2 min(f E N 2 > (og(d)}:
Theorem (Fuk-Nagaev inequality). Under the conditions of Theorem for any > O, we have
11 181011 (log d) 7 (log ( M
C
P(I32 Bo 2)
$6.9
exp
(kaz)²
29K9 1 99/2-1
$..9 log
where the constants in X are independent of ki 8 and
As an immediate consequence of Theorem we obtain a sharp bigo-brobaiility upper bound for
|B 10, that is, for any given tolerance rate å E (0, 1), with at least probability 6, have
B3x - ,x =0 ( [113 Bilbol1 lg
(log (1og k) 1/0+2 Maag
M2 Ba.9
log d log (1/))
kad1/9
k1 /l-1/aa-/2-1/ah)
kal-2/4
(10)
Notably, if the g-th moment of the gradient noise is finite (M, s..g < x)). the second term of the right
hand side, involving k--9, is generally unimprovable Nagaev 1979 Lou et al. 2022).
The distribution convergence for the high-dimensional ASGD relies the following result. Let M2.9 be as defined in Assumption 3
Theorem 5 (Gaussian approximation). Consider stationary SGD iterates B Tr with na as defined in Theorem 7 initialization B3 Was and learning rate a E (0, Oss.g) Suppose that Assumptions 3 hold | for some q > 2. Then, on a potentially different probability space, and for number of iterations T satisfying d < éT, where > 0 is some constant, there exist random vectors TT= 2 (B2)T== and independent Gaussian random vectors {=
with mean zero
and covariance matrix
Cov
(11)
such that
x1]²] 1/2
d 6--4
max KST
[1B - Bl37))
S C. M2. dlog(T))
(12)
with Cagg constant that only depends on c, the learning rate a, and the moment index g.
For diverging moment index q - oc, the Gaussian approximation rate in 12 approaches the rate O (lo((T)(d 176) Thus, to obtain a nontrivial Gaussian approximation bound within T iterations, we need dimension dependence d = o(TL/4-S) with Ç >>> 0.
5 Constant Learning Rate for Large Dimension
Recall that Ling is the Lipschitz constant introduced in Assumption 3 We established asymptotic stationarity and non-asymptotic convergence if < 0e.gg with as.q defined in (5). leading to the upper bound
as.g 7
2μ
7 max 8) L3 2.
d² log(d)
if we choose = Su in (7) and if Leng d. We refer to Section dimension dependence of Lzgq in the linear regression model.
8.2 for the derivation of the
Alternatively, the upper bound for the learning rate a can also be derived by a linear approximation technique (see Lemmal) [T]. defined the nontrivial solution to the following equation
-ugaa+ + a[1g s| + (s 1)] I a² + absgg) 19-2
(13)
7

---

A derivation of this equation is provided in Section 6.1 The existence of a solution of (13) is shown below the proof of Lemma in the supplementary materials. When q 2. the range of a simplifies to
2/
7 2--22-2 (s-
which is also proportional 1 1/ (d) if we choose sa in and if 1,su,2 d. matching the rate of as.q in (5) derived by Lemma 2 though with a slightly more conservative constant for general
8. In the special case with s = 2, both bounds reduce to the classical a < 2 L3 2- If L22 x d for large dimension d, which is shown be true for the linear regression model in Section 8.2 in the supplementary materials, the - and the -2-norm yield similar upper bounds for the learning rate a.
6 Proof Sketches
6.1 Bridge between 6" and n Norms
In nigh-dimensional regimes, convergence rates of constant-leamingg rate SGD 2
with respect the go -norm are of particular interest [Wainwright] 2019 Chen et al., 2023). However, it is extremely challenging to directly study the convergence of 33 T since the f -norm not differentiable thereby ruling out standard gradient-based tools for proving convergence rates or concentration. To address this issue, we instead study les with 84 defined in (7). By the equivalence between tda. and -orms shown in (8) contraction in   -nom follows from (nrm contraction.
To prove the GMC property of SGD introduced in 44, suffices show that for any d- dimensional SGD sequences {Ba and {BatkeN sharing the same i.i.d. observations { but possibly different initializations Bu, Big- IRd the contraction holds for [8,- - Bllle for all k 2 1. To this end, we need determine range of constant learning rates a such that for any q 2 2 and 3, B' E Rd the GMC in Theorem | holds, i.c.,
B ( (g' - a VV (0)) 1r13 -31... for some Ta,s. < 1. (14)
To derive the inequality, we first provide lemma based on linear approximation by considering the scalar function
az12, and linearizing it around a = Then, one only needs to prove that E|x - azlW S r| By the second-order Taylor expansion of x azl3 in a, have the linear approximation
a+ x
where x = B- == Vg(3,) V
x - az | - qa x (x=-1_ ,)),
(15)
with remainder term of order a², see Section 2 in the supplementary materials for details. Since simple triangle inequality argument || az|x|la < |اااا|| + aill @elll fails to control this remainder sufficiently to yield a contraction constant r < 1, we establish more precise bound.
Lemma 1. Recall that S* = (of..... Ui)T for a vector u = (Vi....,ua) vT) For any q 2 2, any
even integer s 2 2, any two vectors x, z E Idd and any a > 0,
qa2 ||g s) + (s - 1-) + alz2)) 1
[ az | ga|x=
z)
2
If s 2, q= 2. the right-hand side is a² This consistent with the Taylor remainder of the right-hand side in Lemma SaaimaDddevve derived by Li et al. [2024c). Using this inequality to prove the contraction in (14) is remarkably different from the approaches relying on the martingale decomposition (MD)
that is frequently adopted in the literature [Dieuleveut et al., 2020 |Metikopoollss et al.) 2020 Mies and Steland, 2023). Our proposed method requires mild moment conditions on the stochastic gradients and yields simpler proofs that can be generalized to broad class of online learning problems. We refer Li et al. (2024b) for detailed discussion. Nevertheless, we remark in advance that Rio-type inequality (I (Lemma?) 2) with slightly sharper constants will be used directly in our main contraction proof, while we retain Lemma Thee for its intuitive appeal. Finally, by choosing & = 8a as in for [14. we can expect the 8?9-norm type GMC to hold for nigh-dimensional SGD iterates.
8

---

6.2 High- Nigh-Dimensional Moment Inequality
To prove Theorem ! we derive a sigh-dimenssonal version of Rio's inequality [Rio 2009 adapted to the q-th moment of -orm... This result provides a slightly sharper constant than Lemma used directly in our moment-come coneent-ontractton analysis.
and is
Lemma Ftigh-dimensional moment inequality). For any q 2 2, any even integer 8 2 2, and any two d-dimensional random vectors x; y. we have
0 + yle 12 - |||||| 1 q + 2111=11111 "F (1
Σ oij u1) + (max(g, - |
Moreover. if E
x] = 0 almost surely, then
|| + v1.11 < ||| mmax(q. s} 1)
(16)
Repeatedly applying Lemma 2 leads to the high-dimensional maximal moment inequality in Lemma in the supplementary materials, which of independent interest.
6.3 Stationarity, Variation and Bias of ASGD
We prove the moment bound || - 30 ll via the decomposition
1 - 3 وا1ا - ||13 - 30 || [[ -
The first term accounts for the deviation due to the non-stationarity of Gx as it initialized from an arbitrarily fixed Bo: this can be bounded using the GMC property of B& shown in Theorem [ The second term captures the stochastic variance of the stationary ASGD sequence. Bounding this term is more delicate because of the intricate dependency structure of B To address this, we deploy another powerful tool in time series - the fimctional dependence measure [Wu] 2005] in Section 8.6 of the supplementary materials, which can effectively quantify the contribution of the random sample & to the k-th SGD iterate 3 for all i < k. As such, by controlling the cumulative dependence measures, we can bound this variance. Lastly, we handle the third term, which represents the oin-iiiinis bias of 3% induced by the constant learning rate (Dieuleveut et al. [2220] Huo et al. 22023] This can be dealt with by extending the approach in Li et al. [2024b] to hign-dimensional settings.
Theorem 6 (Asymptotic stationarity). Consider the ASGD iterates Be and the stationary version G Suppose that Assumptions 7 Jare are satisfied for some q 2 2 and some even integer s Z 2. Then, for the learning rate a E (0, (s.a) with Oss.g defined in (5)
1
1
|||3 BBlelll S
130 -B0l.
K.
1- Ta,8.9
As a direct consequence of Theorem 6. we have 11133 - Bglallo l S 1.30 - B8l. (kke) which indicates the asymptotic stationarity of high-drmensional ASGD sequences. When the bias induced by the initialization is controlled, i.e., 130 B. < 0o, as ka + co, the ASGD iterate Br approaches the stationary solution B in the sense that | Illlll O. By Theorem 6 the convergence for stationary ASGD.
we only need show
Theorem 7 (Stochasticity of stationary ASGD). Consider the stationary SGD sequence { Ja21- Suppose that Assumptions 7 hold with some q Z 2 and some even integer 2 2. Then there exists constant Cy 0 only depending q, such that, for all k 2 1,
|||3: E| - V
848 Mag (a max(q.s) + +1).
In the low-dimensional case, we take = 2 as a special example. Then, Le,q / a max s} = (()) such that the bound is || - E | 01g O(1/Vk). This rate is optimal considering the central
limit theorem of the stationary ASGD.
Next, we consider the bias induced by the constant learning rate. We first introduce some nec- essary notation. Recall G( E[ E)] and VG( =
where
(Bi,... .......... Ba) T. Denote (:G( (G( /03, 1sisd. d.
G²G( [0,0,C(0]] 15u,sa
(G, = (8,0
(17)
We provide the non-asymptotic bound for the bias of stationary ASGD in the following lemma.

---

Theorem 8 (Bias of stationary ASGD). Under Assumptions consider the stationary ASGD G. Assume that g twice differentiable with respect to with positive definite Hessian matrix V²G(B", and uniformly bounded derivatives maxigiçd (3) | < 0o, where
G.())l = max ISIS
(3))
Then, we have
BI -31 =
=0 max(1, (1x sa) (1--
Conclusions and Discussion
This work advances the theoretical understanding of the constant learning- SGD algorithms in high-dimensional settings. By introducing novel coupling techniques in nonlinear time series, we establish asymptotic stationarity of SGD with any initialization. We then derive non-asymptotic q-th moment bounds in general 8 and -ormss, and develop the first Fuk-Nagaev high-probability tail bound for ASGD. While this paper assumes strong convexity and smoothness of the objective, the nonlinear time series perspective offers a principled framework applicable to a broad class of over- parameterized optimization tasks and can be extended non-convex regimes, providing fundamental insights into the stability, convergence, and reliability of large-scale learning algorithms.
Acknowledgments and Disclosure of Funding
We sincerely thank the program chair, senior area chair, area chair, and the four 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 NSF/DMS (510S-2515926) Johannes Schmidt-Hieber has received funding from the Dutch Research Council (NWO) via the Vidi grant Vi. 1iViii.12..21.... 92.021. Wei Biao Wu's research is partially supported by the NSF (Grants NSF/DMS- 2311249, NSF/DMS-2007723), We would like to thank Insung Kong for helpful discussions.
References
A. Agarwal, S. Negahban, and M. J. Wainwright. Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions. In Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
Z. Allen-Zhu Katyusha: the first direct acceleration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1205, Montreal Canada, 2017. ACM.
D. Arpit, S. Jastrzębski, N. Ballas, D. Krueger, E. Bengio, M. S. Kanwal, Maharaj, A. Fischer, A. Courville, Y. Bengio, and S. Lacoste-Julies A closer look at memorization in deep networks. In Proceedings of the 34th International Conference on Machine Learning, pages 333-242. PMLR, 2017.
Bach and E. Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n). In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
M. F. Barnsley and S. Demko. Iterated function systems and the global construction of fractals. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, 399 (1817):243-22 275,, 1985.
A. Belloni, V. Cheroozuukv,, and L. Wang. Square-root lasso: pivotal recovery of sparse signals via conic programming. Biometrika, 98(4):791-806. 2011.
Berkes, Liu, and W. B. Wu. Mamlós-Major-Tusiiee approximation under dependence. The Annals of Probability, 8212) 2014
10

---

J. R. Blum. Approximation methods which converge with probability one. The Annals of Mathemati- cal Statistics, 25(2):38--386, 1954.
Y. Cai, J. Wu, S. Mei, M. Lindsey, and P. Bartlett. Large stepsize gradient descent for non- homogeneous two-layer networks: Margin improvement and fast optimization. In The Thirty-eighth Annual Conference on Neural Information Prucessing Systems, 2024.
H. Cardot, Cénac, and A. Godichon- saatoonnaaggoni... Online estimation of the geometric median in Hilbert spaces: Nonasymptotic confidence balls. The Annals of Statistics, 45(2):591-614, 2017.
I. Chen, G. Keilbar, and W. B. Wu. Recursive quantile estimation: Non-asymptotic confidence bounds. Journal of Machine Learning Research, 24(91):1-25, 2023.
Z. Chen, S. Theja Maguluri, and M. Zubeldia. Concentration of contractive stochastic approximation: Additive and multipiiaative noise. arXiv e-prints, art. arXiv:2303. 15740, 2023.
V. Chernozhukov, D. Chetverikov, and Kato. Comparison and cnti-connentratton bounds for maxima of Gaussian random vectors. Probubility Theory and Related Fields, pages 47-70, 2015.
J. Cohen, S. Kaur, Y. Li, J. Z. Kolter, and A. Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. International Conference on Learning Representations, 2021.
Diaconis and M. Duflo. Random iterative models. Journal the American Statistical Association, volume 95, page 342, 2000.
Diaconis and D. Freedman. Iterated random functions. SIAM Review, 41(1):45-76, 1999.
A. Dieuleveut, A. Durmus, and F. Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics, 48(3): 2020.
I. E. Dubins and D. A. Freedman. Invariant probabilities for certain Markov processes. The Annals of Mathematical Statistics, 37(4):837-844 1966.
Duchi, F. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159 2011.
A. Durmus, E. Moulines, A. Naumov, S. Samsonov, K. Scaman, and H. T. Wai. Tight high probability bounds for linear stochastic approximation with fixed stepsize. In Advances in Neural Information Processing Systems, 2021.
A. Dvoretzky. On stochastic approximation. In Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, volume 3.1, pages 39-56. University of California Press, 1956.
V. Fabian. On asymptotic normality in stochastic approximation. The Annals of Mathemattcal Statistics, 39(4):3377-133) 1968.
C. Fang, C. Z. Lin, and T. Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Advances Neural Information Processing Systems, 31, 2018.
G. Garrigos and R. M. Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv e-prints, art. arXiv:2301.11235, 2023, doi: 10.48500aaXi.2230111233
S. Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341-2365 2013.
N. A. Harvey, C. Liaw, Y. Plan, and S. Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Proceedings of the Thirty-Second Conference on Learning Theory, pages PMLR, 2019.
K. He, X. Zhang. S. Ren, and Sun. Deep residual learning for image recognition. In 20/6 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
R. A. Hom and C. R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge, 1985.

---

D. Huo, Y. Chen, and Q. Xie. Bias and extrapolation in Markovian linear stochastic approximation with constant stepsizes. In Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 81-82, 2023.
A. Javanmard and A. Montanari. Confidence intervals and hypothesis testing for high-dimensional statistical models. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
A. Jentzen and P. von Wurstemberger. Lower error bounds for the stochastic gradient descent optimization algorithm: Sharp convergence rates for slowly and fast decaying learning rates. Journal of Complexity, 57:101438, 2020.
R. Johnson and Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26, 2013.
S. Karmakar and W. B. Wu. Optimal Gaussian approximation for multiple time series. Statistica Sinica, 30(3):1399 1911191799199-11111111 2020.
Kiefer and Wolfowitz. Stochastic estimation of the maximum of a regression function. The
Annals of Mathematical Statistics, 23(3):462-466, 1952.
D. P. Kingma and J. Ba. Adam: method for stochastic optimization. In 3rd International Conference on Learning Reprexentations, 2014.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
T. L. Lai. Stochastic approximation: invited paper. The Annals of Statistics, 31(2):391-408 2003.
J. Li, L. Chen, W. Wang, and W. B. Wu, l² inference for change points in high-dimensional time series via two-way MOSUM. Ann. Statist., 52(2):602-627, 2024a.
J. Li, Z. Lou, S. Richter, and W. B. Wu. The stochastic gradient descent from nonlinear time series persective, 2024b. Manuscript.
Li, J. Schmidt-Hieber, and W. B. Wu. Asymptotics of stochastic gradient descent with dropout regularization in linear models. arXiv preprint, 2024c. arXiv:2409.07334,
S. Li and Y. Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. Proceedings of the 39th International Conference on Machine Learning, pages 12931-12963. PMLR, 2022.
Z. Liu, T. D. Nguyen, T. H. Nguyen, A. Ene, and H. L.. Nguyen. High probability convergence of stochastic gradient methods. In Proceedings of the 40th International Conference Machine Learning, volume 202 of ICML'23, pages 21884-21914, Honolulu, Hawaii, USA, 2023. JMLR.org.
L. Ljung. Analysis of recursive stochastic algorithms. IEEE Transactions on Automatic Control, 22 (4):551-575, 1977.
I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In International Conference Learning Representations, 2018.
Z. Lou, W. Zhu, and W. B. Wu. Beyond Lub-Gaussian noises: stochastic gradient descent. Journal of Machine Learning Research, 23(46), 2022.
Sharp concentration analysis for
K. Lounici. Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators. Electronic Journal of Statistics, 200002) 2008
I. Merad and S. Gaiffas. Convergence and concentration properties of constant step-size SGD through Markov chains. arXiv e-prints, art. arXiv:2306.1 1497, 2023.
Mertikopoulos, N. Hallak, A. Kavis, and Cevher. On the almost sure convergence of stochastic gradient descent in non-convex problems. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1117-1128. Curran Associates, Inc., 2020.
12

---

F. Mies and A. Steland. Sequential Gaussian approximation for nonstationary time series in high dimensions. Bernoulli, 29(4):31 14-33111444 2023.
W. Mou, C. Li, M. Wainwright, L. Bartlett, and M. I. Jordan, On linear stochastic approximation: Fine-grained tolyak-Rupper and non-asymptotic concentration. In Proceedings of Thirty Third Conference on Learning Theory, pages 2997.2997. PMLR, 2020.
E. Moulines and F. Bach. Non-asympiotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
S. V. Nagaev, Large deviations of sums of independent random variables. The Annals of Probability, 7(5):745-789, 1979.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-18 1609, 2009.
Y. E. Nesterov. A method for solving the convex programming problem with convergence rate 0(1/k²). Dokl. Akad. Nauk SSSR, 269(3):543-54)) 547, 1983.
L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. arXiv:1703.00102 2017.
T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
C. Paquette, K. Lee, F. Pedregosa, and E. Paquette. SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality. Proceedings of Thirty Fourth Conference on Learning Theory, pages 3548-3626. PMLR, July 2021.
C. Paquette, E. Paquette, B. Adlam, and Pennington. Implicit regularization implicit condition- ing? exact risk trajectories of SGD in high dimensions. Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, pages 35984-35999, Red Hook, NY, USA, Nov. 2022. Curran Associates Inc.
G. C. Pflug. Stochastic minimization with constant step-size: Asymptotic laws. SIAM Journal on Control and Optimization, 24(4):655-666 1986.
B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838 855, 1992.
A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1571-1578. 2012.
J. Reddi, S. Kale, and Kumar. On the convergence of Adam and beyond. In International Conference Learning Representations, 2018.
E. Rio. Moment inequalities for sums of dependent random variables under projective conditions. Journal of Theoretical Probability,
2009.
H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400 407, 1951.
H. Robbins and D. Siegmund. A convergence theorem for non negative almost supermartingales and some applications. In J. S. Rustagi, editor, Optimizing Methods in Statistics, pages 233-257. 257. Academic Press, 1971.
D. Ruppert. Efficient estimations from slowly convergent Subbins-Momne process. Technical report, Cornell University Operations Research and Industrial Engineering, 1988.
Sacks. Asymptotic distribution of stochastic approximaton procedures. The Annals of Mathematcal Statistics, 29(2):373-405 1958.
13

---

M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Math. Program., (62(1-2):3-112,, 2017.
B. Shi, W. J. Su, and M. Jordan. On learning rates and Schrödinger operators. Journal of Machine Learning Research, 24:1-53, 2023.
N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting, Journal of Machine Learning Research, 15(56): 1929-1958, 2014.
L. G. Valiant. A theory of the learnable. Commuu, ACM, 27(11):11341142) 1984.
V. N. Vapnik. The Nature of Statistical Learning Theory. Springer, New York, NY, 2000.
R. Vershynin. Cambridge Series Statistical and Probabilistic Mathematics. Cambridge University Press, Cam- bridge, 2018.
Probability: An Introduction with Applications in Data Science.
M. Wainwright. High-Dimenssonal Statistics: A Non-Asympiotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2019.
M. J. Wainwright. Stochastic approximation with cone-contractive operators: Sharp -bounds for Q-learning, arXiv e-prints, art. arXiv: 1eee:00055..5 2019.
X. Wang and N. Gao. Stochastic resource allocation over fading multiple access and broadcast channels. IEEE Transactions on Information Theory, 56(5):2382-2391, 2010.
Y. Wang, M. Chen, T. Zhao, and M. Tao. Large learning rate tames homogeneity: Convergence and balancing effect. International Conference on Learning Reprexentations, 2022.
N. Wiener. Nonlinear problems in random theory. MIT Press, 1958.
L. Wu, C. Ma, and W. E. How SGD selects the global minima in over peer-aammtterized learning: A dynamical stability perspective. In Advances in Neural Information Processing Systems, volume 31, 2018.
W. B. Wu. Nonlinear system theory: Another look at dependence. PNAS, 102(40):14150-11154, 2005.
W. B. Wu. Strong invariance principles for dependent random variables. The Annals Probability, 35(6):2294-2322 2007.
W. B. Wu. Recursive estimation of time-average variance constants. Ann. Appl. Probab., 19(4): 2009.
W. B. Wu. Asymptotic theory for stationary processes. Statistics and Its Interface, 4(2):207-226. 2011.
W. B. Wu and X. Shao. Limit theorems for iterated random functions. Journal of Applied Probability, 41(2):425-4 436, 2004.
W. B. Wu and Y. N. Wu. Performance bounds for parameter estimates of high-dimensional linear models with correlated errors. Electronic Journal of Statistics, 10(1):352-379 2016.
H. Xiao and B. Wu. Covariance matrix estimation for stationary time series. The Annals of Statistics, 40(1), 2012.
M. D. Zeiler. Adadelta: An adaptive learning rate method. arXiv e-prints, art. 12125:121,.5701, 2012.
C. Zhang, S. Bengio, M. Hardt, Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In 2017 International Conference on Learning Representations (ICLR), 2017.
D. Zhang and W. B. Wu. Gaussian approximation for high dimensional time series. The Annals of Statistics, 1895) 1919, 2017.
14

---

D. Zhang and W. B. Wu. Convergence of covariance and spectral density estimates for high- dimensional locally stationary processes. The Annals of Statisties, 49(1). 2021.
Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56-134,, 2004.
Y. Zhong, Li, and S. Lahiri. Probabilistic guarantees of stochastic recursive gradient in non-convex finite sum problems. In D.-N. Yang, X. Xie, V. Tseng, J. Pei, J.-W. Huang, and J. C.-W. Lin, editors, Advances in Knowledge Discovery and Data Mining, pages 142154, Singapore, 2024. Springer Nature.
15

---

8 Technical Appendices and Supplementary Material
8.1 Existence and Uniqueness Global Minimum
Lemma 3. Consider the minimization problem 3 arg mingeRs G(B). If the function G satisfies Assumptions 0 and then a global minimizer 3 exists and is unique.
Proof of Lemma We first show the existence of global minimizer. By the coercivity condition in Assumption |). G(B) oe, which implies that choose some large ō E IR such that the sub-level set
S = (B R" G(B) S 6}
non-empty and bounded. Since G is continuous by Assumption 2 S5 is also closed, and hence compact in Rd by the Heine-Bove Borel theorem. Finally, by applying the Weierstrass extreme value theorem, there exists 3 Sq such that G(B*) minges; G(B). Since for any S5. G(B) > 5 2 G(B*). G(3*) mingeR G(B).
Next, show the uniqueness of the global minium. Assume that there are distinct minimizers G1 * 32. By Assumption 2 there exists μ > 0 such that
((3) 32) 1(=1) VG VG(B.)) 2 μ| B21: > 0.
However, since 31 and B2 are both minimizers, VG(33)) VG(32) = O, while n1 B21: This leads contradiction, which finishes the proof.
8.2 Example: Linear Regression
As example, consider the SGD algorithm for the high-dimensional linear regression, observing independent and identically distributed (i.i.d.) pairs & = (æ1, v1), E2 == (x2, 12),.... satisfying
Vh x B+ Ek. for k 1,2,
(18)
for random noises eg that are independent of sy with R[ex] = and E|Ex] < oo for some g 2 We verify Assumptions 2 and 3 and derive the explicit dependency of the learning-rate, the Lipschitz constant, and the moments of the gradient noise on the dimension d.
Let & (y, æ) be an independent random sample from the same distribution as the data. The least-squares loss and the stochastic gradient are respectively given by
(BB [ x B)2, and Vg(B,E) E) -(y x 1)xx.
(19)
Then
VG(B) = (V -
El( - x [)==] = E(xxx - (3)
(20)
Let
= Elwx ], v 3
(21)
To verify the t -type strong convexity
(B1 - (11--3)0((- ((=-1),,, VG(B)- VG(B") 2 1/B B3
for all 8,3' Rd
imposed in Assumption observe that VG( VG = Ev. Thus, the condition becomes
(v--1 Ev)
0 < (o) inf
(22)
vER' 2040
|0|
Lemma 4. Let E (2,4, 4,6,6..... .... Writing Σ (Eij )i l...ddy we have
(8) min
min
Ei
Σ Eagle
i=.....d
16

---

Proof of Lemma Write v (U1...., va) U/l + 1 S of + 13 and
- Because of ""0y"" 111l)=1)((1)))) |2y)) 2 0, we
obtain lef 1
(0)0)))) Σv) = Σ Enet
Eis E0s(us_'03 Dj 2200-11
iej
d
E
Egg (of + 0z)
2m
icj
min
Eg
Σ Engl)
Σ 2/.
jitti
This shows that the rightmost "Gershgorin gap" min;:-...... Eis - -E |اy is a universal lower bound for every s. The lower bound is non-trivial if & is sufficiently diagonally dominant.
For large 8, the inequality (G) 2 min;=1,....dd Ea- - Ejs |re is nearly sharp. To see this, let i" be the index i that minimizes min Eg Σj Etyl. For small 5 > 0, pick v (v1,..., ua) by choosing (0(=-1) = (0, (0.0,... O.... 1,0, 1.O,.... of Ev is given by Ei- Ejfe [E + (6)). Hence for suitable sequences + 0 and 8 + oc, we obtain @(--11), Ee)/|ol E Ej | min, Di Σi [agl
== 1 and for i + i", taking = sign(E++;)(1 - 6). For large s,
0) with the at the i"-th position. Similarly, /0|3 = 1. The 1 -" entry
Regarding Assumption 3 we investigate the dependence of the Lipschitz constant Ls,g on the dimension in high-dimensional linear regression models. If s* is the dual exponent of s, satisfying 1/s + 1/s* = 1, we show that the condition holds with
Lagg ||| =111
(23)
To see this, for any two vectors B, E Rd, we have
Vg(G,E) Vg(3', 5 --((0- (w- x B)ar (y - x 3B)x)))) xx [B -²).
(24)
Taking the -o-m both sides, obtain
(g(3, - (g(3', f) xx (B - 1-) -|00|s x: T - (3-
(25)
By Hölder's incquality, for the dual exponent s* satisfying 1/s + 1/s" 1, it follows that T - B¹) s |z|--- 3 -31
(26)
Therefore, for q 2 2, we have the g-th moment bounded as follows,
1/9 < (B[=)1|=1))) "118 B',s. (O(B'.E)1)
E Vg(B.E)
proving 23
Recall su defined in 7 To bound the -orm, we set the conjugates
Sd
(27)
1
Recall that for the -orom, we have |o conjugate noamnorm, d 1-11
| le
dl/ea
lo S e////oo- Similarly, for the
dd S e implies
1 | S
1 d'd
x < x
(28)
which together with
23 gives
Lea.g S e
|||
x
(29)
The next two lemmas show that the tail behavior of the covariate vector mg determines the behavior of the Lipschitz constant Lagg and the moment Ma.y defined in Assumption 3
17

---

Lemma 5. Consider the linear regression in 18 with i.i.d. generic random samples (x. v). where
a (T1....,, ..a) Let 2 and recall 8a in
(i) (Sub-Gaussian If there is a constant such that for all u E RR, |u 2/ S K/uu2, where 1loa inf(t > 0: Ele / s 2] denotes the sub- Gabb-Gassinn norm, then
Laan - Oldv/loggd))
(ii) (Sub-exponential) If there is a constant K such that for all u ER.,, |u æ I K|ul2. where pl in > 0: Elelol/g S 2) denotes the sub-exponential norm, then
Lea (odlod)))
(iil) (Finite moment) If there is some p 2 2q and a finite constant Kp such that for each 1sj < d, Bl S Kp, then
L.a.9 = =od
(iv) For all three cases (i)-tii),, when 2, L2. = Odd).
Proof of Lemma 5 We write a = 2x to denote generic covariate. By (29 and Hölder's 's incquality, Laa.g xc sc | S e|||a|| |22
The convexity of the function + و and Jensen's inequality yield |a 2o s d Eÿ 120 12g and
Ela 22
24
d max E|r,|24 ISiSd
Therefore, for all the three cases (ii),
|| 112 O(d).
Next, we study the order of (E(la)22)) ((2g) for fixed g 2 2. (i) each zy is Sub-Gaussian, then by Scction 2.5 in Vershynin (0188) we have
[E max Ssid
[zy
(2) < K(v (og/) + v O( (lo/))()))
(ii) If each ry is sub-exponential, then by Section 2.7 Vershynin 2018 we obtain
(E max IS |
(22 O(K (log(d) + log(4))) = O(log(d))
(iii) If each 2y has the finite p-th moment for some p 2 24, then
E max
(,,120] <
B||,, Pr] S dK, = Odd).
Isisd
1SiSd
Finally, for case (iv) with s4 2, by (23
L2 = || 12.-
By the convexity of the function
we apply Jensen's inequality and obtain
|
2
d
x
j=1
j=1
Therefore, for æ satisfying case (iii),
d Σ
E|a
2q
d-
E 2
24
<
d ddpp,
(30)
j=1
18

---

which yields L2.4 = O(d). For the cases (i) and (ii), by Sections 3.4 and 2.7 in Vershynin (0018) respectively, we obtain
|| = ((K(OO((()))) = O(vd),
and
= =(((()))))= o(va),
both indicating T22, (d). This completes the proof.
Lemma 6. Consider the linear regression model in 18 and assume the conditions and therein are satisfied. Recall that Ma.g = 3 For the same four cases (i)-(iv) in Lemma S and sa defined in 77. Mea. is respectively equal to (i) O(V/og((e (ii) (log(d)), (ili) ((2//(24) and (iv) O(vd).
is defined in Assumption 3 for some 2
Proof of Lemma 0 In the linear regression model, the stochastic gradient at the global minimum 3 can rewritten into
V - (y x: (3) - -C. Since the noise is independent of the covariate vector æ. we obtain
Vg("" ( =., = |||c| | = |||||||||~]
By inequality (8) it suffices to bound |||=||>0 llq- Since || ||| the same arguments in the proof of Lemma 5 carry over immediately. We omit the details here.
I
8.3 Some Useful Lemmas
Lemma 7 (Maximal inequality [Chermozhukov al. 2015)). ) Let 21:...,2. dimensional random vectors. Denote the j-th element of 2; by Zij.
on be independent, d-
1 S d. Define M ==
maxigign maxigied [Zig] and o² == maxxissd
D TE. [ Then,
max ISJSa
Σ (21g
E Lvvlogid E[
+ 1E[M2]log(e
where the universal constant in S is positive and independent of n and d. Lemma (L& maximal inequality). Let , ..... Da be independent, d-dimensional random vectors. Denote by Fag the j-th element of x; j d. Then,
< è² (ng 1) Σ (xy - B(r
Σ 1=1
max
max 15jSd
This moment inequality can be derived by repeatedly applving Lemma 2 It generalizes the maximal inequality for Elmaxigisal Σ (dag E[x,g]]] in Chernozhukov et al. (015 reproduced above as Lemma to general g-th moments.
Proof of Lemma 8 One can assume that the independent random vectors 21,..., En have zero means. By repeatedly applying Lemma and choosing s = log(d),
[1 + ... + x, l
<
| + ... x,, 1
||| +... xn 1 (max(g. 5s - 1)
(max(q. 8) 1) Σ ||
<e² (mxx{q - Σ |1: 11
19

---

Lemma 9 (Moment inequality F with fixed d 2 and let
Li et al.
2024c]).
Let q 2 2. For any two random vectors a and y in
A
x 211
||0:12 g||0: 11:2:12-200 y
Then, the following inequalities holds: (i)
A S R (|122|12 + I1vll2))
B||ar|13 g - 112/112).
(ii)
(1 + (1lly -B ( a2 (B)l))) 13)
12
Lemma 10 (Equivalence of -induced matrix norms), For matrix A E Rdxd we have the equivalence of the gh -norm and 8o -norm induced matrix norms follows
|A S ||Al|s S Alloss
(31)
where is defined and ||A||s max |Ax|s//aa 1/////s- in addition, A is symmetric, then
||A||
|| - ||A||s, - ellAll ell.111--
(32)
e
Proof of Lemma 10
By Horn and Johnson 19855. for any 1 S 5 q S so and matrix A Rdxd
((1/))-(1/)) ||All, - ||A||p d (1112)-(1/9) |AAll-
(33)
For and = oo, we obtain
d 1-101 |||| - ||A| S d'I11
(34)
Since d=/s < e by choosing 8 = Sa in 77. we obtain (31)
For symmetric A = (aij)isisaa Gej
aji for all i,j. Therefore,
||||i
max 15/5d
Σ angl max
Layl
||A||
(35)
This completes the proof.
8.4 Proofs for Section 2
Derivation of 15 Since s an even integer, we can write
f(() = azl (x. az))²
(36)
Taking the derivative with respect to a, obtain
((( = da s(a) !
Σ
(a. az))²
2-1
d
(#t az2)
da
1=1
7-1
a3 az)'
s(1, a22) a-1 (-2))
3-1
=
(r; - az1)
(2) - a2z)
1-1z% 21.
(37)
1m1
Therefore,
('(0)
of
Σ
1=1
2
(38)
A first-order Taylor expansion yields then
15
20

---

Proof of Lemma] 7 Recall that we have defined
d
f(a) = xe - az1?
Σ
(x; az))
1=1
A second order Taylor expansion gives suffices to bound suPue[o,a] [-) Defining
f(0) + af (0) + (n) for some n) E [0, It
-
Mu) Σ x2 uzi x u.z (
(39)
we have f(u) = [
d M'u = - >
(c; uzi)
8-1
(40)
i=1
d Σ
M" = s(s 1)
(x; uz;) )=- 22?
(41)
and the first two derivatives of f(u) can be respectively expressed by
('(u) = 9 [M)] [M(
(42)
("(u)= = 2 ( (2- [M [M])) + (MN))))
({-1))((w))
(43)
s
Since s is an even integer, follows from Hölder's inequality that
d
[M]( = s²
Σ
(x. uz,) 1-1 2
uzz))=== 21
d 1/8 2
S 32
[ -uzzz )0)
i=1
= 2² - uz 22 1/-1)/221 1
(44)
By applying Hölder's inequality again, we obtain
d
d
2/8
[M) S s(s 1)
Σ
(x: uzi)))
1=1
i=1
= =s(s - 1)(x uz 1: 5-2 2121
(45)
By the two results above, we have
(u)(
q q ss
-1) |z- - 22 + (M) 9 x
u=
glg s| xx -= 1)|= -211 1
< <g1l9 - sa + (s - (=0. 2- 1
(46)
Since u E [0, a], follows that
sup
[s"(w) 014 s|++ (s 1)] (lx). + al21))*~
(47)
we[0.a]
This completes the proof.
Existence of solution to
13 To see the existence of the solution as.q in
[ qllg-
s| + (s 1)) L2
1 qua +
a 2 (1 + )
denote the function a + F(a) -a (1 ++) for the constant c = ||g - (s-1))/2
and L. = I.s.g- For any 2 2, and any a > 0, F¹ (a) = c|(1 La)) - proving that F(a) strictly increasing on a > 0. Since F(O) p < and F(xx) = +00, the
unique root to F(a)- 0 cxists.
21

---

Proof of Lemma
2
Define ppt) = || + tyy=lll for t E [0, 1]. Then
(1(1)=
2
Biy + 1y5) 9/07 2/
2 E
(o) + 121))
s02 + b111 ) y3
8
/=1
==1
j=1
(ny + kyy) / 8/07 2/9
9/0-1
2 R
E
(ay 1u5)
Σ /=1
(zg + (1yy)) μ3
and
((()= = 2(2 2 - 1) [ Σ (og + tyy)) // j.in1//// 2/0-2
q
1=1
9
s E
Σ
d
(Ig + )/) 1//-11 d
Σ 1=1
(az + ty,y :ttyy)
2
8
j=1
(x) + ty;) 8///// 1//0
+ 2 E
Σ
j=1
E (3 - 1) { Σ
(zg + ty;)
9/5-2
azy + tyj 3z "v5} }
5=1
+ 2 E Σ
(z, + tyj )0) 8/37 2/99
(x) + tyy )0 g/0
1) Σ (z, + (1)+
E
j=1
j=1
At) + (t + (t()
Since q 2, (t) S 0.
Case I. 1f g/s 1 s 0, then 2t < 0 and (²(t) S As(t). By Hölder's inequality,
Σ Loy + tyy 8 20} 1 Σ (xn + tyy, (0-2)/0
2/a
Consequently,
Aa(l) S 2(s 2(0-1) [B{ Σ
2/072/0011
(or + (yg)
1=1
9/0
(0-2)/9 d
2/0
EF
(oy + (455)
Σ
(2n + lyg) s
Σ ==1
j=1
= 2(s - 1) [ Σ
(5g + (yj)) )a)
9/0 2/9-
E
(xg + (ر55
()-2)/e
d
2/
j=1
2(s 1>|| + 1yy1 112- { Σ
d
(4-2)/8
d Σ
2/07
(xr + 1y5) )*
3=1
S 2(s 1)|l tyyle11 11 | + tyl 11 1//111
= 2(s 1) ||1
Case II. If q/s -
>> 0, by Hölder's inequality,
{
Σ
d
(a3 + (2g)
Uグ 2
Σ 1=1
(Iy + ty, ty,) (2) + )/1 '13 2
1=1
d
(a. + tty))
)
Σ
(x, + ty, 2
j=1
1=1
22

---

Therefore,
A2(1) S As(t)² 9 9-
and
('(1) A2(1) + As(1) & As(1) --(1)=11 S 2(1 1) y1>
Then, we have
x + ylx = (00) + / (1- (t) dt
|| 1 2 2 11111111100 1111-1EE(i1 '(11) Σ 2タ 2イ
U3) (max(q,s)
Proof of Theorem
Consider the iterated random function
F F:R + R, (B, F = -
(48)
To prove GMC Theorem fixed vectors B, 3' e Rd.
it suffices to show that, for some 2 and even integer 2 2, for any
[1(e(()) - - S <r...gl -
Recall the inequality in Lemma For and y therein, choose them be B B and {))
= (VVg(3 {) (3( respectively. Then, it directly follows from Lemma 2 that
(()) Fe(
$ 13- 312 2a/3 31 " 18 B 3 3---1 Vg(B.E) Vg((B'
+ a +m2xmax(4 }) 1)1l - T,(B',<)l-11
= - 22aB 31- -----))--111- G((
--)) G(B)))
+ + *) 1) E) - Vo(3',E)1l
This along with Assumptions and
yields
((9) (e( z (1 2at a² (max(q,s) 1) 181
which completes the proof.
8.5 Proofs for Section 3.1
Proof of Proposition
Recall and let VG(3) (B),
with
(3) aG(9)/88 (B(V)(B,E)),; 1= d.
(49)
Since the random samples εx. A: > 1, are independent, it follows that for the k-th iteration, E is independent of B Then, by the tower rule, for all 2 1,
B E Vo (+) VG(3 | =
VG(B; = 0.
(50)
Therefore, by applying the high-dimensional moment inequality (16) in Lemma 2 we obtain
B 10-33%1l 11, |||| 3 -
+ (max(g. - -L)
(51)
23

---

For the second part in (5T) noting that VG( 0, by the triangle inequality, we have
Vo( - VG(B
([ Vg(3", (x))a,), ||1++(+11V(()) VG(3"). + (/ (.))olla)) < ( Ex) Vo(3",
&ollll F VG(Bx-1) VG( 3 & )
(52)
Since l is convex function for 2 1, we have |B|:1| < E1| [.]. Thus, for all 1, by Jensen's inequality, we can bound
VG(Bx-1) VG
= E Vg(Bx-1, Ex) - Vg(3", [x)]l
< BE
1. VO(3" V ,.))%))) 1/9
(53)
This along with Sesumptionnyyeeleee
- VG((3)) - (EgEg Vg(Bk- Eb) Vgg(e" E+) 1/9
Vy(3" E.)ll,1,, : = V
- L..q | |B 3² le
(54)
Inserting this result back into 52 we obtain bound for the second term in 51 using
[/V VG(G < 6T.2, || 1/ 3|ll "3" <x))<
(55)
For the first term in (5I). by applying Lemma again, it follows from Assumptions and 3 that
||1B-11- 3 -VV
< 11118-11 11118x-1-B811 20/|1
1112
| -31%% 1311112--1 (1661 3-1 Σ
(B-11- 1G
j=1
+ a=2mmxx (1,8) - 1)]| ( - VG(3")1.11
$ (1 (1-2ay + a² (max(q. 111 - 11,
(56)
Inserting this inequality and (55) into (1). obtain the inequality
|| 1 (1 2ap 7(max (q s}
1)a² 1) 11.)
+ 3 $} - 1)a² (g( (00,)))))))) 11,
The desired result is achieved since ||| Ex) for the stationary SGD iterates B ~ na. h 2 1, we obtain the same result.
Ma.g by Assumption
3
As a special case,
Proof of Theorem First, we denote the contraction constant in Proposition follows Fa.e, = 2apu 7mmax (q, 8) - 1)a22)2 L2...
(57)
Given the range of the constant learning rate a, we have Pa,s.g < 1. Moreover, notice that
3mma s} 1)a² Vl En)la
0 maax(g Ja2M2222)
(58)
Therefore, for the stationary SGD iterates B na. by Proposition 1 we can obtain
|| 13,1 < Fare.g || - + O( max(g, sta² M,,))
(59)
24

---

Since the SGD iterates S. satisfy the geometric- moment contraction in Theorem I following Remark
2 in Wu and Shao [004],, the recursion f _ V
-
Ex) also holds for & I 0. Thus,
we can recursively apply the inequality above and achieve
|| 101 -
Σ
a,sia
0( (/max sa
1 Fa,s0
0 ma Mag)
(60)
This finishes the proof for the stationary SGD sequence.
Furthermore, for the general SGD iterates 3₂ in (2) that may not have the stationary initialization, we apply the scometric-moment contraction in Theorem [ and obtain
|| - ,3%lll < || 3 + 11 381
p a. |1 B8llll O ma
(61)
which completes the proof.
8.6 Functional Dependence Measure in Time Series
The functional dependence measure in time series [u 2005 is a key concept in our analysis. For nonlinear autoregressive (AR) process.
that we view the high-dimensional SGD iterates {Be JEEN Recall that ÉN. k E L, are i.i.d. Define the shift process F& = (Ex: (........)) and its coupled version FR.11) (Ex.... ..., E.t E/, f.- S k. where & is an i.i.d. copy of E.-
The stationary sequence {18 can be represented by functional system
B (Ex: .x- (Fxs), k 2 1,
(62)
where No is a measurable function that depends on a [Wiener 1958 version of 3% by
Wu 2005
Define the coupled
Ba = -..(EE,....141 S/: E/-1, = h., (Fv.()))) I k.
(63)
The next lemma provides bound for the functional dependence measure |1159 BR lellg- It is later used to derive the moment bounds and the tail probability of the ASGD iterates.
Lemma 11. Consider the stationary SGD) sequence {B32)221 k21- Suppose that Assumptions hold with some 2 and even integer 8 2 2. Then, for all k 2 and I k, we have
Land
11 11,11 lall 4o (1 2ap + 7(max 8} 1)a² L2 k-1 [12 8.9 |1 - 301 M 8.9
Proof of Lemma 77 By applying Lemma 2 it follows from similar arguments as in the proof of Proposition I that, for each / S
||:38- f 1=1 < (1 - 20y + (1max(1, - 1)a21?2.)) * 11188 lal
(64)
By Assumption 3 for all 2 1,
||V Et) 113 < [e]lVv((Bf_111)
"0(("r,:)+al + +2 Et)lal1
S 2L 111
11 1e 2MM2,.
(65)
which yields
11|88 1e a V
10(8%11-)1111
< a² a2((211 22 & + Vg(B
S 40² 1.2 11,91 - 1/1 + M2.0)
(66)
Recall (IV (x))ll S Ma,, by Assumption
3 Therefore,
|| (R, 111 < 4a2(1 2ah + 7(maax $s 1)a² L2 ) k-1
(12 |1 - 13, M².))
(67)
This completes the proof.
25

---

8.7 Proofs for Section 3.2
In this section, we provide the proofs for the convergence results of ASGD Section 3.2 which can be decomposed into the proofs for Theorems 6 to 8 in Section 6
Proof of Theoremp 7 Recall the i.id. random samples Ex (ykk Rk), the filtration Fk. (Ék, 1..1,...) .) and its coupled version Fk,(1) = (Ek).... E1+1, E I S k, where El is an i.i.d. copy of Er. Following Wu 22005] we introduce the projection operator
P:H E[- Fi] B[- Fi-1].
Then, can rewrite the centered ASGD into
1 k i-1
k-1 Σ Σ (g))
B
Σ
(3))
(68)
Since (B) |2 is sequence of martingale differences over i for each = 0......, 1, following Lemma D.2 in Zhang and Wu [221]] and triangle inequality, we can obtain
P PB)) 11g
|| - EJG
1=0
i=1+1
k-1
(s-) .11.
1=/+1
Σ (19:11())111111 1/2
(69)
i=1+1
By Theorem in Wu 2005]. we have
(1P::1 S || 3i, 1i,te-1plalle
(70)
This along with Lemma 11 and definition of Fo,s.g in (58) yields
[|P):1(())1a113 < 40²(1 20I + 7(max (q. 8) - 1) (1212
L 11 1/1, Ma...
40 a.s
1.2 1220111/51111 B 1/1=11 M2
(71)
Recall Fa,s. in (6) and Po.s.g in 58 For some constant >> 0 such that
min
2p 7(maxfq, s} - 1)aL2g)
(72)
have wax and Consequently, further bound
To,s.g S Fa S 1 - wa <1
(73)
69 by
||
||
k
1/2
4c say sa² 2 (1 wa)
Σ
-B'1,?? + M2
i=/+1
1/2
4c,, (1 wa)( L2
|118
1/ + (I: 1)M2a
s=1+1
20 (1 - wwa) Lon
|1|30 |113 - 1.11
1=1+1
20 cy wwa) /(k - 1).Ma.g
=: 11 + 12.
(74)
26

---

For the term 1,, it follows from Theorem 2 and expression (58) that
Σ
6MM, (max 1)(x)
:=-11
= 6a(k - ()max(g - 1)M2...
(75)
Inserting this back into 74) gives
20 8 8.
S
wa) Ma.9 6a(k (maxx $} 1)
k
Civa
S
Ma max $s
(76)
Vk
for constant e > where the last inequality is due
Vk
(a- vk Σ wa-waa)/22
=0
(77)
Wil
Similarly, for some constant 02 0,
22 c
1 S
Ms.g.
(78)
Vi
Combining the results of I and 12, we obtain the claimed inequality
Cq (ClagvaaMon max + c2Maa).
11138 1 S
V
k
For the ASGD sequence (3x JeNN with arbitrarily fixed initialization 3o E R and the stationary ASGD sequence [Ba with S8 Tae we have
Proof of Theorem 6
&
1| - Bhlalla = *111 Σ (B: 8.) /3)|_11
1
<
|1 1.1all
(79)
For each 1 S < kt it follows from the gcometric-moment contraction in Theorem that
|| - 191111 S r 11.30 - -801-ll--
(80)
Recall that Ta,s.4 2pcc + (max(g. - 1) 5,
0. < in 66. Therefore,
Fo,s,a - r(rg))
|| 101allo S k
11100 - 13%11l1 v ra,s
11130 - 881allg-
(81)
Ta,s.
The desired result achieved.
Proof of Theorem 8 Without loss of generality, assume B 0.
We use the notation 17 for the
derivatives G. Notice that
VG( = VG(O) 0.
(82)
Consider the stationary SGD recursion
- - a V k: 2
By taking the expectation the both sides, obtain, for all k: 2
B = 0.
(83)
27

---

Throughout the rest of the proof, we omit the iteration index h and write B = 3/-1 when no confusion is caused. For notational convenience, write ,a)....,Ba)..
first-order Taylor expansion on VG at 3 gives
0 [ VG(0) ( R(3),
(84)
where V²)(0) the d x d Jacobian matrix with entries defined by
8²
[G as,03; ((()
1 1 i,j d,
(85)
"=0
and R(3) is the d-dimensional remainder defined as
R(B) - [// (V(V=))( dt.
(86)
The i-th entry of R(33 can be rewritten into
Re(B3 = (1 dt,
(87)
d. as where (i
x d matrix whose entries are
G.., = 03,0300, G(B), 1slrsd.
(88)
Since VG(0) 0 and V²G(0) is invertible given that Amin [ > it follows from equa-
tion 84 that
E|g "OPGG(O)-ERR(CR
(89)
We only need to bound [[[][ using Theorem all k 2 1.
2 that is B8[ 3= (max s)a) for
Let 3/13) For each I,...,d.
[[)] (-) (1 (1-t)B|6 (tG)
{ (1 1
(90)
By Hölder's inequality, for 1/p
Ei [ (B (B(u ((C00))()))))))
(91)
Again by Hölder's inequality,
E v
(t())))) < d
sup (
(92)
|=,=1
Therefore, by Theorem 2 and Lemma
10
[|33] S M2,, max(g, 3l (1-33 3)
max
(93)
1si5d
where the matrix norm
max 15
(v))) 15)
(94)
Finally, given the uniform bound maxisied
(B) < 30,
E[A = 001 (M,, max s) sud -r (1- 22) 2))
(95)
which finishes the proof.
28

---

8.8 Proofs for Section
Proof of Theorem By Theorem quently, it follows that
6 we have 1113 Bilsllo E 1/(ka)
Golells and conse-
11130 Galell
P(IG 3% > 2)
2 2>0 0.
(96)
(kaz))
Then it suffices to upper bound P( - 3-1
2).
To this end, we first bound the dependence
adjusted norm (Section 2 in Zhang and Wu (017 for (8))221- By Theorem |
elementary
calculations yield
Ma.9
|113g [[ (11.alllll../2-1/// O
1/2--1/4
Consequently, by Theorem 6.2 in Zhang and Wu [017] and Theorem 8 we have
3 - - =) (log d) d))0//2 (log k) 22 M
C 2/9
exp
z9k9 0
M2,, logd
Combining this with (96) completes the proof.
Theorem (Theorem 3.1 in Mies and Steland 2023 Let (G))sz be ii.d random variables and
C₁ (Ck, Ok-1....). Assume X₁ = Gx(cx) E Rd with B[Xa] = 0 for some measurable function Gk. For any denote čk.j (Ck...., &y, G-11....) with εg an i.i.d. copy of cj. Assume there exist θ > 0 and 2, such that for all k.
(E|G)(E)) Gx ()(E
(jV1)3 for all 2 and (BIGa(ce)lB) S.. (97)
Additionally, assume that for some 2 1,
(LEIGA(EO) Gk-1(Eo) 3) r.
(98)
If d S en for some O, then potentially different probability space, there exist random vectors (x))mm =D (Xx))= and independent, mean zero, Gaussian random vectors
Yi ~ N( 1=-00
Σ
Cor(Gu(e)),
such that
1/2
1 m
E max V
Σ ( YF)
s cert Vlo(n)
log(n)
for some constant C depending c).
Instead of univariate é,, we apply Theorem 3.1 with vector vector-valuce valued i.idd. inputs &,. The theorem still applies as the proof depends only the i.i.d. random elements and their L bounds but not on the dimension of E..
Proof of Theorem 5 To prove the Gaussian approximation will apply Theorem (Theorem 3.1 in Mies and Steland 2023 with Gg = ha defined in (62) since 3 is stationary. We now verify
the conditions 997 and 988
Recall the functional dependence measure |1|,3 - 3 (n) ll introduced in Section 8.6 Throughout proof, the q-th moment of the Euclidean norm denoted by
|| 11g : 1111 lall,
Set
Pa.q = 1- 2ay 7(maxfg. 1)a² L3 Ca.g 20 cL3 max(g, 2)a
2
(99)
29

---

for some constant O. If с is chosen sufficiently large, then, by Lemma and Theorem 2 for all k and I k. we have
11 (9. I 4a Pap 2(k-1)
[12 1 )
- -3"11
Pa.l
s 4a Paiy
2(k-1) M2
cl22. ma, + 1)
-Cagpai 21k-11) M2
For E (0, asa.g), it follows that Pa.q < Let Co we have
Then, for sufficiently large constant
1 (t-ll- S Can-Maaaaa Ma.MM.((+1))
(100)
Therefore, the condition (97) holds with θ C2. This verifies the first part of condition 97 For the second part of condition 97 by Assumption and Theorem 2 for some constant Ca.g
-1, 11 || - 3 11, 18 Ca M2.g
(101)
Moreover, since 3% is stationary, G2 = Gk-1 = ha and the left hand side of (98) is zero. Thus, condition (98 is trivially satisfied with r = 1.
Finally, we show that the long-run covariance matrix E Di- oo Cov is well defined in the sense that the spectral norm
||||, finite. Following 663) denote
B (A = 3 (....011 ha .......,,41.. E...1......) ha (F (Fr.....-1.)))) 1 k. (102)
Since 3 Pk1500 is independent of Bi, we have
Cov( ( = 3| - ||
[3) (
(103)
We rewrite the difference as a telescoping sum,
B - (2 -
- (2)(5-1)))
(104)
t=
By stationarity and (1OO). it follows that
|| (S-+111
3 f8.1--0l12 (1 112 112 S Ca.2Ma,nP22 A+1-1
(105)
For the spectral norm,
[Cov(B)
sup U.DERd mm/amm
Ev BiC -hh((5o)
[B(w T //) - BP, ]T. uu?
sup p
|8 (
(106)
where the first inequality is by Cauchy-Schwarz and the last inequality uses (u [B) < 1/8/ with [u/2 = This, along with M2.2 < oo (Assumption 3 yields
Coov(36 (8)
s 11 BR S C.Pt.
(107)
for some constant C²2 0. As a direct consequence,
E| < EE
+2 2 C.pl. < <0.
(108)
R=1
This completes the proof.
30

---

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 included subsection in the introduction to list our key innovations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We talked about the limitations in the last section, especially for the assump- tions of strong convexity and smoothness.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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]
We provide rigorous proofs for all the theoretical results in the supplementary material.
Justification:
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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: 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 whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper contributes to theoretical guarantees of high-dimensional SGD.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. .., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) 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 or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "cippscc/puulli//guu /ttee//ggudddeeeedSuuuummbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
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: [NA]
Justification: This paper does not include experiments.
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, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation 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 errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in 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 execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp/://eaarrp....cpppppbcccct
Answer: [Yes]
Justification:
We followed the NeurIPS Code Ethics instructed.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal 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 machine learning, which can inform
the development of more robust and efficient algorithms. As the work purely theoretical 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 why the paper does not address societal impact.

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no 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 to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
5

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 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:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing 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 as 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 in the main paper.
According the NeurIPS Code of Bthies, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
This paper does 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 on 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 we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, 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 an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standarr components.
Please refer to our LLM policy bestps:/nneurte ////oonffreenee/22225. for what should or should be described.


Reviews:
[{"review_id": "LPslBM59fA", "reviewer": "Reviewer_1YYQ", "summary": "This manuscript investigates the convergence of SGD and its averaged variant with constant learning-rates in high-dimensional regimes.", "questions": "The questions that I am concerned about have been listed in the 'Weaknesses'.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The authors propose two assumptions on the objective function and the stochastic gradients, which make it possible to prove the asymptotic stability in distribution in SGD iterates with any initialization. GMC is the highlights of this study.\n2. The contraction of SGD and its averaged variant in max-norm and moment bounds are also derived.\n3. For the averaged SGD, the corresponding tail probability inequality (in max-norm) is proved, which implies a sharp high-probability upper bound. \n\n\nWeaknesses:\n\nsome typos\n1. Since the abbreviation 'GMC' will be used in line 138, it should be mentioned in line 45.\n2. In line 671-672 of supplementary, punctuation mark is missing in the the inequality.\n\nmajor concerns\n1. In a series of work by Paquette et al (see some selected papers below), they study the high-dimensional SGD for the least–squares problem. The authors also consider linear regression as an example to illustrate their theoretical results. Could you please provide a detailed comparison between these literatures and your works? I believe this would help us better understand the contributions of your research. \n\n    [1] Courtney Paquette, Kiwon Lee, Fabian Pedregosa, Elliot Paquette. SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality. 34th Annual Conference on Learning Theory (COLT), 2021.\n\n    [2] Courtney Paquette, Elliot Paquette, Ben Adlam, Jeffrey Pennington. Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions. Advances in Neural Information Processing Systems 35 (NeurIPS), 2022\n\n2. Although the authors mentioned the limitation of 'strong convexity' in Assumption 1, I am curious about whether this assumption can be relaxed to obtain the main results of this manuscript. \n3. I would be glad to see more validation of the theoretical result. The authors should provide some numerical experiments to illustrate their theoretical results.\n\n\nIn summary, I am currently leaning towards suggesting a Borderline Accept. I look forward to receiving further clarification, which leads to a reconsideration of my evaluation.", "was_revised": true, "final_justification": "I believe the author(s) have thoroughly addressed my concerns. So, i should raise my score.", "rebuttal": "Thank you so much for your thoughtful evaluation and for recognizing the contributions of our work. Your feedback has helped us clarify the significance of our results. In the revision, we will fix the two typos you kindly pointed out. Please see our point-to-point responses to your major concerns below.\n\n**1. In a series of work by Paquette et al (see some selected papers below), they study the high-dimensional SGD for the least–squares problem. The authors also consider linear regression as an example to illustrate their theoretical results. Could you please provide a detailed comparison between these literatures and your works? I believe this would help us better understand the contributions of your research.**\n\n**[1] Courtney Paquette, Kiwon Lee, Fabian Pedregosa, Elliot Paquette. SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality. 34th Annual Conference on Learning Theory (COLT), 2021.**\n\n**[2] Courtney Paquette, Elliot Paquette, Ben Adlam, Jeffrey Pennington. Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions. Advances in Neural Information Processing Systems 35 (NeurIPS), 2022.**\n\nThank you very much for pointing us to these two interesting papers. We have carefully read them. The key techniques therein are very novel, but we believe they rely on the quadratic structure of the least-square loss, which cannot be easily extended to nonlinear cases. Our proposed theory serves as a complement to these studies. Below we provide a detailed comparison.\n\n(i) **Settings and techniques.** Paquette et al. (2021) study the least-square problem\n    \n\\begin{equation*}\n        \\min_{x\\in\\mathbb{R}^d}\\frac{1}{2n}\\|\\mathbf{a}_i\\mathbf{x}-b_i\\|^2, \\quad \\text{with }\\mathbf{b}=\\mathbf{A}\\mathbf{\\tilde x}+\\sqrt{n}\\mathbf{\\eta},\n\\end{equation*}\n\nwhere $\\mathbf{A}\\in\\mathbb{R}^{n\\times d}$ is a random data matrix whose $i$-th row is $\\mathbf{a}_i\\in\\mathbb{R}^d$, $\\mathbf{\\tilde x}\\in\\mathbb{R}^d$ is a signal vector, and $\\mathbf{\\eta}$ contains the noise. The Hessian $\\mathbf{H}=\\tfrac 1n \\mathbf{A}^{\\top}\\mathbf{A}$ is a fixed matrix (independent of the parameter $\\mathbf{x}$), admitting an orthonormal eigen‐decomposition. This allows one to rewrite the SGD iteration with learning rate $\\gamma$,\n\\begin{equation*}\n        \\mathbf{x}\\_{t+1} = \\mathbf{x}\\_{t} - \\gamma \\mathbf{H} \\mathbf{x}\\_{t} + \\text{noise},\n\\end{equation*}\ninto $d$ recursions individually, that is,\n\\begin{equation*}\n        y\\_{t+1}^{(i)} = (1-\\gamma \\lambda_i)y\\_{t}^{(i)} + \\text{noise in the i-th coordinate}, \\quad i=1,\\ldots,d,\n\\end{equation*}\nwhere $\\lambda_i$ is the $i$-th largest eigenvalue of $\\mathbf{H}$ and $y^{(i)} = \\mathbf{u}_i^{\\top}\\mathbf{x}$ with $\\mathbf{u}_i$ the eigenvector associated with $\\lambda_i$. This form evolves each coordinate $y^{(i)}$ independently as a one–dimensional linear recursion. Then, one can aggregate over $i$ to obtain \n\\begin{equation*}\n        \\mathbb{E}|\\mathbf{x}\\_{t+1}|\\_2^2 = \\sum\\_{i=1}^d\\mathbb{E}(y\\_{t+1}^{(i)})^2 = \\sum\\_{i=1}^d(1-\\gamma\\lambda_i)^2\\mathbb{E}(y\\_{t}^{(i)})^2 + \\sum\\_{i=1}^d\\text{noise variance in the i-th coordinate}.\n\\end{equation*}\nAs $d$ grows to infinity, this discrete‐time evolution can be rewritten as a Volterra integral equation (see Eq. (11) therein), which is the key technique for their theoretical results with clear illustration in Section 2. The paper Paquette et al. (2022) follows a similar strategy by adopting the Volterra integral equation (see Theorem 2 therein).\n\nNevertheless, a general strongly-convex nonlinear loss function $f(\\mathbf{x})$ has non-constant curvature, meaning that the Hessian matrix $\\mathbf{H}(\\mathbf{x})=\\nabla^2f(\\mathbf{x})$ depends on the input $\\mathbf{x}$. This also implies that the overall dynamic cannot be decomposed anymore into separate disentangled univariate dynamics.\n\nInstead, in our work, we view the high-dimensional SGD as a nonlinear vector autoregressive process (VAR) and introduce the geometric-moment contraction (GMC) to study the joint convergence of the SGD vector $\\mathbf{x}\\_{t+1}$ as a whole, which does not rely on any diagonalization of the Hessian. This relies on the powerful concept of functional dependence measure that we introduce in Section 8.6 in the Appendix, measuring the degree of the dependence of outputs on inputs in functional systems (Wu 2005). By writing the SGD recursion into an iterated function, one can apply this tool and effectively characterize its convergence even in high-dimensional settings.\n\n(ii) **Data distributions.** Furthermore, Paquette et al. (2021) requires the data matrix $\\mathbf{A}$ to be orthogonally-invariant (see Assumption 1.2). The authors mention that this is a rather strong assumption with a classical example of a matrix whose entries are generated from standard Gaussians. In addition, the \"quasi-random\" assumption in Paquette et al. (2022) holds Gaussian linear regression, sub-Gaussian linear designs and Gaussian random features with a linear ground truth as examples. As a comparison, our theory allows more general data distributions as long as the stochastic gradients have finite $q$-th moment for some $q\\ge2$ (see our Assumption 2, Lemmas 6(iii) and 7(iii)). \n\n(iii) **Dependence on the dimension $d$.** It is a bit difficult to directly make a comparison on the dependence on $d$ since we consider different settings from these two studies. From our understanding, although Paquette et al. (2022) has relatively strong conditions $d^{\\epsilon}\\le n\\le d^{1/\\epsilon}$ for some $\\epsilon\\in(0,1]$ to derive the equivalence between SGD and HSGD (Theorem 1 therein), it can be relaxed in the analysis of HSGD. In our paper, the dependence on $d$ (see our Eq. (9)) is reflected by the constant learning rate $\\alpha$, the moment of stochastic gradient $M\\_{\\log(d),q}$ and some logarithm factor $\\log(d)$. \n\nIn short, we would like to emphasize that our proposed theory is applicable to a wider range of nonlinear loss functions, including the least-square problem as a special case. The dependence on $d$ can be explicitly characterized for in-expectation and in-probability convergence.\n\n**2. Although the authors mentioned the limitation of `strong convexity' in Assumption 1, I am curious about whether this assumption can be relaxed to obtain the main results of this manuscript.**\n\nWe greatly appreciate your comment on our limitation of strong convexity. In fact, the strong convexity in Assumption 1 cannot be relaxed for the geometric-moment contraction (GMC) result in Eq. (6). To see this, we denote the SGD recursion by an iterated random function as follows\n\\begin{equation*}\n\\boldsymbol{\\beta}\\_k=\\boldsymbol{\\beta}\\_{k-1} - \\alpha \\nabla g(\\boldsymbol{\\beta}\\_{k-1},\\boldsymbol{\\xi}\\_k)=:f\\_{\\boldsymbol{\\xi}\\_k}(\\boldsymbol{\\beta}\\_{k-1}).\n\\end{equation*}\nWe take $s=2$ and $q=2$ as a special example. Assume there exists a pair $\\boldsymbol{\\beta}\\neq\\boldsymbol{\\beta}'$ such that the quantity\n\\begin{equation*}\nK:=\\frac{\\langle \\boldsymbol{\\beta} - \\boldsymbol{\\beta}', \\nabla G(\\boldsymbol{\\beta}) - \\nabla G(\\boldsymbol{\\beta}')\\rangle}{|\\boldsymbol{\\beta}-\\boldsymbol{\\beta}'|\\_2^2}\\le0.\n\\end{equation*}\nFor this particular pair $\\boldsymbol{\\beta}\\neq\\boldsymbol{\\beta}'$, we have\n\\begin{equation*}\n\\frac{\\mathbb{E}|f\\_{\\boldsymbol{\\xi}}(\\boldsymbol{\\beta}) - f\\_{\\boldsymbol{\\xi}}(\\boldsymbol{\\beta}')|\\_2^2}{|\\boldsymbol{\\beta}-\\boldsymbol{\\beta}'|\\_2^2} = 1-2\\alpha K + \\alpha^2\\frac{\\mathbb{E}|\\nabla g(\\boldsymbol{\\beta},\\boldsymbol{\\xi}) - \\nabla g(\\boldsymbol{\\beta}',\\boldsymbol{\\xi})|\\_2^2}{|\\boldsymbol{\\beta}-\\boldsymbol{\\beta}'|\\_2^2},\n\\end{equation*}\nwhich is strictly larger than 1 for all $\\alpha>0$, violating the GMC in Eq. (6). \n    \nThis GMC result is the key property such that the SGD iterates converge to a unique stationary distribution as the iteration number $k$ grows regardless of the initialization $\\boldsymbol{\\beta}\\_0$. For the more general settings such as the non-convex loss objectives with multiple local minimums, the convergence of the algorithm will be more sensitive to the choice of initialization. For example, bad initializations may trap the iterates in some local balls. In such cases, it is unlikely to achieve the convergence to a unique stationary distribution for all initial points. However, we would like to emphasize that our proposed idea to view the SGD updates as nonlinear time series can still be useful to address the non-stationarity and complex dependency structures. Developing a notion of local GMC property will be addressed in subsequent work. \n\n\n**3. I would be glad to see more validation of the theoretical result. The authors should provide some numerical experiments to illustrate their theoretical results.**\n\nThanks a lot for this suggestion. We fully agree. Since figures are not allowed in the rebuttal, we plan to add the results to the revision. Here, we would like to provide a detailed plan for the experiment. We plan to validate the moment convergence rate of SGD provided in Theorem 2, where we show that the SGD iterates $\\boldsymbol{\\beta}\\_k$ forget the initialization $\\boldsymbol{\\beta}\\_0$ exponentially fast and will converge at the rate $O(M\\_{s,q}\\sqrt{\\max\\\\{q,s\\\\}\\alpha})$. Specifically, we will generate i.i.d.\\ random samples $(y\\_k,\\mathbf{x}\\_k)$ from a linear regression model $y\\_k=\\mathbf{x}\\_k^{\\top}\\boldsymbol{\\beta}^* + \\epsilon\\_k$, where $\\epsilon\\_k$ are i.i.d.\\ standard Gaussian random variables and $\\mathbf{x}\\_k$ are multivariate standard Gaussian vectors. All our technical assumptions will be satisfied in this setting. We take $s=2$ and $q=2,$ different dimensions $d$ and different learning rates $\\alpha.$ In view of Lemma 7, we expect to see that the MSE scales with $\\sqrt{d\\alpha}$. We will also include the cases for the convergence in $\\ell^{\\infty}$-norm and $\\ell^{s}$-norms with $s>2$ for completeness."}, {"review_id": "f341G9Cffw", "reviewer": "Reviewer_sNN4", "summary": "This work provides statistical averaged and last-iterate guarantees for high dimensional stochastic gradient descent. The authors demonstrate a generalized moment contraction, leading to last-iterate convergence to a stationary distribution around the true parameters, and $q$-th moment convergence of the iterates. Of independent interest is a novel sharp Fuk-Nagaev inequality for bounding the distance in $L_{\\infty}$ norm between the estimate and true model parameters.", "questions": "Overall, the paper is well written and gives a series of guarantees to an important area at the intersection of high-dimensional statistics. \nI have a few questions concerning the asymptotic results:\n* Is there a fundamental difficulty derived from the high-dimensional regime that renders demonstrating strong asymptotic consistency of the parameters difficult? \n* Is it possible to show a central limit theorem for the iterates of the stochastic approximation process? \n* How strong is the $\\ell_s$ strong convexity assumption in relationship to the $\\ell_2$ strong convexity?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n* The paper is clearly written and technically sound, covering the settings of both last-iterate and averaged-iterate behavior with an extensive section in the appendix for the application of these methods to the important application of high-dimensional regression.\n* The techniques for demonstrating Geometric-Moment contraction are new, and more robust when compared to previous results in the literature, providing a bridge to $L_{\\infty}$ guarantees.\n* The Fuk-Nagaev concentration inequality is novel and has uses in many stochastic approximation settings. \n\nWeaknesses:\n* The asymptotic results largely focus on the convergence in moments rather than the stronger notions of convergence almost surely or in distribution.* \n* The connection between geometric moment contraction and convergence to the stationary distribution is not entirely clear.", "was_revised": true, "final_justification": "The authors provide a well-written and thorough treatment of the statistical properties of stochastic gradient descent in the high-dimensional regime.\n\nMy main concerns were about the strength of the geometric moment contraction result and its connection to asymptotic behavior of the iterates. In their rebuttal, the authors gave a detailed explanation showing that this condition ensures both convergence to a *stationary distribution* and *Gaussian approximation* for the iterates. They also clarified the novelty of extending these results to the high-dimensional setting.\n\nFor these reasons, I maintain my positive evaluation (5 – Accept).", "rebuttal": "We greatly appreciate your positive assessment of our technical innovations. Your constructive feedback has greatly contributed to enhancing the quality of our work. Please see our responses to your concerns and questions below.\n\n**1. The asymptotic results largely focus on the convergence in moments rather than the stronger notions of convergence almost surely or in distribution.**\n\nWe greatly appreciate your comment. Indeed, our first main theorem proves the geometric-moment contraction (GMC) of the SGD iterates (Theorem 1). However, we would like to emphasize that this GMC property further implies the convergence of the SGD iterates to a unique stationary distribution $\\pi_{\\alpha}$ as the iteration number $k$ grows (see below Eq. (6)) that is independent of the initialization. Related to your next comment, the key connection between the GMC and the convergence to the stationary distribution is based on the construction of \"backward iteration\" which was first introduced by Propp and Wilson (1996) and later extended to the iterated random function by Wu and Shao (2004). Please kindly refer to our reply to your next comment for details.\n\nActually, based on this GMC property, we can derive very fruitful (non)-asymptotic results beyond the moment convergence of the estimation error in Theorems 2 and 3. In Theorem 4, we provide a tail probability inequality, which facilitates the probabilistic guarantees of the high-dimensional SGD algorithms. Moreover, related to your Comment 4, the GMC property does imply a central limit theorem for the SGD iterates. Please see our reply to your Comment 4 for details.\n\nNote that convergence in probability implies that there exists a subsequence that converges almost surely. However, we admit that deriving almost sure convergence of stochastic approximation in the high-dimensional settings is difficult. It is also rarely investigated in the literature. \n\n**2. The connection between geometric moment contraction and convergence to the stationary distribution is not entirely clear.**\n\nWe sincerely apologize for this confusion. The main idea is to view the SGD recursion as an iterated random function and then use the idea \"backward iteration\" introduced by Propp and Wilson (1996) to find the limiting stationary distribution.\n\nSpecifically, we rewrite the SGD recursion into an iterated random function as follows\n\\begin{equation*}\n\\boldsymbol{\\beta}\\_k=\\boldsymbol{\\beta}\\_{k-1} - \\alpha \\nabla g(\\boldsymbol{\\beta}\\_{k-1},\\boldsymbol{\\xi}\\_k)=:f\\_{\\boldsymbol{\\xi}\\_k}(\\boldsymbol{\\beta}\\_{k-1}) = f\\_{\\boldsymbol{\\xi}\\_k}\\circ \\cdots\\circ f\\_{\\boldsymbol{\\xi}\\_1}(\\boldsymbol{\\beta}\\_0),\n\\end{equation*}\nfor $k=1,2,\\ldots$. One cannot directly find a limit for this forward iteration because by the Markov property, given the present position of the chain, the conditional distribution of the future does not depend on the past (see Diaconis and Freedman (1999) for the ergodicity of this forward iteration). As such, we define a backward iteration\n\\begin{equation*}\n\\mathbf{z}\\_k(\\boldsymbol{\\beta}\\_0) = \\mathbf{z}\\_{k-1}(f\\_{\\boldsymbol{\\xi}\\_k}(\\boldsymbol{\\beta})) = f\\_{\\boldsymbol{\\xi}\\_1}\\circ \\cdots\\circ f\\_{\\boldsymbol{\\xi}\\_k}(\\boldsymbol{\\beta}\\_0),\n\\end{equation*}\nfor $k=1,2,\\ldots$. By Theorem 2 in Wu and Shao (2004), we can show that the distribution of $\\mathbf{z}\\_k$ is the same as the one of $\\boldsymbol{\\beta}\\_k$, and there exists a unique random vector $\\mathbf{z}\\_{\\infty}\\in\\mathbb{R}^d$ that is independent of $\\boldsymbol{\\beta}\\_0$, such that for any $\\boldsymbol{\\beta}\\_0\\in\\mathbb{R}^d$, $\\mathbf{z}\\_k\\rightarrow\\mathbf{z}\\_{\\infty}$ almost surely as $k\\rightarrow\\infty$. Hence, one can show that $\\boldsymbol{\\beta}\\_k$ also converges to $\\mathbf{z}\\_{\\infty}$ in distribution. We will add this detailed explanation to our revision.\n\n**3. Is there a fundamental difficulty derived from the high-dimensional regime that renders demonstrating strong asymptotic consistency of the parameters difficult?**\n\nWe appreciate this insightful question! Indeed, a major challenge in establishing strong (non)-asymptotic consistency (e.g., in moment or in distribution) of SGD iterates in the high-dimensional regime lies in modeling both non-stationarity and dependencies across high-dimensional components. Traditional methods for constant learning-rate SGD typically establish convergence only in a probability measure (e.g., Wasserstein-2 distance in Dieleveut et al. (2020); Merad and Gaïffas (2023); Huo et al. (2023)), which cannot deliver refined non‑asymptotic control over high‑order moments or tail behavior, especially once $d$ grows large. This is because the constants in their theory depend on $d$ in an extremely complicated manner that are quite uneasy to work out.\n\nIn our work, we propose GMC with a clean form by adapting coupling techniques from high‑dimensional nonlinear time series to show that any two SGD paths contract in $\\ell^s$-norm, thereby enabling precise control of the $q$-th moment in general $\\ell^s$ ($\\ell^{\\infty}$) norms. As a key technique, we derive sharp high‑dimensional moment inequalities that carefully track how the dimension $d$ affects the range of learning rate $\\alpha$ and how it enters into the contraction speed. Moreover, our probabilistic guarantees in high dimensions are even more challenging, since we do not require light-tail assumptions (e.g. sub-Gaussian) and we aim to accurately measure coordinate‑wise dependencies. To address these challenges, we develop a new Fuk–Nagaev–type inequality using functional dependence measures to control the tails of the Ruppert–Polyak average of SGD.\n\n**4. Is it possible to show a central limit theorem for the iterates of the stochastic approximation process?**\n\nThanks a lot for your great question. Yes, based on the GMC property, we can provide the central limit theorem of the SGD iterates, as well as a quenched version which holds for any arbitrarily fixed initialization. Even better than the asymptotic normality, we can quantify the rate of the Gaussian approximation as follows.\n\n**Theorem (High-dimensional sequential Gaussian approximation).** *Consider $d$-dimensional SGD iterates $\\boldsymbol{\\beta}\\_k$ for $T$ iterations. Suppose that our Assumption 2 (stochastic Lipschitz continuity) holds for some $q>2$, the dimension $d\\le cT$, for some constant $c>0$. Then, on a potentially different probability space, there exist random vectors $\\\\{\\tilde{\\boldsymbol{\\beta}}\\_k\\\\}\\_{k=1}^T\\overset{\\mathcal{D}}{=}\\\\{\\boldsymbol{\\beta}\\_k\\\\}\\_{k=1}^T$ and independent Gaussian random vectors $\\\\{\\tilde{\\mathbf{y}}\\_k\\\\}\\_{k=1}^n$ with mean zero and covariance matrix* \n\\begin{equation*}\n \\Xi=\\sum\\_{k=-\\infty}^{\\infty}\\mathrm{Cov}(\\boldsymbol{\\beta}\\_0,\\boldsymbol{\\beta}\\_k)\n\\end{equation*}\n*such that*\n\\begin{equation*}\n\\Big(\\mathbb{E}\\max\\_{k\\le T}\\Big|\\frac{1}{\\sqrt{k}}\\sum\\_{i=1}^k\\big[(\\tilde{\\boldsymbol{\\beta}}\\_i -\\boldsymbol{\\beta}^{\\diamond}) -\\tilde{\\mathbf{y}}\\_i\\big]\\Big|_2^2\\Big)^{1/2} \\le c'M\\_{2,q}\\sqrt{d\\log(T)}\\Big(\\frac d T\\Big)^{\\frac{q-2}{6q-4}},\n\\end{equation*}\n*where $c'$ is a universal constant that only depends on $c$ and the moment index $q$, $\\boldsymbol{\\beta}^{\\diamond}=\\lim\\_{k\\rightarrow\\infty}\\mathbb{E}[\\boldsymbol{\\beta}\\_k]$, and $M\\_{2,q}$ is defined in our Assumption 2.*\n\nThe key idea to prove this Gaussian approximation is to apply the recent work by Mies and Steland (2023), in particular their Theorem 3.1. Using the GMC property of the SGD iterates, one can verify the conditions to apply this result. Ideally, when the moment index $q\\rightarrow\\infty$, the Gaussian approximation rate approaches $O(\\sqrt{\\log(T)}(d^4/T)^{1/6})$. Thus, to obtain a nontrivial bound for Gaussian approximation within $T$ iterations, we can allow dimension dependence $d=o(T^{1/4-\\zeta})$ for some $\\zeta>0$.\n\n**5. How strong is the $\\ell_s$ strong convexity assumption in relationship to $\\ell_2$ the strong convexity?**\n\nThanks so much for another great question. First, we would like to clarify that although we suggest large $s$ with $s\\approx\\log(d)$ to make $\\ell^s$-norm approximate $\\ell^{\\infty}$-norm, all of our derived theory also works for small $s$, including $s=2$ as a special case. By letting $s=2$, our Assumption 1 reduces to the standard strong convexity for $\\ell^2$-norms, and the moment convergence in Theorem 2 reduces to $(\\mathbb{E}|\\boldsymbol{\\beta}\\_k-\\boldsymbol{\\beta}^*|\\_2^2)^{1/2}=O(M\\_{2,q}\\sqrt{\\max\\\\{q,2\\\\}\\alpha}+r\\_{\\alpha,2,q}^k|\\boldsymbol{\\beta}_0-\\boldsymbol{\\beta}\\_0^{\\circ}|\\_2)$, where the dependency on the dimension $d$ will be reflected by $M\\_{2,q}$, $\\alpha$ and $L\\_{2,q}$ included in the contraction speed $r\\_{\\alpha,2,q}$. The moment convergence for ASGD in Theorem 3 and the tail probability inequality in Theorem 4 will follow similarly. \n\nFor the case $s>2$, please kindly refer to Lemma 5 in the Appendix where we illustrate the additional requirement posted by the $\\ell^s$ strong convexity assumption. We would like to provide a more detailed explanation here and will add it to our revision. In fact, there is no apparent relationship between these two conditions in general cases since different norms are involved. We therefore study the linear regression as an example. Recall that for the linear regression setting in Section 8.2, we define $\\lambda\\_{\\min}^{(s)}=\\inf\\_{\\|\\mathbf{v}\\|\\_s=1}\\langle\\mathbf{v}^{s-1},\\Sigma\\mathbf{v}\\rangle$. When $s=2$, $\\lambda\\_{\\min}^{(2)}=\\lambda\\_{\\min}(\\Sigma)\\ge \\lambda\\_{\\min}^{(s)} \\ge\\min\\_i(\\Sigma\\_{ii}-\\sum\\_{j\\neq i}|\\Sigma\\_{ij}|)$. The rightmost \"Gershgorin gap\" is a universal lower bound for every $s$. The lower bound is non-trivial if $\\Sigma$ is sufficiently diagonally dominant."}, {"review_id": "oVrlyJ10KV", "reviewer": "Reviewer_BCC1", "summary": "This paper presents statistical guarantees for SGD in smooth and strongly convex setting for SGD and averaged SGD (ASGD). More precisely, the authors are interested in proving moment convergence bounds and assume strong convexity and expected smoothness in $\\ell^s$ and $L^q$ norms, in a sense that is made precise in the paper. Under these assumptions, the authors prove results on the convergnence of SGD to its stationary distribution as well as moment convergence of SGD, in both cases under additional restrictions on the learning rate. Moment convergence bounds are also obtained for ASGD. In the case of ASGD, high probability convergence bounds are also obtained, through the derivation of a so-called Fuk-Nagaev type inequality. The authors also analyze the dependence of the learning rate constraints on the parameters of the problem (in particular the dimension) and provide sketches of proofs of their main results. The proofs rely in particular on the adaptation of a coupling technique to online SGD.", "questions": "- Your theoretical results rely on the assumption that $s$ is even. It is clear from the proof that this assumption simplifies some computations, however, it does not feel very intuitive. Could you add a discussion about potentially removing this condition and how critical it is?\n- Line 123, you mention that using constant learning rates prevail in practical scenarios, but a large number of works seem to use learning rate schedules to train modern models. Can you be more precise about when constant learning rates are used? Moreover, how essential is the constant learning rate assumption in your work? Could all your results be easily generalized the non-constant learning rates?\n- Could you provide more justification as to why it is essential to bound the quantities $\\Vert |\\beta_k - \\beta^\\star|_s \\Vert q$? Why is it necessary to have such bounds for all $s$ and $q$?\n- As I understand, Lemma is not used in the proofs, is it useful to present it in the main text? Moving it to the appendix could allow for more space for qualitative discussions of the results.", "limitations": "Some limitations are discussed by the authors, in particular the fact that their analysis apply only in smooth and strongly-convex settings.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n- The sketches of proofs provide a good idea of how the proof work without harming the readability of the paper.\n- Some of the bounds extend known results in the mean square error case.\n- The introduction of coupling technique is a powerful research direction, it is possible that some elements introduced in the paper can be applied in other settings.\n- New high-probability bounds (Nagaev type inequality) are derived for ASGD\n\n**Weaknesses:**\n\nHere are some potential weaknesses, please correct me if I am wrong.\n\n- About assumption 1. The notation $\\beta^s$ is not clear when $\\beta \\in R ^d$. We can see from the proof that the product is meant element-wise but it should be mentioned. Because of this element-wise product, Assumption 1 should be discussed a bit more, especially whether it has been used in other works. Additionally, the proof of Lemma 4 looks a bit suspicious. Indeed, the first integral features $\\int \\langle \\beta, \\dots$, but a few lines later it is transformed into $\\int \\langle \\beta^{s-1} ,\\dots$ without justification.\n- About Assumption 2. It is mention that the constants $L_{s,q}$ and $M_{s,q}$ may depend on $d$ through their dependence on $s$. However, it seems to me that they also have a intrinsic dependence on $d$ that should be discussed. For instance, is there a link between $L_{s,q}$ and $L_{2,q}$ in the worst case?\n- In the introduction, the paper is partially justified by the fact that SGD iterates are not stationary when the learning rate is large, but we see in Section 5 that the assumption impose at least $\\alpha$ to be of order $1 / (d^2 \\log d)$, which is small in high dimensional settings. In that regard, can we say that the paper apply to learge learning rates.  \n- The results only rely on smoothness and strong convexity assumptions. Moreover, these two assumptions are formulated for $\\ell^s$ norms, so they are different from the standard ones.\n\nI am not familiar enough with this literature to fully assess the technical novelty of the results.\n\n**Other remarks**\n\n- In the introduction, the assumption under which the results hold should be mentioned alongside the informal presentation of the result, to help the readability.\n- In some sections (eg, related works), the reference formatting and the high number of citations make the paragraphs hard to read.\n- The acronym GMC is used before being defined.\n- Line 264, the proof is refered to Section 2 in the appendix but it should be Section 8.4.", "was_revised": true, "final_justification": "The paper is well-written and present new results regarding statistical guarantees for SGD. The main analysis is based on a $s$-convexity assumptions.\n\nDuring the review process, a mistake was found in the proof of lemma 4, showing that the $s$-convexity alone does not ensure the existence of a global minimum. \nAfter several (and very positive) discussions with the authors and other reviewers, this problem was fixed.\n\nI am now confident that this paper is above the bar of acceptance, after fixing these issues.\n\nFor this reason, I have raised my initial score.", "rebuttal": "Thank you so much for your detailed critique and for highlighting opportunities to improve our presentation. Your insights have made the manuscript clearer and more accessible. Please see below the detailed responses to your concerns.\n\n**1. About assumption 1. The notation $\\beta^s$ is not clear when $\\beta\\in\\mathbb{R}^d$. We can see from the proof that the product is meant element-wise but it should be mentioned. Because of this element-wise product, Assumption 1 should be discussed a bit more, especially whether it has been used in other works. Additionally, the proof of Lemma 4 looks a bit suspicious. Indeed, the first integral features $\\int\\langle\\beta,\\ldots$, but a few lines later it is transformed into $\\int\\langle\\beta^{s-1},\\ldots$ without justification.**\n\nWe sincerely apologize for the confusion. We have changed the notation $\\boldsymbol{\\beta}^s$ to $\\boldsymbol{\\beta}^{\\odot s}$ to denote element-wise product. The confusion in Lemma 4 proof is also fixed. We indeed need to additionally assume Assumption 1 to hold for $s=2$ to ensure the existence of global optimum. In the revision, we will fix this. In fact, there is no apparent relationship between the $\\ell^s$ and $\\ell^2$-type strong convexity assumptions in general cases, since different norms are involved. We therefore study the linear regression as an example in Section 8.2 to compare these two assumptions.\n\n**2. About Assumption 2. It is mention that the constants $L\\_{s,q}$ and $M\\_{s,q}$ may depend on $d$ through their dependence on $s$. However, it seems to me that they also have an intrinsic dependence on $d$ that should be discussed. For instance, is there a link between $L\\_{s,q}$ and $L\\_{2,q}$ in the worst case?**\n\nThis is indeed a very good observation. We strongly agree that both $L\\_{s,q}$ and $M\\_{s,q}$ have an intrinsic dependence on $d$, which we have carefully discussed in Lemmas 6 and 7 in the Appendix, respectively. We apologize for not explicitly pointing to these two lemmas below Assumption 2, which shall be added in the revision. As we can see from the results of Lemma 6, $L\\_{s,q}$ differs from $L\\_{2,q}$ up to logarithmic factors $\\sqrt{\\log(d)}$ and $\\log(d)$ when the noises are sub-Gaussian and sub-exponential, respectively. When the noise only has finite $q$-th moment, then $L\\_{s,q}$ differs from $L\\_{2,q}$ by a factor $d^{1/(2q)}$. We would like to emphasize that all the theory in this work includes $s=2$ as a special case. We have included a detailed discussion regarding the relationship between $\\ell^s$ and $\\ell^2$ norms in our reply to your Comment 4.\n\n**3. In the introduction, the paper is partially justified by the fact that SGD iterates are not stationary when the learning rate is large, but we see in Section 5 that the assumption impose at least $\\alpha$ to be of order $1/(d^2\\log d)$, which is small in high dimensional settings. In that regard, can we say that the paper apply to large learning rates.**\n\nThis is in fact a typo. In the introduction, we meant a constant learning rate that does not decay in the number of iterations $k$. Indeed, convergence requires $\\alpha$ to decay with the dimension of the problem. We do agree that in a high-dimensional setting one can call the learning rate small. \n\n**4. The results only rely on smoothness and strong convexity assumptions. Moreover, these two assumptions are formulated for $\\ell^s$ norms, so they are different from the standard ones.**\n\nWe greatly appreciate your comment on our assumptions. Indeed, our results only rely on smoothness and strong convexity assumptions. This is actually why our proposed geometric-moment contraction (GMC) is very useful in SGD algorithms, which provides convergence to the stationary distribution without any restriction on the initialization, or any limitations on the data distributions (e.g., we do not require sub-Gaussian gradients that is frequently assumed in literature), except a mild condition on the finite $q$-th moment of the stochastic gradient at the global optimum for some $q \\geq 2$. This GMC property can lead to fruitful (non)-asymptotic convergence behaviors of SGD iterates, including the in-expectation and in-probability convergence. \n\nRegarding the two assumptions in $\\ell^s$-norm, we would like to clarify that although we suggest large $s$ with $s\\approx\\log(d)$ to make $\\ell^s$-norm approximate $\\ell^{\\infty}$-norm, all of our derived theory also works for small $s$, including $s=2$ as a special case. For $s=2$, Assumptions 1 and 2 reduce to the standard strong convexity and stochastic Lipschitz continuity for $\\ell^2$-norms, and the moment convergence in Theorem 2 reduces to $(\\mathbb{E}|\\boldsymbol{\\beta}\\_k-\\boldsymbol{\\beta}^*|\\_2^2)^{1/2}=O(M\\_{2,q}\\sqrt{\\max\\\\{q,2\\\\}\\alpha}+r\\_{\\alpha,2,q}^k|\\boldsymbol{\\beta}\\_0-\\boldsymbol{\\beta}\\_0^{\\circ}|\\_2)$, where the dependency on the dimension $d$ will be reflected by $M\\_{2,q}$, $\\alpha$ and $L\\_{2,q}$ included in the contraction speed $r\\_{\\alpha,2,q}$. Moment convergence for ASGD in Theorem 3 and tail probability inequality in Theorem 4 will follow similarly. When $s>2$, indeed our assumptions are different from the standard ones. Such condition is required for a general $s$ since our primary goal is to derive high-dimensional convergence in $\\ell^{\\infty}$-norm, which can be approximated by $\\ell^s$-norm with $s\\approx\\log(d)$.\n\n**5. Your theoretical results rely on the assumption that $s$ is even. It is clear from the proof that this assumption simplifies some computations, however, it does not feel very intuitive. Could you add a discussion about potentially removing this condition and how critical it is?** \n\nWe sincerely appreciate your feedback. Indeed, assuming $s$ is an even integer is just a convenient way to define the map \n\n\\begin{equation}\n\\mathbf{v}\\mapsto\\mathbf{v}^{s-1}=(|v_1|^{s-2}v_1,\\ldots,|v_d|^{s-2}v_d),\n\\end{equation}\n\nwithout worrying about fractional powers of negative numbers. Without this assumption, our result will be unreadable and the conditions will be messy. In fact, the most frequently adopted $s$ is 2 and $s\\_d$ in Eq. (7) to measure the convergence of algorithms, that is, $\\ell^2$ and $\\ell^{\\infty}$ norms. As $s\\rightarrow\\infty$ to approximate $\\ell^{\\infty}$ norms, $s$ and $s+1$ will not differ too much. We will add this discussion in the revision.\n\n**6. Line 123, you mention that using constant learning rates prevail in practical scenarios, but a large number of works seem to use learning rate schedules to train modern models. Can you be more precise about when constant learning rates are used? Moreover, how essential is the constant learning rate assumption in your work? Could all your results be easily generalized the non-constant learning rates?** \n\nThanks so much for your questions on the learning rates. We do agree that learning rate schedules are widely used. Constant learning rates are among the most effective schedules; see for example, Krizhevsky et al. (2012), Iiduka (2022) and the tutorial of PyTorch SGD \"torch.optim\". More precisely, when one needs to fix the initialization without any prior knowledge (e.g., the initial point could be very far from the optimum), a constant learning rate can speed up the convergence of the algorithm to a stationary stage. See for example, the very recent work by Defazio et al. (2024) proposed optimal learning schedules with learning rate warm-up and rapid learning rate annealing near the end of training. A constant learning rate can be used in the warm-up stage, where our proposed theory applies. We will cite these references in the revision. Indeed, our theory can be generalized to non-constant cases such as linear decaying learning rates, which however would require heavy machinery, and we will consider it as a potential future direction.\n\n**7. Could you provide more justification as to why it is essential to bound the quantities $\\\\||\\boldsymbol{\\beta}\\_k-\\boldsymbol{\\beta}^*|_s\\\\|\\_q$? Why is it necessary to have such bounds for all $s$ and $q$?** \n\nWe are truly sorry for this confusion. In fact, we only need to bound the quantity $\\\\||\\boldsymbol{\\beta}\\_k-\\boldsymbol{\\beta}^*|\\_s\\\\|\\_q$ for some $s$ and $q$ that are of interest. We allow for a large range of possible $s, q$ as indicated in our theorems. We have revised the statement in the revision to avoid confusion.\n\n**8. As I understand, Lemma is not used in the proofs, is it useful to present it in the main text? Moving it to the appendix could allow for more space for qualitative discussions of the results.** \n\nThank you very much for your suggestion. We assume you refer to Lemma 3. Indeed, Lemma 3 is a consequence of the moment inequality in Lemma 2 and is of independent interest. We will move it to the Appendix in the revised version."}, {"review_id": "QCViESANcK", "reviewer": "Reviewer_WFcH", "summary": "The paper derives new convergence results for SGD and ASGD in high-dimensional settings with constant learning rate. \n\nThe key theory of the paper is to derive generalized moment convergence of (A)SGD and apply the coupling technique in nonlinear time series analysis to show the high probability concentration bound of ASGD.", "questions": "The only question I have is whether the convergence of ASGD in Theorem 3 and the high-probability concentration bound in Theorem 4 can be extended to $\\ell^s$ norms. It would be helpful if the authors would remark on the technical reasons why this analysis is not provided.", "limitations": "Again, I generally like the presentation of this work and I am not aware of any limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strength:**\n\nThe paper is well written and with clear technical contributions in understanding the convergence of SGD and ASGD in high dimensional settings. \n\nTheorem 1 shows the convergence of SGD to a stationary distribution. In particular, the analysis is based on proving that for sufficiently small constant learning rates, the initial distance between two SGD sequences decreases exponentially fast. This is, to my knowledge, a new technique, with which the authors extend the results in previous works (e.g. [Li et al. 2024b]) to high-dimensional settings and general norms. \n\nTheorem 2 and 3 show the convergence of (A)SGD in general moments. Specifically, Theorem 2 shows the last-iterate convergence of SGD in $\\ell^s$ norm; Theorem 3 shows the convergence of ASGD in $\\ell^\\infty$ norm. This recovers some best known result (e.g., [Wainwright 2019]) as a special case. \n\nTheorem 4 derives a Fuk-Nagaev-type inequality of ASGD for high-probability concentration bound in the infinity norm. This leads to a sharp high-probability bound on the infinity norm in certain regimes of the gradient noise.  \n\nThe results are presented in a clean and self-contained way. The proof sketch in section 6 highlights the technical contributions and is very helpful in understanding the techniques. \n\nI have also checked the analysis and found the proofs to be correct.\n\n**Weakness:**\n\nI appreciate the theoretical results, presentation, and proof techniques in this paper. I did not spot any particular weakness.\n\n\n**Updated review:**\nThank for the author’s response! I find these results reasonable, and I will keep my score unchanged.", "was_revised": true, "final_justification": "After reading the author’s response, I find these results reasonable, and I will keep my score unchanged.", "rebuttal": "We are extremely grateful for your strong endorsement and careful review of our proofs. Your support has been invaluable in framing the impact and future directions of our analysis. Please see below our response to your question on the $\\ell^s$-norms.\n\n**The only question I have is whether the convergence of ASGD in Theorem 3 and the high-probability concentration bound in Theorem 4 can be extended to $\\ell^s$ norms. It would be helpful if the authors would remark on the technical reasons why this analysis is not provided.**\n\n**Answer:** Thank you so much again for this great question! Indeed, all of our derived theory, including the convergence of ASGD in Theorem 3 and the high-probability concentration bound in Theorem 4, work for general $\\ell^s$-norms with $s\\ge2$. In fact, we did not provide them in the current version due to the concern of space. According to your suggestion, we will add these results to the Appendix in the revision for the completeness of our work. We would like to summarize them over here.\n\n**Theorem 3 (Convergence of ASGD in $\\ell^s$-norm).** *Consider the ASGD sequence $\\\\{\\bar{\\boldsymbol{\\beta}}\\_k\\\\}\\_{k \\geq 1}$. Suppose that Assumptions 1 and 2 hold with some $q \\geq 2$ and even integer $s \\geq 2$, the conditions in Theorem 7 hold and the learning rate satisfies $\\alpha \\in (0, \\alpha\\_{s\\_d, q})$ with $\\alpha\\_{s\\_d, q}$ defined in (5). For any $k \\geq 1$ and some universal constants $C\\_1,C\\_2,C\\_3 > 0$,*\n\n\\begin{equation}\n    \\\\||\\bar{\\boldsymbol{\\beta}}\\_k - \\boldsymbol{\\beta}^*|\\_s\\\\|\\_q  \\leq C\\_1 \\{\\underbrace{\\sqrt{\\frac{c\\_qs}{k}}M\\_{s,q}(L\\_{s,q}\\sqrt{\\alpha\\max\\\\{q,s\\\\}} + 1)}\\_{\\text{\\small{stochastic variance}}}\\}  +  C\\_2\\{\\underbrace{\\frac{1}{k(1-r\\_{\\alpha,s,q})}\\\\||\\boldsymbol{\\beta}\\_0-\\boldsymbol{\\beta}\\_0^{\\circ}|\\_{\\infty}\\\\|\\_q}\\_{\\text{\\small{initialization bias}}}\\} + C\\_3\\{\\underbrace{M\\_{s,q}^2\\max\\\\{q,s\\\\}\\alpha d^{\\frac{q}{q-1}\\cdot(1-\\frac{2}{s})}}\\_{\\text{\\small{bias of constant learning rate}}}\\}.\n\\end{equation}\n\n**Theorem 4 (Fuk-Nagaev inequality in $\\ell^s$-norm).** *Under the conditions of Theorem 3*, for any $z > 0$, we have* \n\n\\begin{equation}\n\\mathbb{P} (|\\bar{\\boldsymbol{\\beta}}\\_{k} - \\boldsymbol{\\beta}^{*}|\\_s > z) \\lesssim \\frac{\\\\||\\boldsymbol{\\beta}\\_{0} - \\boldsymbol{\\beta}\\_{0}^{\\circ}|\\_s\\\\|\\_q^{q}}{(k\\alpha z)^{q}} + \\frac{(\\log d)^{\\frac{3q}{2}} (\\log k)^{1 + 2 q} M\\_{s, q}^{q}}{z^{q} k^{q - 1} \\alpha^{q/2 - 1}} + \\exp\\left(- \\frac{C k z^{2} \\alpha^{1 - 2/q}}{M\\_{s, q}^{2} \\log d}\\right), \n\\end{equation}\n\n*where the constants in $\\lesssim$ are independent of $k,d,s$ and $\\alpha$.*\n\n\nNotably, since the geometric-moment contraction (GMC) (Theorem 1) is developed for general $\\ell^s$-norms, all the subsequent analysis based on the GMC property is also derived for general $s$. Considering our primary interest is to provide convergence in $\\ell^{\\infty}$-norm by choosing $s=s_d\\approx\\log(d)$ such that $\\ell^{s\\_d}$-norm approximate $\\ell^{\\infty}$-norm, we will keep the $\\ell^{\\infty}$-type results in the main text and add Theorems 3* and 4* to the Appendix according to your suggestion."}]

Author rebuttal:

Meta-review: This paper provides rigorous statistical guarantees for constant learning-rate SGD and its averaged variant in high-dimensional regimes by introducing a novel geometric-moment contraction (GMC) framework. Reviewers lauded the paper's technical strength, particularly the new GMC technique adapted from high-dimensional time series and the derivation of a sharp inequality for high-probability bounds. Noted weaknesses include an insufficient comparison to related literature, which in my view still persists after rebuttal, and questions about the strong convexity assumption, including a flawed proof for the existence of a global minimum that was resolved during discussion. Altogether, the novel techniques and strong theoretical contributions are a constructive addition to the field. Therefore, this paper is recommended for acceptance.
Decision: Accept (poster)