Scaling Laws in Linear Regression: Compute, Parameters, and Data

Authors: licong  lin
jingfeng  wu
sham m kakade
peter l bartlett
u c berkeley
google  deepmind
jason d lee
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 04:38:21

Abstract: Empirically, large-scale deep learning models often satisfy a neural scaling law: the test error of the trained model improves polynomially as the model size and data size grow. However, conventional wisdom suggests the test error consists of approximation, bias, and variance errors, where the variance error increases with model size. This disagrees with the general form of neural scaling laws, which predict that increasing model size monotonically improves performance.

We study the theory of scaling laws in an infinite dimensional linear regression setup. Specifically, we consider a model with $M$ parameters as a linear function of sketched covariates. The model is trained by one-pass stochastic gradient descent (SGD) using $N$ data. Assuming the optimal parameter satisfies a Gaussian prior and the data covariance matrix has a power-law spectrum of degree $a>1$, we show that the reducible part of the test error is $\Theta(M^{-(a-1)} + N^{-(a-1)/a})$. The variance error, which increases with $M$, is dominated by the other errors due to the implicit regularization of SGD, thus disappearing from the bound. Our theory is consistent with the empirical neural scaling laws and verified by numerical simulation.

Main paper: 
 introduction: 
 Deep learning models, particularly those on a large scale, are pivotal in advancing the state-of-theart across various fields. Recent empirical studies have shed light on the so-called neural scaling laws [see 26, 21, for example], which suggest that the generalization performance of these models improves polynomially as both model size, denoted by M , and data size, denoted by N , increase. The neural scaling law quantitatively describes the population risk as:EQUATIONwhere R * is a positive irreducible risk and c 1 , c 2 , a 1 , a 2 are positive constants independent of M and N . For instance, by fitting the above formula with empirical measurements in standard large-scale language benchmarks, Hoffmann et al. [21] estimated a 1 ≈ 0.34 and a 2 ≈ 0.28, while Besiroglu et al. [7] estimated that a 1 ≈ 0.35 and a 2 ≈ 0.37. Though the exact exponents depend on the tasks, neural scaling laws in (1) are observed consistently in practice and are used as principled guidance to build state-of-the-art models, especially under a compute budget [21] .From the perspective of statistical learning theory, (1) the model size M for different power-law degrees a. The expected risk is computed by averaging over 1000 independent samples of (w * , S). We fit the expected risk using the formula Risk ∼ σ 2 + c1/M a 1 + c2/N a 2 via minimizing the Huber loss as in [21] . Parameters: σ = 1, γ = 0.1. Left: For a = 1.5, d = 20000, the fitted exponents are (a1, a2) = (0.54, 0.34) ≈ (0.5, 0.33). Right: For a = 2, d = 2000, the fitted exponents are (a1, a2) = (1.07, 0.49) ≈ (1.0, 0.5). Note that the values of (a1, a2) are close to our theoretical predictions (a -1, 1 -1/a) in both cases, verifying the sharpness of our risk bounds. More details can be found in Sections 4 and 5.error, approximation error, bias error, and variance error (some theory replaces bias and variance errors by optimization and generalization errors, respectively) as in the form ofEQUATIONwhere a 1 , a 2 , a 3 are positive constants and c(M ) is a measure of model complexity that typically increases with the model size M . In (2) , the approximation error is induced by the mismatch of the best-in-class predictor and the best possible predictor, hence decreasing with the model size M . The bias error is induced by the mismatch of the expected algorithm output and the best-in-class predictor, hence decreasing with the data size N . The variance error measures the uncertainty of the algorithm output, which decreases with the data size N but increases with the model size M (since the model complexity c(M ) increases).A mystery. The empirical neural scaling law (1) is incompatible with the typical statistical learning theory bound (2) . While the two error terms in the neural scaling law (1) can be explained by the approximation and bias errors in the theoretical bound (2) respectively, it is not clear why the variance error is unobservable when fitting the neural scaling law empirically. This difference must be reconciled, otherwise, the statistical learning theory and the empirical scaling law make conflict predictions: as the model size M increases, the theoretical bound (2) predicts an increase of variance error that eventually causes an increase of the population risk, but the neural scaling law (1) predicts a decrease of the population risk. In other words, it remains unclear when to follow the prediction of the empirical scaling law (1) and when to follow that of the statistical learning bound (2) .Certain prior works provided risk upper bounds that do not grow with model size [see for example 36, 12] . Still, their results are insufficient for studying scaling law as those bounds require a large model size such that the approximation error is ignorable. Moreover, they do not provide instancewise matching lower bounds to verify the tightness of the upper bounds. See a detailed discussion in Section 2.Our explanation. We investigate this issue in an infinite dimensional linear regression setup. We only assume access to M -dimensional sketched covariates given by a fixed Gaussian sketch and their responses. We consider a linear predictor with M trainable parameters, which is trained by one-pass stochastic gradient descent (SGD) with geometrically decaying stepsizes using N sketched data. Assuming that the spectrum of the data covariance matrix satisfies a power-law of degree a > 1 and that the optimal model parameters satisfy a Gaussian prior, we derive matching upper and lower bounds on the population risk achieved by the SGD output (see Theorem 4.1) . Specifically, we show that R(M, N ) = R * + Θ 1 M a-1 + Θ 1 (N γ) (a-1)/a leading order given by the sum of Approx and Bias , Var = Θ min{M, (N γ) 1/a } N higher order, thus unobservable, where γ = O(1) is the initial stepsize used in SGD and Θ(•) hides log(N ) factors. In our bound, the sum of the approximation and bias errors determines the order of the excess risk, while the variance error is of a strictly higher order and is therefore nearly unobservable when fitting R(M, N ) as a function of M and N empirically. In addition, our analysis reveals that the small variance error is due to the implicit regularization effect of one-pass SGD [47] . Our theory suggests that the empirical neural scaling law (1) is a simplification of the statistical learning bound (2) in a special regime when strong regularization (either implicit or explicit) is employed.Moreover, we generalize the above scaling law to (1) constant stepsize SGD with iterate average (see Theorem F.6), (2) cases where the optimal model parameter satisfies an anisotropic prior (see Theorem 4.2), and (3) where the spectrum of the data covariance matrix satisfies a logarithmic power law (see Theorem 4.3) .Emprical evidence. Based on our theoretical results, we conjecture that the clean neural scaling law (1) observed in practice is due to the disappearance of variance error caused by strong regularization. Two pieces of empirical evidence to support our understanding. First, large language models that follow the scaling law (1) are often underfitted, as the models are trained over a single pass or a few passes over the data [27, 31, 9, 39] . When models are underfitted, the variance error tends to be smaller. Second, when language models are trained with multiple passes (up to 7 passes), Muennighoff et al. [31] found that the clean scaling law in (1) no longer holds and they proposed a more sophisticated scaling law to explain their data. This can be explained by a relatively large variance error caused by multiple passes.Notation. For two positive-valued functions f (x) and g(x), we write f (x) ≲ g(x) (and f (x) = O(g(x))) or f (x) ≳ g(x) (and f (x) = Ω(g(x))) if f (x) ≤ cg(x) or f (x) ≥ cg(x) holds for some absolute (if not otherwise specified) constant c > 0 respectively. We write f (x) ≂ g(x) (andf (x) = Θ(g(x))) if f (x) ≲ g(x) ≲ f (x).For two vectors u and v in a Hilbert space, we denote their inner product by ⟨u, v⟩ or u ⊤ v. For two matrices A and B of appropriate dimensions, we define their inner product by⟨A, B⟩ := tr(A ⊤ B). We use ∥ • ∥ to denote the operator norm for matrices and ℓ 2 -norm for vectors. For a positive semi-definite (PSD) matrix A and a vector v of appropriate dimension, we write ∥v∥ 2 A := v ⊤ Av. For a symmetric matrix A, we use µ j (A) to refer to the j-th eigenvalue of A and r(A) to refer to its rank. Finally, log(•) refers to logarithm base 2. 
related work: 
 Empirical scaling laws. In recent years, the scaling laws of deep neural networks in compute, sample size, and model size have been widely studied across different models and domains [20, 35, 26, 19, 21, 46, 31] . The early work by Kaplan et al. [26] first proposed the neural scaling laws of transformer-based models. They observed that the test loss exhibits a power-law decay in quantities including the amount of compute, sample size, and model size, and provided joint formulas in these quantities to predict the test loss. The proposed formulas were later generalized and refined in subsequent works [19, 21, 1, 10, 31] . Notably, Hoffmann et al. [21] proposed the Chinchilla law, that is, (1) with a 1 ≈ 0.34 and a 2 ≈ 0.28. The empirical observation guided them to allocate data and model size under a given compute budget. The Chinchilla law is further revised by Besiroglu et al. [7] . Motivated by the Chinchilla law, Muennighoff et al. [31] considered the effect of multiple passes over training data and empirically fitted a more sophisticated scaling law that takes account of the effect of data reusing.Theory of scaling laws. Although neural scaling laws have been empirically observed over a broad spectrum of problems, there is a relatively limited literature on understanding these scaling laws from a theoretical perspective [37, 4, 28, 22, 42, 29, 23, 8, 2, 32, 17] . Among these works, [37] showed that the test loss scales as N 4/d for regression on data with intrinsic dimension d. Hutter [22] studied a toy problem under which a non-trivial power of N arises in the test loss. Jain et al. [23] considered scaling laws in data selection. Bahri et al. [4] considered a linear teacher-student model under a power-law spectrum assumption on the covariates, and they showed that the test loss of the ordinary least square estimator decreases following a power law in sample size N (resp. model size M ) when the model size M (resp. sample size N ) is infinite. Bordelon et al. [8] considered a linear random feature model and analyzed the test loss of the solution found by (batch) gradient flow. They focused on the bottleneck regimes where two of the quantities N, M , T (training steps) are infinite and showed that the risk has a power-law decay in the remaining quantity. The problem in Bahri et al. [4] , Bordelon et al. [8] can be viewed as a sketched linear regression model similar to ours. It should be noted that both Bahri et al. [4] and Bordelon et al. [8] only derived the dependence of population risk on one of the data size, model size, or training steps in the asymptotic regime where the remaining quantities go to infinity, and their derivations are based on statistical physics heuristics. In comparison, we prove matching (ignoring constant factors) upper and lower risk bounds jointly depending on the finite model size M and data size N .Implicit regularization of SGD. One-pass SGD in linear regression has been extensively studied in both the classical finite-dimensional setting [34, 3, 14, 16, 25, 24, 18] and the modern highdimensional setting [15, 6, 48, 47, 44, 45, 40] . In particular, Zou et al. [47] showed that SGD induces an implicit regularization effect that is comparable to, and in certain cases even more preferable than, the explicit regularization effect induced by ridge regression. This is one of the key motivations of our scaling law interpretation. From a technical perspective, we utilize the sharp finite-sample and dimension-free analysis of SGD developed by Zou et al. [48] , Wu et al. [44, 45] . Different from them, we consider a sequence of linear regression models with an increasing number of trainable parameters given by data sketch. Our main technical innovation is to sharply control the effect of data sketch. Some of our intermediate results, for example, tight bounds on the spectrum of the sketched data covariance under the power law (see Lemma 6.2), might be of independent interest.Prior works investigated linear regression with random features [36, 12] , which can be viewed as a kind of sketched features via random coordinate selection. They mainly focused on the small approximation error regime, where the model size (or the number of features) is much larger than the data size. In comparison, we treat both model size and data size as free variables. Moreover, we provide matching upper and lower bounds while prior works mainly focused on upper bounds. These two innovations are crucial for studying scaling laws that predict test error as a function of both model size and data size. Finally, in the comparable regimes with small or zero approximation error, our excess risk bounds recover the bounds in prior works [36, 12, 33, 15, 13] . 
setup: 
 We use x ∈ H to denote a feature vector, where H is a finite d-dimensional or countably infinite dimensional Hilbert space, and y ∈ R to denote its label. In linear regression, we measure the population risk of a parameter w ∈ H by the mean squared error,R(w) := E ⟨x, w⟩ -y 2 , w ∈ H,where the expectation is over (x, y) ∼ P for some distribution P on H × R. Definition 1 (Data covariance and optimal parameter). Let H := E[xx ⊤ ] be the data covariance. Assume that tr(H) and all entries of H are finite. Let (λ i ) i≥0 be the eigenvalues of H sorted in non-increasing order. Let w * ∈ arg min w R(w) be the optimal model parameter1 . Assume that ∥w * ∥2 H := (w * ) ⊤ Hw * is finite. We only assume access to M -dimensional sketched covariates and their responses, that is, (Sx, y), where S ∈ R M × H is a fixed sketch matrix. We focus on the Gaussian sketch matrix 2 , that is, entries of S are independently sampled from N 0, 1/M . We then consider linear predictors with M trainable parameters given by f v : H → R, x → ⟨v, Sx⟩, where v ∈ R M are the trainable parameters. Varying M should be viewed as a linear analog of varying the neural network model size. Our sketched linear regression setting is comparable to the teacher-student setting considered by Bahri et al. [4] , Bordelon et al. [8] .We consider the training of f v via one-pass stochastic gradient descent (SGD), that is,EQUATIONwhere (x t , y t ) N t=1 are independent samples from P and (γ t ) N t=1 are the stepsizes. We consider a popular geometric decaying stepsize scheduler [18, 44] , for t = 1, . . . , N , γ t := γ/2 ℓ , where ℓ = ⌊t/(N/ log(N ))⌋.(3)Here, the initial stepsize γ is a hyperparameter for the SGD algorithm. Without loss of generality, we assume the initial parameter is v 0 = 0. The output of the SGD algorithm is the last iterate v N . Our proof techniques apply to other stepsize schedulers (e.g., polynomial decay) as well, but we focus on geometric decay as it is known to achieve near minimax-optimal excess risk for the last iterate of SGD [18] .Conditioning on a sketch matrix S ∈ R M × H, each parameter v ∈ R M induces a sketched predictor through x → ⟨S ⊤ v, x⟩, and we denote its risk byR M (v) := R(S ⊤ v) = E ⟨Sx, v⟩ -y 2 , v ∈ R M .By increasing M and N , we have a sequence of datasets and trainable parameters of increasing sizes, respectively. This prepares us to study the scaling law (1) in the sketched linear regression problem, that is, to understand R M (v N ) as a function of both M and N .Risk decomposition. In a standard way, we decompose the risk achieved by v N , the last iterate of (SGD), to the sum of irreducible risk, approximization error, and excess risk as follows,EQUATIONWe emphasize that the irreducible risk is independent of M and N and thus can be viewed as a constant; the approximation error is determined by the sketch matrix S, thus depends on M but is independent of N ; the excess risk depends on both M and N as it is determined by the algorithm. 
scaling laws: 
 We first demonstrate a scaling-law behavior when the data spectrum satisfies a power law. Assumption 1 (Distributional conditions). Assume the following about the data distribution.A. Gaussian design. Assume that x ∼ N (0, H).B. Well-specified model. Assume that E[y|x] = x ⊤ w * . Define σ 2 := E(y -x ⊤ w * ) 2 .C. Parameter prior. Assume that w * satisfies a prior such that E(w * ) ⊗2 = I. Assumption 2 (Power-law spectrum). There exists a > 1 such that the eigenvalues of H satisfy λ i ≂ i -a , i > 0. Theorem 4.1 (Scaling law). Suppose that Assumptions 1 and 2 hold. Consider an M -dimensional sketched predictor trained by (SGD) with N samples. Let N eff := N/ log(N ) and recall the risk decomposition in (4). Then there exists some a-dependent constant c > 0 such that when the initial stepsize γ ≤ c, with probability at least 1 -e -Ω(M ) over the randomness of the sketch matrix S, we have1. Irreducible := R(w * ) = σ 2 .2. E w * Approx ≂ M 1-a .3. Suppose in addition σ 2 ≳ 1. The expected excess risk (Excess) can be decomposed into a bias error (Bias) and a variance error (Var), namely,EExcess ≂ Bias + σ 2 Var,where the expectation is over the randomness of w * and (x i , y i ) N i=1 . Moreover, Bias and Var satisfy Bias ≲ max M 1-a , (N eff γ) 1/a-1 , Bias ≳ (N eff γ) 1/a-1 when (N eff γ) 1/a ≤ M/c for some constant c > 0,Var ≂ min M, (N eff γ) 1/a /N eff .In all results, the hidden constants only depend on the power-law degree a. As a direct consequence, when σ 2 ≂ 1, it holds with probability at least 1 -e -Ω(M ) over the randomness of the sketch matrix S thatER M (v N ) = σ 2 + Θ 1 M a-1 + Θ 1 (N eff γ) (a-1)/a ,where the expectation is over the randomness of w * and (x i , y i ) N i=1 .Theorem 4.1 shows a sharp (up to constant factors) scaling law risk bound under an isotroptic prior assumption and the power-law spectrum assumption. We emphasize that the scaling law bound in Theorem 4.1 holds for every M, N ≥ 1. We also remark that the sum of approximization and bias errors dominates ER M (v N ) -σ 2 , whereas the variance error is of strict higher order in terms of both M and N , and is thus disappeared in the population risk bound.Optimal stepsize. Based on the tight scaling law in Theorem 4.1, we can calculate the optimal stepsize that minimizes the risk. Specifically, the optimal stepsize is γ ≂ 1 when N eff ≲ M a and can be anything such that M a /N eff ≲ γ ≲ 1 when N eff ≳ M a . In both cases, choosing γ ≂ 1 is optimal. When the sample size is large such that N eff ≳ M a , the optimal stepsize is relatively robust and can be chosen from a range.Allocation of data and model sizes. Following Hoffmann et al. [21] , we measure the compute complexity by M N as (SGD) queries M -dimensional gradients for N times. Given a total compute budget of M N = C, from Theorem 6.1 and N eff := N/ log(N ), we see that the best population risk is achieved by setting γ = Θ(1), M = Θ(C 1/(a+1) ), and N = Θ(C a/(a+1) ). Our theory suggests setting a data size slightly larger than the model size when the compute budget is the bottleneck.Comparison with [8] . The work by Bordelon et al. [8] considered the scaling law of batch gradient descent (or gradient flow) on a teacher-student model (see their equation ( 14)). Their teacher-student model can be viewed as our sketched linear regression model. However, we consider one-pass SGD, therefore in our setting the number of gradient steps is equivalent to the data size. When we equalize the number of gradient steps and the data size in their equation (14) and set the parameter prior as Assumption 1C, their prediction is consistent with ours. However, our analysis shows the computational advantage of SGD over batch GD since each iteration requires only 1/N the compute. Bordelon et al. [8] obtained the limit of the population risk as two out of the data size, model size, and the number of gradient steps go to infinity based on statistical physics heuristics. In comparison, we obtain upper and lower risk bounds that hold for any finite M and N and match ignoring a constant factor depending only on the spectrum power-law degree a.Average of the SGD iterates Results similar to Theorem 4.1 can also be established for the average of the iterates of online SGD with constant stepsize [34, 16, 25, 24, 48] . All results will be the same once replacing the effective sample size N eff in Theorem 4.1 to the sample size N . For more details see Theorem F.6 in Appendix F.The isotropic parameter prior condition (Assumption 1C) in Theorem 4.1 can be generalized to the following anisotropic version [11] . Assumption 3 (Source condition). Let (λ i , v i ) i>0 be the eigenvalues and eigenvectors of H with (λ i ) i>0 in non-increasing order. Assume w * satisfies a prior such that for i ̸ = j, E⟨v i , w * ⟩⟨v j , w * ⟩ = 0; and for i > 0, Eλ i ⟨v i , w * ⟩ 2 ≂ i -b , for some b > 1.A larger exponent b implies a faster decay of signal w * and thus corresponds to a simpler task [11] . Note that Assumption 1C satisfies Assumption 3 with b = a. Theorem 4.2 (Scaling law under source condition). In Theorem 4.1, suppose Assumption 1C is replaced by Assumption 3 with 1 < b < a + 1. Then there exists some a-dependent constant c > 0 such that when γ ≤ c, with probability at least 1 -e -Ω(M ) over the randomness of the sketch matrix S, we haveER M (v N ) = σ 2 + Θ 1 M b-1 + Θ 1 (N eff γ) (b-1)/a Approx+Bias + Θ min M, (N eff γ) 1/a N eff Var .where the expectation is over the randomness of w * and (x i , y i ) N i=1 , and Θ(•) hides constants that may depend on (a, b).When 1 < b ≤ a, the tasks are relatively hard (compared to when b = a), and the variance error is dominated by the sum of approximation and bias errors for all choices of M , N , and γ ≲ 1. In this case, Theorem 4.2 gives the same prediction about optimal stepsize and optimal allocation of data and model sizes under compute budget as Theorem 4.1.When a < b < a + 1, the tasks are relatively easy (compared to when b = a), and variance remains dominated by the sum of approximation and bias error if the stepsize is optimally tuned. Recall that γ ≲ 1, thus we can rewrite the risk bound in Theorem 4.2 asER M (v N ) -σ 2 ≂ 1 min M, (N eff γ) 1/a b-1 + min M, (N eff γ) 1/a N eff ≂ min M, (N eff γ) 1/a /N eff M ≳ N 1/b eff and N a/b-1 eff ≲ γ ≲ 1, min M, (N eff γ) 1/a 1-b M ≲ N 1/b eff or γ ≲ N a/b-1 eff .Therefore the optimal stepsize and the risk under the optimal stepsize isEQUATIONM a /N eff ≲ γ ≲ 1 if M ≲ N 1/beff . Under the optimally tuned stepsize, the population risk is in the form ofmin γ ER M (v N ) = σ 2 + Θ(N (1-b)/b eff ) + Θ(M 1-b ),which is again in the scaling law form (1). This is expected since an optimally tuned stepsize controls the variance error by adjusting the strength of the implicit bias of SGD. Under a fixed compute budget C = M N , our theory suggests to assign M = Θ(C 1/(b+1) ) and N = Θ(C b/(b+1) ), and set the stepsize to γ ≂ Θ(C (a-b)/(b+1) ).When b ≥ a + 1, the tasks are even simpler. We provide upper and lower bounds in Appendix D.3. However, there exists a gap between the bounds, fixing which is left for future work.Moreover, we note that in the comparable regimes where M is large, the results in Theorem 4.2 match existing bounds on the risk of SGD iterates and ridge estimators [33, 36] .We also derive the risk formula when the data covariance has a logarithmic power-law spectrum [5] . Assumption 4 (Logarithmic power-law spectrum). There exists a > 1 such that the eigenvalues of H satisfy λ i ≂ i -1 log -a (i + 1), i > 0. Theorem 4.3 (Scaling law under logarithmic power spectrum). In Theorem 4.1, suppose Assumption 2 is replaced by Assumption 4. Then with probability at least 1 -e -Ω(M ) over the randomness of the sketch matrix S, we haveER M (v N ) = σ 2 + Θ 1 log a-1 (M ) + Θ 1 log a-1 (N eff γ) , Var ≂ min M, Neffγ log a (Neffγ) N eff ,where the expectation is over the randomness of w * and (x i , y i ) N i=1 . Theorem 4.3 provides a scaling law under the logarithmic power-law spectrum. Similar to Theorem 4.1, the variance error is dominated by the approximation and bias errors for all choices of M , N , and γ, and thus disappeared from the risk bound. Different from Theorem 4.1, here the population risk is a polynomial of log(M ) and log(N eff γ). 
experiments: 
 In this section, we examine the relation between the expected risk of the (SGD) output, the data size N , and the model size M when the covariates satisfy a power-law covariance spectrum. Although our results in Section 4 hold with high probability over S, for simplicity, we assume the expectation of the risk is taken over both w * and S in our simulations. We adopt the model in Section 3 and train it using one-pass (SGD) with geometric decaying stepsize (3). We choose the dimension d sufficiently large to approximate the infinite-dimensional case, and the data are generated so that Assumption 1 is satisfied. Moreover, we choose the covariance H ∈ R d×d to be diagonal with H ii ∝ i a and tr(H) = 1 for some a > 1. From Figure 1 , we observe that the risk indeed follows a power-law formula jointly in the number of samples and the number of parameters. In addition, the fitted exponents are aligned with our theoretical predictions (a -1, 1 -1/a) in Theorem 4.1. Figure 2 shows the scaling of the expected risk in data size (or model size) when the model size (or data size) is relatively large. We see that the expected risk also satisfies a power-law decay with exponents matching our predictions. It is noteworthy that our simulations demonstrate stronger observations than the theoretical results in Theorem 4.1, which only establishes matching upper and lower bounds up to a constant factor. Additional simulation results on the risk of the average of (SGD) iterates can be found in Appendix F. 
risk bounds under a general spectrum: 
 In this section, we present some general results on the upper and lower bounds of the risk of the output of (SGD). Due to the rotational invariance of the sketched matrix S, without loss of generality, we assume the covariance H is diagonal with non-increasing diagonal entries. Our main results in Section 4 are directly built on the general bounds introduced here. Assumption 5 (General distributional conditions). Assume the following about the data distribution.A. Hypercontractivity. There exists α ≥ 1 such that for every PSD matrix A it holds thatExx ⊤ Axx ⊤ ⪯ α tr(HA)H. B. Misspecified model. There exists σ 2 > 0 such that E(y -x ⊤ w * ) 2 xx ⊤ ⪯ σ 2 H.It is clear that Assumption 1 implies Assumption 5 with α = 3.Excess risk decomposition. Conditioning on the sketch matrix S, the training of the sketched linear predictor can be viewed as an M -dimensional linear regression problem. We can therefore invoke existing SGD analysis [44, 45] to sharply control the excess risk by controlling the bias and variance errors. Specifically, let us define the (w * -dependent) bias error asEQUATIONand the variance error asEQUATIONwhere λj M j=1 are eigenvalues of SHS ⊤ . We also let Bias := EBias(w * ), where the expectation is over the prior of w * . Using the existing results on the output of (SGD) in Wu et al. [44, 45] , we show that the excess risk in (4) can be exactly decomposed as the sum of bias and variance errors under weak conditions. Theorem 6.1 (Excess risk decomposition). Conditioning on the sketch matrix S, consider the excess risk in (4) induced by the output of (SGD). Assume v 0 = 0. Then for any w * ∈ H, 1. Under Assumptions 5A and 5B and suppose γ ≤ 1/ cα tr(SHS ⊤ ) for some constant c > 0, we have EExcess ≲ Bias(w * ) + α∥w * ∥ 2 H + σ 2 Var. 2. Under the stronger Assumptions 1A and 1B and suppose γ ≤ 1/ cα tr(SHS ⊤ )) for some constant c > 0, we have EExcess ≳ Bias(w * ) + σ 2 Var.In both results, the expectations of Excess are taken over (x t , y t ) N t=1 .Assuming that the signal-to-noise ratio is upper bounded, that is, ∥w * ∥ 2 H /σ 2 ≲ 1, then the biasvariance decomposition of the excess risk is sharp up to constant factors.The variance error is in a nice form and can be computed using the following important lemma on the spectrum of SHS ⊤ . Similar results for logarithmic power-law are also established in Lemma G.6 in Appendix G. Lemma 6.2 (Power law). Under Assumption 2, it holds with probability at least 1 -e -Ω(M ) that µ j (SHS ⊤ ) ≂ µ j (H) ≂ j -a , j = 1, . . . , M.For any 0 ≤ k * ≤ k † ≤ ∞, let S k * :k † ∈ R M ×(k † -k * ) denote the matrix formed by the k * + 1 -k † -th columns of S. We also abuse the notation k † : ∞ for k † : d when d is finite. We let H k * :k † ∈ R (k † -k * )×(k † -k * )be the submatrix of H formed by the k * + 1 -k † -th eigenvalues. For the approximation and bias error, we use the following upper and lower bounds to compute their values. Theorem 6.3 (A general upper bound). Suppose Assumption 5 holds. Assume v 0 = 0, r(H) ≥ 2M and the initial stepsize satisfies γ < 1/(cα tr(SHS ⊤ )) for some constant c > 0. Then for anyk 1 , k 2 ≤ M/3, with probability at least 1 -e -Ω(M ) Approx ≲ ∥w * k1:∞ ∥ 2 H k 1 :∞ + i>k1 λ i M + λ k1+1 + i>k1 λ 2 i M ∥w * 0:k1 ∥ 2 , Bias(w * ) ≲ ∥w * 0:k2 ∥ 2 2 N eff γ • µ M/2 (S k2:∞ H k2:∞ S ⊤ k2:∞ ) µ M (S k2:∞ H k2:∞ S ⊤ k2:∞ ) 2 + ∥w * k2:∞ ∥ 2 H k 2 :∞ .Theorem 6.4 (A general lower bound). Suppose Assumption 1 holds. Assume v 0 = 0, r(H) ≥ M and the initial stepsize γ < 1/ c tr(SHS ⊤ ) for some constant c > 0. ThenE w * Approx ≳ d i=M λ i , E w * Bias(w * ) ≳ i: λi<1/(Neffγ) µ i (SH 2 S ⊤ ) µ i (SHS ⊤ )almost surely, where (λ i ) d i=1 are eigenvalues of H in non-increasing order, ( λi ) d i=1 are eigenvalues of SHS ⊤ in non-increasing order. 
conclusion: 
 We analyze neural scaling laws in infinite-dimensional linear regression. We consider a linear predictor with M trainable parameters on the sketched covariates, which is trained by one-pass stochastic gradient descent with N data. Under a Gaussian prior assumption on the optimal model parameter and a power law (of degree a > 1) assumption on the spectrum of the data covariance, we derive matching upper and lower bounds on the population risk minus the irreducible error, that is, Θ(M -(a-1) + N -(a-1)/a ). In particular, we show that the variance error, which increases with M , is of strictly higher order compared to the other errors, thus disappearing from the risk bound. We attribute the nice empirical formula of the neural scaling law to the non-domination of the variance error, which ultimately is an effect of the implicit regularization of SGD.Many directions remain open for future study. First, our work is limited to the linear model; it would be interesting to see whether similar scaling laws can be derived in more complex models, such as random feature models or two-layer networks. Second, we focus on one-pass SGD training, and it is unclear if similar results hold for other optimization methods like accelerated SGD or Adam. Additionally, from a technical perspective, many results in our work depend on the Gaussian assumption and the source condition of the data. Investigating how these assumptions can be relaxed would also be valuable. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper is theoretical and we do not expect risk of such.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Our paper is theoretical and does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: For simplicity, we denoteA ⊗2 := A ⊗ A.Comments on Assumption 2, 3 and 4 Due to the rotational invariance of the Gaussian sketched matrix S, throughout the appendix, we assume w.l.o.g. that the covariance of the input covariates H is diagonal with the (i, i)-th entry being the i-th eigenvalue. Specifically, Assumption 3 can be rewritten as Assumption 6 (Source condition). Assume H = (h ij ) i,j≥1 is a diagonal matrix with diagonal entries in non-increasing order, and w * satisfies a prior such that for i ̸ = j, Ew * i w * j = 0; and for i > 0,Eλ i w * 2 i ≂ i -b , for some b > 1.Now that we assume H is diagonal. We make the following notations. DefineH k * :k † := diag(λ k * +1 , . . . , λ k † ) ∈ R (k † -k * ) 2 ,where 0 ≤ k * ≤ k † are two integers, and we allow k † = ∞. For example,H 0:k = diag(λ 1 , . . . , λ i ), H k:∞ = diag(λ k+1 , . . . ).Similarly, for a vector w ∈ H, we havew k * :k † := (w k * +1 , . . . , w * k † ) ⊤ ∈ R k † -k * .Recall the risk decomposition in (4),R M (v N ) = min R(•) Irreducible + min R M (•) -min R(•) Approx + R M (v N ) -min R M (•) Excess .Lemma A.1 (Approximization error). Conditional on the sketch matrix S, the minimizer of R M (v) is given by v * := (SHS ⊤ ) -1 SHw * , and the approximation error in (4) isEQUATIONMoreover, Approx ≤ ∥w * ∥ 2 H almost surely over the randomness of S.Proof of Lemma A.1. Recall that the riskR(w) := E ⟨x, w⟩ -y 2is a quadratic function and that w * is the minimizer of R(•), so we haveEQUATIONR(w) = E ⟨x, w⟩ -⟨x, w * ⟩ 2 + R(w * ) = ∥H 1 2 (w -w * )∥ 2 + R(w * ).Recall that the risk in a restricted subspaceR M (v) := R(S ⊤ v) = E ⟨Sx, v⟩ -y 2is also a quadratic function, so its minimizer is given byv * = E(Sx) ⊗2 -1 ESxy = SHS ⊤ -1 SHw * .Therefore, the approximation error isApprox := R M (v * ) -R(w * ) = R(S ⊤ v * ) -R(w * ) = ∥H 1 2 (S ⊤ v * -w * )∥ 2 = ∥H 1 2 (S ⊤ SHS ⊤ -1 SHw * -w * )∥ 2 = I -H 1 2 S ⊤ SHS ⊤ -1 SH 1 2 H 1 2 w * 2 .Finally, sinceI -H 1 2 S ⊤ SHS ⊤ -1 SH 1 2 2 = I -H 1 2 S ⊤ SHS ⊤ -1 SH 1 2 ⪯ I, it follows that Approx ≤ ∥w * ∥ 2 H .The excess risk in (4) can be viewed as the SGD excess risk in an M -dimensional (misspecified) linear regression problem. We will utilize Corollary 3.4 in [45] to get a bias-variance decomposition of the excess risk. The following two lemmas check the related assumptions for Corollary 3.4 in [45] in our setup. Lemma A.2 (Hypercontractivity and the misspecified noise under sketched feature). Suppose that Assumptions 5A and 5B hold. Conditioning on the sketch matrix S, for every PSD matrix A ∈ R M ×M , we haveE(Sx) ⊗2 A(Sx) ⊗2 ⪯ α tr SHS ⊤ A SHS ⊤ . Moreover, for the minimizer of R M (v), that is, v * defined in Lemma A.1, we have E y -⟨v * , Sx⟩ 2 (Sx) ⊗2 ⪯ 2(σ 2 + α∥w * ∥ 2 H )SHS ⊤ .The expectation in the above is over (x, y).Proof of Lemma A.2. The first part is a direct application of Assumption 5A:E(Sx) ⊗2 A(Sx) ⊗2 = S Exx ⊤ (S ⊤ AS)xx ⊤ S ⊤ ⪯ S α tr HS ⊤ AS H S ⊤ = α tr SHS ⊤ A SHS ⊤ .For the second part, we first show thatE y -⟨v * , Sx⟩ 2 x ⊗2 ⪯ 2E y -⟨w * , x⟩ 2 x ⊗2 + 2E⟨w * -S ⊤ v * , x⟩ 2 x ⊗2 ⪯ 2σ 2 H + 2α⟨H, (w * -S ⊤ v * ) ⊗2 ⟩H,where the last inequality is by Assumptions 5A and 5B. From the proof of Lemma A.1, we know that⟨H, (w * -S ⊤ v * ) ⊗2 ⟩ = Approx ≤ ∥w * ∥ 2 H , almost surely. So we have E y -⟨v * , Sx⟩ 2 x ⊗2 ⪯ 2(σ 2 + α∥w * ∥ 2 H )H.Left and right multiplying both sides with S and S ⊤ , we obtain the second claim.Lemma A.3 (Gaussianity and well-specified noise under sketched features). Suppose that Assumptions 1A and 1B hold. Conditional on the sketch matrix S, we haveSx ∼ N (0, SHS ⊤ ).Moreover, for the minimizer of R M (v), that is, v * defined in Lemma A.1, we haveE[y|Sx] = ⟨Sx, v * ⟩, E(y -⟨Sx, v * ⟩) 2 = σ 2 + Approx ≥ σ 2 .Proof of Lemma A.3. The first claim is a direct consequence of Assumption 1A.For the second claim, by Assumption 1A and Lemma A.1, we haveEQUATIONNotice that H -1 2 x ∼ N (0, I), by Assumption 1A and thatSH 1 2 I -H 1 2 S ⊤ (SHS ⊤ ) -1 SH 1 2 = 0, therefore Sx = SH 1 2 H -1 2 x is independent of I -H 1 2 S ⊤ (SHS ⊤ ) -1 SH 1 2 H -1 2 x.Taking expectation over the second random vector in (8), we findE[y|Sx] = EE[y|x] = ⟨SH 1 2 H -1 2 x, v * ⟩ = ⟨Sx, v * ⟩. It remains to show E(y -⟨Sx, v * ⟩) 2 = σ 2 + Approx. This follows from the proof of Lemma A.1. Specifically, E(y -⟨Sx, v * ⟩) 2 = R(S ⊤ v * ) = Approx + R(w * ) = Approx + σ 2 ≥ σ 2 ,where the second equality is by the definition of Approx and the third equality is by Assumption 1B.We have completed the proof.A.4 Proof of Theorem 6.1We now use the results in [44, 45] for SGD to obtain the following bias-variance decomposition on the excess risk. Theorem A.4 (Excess risk bounds). Consider the excess risk in (4) induced by the output of (SGD).LetN eff := N/ log(N ), SNR := (∥w * ∥ 2 H + ∥v 0 ∥ 2 SHS ⊤ )/σ 2 .Then conditioning on the sketch matrix S, for any w * ∈ H 1. Under Assumptions 5A and 5B, we haveEExcess ≲ N t=1 I -γ t SHS ⊤ (v 0 -v * ) 2 SHS ⊤ + (1 + αSNR)σ 2 • D eff N eff when γ ≲ 1 cα tr(SHS ⊤ )for some constant c > 0.2. Under Assumptions 1A and 1B, we haveEExcess ≳ N t=1 I -γ t SHS ⊤ (v 0 -v * ) 2 SHS ⊤ + σ 2 • D eff N eff when γ ≲ 1 c tr(SHS ⊤ ) for some constant c > 0.In both results, the expectation is over (x t , y t ) N t=1 , andD eff := #{ λj ≥ 1/(N eff γ)} + (N eff γ) 2 λj <1/(Neffγ) λ2 j ,where ( λj ) M j=1 are eigenvalue of SHS ⊤ . Theorem 6.1 follows immediately by Lemma A.1 and by setting v 0 = 0 and plugging the definition of Bias(w * ) and Var into Theorem A.4.Proof of Theorem A.4. This follows from Corollary 3.4 in [45] for a linear regression problem with population data given by (Sx, y). Note that the data covariance becomes SHS ⊤ and the optimal model parameter becomes v * .For the upper bound, Lemma A.2 verifies Assumptions 1A and 2 in [45] , with the noise level being σ2 = 2(σ 2 + α∥w * ∥ 2 H ). Then we can apply the upper bound in Corollary 3.4 in [45] (setting their index set K = ∅) to getEExcess ≲ N t=1 I -γ t SHS ⊤ (v 0 -v * ) 2 SHS ⊤ + (∥v * -v 0 ∥ 2 SHS ⊤ + σ2 ) D eff N eff .We verify that∥v * -v 0 ∥ 2 SHS ⊤ ≤ 2∥H 1 2 S ⊤ v * ∥ 2 + 2∥v 0 ∥ 2 SHS ⊤ = 2∥H 1 2 S ⊤ (SHS ⊤ ) -1 SHw * ∥ 2 + 2∥v 0 ∥ 2 SHS ⊤ ≤ 2∥H 1 2 w * ∥ 2 + 2∥v 0 ∥ 2 SHS ⊤ = 2∥w * ∥ 2 H + 2∥v 0 ∥ 2 SHS ⊤ , which implies that (∥v * -v 0 ∥ 2 SHS ⊤ + σ2 ) ≤ 2∥w * ∥ 2 H + 2∥v 0 ∥ 2 SHS ⊤ + 2(σ 2 + α∥w * ∥ 2 H ) ≲ (1 + αSNR)σ 2 .Substituting, we get the upper bound.For the lower bound, Lemma A.3 shows Sx is Gaussian, therefore it satisfies Assumption 1B in Wu et al. [45] with β = 1. Besides, Lemma A.3 shows that the linear regression problem is well-specified, with the noise level being σ2 = σ 2 + Approx ≥ σ 2 . Although the lower bound in Corollary 3.4 in Wu et al. [45] is stated for Gaussian additive noise (see their Assumption 2'), it is easy to check that the lower bound holds for any well-specified noise as described by Lemma A.3. Using the lower bound in Corollary 3.4 in Wu et al. [45] , we obtainEExcess ≳ N t=1 I -γ t SHS ⊤ (v 0 -v * ) 2 SHS ⊤ + σ2 D eff N eff .Plugging in σ2 ≥ σ 2 gives the desired lower bound.A.5 Proofs of Lemma 6.2, Theorem 6.3 and 6.4 R(w) = E(⟨x, w⟩ -y) 2 = E(⟨x, w⟩ -E[y | x]) 2 + E(y -E[y | x]) 2 = E(⟨x, w⟩ -⟨x, w * ⟩) 2 + σ 2 ≥ σ 2 .Note that the equality holds if and only if w = w * . Therefore we have minR(•) = R(w * ) = σ 2 .Proof of part 2. Part 2 of Theorem 4.1 follows immediately from Lemma C.2.Proof of part 3. We choose Bias(w * ), Var as defined in Eq. ( 5) and ( 6) and let Bias := E w * Bias(w * ). Part 3 of Theorem 4.1 follows directly from the decomposition of the excess risk in Theorem 6.1 (note that E∥w * ∥ 2 H /σ 2 ≲ 1), and the matching bounds in Lemma D.3 and E.1. It remains to verify the stepsize assumption required in Lemma D.3. Since we have from Lemma G.4 that1 tr(SHS ⊤ ) = 1 M i=1 λi ≥ c 1 M i=1 λ i ≥ c 2 M i=1 i -a ≥ c 3for some a-dependent constants c 1 , c 2 , c 3 > 0 with probability at least 1 -e -Ω(M ) , it follows that for any constant c > 1, we can choose γ ≤ c 0 for some a-dependent c 0 such that γ ≤ 1 c tr(SHS ⊤ ) . Therefore, we have verified the stepsize assumption.Finally, the last claim in Theorem 4.1 follows directly from combining the previous three parts and Theorem 6.1, noting σ 2 ≲ 1. and Var ≂ min{M, (N eff γ) 1/a } N eff ≲ (N eff γ) 1/a N eff ≲ (N eff γ) 1/a-1 ≲ Bias + ApproxE w * Approx ≂ M 1-b , Bias ≲ max M 1-b , (N eff γ) (1-b)/a , Bias ≳ (N eff γ) (1-b)/a when (N eff γ) 1/a ≤ M/3,Var ≂ min M, (N eff γ) 1/a /N eff , when the stepsize γ ≤ c for some a-dependent constant c > 0. Here the hidden constants in the bounds may depend only on (a, b). Combining the bounds on Approx, Bias, Var and noting Var ≂ min{M, (N eff γ) 1/a } N eff ≲ (N eff γ) 1/a N eff ≲ (N eff γ) (1-b)/a ≲E w * Approx ≂ log 1-a M, Bias ≲ max log 1-a M, log 1-a (N eff γ) , Bias ≳ log 1-a (N eff γ) when (N eff γ) 1/a ≤ M c for some small constant c > 0, Var ≂ min{M, (N eff γ)/ log a (N eff γ)} N eff ≲ (N eff γ)/ log a (N eff γ) N eff γ = log -a (N eff γ)with probability at least 1 -e -Ω(M ) when the stepsize γ ≤ c for some a-dependent constant c > 0.Since Var ≲ Bias and log 1-a (N eff γ) ≲ log 1-a M when (N eff γ) 1/a ≳ M c , putting the bounds together gives Theorem 4.3.In this section, we derive upper and lower bounds for the approximation error in (4) (and 7). We will also show that the upper and lower bounds match up to constant factors in several examples.Lemma C.1 (An upper bound on the approximation error). Given any k ≤ d such that r(H) ≥ k+M , the approximation error in (4) (and 7) satisfiesApprox ≲ ∥w * k:∞ ∥ 2 H k:∞ + ⟨[H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 , w * 0:k w * 0:k ⊤ ⟩almost surely, whereA k := S k:∞ H k:∞ S ⊤ k:∞ . If in addition k ≤ M/2, then with probability 1 -e -Ω(M ) Approx ≲ ∥w * k:∞ ∥ 2 H k:∞ + i>k λ i M + λ k+1 + i>k λ 2 i M ∥w * 0:k ∥ 2 ,where (λ i ) p i=1 are eigenvalues of H in non-increasing order.Proof Approx(S, H, w * ) = I -H 1 2 S ⊤ SHS ⊤ -1 SH 1 2 H 1 2 w * 2 = I -UΛ 1 2 S⊤ SΛ S⊤ -1 SΛ 1 2 U ⊤ UΛ 1 2 U ⊤ w * 2 = U I -Λ 1 2 S⊤ SΛ S⊤ -1 SΛ 1 2 Λ 1 2 U ⊤ w * 2 = I -Λ 1 2 S⊤ SΛ S⊤ -1 SΛ 1 2 Λ 1 2 w * 2 = Approx( S, Λ, w * ).Since S d = S by rotational invariance of standard gaussian variables, it suffices to analyze the case where H = Λ is a diagonal matrix, as the results may transfer to general H by replacing w * with w * . Therefore, from now on we assume w.l.o.g. that H is a diagonal matrix with non-increasing diagonal entries. Define A := SHS ⊤ .Approx = I -H 1 2 S ⊤ SHS ⊤ -1 SH 1 2 H 1 2 w * 2 = [H 1/2 S ⊤ A -1 SH 1/2 -I p ] ⊗2 , H 1/2 w * w * ⊤ H 1/2 .EQUATIONTherefore[H 1/2 S ⊤ A -1 SH 1/2 -I p ] ⊗2 = U 2 + VV ⊤ UV + VW V ⊤ U + WV ⊤ W 2 + V ⊤ V ⪯ 2 U 2 + VV ⊤ 0 0 W 2 + V ⊤ V ,and henceApprox ≤ 2 U 2 + VV ⊤ 0 0 W 2 + V ⊤ V , H 1/2 w * w * ⊤ H 1/2 = 2 U 2 + VV ⊤ , H 1/2 0:k w * ,0:k w ⊤ * ,0:k H 1/2 0:k + 2 W 2 + V ⊤ V, H 1/2 k:∞ w * ,k:∞ w ⊤ * ,k:∞ H 1/2k:∞ . We claim the following results which we will prove at the end of the proof.EQUATIONEQUATIONNote that in claim (11) the inverse A -1 k exists almost surely since r(H k:∞ ) ≥ r(H) -k ≥ M by our assumption and S k:∞ ∈ R M ×(d-k) is a random gaussian projection onto R M . First part of Lemma C.1 follows immediately from combining claim (10) and (11) .To prove the second part of Lemma C.1, first note that with probability 1 -e -Ω(M ) we haveµ min (A -1 k ) = ∥A k ∥ -1 ≥ c/ i>k λ i M + λ k+1 + i>k λ 2 iM forc some constant c > 0 by Lemma G.2. Moreover, by the concentration of the Gaussian variance matrix (see e.g., Theorem 6.1 in [41] ), we have S ⊤ 0:k S 0:k ⪰ I k /5 with probability 1 -e -Ω(M ) when M/k ≥ 2. Combining the last two arguments, we obtainS ⊤ 0:k A -1 k S 0:k ⪰ cS ⊤ 0:k S 0:k / i>k λ i M + λ k+1 + i>k λ 2 i M ≳ I k / i>k λ i M + λ k+1 + i>k λ 2 i M ,and therefore⟨[H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 , w * 0:k w * 0:k ⊤ ⟩ ≤ ⟨[S ⊤ 0:k A -1 k S 0:k ] -1 , w * 0:k w * 0:k ⊤ ⟩ ≤ ∥[H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 ∥∥w * 0:k ∥ 2 ≲ i>k λ i M + λ k+1 + i>k λ 2 i M ∥w * 0:k ∥ 2 (12)with probability 1 -e -Ω(M ) . Combining Eq. ( 12) with the first part of Lemma C.1 completes the proof.Proof of claim (10) Note that-I d-k ⪯ W = H 1/2 k:∞ S ⊤ k:∞ A -1 S k:∞ H 1/2 k:∞ -I d-k = H 1/2 k:∞ S ⊤ k:∞ (S 0:k H 0:k S ⊤ 0:k + S k:∞ H k:∞ S ⊤ k:∞ ) -1 S k:∞ H 1/2 k:∞ -I d-k ⪯ H 1/2 k:∞ S ⊤ k:∞ (S k:∞ H k:∞ S ⊤ k:∞ ) -1 S k:∞ H 1/2 k:∞ -I d-k ⪯ 0 d-k, where the last inequality uses the fact that the norm of projection matrices is no greater than one. Therefore, we have ∥W∥ 2 ≤ 1. Now, it remains to showEQUATIONas claim ( 10) is a direct consequence of Eq. ( 13) and the fact that ∥W∥ ≤ 1.By definition of W in Eq. ( 9), we haveW 2 = (H 1/2 k:∞ S ⊤ k:∞ A -1 S k:∞ H 1/2 k:∞ -I d-k ) 2 = I d-k -2H 1/2 k:∞ S ⊤ k:∞ A -1 S k:∞ H 1/2 k:∞ + H 1/2 k:∞ S ⊤ k:∞ A -1 S k:∞ H k:∞ S ⊤ k:∞ A -1 S k:∞ H 1/2 k:∞ = I d-k -2H 1/2 k:∞ S ⊤ k:∞ A -1 S k:∞ H 1/2 k:∞ + H 1/2 k:∞ S ⊤ k:∞ A -1 A k A -1 S k:∞ H 1/2k:∞ . By definition of V in Eq. ( 9), we haveV ⊤ V = H 1/2 k:∞ S ⊤ k:∞ A -1 (S 0:k H 0:k S ⊤ 0:k )A -1 S k:∞ H 1/2 k:∞ . Since S 0:k H 0:k S ⊤ 0:k + A k = A, it follows that W 2 + V ⊤ V = I d-k -2H 1/2 k:∞ S ⊤ k:∞ A -1 S k:∞ H 1/2 k:∞ + H 1/2 k:∞ S ⊤ k:∞ A -1 AA -1 S k:∞ H 1/2 k:∞ = I d-k -H 1/2 k:∞ S ⊤ k:∞ A -1 S k:∞ H 1/2 k:∞ = -W. Proof of claim (11) It suffices to show U 2 +V ⊤ V = [H -1 0:k +S ⊤ 0:k A -1 k S 0:k ] -1 .Using the definition of U in Eq. ( 9), we obtainU = H 1/2 0:k S ⊤ 0:k A -1 S 0:k H 1/2 0:k -I k = H 1/2 0:k S ⊤ 0:k A -1 k S 0:k H 1/2 0:k -H 1/2 0:k S ⊤ 0:k A -1 k S 0:k [H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 S ⊤ 0:k A -1 k S 0:k H 1/2 0:k -I k = H 1/2 0:k S ⊤ 0:k A -1 k S 0:k [H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 H -1 0:k H 1/2 0:k -I k, where the second line uses Woodbury's matrix identity, namelyEQUATIONSinceH 1/2 0:k S ⊤ 0:k A -1 = H 1/2 0:k S ⊤ 0:k A -1 k -H 1/2 0:k S ⊤ 0:k A -1 k S 0:k [H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 S ⊤ 0:k A -1 k = H -1/2 0:k [H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 S ⊤ 0:k A -1k by Woodbury's matrix indentity, it follows from the definition of V in Eq. ( 9) thatEQUATION)Combining Eq. ( 14) and (15) yieldsEQUATIONand thereforeU 2 + VV ⊤ , H 1/2 0:k w * ,0:k w ⊤ * ,0:k H 1/2 0:k = ⟨[H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 , w * 0:k w * 0:k ⊤ ⟩.For the approximation error Approx, we have the following result. Lemma C.2 (Lower bound on the approximation error). When r(H) ≥ M , under Assumption 1C, the approximation error in (4) (and 7) satisfiesE w * Approx ≳ d i=M λ i ,where (λ i ) d i=1 are eigenvalues of H in non-increasing order.Proof of Lemma C.2. For any k ≤ d, following the proof of Lemma C.1, we haveApprox = [H 1/2 S ⊤ A -1 SH 1/2 -I d ] ⊗2 , H 1/2 w * (w * ) ⊤ H 1/2andEQUATIONTherefore[H 1/2 S ⊤ A -1 SH 1/2 -I d ] ⊗2 = U 2 + VV ⊤ UV + VW V ⊤ U + WV ⊤ W 2 + V ⊤ V and E w * Approx = E w * U 2 + VV ⊤ , H 1/2 0:k w * 0:k w * 0:k H 1/2 0:k + E w * W 2 + V ⊤ V, H 1/2 0:k w * k:∞ w * k:∞ H 1/2 k:∞ + 2E w * UV + VW, H 1/2 0:k w * 0:k w * k:∞ H 1/2 k:∞ = tr((U 2 + VV ⊤ )H 0:k ) + tr((W 2 + V ⊤ V)H k:∞ ),where the last line uses the fact that E w * (w * ) ⊗2 = I d . Using Eq. ( 13) and ( 16) in the proof of Lemma C.1, we further obtainE w * Approx = tr(H -1/2 0:k [H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 H -1/2 0:k H 0:k ) -tr(WH k:∞ ) = tr([H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 ) -tr(WH k:∞ ) ≥ -tr(WH k:∞ ) =: T 3 .whereA k := S k:∞ H k:∞ S ⊤ k:∞ .For T 3 , we further haveT 3 = tr(H 1/2 k:∞ [I d-k -H 1/2 k:∞ S ⊤ k:∞ A -1 S k:∞ H 1/2 k:∞ ]H 1/2 k:∞ ) ≥ tr(H 1/2 k:∞ [I d-k -H 1/2 k:∞ S ⊤ k:∞ A -1 k S k:∞ H 1/2 k:∞ ]H 1/2 k:∞ ) ≥ d-k i=1 µ i (I d-k -H 1/2 k:∞ S ⊤ k:∞ A -1 k S k:∞ H 1/2 k:∞ ) • µ d+1-k-i (H k:∞ ),where the second line is due to A ⪰ A k (and hence -A -1 ⪰ -A -1 k ), the third line follows from Von-Neuman's inequality. SinceM := I d-k -H 1/2 k:∞ S ⊤ k:∞ A -1 k S k:∞ H 1/2k:∞ is a projection matrix such that M 2 = M and tr(I d-k -M) = M , it follows that M has M eigenvalues 0 and d -k -M eigenvalues 1. Therefore, we further haveT 3 ≥ d-k i=1 µ i (M) • µ d+1-k-i (H k:∞ ) ≥ d i=k+M λ ifor any k ≤ d. Letting k = 0 maximizes the lower bound and concludes the proof.Lemma C.3 (Lower bound on the approximation error under Assumption 3). Under Assumption 3, the approximation error in (4) (and 7) satisfiesE w * Approx ≳ d i=M λ i i a-b ,where (λ i ) d i=1 are eigenvalues of H in non-increasing order and the inequality hides some (a, b)dependent constant.Proof of Lemma C.3. The proof is essentially the same as the proof of Lemma C.2 but we include it here for completeness. Let H w := E[w * w * ⊤ ] be the covariance of the prior on w * . Following the proof of Lemma C.2, we haveE w * Approx = E w * U 2 + VV ⊤ , H 1/2 0:k w * 0:k w * 0:k H 1/2 0:k + E w * W 2 + V ⊤ V, H 1/2 0:k w * k:∞ w * k:∞ H 1/2 k:∞ + 2E w * UV + VW, H 1/2 0:k w * 0:k w * k:∞ H 1/2 k:∞ = tr((U 2 + VV ⊤ )H 0:k H w 0:k ) + tr((W 2 + V ⊤ V)H k:∞ H w k:∞ ),where the last line uses Assumption 3 and notice that H, H w are both diagonal. Next, similar to the proof of Lemma C.2, using Eq. ( 13) and ( 16), we deriveE w * Approx = tr(H -1/2 0:k [H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 H -1/2 0:k H 0:k H w 0:k ) -tr(WH k:∞ H w k:∞ ) = tr([H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 H w 0:k ) -tr(WH k:∞ H w k:∞ ) ≥ -tr(WH k:∞ H w k:∞ ) =: T3 where A k := S k:∞ H k:∞ S ⊤ k:∞ .For T3 , following the same argument for T 3 in the proof of Lemma C.2, we haveT3 ≥ d-k i=1 µ i (I d-k -H 1/2 k:∞ S ⊤ k:∞ A -1 k S k:∞ H 1/2 k:∞ ) • µ d+1-k-i (H k:∞ H w k:∞ ) ≥ d i=k+M µ i (HH w ) ≳ d i=k+M i a-b λ i ,for any k ≤ d where the last inequality uses Assumption 3. Setting k = 0 maximizes the lower bound and concludes the proof.In this section, we derive matching upper and lower bounds for Approx (defined in Eq. 4 and 7) in three concrete examples: power-law spectrum (Lemma C.4), power-law spectrum with source condition (Lemma C.5) and logarithmic power-law spectrum (Lemma D.5).Lemma C.4 (Bounds on Approx under the power-law spectrum). Suppose Assumption 1C and 2 hold. Then with probability at least 1 -e -Ω(M ) over the randomness of SM 1-a ≲ E w * Approx ≲ M 1-a .Here, the hidden constants only depend on the power-law degree a.Proof of Lemma C.4. For the upper bound, by Lemma C.1 and noting Ew * 2 i = 1 for all i, we have with probability at least 1 -e -Ω(M )E w * Approx ≲ k>k1 λ i + i>k1 λ i M + λ k1+1 + i>k1 λ 2 i M • k 1 ≲ k 1-a 1 + k 1-a 1 M + k -a 1 + k 1-2a 1 M k 1 ≲ k 1 M + 1 k 1-a 1 for any given k 1 ≤ M/2.Here the hidden constants depend on a. Therefore, letting k 1 = M/2 in the upper bound yieldsE w * Approx ≲ M 1-awith probability at least 1 -e -Ω(M ) .For the lower bound, we have from Lemma C.2 thatE w * Approx ≳ ∞ i=M i -a ≳ M 1-a .This completes the proof.Lemma C.5 (Bounds on Approx under the source condition). Suppose Assumption 3 hold. Then with probability at least 1 -e -Ω(M ) over the randomness of SM 1-b ≲ E w * Approx ≲ M 1-b .Here, the hidden constants only depend on the power-law degrees a, b.Proof of Lemma C.5. For the upper bound, by Lemma C.1 and noting Ew * 2 i ≂ i a-b for all i, we have with probability at least 1 -e -Ω(M )Approx ≲ k>k1 λ i i a-b + i>k1 λ i M + λ k1+1 + i>k1 λ 2 i M • k 1+a-b 1 ≲ k 1-b 1 + k 1-a 1 M + k -a 1 + k 1-2a 1 M k 1+a-b 1 ≲ k 1 M + 1 k 1-b 1 for any given k 1 ≤ M/2.Here the hidden constants depend on a, b. Moreover, choosing k 1 = M/2 in the upper bound givesE w * Approx ≲ M 1-bwith probability at least 1 -e -Ω(M ) .For the lower bound, we have from Lemma C.3 thatE w * Approx ≳ ∞ i=M i -a • i a-b ≳ M 1-b .This completes the proof.Lemma C.6 (Bounds on Approx under the logarithmic power-law spectrum). Suppose Assumption 4 hold. Then with probability at least 1 -e -Ω(M ) over the randomness of Slog 1-a M ≲ E w * Approx ≲ log 1-a M.Here, the hidden constants only depend on the power-law degree a.Proof of Lemma C.6. For the upper bound, by Lemma C.1 and noting Ew * 2 i = 1 for all i, we have with probability at least 1 -e -Ω(M )Approx ≲ k>k1 λ i + i>k1 λ i M + λ k1+1 + i>k1 λ 2 i M k 1 ≲ log 1-a k 1 + log 1-a k 1 M + k -1 1 log -a k 1 + k 1-2a 1 M k 1 ≲ 1 + k 1 M + 1 log k 1 + 1 log k 1 k 1 M log 1-a k 1 ≲ log 1-a k 1for any given k 1 ≤ M/2, where the third line uses i>k1λ 2 i ≲ 1/(k 1 log 2a k 1 ). Choosing k 1 = M/2, we obtain E w * Approx ≲ log 1-a Mwith probability at least 1 -e -Ω(M ) . Here the hidden constants depend on a, b.For the lower bound, we have from Lemma C.2 thatE w * Approx ≳ ∞ i=M λ i ≳ ∞ i=M i -1 log -a i ≳ log 1-a M.Therefore, we have established matching upper and lower bounds for Approx.In this section, we derive upper and lower bounds for Bias(w * ) defined in Eq. ( 5). Moreover, we show that the upper and lower bounds match up to constant factors in concrete examples.Lemma D.1 (Upper bound on the bias term). Suppose the initial stepsize γ ≤ 1 c tr(SHS ⊤ ) for some constant c > 1. Then for any w * ∈ H and k ∈ [d] such that r(H) ≥ k + M , the bias term in (5) satisfiesBias(w * ) ≲ 1 N eff γ ∥v * ∥ 2 2 .Moreover, for any k ≤ M/3 such that r(H) ≥ k + M , the bias term satisfiesBias(w * ) ≲ ∥w * 0:k ∥ 2 2 N eff γ • µ M/2 (A k ) µ M (A k ) 2 + ∥w * k:∞ ∥ 2 H k:∞with probability 1 -e -Ω(M ) , whereA k := S k:∞ H k:∞ S ⊤ k:∞ , {µ i (A k )} Mi=1 denote the eigenvalues of A k in non-increasing order for some constant c > 1.Proof of Lemma D.1. Similar to the proof of Lemma C.1, we can without loss of generality assume the covariance matrix H = diag{λ 1 , λ 2 , . . . , λ d } where λ i ≥ λ j for any i ≥ j. Let SH 1/2 = Ũ Λ1/2 0 Ṽ⊤ be the singular value decomposition of SHS ⊤ , where Λ := diag{ λ1 , λ2 , . . . , λd } is a diagonal matrix diagonal entries in non-increasing order. DefineA k := S k:∞ H k:∞ S ⊤ k:∞ . Then it follows from similar arguments as in Lemma C.1 that A k is invertible. Since ∥γ t SHS ⊤ ∥ 2 = γ t λ1 ≤ γ λ1 ≤ λ1 c M i=1 λi ≤ 1for some constant c > 1 by the stepsize assumption, it follows that I M -γ t SHS ⊤ ≻ 0 M for all t ∈ [N ]. Therefore, it can be verified thatN t=1 (I M -γ t SHS ⊤ )SHS ⊤ N t=1 (I M -γ t SHS ⊤ ) ⪯ (I M -γSHS ⊤ ) Neff SHS ⊤ (I M -γSHS ⊤ ) Neff =: M,and by definition of Bias(w * ) in Eq. ( 5), we haveEQUATION)Note that the eigenvalues ofEQUATION)for some constant c > 0. The first part of Lemma D.1 follows immediately.D.1. Recall that v * = SHS ⊤ -1 SHw * . Substituting SH = (S 0:k H 0:k S k:∞ H k:∞ ) into v * , we obtain ⟨M, v * ⊗2 ⟩ = ⟨M, ((SHS ⊤ ) -1 SHw * ) ⊗2 ⟩ = w * ⊤ HS ⊤ (SHS ⊤ ) -1 M(SHS ⊤ ) -1 SHw * ≤ 2T 1 + 2T 2 ,whereEQUATIONEQUATIONWe claim the following results which we prove later. With probability 1 -e -Ω(M )EQUATIONfor some constant c > 0.EQUATIONCombining Eq. ( 22a), (22b) gives the second part of Lemma D.1.Proof of claim (22a) By definition of T 1 , we haveT 1 ≤ ∥H 0:k S ⊤ 0:k (SHS ⊤ ) -1 M(SHS ⊤ ) -1 S 0:k H 0:k ∥ 2 • ∥w * 0:k ∥ 2 2 . Moreover, ∥H 0:k S ⊤ 0:k (SHS ⊤ ) -1 M(SHS ⊤ ) -1 S 0:k H 0:k ∥ 2 ≤ ∥M∥ 2 • ∥(SHS ⊤ ) -1 S 0:k H 0:k ∥ 2 2 ≤ c N eff γ ∥(SHS ⊤ ) -1 S 0:k H 0:k ∥ 2 2for some constant c > 0, where the last line uses Eq. (19) .It remains to showEQUATIONfor some constant c > 0 with probability 1 -e -Ω(M ) . Since SHS ⊤ = S 0:k H 0:k S ⊤ 0:k + A k , we haveEQUATIONwhere the second line uses Woodbury's identity. SinceH -1 0:k + S ⊤ 0:k A -1 k S 0:k ⪰ S ⊤ 0:k A -1 k S 0:k , it follows that ∥[H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 ∥ 2 ≤ ∥[S ⊤ 0:k A -1 k S 0:k ] -1 ∥ 2 .Therefore, with probability at least 1 -e -Ω(M )∥A -1 k S 0:k [H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 ∥ 2 ≤ ∥A -1 k ∥ 2 • ∥S 0:k ∥ 2 • ∥[H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 ∥ 2 ≤ ∥A -1 k ∥ 2 • ∥S 0:k ∥ 2 • ∥[S ⊤ 0:k A -1 k S 0:k ] -1 ∥ 2 ≤ ∥A -1 k ∥ 2 • ∥S 0:k ∥ 2 µ min (S ⊤ 0:k A -1 k S 0:k ) ≲ ∥A -1 k ∥ 2 µ min (S ⊤ 0:k A -1 k S 0:k )where the last inequality follows from the fact that ∥S 0:k ∥ 2 = ∥S ⊤ 0:k S 0:k ∥ 2 ≤ c for some constant c > 0 when k ≤ M/2 with probability at least 1 -e -Ω(M ) . Since S 0:k is independent of A k and the distribution of S 0:k is rotationally invariant, we may writeS ⊤ 0:k A -1 k S 0:k = M i=1 1 λM-i si s⊤ i ,where si iid ∼ N (0, I k /M ) and ( λi ) M i=1 are eigenvalues of A k in non-increasing order. Therefore, for k ≤ M/3EQUATIONfor some constant c > 0 with probability at least 1 -e -Ω(M ) , where in the last line we again use the concentration properties of gaussian covariance matrices (see e.g., Theorem 6.1 in [41] ). As a direct consequence, we have∥A -1 k S 0:k [H -1 0:k + S ⊤ 0:k A -1 k S 0:k ] -1 ∥ 2 ≤ c • µ M/2 (A k ) µ M (A k )with probability at least 1 -e -Ω(M ) for some constant c > 0. This concludes the proof.Proof of claim (22b) By definition of T 2 in Eq. ( 21), we haveT 2 = w * k:∞ ⊤ H k:∞ S ⊤ k:∞ (SHS ⊤ ) -1/2 (I M -γSHS ⊤ ) 2Neff (SHS ⊤ ) -1/2 S k:∞ H k:∞ w * k:∞ ≤ w * k:∞ ⊤ H k:∞ S ⊤ k:∞ (SHS ⊤ ) -1 S k:∞ H k:∞ w * k:∞ ≤ ∥H 1/2 k:∞ S ⊤ k:∞ (SHS ⊤ ) -1 S k:∞ H 1/2 k:∞ ∥ • ∥w * k:∞ ∥ 2 H k:∞ ≤ ∥w * k:∞ ∥ 2 H k:∞ , where the last line follows from ∥H 1/2 k:∞ S ⊤ k:∞ (SHS ⊤ ) -1 S k:∞ H 1/2 k:∞ ∥ 2 = ∥H 1/2 k:∞ S ⊤ k:∞ (S 0:k H 0:k S ⊤ 0:k + S k:∞ H k:∞ S ⊤ k:∞ ) -1 S k:∞ H 1/2 k:∞ ∥ 2 ≤ ∥H 1/2 k:∞ S ⊤ k:∞ A -1 k S k:∞ H 1/2 k:∞ ∥ 2 ≤ 1.Lemma D.2 (Lower bound on the bias term). Suppose w * follows some prior distribution and the initial stepsize γ ≤ 1 c tr(SHS ⊤ ) for some constant c > 2. Let H w := Ew * w * ⊤ . Then the bias term in Eq. ( 5) satisfiesE w * Bias(w * ) ≳ i: λi<1/(γNeff) µ i (SHH w HS ⊤ ) µ i (SHS ⊤ )almost surely, whereM N := SHS ⊤ (I -2γSHS ⊤ 2Neff .Proof of Lemma D.2. Adopt the notations in the proof of Lemma D.1. By definition of the bias term, we haveEQUATIONwhere the third line usesI M -2γ t SHS ⊤ ≻ 0 M for all t ∈ [N ] established in the proof of Lemma D.1, N i=1 γ i ≤ 2γN eff , and the fact that (1 -w)(1 -v) ≥ 1 -w -v for w, v > 0.Substituting the definition of v * in Eq. ( 5) into the expression, we obtainE w * Bias(w * ) ≳ E w * ⟨M N , v * ⊗2 ⟩ = E w * ⟨M N , ((SHS ⊤ ) -1 SHw * ) ⊗2 ⟩ ≳ λi<1/(Neffγ),i≤M i -2a i -a = λi<1/(Neffγ),i≤M i -a ≳ (N eff γ) 1/a-1with probability at least 1 -e -Ω(M ) . Here, the hidden constants depend only on a.Lemma D.4 (Bounds on Bias under the source condition). Suppose Assumption 3 hold and the initial stepsize γ ≤ 1 c tr(SHS ⊤ ) for some constant c > 2. Then with probability at least 1 -e -Ω(M ) over the randomness of S E w * Bias(w * ) ≲ max (N eff γ) (1-b)/a , M 1-b , andE w * Bias(w * ) ≳ (N eff γ) (1-b)/awhen (N eff γ) 1/a ≤ M/c for some constant c > 0. In both results, the hidden constants depend only on a, b.Proof of Lemma D.4. For the upper bound, using Lemma G.5, D.1 and the assumption that (w.l.o.g.) Ew * 2 i ≂ i a-b for all i > 0, with probability at least 1 -e -Ω(M ) , we haveE w * Bias(w * ) ≲ E w * ∥w * 0:k2 ∥ 2 2 N eff γ + ∥w * k2:∞ ∥ 2 H k 2 :∞ ≲ k 1+a-b 2 N eff γ + k>k2 λ i • i a-b ≲ k 1+a-b 2 N eff γ + k 1-b 2 ≲ max (N eff γ) (1-b)/a , M 1-bwhen b < a + 1, where in the last inequality, we choose k 2 = [M/3] ∧ (N eff γ) 1/a to minimize the upper bound.When (N eff γ) 1/a ≤ M/c for some large constant c > 0, combining Lemma D.2 and G.4 yields the lower boundE w * Bias(w * ) ≳ i: λi<1/(Neffγ) µ i (SHH w HS ⊤ ) µ i (SHS ⊤ ) ≂ i: λi<1/(Neffγ) µ i (SH (a+b)/a S ⊤ ) µ i (SHS ⊤ ) , ≳ λi<1/(Neffγ),i≤M i -(a+b) i -a = λi<1/(Neffγ),i≤M i -b ≳ (N eff γ) (1-b)/awith probability at least 1 -e -Ω(M ) . Here, the hidden constants depend only on a, b.Upper bound when b ≥ a + 1. Following the previous derivations, when b = a + 1, we have with probability at least 1 -e -Ω(M )E w * Bias(w * ) ≲ E w * ∥w * 0:k2 ∥ 2 2 N eff γ + ∥w * k2:∞ ∥ 2 H k 2 :∞ ≲ log k 2 N eff γ + k 1-b 2 ≲ log(N eff γ) N eff γ + M 1-bwhere the last line follows by setting k 2 = [M/3] ∧ (N eff γ) 1/a . When b > a + 1, we have with probability at least 1 -e -Ω(M )E w * Bias(w * ) ≲ E w * ∥w * 0:k2 ∥ 2 2 N eff γ + ∥w * k2:∞ ∥ 2 H k 2 :∞ ≲ 1 N eff γ + k 1-b 2 ≲ 1 N eff γ + M 1-b ,where the last follows by chooing k 2 = M/3 to minimize the upper bound.Note that there exist non-constant gaps between the upper and lower bounds on the bias term in the simple regime where b ≥ a + 1. We leave a more precise analysis of the bias term for future work.Lemma D.5 (Bounds on Bias under the logarithmic power-law spectrum). Suppose Assumption 4 hold and the initial stepsize γ ≤1 c tr(SHS ⊤ ) for some constant c > 2. Let k := inf{k : k log a k ≥ N eff γ}.Then with probability at least 1 -e -Ω(M ) over the randomness of S E w * Bias(w * ) ≲ max log 1-a (N eff γ), log 1-a M , andE w * Bias(w * ) ≳ log 1-a (N eff γ)when (N eff γ) ≤ M c for some sufficiently small constant c > 0. Here, all constants depend only on the power-law degree a.Proof of Lemma D.5. For the upper bound, using Lemma G.7, D.1 and the assumption that Ew * 2 i = 1 for all i > 0, with probability at least 1 -e -Ω(M ) , we haveE w * Bias(w * ) ≲ E w * ∥w * 0:k2 ∥ 2 2 N eff γ + ∥w * k2:∞ ∥ 2 H k 2 :∞ ≲ k 2 N eff γ + k>k2 λ i ≂ k 2 N eff γ + log 1-a k 2 ≲ max log 1-a (N eff γ), log 1-a M ,where in the last inequality, we choose k 2 = [M/3] ∧ (N eff γ)/ log a (N eff γ) to minimize the upper bound.Recall k * ≂ M/ log M (for example we may define k * = inf{k : k log k ≥ M }) in Lemma G.6. Combining Lemma D.2 and G.6 gives the lower boundE w * Bias(w * ) ≳ i: λi<1/(Neffγ) µ i (SHH w HS ⊤ ) µ i (SHS ⊤ ) ≂ i: λi<1/(Neffγ) µ i (SH 2 S ⊤ ) µ i (SHS ⊤ ) , ≳ λi<1/(Neffγ),i≤k * i -2 log -2a i i -1 log -a i = λi<1/(Neffγ),i≤k * i -1 log -a i ≳ k * i=Neffγ i -1 log -a i ≳ log 1-a (N eff γ) -log 1-a (k * ) ≳ log 1-a (N eff γ) -c 1 log 1-a (M )with probability at least 1 -e -Ω(M ) for some constant c 1 > 0. Here, the (hidden) constants depend only on a. Therefore, when (N eff γ) 1/a ≤ M c for some sufficiently small constant c > 0, we haveE w * Bias(w * ) ≳ log 1-a (N eff γ) -c 1 log 1-a (M ) ≳ log 1-a (N eff γ).with probability at least 1 -e -Ω(M ) .In this section, we present matching upper and lower bounds on the variance term Var defined in (6) under the power-law or logarithmic power-law spectrum. Lemma E.1 (Matching bounds on Var under power-law spectrum). Under Assumption 2, Var defined in Eq. ( 6) satisfiesVar ≂ min{M, (N eff γ) 1/a } N eff with probability at least 1 -e -Ω(M ) over the randomness of S. Here, the hidden constants only depend on a.Proof of Lemma E.1. By the definition of Var in Eq. ( 6) and Lemma G.4, we haveVar = #{ λj ≥ 1/(N eff γ)} + (N eff γ) 2 λj <1/(Neffγ) λ2 j N eff ≂ min M, (N eff γ) 1/a + (N eff γ) 2 • (N eff γ) (1-2a)/a N eff ≂ min{M, (N eff γ) 1/a } N effwith probability at least 1 -e -Ω(M ) over the randomness of S. Here the hidden constants may depend on a. 6) and Lemma G.6, we haveVar = #{ λj ≥ 1/(N eff γ)} + (N eff γ) 2 λj <1/(Neffγ) λ2 j N eff = D N eff ≂ min{M, k} N effwith probability at least 1 -e -Ω(M ) over the randomness of S, where the second line follows fromD ≳ #{ λj ≥ 1/(N eff γ)} ≂ N eff γ log a (N eff γ), andD ≲ N eff γ log a (N eff γ) + (N eff γ) 2 log 2a (N eff γ) • j: λj <1/(Neffγ) 1 j 2 ≲ N eff γ log a (N eff γ) when k ≲ M.In this section, we study the expected risk of the average of (SGD) iterates. Namely, we consider a fixed stepsize (SGD) procedure where γ t = γ and define vN := Compared with the last iterate of (SGD) with geometrically decaying stepsizes, we show that the average of (SGD) iterates with a fixed stepsize achieves a better risk, in the sense that the effective sample size N eff is replaced by N in the bounds (c.f. Theorem 4.1). This may give improvement up to logarithmic factors.We start with invoking the following result in [48] . Theorem F.1 (A variant of Theorem 2.1 and 2.2 in [48] ). Suppose Assumption 1 hold. Consider an M -dimensional sketched predictor trained by fixed stepsize (SGD) with N samples. Let vN := N -1 i=0 v i /N be the average of the iterations of SGD. Assume v 0 = 0 and σ 2 ≳ 1. Conditional on S and suppose the stepsize γ < 1/(c tr(SHS ⊤ )) for some constant c > 0, then there exist Approx, Bias, Var such thatER M (v N ) -σ 2 ≂ E w * Approx + Bias + σ 2 Var,where the expectation of R M is over w * and (x i , y i ) N i=1 andApprox := Eξ 2 = I -H 1 2 S ⊤ SHS ⊤ -1 SH 1 2 H 1 2 w * 2 , E w * (T 1 + T 3 ) ≲ Bias ≲ E w * (T 2 + T 4 ), Var ≂ D eff,N N ,andEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONwhere ( λj ) M j=1 are eigenvalue of SHS ⊤ .See Section F.2.1 for the proof.For T i (i = 1, 2, 3, 4), we also have the following upper (and lower) bounds. Lemma F.2 (Lower bound on T 1 ). Under the assumptions and notations in Theorem F.1, we haveE w * T 1 ≳ i: λi<1/(γN ) µ i (SH 2 S ⊤ ) µ i (SHS ⊤ )almost surely, where ( λi ) N i=1 are eigenvalues of SHS ⊤ in non-increasing order.See the proof in Section F.2.2. Lemma F.3 (Upper bound on T 2 ). Under the assumptions and notations in Theorem F.1, for any k ≤ M/3 such that r(H) ≥ k + M , we have with probability at least 1 -e -Ω(M ) thatT 2 ≲ 1 N γ µ M/2 (A k ) µ M (A k ) 2 • ∥w * 0:k ∥ 2 + ∥w * k:∞ ∥ 2 H k:∞ ,where The errobars denotes the ±1 standard deviation of estimating the expected risk using 100 independent samples of (w * , S). We use linear functions to fit the expected risk under log-log scale and report the slope of the fitted lines (denoted by k).A k := S k:∞ H k:∞ S ⊤ k:∞ .Let f 1 (A) := (I -(I -γA) N/4 ) 2 A -1 /γ 2 /N 2 for any positive definite matrix A ∈ R M ×M . Since γ ≤ 1/(c tr(SHS ⊤ )), we have f 1 (SHS ⊤ ) ⪰ 0. By definition of T 1 and recalling v * = (SHS ⊤ ) -1 SHw * , we have with probability at least 1 -e -Ω(M ) thatE w * T 1 = E w * [w * ⊤ HS ⊤ (SHS ⊤ ) -1 f 1 (SHS ⊤ )(SHS ⊤ ) -1 SHw * ] = tr [(SHS ⊤ ) -1 f 1 (SHS ⊤ )(SHS ⊤ ) -1 ](SH 2 S ⊤ ) .Following the proof of Lemma D.2 (by Von Neumann's trace inequality), we haveE w * T 1 ≥ M i=1 µ i (SH 2 S ⊤ ) µ i (SHS ⊤ ) 2 f 1 (SHS ⊤ ) -1 ≥ i: λi<1/(γN ) µ i (SH 2 S ⊤ ) µ i (SHS ⊤ ) 2 f 1 (SHS ⊤ ) -1 ≳ i: λi<1/(γN ) µ i (SH 2 S ⊤ ) µ i (SHS ⊤ ) ,where the third inequality is due toλ/f 1 (λ) ≲ λ 2 γ 2 N 2 (1 -(1 -γλ) N/4 ) 2 ≲ N 2 ( N/4-1 i=0 (1 -γλ) i ) 2 ≲ 1 (1 -γλ) 2N ≲ 1 when λ < 1/(N γ). F.2.3 Proof of Lemma F.3By definition of T 2 , the fact that 1 -x N = (1 -x) N -1 i=0 x i , and recalling v * = (SHS ⊤ ) -1 SHw * , we haveT 2 = w * ⊤ HS ⊤ f 2 (SHS ⊤ )SHw * , ≤ 2[w * 0:k ⊤ H 0:k S ⊤ 0:k f 2 (SHS ⊤ )S 0:k H 0:k w * 0:k T21 + w * k:∞ ⊤ H k:∞ S ⊤ k:∞ f 2 (SHS ⊤ )S k:∞ H k:∞ w * k:∞ T22 ],wheref 2 (A) := [ N -1 i=0 (I -γA) i ] 2 /A/N 2 for any symmetric matrix A ∈ R M ×M. Moreover, we haveT 21 = w * 0:k ⊤ H 0:k S ⊤ 0:k f 2 (SHS ⊤ )S 0:k H 0:k w * 0:k ≤ ∥f 2 (SHS ⊤ )(SHS ⊤ ) 2 ∥ • ∥(SHS ⊤ ) -1 S 0:k H 0:k w * 0:k ∥ 2 .Using the assumption on the stepsize that γ ≤ 1/(c tr(SHS ⊤ )), we haveEQUATION)Combining Eq. ( 28) with Eq. ( 23) in the proof of Lemma D.1 (note that we assume k ≤ M/3), we obtainT 21 ≤ c 1 N γ µ M/2 (A k ) µ M (A k ) 2 • ∥w * 0:k ∥ 2for some constant c > 0 with probability at least 1 -e -Ω(M ) . For T 22 , we have EQUATION∥(SHS ⊤ ) -1/2 S k:∞ H 1/2 k:∞ ∥ 2 = ∥H 1/2 k:∞ S ⊤ k:∞ (SHS ⊤ ) -1 S k:∞ H 1/2 k:∞ ∥ = ∥H 1/2 k:∞ S ⊤ k:∞ (S 0:k H 0:k S ⊤ 0:k + S k:∞ H k:∞ S ⊤ k:∞ ) -1 S k:∞ H 1/2 k:∞ ∥ ≤ ∥H 1/2 k:∞ S ⊤ k:∞ (S k:∞ H k:∞ S ⊤ k:∞ ) -1 S k:∞ H 1/2 k:∞ ∥ = 1, it follows that T 22 ≤ ∥w * k:∞ ∥ 2EQUATIONWe thus haveEQUATIONCombining Eq. ( 31) and ( 29) completes the proof.Substituting v * = (SHS ⊤ ) -1 SHw * in the expression of T 4 and noting v 0 = 0, we haveEQUATIONwheref 4 (A) := A -1 I-(I-γA) 2N A -1 /(N γ) for any symmetric matrix A ∈ R M ×M . Moreover, tr w * ⊤ HS ⊤ f 4 (SHS ⊤ )SHw * ≤ ∥f 4 (SHS ⊤ )SHS ⊤ ∥ • ∥(SHS ⊤ ) -1/2 SH 1/2 ∥ 2 • ∥w * ∥ 2 H ≤ ∥f 4 (SHS ⊤ )SHS ⊤ ∥ • ∥w * ∥ 2 H . Since ∥f 4 (SHS ⊤ )SHS ⊤ ∥ = 1 N ∥ 2N -1 i=0 (I -γSHS ⊤ ) i ∥ ≤ 2by our assumption on the stepsize, it follows thatEQUATION) Combining Eq. ( 32) and ( 33) we findT 4 ≲ ∥w * ∥ 2 H • D eff,N N .Let (λ i ) i≥1 be the eigenvalues of H in non-increasing order. Let ( λi ) M i=1 be the eigenvalues of SHS ⊤ in non-increasing order. Then there exists a constant c > 1 such that for every M ≥ 0 and every 0 ≤ k ≤ M , with probability ≥ 1 -e -Ω(M ) , we have for every j ≤ M, λj -λ j + i>k λ i M ≤ c • k M • λ j + λ k+1 + i>k λ 2 i M .As a direct consequence, for k ≤ M/c 2 , we have for every j ≤ M, λj -λ j + i>k λ i M ≤ 1 2 • λ j + i>k λ i M + c 1 • λ k+1 ,wherec 1 = c + 2c 2 .Proof of Lemma G.1. We have the following decomposition motivated by Swartworth and Woodruff [38] (see their Section 3.4, Proof of Theorem 1).SHS ⊤ = S 0:k H 0:k S ⊤ 0:k + S k:∞ H k:∞ S ⊤ k:∞ = S 0:k H 0:k S ⊤ 0:k + i>k λ i M • I M + S k:∞ H k:∞ S ⊤ k:∞ -i>k λ i M • I M .We remark that this decomposition idea has been implicitly used in Bartlett et al. [5] to control the eigenvalues of a Gram matrix. In fact, we will use techniques from Bartlett et al. [5] to obtain a sharper bound than that presented in Swartworth and Woodruff [38] .For the upper bound, we haveµ j SHS ⊤ ≤ µ j S 0:k H 0:k S ⊤ 0:k + i>k λ i M • I M + S k:∞ H k:∞ S ⊤ k:∞ -i>k λ i M • I M 2 = µ j S 0:k H 0:k S ⊤ 0:k + i>k λ i M • I M + S k:∞ H k:∞ S ⊤ k:∞ -i>k λ i M • I M 2 ≤ µ j S 0:k H 0:k S ⊤ 0:k + i>k λ i M • I M + c 1 • λ k+1 + i>k λ 2 i M ,where the last inequality is by Lemma G.2. For j ≤ k, using Lemma G.3, we haveµ j S 0:k H 0:k S ⊤ 0:k ≤ λ j + c 2 • k M • λ j .For k < j ≤ M , we haveµ j S 0:k H 0:k S ⊤ 0:k = 0 ≤ λ j + c 2 • k M • λ j .Putting these together, we have the following for every j = 1, . . . , M :µ j SHS ⊤ ≤ µ j S 0:k H 0:k S ⊤ 0:k + i>k λ i M • I M + c 1 • λ k+1 + i>k λ 2 i M ≤ λ j + i>k λ i M • I M + c • k M • λ j + λ k+1 + i>k λ 2 i M .Similarly, we can show the lower bound. By the decomposition, we haveµ j SHS ⊤ ≥ µ j S 0:k H 0:k S ⊤ 0:k + i>k λ i M • I M -S k:∞ H k:∞ S ⊤ k:∞ -i>k λ i M • I M = µ j S 0:k H 0:k S ⊤ 0:k + i>k λ i M • I M -S k:∞ H k:∞ S ⊤ k:∞ -i>k λ i M • I M ≥ µ j S 0:k H 0:k S ⊤ 0:k + i>k λ i M • I M -c 1 • λ k+1 + i>k λ 2 i M ,where the last inequality is by Lemma G.2. For j ≤ k, using Lemma G.3, we haveµ j S 0:k H 0:k S ⊤ 0:k ≥ λ j -c 2 • k M • λ j .For k < j ≤ M , we haveµ j S 0:k H 0:k S ⊤ 0:k = 0 ≥ λ j -λ k+1 -c 2 • k M • λ j ,where the last inequality is due to λ j ≤ λ k for j ≥ k. Putting these together, we haveµ j SHS ⊤ ≥ µ j S 0:k H 0:k S ⊤ 0:k + i>k λ i M • I M -c 1 • λ k+1 + i>k λ 2 i M ≥ λ j + i>k λ i M • I M -c • k M • λ j + λ k+1 + i>k λ 2 i M .So far, we have proved the first claim. To show the second claim, we simply applyc • k M ≤ 1 2 for k ≤ M/c 2 , and c • i>k λ 2 i M ≤ c • i>k λ i M • λ k+1 ≤ 1 2 • i>k λ i M + 2c 2 • λ k+1 ,in the first claim.Lemma G.2 (Tail concentration, Lemma 26 in Bartlett et al. [5] ). For any k ≥ 1, with probability at least 1 -e -Ω(M ) , we haveS k:∞ H k:∞ S ⊤ k:∞ -i>k λ i M • I M 2 ≲ λ k+1 + i>k λ 2 i M .Moreover, the minimum eigenvalue ofS k:∞ H k:∞ S ⊤ k:∞ satisfies µ min (S k:∞ H k:∞ S ⊤ k:∞ ) ≳ λ k+2Mwith probability at least 1 -e -Ω(M ) .Proof of Lemma G.2. The first part of Lemma G.2 is a version of Lemma 26 in [5] (see their proof). We provide proof here for completeness.We write S ∈ R M ×p asS = (s 1 . . . s p ) , s i ∼ N 0, 1 M • I M , i ≥ 1.Since Gaussian distribution is rotational invariance, without loss of generality, we may assume H = diag{λ 1 , . . . , λ p }.Then we haveS k:∞ H k:∞ S ⊤ k:∞ = i>k λ i s i s ⊤ i .Fixing a unit vector v ∈ R M , thenv ⊤ S k:∞ H k:∞ S ⊤ k:∞ v = i>k λ i s ⊤ i v 2 ,where each s ⊤ i v is (1/M )-subGaussian. By Bernstein's inequality, we have, with probability ≥ 1 -δ,i>k λ i s ⊤ i v 2 -i>k λ i M ≲ 1 M • λ k+1 • log 1 δ + i>k λ 2 i • log 1 δ .By a union bound and net argument on S M -1 , we have, with probability ≥ 1 -δ, for every unit vector v ∈ R M , i>kλ i s ⊤ i v 2 -i>k λ i M ≲ 1 M • λ k+1 • M + log 1 δ + i>k λ 2 i • M + log 1 δ .So with probability at least 1 -e -Ω(M ) , we haveS k:∞ H k:∞ S ⊤ k:∞ -i>k λ i M • I M 2 ≲ 1 M • λ k+1 • M + i>k λ 2 i • M ≂ λ k+1 + i>k λ 2 i M ,which completes the proof of the first part of Lemma G.2.To prove the second part of Lemma G.2, it suffices to note thatS k:∞ H k:∞ S ⊤ k:∞ ⪰ 2M +k i=k+1 λ i s i s ⊤ i ⪰ λ 2M +k • 2M +k i=k+1 s i s ⊤ i ⪰ cλ 2M +k • I Mfor some constant c > 1 with probability at least 1 -e -Ω(M ) , where the last line follows from concentration properties of Gaussian covariance matrices (see e.g., Thereom 6.1 [41] ).Lemma G.3 (Head concentration). With probability at least 1 -e -Ω(M ) , we have for every j ≤ k, |µ j (S 0:k H 0:k S ⊤ 0:k ) -λ j | ≲ k M • λ j .Proof of Lemma G.3. Note that the spectrum of S 0:k H 0:k S ⊤ 0:k is indentical to the spectrum of H 1/2 0:k S ⊤ 0:k S 0:k H 1/2 0:k . We will bound the latter. We start with bounding the spectrum of S 0:k S ⊤ 0:k . To this end, we write S ⊤ 0:k ∈ R k×M asS ⊤ 0:k = (s 1 . . . s M ) , s i ∼ N 0, 1 M • I k , i = 1, . . . , M.Then repeating the argument in Lemma G.2, we have, with probability ≥ 1 -δ, for every unit vectorv ∈ R k , v ⊤ S ⊤ 0:k S 0:k v -1 = M i=1 s ⊤ i v 2 -1 ≲ 1 M • 1 • k + log 1 δ + M • k + log 1 δ ≲ k + log(1/δ)) M .So we have, with probability ≥ 1 -e -Ω(M ) ,S ⊤ 0:k S 0:k -I k 2 ≲ k M .where k * ≂ M/ log(M ). Also, there exists some a-dependent constants c 1 , c 2 > 0 such that c 1 j log 2a (j + 1) ≤ µ j (SH 2 S ⊤ ) ≤ c 2 j log 2a (j + 1) with probability at least 1 -e -Ω(M ) .Proof of Lemma G.6. The proof is adapted from the proof of Theorem 6 in [5] . We include it here for completeness.First part of Lemma G.6. In Lemma G.1, for some constant c > 1, choose k * := min k ≥ 0 :i>k λ i ≥ c • M • λ k+1 .Then with probability ≥ 1 -e -Ω(M ) , we have:for every 1 ≤ j ≤ M , 1 c 1 • λ j + i>k * λ i M ≤ λj ≤ c 1 • λ j + i>k * λ i M ,where c 1 > 1 is a constant.When λ j ≂ j -1 log -a (j + 1), we have k * ≂ M/ log(M ), and i>k * λ i ≂ log 1-a (k * ) ≂ log 1-a (M ).Therefore, we have λj ≂ λ j + i>k * λ i M ≂ j -1 log -a (j + 1) j ≤ k * , M -1 log 1-a (M ) k * < j ≤ M,where k * ≂ M/ log(M ).Second part of Lemma G.6. Let λi denote the i-th eigenvalue of SH 2 S ⊤ for i ∈ [M ]. Using Lemma G.1 with k = M/c for some sufficiently large constant c 0 and noting that i>k λ 2 i ≂ i>k i -2 log -2a (i + 1) ≲ k -1 log -2a k, we have 1 2• j -2 log -2a (j + 1) -c2 • M -2 log -2a M ≤ λj ≤ 3 2 • (j -2 log -2a (j + 1) + c1 M -2 log -2a M ) + c2 • M -2 log -2a M for every j ∈ [M ] for some constants ci , i ∈ [2] with probability at least 1 -e -Ω(M ) . Therefore, for all j ≤ M/c for some sufficiently large constant c > 1, we have λj ∈ [c 3 • j -2 log -2a (j + 1), c4 • j -2 log -2a (j + 1)]with probability at least 1 -e -Ω(M ) for some constants c3 , c4 > 0. For j ∈ [M/c, M ], by monotonicity of the eigenvalues, we haveλj ≤ λ⌊M/c⌋ ≤ c4 M c -2 log -2a M c ≤ c5 M -2 log -2a M ≤ c6 • j -2 log -2a (j + 1)for some constants c 5 , c 6 > 0 with probability at least 1 -e -Ω(M ) . Moreover, using Lemma G.2 with k = 0, we obtain λj ≥ λM ≥ µ min (S k:∞ H 2 k:∞ S ⊤ k:∞ ) ≥ c7 λ2M ≥ c8 • j -2 log -2a (j + 1) with probability at least 1 -e -Ω(M ) for some constants c7 , c8 > 0 when j ∈ [M/c, M ]. Combining the bounds for j ≤ M/c and j ∈ [M/c, M ] completes the proof.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).If arg min R(•) is not unique, we choose w * to be the minimizer with minimal H-norm.Our results can be extended to other sketching methods [see 43, for example].N -1 i=0 v i /N . Our goal is to derive matching upper and lower bounds R(v N ) in terms of the sample size N and model size M.We allow d = ∞. 


Decision: **Summary** The paper contains an analysis of a random features model trained with SGD.  It assumes an underlying infinite-dimensional linear regression problem.  The decay of the variances of the infinite dimensional problem and the target are both powerlaw type, denoted by parameters $(a,b)$ respectively.  

The data is is projected into finite dimensions by means of a finite-dimensional (isotropic Gaussian) sketching matrix having $M$ dimensions, and then this sketched data and a noisy target (with noise level $\sigma^2$) is released to the optimizer.

Sharp upper and lower bounds for the risk (less its irreducible part) are given over a range of parameters $(a,b,\sigma^2)$, as the number of samples $N$ (hence number of steps of one-pass SGD) tend to $\infty$.  

The new theoretical results leverage existing general risk bounds for one-pass SGD.  Novel bounds for the sketched problem are deduced which are needed to get the sharp dependence on the number of random features $M$. 

**Limitations.**
The risk bounds are not sharp for all parameters in the phase space.  
* $\sigma^2 = 0$ is not covered, nor are the estimates uniform as we take $\sigma^2 \to 0$.  (To the authors: please make it clear in Theorems 4.2,4.3 if this is the case; this was inferred from how you write Theorem 4 and from the $\Theta$ bound on the variance, which otherwise would seem too large.)  

    Hence we are constrained to an asymptotic regime in which we have a fixed irreducible loss level, say $42$.  We are then trying to get to $42 + 10^{-x}$ risk, and we get an accurate picture of how to achieve this risk as $x\to\infty$.  
    
    It seems to me that $\sigma^2$ should be small as a function of $M$, to be relevant to the scaling laws of Hoffman et al or Kaplan et al.  (Note that both these papers increase $M$ by $1000$ without seeing something like $\sigma^2$)

* In the range $b \geq a+1$, the estimates are not sharp.  So, the theoretical results are not quite all in place for the regime they consider.  


**Novelty** The reviewers have raised the concern of novelty of these results.  The opinion of the AC is that the risk bounds are new in the regimes they consider (in contrast to the concerns raised by the reviewers);  the key differentiator between the results of (13551) and existing work is that one must make estimates for the spectrum of the sketched covariance (c.f. Lemma 6.2).  Having done so, one has a finite-dimensional approximation of a kernel problem, which requires effective SGD risk bounds.

Now on the other hand, it is also true that the role of $M$ is very slight in this whole picture.  And one can take $M\to\infty$ first in this picture, the bounds are consistent with existing kernel regression bounds at $M=\infty$.  Hence it is also true that the random sketch is not doing very much, which may be the source of this confusion.  (Indeed Lemma 6.2 in some sense is the statement the random sketch is just a truncation of the infinite kernel problem, in a relatively strong sense).  

So the novelty in this paper is indeed the sharp analysis of a particular random least squares problem, especially eigenvalue/eigenvector estimates.

**Requests for modifications.**

* The reviewers have pointed out literature on source/capacity conditions, especially the list of v1rx.  You have written in the openreview comments how some of your bounds compare to existing ones.  These comparisons to the existing kernel regression literature will greatly contextualize these results, and would improve the manuscript.

**Recommendation**
This paper addresses a recent topic of interest (scaling laws, esp. compute constrained scaling laws) by sharpening and extending existing bounds, in particular giving bounds for powerlaw random features problems which are not in the existing literature.  It should be accepted as a poster.

Reviews: review: paper_summary: paper_summary: This paper proves that the scaling laws that occur in deep learning also occur when solving linear regression with SGD.

Namely, suppose:
* that covariates x are Gaussian with  a power-law spectrum
* the true labels are given by <w^*, x> for unknown w^*
* we run one-pass SGD to do linear regression on an M-dimensional sketch of the covariates x
* we have N data points

Then the risk is upper-bounded by an expression that depends only on the "bias" and "approximation" terms, with inverse polynomial dependence as observed in neural scaling laws. The "variance" term is of lower order (provided the appropriate large step sizes are used).

Extensions to when the data follows a logarithmic power spectrum are also explored.
strength_weakness: strength_weakness: Typo: "optimally tunned"
questions: questions: 1. How dependent are the results on a geometric step-size schedule? What if a constant schedule, or schedule decreasing as gamma_t = t^{-c} is used instead?

2. In line 232, it is stated that when $1 \leq b \leq a$ the tasks are "relatively hard", and in line 236 that when $a < b < a+1$ the tasks are "relatively easy". Is what is meant here that these tasks are "relatively harder/easier" than when a = b?
limitations: limitations: Yes
paper_summary: paper_summary: Motivated by the recent neural scaling law literature, this work investigates the generalization error rate of a sketched linear regression model trained on Gaussian covariates with power-law spectrum under one-pass SGD.

The main result are lower and upper bounds with matching rates, providing a detailed characterization of the different contributions to the generalization error.
strength_weakness: strength_weakness: In my reading, the two main weaknesses are:
1. The lack of a wider context. While it makes precise connections to other recent works on the "*"theory of neural scaling laws"*" such as [Bahri et al., 2021, Maloney et al., 2022, Bordelon et al., 2024], it ignores that the study of generalization error rates in least-squares / ridge regression under source and capacity conditions is a classical topic with an extensive literature. For instance:

     - [1,2,3] have studied both single and multiple pass SGD for least squares regression on Hilbert spaces under source and capacity conditions. This corresponds to the kernel limit $M\gg N$ in this work. Borrowing the notation from [3] for concreteness, after a quick comparison with the identification of the capacity $\alpha = a$ and source $r=\frac{b-1}{2a}$, I believe the "hard" and "easy" rates from Theorems 4.1 and 4.2 can be retrieved from the one-pass rates in [3].
     - [4] extends the discussion of [1-3] to the random features approximation of kernels.
     - The rates from one-pass SGD on least squares can be identified with the rates of ridge regression with an appropriately chosen regularization, which has been exactly characterized in [7]. For example, the blue and orange regions in Figure 1 from [7] correspond to rates in Theorem 4.2 with $\ell = 1$.
     - A recent extension of the above to RFs case appeared in [6] (though note some of these rates were known from [7]).

     From the discussion above, it is not really clear what rates are new in this submission. I am willing to change my evaluation if this can be clarified with an in-depth comparison with these works.  

2. The organization of the manuscript in Theorems with "settings of increasing generality" can come through as deceptive. Aren't Theorems 4.3, 4.2 and 4.1 corollaries of Theorems 6.3 and 6.4?


**References**

- [1] Yao, Y., Rosasco, L. & Caponnetto, A. On Early Stopping in Gradient Descent Learning. Constr Approx 26, 289–315 (2007). https://doi.org/10.1007/s00365-006-0663-2
- [2] Ying, Y., & Pontil, M. (2008). Online gradient descent learning algorithms. Foundations of Computational Mathematics, 8, 561-596.
- [3] Pillaud-Vivien, L., Rudi, A., & Bach, F. (2018). Statistical optimality of stochastic gradient descent on hard learning problems
through multiple passes. Advances in Neural Information Processing Systems, 31.
- [4] Luigi Carratino, Alessandro Rudi, Lorenzo Rosasco. Learning with SGD and Random Features.  Part of Advances in Neural Information Processing Systems 31 (NeurIPS 2018).
- [5] Hugo Cui, Bruno Loureiro, Florent Krzakala, Lenka Zdeborová. Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime. Part of Advances in Neural Information Processing Systems 34 (NeurIPS 2021).
- [6] Leonardo Defilippis, Bruno Loureiro, Theodor Misiakiewicz. Dimension-free deterministic equivalents for random feature regression. arXiv:2405.15699.
- [7] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems, pages 3215–3225, 2017.
questions: questions: - L43-48:

> "*This difference must be reconciled, otherwise, the statistical learning theory and the empirical scaling law make conflic predictions: as the model size increases, the theoretical bound (2) predicts an increase of variance error that eventually causes an increase of the population risk, but the neural scaling law (1) predicts a decrease of the population risk. In other words, it remains unclear when to follow the prediction of the empirical scaling law (1) and when to follow that of the statistical learning bound (2).*"

Given our current understanding of random features regression, this claim is inflated. Several of the works mentioned above [4,6,7], as well as many other works in the random features literature have made the observation that increasing the "width" $M$ does not necessarily lead to an increase of variance / overfitting, thanks to the implicit regularization.   


- L273-275:

> "*It is noteworthy that our simulations demonstrate stronger observations than the theoretical results in Theorem 4.1, which only establishes matching upper and lower bounds up to a constant factor.*"

What do you exactly mean in this sentence? What in Figure 2 is stronger than the exponents reported in Theorem 4.1?
limitations: limitations: The assumptions under which the Theorems hold are clearly stated, but I miss an explicit discussion of the limitations.
paper_summary: paper_summary: This paper sheds new light on the bounds of linear regression by framing them in terms of scaling laws.
strength_weakness: strength_weakness: It is difficult to talk about a weakness: the paper is self-contained, the results are solid and the context very well explained. 

Perhaps the authors should put emphasis on the fact that there is **absolutely no technical novelty and that the contribution relies in re-framing known bounds under the perspective of scaling laws**.
questions: questions: No question
limitations: limitations: No
paper_summary: paper_summary: This work examines neural scaling laws, in the simplified setting of linear regression trained by one-pass SGD. In particular, it attempts to explain the apparent mismatch between the statistical theory on one hand, which predicts that variance error increases with model size, and neural scaling laws on the other, which state that predictive performance should increase with model size. By considering sketched covariates of an infinite dimensional linear regression model with Gaussian prior under mild spectral assumptions, scaling laws are derived while keeping track of a variance term that increases with model complexity and corrects for a mismatch between the best-in-class predictor and the best possible predictor. However, this term is of higher order than the usual approximation and bias terms appearing in scaling laws, accounting for the empirical accuracy of scaling laws in practice. Numerical examples are provided for synthetic data.
strength_weakness: strength_weakness: It is not clear when the variance term is first given on page 2 that it is of higher order than the other terms. The reader has to find the more precise presentation in Theorem 4.1 in order to verify this for themselves. Clarification of this when the term is first introduced would be helpful and improve the paper.
While the paper's contribution is primarily theoretical, the only examples given are synthetic. Validation of the theory on a large benchmark dataset, even if modified to make it appropriate to the assumptions, would strengthen the paper significantly.
questions: questions: Can you please address the weaknesses outlined above?
How do you think this work can this be generalized to other settings of interest?
Under which settings should the variance term be accounted for?
limitations: limitations: Some discussion of the assumptions of their work and their limitations would be helpful. Broader societal impact is mostly not applicable.
paper_summary: paper_summary: Large models often empirically satisfy the neural scaling law i.e. the error decreases when the number of data and the model size increase, however, this contradicts with the widely accepted belief in learning theory that the variance error (one of the decomposed errors) should increase with the model size. Authors investigate this in the infinite-dimensional linear regression setting and show that the variance error is dominated by other errors because of the implicit regularization of SGD. Authors also support their claim with numerical simulations.
strength_weakness: strength_weakness: - The assumptions of the paper might be too strong with linear regression setting and Gaussian design assumption, is it possible to extend to the kernel setting and with relaxed assumption on features [1]?
- While the current analysis is focusing on one-pass SGD, which is not often used in LLM training, can the result be extended to Adam?
- The result is not very surprising 

[1] Barzilai et al.,  Generalization in Kernel Regression Under Realistic Assumptions
questions: questions: - I am confused about the sketch matrix setting? Is the fixed sketch matrix analogous to the neural net with size M and why the teacher-student model in previous work can be viewed as sketched linear regression model
- I am also confused about the Hypercontractivity assumption in Assumption 5, what's its intuition and why it is required in the proof?
- What's the purpose for setting geometric decaying stepsize, what happens if it is fixed or it is polynomial decaying?
- Is the regularization effect of SGD determined by the choice of stepsize, where the optimal choice controls the strength of the implicit bias of SGD?
limitations: limitations: See weakness

Comments: title: Response
Response
Reply to Reviewer v1rx
After Rebuttal
Clarification
comment: Thank you, I will keep my score.
Thanks for the comment. Below we provide a roadmap of our proof to address some of your concerns. 

We agree that convergence rates on SGD and concentration rates on sketching or random features have been widely studied in many contexts. However, obtaining the main results (Theorem 4.1-4.3) in our work requires both application of the existing results and non-trivial developments based on the existing bounds. 

More specifically, our Theorem 6.1 is mainly built upon existing results in [Wu et al., 2022a,b]. However, in order to obtain Theorem 4.1-4.3 from Theorem 6.1, we first develop novel upper/lower bounds (Theorem 6.3, 6.4) of the approximation, bias and variance terms. These bounds decompose $\mathsf{Approx}$, $\mathsf{ Bias}$ and $\mathsf{Var}$ into the head  and tail components (i.e. $\\|w^*_{1:k}\\|\_2\^2,\\|w^*_{k:\infty}\\|\^2\_{H_{k:\infty}}$)  and involve the ratio of eigenvalues of the sketched covariance matrix. The bounds are carefully built so that the upper and lower bounds match up to constant factors in our examples. Theorem 4.1-4.3 are then obtained based on instantiation of Theorem 6.3 and 6.4 under the power-law (or log-power-law ) spectrum.

The role of Lemma 6.2 and C.2: they are intermediate results developed in our proof. Lemma C.2 proves the first part of Theorem 6.4; Lemma 6.2 characterizes the eigenvalues of the sketched covariance matrix and enables us to obtain Theorem 4.1 and 4.2 from Theorem 6.3 and 6.4.  While we appreciate the discussion and understand the perspective shared, we respectfully believe that some technical contributions have been made (e.g., novel uses of Von-Neuman’s inequality) in proving these lemmas and other results.
Thank you for the comparison, this is interesting and in line with what I expected. 

I am increasing my core, and won't object acceptance conditioned that the authors include this discussion and put their work in perspective with the literature above.
Thanks for your response and clarification. I will maintain my score.
Thanks Reviewer v1rx for the clarification. We will show below our rate matches the prior SGD and ridge rates in the comparable regimes. For simplicity, we will ignore logarithmic factors by replacing $N_{\mathrm{eff}}$ with $N$ in our Theorem 4.2 in the following discussions. Note that the logarithmic factor can be removed by considering averaged SGD instead of last iterate SGD.

- Comparion with the prior SGD rate. We use [3] as an example. Aligning the source and capacity conditions, we have $\alpha = a$ and $r = (b-1)/(2a)$. Then the rate in their page 4 becomes $O(1/(N\gamma)^{(b-1)/a}  + (N\gamma)^{1/a}/N)$, which exactly matches ours in Theorem 4.2 when $M$ is large in the comparable regime.

- Comparing with the prior ridge rate. We use [7] as an example. Aligning the source and capacity conditons, we have $\gamma=1/a$ and $r = (b-1)/(2a)$. Then their optimal rate in Theorem 2 becomes $O(N^{-(b-1)/b})$, which matches our Theorem 4.2 when $M$ is large and $\gamma$ is tuned to be $\gamma^* = \Theta(N^{a/b-1})$ in the comparable regime.

Finally, we would like to point out that [3] requires $\mathrm{tr}(\Sigma^{1/\alpha})$ to be finite. However, we do not require such condition, that is, our bounds allow $\mathrm{tr}(H^{1/a}) = \infty$ in our notation.
We will add these discussions in the revision.
Let me be clearer, obviously, nothing is completely black and white, and there is obviously a continuum between a simple reformulation and new contributions. What I mean is that I totally share the feeling of **Reviewer v1rx** that we do not understand what are the *real* novelties of the approach --beyond the story telling. 

Hence, if Lemma 6.2 or Lemma C.2 are really new achievements, I feel that they could be promoted. I sincerely feel it is not the case, but it is only a question of perception and I am happy to be wrong.

Furthermore, convergence rates on SGD and concentration rates on sketching or random features has been widely studied, under the present form, it seems hard to really understand **where** the authors are.

Yet, I maintain my score as I have nothing against nice re-formulation.
I thank the authors for their rebuttal that addressed some of my questions, in particular Q5-Q8. However, I find that your reply to Q1-Q4 miss my point. 

Let me try to be clearer. 

- I don’t mean to say your results lack technical novelty. I understand [1,2,3] provide only upper bounds for kernel methods ($M\gg N$), while you also provide lower bounds with matching rates.

- I also understand that [5,6,7] are for ridge, not SGD. My point is also not about which one is a more practical algorithm. 

 In Q1-Q4 I (tried) to convey two points: 

1. First, how do your exact rates compare with the upper bounds of [1,2,3]? Do they match in the regime where they compare? Are they tighter? 
2. Second, how do your rates compare with the ridge rates from [5,6,7] for kernels and RF? We know that running SGD to convergence with decreasing learning rate recover the least-squares rates, which are not the optimally regularized ridge rates. I want understand  how close to optimal is early stopping in terms of implicit regularisation. See for example Section 4 of [6] for a summary of the rates in [5,7].

It is not just about citing papers, but how your work fit within the classical source and capacity literature, and the conclusions this allow us to make about optimality of early stopping with SGD in the different scaling regimes.
Thanks for your response and I will keep my positive score