Risk Bounds of Accelerated SGD for Overparameterized Linear Regression
Authors: Xuheng Li
Yihe Deng
Jingfeng Wu
Dongruo Zhou
Quanquan Gu
Venue: ICLR 2024 poster (2024)
Keywords: Accelerated stochastic gradient descent
excess risk
linear regression
overparameterization
Primary area: learning theory

Abstract: Accelerated stochastic gradient descent (ASGD) is a workhorse in deep learning and often achieves better generalization performance than SGD. However, existing optimization theory can only explain the faster convergence of ASGD, but cannot explain its better generalization. In this paper, we study the generalization of ASGD for overparameterized linear regression, which is possibly the simplest setting of learning with overparameterization. We establish an instance-dependent excess risk bound for ASGD within each eigen-subspace of the data covariance matrix. Our analysis shows that (i) ASGD outperforms SGD in the subspace of small eigenvalues, exhibiting a faster rate of exponential decay for bias error, while in the subspace of large eigenvalues, its bias error decays slower than SGD; and (ii) the variance error of ASGD is always larger than that of SGD. Our result suggests that ASGD can outperform SGD when the difference between the initialization and the true weight vector is mostly confined to the subspace of small eigenvalues. Additionally, when our analysis is specialized to linear regression in the strongly convex setting, it yields a tighter bound for bias error than the best-known result.

Published as a conference paper at ICLR 2024
RISK BOUNDS OF ACCELERATED SGD FOR OVERPA- RAMETERIZED LINEAR REGRESSION
Wu², Dongruo Zhou', Quanquan Gu² 'Department of Computer Science. University of California, Los Angeles, CA 90095, USA Simons Institute, University of California, Berkeley, CA 94720, USA *Department of Computer Science, Indiana University Bloomington, IN 47408, USA xuheng. 1i@cs. cula edu,, yihedeng@cs. www.ucllacc...o edu, uuu)f@berkeley. edu, dz13@iu. edu, qquêcs ucla. edu
Xuheng Li", Yihe
ABSTRACT
Accelerated stochastic gradient descent (ASGD) workhorse deep learn- ing and often achieves better generalization performance than SGD. However, existing optimization theory can only explain the faster convergence of ASGD, but cannot explain its better generalization. In this paper, study the general- ization of ASGD for overparameterized linear regression, which is possibly the simplest setting of learning with overparameterization. We establish an instance- dependent excess risk bound for ASGD within each eigen-subspace of the data covariance matrix. Our analysis shows that (i) ASGD outperforms SGD in the subspace of small eigenvalues, exhibiting a faster rate of exponential decay for bias error, while in the subspace of large eigenvalues, its bias error decays slower than SGD; and (ii) the variance error of ASGD is always larger than that of SGD, Our result suggests that ASGD can outperform SGD when the difference between the initialization and the true weight vector is mostly confined to the subspace of small eigenvalues. Additionally, when our analysis specialized to linear regres- sion in the strongly convex setting, it yields tighter bound for bias error than the best-known result.
INTRODUCTION
Momentum (Nesterov 1983) is an important technique in optimization. In the context of convex and smooth optimization, Nesterov's 's momentum (accelerated gradient descent (AGD)) achieves the min- imax optimal convergence rate [Nesterov] 2014) and provably accelerates the vanilla GD method. Recent work by Liu & Belkin 2018) shows that stochastic gradient descent (SGD) can also be accelerated by momentum in the overparameterized setting. However, the effect of momentum on the generalization performance is less studied. It has been empirically shown that ASGD does not always outperform SGD (Wang et al. 2023). but there has been little theoretical work justifying this observation. Notable exceptions are Jain et al. (2018) and Varre Flammarion (2022) which provide excess risk bounds for accelerated SGD (ASGD) (a.k.a,, SGD with momentum) for least squares problems in the strongly convex (Jain et al. 2018) and convex settings (Varre Flammar- ion 2022). respectively. However, both of their results are limited to the classical, finiteddimensional regime, and cannot be applied when the number of parameters exceeds the number of samples. On the other hand, recent line of work completely characterizes the excess risk of SGD for least squares, even in the overparameterized regime (Dieuleveut & Bach 2015 Défossez & Bach 2015) Jain et al. 2017b Berthier et al.) 2020: Zou et al.] 202 Wu al. 2022). In particular, Zou et al. (2021b) Wu et al. (2022) provide finite-sample and dimension-free excess risk bounds for SGD that are sharp for each least squares instance. Given these results, it becomes imperative to thor- oughly investigate whether the inclusion of momentum proves beneficial in terms of generalization, particularly in the context of least squares problems.
Contributions. In this paper, we tackle the question by considering ASGD for (overparameter- ized) linear regression problems and comparing its performance with SGD.
Our main result provides an instance-dependee plied in the overparameterized regime. Similar to the bounds for SGD in Zou et al. (2021b); Wu et al. (2022), our bound for ASGD is independent of the ambient dimension and compre- hensively depends the spectrum of the data covariance matrix. When applied to the classical,
excess risk bound for ASGD that can be ap-

---

Published as a conference paper at ICLR 2024
strongly-convex regime, our results recover the excess risk upper bounds in Jain et al. (2018), with significant improvements on the coefficient of the bias error
Based on the excess risk bounds, we then compare the excess risk of ASGD and SGD. We find that the variance enror of ASGD is always no smaller than that of SGD. Moreover, the bias error of ASGD is smaller than that of SGD along the small eigenvalue directions, but is larger than that of SGD along the large eigenvalue directions, with respect to the spectrum of the data covariance matrix. Thus momentum can help with generalization only if the main signals are aligned with small eigenvalue directions of the data covariance matrix and if the noise is small.
From a technical perspective, we extend the analysis of the stationary covariance matrix in Jain et al. (2018) to the overparameterized setting, where we remove all dimension deeeedddedd factors with fine-grained analysis of the ASGD iterates. Our techniques might be of independent interest for analyzing ASGD in other settings.
Notation. In this paper, scalars are denoted by non-boldface letters. Vectors and matrices are denoted by lower-case and upper-case boldface letters, respectively. Denote linear operatons on matrices by upper-case calligraphic letters. Denote the inner product of vectors by (u, v). For a vector v, denote its j-th entry as (v)z: For matrix M, denote its ij-entry (M) For PSD matrix M, define ||u|| M = T Mu. Denote the 2-norm of vector V as |v|l2 = VV Denote the inner product of matrices A, B E R2dx2d as (A, = Σig=1 (A) ( kg. The Kronecker product of matrices is denoted by @. The operation of a linear matrix operator on a matrix is denoted by o.
2 RELATED WORK
The generalization performances of SGD and ASGD applied to underparameterrize linear regres- sion have been studied in a line of works, based on the technique of bias variance decomposition. It shown that for SGD with iterate averaging from the beginning, bias error has a convergence rate of O11/N²) and variance has a convergence rate of OddNN) where N is the number of calls of the stochastic oracle and d is the model dimension (Défossez & Bach 2015 Diculeveut et al. 2017 Jain et al. 2017a). If the eigenvalue of the data covariance matrix is bounded away from zero, then the convergence rate of the bias error can be further improved with additional exponential shrinkage by taking tail averaging of the iterates (Jain et al. 2017b).
For ASGD applied to linear regression, there are two cases: one with the assumption that the eigen- value spectrum of the data covariance matrix bounded away from zero (strongly convex) and the other without such assumption (general convex). For strongly convex linear regression, JJiin et al. (2018) show an accelerated convergence rate for the bias error of ASGD with constant stepsize and tail averaging, compared to that of tail-averaged SGD in Jain et al. (2077)). We extend the use of linear operators and the techniques for bounding the operator spectrum in Jain et al. (2018).
Recently, the generalization of ASGD applied to general convex linear regression is studied by Varre & Flammarion| 2022). Their result shows the acceleration of ASGD with time-varying parameters and weighted iterate averaging, especially for large N. The case of general convex linear regression is closer to the overparameterized setting where fast-decaying eigenspectrum is of special interest. However, their result is not applicable to the overparameterizee linear regression because of the dimensionality dependence. Additionally, their result does not reveal the exponential bias decay of ASGD with constant stepsize.
The generalization performance of overparameterized linear regression has been studied by a line of works (Bartlett et al.] 20200] Tsigler& & Bartlett 2020). For SGD applied to overparameterized linear regression, Zou et al. (02 replace the model dimensionality d with the effective dimension defined in terms of the eigenspectrum. This work manages to deal with any data covariance matrix, while prior works require certain assumptions (Dieuleveut & Bach, 2015). Wu et al. (2022) show similar result for the last iterate of SGD with exponentially decaying stepsize.
PRELIMINARIES
3.1
LINEAR REGRESSION AND ASGD
The goal of linear regression is to minimize the following risk:
Ll (w) == 1/2- Bxxy) [(V - -w, x)]
Our excess risk hound contains an extra term, which can be removed by fine-grained analysis used by Jain et al. (2018) in the classical regime.
2

---

Published as a conference paper at ICLR 2024
where x is an imput feature vector belonging to Hilbert space (denoted by N, which could be either d-dimensional for a finite d. or countably infinite dimensional), y E R is the response, w E H. is the weight vector to be optimized, and D is underlying unknown distribution of the data. We consider the ASGD algorithm with tail averaging. In detail, in the 1-th iteration, a sample (Xt, 8c) D is observed. Then the stochastic gradient calculated by
( (y: (w,x))xx
(3.1)
We follow the classical ASGD scheme (Nesterov 2014), which maintains three sequences w., Ve and uy Let N be the number of samples observed, then for any 1 N, the update rules of We, Ve, Un are as follows.
u -- 1+ a)v-)
(3.2)
W. = u111 - -OVL(u-));
(3.3)
V, Bu,-1
8)v--1 V
(3.4)
where a, 1,B,,, 7, 0 are hyperparameters. The V, sequence is initialized at Wo E H. We remark that ASGD reduces stochastic heavy ball (SHB, PPllyak| (Plyk (1964)) when 8 = 0, directly applied to SHB by setting = (see Appendix C for details). We also remark that ASGD reduces SGD when 5 7-
results be
In this work, following Jain et al. (018)) and Zou et al. (2021b) we consider ASGD with tail aver- aging. The tail-averaged final output is W W == N Di N-
W.. With certain assumptions, L(w) admits a unique global optimum denoted by w == argmin L(w). We focus on the overpa- rameterized setting, where d >>>>> N (or possibly countably infinite).
Define the centered ASGD iterate as v): == W: w"
Denote the noise in each sample as ét =
u,
y/ (w", xx). By 3.I. the stochastic gradient at u can be expressed as
(u,-) 1) = (f + (w", xx) (u xx) )x = x (u:-1 - -w") - 6xx,
(3.5)
By substituting 3.5 into 3.3 and 3.4) and eliminating using 3.2 we have
n = A + Se: where A, =
0
I- 6
5 exxe
-cI
(1+c)
xx,x
q ExXx
and c = a(1 - 3), aδ + (1 a)7, Denote the expectation of A,
I- A = -a [I+cJI-gH]
where H = Ex [xx] is the second-order moment matrix of the distribution D, which is also the Hessian of I(w). Let the eigen-decompossition of the Hessian be H - A.v.y, where (x:) are the eigenvalues of H sorted in descending order with v.'s being the corresponding eigenvectors. Similar to Jain et al. (2018). we assume that H is diagonal, then A is block diagonal O 1- 5A;
In this work, we are particularly interested in analyzing the eigenvalues of A,, since the spectral norm of A; determines the decay rate of the bias error in the subspace of As.
with each block being A; - 1 - qA,
3.2 ASSUMPTIONS
We then introduce assumptions required in our analysis, following those Zou et al. (202bb) Wu al. (2022). Our first assumption regularizes the moments of the data distribution.
Assumption 3.1 (Regularity conditions). The second moment H exists, and tr(H) is finite. H strictly positive definite, i.e., H > O. Thus, L(w) admits a unique global optimum w". The second-order moment of labels Ely?) I is also finite. Let M denote the fourth moment of x:
M = E(x,y)=D(x x x x x].
Then M exists and is finite.
Our second assumption is proposition of the fourth moment of x, viewed as a linear operator M on PSD matrices.
3

---

Published as a conference paper at ICLR 2024
Assumption 3.2 (Fourth moment condition). Assume there exists a positive constant xb 0, such that for any PSD matrix A, it holds that
Ex Ex=D(xx xx Axx ] (HAHH.
A special case of Assumption 3.2 is when D is a Gaussian distribution. For that case, we have = We remark that although Assumption 3.2 does not cover some special cases, c.g., the one- hot distribution discussed in Zou et al. (2021a) similar results can still be obtained by applying our techniques with minor modifications (see Appendix
P for details).
The following assumption characterizes the noise of the stochastic gradient.
Assumption 3.3 (Noise condition). Assume that
Σ ( (V & - (w", x)))xxx]
and の² [ EH 3 la exist and finite. Here, E is the covariance matrix of the gradient
noise at w". For well-specified models where - (w", Xx) ~ NN(,, o moise)) we have E m H and thus 0² o22 naise"
4 MAIN RESULTS
We now provide an excess risk upper bound for ASGD.
4.1 RISK BOUND OF ASGD IN THE HIGHT-DIMENSIONAL SETTING
Before we present the results, we first introduce three quantities which are cutoffs of the spectrum of H. The eigenvalues of A; can be either complex or real, which depends on the range of A Define
k max (i A (Vg cō //lg-68)33/
(4.1)
k = max i: A (V - cō clg- ( 6))2
It is easy that A+ < At. For any 1+ and any i kt, A; has real eigenvalues S 222- and for i between he and kt, A has complex eigenvalues ø1, I2 with the same magnitude. We also define : as
= max (i: A 2 (1 c)/
Parameter choice. We select hyperparameters of ASGD as follows: We first pick a non-negan non-negative integer R. We then select parameters 6, 7, B, as follows, based on x:
8 WAY
1
85 2nh (H)
E 8, 20p
(4.2)
Eish A
1+ 3
We can show that with our choice of paramters, we have kt k k (see Appendix E.1 for details). For convenience, we introduce the following notations for submatrices of H: for any non-negative integers 1i < k2, denote
Heyk
Σ Ava. (
Σ Ava.
i=1+1
Now present the main result, which gives finite excess risk bound for ASGD under the specific parameter choice (4.2).
Theorem 4.1. Under Assumptions 3.1 3.2 and with the parameter choice 4.2
if
2, the excess risk of tail- tail-averaged iterate from ASGD satisfies:
[[L(W [[L(W,,++N] L(w*) < 2 Effective + 2 EffectiveBias.
(4.3)
where the effective variance is bounded by
2
dr
9
14
Effective Var S -²r
+ 18(8 + N2²
X
+ +36N2
X2
Wo
w'1
2N
N
N
6
0.5
i>k*
10
2
1 Wo
w"
|Wo w² w011
+ 4(8 + N)] wo w II
7 7
4

---

Published as a conference paper at ICLR 2024
and the effective bias is bounded by
8(c0/g)2z 2-
4s²
EffectiveBias
N282 |Wo-
N2 c
|| ((--HH))*
0H)) / ww") w''llix
0:k2
16c
100c
N262 II
8H) (wo
w')l
11(I 5H) 9/2 (/2 w w')llir
H
.22(1 c)2
18
[
7 8
H
(wo- w")
/
+ +18
1s/(1
7 H (wo w')
22 + 8)2
2
H
kT.k"
with k- = max Ap 2 1/((7 + 8)N)}, and
(H)
1 2
Σ 1>
A
Theorem establishes the excess risk bound of ASGD under the overparameterized setting. To our knowledge, this is the first instance-dependent bound of ASGD within each eigen-subspace of H. Our excess bound includes both the variance term, which depends the randomness coming from the data distribution D, and the bias term, which includes "accelerated convergence" terms brought by the ASGD.
Remark 4.2. The cutoff index k- is referred to as the effective dimension, which be much smaller than the model dimensionality d, especially when the eigenvalues decay fast. We want to emphasize that similar effective dimension has also appeared in the previous work which analyzes the convergence of SGD under the overparameterized model setting (Zou et al. 20216 Wu et al., 2022). Nevertheless, the effective dimension of SGD) is kŠ == max (7: AR= 2 1/(NN) which is smaller than that in ASGD. In Section 5 SGD and ASGD.
we will provide a comparison of the risk bounds between
Remark 4.3. It is worth noting that under the parameter selection 4.. one verify that tll < 1.
Such a condition guarantees that r = 1/(1 - v0) is finite, which further guarantees that our derived
risk bound for effective variance is valid.
4.2 IMPLICATION IN THE CLASSICAL SETTING
In this subsection, we show that Theorem 4.1 implies the excess risk bound in the strongly convex setting and can recover similar result as Jain et al. (2018). The hyperparameters of ASGD are chosen to be
28 "pdd
pd
8
20h (H))
7-
V
1 B
(4.4)
where == Ad is the smallest eigenvalue of H. We remark that the parameter choice in 4.4 is different from the choice under the overparameterized setting given in (4.2) because 7 is chosen as the model dimension d, and the upper bound of in (4.2), which is (2 E At), becomes vacuous. Instead, we require eigenvalues such that A; has real eigenvalues (i.e., when i kt,, see Section for detailed proof). The following corollary provides the excess risk bound in the strongly convex setting:
2.3/u μ to guarantee that no eigenvalue falls in the region of small
3 3.2 and 3.3 and with the parameter choice in (4.4) the excess risk of lvil-averaged iterate from ASGD in the classical regime satisfies:
Corollary 4.4. Under Assumptions 3.1
B [c) L(w")
100
exp (-
B8 2 [L(wo) L(w")]
N2
Elfective Bias
1008 [L(w)) L(w")] 360
12802d
N2
N N2,3
Rffective Variance
Denote x = (r(H)/u, then (1/ (R)/ Assuming that L(wo) L(w") = O(o²), then the bound given in Corollary fully recovers the excess risk upper bound given in Theorem I of Jain et al. (0118 in terms of exponential decay rate, leading-order variance and lower-order vari- ance. Moreover, the coefficient of effective bias is OHkR/N2), which significantly improves upon
5

---

Published as a conference paper at ICLR 2024
O 1//1/////////3 given in Jain et al. (2018)
3. It is worth noting that Liu & Belkin (2018) proved
(1) coefficient for effective bias of ASGD. Our result can also recover the constant coefficient when [1 c) 2 2, because 1
20,3 < 23 and 32 s 1. The difference in this
coefficient between the bound in Liu & Belkin 2018) and ours mainly due to slightly different
treatments of terms in the form of N Σi= (1 5)', which is not essential.
5 COMPARISON BETWEEN ASGD AND SGD
In this section, we first introduce the SGD update, which is given by
SGD
SGD w - (VL(W SGD),
where 8 satisfies the requirement in SGD W N = -N E -
(4.2 Analogous ASGD, tail-averaged SGD is defined as w wSGD, The excess risk of tail-averaged SGD then [[L(w
[ww). ). We then present the following theorem, which shows the existence of linear regression instances where ASGD outperforms SGD (the proof is given in Appendix (D2)):
Theorem 5.1 (Informal). There exists class of linear regression instances and corresponding choice of parameter such that the excess risk bound of tail-averaged ASGD satisfies
B[T( x)] T(w") ( + N 0.9873*))
and the excess risk bound of tail-averaged SGD satisfies
([ e T(w") (N=2 N- .0.99")))
Theorem 5.1 is inspired by the following comparison of the effective variance and bias of SGD and ASGD with the assumption that (NN). This is technical assumption that helps simplify excess risk bounds, and the comparison can be extended to the case of 8 Q(N).. Under the same set of assumptions as Theorem 4.1 Zou al. (202Tb) prove that, with bias-variance decomposition similar to 4.3), effective variance and effective bias of SGD satisfy:
ROOD N
Effective Var S o
+ +
Σ
x
4 N
H
Ilwo
+ (s + w'll
- w :0
KŠGD N
N82
Σ x
i>
EffectiveBias
N2 - 8H) ww)
+ ([[--H)' w>)
where rSGD (1 9 tr (H) and REGD max {i: X; 2 1/(8N))-
Comparison of effective variance. Assuming that the initial variance wo - w is bounded, the effective variance of ASGD is dominated by
2r
24k* N
+ 18(s O({++N)??
Σ xp
1>
and effective variance of SGD is dominated by
o²
r'rsOD
SGD
Ns+NN88
Σ S
X
N
Thus, ignoring a², and FSGD and constants, effective variance of ASGD in the subspace of A; is Ommin (1/N, 2 )) compared to O(min (1/N, N)22?)) for SGD. With y 2 according to the choice of parameters in (.2). we conclude that the excess variance of ASGD in every subspace larger than that of SGD.
The following corollary characterizes the effective variance of ASGD when the eigenvalue spectrum decays with polynomial or exponential rate. These examples have been studied for SGD in Zou
al. (2021b) and Wu al. (2022).
Corollary 5.2. Under the same assumptions as Theorem
2| is bounded. 4.1 suppose that ||wo- - -w
1. If the spectrum is X; i1(1+) for some > then the effective variance is ((R/N))/(L+))

---

Published as a conference paper at ICLR 2024
2. If the spectrum is X e then the effective variance is O + log N)/N).
Remark 5.3. For SGD, the effective variance is O((1/N)//1-r) if the eigenvalue spectrum is
A = = (0++), and (log N/N) if the eigenvalue spectrum is A = e (Zou et al. 2021b). There- fore, the effective variance of ASGD is larger than that of SGD under both eigenvalue spectra.
Comparison of effective bias. Effective bias of both SGD and ASGD decay exponentially within each subspace. The decay rate of SGD is (1 - 8x,)" " in the subspace of X, For ASGD,
1. When I k,, the decay rate in the subspace of A is (cd/g)". By definition of kt, we have 1 8A, $ có/g (see Appendix E.1 for detailed proof).
2. When 1+ <is S kl, the decay rate the subspace of X is [o(1 - 8A.)] According to the definition of k when by < i k. we have 1 - -d, S ve(1- - 8A,): When & < i S kt, we have
1 5x Ve(1 82,).
3. When > kt. the decay rate in the subspace of X is - (7 )))" By the choice of parameters 4.2 we have y 2 so 1 - (r 0) < 872-
Combining the three cases above, we conclude that the effective bias of ASGD decays faster than that of SGD in eigen-subspaces of A; where > k while it decays slower than SGD in subspaces of A where
Egenvalues of A, (complex/rea))
A
Ag
lydtt Bul)"
[ef/g]"
Acceferation
Slow down
i s k. This phenomenon is illustrated in Figure I Therefore, ASGD can perform better than SGD if Wo w is mostly refined the eigen-subspaces of A; where ke
Contraction
SGD: 5A,)"
c1/b
Figure 1: Illustration of the eigenspectrum.
We remark that this result is consistent with the acceleration of bias decay presented in Jain et al. 2018). Without instance-specife analysis, the exponential decay rate bias is determined by the decay rate in subspace of the smallest eigenvalue. As the effective bias of ASGD decays faster than that of SGD in the eigen-subspace of small eigenvalues, the worst-case decay rate of the bias error of ASGD enjoys acceleration compared to SGD.
EXPERIMENTS
In this section, we empirically verify that ASGD can outperform SGD when wo - w is mainly confined to the eigen-subspace of small eigenvalues.
Data model. Our experiments are based on the setting of overparameterized linear regression, where the model dimenstion is 2000. The data covariance matrix is diagonal with cigenvalues A; i-2 The input x, follows Gaussian distribution (O, H). so Assumption 3.2 holds with v == 3. The ground truth weight vector is w = 0, and the label y/ follows the distribution (N(, where 0² 0.01.
Hyperparameters of ASGD and SGD. We select parameters of ASGD so that it satisfies the re- quirements in 44.2p. We first let , 5. According (4.2). å satisfies ô < 1/m², we pick 0.1, which is also the stepsize of SGD. We then let a = 0.9875, so that (1 - c)/5 = 2(1 - a)/8 8 = 0.25 A2 which implies that k = 2. Finally, we select / (1 a)/a and 7 R/()).)) We can verify that the parameters satisfy all requirements in (4.2).
We fix the length of tail averaging as N 500. and conduct experiments on different where 500. In each experiment, we measure w w Hw..+N. For each 8, we run
8 = 50, 100, the experiment 10 times and take the average of the test results.
We examine three different initializations: (a) Wo = 10 representing the case where Wo w mainly refined to the subspace of large eigenvalues, (b) Wo = 10 e2, representing the case where w" is mainly refined to the subspace of Aę. and (c) Wo = 10 C20. representing the case where Wo - w mainly refined to the subspace of small eigenvalues. Experiment results are shown in Figure? 2 We observe that ASGD indeed outperforms SGD in the scenario where Wo w is mostly refined to the subspace of small eigenvalues, and performs worse than SGD when Wo w is refined to the subspace of large eigenvalues. Additionally, the excess risks of SGD and ASGD similar when Wo w' aligns with the subspace corresponding to Aç. which is also aligns with the implication of Theorem 4.1
7

---

Published as a conference paper at ICLR 2024
0.0
540
034
3.20
0.30
6.0
232
(a) WD 10 e1
(b) Wo e2.
(c) Wo e20-
Figure 2: Comparison of excess risk of ASGD and SGD. The noise scale is 0.01. We run each experiment 10 times and take the average of the excess risk in the 10 trials.
PROOF SKETCH
In this section, we present the high-level ideas in our proof. We mainly introduce two main ideas of the proof, including (i) bias- vansvvriance decomposition, and (ii) analysis of excess risk bounds within each cigen-subspace, based on the eigenvalues of A, Define the tail averaged centered ASGD iterate 72,e+N = N-1 ==+N-1 th The excess risk is then
[( sN) I(w")
H 0
E Ms.0+N N 2 Mantnil)
2
0
We also define the linear operators == E[A, @ Ad and B = & A. which are both PSD operators. Additionally, the difference B B is also a PSD operator, which contributes to the effect of the fourth moment in the excess risk bound. The reader can refer to Appendix F for details of the linear operators.
7.1 BIAS- VARIANCE DECOMPOSITION
Following the techique used extensively in previous works (Dieuleveut & Bach 2013 Jain al.
2018 Zou et al. 2021b, Wu et al. 2022; Liang & Rakhlin 2020), we decompose the centered iterate
77: into the bias sequence 77: and the variance sequence 7h vai defined recursively
bias
hias
no
bias
775
(7.1)
Am
var
Se,
0.
(7.2)
The tail averaged iterate then 7s N Te: +
No where
s+ -
N-1
Σ
m
N
Tsss+N
N
m
(7.3)
The excess risk can be decomposed into bias and variance:
B[L I((w*) =
H
E. T 6 (ostN)
2. Bias + 2 Variance,
where
H
H 0
Bias =
2
18 1
Ma:-N N 2
bius
briss [ss
Variance =
2 0
E T X MEstNl
Define the covariance matrices B, = E(mh of B, and C, then satisfy
bias
& bin and C. == (m) & n.... The recursive forms
B. = Bc B
Bo 770 705
(7.4)
C, = B C.-I+ E, C. = 0.
(7.5)
7.2 PROOF OF THE BIAS BOUND
In this part, provide an overview of the analysis of the bias bound in simplified problem setting. We consider the last bias iterate (i.e., N 1) and assume that B B. The analysis of the general
8

---

Published as a conference paper at ICLR 2024
cases is given in Appendix H According to the recursive form of B, in 7.4). we have B, B Bu.
With the assumptions that B = B, we have
B, B B A A (
1 1
(wo w²) w w²) (A9)
(A")
Note that A is block-diagonal with each block being A;, so bias can be expressed as
Bias 1/1 H
0 0
EE
17
bius Me.s+N
bias [sis+N]
1
H
0 0
B
A
A
1 ))
2
where w; == -Wo w") )r The following lemma explicitly characterizes A
Lemma 7.1. Let the eigenvalues of A, be 21 and 22. Then, for any integer 2 1, we have
1-2
c(1 - 5A,)
(1
5A,)
A
222
The detailed proof of Lemma 7.1 is given as the proof of Lemma
E.3
With Lemma 7.1 have
I A H, (1- 81,) 22 ( c)
(x1
x2 21
For < kl and > kt, i.e., A, has real eigenvalues < 22, I decays exponentially with the same i k i.e., A; has complex eigenvalues with |.a| = |22)). [T] is bounded by
rate xzz. For ki
[I| = (1 5As)
I2 (x2 - c)
01 c)
IA
2
2
01
+
D2
2c
22
32 I1
2
2
22
I1
[222]
+
22
2c
22
1-1 5-1
1
x2
2
where the first inequality holds because 0 < 1 - ob; < 1, and the second inequality holds due to triangle inequality. For the term (x;
8-
1) 1
- 21)1. note that
---1 3-'-zi" 22
2
2
12 2- 2
Ix th 121 1-1k=-2-
2-k = (s-1))22 1=2
k=
k==
where the incquality holds due triangle inequality, and the second inequality holds because |z] [z2]. Therefore, the exponential decay rate iI| |02]". The following lemma provides tight bounds of F2, thus characterizing the exponential rate of bias decay within each sigen-subspace:
Lemma 7.2. Let æ1, be the eigenvalues of A; Then
(a) When < kt, (c5 Velg 0)(g co)) x2 c5/g.
When A < kt, |22|| v((1-
(c) When i i> kt,
(7 8)4, 22 < (7 + 8)
The detailed proof of Lemma
7.2 is given in Appendix
E. We can thus obtain the exponential
decay rate of the effective bias.
CONCLUSION
In this work, consider accelerated SGD with tail averaging for overparameterizee linear regres- sion. We provide instance-dependent risk bounds for accelerated SGD that are comprehensively dependent on the spectrum of the data covariance matrix. We show that the variance error of accel- crated SGD always larger than that of SGD. We also show that the bias error accelerated SGD is smaller than that of SGD along the small cigenvalues subspace but is larger than that of SGD along the small eigenvalues subspace. These together suggest that accelerated SGD outperforms SGD only if the signals mostly align with the small eigenvalues subspaces of the data covariance and that the noise is small. Our results also improve a best-known bound for accelerated SGD in the classic regime (Jain al. 2018)

---

Published as a conference paper at ICLR 2024
ACKNOWLED
We thank the anonymous reviewers and area chair for their helpful comments. XL, YD and QG are supported in part by the NSF grants 1IS-2008981, CHE-2247426, and the Sloan Research Fellow- ship. The views and conclusions contained in this paper are those of the authors and should not be interpreted representing any funding agencies.
REFERENCES
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
Raphaël Berthier, Francis Bach, and Pierre Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. arXiv preprint arXiv:2006.082) 2020.
Alexandre Défossez and Francis Bach. Averaged meattmmman----ees Bias-variance trade-offs and optimal sampling distributions. In Artificial Intelligence and Statistics, pp. 205-213, 2015.
Aymeric Diculeveut and Francis R. Bach. Non-parametric stochastic approximation with large step sizes. The Annals of Statistics, 2015.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger con- vergence rates for least-squares regression. The Journal of Machine Learning Research, 18(1): 3520-3570, 2017.
Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, and Aaron Sidford. A markov chain theory approach to characterizing the minimax optimality of stochastic gradient descent (for least squares). arXiv preprint 171.v:1710 2017a
Prateek Jain, Praneeth Netrapalli, Sham M Kakade, Rahul Kidambi, and Aaron Sidford. Paralleliz- ing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification. The Journal of Machine Learning Research, 18(1 18(1):8258-88) 82999, 2017b.
Prateek Jain, M. Sham Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Acceler- ating stochastic gradient descent for least squares regression. COLT, pp. 545-604, 2018.
Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham Kakade. On the insufficiency of ex- isting momentum schemes for stochastic optimization. In 2018 Informaiion Theory and Applica- fions Workshop (ITA), pp. 1-9. IEEE, 2018.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can gener- alize. The Annals of Statistics, 4803):1329-137,, 2020.
Chaoyue Liu and Mikhail Belkin. Accelerating sgd with momentum for over-parameterrzee learn- ing. arXiv preprint arXiv: 1810. 13395, 2018.
Yu E Nesterov. A method for solving the convex programming problem with convergence rate of ). Dokl. Akad. Nauk SSSR, volume 269, pp. 543-547, 1983.
Yurii Nesterov. Introductory Lectures Convex Optimization: Basic Course. Springer Publishing Company, Incorporated, edition, 2014. ISBN 1461346916.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr compu- tational mathematics and mathematical physics, 4(5):1-17, 1964.
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009. /4286, 2020.
Aditya Varre and Nicolas Flammarion. Accelerated sgd for non-strongly-coonex least squares, 2022.
Runzhe Wang, Sadhika Malladi, Tianhao Wang, Kaifeng Lyu, and Zhiyuan Li. The marginal value of momentum for small learning rate sgd. arXiv preprint arXiv:2307. /5/96, 2023.
10

---

Published as a conference paper at ICLR 2024
Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M Kakade. Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression. The 39th International Conference Machine Learning, 2022.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean Foster, and Sham M Kakade. The benefits of implicit regularization from sgd in least squares problems. The 35th Conference on Neural Information Processing Systems, 2021a.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M Kakade. Benign over- fitting of constant-stepsize sgd for linear regression. The 34th Annual Conference on Learning Theory, 10.

---

Published as a conference paper at ICLR 2024
The organization of the appendix is as follows.
In Appendix
A
we provide additional experiments to justify our theoretical results.
In Appendix
B we discuss the choice of hyperparameters mentioned in (422).
In Appendix
we extend our main results to the Stochastic Heavy Ball method.
In Appendix D
we prove Theorem 4.1 which depends on two key lemmas: Lemma D.3 to
bound the variance term, and Lemma D.4 to bound the bias term.
In Appendix D.2 we prove Theorem 5.1
In Appendix
E provide the upper bounds for A, which is the population version of A., the update matrix of the noise Th, The upper bound of A is crucial to our proof.
In Appendix we provide the upper bounds for a group of linear operators, which are crucial to our proof.
In Appendix
G
we provide the detailed proof of Lemma D.3
In Appendix H
we provide the detailed proof of Lemma D.4
In Appendix
we prove Corollary
Appendix
we provide the detailed proofs for the setting of standard basis.
In Appendix
K
we provide the proof of all remaining lemmas.
12

---

Published as a conference paper at ICLR 2024
A ADDITIONAL EXPERIMENTS
In this section, we provide additional experiments that justify the theoretical results provided in Theorem 4.1
Data model. Similar to the experiments provided in Section 6 the model dimension is set to be d = 2000, and the input x; follows Gaussian distribution (0, H). We consider H with three types
of spectrum: (i) A k-2 2, (ii) Ae log(k: + 1), and (iii) As e
k/2, The ground truth weight ~ (O, o²) where a = 0.2.
vector is w = O, and the label yt follows the distribution
Hyperparameters. We select the same hyperparameters of ASGD and SGD as the choice in Sec- tion i.e., v0 = 3, K = 5. = 0.1, 0.9875, 3 = (1 -a)aaaaaaa a and 6 (b)R))). We fix N 500 and conduct experiments on different s where s = 50, 100, 500.
In each experiment, we measure both the bias error (w wit s:s+NN Hw s:s4 n and the variance error the experiment 10 times, and take the average of the test
(w ++++N) Hw N. For each 8, results. We examine two initializations: (a) Wo = 10 e1. which is the case where Wo - w is mainly refined to the subspace of large eigenvalues, and (b) Wo 10 eio, which is the case where Wi w" is mainly refined to the subspace of small eigenvalues.
The experimental results are shown in Figures and 5 In all experiments, the variance error of ASGD is larger than that of SGD. However, the bias error of ASGD decays faster than that of SGD when Wo w is mainly refined to the subspace of small eigenvalues.
ASG0 Max
500 aie
A5SI vol
500
20-1
Asso
Doeeer
569 as
A300 va
12
1.00
200
450
540
310
200
300
60
520
(a) Wg 10
G1
(a)
Wa
10
610
Figure 3: Comparison of bias error and variance of ASGD and SGD. The spectrum of H is λ
k-
A650 Hax
500 2ie
360 bist
A5500 vol
A3UD VM
500
30%
12a
200
500
100
(a) Wi 10- éi
(a) Wa
10 610
Figure 4: Comparison of bias error and variance error of ASGD and SGD. The spectrum of H is d
A logg( + 1).
B PARAMETER CHOICE
B. DERIVATION PARAMETER CHOICE
Following the optimization literature (Nesterov 1983), we first fix the relationship between a and
as
1
(B.1)
1+ 9
We then fix
8
(B.2)
13

---

Published as a conference paper at ICLR 2024
6500 1a
940 2
10"
Booee tok
ASC0
30rt-
101
30-1
100 166
(a) Win C1
(a) W0
610
Figure Comparison of bias error and variance of ASGD and SGD. The specturm of H is A R/2
following Jain al. (2018). We remark that introducing prevents the effect fourth moment from blowing up (see proof of Lemma F.5). Furthermore, we require 2 d to enforce acceleration.
Then, from the requirement < 1, we require
8u tr (H)
1
Σ
\ <.
2
Therefore, it suffices to take
75
(B.3)
2 (r(H)
2 EiSk A
Combining B.1
derive the choice of parameters in 4.2 We remark that we get rid of dimension dependency by merit of the term u> this term, should be chosen as the model dimension d (as Jain al. (0188)
B.. and B.3
4 EisR A, Without
B.2 DISCUSSION OF PARAMETERS
In the parameter choice (42)). is a free parameter. this section, we discuss how the choice of affects the excess risk bound. Suppose that both equalities are attained in (B.3). We focus the impact of on (i) eigenvalue cutoff k. and (ii) bias decay rate. Note that
2Φ EiSR A
so y increases as K increases. Furthermore,
8
so / decreases as increases. We also have
1-3
c c=
1 1
so è increases as A increases.
l is defined 1: max > 2 (1- c)/8, so 1: increases 7 increases; The bias decay rate the subspace of the smallest eigenvalues (i.e., i > 1T) is (r + 8)4,/2, so the decay rate accelerates for larger R. However, for the subspace of X; where kl
k+, the bias decay rate is
[c(1 )//2 so the decay rate slows down for larger R.
Combining all the above, we conclude that the choice of is subject to the eigenvalue spectrum of the data covariance matrix. Additionally, choosing small K will make the algorithm perform more like SGD.
C IMPLICATION FOR STOCHASTIC HEAVY BALL METHOD
In this section, we extend the results we obtained for ASGD to By taking 5 in 3.3 and eliminating and u, using (3.2 and 3.4) we get
W Wt (1-a)7 V (((w)) a(1 (8 (w, W.-1):
14

---

Published as a conference paper at ICLR 2024
which is exactly the form of the stochastic heavy ball (SHB) update. Therefore, the excess risk
bound we presented in Theorem (.1 can be directly applied to SHB.
As there are three free parameters but only two combinations (1 o))7 and a<1 (3 used,
enforce that / = (1 a)/a a and define c c= a(1 8) and @ = (1 7. similar to ASGD. By (4.1)
and the definition of k we have k = k- = 0. Therefore, the following corollary gives the excess risk bound of SHB:
Corollary C.1. Consider stochastic heavy ball (SHB) method, given by the update rule
W++1 = we - (L-VV((w,) + c(w: - wt-1), where the hyperparameters satisfy CE (0, 2/M] and (1 - c)7/2 with
4
EE
0. 2/ (r())
Define 7SHB = (1 - th (r())/4))- k. = max(k d 2 1/(rNN), and define ky as in (4.1)
Then we have the following upper bound for the excess risk:
E [[[(W.:+ND]] L(w") = 2 Effective + + EffectiveBias,
where effective variance bounded by
Effective Var S a Frshr
27k*
+ 18(s N)7
Σ \3
TTSHB
9k*
36N
Σ
2N
N
i>k
10
2
Wo w 11 Hout
+ wwo
w " + +4(s + +N) - w ww 110000
and effective bias is bounded by
100
|wo w' H
EffectiveeBas S c. 4s² +
(1
c1-
N2
18
HH
H 2
+ N2ya
I
(Wo w
+ 18
(wo w")
2
Hg
Remark C.2. In the eigen-subspace of X₃ the exponential decay rate of effective bias of SHB is max(c", (1 -(*))2),, which never faster than that of SGD. This happens because for SHB, y has to be smaller than that of ASGD control the effect of stochastic gradient. We can thus demonstrate that ASGD is superior to SHB in terms of the exponitial decay rate of the bias error, which extends similar result given by Kidambi al. 20118 to the instance-dependent case.
D PROOF OF MAIN RESULTS
In this section we prove Theorems and 5.1
D.1 PROOF OF THBBREM 4.1
We start with the basic bias-variance decomposition lemma.
Lemma D.1 (Bias-variance decomposition, Jain al. (018 The excess risk can be decomposed into bias and variance as
[[ - I(w*)
H
E. I Ma:a-N 8 NototNl) < 2 Bias + 2 Variance,
= 2
(D.I)
where
1 H
Bias =
2
0
0
1
H
Variance
Elm 7os++N]
2
0
0
15

---

Published as a conference paper at ICLR 2024
This indicates that the generalization error could be bounded respectively by analyzing the bias and variance. We then further decompose bias and variance.
Lemma D.2. Bias and Variance can be decomposed as
1
0 Mo). Bias
1
( 0 M.)
Variance
2
0
0
M1
2
2
0
0
M3
where
N Σ k=
N N-1
M
A
C,
Σ A
(D.2)
N2
k=0
N-1
N --1-1
NN-1-1
M = N2
A
(Cott - C+t--1
Σ
A k
(D.3)
R=0
k=
--
N-1
M3
=
A
B
(D.4)
N
k=0
1 N-1
N-1-1
N-
M =
A#
(B
B B B
Σ
A#
(D.5)
N2
k=
Proof. The proof largely follows Zou et al. have the following
(021b). From the definitions of bias as in
7.1 we
E 1T
bias
Mi
B
bius M7-1
Am
(D.6)
and for 77
variance as in (..2 we have
E m m
E AAA + Solm An
(D.7)
Then, regarding the term E Ms
T N= we have
E M
C nsis+N]
N-1
8+ -
s+N
Σ
E var
Em
var + Σ
E[n
me
var +
Σ
E
var
@
m
var
N2
k=
k=1+1
8+N-1
C
+
Σ k=H+1
A
C.,
+
Σ
Cg(A
NZ
k=t+1
N 1
N--1
1
A
C,
A
NZ
k=
N
NN W-t-1
N-t-1 Σ
Σ
A
(C.4+ - Bo 1)
k
N
where the second equality holds by applying (D77 k - I times, and the last inequality holds due
to Lemma K.4 The decomposition of bias into M3 and M2 can be proven in exactly the same manner.
From Lemma D.2 we can further bound the variance and bias terms as follows. We have the following bound for variance, whose detailed proof can be found in Appendix G
Lemma D.3. Under Assumptions have
3.1
3.2
and
3.3 with our choice of parameters in
Variance 5 7r
27k
+
18(s + N) co)2
Σ x2
2N
(1-c) c)2
where As* max(k: d 2 2N -00)(1 - c)))
16

---

Published as a conference paper at ICLR 2024
The following lemma provides upper bound for the bias error, whose detailed proof can be found in Appendix
Lemma D.4. Under Assumptions we have
3.1
3.2 and
3.3
and with our choice of parameters in (4.2)
9k* N
36N (g c6)2
14
Bias < Effective Bias
Σ x
wwo
w w"ll
N
(1 [1-c]² c)²
12
10 wo w
1 1-c c
+ 1-c
H
+
|o w"ll I
w - + 4(s + N)]
q cd
where
8(c5/g)23 N282
4s²
Effective Bias
|wo w w0
c |[[ 0H)
-w")ll H
N2
u.ki
16c
100c
N282 (I
(HH)'/(Wo
w-)
|[[I
w w')l
N2 c)2
9(1 -c)²
11-9-0
I 9
c5 H
(wo- w")
2N co)²
1 1-c
H-1 AT.K*
9- cō H
(wo "wo-w")l
18
Hu
Substituting Lemma D.3 and Lemma D.4 into (..1
Lemma D.I
yields our final result presented
in Theorem 4.1
D.2 PROOF OF THBOREM 5.1
We consider the linear regression instance where the samples x, follow the Gaussian distribution W(O, H) where X; = 2- so vb = 3 in Assumption 3.2 The hyperparameters of ASGD are chosen aa/a, 5, 8/ (/(3)))) 79/ 150 and N 500. Finally,
as 5 = 0.1, a 0.9875,
we require (Wo w"), = 0 for 8.
We now present formal expression of Theorem 5.I
Theorem D.5 (Restatement of Theorem 5.1) When applied to the aforementioned class of problem
instances and initialization such that l|wo w 1 = (o)),, the excess risk of SGD satisfies
B[L(w (( ] L(w") (0022(N N 0.996")),
and the excess risk of ASGD satisfies
E[ L(w") O - 0.9873*)).
Proof. We first recall the excess risk lower bound for SGD given by Theorem 5.2 of Zou et al. 2021b:
o²
E
SGD N)] I(w*)
SGD N
+
Ns+
Σ x
600
Variance
1
|I - (H) + 10082N2
Ho. +
- (H- w Wl
100
EffectiveBias
As C = 2a - 1 and == ad + (1 - a),, , we have = 0.975 and 79/750. By definition of k. kt,
k 4.1 we have
1= == T= - k1
The analysis of the Variance term is given in Corollary 5.2 For the EffectiveBias term, note that all coefficients are absolute constants, so suffices to consider the exponential decay rate in the eigen-subspace of λz. For SGD, the exponential decay rate is (1 - 82,) = 0.996", and for ASGD, the exponential decay rate is (1 - (y + 8)A,/2)* 0.9873*.
17

---

Published as a conference paper at ICLR 2024
E PROPERTIES OF A,
E. SEGMENTATION OF EIGEN-SUBSPACES
Recall that A, is defined as
0 -1:
A
(E.1)
-c
1 1+c-941
so the eigenvalues of A; are
I1 1+C- QA
(1 (1+ce q/,)² - 4c(1 - o7₂)
(E.2)
1 1 q
(1+c 91,1² - 4c(1-6pp
I2 2
(E.3)
2
From 1E.2 and EE.3)
see that whether A, has complex real eigenvalues depends whether
the following holds:
( 4c(1 -82) <
(E.4)
Directly solving (E.4) we have
(v9- có velo- A < <V + vdqa-8)2//²
Define the eigenvalue cutoffs as
k == (i: > > (V 0ō
(E.5)
k = max (i
A 2 (1 05 - /
(E.6)
and we note that
(Vg- /dl 0)}²
1 1-c v1 - cδ - vdg -0)
(1 - c)²
G2
9
Vq cb + /dl 8)
(Vq c8 Vcla - -))2
(Vq - + Vdl - 6))²
1 1-c vq - σ + /dq -6)
(1 - c)²
q V1 - - /dl -0)
(Vq cō Vclq - 0
Thus, i < 1st or i > kt, then A; has real eigenvalues; If 1 < i s ke, then A, has complex eigenvalues. We also define two other important eigenvalue cutoffs
= maxfi: x 2 (1- (1-c)66)
(E.7)
and
1-c
k* = max i 2N co) J
We have the following lemma concerning the cutoff of eigenvalues:
Lemma E.1. Let kf and &t be defined in EE. and E.6 Then we have For all i >> kt,, we have
1 --6
A
9
For all i < A we have
A > c
Proof. For all i > kt, according to
we have
cd Velg 8)
1-c
1 1-c
cd + clq 8)
where the second inequality holds because Vi- velo-o) 6) cause q 2 6.
< 1, and the last inequality holds be-
va Vela-8)
18

---

Published as a conference paper at ICLR 2024
For all i> k4, we have
c 1 1-c c
vq- - + Vdq - 8)
1-c
A
q
vq σ0 /dq -6) 6)
8
= (1 c) bp 5) (1 + 8) v(q 1-))(1-666(
óg(ve 9 - cb - vdlq - 8))
c1 /dg 6)
1(q + 8) (q c6)]
óg(v9 00 - Vcl - -))
(1- (1-2)/ol c(q -6)
0,
g(V4 ob vdl - 5))
where the first inequality holds due to (E.6). and the second inequality holds because q - 8 < c(g- - -5).
0
With Lemma E.1 immediately know that k S ke S RT. If we also assume that N(1 c) 2 2,
then
1 c 2N(g c5) 4(q co) S (V9- + vdlq- -
- (1 - c)²
(1 c)²
where the inequality holds because c(q 8) S q - c5. We thus have k. 2 ktt
We then provide bounds for the spectral norm of A,. The bounds are accurate in the sense that when I1, 22 are real, the upper bound of - X2 is at most the multiply of a constant of its lower bound.
Lemma F.2. Let 2n and 22 be defined in (2.2 and
E.3)
Then have
if S kF, then T1, 22 are real, I2 is an increasing function in A, and
oB Vdl 8)(4 - c5)
4
q
kt < kt, then æ 22 are complex, and
|2>||
ve(1-5X.) -x,);
If > kt, then 1 22 are real, and
velg- 8))
9 co
d; S x2 S 1
1-c
c
Proof. if S k=, then by definition of 22, we have
C x2 gi: - 1 - /(1 + c- q2:)2 4c(1 - 0A:)
20(4 5)^;
q -c ((1 + c -2,)² - 4c(1 - 87:)
20(g- - 5)
1
l- v 1
--
yq-oš / v0
qb
qu
va-ot ve(g-
ai
va-o8 V Vola-8)
Note that the denominator is decreasing as a function of (1 - -c)////)), so we have
[1--1 1-c vq- + Vdla-)
1-c
(1-1 1-c vq- cō /ola - 8)
q4: +
qdi v0 c8 Vdlq - 8)
qd: vq-cō cō Vcla- - 8)
$ 11-0+122
also have
1- 1-c
((1-
1-11-c v9-c6 + vdq 8)
1 1-c vq-cd - vclg - 8) q Vq-cō + vcl - 8)
qd:
qdi Vq σb Vcly - 5)
19

---

Published as a conference paper at ICLR 2024
21 Vg c8 cō Velg d)
2 2/llg - 6)
vq V cb + v -)
vq cd vcla -6)
Therefore, we have
2019 - 8) co
22 S c-
2q
and
22 2 20(9 -0(9-8) 8) vq
c8 + Vclq 8)
cb Vclg 0) c5)
2 2/clq c/q
-0)
1 <i S kt, then we have
21 c11 - -8A;);
where 21 22 Thus, |2a| = [22| vcl1 - 52:).
i kt, then we have
- c qi V(1 + qA:)2 4c(1 87;)
1 D2
2(g c5)A;
(E.8)
1 1-c+ + c -()))=-)))=---- - 4c(1 - -21,)
Note that
① 01;
(1 (1-c+ - 4c 8d0) + V(1+c qAi)² 4c(1 - 82,)
2c0 9(1 + 9>;)
4elg - () - cō)
VI+c- 11+4c-9,,2--- -2.c---))--4111 (1,1--8,)f + -d,))² 4c(1 -8%,) + [[1 + c)q 2c8 g2\il}
We also note that
VV cc)= 4e(1 82,) +(1 c)g 200 o2 X1)
(1+ 2c8- g²>, A
2 (1 + c)q 2cd-
(V (Velg 8) Vcla-50 8))3
=2velg 8)(4 c6) 2
where the first inequality holds because / (1 + - qA:}² 4c(1 - -2,) 2 0, the second inequality
holds because due to
E.5 Therefore, have
(1 1 + V (1+ 9>;)² 4c(1 - 4c(1-6Xx)
S 0,
0%:
s0 1 c qd:
V( (1 + c q2,1) - 4c 82, a function decreasing in A; We thus have
1- + (1+ A 4o
( -
11-
= 2(1 - c).
and
1 1- -- qd: + (1 -1+c- -A,} 4c(1 - )A;)
21-c+ V4- c0 Vclg - 8)
2(1 c) c)vq cd
vq c + Vela - 8)
v4 - cd + Vclg 5)
Therefore, we have
2(q co)
32 <
c \
2(1
and
- 2(g-c80JX
vq - σb
VVq cd + l0q 8)) Xi-
82 2 1
=
2 21-0)
1-c
Vq V
20

---

Published as a conference paper at ICLR 2024
E.2 CHARACTERIZATION OF A
Before we prove the upper bound for variance and bias, we first characterize the property of A for k 2 1 and i [1. d]. i.c., each block of matrix A corresponding each eigenvalue X, of H.
Lemma E.3. Let A, be defined as in (E.I). write A
(A n 22
(A 12
A
=
(A 122
Let the eigenvalues of A, be 1 and 22 as defined in we have
E.2 and
E.3
Then, for any integer l: 2 1,
(A -d(1 oA,))
32
2
21
(At) = - -8,)
32 2
31
x// 1
(A,)21
22 Ø1
(2 12 k+1
D22 21
Proof. We prove Lemma
E.3 by induction. For h = we trivially have
22 x
22 2j
c(1 5A,)
0,
(1-dA;)
-dAi,
-c.
12
x1
T2 I1
32 31
We also have
22 x T2 .1
21 +
1 gd;-
Therefore, Lemma E.3 holds for k = 1. Suppose that the lemma holds for k. Note that A k+1 A; A, so by induction hypothesis, we have
(A*+)) )n = (1- (1))))))A)) -cc1 5A,)
22 x
32 I1
1+1 12 = (1 52, (A 22 = (1 (1- 82:)
122
k+
82 21
++1 (A.+1) 21 -c(A ( I11 + +1 (1+c- (A
)22
= 21 5x,)
22
k-1
x4
k-1
c(1 + c- 9Ax))
32 x
22 I1
22 σ1
k-1 x
1/ 11
C. F142
c(z1 + x22)
32 F1
12 .1
22
k+1
x
k+1
T2 D1
(A k+1
22 - -(A) (11)1 + (1 + q2:)
21 =
k+1 R+1
c11
8bi))
+ (1 + 9A:))
322
21
322
D2 21
1 *
82
k+1
x
-
+ (x) + x2)
T2 F1
42 31
k+2 k+2
122 $1
L2 21
where we used the property that 2 + x2 = + c qA; and 21 = =c11 - -81,). Therefore, Lemma F.3 holds for ls 1, and induction is completed.
21

---

Published as a conference paper at ICLR 2024
F LINEAR OPERATORS AND EFFECT OF FOURTH MOMENT
F.1 PROPERTIES OF LINEAR OPERATORS
In this section, introduce linear operators matrices well their properties. We first give the following definitions of linear operators:
I 181, M M=ExxxxxXX
M=
(F.1)
B = E A.,
A X A.
Ar can be defined as the sum of deterministic component V and stochastic component V2:
V1
0 d (1+c)I
V2
0
xx,x, qx,x,
(F22
0
Define
0 0
-H -
V2 = E 2
(F.3)
then A V1 + V2. We are also interested linear operators E B[V, V2) and V2 @ V2. We introduce the concept of PSD operators:
Definition F.1 (PSD operator). An operator O defined on symmetric matrices is called PSD oper- ator if M ž implies O o M ž
The following lemma summarizes some basic properties of the linear operators.
Lemma F2. The operators defined in have the following properties:
(a) M, M, and M -M are PSD operators.
(b) For any PSD matrix M E 2d let
M
M
(F.4)
M
M
where M11 M12, M21 and M are d-by-d blocks. We then have
[82
5g
E 2 V
2 (M Mæ2)
59
q²
(V2 2 V2 MM
q²
2
(Mo
M2))
p9
Thus, E V2 2 & V2 and V2 & V2 are both PSD operators.
(c) B and B both PSD operators.
B - B E V2] V2 & V2 is PSD operator.
Proof. The proof follows those of Jain et al.
2018
Zou et al. 2021b), and Wu et al. 2002
(a) For any PSD matrix M, we have
M M E|xx Mxx T [x Mx)xx 2 0,
where the incquality holds because x Mx 2 and xx' > 0. Furthermore,
M o M HMH > 0,
where the inequality holds because M > 0 and H is symmetric. Lastly,
(M - M) M = xxxx Mxx
HMH Ex(xxT H)M(xx - H)) 2 0,
where the inequality holds because M and xx H is symmetric.
22

---

Published as a conference paper at ICLR 2024
(b) Note that M22 č 0 because M O.
We thus have
E
& V M - E V
0
x
M
1
0
E
0
xx
M21
M2
5x,x,
-qxpx
[82x
x,X
dqx:x M
{
E
x M22x,x
xx
602
ōg
@ E x M
6q
0g
@ (Mo M = 0,
b9
18
where the last inequality holds because M2 ł O, is PSD operator and a similar way.
6g
q²²
0.
VMMV M
HH
M
M
0
0
0
M21
M2
6H
HHM22
2gHM2
2qH
q HHM
T82 og
X HM
69
82
og
@ (M M22) = 0,
88 5y
5g
where the inequality holds because M22 2 0. M is a PSD operator, and
2 0.
o9 q²
(c) We have
BoM B-M= EAMAA]] BoM=AMA?
so both and B are PSD operators.
(d) Note that A, V1 + V2, and A V1 V2, S0
(B B) = (LE((V) V2) 2 (V, + - V2) 8 (V, (V1+ V2)) oM
(LEVV2 @ V2 V2 V2) o M
8 0g .g o @ ((M M) o M2) 0,
where the second inequality holds because because E & V2) V
V @ V, and E| R Vi] V VI, the third inequality follows from part (b), and the inequality holds because
5g
M 0, M MM is PSD operator, and
9 > 0.
5g
F.2 ANALYSIS OF FOURTH MOMENT
In this section, we study the difference of operators B and (due to the fourth moment) when they operated on PSD matrix M. Specifically, are interested in bounding the inner product
Σ B' M
(F.5)
1=0
The following lemma is the starting point of the analysis of fourth moment:
23

---

Published as a conference paper at ICLR 2024
Lemma E.3. For any PSD matrix M, we have
[B - B) o
M
3
V2 M,
where
(00
82 5y
B X V2 M
H
M
8q
q2
x H.
Proof. By Lemma F.2 d), have
BB
L & 22 - V2 V2)
M - L & V
where the inequality holds due to Lemma F.2 b).
Let M22 the matrix that contains the last d rows and columns of M. By definition of V2 in we have
F22
E
22 V2
M
óg v²
@
(M a
M)
[82
8g
trr((M22))
g²
H
ōq
0
6²
M
5q
g²
H.
where first eqaulity holds due to Lemma b). and the inequality holds due Assumption 3.2
The operators (I- and (I B) are of special interest in the analysis of fourth moment. We first show the existence (I B3) --
Lemma F.4. With the parameters in (I B)- exists and a PSD operator.
Proof. It suffices to show that the property holds for any rank-one matrix xx We have
[I - B) (xx
8 o (xx
= Σ A (xx (A*T = Σ (A (A*x)
k=0
k=
Kmma 0
Thus, the ij-entry of (I - BB--111- (xx] T)
(I-B3-1
2 (A*
I(*x)) |AAx/((
The series converges because all eigenvalues of A, i.e. eigenvalues of all A,, have magnitudes strictly smaller than 1.
We then define operator T as
8 V1 V2
I B V2.
(F.6)
Since B is invertible and (I B) is a PSD operator, is also invertible, and T-1 1 is a PSD operator. We can thus define matrix
(
82
5y
U=T
H
(F.7)
6g
The following lemma charanterizes key property of U: Lemma F.5 (Modified from Jain et al. (2018). With the choice of parameters in 4.2 the inner
<ie
product
is upper bounded by where
H
8 tr
A/.
(F.8)
2
2
Specifically for SHB where
0, have
0
0
(
U
0
H
2(1 c)
24

---

Published as a conference paper at ICLR 2024
Proof. Denote U,- R²x as the i-th block of the block-diagonal matrix U. By Equation (56) of Jain et al. 2018), we have
(U;)22 c1+
c0) 2cqod;
6
(1 + (q - 5)
+
(F.9
2(1 c² c>: + co))
2
2(1 è + c>: + cō))
On the one hand, (U;)22 is bounded by
5 +
(1+ (q -6)
5)
(-)c)l9-1) 6)
(Ux) -
2 2((1 - - + cdilq + +c))
2
2(cg + 8)
8
(1+c)(q -6
6)
9 9-8 8 1-c
+
+
2
2(1 + c)
2
1-c 20>;
5 7 6 20
8
7 8 5
(F.10)
2
262
2
8A, 2
2
where the first inequality holds because 8\; < 1, and the second inequality holds because 2 6,
and the third inequality holds because 7 8 8 S y and aB S 3. On the other hand, (U+)22 can also be bounded by
(1+ 8) 8 +
q - 6
7
8
7
(U,) 22 S 2 +
2(1- c2)
2 2(1 - c)
=
2
+
4
2
+
4'
(F.11)
where the first inequality holds because 1 - 2² + (q 0
2 - G. and the second inequality
holds because (7 5)/4 7/4. Thus, have
<
0 H U -
Σ (U,)) S
A
8 (
1
+
7
Σ
A
20R
4
2Φ
i>k
i>R
where the inequality holds due to F.10 for S and Specifically for SHB, we have
(IIIT) for > R.
(U))22 = 2( ((1--)) cqpi) - (1+
(1+c)g
2(1 c2) 2(1 - c)
where the inequality holds because 2((1 c²) + cq):) 2 -c²). We thus have
(0
0 H
) Σ
U
(U.)22 S ((r(HH
2(1 2(1-c)
s=1
The following lemma charaterizes (I B) -1 in terms of T and Vz: Lemma F.6. The operator (I - -B)-1 can be written in the form of geometric series
(I 3)
'EV V
Proof. According to the definition of B,
B = E
A
A
E (V + 8 & (V, V.)]
V1 V1
V1 x V2 + V2 V, +
V2 & V
where the last equality holds because V = V2. We thus have
(I B)
T E 2 x Vzl)
{T I - T E B V
I-T E V 8 Vzl
T-1
(T B
1T-1
where the last inequality holds due geometric series of linear operators.
25

---

Published as a conference paper at ICLR 2024
We now show that (I - B)- exists and is a PSD operator.
Lemma F.7. With the parameters in for any PSD matrix M. (I B)- o M exists and is PSD matrix. Moreover, we define
T-1 M, then we have
+
0
0
I B)
M
= Q
+
Q
U.
1 vl
Proof. With Lemma F.6
we have
(I -J-B)-1
M
(T
E
V2 2
V2))
Q
Note that by Lemma
F33
(0:
0
8 8g
E
8 V o Q
3
Q
q²
H.
H
6q
and by definition of U
have
(
0
0 H
V2] o Q N vi
Q
U.
Then, applying Lemma
F.5 and the definition of recursively, we have for all & 2 1,
<T &
V2)) N 1
U.
(F.12)
Summing
F.12 considering the special case of k = 0, we have
O H
0
0 H
I B-B M Q
U
Q
Q
U.
db
0
Therefore, (I B) exists and is a PSD operator.
The following result shows that the inner product (.5) tors are replaced with B.
different by only constant if all B opera-
Lemma F.8. For any PSD matrix M E 2dx2d define the partial sum
R² =
8
о
M.
k=
Then we have
t-1 1
0
1-1
R,
3
2 M
Σ
o
M
U
1l
k=0
k=0
and
0
0
0
1-1 Σ
H
R
<
r
0
H
B
M
1=0
where r =(1 (11-b1)-1
Proof.
By definition of R,, have
R, = (I- - B¹) o M
(I- -) B¹) о M
t-1 (I-B) - B Σ 5 M.
(F.13)
where the inequality holds because B <3 B. Note that by definition of B, we have
I I-B=I- (V1 V2) & (V, V2) II V1 V V1 V2 V2 T, (F.14)
26

---

Published as a conference paper at ICLR 2024
where the inequality holds because V2
V2 is a PSD operator. R. can thus be further bounded
R (I -I-
To
Σ
M
k=
0
0 H
B
M
M
U,
1l
km
where the first inequality holds due to Therefore, taking inner product with
F.14 and the second inequality holds due to Lemma F.6
we have
0
H
0
R
0
H
0
1-1
0
t-1
0
0 H
0
H
8
M
+
4
0
H
M
0
A=0
k=0
0
v
0
[-1
8 M
+
B
M
H
1
H
k=
k=0
0
0
8
M
k=
where the second inequality holds due to Lemma F.5
G VARIANCE UPPER BOUND
G.1 PROOF OF LEMMA D.3
In this subsection, we prove Lemma D.3 We need the following lemmas. The first lemma charac- terizes the recursive formula of C₁
Lemma G.1 (Section E.2 of Jain et al 2018 ) Define
S E[c, @ Ct),
(G.I)
then the covariance matrix C, satisfies
C, = B C,-1 +
Combining Lemma G.I with Lemma K.3
we immediate know that C, is an increasing sequence
with
C = Σ B* E.
(G.2)
k=0
The following lemmas provide upper bounds for M1 and M,, respectively:
Lemma G.2. With the choice parameters as in (4.2). we have
(it
[
0 0
9h
36N(g co)2
M
S
2r
Σ X
N
(1-c)2
i>k
Lemma G.3. With the choice of parameters as in
4.2 we have
M2
S
18k*
36s(g - c5)2
Σ X2
0
(1 - c)² D
We now prove Lemma
D.3
Proof of Lemma D.3
By Lemma D.2
0
0
Variance <
M2 + M2
2
0
27

---

Published as a conference paper at ICLR 2024
r²r
9k*
36N c6)2 Σ 17
r²r
36s c6)2 18k"
Σ
+
+
2
N
(1-c)2
2
N
(1 - c)2
1>k
1sk
= r²r
27h"
18(s + (q - co)²
Σ
X?
2N
(1 (1-c) c)
E>
where the second inequality holds due to Lemma G.2 and Lemma G.3
We remark that due to Lemma K.1 we have 2- proof are smaller than those given in Theorem Therefore, the variance bound Theorem can be fully covered by the result provided in this proof.
2+6
I 7. Additionally, the constants this
2
G.2 PROOF OF LEMMA G.3
We start with upper bound for Σ:
Lemma G.4. Let Σ be defined in G. Then
8 8g
Σ H 0²
@ H.
ōq q²
Proof. By definition of Σ in G.1.. we have
8 x óg x,
gg cx
5² 5g &
Σ = [2 8 S1
E
q² xxxxx
5q q²)
(G.3)
By Assumption 3.3 we have x²
H EH 2H--1/11, so 1/2
1/2 3 o III,
and
Σ Σ H.
(G.4)
Combining G.3 with G.4, complete the proof.
We then provide an upper bound for the limiting matrix C... Lemma G.5. Let C... be defined as
C = (I - 1)--8)oo Σ =
B Σ,
(G.5)
k=0
Then
0 0 H
021
C
< - 1/1
where is defined in F.8
Proof. By definition of Coc, we have
60
og
C (I- B8-
-8-
ΣΣ
8²(I
0
B)
H
8q
V
0
0
0²
U+
U
U
1- 1l
0
4l
2
3 0²
U
U
U,
vl
where the first inequality holds due to Lemma F.6 and the second inequality holds due Lemma Therefore, the inner product is bounded by
F.3
)
0
0 H
2
U
1
1
where the second inequality holds due to Lemma
E5
28

---

Published as a conference paper at ICLR 2024
We now prove Lemma G.3
For the matrix M2, we have the following upper bound:
N-
N
1-1
N-
M2-
A k
[[B
B)
C.+1-1+
+
Σ
A k
N2
K=
K=
N
A
2
0 0
0
Cstt-1
+ +
[82
89 q
H
N-
A
N
H
89
[((0
0
0
88
6g
N--t11
Σ
A
C 00
+
H
A#
0
H
q
k=0
NN-
Σ
A
0²
62
8g
2 H
Σ R=0
A K
N
vil
59
N-1
Σ
Σ
A
(1
[82
8q] 6g
H
NN-1-1
Σ
A#
(G.6)
where the first equality holds due to Lemma G. the first inequality holds due to Lemma G.4 and the second inequality holds because C, is increasing, and the third inequality holds due to Lemma G.5 As A is block diagonal and H is diagonal, plugging (G.6) into the inner product, we
Lemma F.3
have
N Σ
2
H
0 0
5
M2
A
0
k=
[-1
18)
Σ A
i=1
N-1
9k* + 36N (q - co)²
Σ X?
N
(1 (1-
1=0
i>k
9k"
36 co)2 Σ X²
o'r
N
(1-c)²
i>k"
where the second inequality holds due to Corollary K.7 G.3 PROOF OF LEMMA G.2
The following lemma provides an upper bound on C, by its update rule. Lemma G.6. For any t >>000 0, C, can be upper bounded by
(lor
[[2 5g 889
C, o2r
o
8H)
H
R 0
Proof. By the recursive formula 7.5).
we have the following,
C, = Bo C.-1 + +
Bo C.-1 + (B
B)
C
+ Σ
0
0
8
dg
[82 5g
< B. C, +
C
X H + 2
< H
H
8q q²
gq q²
0 0
82 8g
82 5g
3o C, +
C
C H + o²
② H
0
H
Eq 9²
89
q²
2201
[22
8g
682
8g
3B C.-1 +
H + 02
1
vll
89
[
8g
= C, + 02r
3 H.
(G.7)
0g
29

---

Published as a conference paper at ICLR 2024
where the first inequality holds due to Lemma F3 and Lemma G.4 the second inequality holds due to holds because C is increasing, and the last inequality holds due to Lemma G.5 Applying G.7 recursively, we have for all > 0,
8²
5g 2
C 3 R
B
&
89
q
We are now ready to prove Lemma
G.2
With Lemma G.6
we have
N
N-1
M
A
C
Σ
A
N
0=
k=0
N-1
A k
B
8²
59
H
N-1
Σ
A
N2
89
k=0
A=0
NN-1
Σ
A
(
82
89
N--1
Σ
Aith
(G.8)
N2
6g
As A is block alock-diagonal and H is diagonal, plugging
G.
into the inner product, have
1
Mi
22r
+
(G.9)
N
f=0
k=U
r²1
36s ( co)²
18NK
Σ
X
N2
(1 c)2
8>*"
18k
36s(g co)2
rr
N
c)²
i>
where the second inequality holds due to Corollary K.6
H BIAS UPPER BOUND
H.1 PROOF OF LEMMA D.4
In this subsection, we prove Lemma D.4 We first need the following lemma for B,
Lemma H.1. With B, as defined in 7.4 we have
B. = Bo B,-
and
[
8g d
B, = R Bn
B
Bb
@
H.
H
5g
We also have the following lemma for the partial sum of B,: Lemma H.2. Let B, defined in (74
Then we have
14
10
B
<
wwo
w
+
1-c || w 1 ||
b.E
1 c-c
+
|w w
w'llf
+ 4t//wo
w wl
c5
We now ready prove Lemma D.4
30

---

Published as a conference paper at ICLR 2024
H
Proof of Lemma D.4 By Lemma
D.2 it suffices to bound the inner produce of
with M3
0 0
and M1 separately. For M3. by Lemma H.1
we have
N-1
N-1
M3
1
B 8
Σ
A
N2
0=
k=0
N--1
N
1
Σ
A
K+
Bp
Σ
A
k+s
N2
K=
h=
Σ
0 H
B. 1-2-1-1 1-t
NN-1
Σ
A k+t
(Bo
bg
x
N-1
Σ A k+t
(H.1)
N2
0
We also note that
(wo- w w*)T
(Wo - w')( w')
Bo
(wo- w (Wo w*)T (Wo- w (wo w wT
=
@ (wo - w "(w - ww) W
(H.2)
Hi is diagonal and A is block diagonal, so plugging
H.I and
H.2
into the inner product, we have
0
d
N Σ
2
M3
0
N2
k=
0
0 H
d
N-1
0
B
1--1-11
Σ
X
A
(H.3)
N b=
q
im
km
By Corollary K.9
have
N
[
Effective Bias =
A k+s
2N
[
k=O
8(c0/q)20
4s2
N282
WW
w
11||
H-1
+
N2
[|(I
8HH)'/((w)
(wo w II +
16c
100c
+ N282
8H) 0/2 (wo-
w
+
| (H) - w 11
N2
c)2
9(1 c)²
[ (1-
q - cō H
(Wo w*)
2N - c6)2
1 - c
c9
2
11
I 1 - H
(Wo - w*)
HH::00
K can be bounded as
N
(d)
K
B BB-1-1
Σ X3
Σ
A
N2
H
16
9k* *
36(g - 2 N2
Σ X
Σ
0 0
B
N2
(1 2)2
H
1b
36(g N2
[
0
9k*
Σ
.B.
N²
(1 2)²
0
H
< /rr
9k*
36N ( co)2
Σ X2
14
Wo
w
11 b.R
N
N
(1 2)2
31

---

Published as a conference paper at ICLR 2024
10 |o
1 llwo
w
Il
+
co
w
ata-
+
+sslwwo
w w'Il
(H.44
q
where the first inequality holds due to Corollary
K.6 and the second inequality holds due to Lemma
H2
For M4, we have
N-1
N
NN--1
N-
M =
1
A k
((B - B) Batc-1)
Σ
A
N
km0
km0
N
1
0
0 H
Batt-l
NN-111 Σ
k
82
N
N-t-1 t-1
Σ k=
A
k
T
(H.5)
N
q²d
k=0
where the first equality holds beause B Bs+t-1 H is diagonal and A is block-diagonal, so plugging (H.5) into the inner product, we have
B and the inequality holds due to Lemma
N-1
d
N
(-1
2
H 0
M
S
0
B
B
Σ
N2
H
9
1=1
Amm
0
BB+N-1-1
d Σ
X2
k
[6]
N2
H
1=1
k=0
9k*
36N (g- c0)²
Σ X2
Σ
N-1
0
0
.B B
N
(1 c)²
0
H
kDk*
9k*
36N (g - c5)²
0
0
B Bott
(H.6)
N
N
(1 c)²
H
k>
where the second inequality holds due to Corollary
K.7
Note that
N-1
1
8+N-1
0
0 H
0
Bett
B₁
0
H
1=
1=0
14
10
S
Wo - w 111
+
Wo w w'
1-c c
9 cō
||
w w0ll
4(8 + N)[(
w 11
H4
(H.7)
where the first inequality holds because B, 2 O, and the second inequality holds due to Lemma Plugging (H.7) into (H.6), combining the result with (H.4) we have
H.2
( 2
1
H
Bias-
M3 + M4
0
0
Effective Bias +
v/
9k*
+
36 (q- co)2
Σ x²
14 wo w
w'IlB
2N
(1 (1-c) 6)2
1 [wo - w 11
10
c
ll
w w"IlP,rxx
+ + w 1|
H E.tt
q c5
vr
9k*
36N c6)2
/ wo - w'Ili
14
10 +
+
x²
|| - w 11 E
2N
N
(1
- c)²
1 -
c
W
+ +((s+ + N) w'll
9 c
32

---

Published as a conference paper at ICLR 2024
Effective Bias +
vr
9k*
36 (q
c6)2
Σ 1
14
wo w
N
(1 c)²
1sk
1 Wo
10
w w Eik
c
Wo w w'lli "le + +(18 N)|lwo- w Hu
od
where the second inequality holds because 4s||wo
w" w"llit I 4(s N) -
-ww w
We remark that due to Lemma K. we have 2-08 2+ I y. Additionally, the constants this proof are smaller than those given in Theorem 4.1 fully covered by the result provided in this proof.
2
Therefore, the bias bound in Theorem 4.1 can be
H.2 PROOF OF LEMMA H.1
The recursive formula B, Bo B is proven in Section B.2 of Jain et al. (018). We further have
B, = Bo B B
B
+
(B
B)
B
0
0
82
89
3 B.o1.11
B
X
H
0
69
q
3 B o Bn +
0
B
B
18-1-k
6 5g 89 q²
H
H
62
0g
B Bp
B
1
H
H
where the first inequality holds due to Lemma applying the bound.
F3
and the second incquality holds by recursively
H.3
PROOF OF LEMMA H.2
Note that B, B' Bg by
7.4)
By Lemma F.8
we have
Σ
8
B r
H
Bo
r
H
A' (H.8)
H is diagonal matrix, and A is block-diagonal matrix with each block being A,, H.8 be further bounded by
1
H
B
r
[1)
k=
14
10
S r
Woo
w 11?
+
1 I-c
||wo w 11 ||
5
Wo
w'
1 + 4t|lwo w wI 1
c5
where the second inequality holds due to Corollary K.IT I PROOF FOR THE CLASSICAL SETTING
In this section, we prove results for the case of finite dimensions. Before prove the theorem, first note that with the parameter choice in (4.4) and R = d,
Vō (H()
1
2/1
4'
So r 4. We also note that with 7/4 233, we have
(1 - 2)²
(1- c)2
(1 c)²
(Vq- cō + /elg -))2 (1+ 2cd + 2 olg
-8)(8 cō)
(1 + c)q
2cd
33

---

Published as a conference paper at ICLR 2024
a2)2- 2a(aò + (1-10) a)7) - 2(2a 1)6 (1-a)0 + an
-)1
2(1 x)) -
2,3 7 μ.
α7
where the first equality holds because 2/c(q - () - co) 2 0, the second equality holds because
c= 2a - and q ad + (1 - a17, and the second inequality holds because - (.) 2 0. That is to say, there is no cigenvalue in the region of > kT.
The main idea of the proof is similar that of Theorem 4. We decompose the excess risk into variance and bias, and then characterize M1. M2, M3 and M4. The following lemmas provide
upper bounds for the inner product of
with M1. M2, M3 and M1.
0
0
Lemma 1.1 (Modified from Lemma
G.2
With M1 defined in (D2),, we have
128o
M1
N1 c)
Lemma 1.2 (Modified from Lemma
G.3
With M2 defined in (D3).. we have
H
36o2d
M2
N
N
Lemma 1.3.
With M3 defined in (.4). we have
H
0 0
100
(1 - c)s
504
0
M3
S
N2 c)2 exp
||wo - w" +
N2 c)
|wo w"
Lemma L.4.
With M4 defined in (D.5). we have
H
504gbd
M4
|| 1000-w11p w
N2 c)
With the lemmas above, can prove the upper bound of excess risk in the classical setting.
Theorem 1.5 (Restatement of Corollary 4.4). Under Assumptions eter choice (.4. we have
3.1 3.2 and 3.3 with the param-
100
(1 c)s
E L w NN) L(w") -
exp
|w
N2 - c)2
2
360 d
128
1008I0
||
w 1
N
N2 c)
N2
Proof. By Lemma D.land and Lemma D.2
we have
E [. (ws:s+))) L (w*) s
Mr
M2
M3 M4
(I.1)
0
Substituting the results of Lemma Lemma
Lemma
and Lemma
into we get the
desired result.
We remark that due to Lemma K.I we have 1- - c 2 8. Additionally, the constants in Theorem I.5
smaller than those in Corollary 4.4 Therefore, Theorem 1.3 can fully recover Corollary 4.4
I.1 VARIANCE UPPER BOUND
The proof for Lemma 1.2 is straightforward given Lemma G.3 and the fact that there is no eigenvalue
in the region of > k., Below we provide the proof for Lemma L.1
Proof of Lemma I.
According to G..9
in the proof Lemma
we have
[H
[H
0 0
2
d
s-1
N-1
2
M
S
(1.2)
N
9
1=0
k=
Similar to the proof of Corollary K.6
have
34

---

Published as a conference paper at ICLR 2024
(a) When i i k!
88
A t
(8)
S (1 - (1-c)
==
0=
(b) By (.24 and (6 when 1 <iskt.
007
32
- (1 - (1-c)x²
==0
1.2 can thus be bounded by
H
0
M1
S
40
2
N
A! ++
2
N
1=1
j=0
k=0
40
X
Σ
X2
32
N2
(1 - (1-6)A
(1 - c)>
iskt
i>
[16ht + 128(d - kt]
N2 c)
128o²d
N2 c)
where first inequality holds because r = 4 and due to (.2) and the last inequality holds because the coefficient 16- < 128.
1.2 BIAS UPPER BOUND
We first provide list of lemmas modified by considering only eigenvalues A; with S kt: Lemma I.6 (Modified from Corollary K.6). Let A, be defined in (E.I). Then for all j 2 0,
2
A +
S 9d.
Lemma L.6 follows directly from the corresponding results in the overparameterized regime, and we do not provide the proof here. Lemma 1.7 (Modified from Corollary K. .. Let A, be defined in E..Ip Then we have
Σ
Σ k=0
A
H]
1
c]- exp (- (1 c)s)
100
| w' H-
1
(1
2
1
Proof. By Lemma K.8
(a) For all i < k4, we have
N-1
Σ
A
H]
2
4
2* - (0889))
4
x
x
where the second inequality holds because (có/g)² < e S Vc. (b) For all kl
i < ke, we have
2s|c(1 522)) + 4 82,
1o(1 - 821)]s/2
4
< 2 Σ Je(1-
+
[o(1 - -5)a))//2
82:
j=0
|c(1 - -8A.) - [c(1 - 622)]a/2
4
[c(1 - -82a))=/2
[c(1 51:))2/4
8);
35

---

Published as a conference paper at ICLR 2024
2 |c[1 <21 -
- [c(1 -81,)
82;)]8/2
4
[o - 8x,]]
82,/4
81,
8/c(1 511,11/44 - 4fc(1 -87)]'/2
8
-
[c(1 -82;))
(1.3)
57,
87
where the first inequality holds because [c(1 - 6x,)] < [e(1 8).) the second
inequality holds because 1 - [c(1 5x,)] 1/4 2 1 - (1 52,) 1/4 2 52,/4, and the last
inequality holds because [c(1 8Aa)]a/2 2 0. We thus have
N- Σ
2
4
|c(1 - -x ?
A +
20|c(1 - Sx,)]
+
07;
64
64
[c(1 -5 -
c²/2
8 82
8²
where the first inequality holds due to Lemma K.8 the second inequality holds due to and the last inequality holds because c(1 - 81,) S c.
L.3
(c) For k < i kl, we have
10
2sfc(1 - 51,))a/2 +
[o(1 - -8x;)///2
1-c
S 2 1-1
10
Σ
[d(1 - oX.)) +
[c[1 - 8x,)]&/2
1
1=
2 |e(1 oA.)) - [o(1 - 62:)]8/2
10
[c(1 5X2)]0/2
1 - 1c(1 - 6xx))1/4
1 1-c c
< 2 le(1 - 522,) - [c(1 - 82,))s/2
10
1- [d(1 - d1Ae]s/22
(1 c)/4
8lc(1 -8x,) + 2/c(1 0x2))0/2
10
[c(1 82,)]0/4
(I.4)
1-c
1
where the first inequality holds because |e(1 - 8A.){
8/2 < |e(1 - o the second
inequality holds because 1 1 [c(1- 1/1 > 1 1- //1 2 (1 c)/c)/4, /4, and the last inequality
holds because [c(1 - dx:)]a/2 < [c(1 - 8x..]s/44 We thus have
N 1
[1]
2
10
[c(1 - 5x2.)(/2) 2
Σ
A ++
(2s(c(1 - 82,)) +
[1
I c
1
100
100
[c(1-8x,]]'/
c²(2
(1 (1-c) 0)2
(1 - c)²
where the first inequality holds due to Lemma K.8 the second inequality holds due to and the last inequality holds because c(1 82,) S c.
I.4
Concluding all the above,
N-
1]
1
2
Σ
A
4
64
100
e212
82X2 c²/2 +
6²/2
82X2
(1 - c)2
kt Heisk
i>k
222
drwf (1 c)²
64
c//2
100
6//2
(1 c)
(1 c)2
iskt
Ni ciss
100ca/2 d
Σ A = 100c0/2
<
|| - w 1|
(1 - cc) i=1
(1 11-c) c)2
36

---

Published as a conference paper at ICLR 2024
100
(- ([(-))))) -|wo - wl 2
(1-c) exp
where the second inequality holds because 8Λ, 2 1 c for i I k. the third inequality holds because the coefficients 4, 64, 100 are bounded by 100, and the last inequality holds because c²/2 exp(- (l))s)))))
Lemma 1.8. With B, defined in (74). we have
0 S H
56
B
Wo
w
1
Proof. By Lemma H.2
taking r = 4, we have
0
B
S
56
Xmay +
40
Σ Xmuy
84
1-c
k=
Ksk
kliisht
56
40
Xuu?
1
iskt
ktiish
56
Wo
w 11
c
where the first inequality holds because 8A; 2 for S kt, and the second inequality holds because the coefficients 40, 50 can be bounded by 56.
H
We are now ready to bound the inner product of
with M3 and M4.
0
Proof of Lemma 1.3
Similar the proof of Lemma D.4 we have
H
0 0
M3
0
N-1
1
A 1
Σ
A i+
[]
N2
k=
d Σ
N
2
0
0
BB----1
Σ
A
k++
N2 1=
0
H
1=1
k=
100
(1 - c)s
0
0
N2
Cjz
exp
2
|
w
H
N2
H
B 1- 1-1
9d
t=0
100
(1 c)s
9dd
56
N2
c)2
exp
2
|Wo
w']l
N2
1
||wo w 1/
100
(1 c)s
504ghd
exp
|
w l
|wo w 12:
<2 c)2
2
N (1
c)
where the second inequality holds due to Lemma L. and Lemma L6 and the third inequality holds
due to Lemma L88
Proof of Lemma 1.4
Similar the proof of Lemma D.4 have
H 0
0
0
0
M
B. B-
x
0
N2
H
N-1 1
0
0
B B.+N-L-1
N
H
37

---

Published as a conference paper at ICLR 2024
9dd
8
Σ
N-1
0
0 H
B,
N
1=
9
56
504
Wo
I1
|Wo
-w'l
N
N2
-
where the second inequality holds due Lemma L.6 the second inequality holds because B, and the last inequality holds due to Lemma
0.
J PROOF FOR THE ONE-HOT DISTRIBUTION SETTING The choice of parameters is as follows:
7 E (0, 1), d (0, 8 (0, a 1+
(J.1)
We now present the excess risk bound:
Theorem J.1. Under Assumptions 3.1 3.3 and 3.2 with the parameter choice of J.1 assuming N - c) 2 2, we have the following upper bound for the excess risk:
B[L(Ws:s+ +:s+ N)] L(w") s 2 Effective + EffectivvBBas,
where effective variance is bounded by
27k
126
Effective Var S T²T
+ 18(s+
Σ
X?
+
|/
w
2N
N
H
12k
90
18
+
|Wo w
+
Woo
w
H-1
+ +36,2N22 2////o w w1
Afie*
and effective bias is bounded in the same way as Theorem The constant is formally defined
4.1
(J.2)
maxisisa( (U,)22
Note that
(U:)22 S 9- 08
5 7
2(1 - 2
so the upper bound of r is given by
1
1-7/2
The proof of Theorem J.I depends on the following lemmas:
Lemma J.2 (Modified from Lemma G.2
Let r be defined in J.2.. Then we have
0 000
18k*
36s(g co)²
M
S
d²r
Σ
x
N
(1 (1-c) c)2
1>
Lemma J.3 (Modified from Lemma
G.3
Let r be defined in (.2) Then we have
[
0
M2
S
2r
9k*
36N co)2
x
0
(1 1--c) c)2
1>
Lemma J.4. Let r be defined in
J.2
Then we have
H
0
126
90
9(1 c)
M2
Wo
|/o
w/
0
0
N2
36(g
22
Wo
w
+ EffectiveBias,
(1 (1-c²² c)2
where ITTectiveBias is the same one in Theorem 4.1
38

---

Published as a conference paper at ICLR 2024
Lemma J.5.
Let r be defined in
1.2
Then we have
H
0
0
M4
N
r
126
Wo
w
+
1-c
90
ww
wI|
+
9(1 -c) c)
cd
w "I]
oiE
36(g
c5)2 + N)
Wo w H2
c)2
Proof of Theorem 1.1
Note that the excess risk is
H 0 0
M1 M2 + M3 M1
0
so the upper bound can obtained by combining Lemmas L.2 and
Notations. In this section, for any matrix M
I 2dx2d denote
Mn
M12
M
ER 2dx2d
M21
M
where My E Raxd
J.1 ANALYSIS OF FOURTH MOMENT
In this setting, for any matrix M
1adx2d have
oq -
122 6g q²
E E Vajo M
& (H
M22)
diag(Ai (M2)) (M 11,..., A,, )d))
0g
Lemma J.6 (Modified from Lemma Then
F.7 For any PSD matrix M E 2ddx2 define Q = T
BJ- o M Q + diag (Q22)11
Q22)dd Ua (U.)22
U
(U1)2
Proof. By Lemma F.6 we have
(I BI-B) o Σ
(T
V @
V2))* oQ Q.
Note that
[82
5y q²
B V
diag (iag(A((Q22))) . (z(Q2z)aa)
åg
so by definition of T,
T E V 3 V, Q = (lag((Q22))
(((Q222)11 U1.... U,,...(QQQQ))uuU (Qz))au
We can similarly prove that for all k 2 1,
(T V2))* Q diag( Q22) (U, 1/2 U1, (Q22)11 (Ua)az Ua)-
Summing the above, we have
(Q22)1 U (Quz)dd U2 (Ua)22
(I- o M = Q + diag
(U
Lemma J.7 (Modified from Lemma E88. For any PSD matrix M 2dx2d define the partial sum
R²
B M.
Then have
1-1
(B o M)22
(( o M)222
R <
M
diag
Ui....,
Ud 1 - (U1)22
1- (U1)2
k=
k=0
and
T52
ög
((3 o M)22 1- 1-(U))
Aa((B* M)22)ad
V
& V2
<
o diag
5q
9
1- (Uz)22
39

---

Published as a conference paper at ICLR 2024
Proof. Similar to the proof of Lemma
F88
we have
B
M 3 (I -
To
Σ B e M
k=0
diag ((B* o 2222111
(B o M)22)ad Ua
B
M
U1
1- (U1)22
1 (Ua)22
k=
k=0
where the equality holds due to Lemma
J.6
We thus have
[02
ag
B 2
V2lo
Σ B* M
1
diag (A1((B*
M))22dd
0g
km=0
R 0
X1 (U
da (aa22 ((B* M)zz)dd)) (U2)22
diag
(BB* M)22)11
1 (U1)22
k=0
[82 ög
t1 AI 2)22)11
\e M)22)dd
8 diag
óq
q²
1 - (U1)22
1 (Ua)22
J.2 VARIANCE UPPER BOUND
We now provide the proof of Lemma J.3
Proof of Lemma J.3 Note that
0 ([0²
5g)
C. = (I -.-B)
B) 1 02 -I---
3 H
[gg
q²
(U1)22
(Ua)22 Ua
o² U + diag
U
(U1)22
(Ua)22
U1
Ua
= o
(U1)22
(U
where the second equality holds due to Lemma
J.6. We thus have
og q²
(U,)))
Aa (a(22)
E V 2 & Vzl o C 1 0²
@ diag
(J.3)
(U1)22
(Ua)22
Therefore, M2 can be bounded by
N-1
N 1-1
N
T
M2
1
k
[B- Co+c-1+ 0 Σ
Σ
A
N
1=1
0=
k=
N-1
N --1-1
[N NN-111
Σ
A k
E V & Vzl a Cos + {
Σ
A#
N
k=O
N
2 88
Ai (1122)
(2)222
N-
T
Σ
Σ
A *
8 diag
+ +H
Σ A k
89
(U1)22
(Ua)22
k=0
NN-
82
5g
A1
Aa
Σ
A *
2 diag
Σ
A /
N
59
1 1-(Un) (U1)22
(U))22
K=
N-
82
8g q2
Σ
&
X H
Σ k=
A k
(J.4)
äg
40

---

Published as a conference paper at ICLR 2024
where the first inequality holds because B - B E
V2
V2 V2
E
V2l and
B++t-1 I Co. the second inequality holds due to (I.3). and the last inequality holds due to defini-
H
tion of r. The inner product of M2 and
can thus be bounded by
0
H 0
0 0
o²r
d
N-
0
M
N
q
9k*
36 (g c6)2
r²r
X
N
(1 - c)2
1>k
where the second inequality holds by deduction similar to that of Lemma G.3
Lemma J.8 (Modified from Lemma G.6..
For any t 0, C2 can be upper bounded by
(18
802
5g
C, 02r
B
q² H
89
Proof. By the iteration formula C, = B Ct-1 + Σ, we have
C, = Bo C,-1 (B B) C,-1 + E
3 Bo C,-1- - B[V, V % V2) o C.-1 + E
882 89
3 Bo C.-1 E V s V2]
Coo + o²
H
06
q²
882 óg
A1
Ad
3 Bo C,
0²
@ diag
6q
q
(U1)22
(Ua)22
óg q²
< B C - r²r
s H,
89
where the first inequality holds because B B V @ Vz). the second inequality holds because
Ct- 3 Co and Lemma G.4 the third inequality holds due to (.3)). and the last inequality holds due to the definition of r. lterating the inequality above, we have
(lor
5g g
C. 1 02
B
2 H
As the bound for C, is exactly the same the bound given in Lemma G.6 J.2 in exactly the same way as Lemma G.2
can prove the Lemma
J.3 BIAS UPPER BOUND
Lemma J.9 (Modified from Lemma
For any 2 0, B, can be upper bounded by
62
5g
B, < 8 Bo
B
q²
(B2-1-))22)
k=
Proof. By the iterative formula B.
B o B,-1, we have
B, Bo B
(B B)
B
1 1o B
B
E E & V B
T22
5g
= BoB,.11 B +
2 H
B 122)
ōq
q
t-1
82 8g
1 B o Bg
+
X H O (B (B(-1x)22)
8g
km
where the first inequality holds because iteratively applying the previous inequality.
B z V
X V2l. and the second inequality holds by
41

---

Published as a conference paper at ICLR 2024
Lemma J.10. We have
A [
Σ (BB) S r Σ
0=
Proof. Note that
Σ
(B,)22)a
(B' o BBo) 22
t=0
(B' o BB)22) (U.)22
B B
22 H
1- (U,)22
w??
2
(U
)22
t=0
2
2
Σ
t=
where the first inequality holds due to Lemma 1.7. and the second inequality holds due to the defini- tion of r.
Proof of Lemma
J.4
By the bound for B., we have
NN-1
N
N-1
N 1
M₂
B
1 N2
A
k++
Bo
A k+
N2
k=0
k=0
k=0
k=
N--1 1
((
(102
([02
N Σ
Σ
A k+t
8 (H ④
B 1-1-))2))
h+!
N2
K=0
H
0
so its inner product with
is
0
H
0
N Σ k=0
A kts [
2
M3
0
Effective Bias
d
N
0 q
2
B (B--1-)22)): 84
A
N
t=
k=0
The Effective Bias is the same the standard case. K can be bounded by
36(g c6))-c6)2NN² N2
K
(B. (B..
(B.-1-))2)
N2
(1 - c)²
i= +1
1=0
36(g 22
9
(B.- (B.-1-)22) +
(B BB-1-1)22)H
N2
(1 (1-c)- c)2
1=1
1=0
i= +1
t=0
126w?
90w2
9(1 c)m?
36(g -0)3
N2
1-c
(g - )
(1 (1-c)- c]2
LigA
Reigh
4>b"
126
90
9(1 c)
Wo
w" 2
HH1 +
l|wo
w 10
Fiat +
| w 112 H-
N2
1
cō
36(g - 2 s
|
w
1
Hr (
(1-c0 2)2
42

---

Published as a conference paper at ICLR 2024
where the first inequality holds due to Corollary K.7
and the second inequality holds due to Lemma
1.10
Proof of Lemma J.5
For M4. we have
N-1
NN-1-1
N--1-1
M4
1
Σ
Σ
A
((B
B)) Bstt-1)
Σ
A
N
N-1
TN-1-1
NN-1-1
T
Σ
A
(BIV2 8 Vel o B B
Σ
A
N2
0=
k=0
= N2
N-
Σ
N
Σ
A
1+
82
fg
q
og
N (H C (B
(Bet-1)22))
N---1
Σ
k
T
H 0
where the incquality holds because B 3 E V2 is thus bounded by
X V2l. The inner produce of M, and
0 0
H 0
0
M
N-1
N-t-1
2
1
X2
(B 1B,+t-17 1- 122)
Σ
A
N2
1=
1=1
k=
N-1
36(g 22) N-1
1
9
ΣV
(B )22)
(B (Bs+t- 122)
N2
(1-
k=
1
R-
S+N-1
d
36(q - 22
s+N-1
9
(B.))2) +
((
N2
(1 c)²
t=1
1=0
i= +1
1=0
126
90
9(1 c)
w -
+
Wo 11 lixt
+
|o w"
1|2 1|
Nº
1 1-c c
- c5
36(9- 25)2 + N)
Wo - w I|
cl-
where the second inequality holds due to Corollary K.7 the second inequality holds due to Corollary
K.7 the third inequality holds because >/1 (BB.t-1)22) Σit0 ((Br)22) and the last
inqqullity holds due to Lemma J.10
K AUXILIARY LEMMAS
The following lemma summarizes properties of auxiliary parameters y and c relation to model parameters ar B,y y and 8.
Lemma K.1. We have the following properties regarding q and
(a) We have 2a 1, and
1. Moreover, 8 < 1 - 20.3 S 23.
(b) We have d 5 q < (1 + c) Thus, 9 - 8 s c(g - co).
(c) We have
q cd
7 5
q 8
7 -
1-c c
2
1-c
2
Thus,
q cõ
8
< 7
1
Proof. We first recall that c a(1 - 9) and q aδ + (1 a)n-
43

---

Published as a conference paper at ICLR 2024
(a) Substituting == (1 a)/a into the definition of we have
1 (
1-a a
a ) = 2a - 1.
c= a
Note that 3 E (0,1), so a = 1/(1+ + 3] E (1/2,1). Therefore, c= 2a E (0,1). Moreover,
1 1-c= a(1 -8 =
a 2 (1 aaB + aB 3,
where the equality holds because < 1. We also have
1 1 c- 2(1 - a) 20.3 s 23,
where the inequality holds because a <
(b) we have
q = ad + (1 - a)y ô = (1 (1-a1) a)(( 6) 2 0,
(K.1)
where the inequality holds because 7 2 6 and a E (0, 1). We also have
6
q -1 (1+c)0 aδ + (1 a1-a)7- -2d (1 a1- aδ a (3> 6) -a a
< 0,
1/
where the third equality holds because 1 - a = o.3, the fourth equality holds because B (1)r),, and the last inequality holds because पो 1. We thus have
(q q 6) c(q - -c6) = - c)lg - (1 + c)o] S O.
(c) We have
cō aδ + (1 - a)7 - (2a - 1)6 (1 a (7 + 00)
(K.2)
Combining
K.1 and K. with the fact that
c 2(1 a)), we have
q- cō 7 6
q- 7- 6
-
2
1 c
2
Note that S 7. so
q - cō
8 <
<
7.
1 1
Lemma K.2. Let F1, 22 be defined
E.2 and E.3
Then we have
(a) (1 zi 21 22) c
(b) (c (c x2) =(( -
(c) (1+21)(1+z))
2(1 + c) - c
(d) (cō qr:)(c6 9o2) = c(q- - 6)(4 - co).
Proof. In the proof, we will use the properties x1 x2 1+ c qd, and 01 c(1 -82g)
extensively, which follows from Veda's 's Theorem.
(a) We have
x2) = 1- 1- = (q- co)A
(b) We have
(c-xi)(c-a) = -- = cly -0)
(c) We have
q + c(1 82,)
= - c5)
(d) We have
(co - (0 q = c² 2 - cōq(œ1 + x2) + 92 2212
= 208 - cōg(1 +c - q>i) + d2 c(1 - 52,)
<(g 5) cō)
44

---

Published as a conference paper at ICLR 2024
Lemma K.3. For given PSD matrix M, we define the following sequence of matrices recursively: Ro = 0, and
R Bo R + M, t20 0.
(K.3)
Then for all t 2 0, we have
R Σ B M.
(K.4)
k=0
Thus, R2 is an increasing sequence:
R 3 R1 3
R.
(K.5)
Proof. We prove K.4) by induction. When t = 0, K.4 holds trivially. Suppose that K holds
for t. By the recursive formula K.3
we have
1-1
R = Bo R. + M Bo
Σ
Bh M +
Σ
B M
Σ
8* o
M,
k=0
where the second equality holds due to the induction hypothesis. Thus, By (.4). note that
K.4 holds for 1.
R R. Σ B
M
Σ B M B
k=0
k=0
where the incquality holds due to Lemma
F2 c). Therefore, R. = R4+1-
Lemma K.4. Let {M,)21 be a sequence of PSD matrices and 8, N be positive integers. Then
Σ
Σ
A
A-'M,
M.+
Σ
Lki++1
k=
N-1
N-1
N-1
NN --1-1
N-
T
=
A
k
M
Σ A k=0
+ Σ
A
(M. (M. - Bo M.tte)
Σ
A
K=0
k=
k=0
Proof. For 8,8 + 1, I,..., + +N-- -2, have
8+N-1-1
8+N-1-11
8+N-1-2
T+NN---2
A
M
Σ
A#
Σ
A (AMAT)
Σ A
1=0
k=
kmO
8+N-1-1
Σ
AA9T
Σ
AAMT(AR)
j==1
N
+4N-t1
Σ A +
Σ
a+N-1
++N-1
= Σ
M
Σ
k=#+1
k=t+1
Take the sum over and we have
s
N
Σ
Σ
A
K
k
M,
Σ
M.
k=H+1
k=H+1
6+N
++N-1-1 Σ
s+N---1
-Mo+N-1+
Σ
M,
Σ k=0
A
t=
k=0
45

---

Published as a conference paper at ICLR 2024
2-
T+N-1122
T+
Σ
Σ
A
k
(AMAT)
Σ
k=0
K=
N-1
N-1
T
s+N-1
++N-1-1
S+N-t-1
T
Σ A
M
Σ
A
+
Σ
Σ A=
A k
M
Σ
Ks
0=
1=
k=
N+N---1
T+N--11
E
Ak
(AM,
(AM-IAT)
Σ
A k
0=0
A=0
N-1
N-11
S+N-1 Σ
-
Σ K=
A
M
Σ
A
Σ
A k
(M. Bo MI-1)
Σ
A
k
K=U
N-1
N--1
N-1
N--t11 1
N-
Σ
A
k
M,
Σ
A
+
Σ
A
(M&+e- B MoM-2111
Σ
A
A=
LK=0
k=
k=
where the second equality holds due to change of index, the third equality holds due to the definition of B, and the fourth equality holds also due to change of index.
Lemma K.5. With A; defined in E. let 21 and Ta be the eigenvalues of A, defined in
E.2
and
Then
For all i S 14, we have
(c5/a)
Σ
Afth
[8]
[8]
2 (c5/g))
[9]
A
For all b < x Ri we have
Σ
A + [8]
3
le(1 5x,)1/2 + 5jfc(1 - -22:](6-11/2
S
[
A,
For all F <is kl, we have
Σ
--1
A *
66
S
3 A
|c(1 -5x,)//22
1-c d
-j((( - 6x.))
For all i kt, we have
0 Aith
Σ
[8]
3
1
1-
(1
1
-
2 !
cd
Xo
q co di [[
9
X
1-c
c
Proof. Note that
57 q
[8]
= (A - -A!tt) 1
1/4 1
+
= (A} - A (1 101-AA11 A1
k=
1 (A 1u + (A))12 (Att)) 111 (At+9)22
(K.6)
A (A 11 + (A: 112 (Att)), " " (A
Combining Lemma E. with K.6 we have
8
A k
= X, ((A))) + (A))12 - (A!+*) )1 - (A))))12)
k=0
1
+ (1 - 5Ax) 22 2
21
H+t
x22
22 x ++
H+1
(1 05x,)
.22 21
32
32
T2 σ1
46

---

Published as a conference paper at ICLR 2024
1 (1 52; - x1 x1))2(111 - x/2) - (1 - 52; - 12) (1 x1)
(K.7)
X
22 I1
For i S kF, note that 2122 = c(1 - d\;)) and 22 S c by Lemma E.2
so we have
1 8λ: S क1 12 S.
(K.8)
Thus, the upper bound of K.7 is given by
h-1
1
(ō); + 21 1)sq (1 x/2 (ō); + + 1)sq xx)
Σ At
9
122 - I1
1
z
(dd, + 31 - -1) - -1) 2
+ (1 xt)
X
8/2 21
1 - x
+ (1 x²1) = 5z (1 - =11)
5x
$ (o)) + 11 -1) -1
S -
(K.9)
I1 where the first inequality holds because 8A + 21
A
1 I1
1 2 and Z2 2 2₁, and the second inequality
holds due to Lemma 12 Note that
1
22
1 12
(1
(q - co)A:
1 ob dd-voly (d(l-b((1 (o)
1
c(c ) 5) q cō
2
9 (q co)A;
1
S
(K.10)
qd
where the second equality holds by Lemma K.2 the second inequality holds because c(g 0) cō and 2 6. Note that in S x2 S co/g so K.9 can be further bounded by
a), the first inequality holds due to Lemma E.2 and
Σ
A
6 9
6
2 (c5/a) - (c5/9)', X;
where the second inequality holds due to (K.10).
The lower bound of (K.7) is given by
Σ
A
88 a
1
(8); + 21 - 1)a5(1 x2)) + (6), + x2 1)at(1 - x55))
2
A
I2 - I1
1
-(6); + - 11)= + (6); + 322 -1)= 1 2/
(K.11)
A
3/2 I1
where the first inequality holds because 8Λ; + - 2 and 11 S 22. If 2 1, then
(dA: + x1 1)2/ + (ō\; + x2 - 1)a1
82 - 31
22 x 1-1
= -57 +.1 - 1)
+ (1 -8x;)aa--1
82 - 11
(c0/9)²1
2 -6A; + -1 - 1)x2 05/4 31
2102- (1 - 822 (c5/g)) 11
c8 cō/9- - σ1
-11 - 5Ax.) c 02
(c5 (1//1)-11
(K.
cō/9
where the inequality holds due to Lemma J),). Note that
K.12 and the last equality holds because 21 c(1
C- x2 = (1 - -8x))
(c- (2662//66/g x2)
q2 11--5M0 -1,-5 -22) x2))
(1 - d)i)) cō/9 x1
(c0/g x 1) x2)
clq -8)(0 co)
47

---

Published as a conference paper at ICLR 2024
q²
(1 1 8.
(Vg cō
/clg- 0)}² -
Vdla 8)(9 cō)
(
<gg (g - c5)
q²
/og- 0](g cō)
4
(cd
vdq 8) co))²
(1 /1 -dy- 6) q cd
eq²
2²8²
cō 9
.
(K.13)
eq2
where the second equality holds due to Lemma
K.2 d), the first inequality holds due to (E.6) and
Lemma E.2 the second inequality holds because cō vdly co) S cō and c(q 6) S g co.
and the last inequality holds because S q. Therefore, substituting (K.12) and (..3)) into (K
we have
Σ +
5
1- 22
2((0//)3= 2
2 (c0/g)/ X,
de
1
where the second inequality holds because 1 - 22 S 1. If = 0, then
1 x (od, + x1 1) + (oλ + 32 1)
1
2 0,
122
so the upper bound holds trivially.
For A < S kt, the upper bound of (K.7 is given by
Σ AC 0=
0
(1 5A
xn )=2
-
-1
52: - x2) x1)
x;
-1
1
x1 xb) + + -11)
X
2
+ D2
1 (1- - 222) x (1 21)
- 02
2
32 - 21
1
{1 x²/) + +z/(1
x1)
1- c (28 - -)4
+
X
2
2
22 o
(1 -
#1)
+
(1
x1)
12 + x
52
31
2
T2 21
2
|1
| ||
|1 c (28 a)
2Λ:
2A:
22
[1 -
x1
+
x/bl
2/ w
|
(K.14)
x2
Σ1
2
42 Φ
where the second equality holds because 21 +
=
1 + c
gd. and the inequality holds due to
triangle inequality. Note that [1 x²
= |1 - x
S + [xb]
< 2 because
S 1. We can thus
bound 14.14 as
A
j+
| + [
(28 9)Ab1
2/1 z
| + |لا||
2
+
X;
2),
I22 I1
822 21
2
2
lc(1-
821))5//2
11 - c (25
7)>al
[2]fc(1 52x))(0-112 1)/2 +t(e(1 -xt))
2X,
48

---

Published as a conference paper at ICLR 2024
1 (26 q)Ail.
=
[c([ 82,)](-11/2
A
2
| c - (28 7)dil
-tfe(1 - 8X,)) [e(11-8x]]((11))
11/2 fe(1 821))3/2
(K.15)
A
2
where the second inequality holds due to Lemma
K.13 For kt <is Rt we have
1 (25 q) 8A; (26 q)>; (q 8) S 6As,
where the first inequality holds because - c v Oi2 and the second inequality holds because q S (1+ c)ò 26. We also have
1 - (25 - a) 2 (q - 26) 2 (6 - 26) = -
where the first inequality holds because Therefore,
c 2 0, and the second inequality holds because q 2 6.
c (28 7) S 5A,-
(K.16)
K.15
can thus be bounded by
Σ k=
A
+
(
0
)
S 851c(1 - -
+
(2 2 5 2
+
2 82, )
[c(1 - -8x))//2
9
A
= 3 11222
1/2)
+
[c(1 - 8x,))112
where the inequality holds due to K. and Lemma K.
For To < S ktt we have
1 1 c - (26 2 c- (1 - c266 - 9)/6 (1 c){g 6)
8 2 0.
where the first inequality holds because \; S (1 -1-) 65 and the second inequality holds because q 2 5. We also have
1 1 c- - (28 q) S 1 --c
where the inequality holds because 25- 2 25 (1 + c)0 =(1 (1 c1) 2 0. Therefore,
|| c- (28 - 9)hp - c
(K.17)
K.15) can thus be bounded as
A j+
10)
[8]
S
1 1-c
di
j[c(1- 52:))(r-11/2 +
2 1-c
2);
T-c)
2 ) [c[1 d2.))s12
1 c j[c(1 5x,) (1-)//111 11/2 +
3
Ic(1 - 52,)1122
X
where the inequality holds due to K.17 and Lemma K.14 For > kt, note that
1 1 1 F2 (1 82.)
9- 8 - 20
1
9- c5
9
1-c
\/
-
1-c
where the first inequality holds due to Lemma The upper bound of (.7p thus given by
E.2 and the second inequality holds because g 2 6.
8
1 (1 5A, x1)
21)a3(11
x2/) - (1 52; x2)= (1+1)) xz/))
Σ km
A
++
<
A
42 I1
(1-8A; x2) 2// x
2
(K.18)
A
822 11
where the inequality holds due to
<
22. If 2 1,
2 _
3-1
x 1-1
(1 1-82 8\
122
22 (1 - 87, 21
322
(1 62x:)o2
F2
11
822 Z1
49

---

Published as a conference paper at ICLR 2024
9 cò A1
j-1
(1 8A,- 12)
+ (1 - -81))
c
q-06 X;- 11
1-c
1 9 cδ
j-1
(1 - 81,)
1 1-c
4-od Xi) - c(1 - -81;)
c X
8-c5 X/ - 311
1-c
9
cō \/
1 02
1
9-cδ d;
1-c
2-06 I-c
d
g-06 1-c
A Iz
where the inequality holds due to Lemma K.
Note that
1-
(1-o)²
1 52c 1-c
(vg cō V cla 8)3²
S
g-06 1-c
(1-c)²
(vQ-08+ ob v((1-)))2
(1 dq c5)/(q 8))²
(1 1)2
4
c6)/ - 0))2 - c1-c) S
(K.19)
(1+
- 1c4
(1 (1+1) 1) (1-c) 3 c
where the first inequality holds due to (E6)). and the second inequality holds because q - 5 cgg- c5). We also note that
9-05 d; C
Q-o5 A; - C 1
1-c
1-c
g- 0
Xi
11
1 8-có Ai-
(1+0-ad,) - v (1 (1-c- -e
1
g-05
(1 (1-c)²
1 - c
1-c
(Vg- c6+ vd9-
2
2.
1
(1+0)--20 200
1
(1+0) 206
(1-o)²
1-c
(vq-ch + Vela 8))2
dg 6) q - cō
= 2 +
2
(K.20)
where the first inequality holds because v11 (1+c- yd:)²- - 4c(1 - 82,) 2 0, the second inequality
holds due to (F.6), and the third inequality holds because 9 - S c(q eσ). Combining 19) and K.20), we have
1 82
4(2 + c) 3 c
3
(K.21)
1-c
X2
8-co
1-c
F1
where the second inequality holds because < 1. where the second inequality holds because
x2 2 1 1-22 2 Ai due to Lemma E.2 Combining (..18) with K.21 we have
Σ 0==0
A
i+h
6 q
I
3 (1
9 c5 1 1-
1-c {1)
(1 - 2a²)
3
1 9 c8
1 1 2 2 -- co Xo )
X
1
where the second inequality holds due to Lemma
E.2 If j
0, then by K.18)
Σ
A [8]
1 1-
x
2 co
1
A
A
1-c
where the second inequality holds due to Lemma The lower bound of (K.7) is given by
E.2 Thus, the upper bound also holds for j = 0.
Σ
l
A
*
9
0
A (1
1
(1-52,-
52,
x22
2 (1
ab)) xf(1 - -11) + +z2 =ab)
x2 21
0=
50

---

Published as a conference paper at ICLR 2024
23 xb) -x2(1 x1)
O2:- x2)
+ +z2(1 =a/)
02 - 21
222 r
(1 8A:- 22)
+ (1 x22
x2 31
1 12
-(1 8A - 02)
+ (1 - x5))
X
32
5u
(1 - x/22 2 0,
-2
where the first inequality holds because 21 S 22, the second inequality holds due to Lemma K. 12 and the third inequality holds because 0 < 22
The following corollaries follow from Lemma Corollary K.6. With A, defined in (E.
K.5
assuming that NV - c) 2 2, we have
d
N
2
< 18NK + 36s.V2 - c5)²
Σ
i+
Σ 1>b"
(1-c)² c)²
0=0
k=u
Proof. By Lemma
K.5
we have
(a) For S k7
Σ
N-1
A j+
2
-
4 s-1
(c5/9)²²
S
4 5-1
Σ
4 1-c
[
X j-0
x
X
1-c
jm0
k==
1
j=0
4
5
(K.22)
(1
c)
2N
X?
where the second inequality holds because (c5/g)² < c² < c, the third inequality holds
because 1 1-c- c² S 1, and the last inequality holds due to the assumption that N(1 cc) 2 2.
(b) For kt <i ki
3
co(1 - 52,)112 + +5jle(1 - 5x,)1
A
1/2-1
3
[c(1 52,))/2 + 28[c(1 62,)11/4
Σ 1=0
[c(1 - -82))
A
le(1 1/4)
[o(1 82,)]5/2
[d11 51,))// + 28
A
Ve(1 - -82)
3 [c(1 -8x0)//22 + 28
le(1 - -82,))/4 -lo(1 822.)//2
S Xe
52,/2
4fc(1 - 5xa))//4 - |c(1 - -82))//2
< A
Ic(1 -5x,))/44
(K.23)
where the first inequality holds because [c(1 82,)) < [c(1 - -2x)) for all / 5
i/2 1, the second inequality holds because / c(l 8A,) 2 1- vI oA 2 82:/2,
and the last inequality holds because [c(1 - 51:)] 2 0. We thus have
|o[1 - 6x,)1/2 + + - 62.)) - 2
S
16
|o(1 8x.))/2 = 16 1 1- [c(1 62/)
Σ
x7
x 1- Ve(1 - 82,)
51

---

Published as a conference paper at ICLR 2024
16
1
16
1
32
S
c1 - 87g)
X
(1-c)/2
(1 c)
(K.24)
16N X
where the first inequality holds due to Lemma K.5 the second inequality holds due to (K23), the third inequality holds because 1 - [o[1 5xx]]=/2 I 1, the fourth inequality
holds because - ve(1 - 52,) 2 1 v 2 (1 - c)/2, and the last inequality holds due
to the assumption that (V a) 2.
(c) For ke < kl,
3
c(1 - 5x:)j//2 + 1-c
i|c(1 - 88:)]
X
3/2-1
3
+ 2(1 c)
< X,
lo(1 - sx.)pi/2
[o(1 - -81))/14
Σ |e(1 - 8X, 1=0
A
3
+ 2(1 c) [d[1 61.)81/4 - [c(1 - 82.))1/2
X le(1 5X,)p122
1 vcll - oA,)
3
lo(1 52,))1122 + 2(1 c) [c(1
-8A:)uM - |e(1 - 82x))0/2
A,
X
(1 c2/2
4|c(1 SA,)1/4 - [c(1 8A,)]
4
S A
|o(1 - 52,))1/4
(K.25)
A;
where the first inequality holds because [c(1 - 52:)) < [c 101-600 52 for all
& S j/2 1, the second inequality holds because c(l - ox,)) 2 1- (1-c)
and the last inequality holds because [c(1 - d2::) 2 0. Due to the same deduction as that in part (b), we have
2
Σ A+
[8] [9]
5
32
(K.26)
(1 - c)
1=
16N
X?
(d) For kt
<ish.
<
N
++ [
10)
2
1 - 9 - c5 A/
N72
|
11 g - c5
2j
xi
x
1-c
1
9
1
- 2 9 - c5
\
Σ
1 q c5 A
X²
1
21² 2
9(1
1 11-1-29-00 -
9-
q 9- cb
]
1 1
c
9 c)
2N c6)
18N
1-c
X?
52

---

Published as a conference paper at ICLR 2024
(1- 4-2 (1-9-e)) X1) 2j
- -11- 4-2
)
where the second inequality holds because
1-c \1
the third
inequality holds because - (1 - 24 X,)
I 1 and 1 1-
1-(1- (1- 9-0 )s)
1, and the
last inequality holds because X; 2
I-c 28]
due definition of k*
(e) For i > k"
// 1 - 9 - c5
272
Σ
S
9
1 - (1 11-2 c A1
1- 29-00
1 A1)
x
1=
0=
j=
9 co
2 8-11
N6sN2 (q c5)2
-
22
1 1 )1)
Σ
x
(1-c)2
5=0
(1-29-02)) 1-0 21) N
where the second inequality holds because
s 2N q- X and
(1 - --
2/ 1
Concluding all the above, we have
N-1
2
Σ
A
1=1
/=0
X²
2N
Σ
X²-
16N
+
Σ
X
18N
+
Σ
X
N6sN2 co)2
X²
X?
X²
(1 (1-c)2
keeight
kicigh
36&N2 (q co)²
2 + 16 - 1+) + 18N( - k²) +
2
(1 c)
1>
S 18NE + N6s (q c5)2
X
(1-
where the second inequality holds because all coefficients 2, 16, 18 are bounded by 18.
Corollary K.7 With A, defined in (E. we have for all j 2 0,
Σ x
Σ
A
k
88) < 9k
36(q co)2 (1 c1-
Σ X2
q
1
i>k"
Proof. By Lemma K.5
we have
(a) For kt,
N
1)
08 9
2
4 (c5/g)21 < X?
Σ
A
j
S x3
k=
where the second inequality holds because cō/g S 1.
(b) For kt <isk.
3
[o(1 - 52.))/2 + 5j|c(1 - 62.) 11/2
X,
j-1
[c(1 82.)]512 4
Σ [c(1 - -82))1/22
S Xe
3
1 1- Ic(1 - 82,)
[d(1 022))//2 +
A
vo(1 - 87be)
3
1 [c(1 - 6/2))p/2
[c(1 0A
+8-
A,
8X:/2
53

---

Published as a conference paper at ICLR 2024
2 [c(1 - 5x:))1/2
3
S
(K.27)
2
where the first inequality holds because [c(1 - (111-6x: (1 - the second inequality holds because 1 - v cc(1 8X,) 2 21- 5A, 2 52./2. and the last inequality holds because [c(1 - 8xx:)[/2 1 1. Therefore,
for t - j --11 1,
-1-
N-1 Σ k=
2
A
i+
5
3 A;
|o(1 - -x.)) - 8x)] -x 11/2 S
C
where the first inequality hold due to Lemma K.5 and the second inequality holds due to K.27
(c) For k <isk!,
3
jo(1 - 5A.))//2
+
1-c c
s[c(1- 81:))(i-1)/2
A
A
j-1
$ A
Je(1 52.)1/22
+
1
[c(1 - -xxi)1122
A
t=0
3
1 1- 1-1c(1 - 82o)]3/2
|c(1 5x:)1/2
+
X,
A
- vc(1 - 87,))
3
1 - 1 - -
[c(1-6xx)) 622o)
|e(1 5x:)112
+
A,
X
(1 c2/2
2 + |c(1 8/.))//2 3
(K.28)
A
A
where the first inequality holds because [c(1 - the second inequality holds because 1 vc(1 5),)) 2 211-e2 -2/2,, and the last
[[((1_)))] fort S 1-
inequality holds because [c(1 512)]s/2 < 1. Therefore
Σ A=
A t 1
3 [c(1 [c(11- Sx.))//2 + ( (
1
j[e(1-6x:)] 6x:)) 31o(1-)))j((-1/22)
9 X
-
<
X;
where the first inequality holds due to Lemma K.5 and the second inequality holds due to
K.28
(d) For k", we have
N 1
[8]
2
9
1 1-2 -6
)/
N72 2
- c5
2j
A
5
1 1-c \1
9
X
1
k=
N72 2
9
1 2 cb A
1
X7
- c
9 36N2 ( c052
min
X
(1 (1- c)2
where the second inequality holds because 1 g-o5 X S 1, and the last inequality holds
I-c
because 1 - (1 - r) < and - (1- - r) N < rN for all r E (0,
Combining all the above, we have
N -1
2
Σ
x
Σ
A
i*
1=1
k=
Σ
22
4
Σ
9
Σ
x
9 x
Σ
X
36N 2
(1-c)
K
1>
54

---

Published as a conference paper at ICLR 2024
(9 c5)²
= 4k* + +9(h - -b² - +9(1= - -k) +
Σ X2:
(1-c)²
13
s 9%* + 36.N (q- c5)²
x2
c)²
where the first inequality holds because the bound x
is applied for kl <is k", while the upper
bound [1-c)=
(6 is applied for i > k*, and the second inequality holds because coefficient 4,
can be bounded by 9.
Lemma K.8.
With A, defined as in let 21 and 22 be the eigenvalues of A, defined in E.2 Then
and
E.3
For all i S kt, we have
4
t-1 Agtth +
[]],
2 (c8/9)².
(c5/98'
82;
For all 1, < s Re we have
Σ A []]
< 22)c((- 6x0)s/2+ +
4
[o[l - SA.))//2.
σx,
. For all F <isk!, we have
Σ th + H), S 25fcc(1 52.)) +
10
1 [c(1 82.))//2
. For all i > 1e,, we have
Σ A H))
t-1
3(1 c)
[ (1-(12
1-c c X: )} (1 9- xxx²² -
00
(q cō)Ai
1 - c
Proof. Note that
(A - AT A.) -1 [
c- (g - 8)2$] 1 1
Σ A
= (A} A(th)
(q- c5)};
k=0
1
(1 c (q ()A.)((AA)))) (1)
(1-c))A))))))) )122 (A!t))1) )2))
(q cd) co)>i
(1 - c - ()A)) - -AA )21) (IAc) (22+))2))
(K.29)
Combine
K.29
with Lemma and we have
[1),
1
(q -9-))))) 214 x²)) -
x22a (1 z1)
A
(q- (1 ca
022 11
.22(1 - -2/) x 21 21)
+(1- - c)(1 o2,1)
32
1 [1-c)(1 (Ax)) (1 c+ (q 8)).) x1)
(q - Ao)A:
11 - x2
[11 c) - -81,) (1 c (q 8) A1)erp) - xf)
(K.30)
D22 x1
For < kc!, note that
- (1 52x) - (1 c+ (g 8)AsJa1 -1- + 5b 1) (g -0) S 0
55

---

Published as a conference paper at ICLR 2024
due to K.8 and 9 6 2 0. The upper bound of (K.30) is thus given by
Σ Atth
1
+ {1),
1
- (11c))1 5A:) - (1 - c (q ( (a-8)x)ja1(a( - x5)
S (q co)A:
21 x2
k==
(11 - c)(1 - -8x)) (1 (1-c+ (q 8) bz
122 I1
x
(1 - ( - 5)):)(1 - x+a)
(q - c6) )
- zं 12 I
+ [11 1
b)
6)1,)31 - (1 c)(1 - SA:o]
d [1 - (q 0) xf²)
1 cd) cd)
1 1- x
+ [1 c+
(g - -8)1;)01 (1 -c)(1 - 8X:3]
1 1- 11
(1 x4)
(9- -5)x 21 x1)
(g co)a;
1
1- I1
2
(c6//)',
where the first inequality holds because 22 2 2τ, the second inequality holds due Lemma K. 12
and the last inequality holds because 11 S 22 S c5/q 1 - z < and 10 The lower bound of K.30) is given by
Σ A j+ k=
2 1
[111 -c (q (--)))a)m )m1 - -(1 -11- -1--0 e)(1 - 50,))=21111111 a²))
c6)A
I1 -22
[11 c (q -5)Ar) (1 c)((1 - 5)x))aa(( abb)
x2 -2-11 11
- co) { (1 (1-c)(t (1-c)(1-52.)4) -62))a
- x22
1 x j-1
- -111- - c (q- ))1 - (1 - -c) -1 8x,]]22 (1x))118x/]13-
(K.31)
12 - 21
where the incquality holds because x1 S æ2 If 2 1, then
j-1
(1 - c)(1 - -11)) [[1 c+ (g - )) - (1 - -1x;j12
12 x
822 I1
(1 c) - 51,)002 - (1 - c (q 8)A,)1122 (c6//)-11
c0/9 31
-1-0l cc)c((1- - 52:) - (1 - + (q 8)A,) cl1 - -da)) (c5/9))
cō/9 21
-(11 - 0x,) (1 - c) - 22) + c(q 8)A, (68//))-1
(1-c)cc-
(K.32)
cō/q x1
where the ineuqality holds because (1 - c)(1 6Ax.)a-- 2 0 and due to Lemma K.12 Note that (1-c)cc-
- (1-52;) (1 - cc - x2) + c(g 8)2,
cō/q 11
c) - -+ctgd v (1te- (1,,))))) -1.)
= =(1 (1-6As) (1
+ c(q 8)
2
c5/9 ltc-gd.- / -2,te-92,,* -
2
56

---

Published as a conference paper at ICLR 2024
< (1 8Ap)) (1 - -1
2
+ dq-
-
= 2((1 oAx:) [11 + c)q- -208 (1 cc)
c5/9
q²t: 111 + c)q 200]
((1 + c)qq - 200 (Vg-cō+ v /clg-51) 5]) (1 c)2
5 1 8. (Vq cd (oaa-)))
-
q²
(Vg cō + v /cgg- 8))2 [(1 + c)q - 2c0]
(cō - Volq 64 - c6) ( o5 + Vdaa - -5)²
cq¹²
(co)2 A(q - cd) eqp v
4c(q co)
(K.33)
where the first inequality holds because V1+ qA,)² 4c(1-8x)
82,) 2 0, the second inequality holds due to (E.6), the third inequality holds because cδ /clg - 6)(g co) cō and c(g 8) =
q cδ, and the last inequality holds because d S q. Combining (K.3)) with K.32 and K.3 we have
A
[] {),
1 - z/
4c(1 cō)
2 (q c6)>;
-
(05/g))-1
52, (05/g)'
where the second inequality holds because 1
x² < 1.
For h < <is
s kt, i.e., A; has complex eigenvalues 21, 22, we have
1-1 1
[] 11)
Σ
A +
= (q -9- co)a (1 - c)(1 (1-0)(1- - -0,))2 x²y)
0=
(2g x
(1 - x²)
x
(x5 x1)
+ +[(1 c) - 522) -(1
(1 - c (q - 5)Ax)az2 11
22 21
1
111 c) -52,) (1 - c (g - o))2)0221 |2ا
(g - c5)
22 x
-11- x + + 2/² 2
(1 (1-c) c) 67₂e)
| =//b
T22 11
222 11
(g (
(K.34)
where the inequality holds due to triangle inequality. Note that
- (1 - 52x) -1 m221
-
8) c) -x,,) - -1 c 8)2, )m1)
where
- (1-c+ 11 -11 (1-c c (q 8)2r)a11
(l (1-c) -1011-0
(1 ())
+ (1 - c+ (q - ()A,)) 22102
= - (01--MMp 1-c))(1-6X))--
c)(1 61 c (q- 8)), c
c- -
+ (1 c+ (q - .)
= - (1-8))a------ - 6)
S <c(1 - 6g: 25)²>3,
where the inequality holds because 9 - < c(q - -c)). Therefore,
[11 c) - 6A.) (1- c (g 0)):)a2l S (a - /( (K.35)
K.34p can thus be further bounded by
H]
Σ t+
k=
57

---

Published as a conference paper at ICLR 2024
S VVl1 5d:)) 1pr1l
42
2--1
+ +211 p-1
x r
+ 2(1 c)(( 62x))
|12
22 -
21
122 x1
- (0-o5)A
2(1 c) [q
2 t/c(1 - 5x,)11/2+
f[c(1-6x,]]12
+ +2( -0-11 11 - - 62:)]1/2
1o(1-6x:)]0/2
(K.36)
c
where the first incquality holds because
[1
x/2
S 2 and due to (K.3)). and the second inequality
holds due to Lemma [E.2]and Lemmal K. 13
For b < S k, we can further bound
(K.36) as
Σ A +* H) )) 0=
2 c11
oA:)
2(1 - c)
1 1-
8di 1-dx;
+2( - 11/
(q-c8) VV
1) [c[1
|c(1- -
-52,)1/22
2
<
+
+ 2j
[c(1 - ddx.]]/2
822
4
2j[c(1 5x,))12
+
[c(1 8x,))s/?
82
where the first inequality holds due to Lemma
K. 14 and the second inequality holds because S c cand
vol1 -A,) S 1, (1 - c)/(q - cd) - 1/8, dA;
- 1 < j.
For l < i < kt, note that
1 c
dA
(q co)A:
S 1
(Vq 14-00-00 + V dq (2-6) 8)}²
8(1 - c)2
Vola c5)
(1 cl-
(Vq - c5 + Vdla 8))²
(Vq - δō + Velg - 6)) 0 + Velg co))
vdl c) - co)
(1 + c)vv σb 2 /clg- cd)
vo(1 c) co)
4
W
(K.37)
where the first inequality holds due to EE.5). and the third inequality holds because c
the second inequality holds because q- 8 S c(q co), Therefore, (K.36) can be further bounded by
1-1
A + H]
2 c(1 dA,)
+ 2(1-c) c) c)
/
1 11
sA 2 1)
Σ
[c(1- - 621))112
1-c
- (q-co)A;
c
2
+
2j
[o(1 - 8x;))
1-c c
1-c
10
2j[c(1 5/2
1-c [c(1 - 8x,))
where the first inequality holds due Lemma /e(1 - [X, < 1. - < j and due to K.37
K. 12 and the second inequality holds because
For j = 0 and t > 1, we have
(-1
Σ
A
i
1
(1-c) -
(1--) -8,,) - -11 (1-c+ - (q- (1-5)),)==(111 - (1=xb)
(g c
x2 21
- (1-c)(1
0Xx)) - (1 - c+ (g - 8)A1)x2(11 - 21)
58

---

Published as a conference paper at ICLR 2024
(1 c (q- 6)A.) - (1 - c) 521)a1
c5-
22 11
-[(1-)] - (1,) (1 + (q 8)1,)a1122
22 - I1
1
(1 (1-c) + (g 8)4, + (1 c)(1 526)laa
(q - c51,
22 x-
+ (1 c) -81,) (1 c (q - 5)1,)=1l 1122l
2/2 21
1 8-8 8 (1-
(1-c) c)
)7;)
|e(1 (t
(q co) a- cō
- (9-co)2
+ + - 6A.) : (t 1)(c(1 - 8x,][(121/
(K.38)
where the first inequality holds due to triangle inequality, and the second inequality holds due to Lemma K.13 When k < i s k. (.38) can be further bounded by
A + 11 )
1 1-c c
+ 9-8 8
(1- - .%:)
+ c(1-6A) oXx)
[g co)A;
9- co
(q co)A:
d7
c
1-c
+1+
(q co)
(q co)A;
87;
1
1
1
4
82 d7
52
52,
874'
where the first inequality holds due to Lemma K. K.14, the second inequality holds because (q-
cd)/(1 c) 2 5, 1 - 5A; < and e S 1, and the last inequality holds because 9-20 2 8 and
54,- S 1. When &o <is kt, 38 can be further bounded by
)
11
A +
[
0=
c
5-8
(1 - (1-c)(1 - 8Ad))
- (1)
+ -6)
(q c
q q- c8
1 1-c
c
+1+ 1-c
(g c
(q cO)A 1-c
2(1 - c)
(Vq cd + dq
5))²
1
(q c5)
c)²
I-c
1-c
2
c(g 8)
2
[+
1-c c
q co
1-c c
2
2
10
< 1-c (1+1)² + 1-c 1-c'
where the first inequality holds due Lemma K.12 the second inequality holds because q - S -cô, 1 - 8A; < 1 and с < 1, the third inequality holds due to E.5). and the last inequality holds because c(g d) S q cò. Therefore, the upper bounds hold for j = 0.
For i > kt, note that
(1 - c) - 52,) - (1 - c (g 5)A:)a02
2 (1 - () - 52,) - (1 - c (q 0)As) (1- 9 q-c5 c5
1 A.)
59

---

Published as a conference paper at ICLR 2024
(q () cō) x2 2 0,
(K.39)
c
where the first inequality holds due to Lemma E.2 and the second inequality holds because q- - 2 q - 5 O. We thus have
Σ
c-1
A +
H]
(1 (1-ccj c)(1 -dx,) (1 c c+ (g
x25)
S
(q -06jAs
-22
0==0
[11 - -c)(1 - -82;) - (1 -1- (4 - 8) As 8))1) (1 - x²))
D22 -1
1 1 x22
(1 - c) - 5x,)
222
4-1 21
+ [[1-c(1--a)) - (1 - c (a -
(K.40)
T2 21
where the inequality holds due to K.39 and 11 S x2 j 2 1. K.40) is further bounded by
[1- - c) o2,) (1 c1-c+ c (q - 8)A1)a2)a1 22 x7
(1 c1 821)22
22 21
q c8
-
5-1
(1 (1- (1- - -82) + (1 (1 - oA,) - (1 - + (q o)A,)a22
<
1 A1
x1
A F1
1-c
q - cd
j-1
1 1 di
(1 c)(1 -dAa) + (1 c)(1 - 82,)21 - (1 - c (q 5)A.) c(1 - oA.)
1 g-ch Xi- x1
1-c
1- -- \o
;
d- -
(1 c)² [[1 + c)g 2c0
(K.41)
q-c X;-
where the inequality holds due to Lemma K.12 and Lemma
E.2
We already have
1-8 82g
4
8-0 X/
1-c
by K. 19
We also have
(1 c)² [(1 + c)q - 2c5 X₂
(1 - c)2 - [(1 + c)g 2c8 A
9-06 Xi 21
1 g= X (1+c- - - (1+c--g..) (1tc-09.)--Ac(1- -4c(1-62.
I-c
1-c
(1 2)
[1 + c)q 200|A,
= =2(1 - -c)
(1-c)² - [(1 + c)q 200 \ + (1 o) / + c - -2i)² 4c(1 - 87,)
< 21 c)2
where the inequality holds because (1 cc) (1 +
- 9d:) 2 - 4c(1 - o2:) 2 0. We thus have
1 82 c)-c)2 [[1 + c)q 208] 2-
8
2(1 c) c) -
3 (1 - c) < 3(1 - c), (K.42)
1-
1
X 21
3 ++ c
1-c
where the second inequality holds because e 2 0, and the last inequality holds because 8/3 < 3. Combining (K.42) with (K.40) and (K.4T), we have
t-1
[
3(1 c) (q
(1 q c6 21) (1 -xb)) 1 - c
Σ
A +*
i
S
co)>;
K=
60

---

Published as a conference paper at ICLR 2024
3(1 cc)
(1-9-09
q 9-06 co
A )
)
11-1-29--0 cō 11 )
11-1)111100 1-c
[q - co)A;
1 c c
where the second inequality holds due to Lemma
E.2 For 0, we have
x2 1
[11 - c1 5A,) - (1 c (q 5)2
+ (1 c (q -0)11)a2
22 I1
(1 - c)2
1 c+ b7 -51, 11 (g 8)
(Vq - c5 + v /cqq 8))2
(1 o) [g -
+ 8) c6)
dg () (1)
cσ)
(9- + (0- -))))
$ (1 c) dg - 6) + (q 100--00 (0-6 2(q -0-)) 8)
2
= (1 c)
[+t + c1+ E.
S 3(1 -
where the first inequality holds due to and the last inequality holds because c 2 0. Therefore, the upper bound also holds for 0.
the second inequality holds because q- 2 (q - 00/cc
The lower bound of (K.30) is given by
Σ A M k-=0 0
{1),
2
1
[1 c1 52a)) - (1 c + (q 8)1 - 255))
(1 c6)c
51 D22
(11 (1--)]o c]( - -81,) -(1 (1- c (q 8) )r2) ( x1)
32 I1
z22
(1 c (q - (0)))))111 - x52)
(q co) A
1/2 x1 D2 21
- -1(1 -c)(1- - -)x,) - -(1 c (9 5)):)az))
J2
(1 + ( 0) x5²)
(q - }
1 1- x2 [11 c)(1 - ddx,) (1 c (g - 0))))22)
x2
5 xb) 2 0,
22
where the first incquality holds due to K.39 and Ø1 < 22, the second inequality holds due to Lemma K.I2 and the third inequality holds because 0 < I2 < 1.
The following corollary follows from Lemma K.8 Corollary K.9, With A, defined in (E. we have
N-1
H))
Σ
A
k=
16 8z (c5/g)²
25
w'1
+ 8
("Pll(I-H)'" 2()) - w w'))l
0i6t
32
200
+ 8
c II(II 5H) / ]|
H 1 +
c c 5H) (wo w
(1
c)2
+ 9(1 - c)2
[ g 9- c5
1 H)
(wo - wi))
(g co)²
(I- q cō H
+ 36N2
(wo w²)
1-c c
61

---

Published as a conference paper at ICLR 2024
Proof. By Lemma K.8 we have
(a) For & ki, we have
N- 1
* 11,
16
Σ
A
oorد (c6 (c6/1)20
A=
(b) For k+ < <is Ri, we have
Σ
A +
11
1 22|c(1 - -6x;)]//2 4
1o(1 - 111-)x)))0/88
2
32
S 8s (s8 - (c(1-\))]' +
[c(1 - oAx:)'"
where the inequality holds due to Cauchy-Schwarz inequality
(c) For Fo <is kt, we have
N 1
Σ
A +
H),
H
2 < - -8x)) + 1-c Ic(1 - 522))o/2)
10
A=
200
S
- [((1_\)) + (1 (1- c)2 ic(1 8x,)1.
where the inequality holds due Cauchy- inequality.
(d) For i kt, we have
N Σ k=
1]
2
9(1 c)²
1 - (1 (1-
1-----0- - cō
277
9 - cô
20
A +
<
A
1
X
(q c6)227
1 -
1
9(1 - c)2
30.2 / (1- 9 - cō
20
S min
(q ( c5) -5)xx3330007
1 - Xa
where the second inequality holds because 1 - -1 - r) < 1 and 1 - -(1 (1-r)- -)) S rN hold for all E (0, 1).
Concluding all the above, we have
N-1 1
H)
Σ
A
k=0
5 Σ xnoo
16
(c6 (06//)2)
32 + Σ smu, (of(((-6x)]' + 82 (72((((18x)) 6x,11)
82X?
is
kttish
Amok (882(0(11 - -8a;)1 + (1 - c) |c(1 - -Xxo1*
200
Reiiht
Σ Arw? 9(1 - 0)2
(1-9-90) co
\o
20
+
Σ
dwwk 36N2 (1 q - cb
(1-
1 - 2;
2a
1 - c
kleigh
k>k
16
8 (c5/g)
25 |W w 1 |
+ +8s2c*1
- (H)
/ - -w*) 1
32
200
c - /HH (wo w 11
+
c /H)z/2(wo -w')l
8z
H kix
(1
c)2
9(1 - c)2
(I- 11-9-0h 9- cō 1 1-c
HH
(wo- - wx)
c0)
(q - co)²
H
k7
2
+ 36N22
(1-9 1-c
| q co
H
(wo w
He
62

---

Published as a conference paper at ICLR 2024
where the first inuequality holds because the upper bound 9(1-c)² [g-c8)'X²
is applied for kt <is kt* and
36 is applied for k".
Lemma K.10. With A, defined in E. let 21 and 22 be the eigenvalues of A, as defined in E.2
and
E.3)
Then
For all i k2, we have
2
S
28X;
For all 1+ < i S R we have
14 8X,
2
For all ie < kt, we have
1
10 1-c
Σ k=0
A
1
For all i kt, we have
1 1-c (1 cd)
1 1- 1-(11- 11-29- c5
20
k
S
1 1-
0
Proof. Note that
A K
1
= (Af)21 + (A,)) = -c
222
x1
22
11
1++
T22
(x2 c) (x) c)
(K.43)
22 F1
where the second equality holds due Lemma
E.3
Summing up the square of (K.4)) yields
(I2 - c)a - (x)
c)x41"
32 11
K==
(I2 2² 2k
(x2 c²) (11
(x) - c)2
(x22 - (1)=
(x2 - x2
(52- - x11²
k=
(I2 - c) x2
D22 ()) c)(l (x1
(x1 - c)2 x2')
(K.44)
(1 (12 12
(1 - 31 ) [22 - x2) )
(1 - (222 - )2
Denote
(I2 2)2
B = (i) - c)
C == (α) c)2
A ==
12
T1
x
then we have
A B
(x2 - ()(1 CF2)
B-C C
(x) - c) c.1)
T2 T1
(1- - (1 x2
82 - 41
(1- x1) x1
A- 2B + C (1 () + 12
20(11 + x2)
(x2 x1)²
(1 - 21)(1 (1 1122)
For all < kF, (K44) is bounded by
2
A-2B 2B + C
C B
322 Ø
122 x
2
= (1 - =2?)
C.
2
(x2 )2
D22 31
32 3
F2 21
< (1 -1-22
13
2t
A 2B + C
20g
C
8 2
( 2 1
(02 )
32
63

---

Published as a conference paper at ICLR 2024
A-2B CC
+ 2zz(C B)
(x22 - x1)²
12 1
1- 21
(1 + (1 + x2 -20xx1 + x22
2zz(c - 21 21) cσ1)
+
(K.45)
(1 - x1 x²) (1 - x122) (1112
(1 (1- (1-2)) x1
2
where the first inequality holds because C
2 0. and the second inequality holds because
mz-zz
due to Lemma K.12 Note that
(1 + e² (1 + x2222) 20(21 + x22)
(1 - =1 - =z²)
(1+c)²
(1 - c)
(1+c)
(1 - c)
2(1 + 21) + x22 +
2(1 - 12 21)(1 T22)
2
2(q - c6)>;
(1+c)² (vq cō da - -00)²
(1 + 1)
9 c5
5
(K.46)
2
2 c6)
2
2(g co)
2'
where the first inequality holds because + 0/2 2 + æι 2 1, the second inequality holds due to
E.6). and the last inequality holds because vq - cd /clg - 8) I Vq co. We also have
(c z1 (1 - cT 222)22
(c- x [c x2 x2)02 cqg 0) 22
< (c x1 12
1 1-
c x2
22
dy 8)1; : o5- 109-581y-c)
/elg- 8)(e5 Vcly 8) cσ)
/cly 5)(
v - cō + /clg- - 8)
V dg 8) 6
57 2
Vdl 8) + /dl- A,
(K.47)
where the first inequality holds because 1- CZ the second inequality holds due to Lemma
< 1 1-2x xÿ (due to the fact that 1 S 22 S <0/99 S c).
E.2 and the last inequality holds because vqg - có 2
/clg- - 5) and c5 Valq- - 5)(q - co) S cō S
8. We finally have
222
c(1 dAx.= 2 sAi.
(K.48)
Substituting K.4
K.4
and (K.48)
into K.45).
we have
2
7
A
S
+ 5A
2
82i
(82,)2
254,
k=
For kt <is kl,
K.44)
can be bounded as
[]
!
A
A- +0
A+C
(1) - Ø1
C A
22 -21
21 21
(1 (#142)")
(I2 21)2
2
322 31
2(x22 31
82 31
< 11- (x1
A 2B + C
IA+ Cl
w/ 2
2
+ 2
C A
22 1
(I2 - )
2
22
222 31
32 F1
A- 2B +C
AA+C|
C A
(1[1 -
+
21(c(1 - 0A:)) (1-1)/2
(r2 x2
2
2
222 X1
(1 c²) (11 + x1 - 20(x1 + +x22)
|A
+ Cl
(t[(1 6x.))
+
Z1
(1 (1- x== x²²)
2
2c(1 + x1 - (1 (1+ + x2)
2t[c(1 -bA:)] 12-11/2
(K.49)
2(1 - (1)
where the first inequality holds due to triangle inequality, and the second inequality holds because
0 0.1 1 (x122)' < 1 and due to Lemma K.13 We now bound the coefficients. Note that
(1-x1)(1 - -22) = (1 c1-
(1-c) c)2
(Vg c5
+
/clg 6))² < (Vq - cō + / cō) 2
- <
q cd
cō
64

---

Published as a conference paper at ICLR 2024
where the first inequality holds due to (E.5). and the second inequality holds because c(q - 1 q - co. We also note that
c1+
(1+ c)2
(1+c)2
$
(1 (1+21)(1+0g x22)
2(1 + c) (q + c8)A,
2(1 +c) - (1+ 2c)0A, (1 1) =
(1 + c)²
2(1 + c)) (1 + 2c)
where the first equality holds due to Lemma K.2 c), the first inequality holds because S (1 + c)o, the second inequality holds because OΛ, have
I, and the last inequality holds because c S We thus
(1 + (1+ 21 2c(21 + x2)
(1 + c)2
(1-c) c)²
S 4, (K.50)
(1- x1]{1 x3))
(1+ (1) (2)
(1 (1-5) (1 - x2)
2c(1 + x1322 (1 (21 + x22)
(1 (1+c) c)²
(1 c)2
2. (K.51)
(1 - xz)(1 x22)
(1 x1) +22)
(1 -1- 01 )1 + x22
We then bound |A + Cl/2. Note that
A+C
1
[ c) c)²
(x2 - c)²
(x) - e) - x3) + (I2 c)² x7)
2
1 1- o
1 x2
2(1 - x1)(1 122
2ca -2c(x1 + x2) + (1 (x) + m3) + 20 + x2) - 20723
2(g co) [2(1 + c) (q + x4
(1+c)(1-c)) - 2(1 c) + c3) c(1 + 2c)o + +[1 - +2 22
2(q - cf)2; 2 + + (g cō)A.]
(K.52)
For A <is k we aim to bound the denominator of (.52 by X multiplied by a constant. Denote the denominator divided by A? as
((A,) + c1 c)3 2(1 () c c c( 2c)0
+ +1(1 +((1-2))q² + 2c 2c2 22)
X?
A
then
d6 0..
(1 + +1 - c)²
2(1 c)
A - -[++c+
(1 [1 [1+c)] c] - -c)
$ 2(1 c)
(1 11--0 c)/8 - -1+ 2c)0]
= =-2(1 - +)) 6) 0,
where the second inequality holds due to E.7 and the last incquality holds because q 2 6, so is decreasing function in 1/A,. We thus have
((A)) 2 @((1 c)
(1+c)(1-o) c)3 c]]-c)[(1 +c+ c² - c(1 + 2c)0]
+[11 101-c200 2) +22009 -2c28-)
(1-0)2/82
(1 c)/8
= (1+c)lg - - (1+ c)0)
2 (1+ c) 8)[(1 c)6 (1 + c)8l -2c0(1 + c)(9 8)
2 -556 - c5))
where the first inequality holds because x; 2 (1 - c) the second inequality holds because q 2 6, and the last inequality holds because < 1 and q Ag 2 1, so (A C)/2 < 262, We also have
cτ. We also note that 2(1 c) (g +
(Vg-oo
v c(g - 8))²
((A.) 5
92
65

---

Published as a conference paper at ICLR 2024
(Vq- cò + vdq 8)}2 -
2(1 c(1+c) - +0 2 c(1+c)
-q
q²
so the upper bound of 14C is
2
A+C
(dq 8) -
A
2
1 - (cō - vdq
/12 (Vg - cb + v - o))²
(cly - 8) -
1 (cō Vely - -8(( co))/4 (Vq-0ō cd + Vcla - 8))2
9. g.clg -8);
(q c8) + /clq (q
28(g c6)p- 20\;s
q c
where the second inequality holds because (cō /clg 8)(9 - co))/4 S 1, and the last inequality
holds because c(g 5) S cτ, S (1 + c)o 20 and vclg 6) - cō) 2 0. Therefore,
A C
28
(K.53)
2
where the second inequality holds because 2(1 + c) (g + co)A; 2 1. For R <isk we aim to bound the denominator of k.52 as A multiplied by a constant. Denote the denominator devided by X₂
+22 (A.)) = (1 c)+c)(11 c)3 22 - 1001--/(++cce)---0++2000000000 + 2c. 2c.001x.,
2(1
d
then the lower bound of ((A;) is given by
(Aa,) 2 2( -
+ + 2(
= --1(1
+ 8) .o),
2 2(1
where the first inequality holds because (1+c)(1-0)* and [(1 22) - 22 2 0, A; and the second inequality holds because and q 8 S 9 co. Note that the maximum of sp(A,) is attained at either ع or (Vg-cō+
(1-c)² For the former, we have
((11 ((11))/0)) c) - c)3
2(1 - c(11 + + c(1 2c)0
(1 - c)/8
+ [[1 - 0) + 26 pq 2c²8² 1-c
8
= (1 - c) + c) - 0){11 c)g/6 - (1 c]]
< (1 - (1 6)((1cc)(1 c)( (1++c) -)
= =-c(1 (
where the first inequality holds because & S (1+ and the second inequality holds because q S 6. For the latter,
(1 c])
10
(Vq cō + Velg -8)2
2((g co) (c(q -6) - Velg -
4 cō + Velg 5) cō)
q2
- c5 Vclq -5)(g - c5)
vq cd
+ c5 + Vclq 5)(g - -8)
2(1 - c)c(q - 8) Vq cδ + Velg 8)
q
66

---

Published as a conference paper at ICLR 2024
S <2c - cd). 1. q + cō + --- cō 22 (1-c)lg-- -c))
where the inequality holds because 9- - 8 H clq - c5) and c(g 6) s 4 cō. We finally have
2(1 + c)- (q + co)A; 2 2(1 +c) - (1 + 2c)dA; 2 2(1 + (1+2c) c) = 1 + 2c",
where the first inequality holds because q & (1 + c)o, and the second incquality holds because 5Λ, I 1 - c (due to definition of k). Therefore,
A + CI 2
1 c+++c
} (1-c)
S max
(K.54)
1 2c 1+c c + 2c
where the second inequality holds because 1 1 c c² < +1+ + 26 and c² x1+c+ 2c Therefore, when k+
<
i
< k 1 xı 2 8); so (K.99) can be further bounded by
A
I
+
20 (ffc(1 - 8X,)) (t-)//21))3332 + 2
2. 22/c(11 - 52:))(21-1122
k=
4
2
14
+
26
x²
87:
82,
where the first inequality holds due to
K.50).
(k.51) and (K.53). and the second inequality holds
due to Lemma K.14 When
< s kt,
11 2 1 - c, so (k.99) is further bounded by
1
S 1 -
+ (1 c) ([((1- - (t 11/2/2
2- 2f(c(1 - 61.))
c
2
4
2
10
(1 c)
(1 c)2
1-c c
1-c'
where the first incquality holds due to K.50). K.5
and the second inequality holds due to Lemma
K.14
For all i >>>> kt.
(.44)
can by bounded as
2
A A 2B + C
B - C
21 - -1)122)
22 - x1
= (1 (1-12)) 122
2
C
(02 - x1 -1)
T2- F1
32 - I1
422 21
k=
A 2B + C
(1 + 0² (1 + x2 - -20(11 + x22)
s <1 21)
=(1
122)
(r2 x1
(1 x1) x2) 21
(K.55)
where the inequality holds because negative terms are dropped. Note that
(1-c)
(1 (1
c)²
(1 - 11=x))(1- - x22
( -
and
c1+
(1 c))
c)2
(1 (1-c)2
(1+c)² = 15
(1 + xt) (1 + x2)
(Vq cō Velg- - 2))
(q co
where the first inequality holds because c < 31 S T2, the second inequality holds due to E..5 and
the last inequality holds because Vclg - 0) 2 0. We thus have
(1 [ c )1 +1122) - 20(x11 + +x2)
(1 c)2
(1 - c)²
(1 x1 =
2(1 11) (1 + x2)
2(1 x) 21)(1 x22)
c) (1-
(1-c)²
(K.56)
2(q 2(q-c6)X co)X; 2(g co)>; (g co)>,
We also have
1 x1 = 1 c cdd, 21-c,
(K.57)
where the inequality holds because cτ\; 2 0. Substituting (K.56) and K.57 into K.55)
we have
[(
Σ
S 23' >
2
1-c
1-c c
1 9 co
20
< (q - c6){
(q - co)A
1 1-c c
O==
2
where the second inequality holds due to Lemma E.2
67

---

Published as a conference paper at ICLR 2024
The following lemma follows from Lemma K.8 Corollary K.11. With A; defined in E. we have
14
10 1-c w01l b.k
A
Wo
w
|wo
c
k=0 0
c c
wo w w"llit + 4c|lwo
w "
q cō
Proof. By Lemma K.8
specifically for ht <i S kt, we have
Σ
1-1
A
2
- (q (q- co)2 -0-0d)
1
[1
1 1- (1 21 c5
1 - X 1 c
20
(q co)
where the inequality holds because 1
(1 (1-29-0)
1-0 X1)
I 1; For i i> h=,
2
1-c
1-29 c8
21
1-c c
(g (0--6)), 4t,
S
\1
4t
2 c-)4A
9 co)2
1 c-c
k=0
(1 (1-2 29-0 X1)
20
where the inequality holds because 1
I 4t
Therefore,
1-c
1-c
2
X
A
2
Xru?
7
Σ
\may 8d1
14 + Σ Mmm,
10
28\;
1 1-c
Reisht
1
+ Σ dmw? 4t
+
(q co)>;
A
<iSk
S>k"
7
14
10
Wo
1I, oski
llwo
w w'1lf,.. [l
|wo
w w'
28
1
1-c
|W
+ 46
|w w w II
9 cb
14
10
l|wo
w'
1P
+
|wo ww H Reat
8
1 c
1
+ co
Wo
w"1l,,,,. + 4t w "
where the second inequality holds because 7/2 < 14. Lemma K.12. For any 0 32
1 (x) + 122) and integer 2 0, we have
0 r
x2 I
0
Proof. The lemma holds trivially for 1 = 0. For > we have
2/
1-1
1-1
0 x
1-1
2 -11
0 Z1
k=
where the inequality holds because x222 S 0. Lemma K.13. Suppose 3ı, 22 are complex eigenvalues of A, for 1 <ig kt_ Then for any t 2 0,
< <((c(1 - 62.))(c-1122
22 Z
68

---

Published as a conference paper at ICLR 2024
Proof. We have
2 - x
| |z|-1
t[c(1 dt
22
32 I1
k=0
where the inequality holds due to triangle inequality, and the second equality holds due to Lemma
Lemma K.14. For any & 2 0, we have
t|c(1 d2.))(=-1/22 v min
2 2 [2," c
Proof. Note that
t-1
1 1 |c(1 - 82,)] 1 ve(1 52,)
Me(1 (t-))
Σ k=0
[0(1 (1:))
<
Σ [c(1 82.))
1
2 87,
< 1 Vcl1 - -x,)
S
82;
where the first inequality holds because d(1 52,) I 1, the second inequality holds because
[c(1 - 8x/2]//22 < 1, the third inequality holds because e s 1, and the last inequality holds because ox z 82./2. Similarly we have
2 1-c
t|c(1 6x,)) I 1 Ve(1 82:)
where the second incquality holds because OA, s c, and the last incquality holds because Ve 2 (1 - 22.
69


Reviews:
[{"review_id": "biiJu51cof", "reviewer": "Reviewer_hi74", "summary": "This paper studies the generalization of ASGD for overparameterized linear regression, which is possibly the simplest setting of learning with overparameterization. This paper establishes an instance dependent excess risk bound for ASGD within each eigen-subspace of the data covariance matrix. The analysis shows that (i) ASGD outperforms SGD in the subspace of small eigenvalues, exhibiting a faster rate of exponential decay for bias error, while in the subspace of large eigenvalues, its bias error decays slower than SGD; and (ii) the variance error of ASGD is always larger than that of SGD.\nThe result suggests that ASGD can outperform SGD when the difference between the initialization and the true weight vector is mostly confined to the subspace of small eigenvalues. Additionally, when the analysis is specialized to linear regression in the strongly convex setting, it yields a tighter bound for bias error than the best-known result.", "questions": "No", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The analysis shows that (i) ASGD outperforms SGD in the subspace of small eigenvalues, exhibiting a faster rate of exponential decay for bias error, while in the subspace of large eigenvalues, its bias error decays slower than SGD; and (ii) the variance error of ASGD is always larger than that of SGD.\nThe result suggests that ASGD can outperform SGD when the difference between the initialization and the true weight vector is mostly confined to the subspace of small eigenvalues. Additionally, when the analysis is specialized to linear regression in the strongly convex setting, it yields a tighter bound for bias error than the best-known result.", "weaknesses": "No", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5WbhUGPPxh", "reviewer": "Reviewer_BSyC", "summary": "The authors analyze stochastic gradient descent with momentum in the overparametrized linear regression setting and they study excess risk bounds, showing that the variance of this algorithm is never better than for SGD and that the bias is also larger for the subspace of largest eigenvalues. They show that for the subspace of the the lowest eigenvalues, the bias of the algorithm is smaller than that of SGD", "questions": "Can you provide any examples of settings in which you can guarantee you can initialize to be in the good regime that you show for ASGD, i.e. when $w_0 -w^\\ast$ is essentially aligned with the subspace associated to small eigenvalues?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "In the strongly convex regime, the authors get better bias error term than previous work (except for a term, that the authors claim that can be removed but that wasn't removed). They extend the techniques in Jain et al 2018 to the overparametrized setting which allows them to specify what happens in their setting with ASGD\nThe paper is well written.", "weaknesses": "It is known from before in many settings that accelerated gradient descent does work very well with noise, and in fact, this is what is corroborated by this work for the setting of overparametrized linear regression. The variance is shown to be greater, the bias is shown to be greater for the subspace of large eigenvalues, which are the most important ones. The claim in the abstract about ASGD outperforming SGD if the initialization minus optimizers lives in the subspace of the small eigenvalues is true but a bit useless, since it is very unlikely this happens. It is a low dimensional subspace and most of the rest of the space is dominated by the large eigenvalues.  It is informative and of value to have all of the details in this setting that are provided in this work, but the results are weak, essentially a negative result that could have maybe been anticipated for this kind of algorithm.\n\nEdit: thanks for the reply to the questions. I edited my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q6GZx9HZhu", "reviewer": "Reviewer_MrsP", "summary": "This paper studies the generalization of ASGD for overparameterized linear regression, which is possibly the simplest setting of learning with overparameterization. The authors establish an instance-dependent excess risk bound for ASGD within each eigen-subspace of the data covariance matrix. The theoretical findings show that (i) ASGD outperforms SGD in the subspace of small eigenvalues, exhibiting a faster rate of exponential decay for bias error, while in the subspace of large eigenvalues, its bias error decays slower than SGD; and (ii) the variance error of ASGD is always larger than that of SGD. Our result suggests that ASGD can outperform SGD when the difference between the initialization and the true weight vector is mostly confined to the subspace of small eigenvalues.  Finally, sufficient experiment verify the effectiveness of the theoretical findings.", "questions": "1. How is overparameterization reflected in Theorem 4.1?\n\n2. Please provide a more detailed explanation of the challenges encountered in theoretical analysis and how to address them in the submission.\n\n3. Can you provide more instances that satisfy Assumption 3.2?\n\n4. The experiments are not comprehensive enough, for example, the paper finds that the variance error of ASGD is always larger than that of SGD, but there is not enough experimental support for this claim.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical findings are solid.\n2. This paper is well-written and easy to follow.", "weaknesses": "The experimental results do not provide strong support for the theoretical findings in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)