We appreciate Reviewer 6YBu for their careful review and valuable feedback. We hope to address all questions below.

W1. My main concern with this paper is that its contribution over [1-2] appears to be limited.

A1. We respectively disagree that our analysis has limited novelty. For multi-pass SGD, we generalize the results of Pillaud-Vivien et al. (2018) [2] in two key aspects. First, the upper bound on the risk of multi-pass SGD in Theorem 1 of [2] is restricted to the regime $\mu a \leq b \leq a$ for some $\mu \in (0,1]$. (It can be verified that our parameters $(a, b)$ equal $(\alpha, 2\alpha r + 1)$ in their work, and note that choosing $\mu = 0$ in their Assumption A3 leads to $\kappa = \infty$, making the bound vacuous.) In contrast, our upper bounds in Corollaries 3.3 and 3.4 apply to a strictly broader regime $a>b-1$. Second, [2] provides no lower bounds for the risk of multi-pass SGD. In contrast, we establish matching lower bounds in the regime $a>b-1$, verifying the tightness of our upper bounds. We believe these generalizations are not possible without introducing technical innovations. Note: the condition $b > a$ in lines 219–221 is a typo and should be revised to $b > a > b - 1$. Similarly, lines 129 and 169 should include the condition $a > b - 1$.

Compared to the analysis in [1] for one-pass SGD, the non-commutativity between the empirical covariance and population covariance matrices introduces additional technical challenges, requiring new proof arguments. For example, unlike for the bias upper bound (lines 267-270), the covariance replacement trick in Lemma 7 of [2] does not apply when establishing the bias lower bound (Lemma B.2). Instead, we derive the bound by showing that a specific function of the empirical covariance commutes with the population covariance in expectation.

Q1. Is it true that in the isotropic prior case, the bounds are essentially the same as the ones in Lin et al. (2024), or I am missing something here?

A2. Yes, the bounds are the same in the regime where $a = b$. In fact, the rate $O(N^{(1-a)/a})$ in this case is minimax optimal for a class of linear regression problems with the same spectral conditions [2], and hence cannot be improved.

Q2. What will happen if, instead of assuming the data distribution and the prior share the same eigenvectors, we only assume they are correlated?

A3. First, we emphasize that our general upper and lower bounds on the bias, variance, and fluctuation (Lemmas B.1, B.2, C.1, D.1, D.4) do not require either the power-law assumption or the alignment between the eigenvectors of the data distribution and the prior. These bounds hold under Gaussian design with an arbitrary data spectrum, as long as certain regularity conditions (Assumption 3) are satisfied.

The alignment of eigenvectors is assumed only to derive exact rates from the general bounds under the power-law setting. In fact, our main results in Section 3 still hold when the prior covariance $\mathbf{H}^{\mathbf{w}} := \mathbb{E}[\mathbf{w}^* \mathbf{w}^{*\top}]$ is bounded above and below (in Loewner order, up to constant factors) by a matrix $\widetilde{\mathbf{H}}^{\mathbf{w}}$ that has a power-law spectrum and share the same eigenvectors as the data covariance $\mathbf{H}$ as in Assumption 1D.

[1]. Lin, Licong, et al. "Scaling laws in linear regression: Compute, parameters, and data." Advances in Neural Information Processing Systems 37 (2024): 60556-60606.

[2]. Pillaud-Vivien, Loucas, Alessandro Rudi, and Francis Bach. "Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes." Advances in Neural Information Processing Systems 31 (2018).

We appreciate Reviewer b6Gz for their thorough review and constructive feedback on our work. Below, we hope to answer all questions raised in the review.

W1 and Q1. Clarity: the main paper is pretty clearly written. However, the proofs in the appendix sometimes are not that clear and detailed. E.g., from line 846-line 849, too many things are done at the same time. Also, nested lemmas (e.g., lemma D.2 and D.3 are stated in the proof of lemma D.1) makes the flow hard to follow. The clarity can be improved by providing a better high-level proof sketch of bounding the fluctuation error. (If I understand correctly, this is the key difference from the results in [1]).

A1. We thank the reviewer for the constructive comments on improving the clarity of our proof. We will include additional details and provide a high-level proof sketch for bounding the fluctuation error in the paper. For completeness, we present the sketch here.

To bound the fluctuation error, we express the difference between the multi-pass SGD and GD trajectories, $\mathbf{v}_t - \boldsymbol{\theta}_t$, as a stochastic process (Eq. 17) that fits into the framework of Lemma D.2, which provides a bound on the fluctuation error $\mathbb{E}[\\|\mathbf{\Sigma}^{1/2}(\mathbf{v}_t - \boldsymbol{\theta}_t)\\|^2]$ under certain conditions, up to a mismatch between $\widehat{\mathbf{\Sigma}}$ and $\mathbf{\Sigma}$. We verify that the required conditions hold with appropriate choices of parameters (Eq. 19), which are further bounded using a leave-one-out argument (Lemma D.3). Applying Lemma D.2 with these parameters and a covariance replacement trick (line 776) yields the bounds stated in Lemma D.1.

Moreover, we emphasize that, in addition to bounding the fluctuation error, generalizing the one-pass SGD results from [1] to GD in our setting introduces additional challenges. Please see our response to your W3 below for further discussion.

W2. Significance: The submission advances our understanding of scaling laws under data-reuse. While this is somewhat significant, the main limitation is that the analysis is limited to linear models. In addition, the Gaussian design matrix is a pretty strong assumption.

A2. Extending the results to nonlinear settings such as logistic regression or two-layer neural networks would be an interesting direction for future work. We will comment on this in the paper. That said, we believe our contribution, deriving finite-sample matching upper and lower bounds for multi-pass SGD in sketched linear models, has made substantial contributions to the theoretical understanding of scaling laws.

In fact, the Gaussian design is not necessary for all the upper bounds in Section 3. Namely, it can be shown that the Gaussian design assumption (Assumption 1A) can be relaxed to the following: $\mathbf{x}= \mathbf{H}^{1/2}\mathbf{\widetilde x}$, where $\mathbb{E}[\mathbf{\widetilde x}\mathbf{\widetilde x}^\top]=\mathbf{I}$, and the vector $\mathbf{\widetilde x}$ is symmetric and 1-sub-Gaussian, i.e., $\mathbf{\widetilde x}\overset{d}{=}-\mathbf{\widetilde x}$ and $\mathbb{E}[e^{\lambda\langle \mathbf{v},\mathbf{\widetilde x}\rangle}]\leq e^{\lambda^2/2}$ for any unit vector $\mathbf{v}$. In short, the relaxation can be made since the Gaussian assumption is mainly used to establish certain concentration bounds (e.g., Bernstein’s inequality), which also hold for sub-Gaussian vectors. On the other hand, for the lower bounds, the Gaussian assumption is still required in order to establish the conditional independence in line 521 and 754. We are happy to provide a more detailed explanation, should the reviewer have any concerns regarding the relaxation.

In addition, we run simulations to verify the claim. We generate data $\mathbf{x}=(x_1,\ldots,x_d)^\top$ from the distribution where $x_i$ are independent and $\mathbb{P}(x_i=1)=\mathbb{P}(x_i=-1)\propto i^{a-b}, \mathbb{P}(x_i=0)=1-2\mathbb{P}(x_i=1)$ with $a=2,b=1.5$ instead of Gaussian. Under the same setting and choices of hyperparameters as in Figure 1(a), similar to the Gaussian case, we observe that excess test error of one-pass SGD and multi-pass SGD both exhibit power-law scaling in the number of effective steps ($L_{\mathsf{eff}})$. Moreover, the fitted slopes are both close to the theoretical prediction ($0.34\approx0.33=(1-b)/b$ for multi-pass SGD and $0.26\approx0.25=(1-a)/b$ for one-pass SGD).

W3. Originality: The submission extends previous results on scaling laws to multi-pass SGD. The proofs follow closely along the lines of [0].

A3. We respectively disagree that our analysis has limited originality. For multi-pass SGD, we extend the results in [0] in two key aspects. First, the upper bound on the risk of multi-pass SGD in Theorem 1 of [0] is restricted to the regime $\mu a \leq b \leq a$ for some $\mu \in (0,1]$. (It can be verified that our parameters $(a, b)$ equal $(\alpha, 2\alpha r + 1)$ in [0], and note that choosing $\mu = 0$ in their Assumption A3 leads to $\kappa = \infty$, making the bound vacuous.) In contrast, our upper bounds in Corollaries 3.3 and 3.4 apply to a strictly broader regime $a>b-1$. Second, [0] provides no lower bounds for the risk of multi-pass SGD. In contrast, we establish matching lower bounds in the regime $a>b-1$, verifying the tightness of our upper bounds. We believe these generalizations are not possible without introducing technical innovations. Note: the condition $b > a$ in lines 219–221 is a typo and should be revised to $b > a > b - 1$. Similarly, lines 129 and 169 should include the condition $a > b - 1$.

More specifically, as mentioned in our response to your Q1 above, for the fluctuation error of multi-pass SGD, we follow the standard practice as in [0] and the early work by Aguech et al., 2000 [2] to express the difference between the multi-pass SGD and GD trajectories as a stochastic process (Eq. 17). We then bound the fluctuation error through controlling the accumulated error of the stochastic process using Lemma D.2 and Lemma D.3, which involves a novel leave-one-out argument to control the model parameters. Note that our Lemma D.2 also generalizes the corresponding results in [0], as the analysis in [0] does not apply when $a=b$ for infinite-dimensional problems. In addition, we derive a novel lower bound on the fluctuation error that matches the upper bound up to logarithmic factors in certain regimes (Lemma D.4 and D.5).

Q2. Would the analysis/results extend to SGD with l2 regularization?

A4. This is an interesting question. We believe part of our results extend to multi-pass SGD with l2-regularization. We will comment on this as an interesting future direction. On the other hand, we would like to point out that, mult-pass SGD already provides sufficient implicit regularization, in which the achieved excess risk is minimax optimal for $a$ and $b$ such that $a>b>2$, (see [0]). Therefore, adding an l2-regularization might not provide additional benefits.

Other: typos: Second line of equation after 521, missing a S?

Thanks for pointing this out! We have fixed it.

[0]. Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes

[1]. Licong Lin, Jingfeng Wu, Sham M Kakade, Peter L Bartlett, and Jason D Lee. Scaling laws in linear regression: Compute, parameters, and data. arXiv preprint arXiv:2406.08466, 2024

[2]. R. Aguech, E. Moulines, and P. Priouret. On a perturbation approach for the analysis of stochastic tracking algorithms. SIAM J. Control and Optimization, 39(3):872–899, 2000.

We are grateful to Reviewer inkZ for their careful reading of our work and valuable feedback. Please find our responses to the comments below.

Q1. Some stylistic suggestions to further improve readability:

• The notation paragraph can be moved to Section 2.
• In Corollary 3.3, the part after ‘In contrast’ should be part of the text and not the result statement, since it only discusses a result from prior work.
• In Fig. 1, the last part in the caption (values of M and N for the subfigures) can be included in the respective subcaptions.

A1. We sincerely appreciate your stylistic suggestions and will revise our paper accordingly.

Q2. In Section 5, the proof overview can be improved by including some more details. The headings in line 258 and 259 seem unnecessary and this part can be made more concise. In the paragraph discussing the main technical difficulty, currently, the details are helpful to contrast the technique with prior work, but some of the statements, such as the one about Lemma D.3, and the one about a ‘novel lower bound’, are not very informative. It would be helpful to include some mathematical expressions for these to make the proof overview easier to follow.

A2. Thanks for the suggestions! We will provide a more detailed proof overview in Section 5.

Q3. The paper does not have a limitations section. The authors can include a paragraph to discuss some limitations of the work.

A3. We will expand our discussion of limitations in the conclusion section. One limitation of the paper is the assumption that the eigenvectors of the prior and data distributions are aligned (implied by Assumption 1D). While this assumption cannot be fully removed without affecting the error rate, it would be interesting to investigate what alternative rates are achieved when the eigenvectors are not aligned. Another limitation is that our results are currently restricted to linear models; extending them to nonlinear settings such as logistic regression or two-layer neural networks remains an open question.

We thank reviewer Y8gi for their positive feedback on our work. We are glad that the reviewer found our work to make progress towards understanding neural scaling laws and to help explain empirical observations such as those in Muennighoff et al. (2023).

We are grateful to Reviewer 6mRL for their thorough examination of our work and for their helpful comments. We hope to address all questions below.

W1. The setting is limited and to some extent, appears artificial. In particular, the introduction of "sketching matrix" requires further motivation beyond it allowing the introduction of a "model size" parameter. Furthermore, for linear models, it is unclear if the sketching dimension "M" captures the model "size" since the capacity of the model does not grow once the sketching matrix becomes full-rank. The paper further assumes that $M\ll d$ , which precludes the study of overparameterized regimes.

A1. The random sketching is introduced in our setting to control the dimension $M$ (or model size) of the linear models. We believe it is a basic and natural approach to introduce linear models with varying dimensions (model complexity) in regression problems. Similar random sketching approaches have been used to control model dimensions in many other works on the theoretical understanding of scaling laws [1,2,3].

We respectfully disagree with the reviewer's point that “the model size does not grow once the sketching matrix becomes full-rank.” Note that we consider an infinite-dimensional linear regression setting where the dimension $d = \infty$ (see line 66 and e.g., Assumption 1C). Therefore, increasing the sketching dimension $M$ always increases the model capacity. Our setting does not preclude overparameterized regimes either, since our results hold for any finite sample size $N$ and model size $M$ (e.g., Corollary 3.2), covering both underparameterized regimes ($M \leq N$) and overparameterized regimes ($M > N$).

W2. The analysis is of limited novelty and largely builds upon existing works, in particular the work of Pillaud-Vivien et al. 2018.

A2. We respectively disagree that our analysis has limited novelty. For multi-pass SGD, we generalize the results of Pillaud-Vivien et al. (2018) [4] in two key aspects. First, the upper bound on the risk of multi-pass SGD in Theorem 1 of [4] is restricted to the regime $\mu a \leq b \leq a$ for some $\mu \in (0,1]$. (It can be verified that our parameters $(a, b)$ equal $(\alpha, 2\alpha r + 1)$ in their work, and note that choosing $\mu = 0$ in their Assumption A3 leads to $\kappa = \infty$, making the bound vacuous.) In contrast, our upper bounds in Corollaries 3.3 and 3.4 apply to a strictly broader regime $a> b-1$. Second, [4] provides no lower bounds for the risk of multi-pass SGD. In contrast, we establish matching lower bounds in the regime $a>b-1$, verifying the tightness of our upper bounds. We believe these generalizations are not possible without introducing technical innovations. Note: the condition $b > a$ in lines 219–221 is a typo and should be revised to $b > a > b - 1$. Similarly, lines 129 and 169 should include the condition $a > b - 1$.

More specifically, for the fluctuation error, we follow the standard practice as in [4] and the early work by Aguech et al., 2000 [6] to express the difference between the multi-pass SGD and GD trajectories, $\mathbf{v}_t -\boldsymbol{\theta}_t$ as a stochastic process (Eq. 17). We then bound the fluctuation error $\mathbb{E}[\\|\mathbf{\Sigma}^{1/2}(\mathbf{v}\_L - \boldsymbol{\theta}_L)\\|^2]$ through controlling the accumulated error of the stochastic process using Lemma D.2 and Lemma D.3, which involves a novel leave-one-out argument to control the model parameters. Note that our Lemma D.2 also generalizes the corresponding results in [4], as the analysis in [4] does not apply when $a=b$ for infinite-dimensional problems. In addition, we derive a novel lower bound on the fluctuation error that matches the upper bound up to logarithmic factors in certain regimes (Lemma D.4 and D.5).

W3. (minor) missing related work. Although for different reasons, another recent line of work also demonstrates improved sample complexity (and consequently, improved scaling laws by data reuse) in the feature learning regime for two-layer neural networks…

A3. We thank the reviewer for pointing out the related works on improved sample convexity in two-layer neural networks via data reuse. We agree that data reuse can indeed improve sample complexity in many other regimes. However, a key distinction in our work is the use of random sketching, which introduces additional technical challenges. We will discuss these works and their connections to our results in the paper.

Q1. Could you provide brief motivations for the introduction of the sketching matrix and the assumption $M\ll d$?

A4. As explained in A1, we believe random sketching is a basic and natural approach to allow us to analyze a sequence of linear models with varying dimensions (model complexity) in regression problems [1,2,3]. The assumption $d=\infty$ is made to mimic the real-world scenario where the true data distribution is highly complicated (e.g., in text data) and no model with a finite size $M$ can capture all information about the data.

Q2. Lines 151-153 appear unclear without looking into Koltchinskii and Lounici (2017). Could you provide a short, self-contained summary of the source of the condition on the initial step-size?

A5. Since gradient descent is known to converge when the learning rate $\gamma \leq 1/L$ for convex objectives that are $L$-smooth, it suffices in our linear regression setting to choose $\gamma \leq 1/L = 1/\|\mathbf{S}\mathbf{X}^\top\mathbf{X}\mathbf{S}^\top/N\|_2 \asymp 1$. The final equivalence follows from concentration properties of Gaussian covariance matrices (see, e.g., Koltchinskii and Lounici, 2017).

Q3. The parameter $b$ is unspecified in the abstract and only defined later in the source condition.

A6. The parameter $b$ is introduced in the form of $b-a$ in the abstract. We will clarify this in the revision.

Q4. What happens when $a<b$?

A7. When $a<b<a+1$, as shown in Corollary 3.4 and the subsequent discussion, the optimal rate in $N$ is obtained when using the data once (i.e., $L_{\mathsf{eff}}=N$) and the learning rate $\gamma = L_{\mathsf{eff}}^{a/b-1}$. In this case, we are able to obtain the same rate $\widetilde{O}(N^{\frac{1-b}{b}})$ as in [3] for one-pass SGD. The case $b\geq a+1$ remains unclear to us and is left for future investigation.

Q5. What are the central challenges introduced by the introduction of the sketching matrix while bounding the fluctuation error (lines 274-276)?

A8. Sketching introduces additional difficulties when translating the general bounds on the fluctuation error to the setting where the source condition holds (Lemma D.5), as it requires precise characterization of the spectrum of the sketched covariance $\mathbf{S}\mathbf{H}\mathbf{S}^\top$ to control the terms in the general bound (line 750). We will further clarify this in the revision.

Q6. What motivates the choice of the geometrically-decaying step-size schedule?

A9. As discussed in our work (lines 82-85), our analysis applies to other stepsize schedules (such as polynomial decay) as well, but we focus on geometric decay since it is known to yield near minimax optimal excess test error for the last iterate of SGD in the finite-dimensional regime [5].

[1]. Bordelon, Blake, Alexander Atanasov, and Cengiz Pehlevan. "A dynamical model of neural scaling laws." arXiv preprint arXiv:2402.01092 (2024)

[2]. Paquette, Elliot, et al. "4+ 3 phases of compute-optimal neural scaling laws." Advances in Neural Information Processing Systems 37 (2024): 16459-16537.

[3]. Lin, Licong, et al. "Scaling laws in linear regression: Compute, parameters, and data." Advances in Neural Information Processing Systems 37 (2024): 60556-60606.

[4]. Pillaud-Vivien, Loucas, Alessandro Rudi, and Francis Bach. "Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes." Advances in Neural Information Processing Systems 31 (2018).

[5]. Ge, Rong, et al. "The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares." Advances in neural information processing systems32 (2019).

[6]. R. Aguech, E. Moulines, and P. Priouret. On a perturbation approach for the analysis of stochastic tracking algorithms. SIAM J. Control and Optimization, 39(3):872–899, 2000.