Larger Datasets Can Be Repeated More: A Theoretical Analysis of Multi-Epoch Scaling in Linear Regression
Authors: Tingkai Yan
Haodong Wen
Binghui Li
Kairong Luo
Wenguang Chen
Kaifeng Lyu
Venue: ICLR 2026 Poster (2026)
Keywords: Deep learning theory
Multi-epoch training
Data-reuse
Optimization
Scaling law
Large language model
Primary area: learning theory
TL;DR: Theoretical analysis of multi-epoch scaling in linear regression

Abstract: While data scaling laws of large language models (LLMs) have been widely examined in the one-pass regime with massive corpora, their form under limited data and repeated epochs remains largely unexplored. This paper presents a theoretical analysis of how a common workaround, training for multiple epochs on the same dataset, reshapes the data scaling laws in linear regression.
    Concretely, we ask: to match the performance of training on a dataset of size $N$ for $K$ epochs, how much larger must a dataset be if the model is trained for only one pass?
    We quantify this using the $\textit{effective reuse rate}$ of the data, $E(K, N)$, which we define as the multiplicative factor by which the dataset must grow under one-pass training to achieve the same test loss as $K$-epoch training.
    Our analysis precisely characterizes the scaling behavior of $E(K, N)$ for SGD in linear regression under either strong convexity or Zipf-distributed data: (1) When $K$ is small, we prove that $E(K, N) \approx K$, indicating that every new epoch yields a linear gain; (2) As $K$ increases, $E(K, N)$ plateaus at a problem-dependent value that grows with $N$ ($\Theta(\log N)$ for the strongly-convex case), implying that larger datasets can be repeated more times before the marginal benefit vanishes.
    These theoretical findings point out a neglected factor in a recent empirical study by [Muennighoff et al. (2023)](https://arxiv.org/abs/2305.16264), which claimed that training LLMs for up to $4$ epochs results in negligible loss differences compared to using fresh data at each step, $\textit{i.e.}$, $E(K, N) \approx K$ for $K \le 4$ in our notation. 
    Supported by further empirical validation with LLMs,
    our results reveal that the maximum $K$ value for which $E(K, N) \approx K$ in fact depends on the data size and distribution, 
    and underscore the need to explicitly model both factors in future studies of scaling laws with data reuse.

Published as a conference paper at ICLR 2026
LARGER DATASETS CAN BE REPEATED MORE: A THEORETICAL ANALYSIS OF MULTI-EPOCH SCALING IN LINEAR REGRESSION
Tingkai Yan" 8 Haodong Wen a
Binghui Li
Kairong Luo" Wenguang Chen n
Kaifeng Lyuto
"Institute for Interdisciplinary Information Sciences, Tsinghua University
School of Mathematical Sciences, Peking University
"Center for Machine Learning Research, Peking University
"Department of Computer Science and Technology, Tsinghua University Peng Cheng Laboratory
yant inggai6666 gma com, whd25 ls ribinghui@pker edu, en, 1uokr246mall tsinghua edu. on (cwg, klyu) @mail 1. ts tsinghua..... enu.en
htt.imaissssssssssaaaaaaea tsinghua edu. cn
ABSTRACT
While data scaling laws of large language models (LLMs) have been widely examined in the one-pat one-pass regime with massive corpora, their form under limited data and repeated epochs remains largely unexplored. This paper presents a theoretical analysis of how common workaround, training for multiple epochs the same dataset, reshapes the data scaling laws linear regression. Concretely, we ask: match the performance of training on a dataset of size N for K epochs, how much larger must a dataset be if the model is trained for only one pass? We quantify this using the effective reuse rate of the data, E(K,N) N), which we define as the multiplicative factor by which the dataset must grow under one-pass training to achieve the same test loss as K K-epoch training. Our analysis precisely characterizes the scaling behavior of E(K, N) for SGD in linear regression under either strong convexity or Zipf-distributed data: (1) When is small, we prove that E(K, N) R K, indicating that every epoch yields a linear gain; (2) As increases, E(K, .) plateaus at problem-dependem value that grows with N (oolg N)) for the strongly-conver case), implying that larger datasets be repeated more times before the marginal benefit vanishes. These theoretical findings point out neglected factor in recent empirical study by Muennighoff al. (2023), which claimed that training L.MS for up to 4 epochs results in negligible loss differences compared to using fresh data at each step. i.e., E(K, N) K for K < 4 in our notation. Supported by further empirical validation with LLMs, our results reveal that the maximum K value for which E .N x in fact depends on the data size and distribution, and underscore the need to explicitly model both factors in future studies of scaling laws with data reuse.
INTRODUCTION
Scaling laws (Hestness al., 2017: Kaplan et al., 2020; Hoffmann et al., 2022) have emerged as central framework for characterizing the behavior of large language model (LLM) pre-training. The Chinchilla scaling law (Hoffmann et al., 2022) established robust empirical trends in performance as a joint function of model size and dataset size under the one-pass training paradigm, in which each data point is used most once. This assumption, however, is becoming increasingly untenable. The quest for more capable models has driven an unprecedented escalation in data requirements: from fewer than 10 billion tokens for GPT-2, 300 billion for GPT-3 (Brown al., 2020), 2 trillion
"qqual contribution. Corresponding author.

---

Published as a conference paper at ICLR 2026
6:25
0.35
0.26
locs (200))
5.75
Riy 0.
Saturation Puints
DIC #ipoch
Sport Teatssaa aaggh
5,00
Borncy Eporte wall
322
6%10
4Epach
Step
Fresh Data SizedB)
(a) E(K, N) as function of K.
(b) Validation loss of one-pass and (c) The saturation points grows lin- early with log N.
multi-epode -eoliieepchhhhc training runs.
Figure 1: Our LLM experiments show that larger datasets can be repeated more. (a) The effective reuse rate E K, N) s K when is small, but eventually saturates at certain number of epochs. (b) The saturation point shifts to larger K as the dataset size increases. (c) Empirically, the saturation points scales linearly with log N.
for Chinchilla and LLaMA 2 (Hoffmann et al., 2022; Touvron et al., 2023), and 36 trillion for Qwen3 (Yang et al., 2025). Projections further suggest that the pool of publicly available data may be exhausted early as 2028 (Villalobos et al., 2024).
A common response to this emerging data scarcity is to train models for multiple epochs over the same dataset. Recent empirical studies have begun to examine the consequences of such repetition: for example, Muennighoff et al. (2023) and Xue et al. (2023) show that moderate reuse can still yield competitive pre- pre-training performance. Yet the fundamental scaling behavior of multi-epoch training remains poorly understood particulartt from a theoretical standpoint.
In this paper, study fundamental question in understanding how multi-epoch training affects the data scaling laws: To what extent can training for K epochs on N samples be effectively seen as one-pass training with an increased number of data samples? Formally, let L(K, .) denote the expected loss of K K-epoch training on N samples. We define the effective dataset size N' N) as the minimal number of samples in one-pass training that achieves comparable or lower loss C(1, < C(K,N) In this paper, we are concerned with the ratio E(K, N'(K, /N/N, which we term as the effective reuse rate of the data, key quantity that characterizes how many times larger the dataset must grow to match the same performance as K Keepoch training (see the detailed version in Definition 3.
In recent study of scaling laws for multi-epoch training, Muennighoff et al. (2023) encountered this question and proposed an empirical approximation: N' N) = (1 + R² e -KK -11)/R)) -N, where R is a fitted constant (R" x 15.39 in their experiments). This formula suggests that the benefit of repetition grows with K but saturates exponentially at (1 + R*) NN as K increases. While supported by some empirical evidence in their study, this approximation still leads gap between scaling law predictions and empirical results (see Figure 3 in their paper). Moreover, the formula implies that the ratio E(K, N) = N'K,, K N/NN is independent of N, so the benefit of repeating the dataset K times is equivalent to increasing its size by factor that depends only on K, regardless of how large N is. It remains unclear to what extent this independence holds in general.
noticeable
Our Contributions. In this paper, approach the above question the effective reuse rate of data in the setting of linear regression, a setting that is simple enough to reveal the key mechanisms of data reuse, while still tractable for precise analysis under stochastic gradient descent (SGD). We provide a theoretical characterization of F K, NN in various regimes, and point out a neglected factor in the empirical study of Muennighoff et al. (2023): the effective reuse rate depends not only on the number of epochs K, but also on the dataset size N. In fact, we show both theoretically and empirically that larger datasets can be repeated more. Our main contributions are as follows:
1. In Section 4, we analyze multi-epoch SGD for linear regression under strong convexity. We show that when K is small, E(K, .N R K, so every new epoch leads to a linear gain. As K increases, E( K, N) saturates at problem-dependent value of order Olog N), suggesting that larger datasets can be repeated for more epochs before the marginal benefit vanishes.
2. In Section 5, we go beyond the strongly convex case and study class of Zipf-law distributed data, and show that (KK, .N exhibits similar scaling behavior to the strongly convex case, except that the saturation point scales as a power of N instead of log N.
3. Technically, we derive the optimal learning rate (Lemma 4.4) for multi-epoch SGD in linear regression and its corresponding approximation formula for the expected excess risk up to o(1) multiplicative error (Lemma 1. These results may be of independent interest.
2

---

Published as a conference paper at ICLR 2026
4. In Section 6, we conduct LLM pretraining experiments with up to 200B repeated tokens. Consistent with our theoretical findings, the empirical results show that E(K,N) = K for small K, but eventually saturates at epoch number that scales linearly with log N. See also Figure 1 for details.
2 RELATED WORK
Data Reuse in LLM Pre-Training. Empirically, there is long debate over the effect of data reuse in LLM pre-training. Some works (Lee al., 2021; Hoffmann al., 2022; Hernandez al., 2022; Wang et al., 2023) suggested it may be harmful, while some works (Taylor et al., 2022) reported the benefit of data reuse when the number of epochs is small (K < 4). Xue et al. (2023) then discovered a degradation phenomenon in multi-epoch training and investigated relevant factors and regularization methods to tackle it. Muennighoff et al. (2023) trained LLMs under different configurations and also found that reusing data is as good as using fresh data in the first few epochs. Yet, as the number of epochs increases, the returns for repetitions diminish. In our work, from a theoretical perspective. we rigorously analyze the effect of data reuse using non-asymplotic techniques, and we define and calculate the effective reuse rate under two cases, shedding light on the theoretical understanding of data reusing in LLM pre- -reitrain
Comparison with Lin et al. (2025). A recent study on linear regression with data reusing (Lin et al., 2025) is among the most relevant to our results. They showed that when the number of epochs is relatively small (smaller than some power of the dataset size), the order of loss remains the same as one pass SGD for the same iterations, which aligns with our results. However, their results only imply that EK,, N) = (KK) for small K, while our analysis directly gives the explicit loss characterization with o(1) relative error bound and more exact description of the effective reuse rate, which reflects the data reusing scaling behaviour. Our analysis is across various problem setups, and further shows the general scaling trend of data reusing under different problem setups.
3 PRELIMINARIES
Notations. We use ||- I| to denote the f2-norm of vectors and the corresponding operator norm of matrices. For two sequences (A,)%= and (B,, ) we write An = O(B)), ), or alternatively A, S Bn, B, = I(A,). Bn 2 An. if there exist constants C >> 0, N > 0 such that |A,,| < B,, for all n 2 N. We write An = O(B,), or alternatively A. x Bn, if both A, = O(B,) and An = 2((B,) hold. Moreover, for some variable n. write An o,, (B,) if for every constant e > 0, there exists no > 0 such that [An| < B, for all n 2 no. In this paper, when n is clear from the context,
write An o (B,) for short. Furthermore, we write A, (B,)) if B,, AAA)). For matrices A2, A., we use I A; to denote the product A, An We define |uuls := Vu Su for any vector and any positive semi-definite (PSD) matrix S.
Linear Regression Problem. We focus on a linear regression setup, where data point (x, y) E Rd x R follows a joint distribution D and ||>||| S D for some constant D. W.L.O.G., we assume that the covariance matrix of data input is diagonal, i.c., H == E(xx = diag (>1, xe..... Ad). Ad- A direct corollary is that X1 < D For a given data input ær, the label y is generated by y == (un" ; x) + E, where w= E T2d is the ground-truth weight and & represents the independent random label noise with Eg] = 0 and B| o². We aim to train linear model f(x; w) := (w, x) to predict the data label, where w E 12 is the trainable parameter. We use MSE-loss f(w; x. y) = 2f((;;; w) y to measure the fitting error. Then, the population loss is defined as [(w)= == Eq fta..w>D/ll (f(w;; x. y)]. Further we define the excess risk R(w) := L(w) 2 which is the expected population loss minus the irreducible loss 1
where \ A2 2
Multi-Epoch SGD Training Algorithm. Consider finite training dataset with N data points (Eoo y0), (xt,, 21 ),.),.., NIN -N-1)), where the data points (æt, yi) are i.i.d. sampled from the distribution D. We use K K-epoch stochastic gradient descent (SGD) with random shuffling minimize the loss function. And the initial parameter wo is set to O. Formally, we denote K independent random permutations of [M] by ....... .K. And we define j. := Tk, (it), where i, := mod N, k, : [t/N] + 1. Then we have the update rule for K Keepchh SGD with N data points
W++1 wt V/
w (1015 Feje 11.) (I 1110 n)) w. 2...
3

---

Published as a conference paper at ICLR 2026
Next, given K K-epoch SGD over N data points, with learning rate 1, define Wk.N.y be the distribution of WKN- The randomness within WKN comes from the random draw of the dataset, label noise Ç, and the shuffling in SGD. Based on this, define the expected excess risk of given K-epoch SGD over data points, with learning rate v) as R(K, N: == Bww-WK.... [R(w)]. We assume < D-2 for training stability.
We also consider multi-epoch training under more practical training configurations, for example, using a class of polynomially decaying learning-rate schedules. See Section K for more details.
Comparing Performance under Optimal Learning Rate Regime. To compare the performance of one- pas-passee and multi-epoch SGD, we consider the settings where the learning rates for both methods are optimally tuned. Formally, we introduce the notion of the optimal expected excess risk of y epoch SGD for N samples as R (2(K,N N) == min (0, 2221 [R(K, n)). To calculate this value analytically,
in the next section, we will show that we can get learning rate choice that can approximately achieve the above optimal expected excess risk R , N) both for one-pas, pee-pass and multi-epoch SGD. Following our discussion in the introduction, we define the effective reuse rate follows:
Definition 3.1 (Effective Reuse Rate). Given K-epoch SGD trained with N fresh data samples, the effective reuse rate is defined as: E) == N (i' 2 0: R (1, S (K).
That is. the effective reuse rate measures how many times larger the dataset must grow under one- one-pass training to match the performance of K K-epoch training, both under the optimal learning rate regime.
4 MULTI-EPOCH SCALING IN STRONGLY CONVEX LINEAR REGRESSION
In the study of linear regression problems, the strongly convex case is a classical and central theoretical framework, serving as the standard entry point before relaxing to weaker conditions in many analyses (Hastie, 2009; Ge al., 2019). In Section 4.1, first give the problem setups and the main results of the effective reuse rate. In Section 4.2, we give a proof sketch for our theoretical results, and the detailed proof of this section be found in Appendix G.
4.1
MAIN RESULTS
As we focus on the strongly convex case, we make the following assumption on the minimum eigenvalue of the Hessian matrix. Assumption 4.1 (Strong Convexity). We assume that Xa 2 μ for some constant >> 0.
For simplicity, we make the following prior for the ground-truth weight w".
Assumption 4.2 (Parameter Prior). The ground truth w" satisfies wt + 0 for all i [d].
As the number of samples N can be very large in practice, training on the entire dataset for large amount of epochs can be computationally expensive. This motivates us to impose an upper bound on the number of epochs K. Technically, this ensures that the accumulated error terms remain manageable in our analysis.
Assumption 4.3 (Computationally feasible number of epochs). We assume that the training dataset size N and number of epochs K satisfy K = O(Nu.1)
Here, the exponent 0.1 chosen for case calculation, though it may not be tight.
To compute E(K, N). we first precisely characterize the optimal expected excess risk. In particular, we derive asymptotic expansions for R"(K, N) in the regimes K = o(log N) and K = w (log N), each expressed as leading term accompanied by explicitly controlled higher-order remainder.
Theorem 4.1 (Multi-Epoc) Data Scaling Law). Under Assumptions 4.1 to 4.3, for multi-epoch SGD with the number of epochs K, dataset size of N, it holds that
5 o²tr(H) Shd
log(KN) (1+ (N)))
for = o(log N):
R RK,
KN
(N)+
for K w(log N).
Theorem 4.1 describes how expected excess risk decays with number of epochs K and dataset size
N when choosing the optimal learning rate. When K & log N, then RR (K, (KNN N) θ 1og where
4

---

Published as a conference paper at ICLR 2026
T= KN; by contrast, when K > log N. then R R*(K,N N) O (2:) which does not depend on K, showing that endless data reuse turns out to be useless.
Next propose the expression of E(K,N) NN) by applying Theorem 4.1.
Theorem 4.2. Under Assumptions 4.1 to 4.3, multi-epoch SGD with the number of epochs K, dataset size of N, it holds that
(1 + (x)) K (x(H) Da2d (1 + oN(()) log N for K w(log N).
for K a(log N);
N)K,N)
Theorem 4.2 pinpoints two regimes for the effective reuse rate in the strongly convex case. The first one is the effective-reuse regime: when K < log N. then E(K, NN K (1 + o()). This suggests that each extra epoch is essentially as valuable as a fresh pass. The second one is the log (1 + (w((1), which means Dxd
limited-reuse regime: when K > log N, then E.KK, N) additional epochs yield only logarithmic gains. This further implies that the model has effectively "seen" the dataset enough times that additional repetition redundant.
Together, these two asymptotic descriptions expose phase transition when the quantity
lim Nog changes from co. For the former case (lim, log N 0), multi-epoch
K training behaves like unlimited data augmentation; for the latter (limN log N oc), the benefits of reusing data all but vanish, capping E(K, .N at Oloog
Larger Datasets Can Be Repeated More. Our theorem provides the following insight. Fixing the data distribution, as we collect more data, the largest possible epoch number K stay in the effective-reuse regime also increases. Consequently, larger datasets can sustain more epochs while maintaining linear gains from data reuse. Specifically, for the setup we study in this section, if we have collected N data points in total, then with multi-epoch training, we can get a performance comparable to one-pass training on ( log N) data points, which is superlinear in the number of data points we collected. This finding highlights neglected factor in the data-constrained scaling laws proposed in Muennighoff et al. (2023), which assumed a uniform effective number of epochs across different fresh data sizes. In Section 6.3, validate this insight by showing that the effective reuse rate indeed increases with the dataset size in LLM pretraining.
Discussion:
Effect of Learning Rate Decay. The factor log N is in fact associated with the use of constant learning rate in our setting, where 1) may depend on the total number of steps but remains fixed throughout training. While our main focus is on the constant learning rate setting, introducing learning rate decay may lead to different scaling behaviors and warrants further theoretical investigation. Under learning rate decay, for example using Ti T+ with b 0 and 0.5 a S 1 at step by direct calculation based on the setup of Theorem in Ge al. (2019), it is not hard to show that one-pass training yields R R² N) = O(KH
add) for sufficiently large N when
N
X, is the condition number of H. This bound loses only by constant factor = 1, where ки == Å
o²d implied by the Cramér-Rao lower bound (Jain et al., compared to the statistical minimax rate 2N 2017). Therefore, under learning rate decay, the effective reuse rate of multi-epoch training is at most ((KH). In Section K, we provide preliminary analysis comparing one-pass and multi-epoch training in the limit of infinitely many epochs, showing that multi-epoch training can almost attain the statistical minimax rate and achieve E(oo, N) [((H). It remains interesting direction to understand how E(K,N) saturates to this value and how it depends on the dataset size N.
4.2 PROOF SKETCH
We now provide a proof sketch of our main results. First, we need to compute the optimal expected excess risk R² (K, This requires us to compute R(K, N; 1)) and then select the optimal learning rate 17" that minimizes R(K, N; m)) However, due to the random shuffling and multi-pass processing of the training data, directly analyzing R(K, N; is intractable. To overcome this, we seek an analytic approximation of R(K, N:)), which is derived through the following steps.
Varianee Decomposition for Training Dynamics. Following the widely-applic bias variance decomposition approach to analyzing the dynamics of SGD training (Neu & Rosasco, 2018; Ge et al., 2019; Zou et al., 2021; Wu et al., 2022a), we define 0, = w. w" and examine the following two processes of bias and variance:
Step 1:
0bias 0piss
17 (Obise .m..) Mz. 0:35
5

---

Published as a conference paper at ICLR 2026
0r 17 (0tmr )z,) Zz + n/SS, Je where the two processes are initialized as Obins ww =" and
0er 0. It follows that 0, O + 0ttrr, with [[ O. We can then decompose the excess risk R w.) into two components: the bias term and the variance term, which we formalize as follows 0
R(w;) 0
10 I
Step 2: Analytic Risk Approximation by Matrix Concentration. A key challenge in tracking the dynamics of multi-epoch SGD training arises from the con-commutative nature of the matrices in the weight updates, which depend on randomly shuffled and multi-past data. For example, the bias weight evolves as A giia (IT [
N [ II s (1) a (1 Obiss, where we can see that one
data point appears more than once across different epochs. Thus, the above matrix multiplication
involves massive correlated data, which makes calculating the bias term E [| H intractable.
To resolve this issue, borrow tools from concentration inequalities for matrix products Huang et al. (2022). Specifically, we use the following result:
Lemma 4.1 (Corollary of Theorem 7.1 in Huang et al. (2022)). Given n data points such that 2n-1
iidd NO, H), and defining A = TT (I n2,z]), we have E||A EA| <
20,
(VosrPnl) where 8 = D log d for some absolute constant C >
However, several obstacles prevent us from directly applying Lemma 4.1 our problem. For example, actually need to control enror terms like E
I k+1 A (EA)* where A represents the product of sequential updates through all samples in epoch (see the formal definition in Equation (1), Appendix E). To address this, our main idea is to derive a tight upper bound for the original term, and decompose this upper bound into the sum of series of sub-terms for which we can apply Lemma 4.1. (see the detailed derivation in Appendix G.2.1 and Appendix G.2.2)
Finally, we derive an eπrоr bound on matrix deviations based on our calculations, which is a higher- order infinitesimal of the main term when ry E Ω (T o) and = 0 with
T KN denoting the total number of training steps. This provides theoretical guarantee for to approximate the risk function with tractable expression. For the bias term, we have
K
N-1
E
0KNN
= E
II 1m0
n n (1)00))21111))
0g
H
II
I ya 10
Oo
[|( - )H)
KN
0u
where the approximation step follows from Lemma 4.1, and the last equation follows the facts that E (1) (1) H and æ; is uncorrelated with æ, for + j. For the variance term, the data correlation issue is similar to what we met in the bias term case. Again, leveraging Lemma 4. and following similar analysis, can get approximation formula for the variance
shown:
202 N
(I- HHH KN ((I H - -I- H1)
E 0 var 2
tr
(I-
+ no² (H, (I-nH) 2KN
2KN 2KN -H)
Step 3: Narrowing the Range for Optimal Learning Rate. However, although we have an analytic approximation for risk, it is important to note that this approximation holds only for a specific range of parameters. For detailed discussion, refer to Lemma G.I. To mitigate this, first determine reasonable range for the optimal learning rate in two steps: First, choose rj log K K 2A,K reference learning rate; Then, by comparing the losses for the reference learning rate and other candidate learning rates, we can eliminate a large range of values. This analysis helps narrow down the potential range of learning rates (Lemma G.5 for small K and Lemma G.6 for large K). Within

---

Published as a conference paper at ICLR 2026
this range, further simplify the risk approximation make it more tractable for optimization, as shown in the following lemmas:
Lemma 4.2 (Small K). Let H PDP be the canonical form of H under similarity,
and let 02 Li-d 2i-d-a+t1 (POo) Under Assumption 4.1 and 4.3, for learning rate n e K ollog N), we have R(K,N;n) MM,,, N;n)( o(1)) with (xxppp2277KN)) str(M
log KN DoR KN
BAJKN X
M (K, N:n)
Lemma 4.3 (Large K). We define fg as the same Lemma 4.2. Under Assumption 4.1 and 4.3, log 3 o (t)) and = =w(log N). we have R(K, N; = (1)) for learning rate 1) E
o(1) with M NiT) 10 -2app(222mK)) + ger(H)o² o'd 2N
Step 4: Deriving the Approximately Optimal Learning Rate. At this point, have narrowed down the range for the optimal learning rate and simplified the risk approximation. The next step is approximate the optimal expected excess risk. To achieve this, differentiate the simplified risk function M(K, (K n))) in Lemma 4.2 and Lemma 4.3 with respect to the learning rate vj and give the critical point 17 1/' (K, N). which are presented follows:
Lemma 4.4 (Approximately Optimal Learning Rate). Under Assumption 4.1 and 4.3, we consider K- pKg epoch SGD with N fresh data and learning rate 1) NK, 2A.KN' it holds for K o(log N) or K = w(log N) that R K, NN; = R (K, (1 (1))
10
where p Ho) Then
Using Lemma 4.4, complete the proof as follows. By evaluating the risk the approximately opti- mal learning rate v/' (K, .) log N we obtain an approximation of the optimal risk (Theorem 4.1),
NN
based on which we derive the effective reuse rate (Theorem 4.2).
A SOLVABLE CASE WITH ZIPF-DISTRIBUTED DATA
Natural data distributions often exhibit power law structures. To capture this phenomenon, we go beyond the strongly convex case and analyze stylized linear regression model with Zipf-distributed data, where the excess risk admits closed-form expression and the effective reuse rate can be characterized explicitly.
Through this setup, we can see that the effective reuse rate exhibits a similar scaling behavior: as the number of epochs K increases, E(K, .) initially grows linearly but eventually saturates at problem-dependent value that increases with N. In contrast to the strongly convex case, however, the saturation point does not scale as ~ log N but instead scales as a power of N.
Problem Setup. We use the same notation for excess risk, one-pass and multi-epoch SGD, and i.id. training data as in Section 3. We specify the data distribution as Zipf distribution over one-hot data points, where the i-th data point is (f) μàe; for some μ4 0 and the probability of sampling the i-th data point is P; = c i i for some constants >> 0 and a > 1. The label
generated by y = (w",a, x) with no label noise. The ground-truth weight w" 12d follows an isotropic prior distribution.
Assumption 5.1 (Parameter Prior). w* is sampled from a prior distribution with E/w0" wn" T
Interpretation. This setup can be interpreted as a simplified model of real-world data with heavy- tailed feature distributions. Each coordinate represents an atomic feature that appears with Zipf- distributed probability, mimicking the long-tal statistics observed in domains such text and natural language. The scaling factors μ4 encode feature importance, which may reflect, for instance, effects introduced by feature weighting or normalization.
5.1 RESULTS ON POWER LAW SPECTRUM
Assumption 5.2 Law Spectrum). There exist two constants a, b> with such that the data input distribution satisfies that p; (a-(a-)) and A; = =i where e = Dd
- fo-8 1
7

---

Published as a conference paper at ICLR 2026
Here establish matching upper and lower bounds for in the small-K and large- regimes, given the solvable model. Comparing with the strongly convex case, we observe a different
scaling behavior: when K < Na-b, R R*,,NN decays power law in KN,, with exponent "=1; whereas when K > N RD NK exhibits power-law decay in N and is independent of K. Theorem 5.1. Consider -epoch SGD over fresh data. Under Assumptions 5.1-5.2, and given the data dimension ()=,, holds that
(KN)-
for o(No=z) for K = w(No-t.
R' ())
N
Then we derive the formula of E NN by first solving the equation R (1, R²' RK, (K,N) based on Theorem 5, and divide T by N.
Theorem 5.2 (Multi-Epoch Scaling Under Power-Law Spectrum). Consider K-epoch SGD over N fresh data. Under Assumptions 5.1-5.2, and given the data dimension d (2((K))=) it holds that
K(1 +(1) for K o(N==s) O(N=T) for K = w(N=o).
E(KK, N)
Under the assumption of logarithmic power-law spectrum, the trend of the effective reuse rate as function of K approximates the phenomena described in Theorem 4.2 in the strongly convex setting and the trend described in Theorem 5.2 under the power-law spectrum assumption. We still observe an effective-reuss regime (E(K,N) N) = K) when K relatively small (K < (Nb((--))), and as K increases, the effective reuse rate undergoes phase transition, converging an upper bound determined by N, entering the limited-reuse regime (E(K,N) @(Nb/(a-b)))
We can see that the exponent of this power of N is determined by the rate of eigenvalue decay of the Hessian and the rate of norm decay of the parameter with respect to dimension. The proofs of Theorem 5.1 and Theorem 5.2 are given in Appendix I,2 and Appendix I.3 respectively.
5.2 RESULTS ON LOGARITHMIC POWER-LAW SPECTRUM
Further, we aim to understand under the same Hessian matrix, how the data distribution correlated with P and A affects the effective reusing rate. By changing the spectrum of A, can also obtain matching upper lower bounds for R (K, .)) and characterization for E'K, which behave differently from the power-spectrum case. Here we present only the latter; the former be seen in Appendix D.
Assumption 5.3 (Logarithmic Power-Law Spectrum). There exist two constants 1, 0 such that the data input distribution satisfies that pa ci ci "Log"( + 1) and A, 1/log" (illog(i + 1), where
c= (Ei i-olog" (i
Theorem 5.3 (Multi-Epoch Scaling Under Logarithmic Power-Law Spectrum). Under Assump- tions 5.1, Assumption 5.3, and given the data dimension d = (((KN) ) one-pass SGD and K K-epoch SGD over N fresh data, holds that
K(1 +o(1)) for K = o(log" N) E(K, N) = O N) for K = w(oog N).
The Saturation Point Varies across Different Problem Setups. The phase transition point where the effectiveness of data reusing changes from the effective-reuse regime the limited-reuse regime varies across different problem setups. In strongly convex linear regression problems, this phase transition happens when the limit limg- log N changes from to oc. And in the above power
spectrum and oog-oower spectrum case, the limit turns to be lim -00 x and lim -000 log"
K
K
8

---

Published as a conference paper at ICLR 2026
E(K.N) for Different K
Power Spectrum: EIK, M.
Power Spectrum EIK log(A)
N- 5-100
K-2
N- 1-100
K=100
3-100
K-1000
1711
102
BK.NI 0,205922
EKK
5-10"
EIK,00
1-110
2-
109
100
1000
10600
100000
10a
102
107
16
N
K
log(N)
(a) Strongly convex EKK,N) (b) The solvable with Zipf- Zipf-distributed data and power spectrum: E(K, N) versus and N.
with N
Figure 2: Simulation experiments for strongly-conee lincar regression and the solvable case with Zipf- distributed data and power spectrum. Results show that E(K, N) is approximately proportional to some function N when is relatively small, and EKK, N) =s K when case with Zipf-distributed data and power spectrum, we also fit the effective reuse rate using the formula E P(K,N) N) ci N suggested by Theorem 5.2, and the fitted exponent cq 0.279 & a-b theory.
relatively large. For the solvable
matches our
EXPERIMENTS
6.1 SIMULATIONS IN SECTION 4
First, we conduct our experiments on synthetic datasets with strongly convex linear regression to verify the characterization of effective reuse rate E(K, N) in Theorem 4.2.
Experiments Setup. We generate data pairs (æ,, 34) where x; i.dd N Ia) with dimension d 100. For the label yı, generate it y/ (w",,,) xx, E,, where w" the ground truth generated by standard Gaussian with unit variance. Also, & ~ (N0 IR)). Here in our simulation, we set a 0.1. To make our simulation aligned with the theoretical setup, we set the learning rate K.N. 7 x KN and we grid search the ratio c : log KN/KN for the c* which minimizes the final loss KNN
given training steps
Results. As shown in Figure 2a, plot E(K, N) function of log N for various fixed values of K. Each curve corresponds to a fixed number of epochs (e.g.. 3, 5,.,,... 20) and illustrates how the effective reuse rate E(K, N) grows with dataset size. For small data size (log N < K), the effective reuse factor increases roughly linearly with log N, indicating that adding more data substantially boosts the one-pass equivalent performance. However, as N becomes large (log N > K), each curve flattens out and approaches an asymptote at E(K, N) ~ K. In other words, once the dataset is sufficiently large relative the number of epochs, additional passes through the same data yield no further benefit beyond factor of K. This behavior is exactly predicted by Theorem 4.2: when K much smaller than log N, we have F K, N) K (nearly full K K-fold data reuse), whereas when K is large relative to log N, the effective reuse saturates and grows only the order of log N.
6.2 SIMULATIONS IN SECTION 5.1
We now verify the predictions of Theorem 5.2 using synthetic data generated under the spectral assumptions of Section 5 with power-law decay Hessian spectrum (Assumption 5.2). In all sub- figures of Figure 2b, we set the data dimension d to 10 and tune all the learning rates to their optimal values. Here we set a = 4.5 and =
Results. Figure 2b plots E(K, , N) versus K and log N for the solvable model with Zipf-distributed data. The curves depicting F(K,N N) versus K show that E(K, N) K when K is relatively small and saturate some value depending on N when K is large. In the right panel, which describes the relationship between E(K,N and log NN observe that when K is small (namely K 2). E(K, N) increases and approaches K as log N increases, and the plots overlap when K large. Those phenomena provide empirical confirmation of the scaling behaviors predicted by Theorem 5.2. We also fit E(K, N) in the large- K regime with a power-form function as stated in Theorem 5.2. The fitted exponent is 0.279 b
aligning with our theory.
6.3 EMPIRICAL VALIDATION ON LARGE LANGUAGE MODELS
Experiments Setup. We conduct experiments on a large language model to empirically validate the hypothesis that larger datasets allow for more effective repetition. We perform pretraining

---

Published as a conference paper at ICLR 2026
with fresh data sizes of 0.2B, 0.5B, 0.8B, 1.0B, and 2B tokens, each trained for 100 epochs. As control, we also include a run with 200B fresh tokens. For each fresh dataset size N and training epoch K. approximate the effective reuse rate E(K, N) by determining the effective fresh data size Ny(K, N) required to achieve the same validation loss after one pass through the data. The effective reuse rate is then computed as: N) N,((K,)
N
Our experiments utilize a 0.3B parameter model adapted from the Qwen2.5-0.5B architecture (Qwen et al., 2025) and a subset of the DCLM dataset, totaling 200B tokens. A separate subset of the DCLM dataset is reserved for validation. Crucially, we use a constant learning rate schedule across all experiments to align with our theoretical analysis and mitigate the confounding effects of learning rate schedules, as reported in prior work (Hoffmann et al., 2022; Luo et al., 2025). Figure 1a depicts the relationship between E B(K, N) and K. Figure l depicts the training curves for different data sizes, and marks the points of different curves where E(K, N) XK, where À controls how strict the criterion is for determining when multi-epoch training begins to underperform one-pass training. Given such X. denote the corresponding number of training epochs as K (A, NV), which we refer to as saturation points. In our experiments, we take À = 0.75. Further, in Figure Ic, we show the precise relationship between (A,,, N) and N. More details regarding the experiment setup are available in Appendix C.I.
Previous Work: When K S E(K, K. Our theoretical analysis indicates that E(K, N) should be close to K when K is small (e.g.. K < 4). In Figure 1a, when the epoch number is small (approximately < 5), observe that E(K, N) increases at a rate comparable to the epoch number, as indicated by the black dashed line. Thus our predictions of E(K, N) when K is small aligns with the cata-coonttained scaling laws (Muennighoff et al., 2023).
Larger Datasets Allow More Repetition. E(K, .N) increases with the number of fresh data sizes and eventually saturates for sufficiently large fresh datasets. Our results challenge the conttroontr scaling laws proposed by Muennighoff et al. (2023), which assume a uniform effective number of epochs across different fresh data sizes. In Figure 1b, we show that at the critical points where one-pass training start to outperform multi-epoch training significantly. E(K, .N) increases as N increases. This suggests the continued potential for scaling pretraining through multi-epoch training with larger datasets.
Fitting Experiments. In Figure Ic, to provide real-world evidence that larger datasets can be repeated more, we plot the saturation point values for different N to illustrate how they vary with N. Then we fit them as a function of N; see Appendix C.2 for details of the fitting procedure.
Surprisingly, though we do not claim that E(K, .N (log N) holds for general LLM trainings when K is large, as we calculated in the strongly convex linear regression case, here we do observe that K (A, .) gradually increases when N increases, and it follows that K K(X, N) Ri 0.80 log N + 5.21 with the correlation coefficient being r = 0.97. In this formula, the dataset N is measured in billions of tokens (B).
Experiments with Learning Rate Decay. For further investigation of the scaling behaviour of multi-epoch training, we conduct LLM experiments with a non-constant learning rate schedule, aligning with the common practice in reality. Specifically, we additionally repeat the above analysis with WSD learning rate schedule with linear decay. The experimental setup and results are described in Appendix C.3.
7 CONCLUSION
In this paper, we intrdouce the concept of effective reuse rate E(K, N)) and show both theoretically and empirically that larger datasets can be repeated more. More specifically, E(K,N) N) saturates at later epochs as the dataset size increases. Several directions remain open for future study. (i) Our analysis is limited to the setting of optimal constant learning rates, and it remains to understand how learning rate decay, as well as the effort spent on tuning the learning rate, affect the effective reuse rate. (ii) Our theoretical analysis currently focuses on linear models, and a natural next step would be to extend the framework to more complex settings, such as neural networks with feature learning. (iii) We focus on reusing the entire dataset across multiple epochs, but to fully explore the potential of data reuse, one may consider more refined strategies such as selectively reusing or rephrasing high-quality data. (iv) Technically, our main results rely on strong convexity. Although we analyze a solvable case under a Zipf-law data distribution, generalizing these proof ideas to broader non-strongly convex settings remains important theoretical challenge.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
This work supported by the National Natural Science Foundation China under Grant Number 62495062. Binghui Li is supported by the Elite Ph.D. Program in Applied Mathematics Peking University. We would like to thank Licong Lin, Huaqing Zhang, Jingfeng Wu, Kaiyue Wen, Jingzhao Zhang and Jason D. Lee for their insightful comments, and the anonymous reviewers for their valuable feedback.
REFERENCES
Armen Aghajanyan, Lili Yu, Alexis Conneau, Wei-Ning Hsu, Karen Hambardzumyan, Susan Zhang, Stephen Roller, Naman Goyal, Omer Levy, and Luke Zettlemoyer. Scaling laws for generative mixed-modal language models. In International Conference on Machine Learning, pp. 265-279. PMIR, 2023.
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. Sgd with shuffling: optimal rates without component convexity and large epoch requirements. Advances in Neural Information Processing Systems, 33: 17526-17535, 2020.
Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iuvant: Data repetition allows sgd to learn high- -imeesiinnii multi-index functions, 2025. URL https: //arxiv. org/ abs/ / 2405. 15459.
Alexander Atanasov, Jacob Zavatone- Veth, and Cengiz Pehlevan. Scaling and remormalization in high-dimensional regression. arXiv preprint vrXiv:2405.00599 2024.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. Proceedings of the National Academy of Sciences, 121(27)xc2111888822 2024.
Xiao Bi. Deli Chen, Guanting Chen, Shanhuang Chen, Damai Dai, Chengqi Deng, Honghui Ding, Kai Dong, Qiushi Du, Zhe Fu, al. Deepseek I1m: Scaling open-source language models with longtermism. arXiv preprint arXiv:2401.02: 102954, 2024.
Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A dynamical model of neural scaling laws. arXiv preprint arXiv:2402.01009,, 2024a.
Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. How feature learning can improve neural scaling laws. arXiv preprint arXiv: 17850, 2024b.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neclakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
2020.
François Charton and Julia Kempe. Emergent properties with repeated examples. arXiv preprint arXiv:2410.07041, 2024.
Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborová, and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents, 2024. URL https: wtt.aaaxvvvv......a.aa..aaa. abs /2402 03220.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger conver- gence rates for least-squares regression. Journal of Machine Learning Research, 18(101):1-5 2017.
Elvis Dohmatob, Yunzhen Feng, Pu Yang, Francois Charton, and Julia Kempe. A tale of tails: Model collapse as a change of scaling laws. arXiv preprint arXiv:2402.07043, 2024.
Damien Ferbach, Katie Everett, Gauthier Gidel, Elliot Paquette, and Courtney Paquette. Dimension- adapted momentum outscales sgd. arXiv preprint 2rXiv:2505.16098. 2025.
Rong Ge. Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. Advances in neural information processing systems, 32, 2019.

---

Published as a conference paper at ICLR 2026
Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The stavy phenomenon in sgd. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3964-3975, PMLR, 18- 24 Jul 2021. URL https:://// : http:ss://prreeeeeeee proceed ngs.... mml.m.l.... www.spess//eee 39/ gurbuuuuuubbba hww.hbaalaban211mmm aban21a. html.
Trevor Hastie. The elements of statistical learning: data mining, inference, and prediction, 2009.
Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B Brown, Prafulla Dhariwal, Scott Gray, et al. Scaling laws for autoregressive generative modeling. arXiv preprint arXiv:2010. 14701, 2020.
Danny Hernandez, Tom Brown, Tom Conerly, Nova DasSarma, Dawn Drain, Sheer El-Showk, Nelson Elhage, Zac Hatfield- Tom Henighan, Tristan Hume, al. Scaling laws and interpretability of learning from repeated data. arXiv preprint ar arXiv:2205. 10487, 2022.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically, arXiv preprint arXiv: 00409, 2017.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203./555 2022.
De Huang, Jonathan Niles-Weed Joel A Tropp, and Rachel Ward. Matrix concentration for products. Foundations of Computational Mathematics, 2266)117 2022.
Marcus Hutter. Learning curve theory. arXiv preprint
2021.
Ayush Jain, Andrea Montanari, and Eren Sasoglu. Scaling laws for learning with real and surrogate data, 2024. URL https: /ttp/v.wivv///////////..///.aa org/
Prateek Jain, Sham Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, and Aaron Sidford. A markov chain theory approach to characterizing the minimax optimality of stochastic gradient descent (for least squares). arXiv preprint arXiv:1710.09430. 2017.
Arlind Kadra, Maciej Janowski, Martin Wistuba, and Josif Grabocka. Power laws for hyperparameter optimization. arXiv preprint trXiv:2302.004// 2023.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv.2001.08361, 2020.
Joshua Kazdan, Rylan Schaeffer, Apratim Dey, Matthias Gerstgrasser, Rafael Rafailov, David Donoho, and Sanmi Koyejo. Collapse or thrive? perils and promises of synthetic data in self-generating world. arXiv preprint arXiv:2410. 16713, 2024.
Tanishq Kumar, Zachary Ankner, Benjamin F Spector, Blake Bordelon, Niklas Muennighoff, Man- sheej Paul, Cengiz Pehlevan, Christopher Ré, and Aditi Raghunathan. Scaling laws for precision. arXiv preprint ar 2tt.:22111.043300 2024.
Katherine Lee, Daphne Ippolito. Andrew Nystrom, Chiyuan Zhang, Douglas Eck, Chris Callison- Burch, and Nicholas Carlini. Deduplicating training data makes language models better. arXiv preprint N.Xiv:2107.06499 2021.
Binghui Li, Fengling Chen, Zixun Huang, Lean Wang, and Lei Wu. Functional scaling laws in kernel regression: Loss dynamies and learning rate schedules. arXiv preprint 2rXiv:2509.19/89 2025a.
Binghui Li, Kaifei Wang, Han Zhong, Pinyan Lu, and Liwei Wang. Muon in associative memory learning: Training dynamics and scaling laws. arXiv preprint arXiv:2602.05725, 2026a.
Binghui Li, Zilin Wang, Fengling Chen, Shiyang Zhao, Ruiheng Zheng, and Lei Wu. Optimal learning-rate schedules under functional scaling laws: Power decay and warmup-stable-decay arXiv preprint 20X1:26002.06777 2026b.
12

---

Published as a conference paper at ICLR 2026
Houyi Li, Wenzhen Zheng, Jingcheng Hu, Qiufeng Wang. Hanshan Zhang, Zili Wang, Shijie Xuyang. Yuantao Fan, Shuigeng Zhou, Xiangyu Zhang, and Daxin Jiang. Predictable scale: Part 1 optimal hyperparameter scaling law in large language model pretraining, 2025b. URL
https: /tt:://axiv.../ www.iioorg/e..ee.e........oooowe
04715.
Xuheng Li and Quanquan Gu. Understanding sgd with exponential moving average: A case study in linear regression. arXiv preprint wwXiv:2502.14122 2025.
Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods, 2019. URL https:tt//// /taxiviiviv..///.a//eea/eeaaaala org/ /0bb/16055 08882.
Licong Lin, Jingfeng Wu, Sham M Kakade, Peter L Bartlett, and Jason Lee. Scaling laws in linear regression: Compute, parameters, and data. arXiv preprinl arXiv:2406.0884 2024.
Licong Lin, Jingfeng Wu, and Peter L Bartlett. Improved scaling laws in linear regression via data reuse. arXiv preprint arXiv:2506.08411 2025.
Kairong Luo, Haodong Wen, Shengding Hu, Zhenbo Sun, Zhiyuan Liu, Maosong Sun, Kaifeng Lyu, and Wenguang Chen. A multi-power law for loss curve prediction across learning rate schedules. arXiv preprint arXiv:2503. 2025.
Alexander Maloney, Daniel A Roberts, and James Sully. A solvable model of neural scaling laws. arXiv preprint arXiv:22 /6859, 2022.
Alexandru Meterez, Depen Morwani, Costin-Andrei Oncescu, Jingfeng Wu, Cengiz Pehlevan, and Sham Kakade. A simplified analysis of sgd for linear regression with weight averaging. arXiv preprint arXiv:2506. 10000.1553. 15535, 2025.
Eric Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The quantization model of neural scaling. Advances in Neural Information Processing Systems, 36, 2024.
Niklas Muennighoff, Alexander Rush, Boaz Barak, Teven Le Scao, Nouamane Tazi, Aleksandra Piktus, Sampo Pyysalo, Thomas Wolf, and Colin A Raffel. Scaling data-constrained language models. Advances in Neural Information Processing Systems, 14.50358-503777 2023.
Yoonsoo Nam, Nayara Fonseca, Seok Hyeong Lee, and Ard Louis. An exactly solvable model for emergence and scaling laws. urXiv preprint arXiv:2404. 17563, 2024.
Gergely Neu and Lorenzo Rosasco. Iterate averaging as regularization for stochastic gradient descent. In Conference On Learning Theory, pp. 3222 22222.22..22 PMLR, 2018.
Elliot Paquette, Courtney Paquette, Lechao Xiao, and Jeffrey Pennington. 4+3 phases of compute- optimal neural scaling laws, 2025. URL https: //tp:v////xii/////a http:///...////aaaa...ra////////
15074.
Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes, 2018. URL https:// arxiv. wrw. abs 805. 10074.
Qwen, An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang. Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang. Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu, Rui Men, Runji Lin, Tianhao Li, Tianyi Tang, Tingyu Xia, Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su. Yichang Zhang, Yu Wan, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. Qwen2.5 technical report, 2025. URL https: /tass///rrivvi org/ alss /2412. 151115..
Utkarsh Sharma and Jared Kaplan. A neural scaling law from the dimension of the data manifold, 2020. URL https: http://xxvvvv////////.// org abs 2004.10802.
Xian Shuai, Yiding Wang, Yimeng Wu, Xin Jiang, and Xiaozhe Ren. Scaling law for language models training considering batch size. arXiv preprint 202055241..01505, 2024.
Ross Taylor, Marcin Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic. Galactica: A large language model for science. arXiv preprint 2r .09085, 2022.
13

---

Published as a conference paper at ICLR 2026
Howe Tissue, Venus Wang, and Lu Wang. Scaling law with learning rate annealing, arXiv preprint arXiv:2408. 11029, 2024.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXhv:2307.09288 2023.
Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389-43 434, 2012.
Roman Vershynin. Cambridge University Press, 2018.
Probability: An Introduction with Applications in Data Science.
Pablo Villalobos, Anson Ho, Jaime Sevilla, Tamay Besiroglu, Lennart Heim, and Marius Hobbhahn. Will we run out of data? limits of IIm scaling based on human- -eenanneeeertted data, 2024.
Jinbo Wang, Binghui Li, Zhanpeng Zhou, Mingze Wang, Yuxuan Sun, Jiaqi Zhang, Xunliang Cai, and Lei Wu. Fast catch-up. late switching: Optimal batch size scheduling via functional scaling laws. arXiv preprint arXiv:2602. 14208, 2026.
Peihao Wang, Rameswar Panda, and Zhangyang Wang. Data efficient neural scaling law via model reusing. In International Conference Machine Learning, pp. 36119-336204 PMLR, 2023.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize. In International Conference on Machine Learning, pp. 23549-23588, PMLR, 2022.
Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression, 2022a. URL org/ alss 2110.0111.2 61998
petpss//arxarr
Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. The power and limitation of pretraining finetuning geeeuunnnn--nnetunnnng for linear regression under covariate shift, 2022b. URL
https: / arxiv, org/ abs 2208 01857.
Zhangjie Xia, Chi-Hua Wang, and Guang Cheng. Data deletion for linear regression with noisy sgd. arXiv preprint arXiv:2410.09311, 2024.
Fuzhao Xue, Yao Fu, Wangchunshu Zhou, Zangwei Zheng, and Yang You. To repeat or not to repeat: Insights from scaling I1m under token-crisis. Advances Neural Information Processing Systems, 36:59304-59331 2023.
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, Jian Yang. Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang. Jing Zhou, Jingren Zhou, Junyang Lin, Kai Dang. Keqin Bao, Kexin Yang, Le Yu, Lianghao Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang, Qin Zhu, Rui Men, Ruize Gao, Shixuan Liu, Shuang Luo, Tianhao Li, Tianyi Tang, Wenbiao Yin, Xingzhang Ren, Xinyu Wang. Xinyu Zhang. Xuancheng Ren, Yang Fan, Yang Su. Yichang Zhang, Yinger Zhang, Yu Wan, Yuqiong Liu, Zekun Wang, Zeyu Cui, Zhenru Zhang Zhipeng Zhou, and Zihan Qiu. Qwen3 technical report. arXiv preprint arXiv:2505 09388, 2025.
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transformers. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 12104-12113, 2022.
Hanlin Zhang, Depen Morwani, Nikhil Vyas, Jingfeng Wu, Difan Zou, Udaya Ghai, Dean Foster, and Sham Kakade, How does critical batch size scale in pre-trainings arXiv preprint arXiv:2410.2166. 2024.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfitting of constant-steps snttsintsttessie sgd for linear regression. In Conference on Learning Theory, pp. 4633-4635. PMLR, 2021.
14

---

Published as a conference paper at ICLR 2026
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean P. Foster, and Sham M. Kakade. The benefits of implicit regularization from sgd in least squares problems, 2022. URL httpa: //arxiv.... org/ abs /2108 04552.
Nicolas Zucchet, Francesco d' Angelo, Andrew K Lampinen, and Stephanie CY Chan. The emer- gence of sparse attention: impact of data distribution and benefits of repetition. arXiv preprini wrXiv:2505.17863, 2025.
15

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
2 Related Work
3 Preliminaries
4 Multi-Epoch Scaling in Strongly Convex Linear Regression
4.1 Main Results
4.2 Proof Sketch
5
A Solvable Case with Zipf-distributed Data
5.1 Results on Power-Law Spectrum
5.2 Results Logarithmic Power-law Spectrum
6
Experiments
6.1
Simulations in Section
6.2
Simulations in Section 5.1
6.3 Empirical Validation on Large Language Models
7
Conclusion
10
A The Use of Large Language Models (LLMs)
18
B Additional Related Works
18
C Additional Experimental Details for LLM Training
19
C.1 Pretraining Setup
19
C.2 Fitting Experiments
19
C,3 Experiments with WSD Learning Rate Schedule
20
Additional Results and Simulations for Logarithmic Power-Law Spectrum
20
D.1 Scaling Law for Logarithmic Power-Law Spectrum
20
D.2 Simulations in Section 5.2
21
E Additional Notations
21
Proof Outline in Strongly Convex Linear Regression
22
G Proof of Main Results in Strongly Convex Linear Regression
22
G.1 Step I: A Concrete Version of Bias- Variance Decomposition
22
G.2 Step II: Risk Approximation and Error Bound Analysis
23
G.2.1 Variance Term Analysis: Proof of Lemma G.2
24
16

---

Published as a conference paper at ICLR 2026
G.2.2
Bias Term Analysis: Proof of Lemma G.3
31
G.3 Step III: Narrowing the Range for Optimal Learning Rate
34
G.3.1
A description of the Range of Optimal Learning Rate, Small-K Case
35
G.3.2
A description the Range of Optimal Learning Rate, Large-K Case
36
G.3.3
An Approximation of the Excess Risk, Small-K Case
37
G.3.4
An Approximation the Excess Risk, Large- Case
38
G.4 Step IV: Deriving the Approximately Optimal Learning Rate, Proof of Lemma 4.4
39
G.4.1 Proof of Lemma 4.4, small K
39
G.4.2 Proof of Lemma 4.4, large K
40
G.5
Proof of Theorem 4.1
40
G.6 Proof of Theorem 4.2
42
Proof Outline for the Solvable Case with Zipf-distributed Data
I
Proof of Main Results for the Solvable Case with Zipf-distributed Data
44
L1
A Closed Formula for the Excess Risk: Proof of Lemma
45
I.2
Scaling Laws for Power-Law Spectrum: Proof of Theorem 5.1
46
1,2.1
Proof of Theorem 5.1: Small-K Case
46
1.2.2
Proof of Theorem 5.1: Large-K Case
50
1.3
N) for Power-Law Spectrum: Proof Theorem 5.2
1.3.1
Proof of Theorem 5.2, small-K case
51
I.3.2
Proof Theorem 5.2, Large-K Case
52
1.4
Scaling Laws for Logarithmic Power-Law Spectrum: Proof of Theorem D.1
53
1.4.1
Proof of Theorem D.1: Small-K Case
53
I.4.2
Proof of Theorem D.1, Large-K K case
57
1.5
E) for Logarithmic Power-Law Spectrum: Proof of Theorem 5.3
58
I.5.1
Proof of Theorem 5.3, Small-K Case
58
1.5.2
Proof of Theorem 5.3, Large-K Case
58
J
Additional Technical lemmas
59
Theoretical Analysis under Learning Rate Decay
65
K.1 Problem Setup........
65
K.2 Sub-Optimality of One-Pass Training
65
K.3 Optimality of Multi-Epoch Training
65
17

---

Published as a conference paper at ICLR 2026
A THE USE OF LARGE LANGUAGE MODELS (LLMS)
In this paper, we use LLMs (mainly GPT-5 series) to polish some of the sections in our paper, and to check the grammatical issues. Besides that, we use LLMs to debug our code in LLM experiments (Section 6.3) and simulation experiments for Section 4 and Section 5. Also. LLMs are used to help improve the plotting scripts.
B ADDITIONAL RELATED WORKS
Data Reuse in Synthetie Setting. Besides the real-world LLM pre- vee-training regime, many works also reported the improvement of data reusing under synthetic settings empirically (Charton & 2024; Kazdan et al., 2024) or theoretically (Zucchet et al., 2025; Dandi et al., 2024; Arnaboldi et al., 2025).
Kempe,
Empirical Findings on Scaling Laws. Scaling laws reveal the relationships between large-scale model training loss and various factors such model size, data size, and compute budget. These laws were initially observed by Hestness et al. (2017), , but gained significant influence through the work of Kaplan al. (2020), and have since been further developed in series of studies (Henighan et al., 2020; Hoffmann et al., 2022: Zhai et al., 2022; Kadra et al., 2023; Aghajanyan et al., 2023; Muennighoff al., 2023; Bi al., 2024; Shuai al., 2024; Kumar al., 2024; Tissue al., 2024; Luo et al., 2025). Notably. Muennighoff et al. (2023) further refined these models by incorporating the number of training epochs into a more complex scaling law, which empirically describes the effect of data reuse. In our work, we provide a theoretical analysis of how the effective reuse rate E(K, N) relies on the epoch number K and fresh data size N. highlighting the role of N in the factor that was overlooked in Muennighoff et al. (2023).
scaling behavior of (KK,N)
Theoretical Explanations for Scaling Laws. A series of studies (Sharma & Kaplan, 2020; Hutter, 2021; Maloney et al., 2022; Wei et al., 2022; Jain et al., 2024; Michaud et al., 2024; Nam et al., 2024; Atanasov et al., 2024; Dohmatob et al., 2024; Bahri et al., 2024; Bordelon et al., 2024a; Lin et al., 2024; Paquette et al., 2025; Bordelon et al., 2024b; Zhang al., 2024; Ferbach et al., 2025; Li et al., 2025a; 2026a;b; Wang et al., 2026) have sought to theoretically explain scaling laws from various perspectives. Among these, recent works (Bordelon al., 2024a; Paquette et al., 2025; Lin et al., 2024; Bordelon et al., 2024b) have analyzed scaling laws by tracking the training dynamics of SGD through linear regression setup. Specifically, Bordelon al. (2024a) investigated full-batch gradient flow setup, while Paquette et al. (2025) and Bordelon et al. (2024b) focused on online SGD with a sufficiently small constant learning rate. Additionally, Lin et al. (2024) studied a geometric decaying learning rate schedule (LRS) (Ge et al., 2019; Wu et al., 2022a). Recently, Li et al. (2025a) proposed a functional scaling law that characterizes the loss dynamics for general LRSs. However, these scaling law studies did not account for the impact of data reuse. In contrast, our work examines the scaling behavior of multi-epoch SGD training within the context a linear regression setup.
SGD Analysis in Linear Regression. The analysis of SGD in linear regression has been extensively studied over the years, encompassing both one-pass and multi-epoch SGD. In the context of one- pae-pass SGD, Zou et al. (2021); Meterez et al. (2025) considered an SGD procedure with constant step size and averaged iterates, offering a sharp risk bound in terms of the eigenvalues of the covariance matrix. Gurbuzbalaban et al. (2021) examined one-pass SGD with batch size and proved that the distribution of the SGD iterates will converge to a heavy-tailed stationary distribution. Zou et al. (2022) compared the performance of SGD in the absence of ridge regression. Wu et al. (2022a) and Wu al. (2022b) studied SGD in linear regression under covariate shift. Xia et al. (2024) considered SGD updates with noisy gradient and analyzed the perfect deleted point problem. Li & Gu (2025) considered SGD with exponential moving average in the linear regression setting. For multi-epoch SGD, Lin & Rosasco (2019) examined a scenario in which gradients are sampled uniformly at random and mini-batches are allowed. They analyzed the effects of mini-batch size, number of epochs, and learning rate, carefully combining these parameters to achieve the optimal convergence rate. Pillaud- Fillied-Vivien et al. (2018) showed that while single-pass averaged SGD is optimal for a certain class of "easy" problems, multiple passes are required to achieve optimal prediction performance on a different class of "hard" problems, provided that appropriate step size is chosen. In contrast to the matching upper and lower bounds derived by our theory, however, all the above works were only able to derive an upper bound for the loss.
18

---

Published as a conference paper at ICLR 2026
C ADDITIONAL EXPERIMENTAL DETAILS FOR LLM TRAINING
C.I PRETRAINING SETUP
In our pretraining experiments, we employ the AdamW optimizer with a weight decay 0.1 and a gradient clip of 1.0. We set the peak learning rate to 0.001, aligning with the approximate optimal learning rate reported by Li et al. (2025b). Balancing the optimal batch size suggested by Li et al. (2025b) with training efficiency, roughly 0.5M data points per batch. We adopt the vocabulary of Qwen2.5 (Qwen et al., 2025) models. Our pretraining model consists of approximately 117 million non-embedding parameters, consistent with the methodology of Kaplan et al. (2020), and total of 331 million parameters following the convention of Hoffmann et al. (2022). The detailed hyperparameter configurations are presented in Table 2, and the model architecture specifications are provided in Table 1. To ensure a fair comparison by eliminating the influence of batch order variations, we fix the random seed that governs the data stream across all experiments.
utilize sequence batch size of 128, which corresponds to
Table 1: Model configurations and parameter counts. d,: hidden dimension; dy: feed-forward dimension; nyt number of Transformer layers; n& number of attention heads; 0k= number of key- value heads (for grouped-query attention); Vocab Size: size of tokenizer vocabulary; #NE params: number of non-embedding parameters (in millions); #Params: total number of model parameters (in millions).
Name
dj
n1.
Th
Tkky
Vocab Size
#NE params
#Params
0.5B
896
4864
24
14
2
151936
355
491
0.3B
640
3328
16
10
2
151936
117
331
Table 2: LLM Experiment Settings
Parameter
Value
Data
Sequence Batch Size
128
Sequence Length
4096
Learning Rate
Peak Learning Rate
0.001
Schedule
Constant
Warmup Steps
400
Optimizer
Optimizer
A
Weight Decay
0.1
31
0.9
82
0.95
1e-8
Gradient Clip
1.0
C.2 FITTING EXPERIMENTS
To provide real-world evidence that larger datasets can repeated more, we show how the saturation points can be used to determine the appropriate number of training epochs. Recall that the saturation points are the points at which multi-epoch training first starts to underperform the one-pass base- line. We estimate these points from the pretraining loss curves presented in Section 6.3 and fit its dependence on N.
To estimate this quantity from the training curves, proceed follows. First, to reduce the impact of noise, we smooth the loss curves with exponential moving average (EMA) with decay coefficient 0.9 and window size of 3 checkpoints. Then for each dataset size N, examine the ratio
19

---

Published as a conference paper at ICLR 2026
Fit: y 2.35 log 5.25 r= 0.96
Saturation Points
5
6x 10
10
2 10
Fresh Data Size(B)
Figure 3:
The saturation points (A,, N) as function of the data size N under a WSD learning rate schedule with linear decay.
E(K, N)/K. A larger ratio requires multi-epoch training to remain very close to the one-pass baseline, whereas smaller ratio allows more deviation. Next, given threshold hyperparameter X, we identify the closest epoch K at which this ratio first falls below X, which we denote as K (A, N). Here we choose À 0.75, and we define K (X,, .N as the saturation point.
We fit those points and find that K (AA,N .N s 0.80 log N + 5.21 with a correlation coefficient of 0.97. The fitting results are shown in Figure lc.
C.3 EXPERIMENTS WITH WSD LEARNING RATE SCHEDULE
Next, to make our LLM experiments more consistent with real-world pretraining practices, we repeat the LILM experiments under a warmup-stable-deent (eepssaabbbbedeyyWWWW))) learning rate schedule.
Concretely, we start from the checkpoints obtained in Section 6.3 for fresh data sizes N E {0.2B, 0.5B, IB, 2B} after K (2,4, 4, 16] epochs of pretraining with a constant learning rate of 10-3, From each checkpoint, ing the learning rate from 10-3 to 10 resulting in a WSD learning rate schedule followed by linear decay. For the one-pass baseline, adopt the same schedule as in the N 2B run.
continue training for one additional epoch while linearly decay-
For each dataset size N, this process produces set of four validation values, each associated with of the four selected epoch numbers K. We model the dependence of the final loss the training steps & using the parametric form {(x) = A + ==* where A, B, a are fitted parameters. The fitted curves are then used to predict the final validation loss under this WSD schedule for arbitrary training budgets. Using these predictions, we compute the saturation points following the same procedure in Section 6.3. Here we still choose 0.75.
B
The resulting saturation points are summarized in Figure 3. We observe that, even under this different learning rate schedule, the saturation points still satisfy the logarithmic scaling (A,, N) O N). Specifically, we have K N) x 2.35 log N + 5.25 with correlation coefficient of r = 0.96. This confirms that our message that larger datasets can be repeated more also holds for real L.L. training setups.
D ADDITIONAL RESULTS AND SIMULATIONS FOR LOGARITHMIC POWER-LAW SPECTRUM
D. SCALING LAW FOR LOGARITHMIC POWER-LAW SPECTRUM
We now present the scaling law for logarithmic power-law spectrum. Its proof can be seen in Section 1.4.
20

---

Published as a conference paper at ICLR 2026
Log Spectrum: E(K, N)
Log Spectrum: E(K, log(N)
K=2
E(K. (M
104
5=
K=525
10a
10
K=1000
5=5*10
EIK, N) 0.276-10ggN)200
N N=1*10*
5 10
= 1 10
10
10
10
102
10a
10
11 log(N)
12
13
14
K
Figure The solvable cases with logarithmic power-law spectrum. E(K, N) exhibits a simi- lar behavior to that presented in Figure 2. We also fit the effective reuse rate using the formula E(K,N) = с1 (log suggested by Theorem 5.3, and the fitted exponent Co 2 x b matches our theory.
Theorem D.1. Consider a K K-epoch SGD over N fresh data. Under Assumptions 5.1, Assumption 5.3, and given the data dimension d = ([(KN)& it holds that
(KN) ==1
for K = =(log" N) a-1
(K, = (N N)
for K = w(log" N).
D.2 SIMULATIONS IN SECTION 5.2
Now we focus on validating the predictions of Theorem 5.3 using synthetic data generated under the spectral assumptions of Section and log-power decay spectrum (Assumption 5.3).
Experiments Setup. Similar to Section 6.2, in all sub-figures of Figure 4, we set the data dimension to 10" and tune all the learning rates to their optimal values. Here we a 1.5 and b 2.
Simulations for the Solvable Model. Figure 4 plots E(K, N)) versus K and log N for the solvable model. The curves depicting F N) versus and E K, N) versus log N show trends consistent with those in Section 6.2, aligning with Theorem 5.3. Furthermore, in the large-K regime, we fit the exponent according to Theorem 5.3 and obtain 2.036 = 2, which provides strong validation of our theory.
E ADDITIONAL NOTATIONS
In this section, we provide some additional notations appeared the following proof our main results.
Key Quantities.
We define the following key quantities to analyze the sequential updates. For each
epoch k let
(
II (I n (1)
(1)
i=N-1
represent the product of sequential updates through all samples epoch k. More generally, we define the partial product operator:
z
a-45
(k)
180
(1)
with ( (k)
N-1-00'
t=
21

---

Published as a conference paper at ICLR 2026
We further define that Z - 1- -
I. The cumulative effect across epochs is captured by:
k+1
T
II A and T(K) I. k=
Pseudo-expectation Notation E. Because matrix multiplication is non-commutative and the shuf- fling in training introduces statistical dependence, the expectations of the random matrices defined above cannot be written in a tractable closed form. To approximate the population excess risk, we therefore introduce the auxiliary notation E. By construction, E computes the expectation of each factor as if the variables were independent, deliberately neglecting the correlations. We then invoke conrii-concentration inequalities to bound the gap between this "pseudo" "expudddt-xtctttionn and the true expectation of the original dependent random variables. Specifically, for the above random matrices used in our proof, here we further define that
a-6 == (I - H) a-b+1 !
(2)
EA(R) (R) ;= -1
(3)
M(K -k) ËT(k) =III (H
(4)
(s(()) -((2(0) N- N-1-x77 (0+1) Baanan E Z [
F PROOF OUTLINE IN STRONGLY CONVEX LINEAR REGRESSION
In this section, we give the outline of Lemma G. Lemma 4.4, and Theorem 4.2. The main technical challenges and our proof insights are briefly stated Section 4.2.
Section 4 centres on Theorem 4.2, which establishes scaling law for the effective reuse rate E(K, N) terms of the relative magniudes of number of epochs K and dataset size N. Its proof unfolds in three stages.
An explicit approximation the expected excess risk. Lemma G.1 derives a sufficiently accu- rate asymptotic formula for the expected excess risk of multi-epoch SGD. The argument begins with a bias-variance decomposition, splitting the expected excess risk into a variance term (Lemma G.2)
and bias term (Lemma G.3).
Variance term. The closed-form approximation relies on concentration properties of matrix contractions together with a careful treatment of data shuffling.
Bias term. The same contraction inequality is employed to obtain an analytic expression, after which tight error bounds proved for the full range of relative sizes of K and N. These bounds hold uniformly over a broad class of learning rates, necessitating detailed case-by-case analysis.
Selection of nearly optimal learning rate. Lemma 4.4 identifies a learning rate whose resulting loss is asymptotically equivalent the minimum excess risk attained with the optimal learning rate as stated in Section This "approximately optimal learning rate" will be fixed in Appendix G.4.
Proof of the effective reuse rate scaling law. With the one-pass and multi-epoch SGD training learning rate set to the near-optimal learning rate obtained above, the proof of Theorem 4.2 proceeds to characterise the behaviour of E(K, .) as and N vary, yielding the desired scaling relation. Together, these three components establish Theorem 4.2 and provide comprehensive description of how reuse efficiency depends on the interplay between K and N.
G PROOF OF MAIN RESULTS IN STRONGLY CONVEX LINEAR REGRESSION
G.1 STEP I: A CONCRETE VERSION BIAS- VARIANCE DECOMPOSITION
Before we begin our proof, we first present the following lemma, which provides the formal version of the loss estimate for specific range of learning rate parameters. We define R(K,, N, as the
22

---

Published as a conference paper at ICLR 2026
estimator of R(K,N;
Ř(K, N:n) = (.( + N: + NN,
bias term
vor term across spochs
var terme wittlen epoch
where
(K, N:n) = (20 = (1-)((1-1)) H(wo -w=),
0²
( (I (1- (I-(I- ) ((I ,H - -I (1-nH))RM)
R2(K, N:1) N
I+ (I -
Rg(K, = no²
2 - -1-
G.2 STEP II: RISK APPROXIMATION AND ERROR BOUND ANALYSIS
In this section, we rigorously formulate the analytic risk approximation in Lemma G.I and provide its proof. Lemma G. indicates that the error bound is of higher order than the main term when the parameters are restricted to a limited range of values.
Lemma G.1. Under Assumption
and 4.3, we further assume that for every x in the training set, ||a=|| D for some constant D O. Consider K-epoch SGD) with learning rate yi (+) (+), ,((T=))) K = (n- and data shuffling. Then, after T KNN steps, the estimator
of the expected excess risk satisfies:
R(K,N:n)
(1+
Recall from Section 4.2 that the risk R(K,N:1) can be decomposed into the bias term R Rbius (K, NN == O|biass] H and variance term R Rar (K, N;n) := |0 H. which implies that Lemma G.I is a direct corollary of the following two lemmas:
Lemma G.2 (Variance Term). Suppose that Assumption 4. holds. Then for K- SGD with dataset size N and learning rate nj E [)(G), of )) and shuffling, when poly(T) Z d, we have the T2
estimator of the variance term var (K, N; == Ew- [R(w) after T = KN steps
(I HH) KN (I- N (I (I-nH)K HH)K
R var K, (K,N = tr
N
[+
1102
( nH)-1
where the expectation is taken on the training set and shuffle, and the estimate error is
R var K, N; RK, (K)N:)) = - VTog d).
when K <
log
1I dogg
Lemma G.3 (Bias Term). Under Assumption 4.1. a K Keepoch SGD with dataset size N, learning rate n and shuffling, when poly(T)) 2 d, we have the estimator of the bias term R bias (K, N; Euw-WKN... (R(w))baar bias] after T K N steps
1
R K. N:n)
2 5wm -
H - -w").
Then we have the following estimate errors:
1. When K 2 2 and K x=o (-
(log 8
23

---

Published as a conference paper at ICLR 2026
2log T. (a) When n S 3x, the estimate distance is given by
R (K, N;)) -R Riis (K, N) -o N2K K (V12KN)
(b) When 17 2 3x,
2log the estimate distance is given by
R hins (K, N;)) - R bias (K, N;n) =0 T
When K 1:
R R bias (1,T; R bias (1, (1)) 0 (112T -2A0T))
G.2.1 VARIANCE TERM ANALYSIS: PROOF OF LEMMA G.2
We first recall some notations Appendix E that z _ 11 i= (1 1 x1) m1)) ((k)
Eiog (k) ity, and it does not cause confusion, we omit the superscript "var" in all the training parameters
N NN-1-t+1Sm2(7) ( (
(k)
N N 1-10 T(() = II k+1 A and T = I. For simplic-
@var in the proof of Lemma G.2. Now we derive the recursion before and after the k-th epoch.
O&N = (I 1p x (2(--)) OKN-I + IBR - (N--1)
N-1
17
Z
(K)
-11-+4115 (1)
A (K-1))
1=0
nb (k)
+ A (k) 1(x 1)-1): 1)N:
where (i) is the i-th index after the permutation Tye in the K-th epoch. Further writing out the above recursion gives the parameter after K epochs
((K) (*+
OKN- = 1 A=1
A natural move here is to replace 0KN with the expression above in the variance term
1 okx
1 1E
R var (K, N; = E
HOKN KN
H, OKNOKN)
1 E
H.
Σ
Σ
g()
(BOI) T
(TTS)))
2
(NI)
x,j=1
1/ 1²00 E
K
N-1
(T(S))T 7
H.
Σ
Σ
T
Σ ((1))
(T(S))
2
(N!)
f-==1
1=0
02
1
K
T
N-1
Σ s((0)) (TTS))
2
(N!)K
1=0
except Tely
o222
E
H.
K Σ
Σ K
N-1
Σ
S((i)
(TT))
(6)
2
(NI)
TTL
1=0
except
where in the third equation, we take expectations with respect to the label noise(Ei) N-1 and in the last equation, we decompose the variance term into two parts, according to whether the (i) and bQ) are from the same epoch or not.
After explicitly writing the variance term, and to get a close-form formula for it, we then take pseudo expectations of T()) TU), s((i) and 5(()) separately to get the approximation of R (K, N;
24

---

Published as a conference paper at ICLR 2026
given follows:
12002
N
R (K, N;,)
Σ
ET
Σ
Σ
ETO
(N!)²
i
1=
minmy
1,==1
02202 + 2
N-1
E
H
(T()
Σ
Σ
Es (i))
BT
N
I=0
The intuition of the "pseudo expectation" and the related definitions are in Appendix E. Fix I, notice that when + j. by Equation (5),
Σ ES Kii
Σ Fi
E
Z (0)
. Z N-
(1)+1
(1)+1-N-1
Σ Ti
(I
HH
1-110 (1) (I nH N-1-5,
For a fixed i, for all m E [0, N 1]. there are (N - 1)! permutations n, that satisfies my (m( = I. So
N-1
Σ ES = ((N- 1)1)
Σ
nI- N- (I ( N-1n
m,
By applying similar derivation to the j case, we obtain that
N-1
ΣES(" (N 1)!
Σ (I- (H-
N N-1 H H1 nH N-1-m
mHH
(8)
m=0
Plugging Equation (7) and Equation (8) into the expression of R (K, ni), and we have
R
(K, n)
2
K
N-1 N-1
(
(i)
Σ
Σ
(I (I-n
22-2 m- H (T(
2
N2
1=0 m.n=0
K
N
1f
E
H.
ET
Σ (I (1-ntt 2H- H ET(
2
N
i=1
1=0 m=
0
E
H
H
M(K-i)
(I- H ( N(K-))
2
N
:=
K
1102
E
H.
II - nH N(K-1)
nHu ( (2I nH) N(K-N
where the second equation uses Equation (4), The quantity v accounts for the variance term across different epochs and T Then we calculate V, and Vr, separately. For V1, we have
K (I
V
H
Σ
TH HH) N(K-i) (I- (I- H H
H THH N(K-))
2
N
i.j=1
02
K
Σ [I
HH N(K-i) (I (I- (1)
H H- ( N(K-1)
2
N
i=1
25

---

Published as a conference paper at ICLR 2026
9²
H 1
(T- mH))K
2 H- ( (I- -1-(1- - -)tn)t))) 2
2
N
[ -1-1)) ) (1-0)((11)0 (1-(2))1)) (1----))""
(
H
2N
(1=(IInHt)*N))) kk))
2N
2²
(I (I- (I-((
(I- (1-(1-nH1)2a))) m)tt)(k())
tr
2N
d²
(I+ (u--H))-
N ir
The last equation is obtained by direct algebraic calculation. For W2 by direct matrix calculation, we
get
V E (1)) (I- (I-((-n)))aaNN))
n7²² 2
Next we obtain the error bound for R (K; R var Rv,,K, which can be represented as
Raa (K N::)
Rar (K, N:n)
02
2 E
H,
1
Σ
Σ
T
Σ
N-1
Σ
s(())
(mIST) )
(N!)&
itf
3.j | excepi Teittyy
1200
E
H
Σ
(I-
(I-nH)N(--) N(K-i)
ΣΣ
Σ
EES {5) (1))
(I- nH) (I-nH) H--H)M(R- M(K-)) )
=1
(N!)²
1=0 RErTH
11 0
E
H.
1
K
Σ
(
N-1
((i))
(I!:))
2
(NI)
TIOEK K
1=0
except Iy.
17002 E
H
1 N!
K C
NN-1 ΣΣ 1=0
ES( (i)
(I (I-NH)
)/ I2.
=1122
where the first inequality uses the triangle inequality. The term /1 represents the error term between epochs, and In represents the error term within one epoch. We will bound Iı and In separately in the proof.
Upper bound for 4. To bound 4, a natural move here is to plug in a term that takes pscudo expectation over (T()) two terms.
K 1= but does not take pseudo expectation over (s
((t)) Drng. and divide 7, into
K
(T
1
1
E
H.
Σ
Σ s((i)
2
(N!)
1=0
i
except n..
12002 E
K Σ
H.
(I-nH) N(K-
Σ
Σ
s(1i
(I- nH ((KK)
2
(N!)²
(*)
1=0
+
120
E
H.
1
Σ
k
(I-
(I-nH)
Σ
S (i
(I - H- N(K-1)
2
(N!)²
2
1=0
$5=1
26

---

Published as a conference paper at ICLR 2026
1/0²2
K Σ
N-1
E
H
1I
H
N(K-1)
Σ Es((0)
(1 (1- (-
2
(N!)²
(+)
fJ=1
41 + 112-
Next we bound the terms 111 and L12 separately, Notice that
N
Σ Ki =1 excopt 5,
(1
Σ
Σ
s(())
(I - (HHHH)N
1=0
K (H
N N-1
= (N!)
N(K-N
Σ s(1))
(I (I- (H) H-))H)((K-) N(K-))
1=0
because the summands do not depend on the permutations except ny, Ty. plugging Equation (9) into the expression of I we have
In
S
0
2 E
H
K
Σ
TO Σ
Σ 1=0
N
s((i)
(T(S))
2
(N!)
i i
except fissfy
11 01202
K
Σ
(I- HH N(K-)) N(K-))
Σ
N
s((i)
(I nH) M(K NH)N
2
(N!)
i (J=1
M except Ti.ly
1=0
Then we use Equation (4) split 4n into three terms and by triangle inequality:
In
0 2
E2
H.
1
Σ
(TO.
ET())
Σ
Σ
s((i)
ËT
(N!)
Te,
1=0
i except 7i.
12002 E
H
Σ
ET
N-1
Σ s((i)
(T BT(T)
2
(N1)K
(+)
my TK except mi.
1=0
f.)
K
N
10000
E
H.
Σ
(T
ET (4)
Σ s(1i)
(I (IO -ET(E
2
(N!)K
(
mi Tg
1=0
except k..
Next, we use Lemma J.1 and the fact that s(())
S I to bound the matrix inner products:
1OONNDA((H
I1 S
Σ
E [E|TO
ËT +E [
ET (1)
2(N1)K-2
1 excepe J..oy
+ E ( BT
(
Br
27

---

Published as a conference paper at ICLR 2026
Notice that Lemma J.2 and Lemma J.5 implies that
E
T
ET
I (V8AnPNK + |EAI))
|EAD K
S (VONPNK +1)*
log 2 nVOAT
$ 2K 2K NK when K S
where 8Λ = C log d is the constant appeared in Lemma J.4, and Ö is some absolute constant. The second inequality uses the fact that ( (vOAn2NN + |EA|]) - ||EA| | motonously increases with ||EA|| ||. A similar approach combining Lemma J.2 and Lemma derives another concentration
inequality for (())
T BTO
I s (2KVONPNK))
log
when
K
Applying Cauchy-Schwerr Schwarz's inequality and the concentration inequalities for (T(:), we get that
1D In S
Σ
(B|ITo)
ET +E T ET
2(N1)K-2
1 excepe manny
$
+ -E T (F|IT))-BBOO))
1PO2NDPu(HH)
K
4KV + (2K (2K)
2
Our next step is to bound 112. We first make use of the fact that I - HH S I, and get that
s((0) -B.((5)) )
11002
K
112 <
EE
H.
Σ
2
(N!)²
itj
l=0
Recall that for a fixed i, for all m E [0, N 1). there are (N 1)! permutations that satisfies n; (m) 1. So
02
K
W-IN-IN-
112 <
EE
H.
Σ
(NN- 11)2 (Z HZ (
2
(N!)²
-+1-N N-1
1=0 m=0 n=0
1 ))
E 1 +1
HE
n+
Notice that
HZ
E2(" (1)
N- N-1+m+ HEZ (i)
N
1+1+1
1+1+NN1
n+1--N-1
Z
N- 1-m+11
EZ((1 (i)
N-N-1-m-
HEZ (i)
1+1-N-1 + EZ 1-1
H (1)
2+11-N-11
EZ(()
W-1-m++1
EZ(
EZ N-1-
H
1 EZ(3)
(1)
28

---

Published as a conference paper at ICLR 2026
Applying Lemma J.1 and using the fact that EZ (1)
1-mm+1 E I,
2
N
112 S
E
EE --
2N
1-m+1
f
EZ ()
x+ -+1-NN --
2+1-N-1
N 2- N-2
+ -- NN11 -11)
Z 1-1-mm+1
EZZ
m++1
-
EZ(
(2)
n+
m= n=0
Applying Cauchy-Schward incquality and Lemma J.4 gives
P H IN
112 I
2N2
Σ
Σ
E
N-1
EZ 1-1--++11
m==
fj=1
E
EZ ()
-+1--ー1
N- T-2N-1 N-
EZ +m+ 1²)² (z)
B
(
1+1--N- | ==
[
E
EZ(1)
1-m+1
m==00 #=0
11 12 H)
IN
K
N-2
N-2
Σ
Vo
Σ (VoNP(N-11
+
2N22
n=
6,=1
2-2
V 20 - -1
m=0 n=0
$ n 12 Vlogg r/ 222 NNN22oog logd when 17 ol
Upper bound for /z. We bound // using a similar technique as what we did for J, We first plug in a term that takes pseudo expectation over (T()) K for every and i, and decompose Iz into two terms:
i=1 but does not take pscudo expectation over s
I <
11
H
Σ
Σ
Σ
N-1
Σ
((i))
(
(Ti))) T
2
(NI)
m
1=0
except
1002
E
H.
1
K
I H N(K-i)
Σ
NN-1
S (1)
(I -I- (I-nH) M(K-1) M
2
N!
i=1
1=0
1202
K
N
E
H
(I
N(K-O) N(K-
1HH
Σ
((8)
(I nH) N(K-
N!
1202
E
H.
1
K
I
H
N(K-I)
N-1
Σ
Σ
E.S (1)
(I - H-C-
2
N
1=0
121 + 122.
Next bound the terms J2 and Tz2 separately. Notice that
K
N Σ
H Σ
N(K
(())
(I N(K-))
KT exoept n
T
t=0
29

---

Published as a conference paper at ICLR 2026
K -
N- Σ
(N!) K- -1 =
-
H)
N(K
S(i))
(I - H N(K-i)
)
i=1
T
1=0
because the summands do not depend the permutations except Ty. we have
T21
1/022
2
E
H
K
T
Σ
Σ 1=0
S
[i)
(T())
(N!)
K
i=1
mT TK TK excepl x;
020²
K
E
H.
Σ
(I
H N(K-)
N(K-i)
((ii)
(I - H (H-
(N!)
71 71 TK except R1
1=0
Then we use the fact that (T) = (I (HH) to split 121 into three terms:
121 <
0
2
E
H.
K
( - ET Σ
S (i))
(1 - (--HHN((--))
2
K
im
KiouTg TK exoept R;
1=0
1/ 1202 E
K Σ
NN11
H.
(I - ) N(K-1)
Σ
S (ii)
(T (TO)
2
(NI)
im
TT T K exceppt xi
1=0
N
+ H,
11
E
Σ
Σ
(T ET( (i)
Σ
Σ
s((0))
(T
2
(N!)
TI- 1=1
1m0
except mi
Next, we use Lemma 1.1 and the fact that 5 the concentration inequalities we derived for (i))
2 I to bound the matrix inner products, and apply
n²02'ND' 12 < 2(N1)K-1
Σ
EE (E|T ET(
+ T ( (T())
Ey Tx except W.
E T(() - ET
120 N H
4K VKNKKN (2KV 2 ")
2
Then we bound 122. Recall that I -
HHH S I, we get
0222
1 K
122 <
E
H
Σ S 1=0
ES (36)
2
N!
Recall that for fixed i, for all Ty (m) = I. So
[0, N 1). there are (N 1)! permutations n; that satisfies
In2 <
1202 E
H.
1
N-1N-1
Σ
Σ
(N - 1)!
NN-1-m+ HZ (
Z (0)
2
N!
1=0 m=0
EZ
HEZ
11
m+1-+-11
1200 E
1 K
N-1
N-2 Σ
H.
Σ
Σ
-
((Z-)-
-EZ(0 (2)
B-X-mmm+t H
2
N!
1=0
m=
30

---

Published as a conference paper at ICLR 2026
1 x-1-m=+
EZ (1)
+))++)))
N
Using Lemma J.4, we have
17 1 H
I
K
NN-2
122
E
N -W-1--m 1-1++1
EZ (2)
2N
N m
1=1
Am=0
I HII
HIN
Σ
20 - 1-m)
2N
2 N1 K log d when ol
Combining all the arguments above, we derive that
Ru (K,N: R (K,N:
< I1 + I12 + I21 + 122
C 12o² N H
4K 4KV + (2K (2KVPN)N ")
2
+ 0 K2 N logd 17 K2N log d) OOi logd)
= O N K3 Vlog d) when o
The above equation completes the proof.
G.2.2 BIAS TERM ANALYSIS: PROOF OF LEMMA G.3
For simplicity, and as we did in the proof of Lemma G.2, in this section we omit the superscript "bias" for all the training paramters @bias Analogous to the proof of Lemma G.2, we can derive the parameter recursion as
OAN = (I 1 (N a2 1N) 0KN-1
(I 11 TT (I) (1) 1N) 040 1--N)-
For the parameter after K Keepochs updates, we have
0kn = A (K) A = II
A 13) 0
1=K
We also have the approximation for the bias term
Rbias (K, N;n) = ( H, BOKN)
E 0 KN HOHN
OJ
E 1
II A
H
A
On
V=K
1 0
"A
H
(A())
Oo
2
V=K
1
0
((I
nH) KN H ((I
nH
KN
0
Rer (KNN))
31

---

Published as a conference paper at ICLR 2026
The estimate error can be given as
h hias (K 17) - R (K,
Ni
T
0
II A [=K
H
II
A (1)
0o
=0, 0
II V=K
EA (1)
EA
1
0o
2
2
-=K
|=K
E 0
II
A
|EA||*
K
11
A
|EAA| K
00
2
V=K
Y=K
+ 2
0
|EAI H
II A
[RA|
0
N=K
0.1l
(||A*
(EA)
+ E| | - (EEA(E)))
(10)
2
where the last equation uses the fact that |EA|| S 1. Next, discuss the approximation bound for the bias term in Equation (10), with different categorizations based on the range of K.
1. Under Assumption 4.1 and K =
NE (log N
(a) S
21og 3A,7"
We now verify that K =
|EA||
under given conditions. We have
nVT
|EA|| = (1 - -1aa) N
(1 naas) F 2 (1 - 1zAa)
2 log T
log (1-
2 37
1
=
e
3T
Ing
0
87
A
1
T
thus
EAA
T8 T
nTT
log
N (log N
Also, given =0
we obtain that
T log
T log
K o
The second equality uses log T = log N + log K Olog N). Now we use the results in Lemma J.5 and Lemma J.6, and then the estimated distance can be given as
R bias K, N;n)
R.bia (K, (K,N
H 1011| |101 (( < 2
(2220PNNK +1)
(V20MPNK |
+ -1) 1)(=1))
+2
[EA
SK
22
<
H
2 2K
+ 4K EA
2
[EA
EEA 2K -
K N
=
where the second inequality is by Lemma J.2.
32

---

Published as a conference paper at ICLR 2026
(b)
2log T 3A,
We have
R blas (k, N: -R R.blas (k, N; 17)
S R
blas (k: N:n) + RR bias (k., N:
bias (k, N; + R bias (ki, N;
2 3hd
Rhiae (k; N; Riaa (ki, N;
(k;
+ 2iR (k: N;n) Bx
< O (1EEAIJ K WNKNN
1 22x x
|0|| |
|
2
2lor 2A,7
log T
2KN
O (||EA]|2))
2 SA
37
N
0 T3
when K =
(log N)
where the first equality uses the fact that K =
|EA| nvT
when v
21og 3x27"
For the K = 1 case, which is equivalent to one-pass (OP) SGD, we derive different upper bound for bias term error. In this scenario, we have the update rule
0, aa )0.-1-
We can denote the covariance as B,, which is
B, =E0,0,
EEI 1, 00- 0,_ (I 12
B - n - B H +n E 0,-10,_100 a
(,,I) - (I- - hH + Ex, H) 10 1 H).
(11)
Since the bias term in the excess risk can be represented as
R (1,
(r)
We then get the lower and upper bounds for B., and derive the corresponding lower and upper bounds for the bias term in the excess risk. Lower bound. By Equation
(11), we get a lower bound of B,
BT ž (I nH)
nH
] .... n -
- -))
and
bias (1,T;
(H, (T)
2 (H, (I - -TH Bu mHH)T)
2
2 0 ((InTH)) H ((I - -TH)²) 0o.
Upper bound. By the recursion of B,, we have
B 1 (I (I- B ()) + 17 Eur w. Exy a 11 - H)
[I BI + +
Eu r- - wn
Eer
-H0 H
(I BI 7H) + " E Br-in t Eer [,1==00111100_0001.1
33

---

Published as a conference paper at ICLR 2026
Then, combining Assumption 4.1 and Lemma J.9 gives
B 1 (I + = (
0
H
3..
(I-n Bo - 2
Bi H) (1 (I-1 H,
and
(T) S ( Bo - Σ
H, B,) (I- H. H
1=0
We also have
B. $ (H, + 1 atr H (H, B.-1)
$ (1 - m)a) (H B B + 2/ H H, B
1( + atr( H )) 2N 1] (H, Bo)
e logl(A H -2am++ (H, Bo)
e 20anit (H, Bo)
I Cie Cie-2Aum 2damt (H, Bo)
and
(I ([-nH))(TTT-))) H, H = (I ( 2 2(T-1-1) H²)
< tr 2 (1 m/aaa" 2T 11-3
I (H2) 2 (T- 1oR(1
(H2) -2
I Cze 2T--11)))
So
T-1
H. < H (I- (I-
Bu (HH)) + + 12aa Σ
Gee
2Aari (H, Bb) Oze 21-0(T-1--) (H²)
1=0
= HH Bu - ) + T 22ay/
And finally we get
R bias (1,T;n)
(I- Ba m/H))
-o([-1)H) = =0 -2harff
G.3 STEP III: NARROWING THE RANGE FOR OPTIMAL LEARNING RATE
We recap that our goal is to derive the scaling law formula for strongly convex linear regression with multi-epoch SGD, and the formula of the effective reuse rate. Before start proof, first give a technical lemma below.
Lemma G.4. Given 7 E [w (+) o [ and define na to be the number of the minimal eigenvalue Da in H. then it holds that
PO 11 n2112 02 (03pp-22a7))(1+
d
1x1 -)x))2r = node (2 Σ
34

---

Published as a conference paper at ICLR 2026
Proof of Lemma G.4. For the first equation, for any A Ad, define pi A. > 1, then have
(1 (1-10 (1-12,) 2T exp (27 log(1 -)A,)) exp (27( + 011)
(L= -elo==o(xxpp-PX10
(12)
Since X & DD, we have
d-na
= ((ex((-2Xu7T)),
From Equation (12), we can also directly get the second equation, which completes the proof of Lemma G.4.
G.3.1 A DESCRIPTION OF THE RANGE OF OPTIMAL LEARNING RATE, SMALL-K CASE
Lemma G.5. Under the conditions in Lemma 4.4, and when K (log N). we have nf" 2' a alog J 31,77 T where the constant == D²ur(H) Xatr(HFa)
Proof. We first prove the upper bound. Given learning rate 7), Equation (6) gives
R(K, N;n) 2 var (K, N;n)
17 0²202
H,
K
Σ
Σ
N Σ 1=0
s((01
(T(SI)
T
2
(N!)
K
exoopt ST
1 1/002
K Σ
N-1 1
(TrC)) T)
E
H.
Σ
s(())
2
(NI)
K
T except W2
1=0
=:
For 1h, using the fact that (I - nxx T) > (I (1-111 ( we replace all the terms (I 1jox" T) with
(I I) thus we have lower bound for th1
17²02
N((N N((N-1)1) 1
11 2
H.
Σ $
Σ
(1- D22 (2)
Σ
(1
DDDj2NN22---EB "E(c"" (e:0 T1
2
(NI)
[ (T=mx)
mmn=0
x-=1
1202
H.
M (1 - (D- D)2 (1- m H
2ND4
i,f=1
0²
2ND ir H² 1
o²
(1 (1 N 2KN
H (1 (1 k))))))))))
2 Ir
1 my 122
a²
2 1 - (1
- DD2NN ((1 (D - (1 -1- (D-nD))))N))
ND tr
1+
For vi similar argument get its lower bound
4/2 > 0²02
H Σ (1 - n2 2N(( 1 (1 D2 2N
1 1 (1 D2)2
i=1
1102
(1 - 122222KN
1
(1 - 22
H.
1- (1 D22222 H
2D
1- (1 D2222
n (H²
(1 + o())
4D)
35

---

Published as a conference paper at ICLR 2026
Notice that from the above lower bound, when K ollog N), we have
R(K, N; 2 41 + 4/2
11 tre
2 20 N
(1+ (1+)(1))
4D2
n (
(1+
(13)
4D
Taking 1) > log T
and ( Aatr(H2) gives
log
R(K,N::)) 2
(1+)
4A4T
Now we recall that R*(K,N) R(K,N ((K,N; (1++
o²tr(H)) log T
SAaT (1 (1+) < ( log
(1 + o())
4haT
Thus we have that 17" < log T When
Next, we give the lower bound of 17"
T
log T DAT
we have that
1
log w
exp(-22aril))
) )= N:)K, (R
T2/3
The above equation shows 17'
log T 3
which completes the proof.
G.3.2 A DESCRIPTION OF THE RANGE OF OPTIMAL LEARNING RATE, LARGE- K CASE
Lemma G.6. Under the conditions in Lemma 4.4, and when K w (log N), we have 17" T
31,T (+))
Proof. The proof comprises of three parts. First, we prove that 17" 2 log we verify that 1/* S & for sufficiently large N. Finally, we refine the proof the second step and justify that 77" = o ( All proofs are carried out by contradiction. The method proceeds as follows: we take specific = 'y' and compute its loss, then prove that R R*(K,N R(K, Ni when N is sufficiently large if 17" does fall into some interval.
3A42 when large. Second,
First, by Equation (15), we have
o²d R(K,N:n') = 2N (1 + o()).
Then we begin our main part of the proof.
Proof Step 17" 2
log 3x,2"
We assume that 17"
log T 3
Observe that Riiss (K,N: decreases with 17. So
log T 3X,T
R'(K, N) 2 R
Rbias bias (K, 2 R
Rbias bias (K, N;
(wo w " nH 2T H H(ws w w0) o(1))
( (xx((=2ax())) (1 (1+
lox 3327
1
θ
T
N
36

---

Published as a conference paper at ICLR 2026
where the first equality is due to Lemma G.3, the second equality is due to Lemma G.4, and the last equality is due to Assumption 4.1.
Proof Step II: n² I oFtr(FAA)N- We assume that 77"
4DPd
4Dpd oAtr( By Equation (13), we have
)0²ur(HH²)
o²d
odd
N3, 2
4D2 (1+) >
N (1 + o(1) >
2N (1 + ((1),
which is a contradiction. A direct corollary is that (*(,NN) = R(K, N: o1))
R(K, N:n") = (w0 - w'
- "H" " (wo - -w")
25
0²
[I (I- KN) ((I -11" H) - (1 17- H))
+
tr
N
I I+ 11-1-1/H)
n²0²
+
(H, (I - (I - 17 H (2I -1j 17" (H)
2
0² (1 (1-
P0o)) {) - (f >,)
2
N 1+ 1 17
+ 17'
tr(H)
070²²
4 Σ
d
1a(1 - 7" X1) 2T + ((7)))
4
-=1
1 2
d 0² NN
N N1+c-No'M No + n²02
B2 exxp -2x T)
4 ((HH) (1 (1+
Proof Step III: n7" = 0 )
We assume that there exists a constant e >> 0 and a sequence (N+);= that satisfies N; + oo when i oc and 17" (N.) 2 N; for all i. As we only conduct our analysis on the sequence (N.) without loss of generality, we take (N,) = IN.
We define f(6) = Ei= 0² Itc-oa
-MA;
60² (rH). Then we have
0² d
d
dGe 6d
2 d
(1-e E 5
('())
4 A
Σ
Σo²
> 0 when ó > 0.
(1+e
e
4 i=1
(1 + c e-Ao2=
i=
1=1
So
f(e) > f(0) = o2d
2
and
R*(K,N) 1 (0)N)(1+001) 1 110(+ + +o()))
o²d
(1 + o()) R((,N:,)) 2N
which is contradiction.
G.3.3 AN APPROXIMATION OF THE EXCESS RISK, SMALL-K CASE
Lemma G.7. Let 03 = Ei (PO)) H PDP be the canonical form under similarity
of H. Under the conditions in Lemma 4.4, for learning rate E
log KN a log for constant
3
KN
(Pu(H) and K = o(log N). then we have the approximation of R(K, N; as a Xatr(H]]
R(K, N:n) M (K, NN:
M(K, N: = 2 0 exple (oxxp--2AaTT)-a-- H)r
4
where steps T = KNN
37

---

Published as a conference paper at ICLR 2026
Proof. From Lemma G.I, have that ((KK,N:) can be written as
o())), where R(K, N:n)
1 w
R(K, N:
(wo-
HH) 2T H w")
2
o²
- (1 KN) ((I 1H NM (I nH
k)) KN
tr
N
It (+-I-1H HH)
(H, (I- -I- -- (2I -1H)
d
0² (1-1)))*
Poo))\i( - -mAi)
2 1=1
N 1+ (1-
n0²
n7022
(r(H)
Σ
X₂ ) 0
4
i=1
02 Bddexpl-
e-paa(--)a -2aa1IT)
n10
ir(H)
(1 (1+ 0 |
M(K.N.)
2 B5deep(- 2Aait)) + no²
4 (r(H)
(1+)(1)),
(14)
M(K,N:)
where the second to last equation uses Lemma G.4 and the fact that 1y(1 -)a)) 0 OM((K,N N,;1)) 7 J) and the last equation uses the fact that when K o(log (), (
for 17
log T
N)
0 (M(T:n))
K,N
G.3.4 AN APPROXIMATION OF THE EXCESS RISK, LARGE-K CASE
Lemma G.8. Under the conditions in Lemma for
Tog 33,T
o ( and K = w (log N), we
have
N;R(K,N;,)) M(K, (1)+))))
1 M M(K, N:
- 2 explxexp(222.0 + ntr H 0² o²d
4
2N
where 83 =
dd Ei-d-net (PO)) and PDP is the canonical form under similarity of H.
Proof. Given K = O(v0.)), one can verify that
N 7 = 0.
lim KnZ==
lim N
N-500
N
So condition K (T- 8) is satisfied, thus by invoking Lemma G.1, we have R(K, N: R(K, (1 o(1))
Note that when = ) , for any i d]. we have
Xmn) - - 1
38

---

Published as a conference paper at ICLR 2026
Combining this with Lemma G.4, we have
R(K, N;
2 (wo
w
(1- H(W))HHHH - =w")
0²
(I- KN) ((1 - nHH -(1 - AH)
+
lr
N
I+
H, (I- -I- -II- ) (2I - -H)
2
0² (1-
po,)) {11 na:;)
2 1=1
N 1+ (1- - nA,
n702 d
+
tr tr(H)
Σ
1 - n111)² + +0 (1²)
4
i=1
Aa explp 22 + no² -o (r(H))
+ o²d
(1 (1+)(1)))
(15)
2N
M(K,Nst)
which concludes the proof.
G.4 STEP IV: DERIVING THE APPROXIMATELY OPTIMAL LEARNING RATE, PROOF OF LEMMA 4.4
The proof of Lemma 4.4 for the small-K case and large-K case follows a similar pattern. First, we minimize the aproximate excess risk obtained in Section G.3.3 and Section G.3.4. Then we conduct an error bound analysis and complete the proof.
G.4.1 PROOF OF LEMMA 4.4, SMALL K
Part Minimizing the Approximation of the Excess Risk
Lemma G.9. Under Assumption 4. and 4.3, we consider K-epoch SGD with N fresh data and loo alogT), where steps T := KN and is some constant learning rate 7) satisfying 1) L3ATT independent T, but can depend on and Xı, .2,....,Ad Then when K o (log N), the chosen of learning rate T/' 2x. = arg min me(
M(K, N;r).
Proof. Given Lemma G.7, we take the derivative of M(K, N; with respect to
0M
expeexpp---- exp(-2A + tr (2)
0AAT
On
Define p ::= tr( 3
469 and we let
2M By
0, then we get
pp''' eexp(222an1)) 22artt") +
pT = exp(2AenIT)
log PT
= 2A
The above equation completes the proof.
Part H: Error Bound Analysis
Lemma G.10. Consider K K-epoch SGD with N fresh data and learning rate n. Given a set of learning rate values I, and an excess risk estimate that satisfies R R(K, N:n) (KK, N; (1 + o(1) when n. E P. Assume that n/' arg miny M (K, N: and 1j" E Then we have R(K, N: (K,
R^ (K, N) (1 +1))
39

---

Published as a conference paper at ICLR 2026
Proof. According the optimality of ry" holds that RK, - R(K, N; = Also, according to the optimality of rf' it holds that (1) - M(
+ +0)).
= R
Combining the above two equations gives
R(K,N;;") R* (K,
Combine the above two lemmas and we finish the whole proof.
G.4.2 PROOF OF LEMMA 4.4, LARGE K
Part I: Minimizing the Approximation of the Excess Risk
Lemma G.11. Under Assumption 4.1 and 4.3, consider K-epoch SGD with N fresh data and log
learning rate 1) satisfying 17 13x,T ( Then when K = w (log N). the chosen learning rate
n'
log pT arg min of M) (K,,N) N:n). lox 5x,2
2A,T
Proof. Given Lemma G.8, we compute the global minima of (KK, N; we have v/' = log
2A,7
(+) = arg minlgER M (K, n)),. which lies in the regime large.
log 3x2T 0 (+) when is sufficiently
Part II: Error Bound Analysis The proof of Lemma 4.4 concludes directly by applying Lem- mas G.6, G.8, G.10 and G.11.
Combine the above two parts and we finish the whole proof.
G.5 PROOF OF THEOREM 4.1
Proof. Notice from Lemma G.1 and Lemma G.4, we have that
1 01 2KN (1+ o1+)
R(K,N:)
R,(K,N.))
2 (1 11,)
(1(1))))))
Ra(K.N.))
no²
nayoo 2
T ]
+ tr (H)
da(1 - -1-))222
2KN (1 (1+ o(1)) when 77 E
w
T o
4
4
Rs(KNN.n)
Next, we carefully analyze the magnitude of R Ri(K, m). R2(K,N and Rs(K, N)n,, and using these results, we can simplify the excess risk expression.
Now, We take 7
log 2A,T
log KN
+ O (+) in Lemma 4.4, then
2N,KN
log KN
1--a)) 2KN
2K
exp 2KN log
[ 1-
2KN
T
exp (- loog KN + 0()))
0
T
40

---

Published as a conference paper at ICLR 2026
Thus
1
Ri(K, N,)) 2 -0gAa (1 - XaM)2KN
-0 1
T
and
Rg(K, d2H log T
noo² log T
Aa (1 )am) (1 + o(1))
8Y4T
8AaT
d²tr((H) log T
1+0 7
) log T
(1+
(K,
Next, we discuss two scenarios where K is relatively small and K is relatively large, to be specific, K ollog N) and K = w(log N).
When K o(log N), We have
N
log KN
(1- - Xm))
1
2KN P: + 0
KN
log KN
1 KN
exp
N log
Pi +0
2KN
log KNN
Pc + o(1))
exp
2K
o())
As consequence,
R2(K, Σ 0² o(1)
N N1+001 o(1)
N
Meanwhile,
Ro(K, (, =0 O log KN
0 (Rz(K,
KN
N
So
R*(KNN) NIK,N:,)(L000 )²tr(H) log T
8A4T + o()))
When K- = w (log N), we have
(1 No -11 10N~~111-11
log KN
))
2KN Pi +0
KN
log KN
1
[Nlog
exp
Pi
2KN
KN
loog KN
1
exp
2K
Pt + O
K
exp (o(1))
= =1+ o(1)
41

---

Published as a conference paper at ICLR 2026
So
1 o(1) o²d
(,, Σ
(1+ o(1)
N + o(1) 2N
i=1
=0
N
Ra(K, N, O
(
log KN
(R2((
KN
N
As result, we have
o²d
(*K, = NIKKN:
2N (1 (1)).
G.6 PROOF OF THEOREM 4.2
Now we establish the formulation of ((K,N) by solving the equation R R*,, (K,
When K o(log N), solving R*(1,TT (K,,N),, get
o² tr( H log T
(1 + 0T (1)) o²tr( H log T
(1 + oT(())
8'
S4&T
log T
log
T' (1 + OT (1)) = T (T))
(16)
According to the definition of the small o notation, there exists constant To such that when T > To. the right hand side is smaller than maxr log (1 or (1)). So W.I.O.G, could assume that T 2 in the following and use the fact that the function Ing monotonously decreasing when 3. Lemma G.12. Given and satisfying Equation (16), holds that T ~ when > To some constant To-
Proof. Notice that there exists Ti such that (or(1)] < 1 when T > Ti and or (1) is bounded.
Furthermore, or (1) 11, because the left hand side is strictly greater than zero due the fact that Dzz So when T > Ti, we have
log T
log
T
1 2 T
(17)
7"
log T'
1 log T
Cs T"
2
(18)
2 T
for two constants < 1 S 05. We claim that T 2
T =: aT when T 22 otherwise,
log T
log aT
C4
2 C4
T
aT
3 log a'l'
T
3 T
when T> 1
2T
a²
which contradicts Equation (17). We also have s 3o,T =: BT when T 2 82 by similar argument; otherwise,
log T
log 3T
C5
< C3
T
3T
log 3T
37
log T
<
when T 82
2T
42

---

Published as a conference paper at ICLR 2026
which contradicts Equation (18). So T ~ T when T min _/ 32,To) Tu-
Next, we prove the first part in Theorem 4.2, which ((K, = when ollog N).
We define F(T) log
T 8(T) = (or(1)), and c(T) = (()))) ((7))
2
Consequently, we have -F(T))(T) - -
F(T) F
(19)
So due to the convexity of F(T).
(F) - SF(T) -(T)) +(T))))++()))))))))))) = T (0(
log T Thus we have
log T
T' T22
The above equation completes the proof.
Combining Equation (16) and Lemma G.12 gets
log T -
log T"
(T (T)
(T -T).
(20)
T2
T12
Further using Equation (19),
(T F(T) - F(T") S +(T))(T)+F(TY)
(21)
Combining Equation (20) and Equation (21) gives
T" $ T(1 + o(1))
Substituding the definition of E(K, N) and we get the first part in Theorem 4.2.
When K (log N), solving R1, T") R² R*K, N), we get o²tr(H))ogg T 8'
o2d (1 (1+oN(1)).
or + or (1))
(22)
2N
There exists constant No such that when N > No. the right hand side is smaller than the minimal value of R²' (1,T") when is finite, that is, minr Ho log 8A.7" (1 + (1)). So W.L.O.G, we could assume that T' in the following and use the fact that the function log monotonously decreasing when x >>> 3.
Now we provide lemma to give a loose bound T' fisrt, and then we apply the lemma get the formula of B(K,N).
Lemma G.13. Given T' and N satisfying Equation (22). It holds that N T' < N when N 2 No for some constant No-
Proof. Notice that there exists N1 such that (1)) when N Ni. and or (1) is bounded. Furthermore, or (1) > -1, because the left hand side is strictly greater than zero due to the fact that n Dz. So when N N1, for the left side in Equation (22), we have
1
log T"
8²tr H log T'
log T" T
Co T
S
(1 OT (1)) S 07
8haT"
where co < C7 are two positive constants. And for the right side.
o²d
C9
<
(1
ON (1)) <
N
2N
N
43

---

Published as a conference paper at ICLR 2026
where 0g < 0g are two positive constants.
Then we prove that T
2
N when N 2
max
e 00
Otherwise, we have
oºtr( H) log SA
log T T
log
Cg
o²d
(1+ 2
2 N
Z
(1 + ON)))),
N
2N
4
which is a contradiction. Then we prove that T" Otherwise, we have
S N when
Gu
for some constant 610-
t² H T' or S 07
log T
07
log N N
307 log N
C10
odd 2N
(1 ON (1)).
BA
N
N
which another contradiction. The third inequality uses the fact that
log is bounded. We take NO
No = max e
en
cin
and we prove the claim. .No)
Combining Equation (22) and Lemma G.13 gives θ (N lo) = ( log and log T' log N log log N +(1).
(23)
Again, combining Equation (23) and Equation (22), and get
T'= tr(H)Nlog T
(1 (1) tr H (r(H) Nog
(1 (NN)
4Aad
4Aad
and
T Ir(H) log N
R(K, N)
(1 + ox(1))
N
4had
as direct corollary.
The above equation immediately finish the proof.
H PROOF OUTLINE FOR THE SOLVABLE CASE WITH ZIPF-DISTRIBUTED DATA
In this section, give the proof sketch of Lemma 1.1 and Theorems 5.2 and 5.3. Lemma I.1 gives a general expression of the excess risk, Theorem 5.2 and Theorem 5.3 characterise the behavior of E E(K, .N) respectively under power spectrum and logarithm power spectrum assumption. Their proof outlines are given separately as follows.
Proof sketch of Lemma 1.1. We exploit the properties that the sequential updates are commuta- tive and all finite-order moments of data are computable, and we obtain the result through direct calculation.
2. Proof sketch of Theorem 5.2 and Theorem 5.3. For Theorem 5.2, we consider two cases when K is relatively small and K relatively large. As special case, one-pass scenario belongs to the small-K case. We first derive matching upper bounds and lower bounds for high-dimensional cases for both the two regimes. The core of the proof lies in determining E(K, .N) by solving ER(WT:) = ER(wK,N) which requires an asymptotic analysis. We tackle this issue with two steps. First we prove a loose bound for T" for beyond a threshold, then we refine the obtained results and utilize the convexity of loss approximation to derive more precise estimates. The proof of Theorem 5.3 is similar to that of Theorem 5.2.
I PROOF OF MAIN RESULTS FOR THE SOLVABLE CASE WITH ZIPF-DISTRIBUTED DATA
Similar to the proof insights in Section 4, the first move to get the formula of the effective reuse rate to get an accurate proxy of the excess risk. Here, leveraging the simplicity of the setting, we can derive general closed formula for the excess risk.
44

---

Published as a conference paper at ICLR 2026
Lemma 1.1. Under Assumption 5.1, the excesss for K K-epoch training over N fresh data. with learning rate y) can be given by
R(K, N: = PA, (I-P 2
where the expectation is over the randomness of wt and training datasets {2,, Yo 1
The above lemma states that we can explicitly write out the exact expression for the excess risk. From the above expression for the excess risk, we can observe that, in the absence of label noise interference, and under the condition that the absolute values of all elements of the diagonal matrix I- 77 are less than 1, the optimal learning rate can the constant order. Therefore, in the subsequent study of the effective reuse rate, consider using the same learning rate 1 (11) for both multi-epoch and one-pass SGD.
It is worth noting that here law, as we only impose constraints on the power spectrum of the Hessian matrix H. In contrast, the probability matrix P can follow Zipf"s law any other law. In the remainder of this section, first consider the classic Zipf's ' law setting, where P follows a power law, and the data matrix A also follows power law, which is consistent with the previous power law analysis. In Section 5.2, explore the case where P follows a log-power spectrum (Lin et al., 2024), and investigate the impact of changing the spectrum's 's properties on the resulting effective reuse rate formula.
actually describing more general problem setting than the Zipf
1.1
A CLOSED FORMULA FOR THE EXCESS RISK: PROOF OF LEMMA I.
We first write out the update of parameter after K epochs
OKN- (K)) A II A
(I - 1- (I (e Po.
Then we get the excess risk expression
R(K,N; = 1 1 O KNN HH.KHOKKN K.N
=E 00 PA - 1 2K ... ...(I- -I- 2 Oo.
Assumption 5.1 gives
R(K,N:m) = E 1
00,0% PA (I 1paN 110 (I maxuo )2x)
1, PA (B(1 - 1) 2K N
Direct calculation gives
E xx '
Σ
25 2i-3pppees PNA
and
E (T
rjma: T) 2K
r)2k]
I +
2K
'2K
(-1Y) P P(I - 1
i
j=1
Then write out the excess risk
R(K,N: =
PA (I P P(I ))))2)
The above equation completes the proof.
45

---

Published as a conference paper at ICLR 2026
1.2 SCALING LAWS FOR POWER-LAY LAW SPECTRUM: PROOF OF THEOREM 5.1
Before we begin our main part of the proof, note that for all ( and 1 S 2. there exists di = (1) such that > 0 when >> d1. Then we divide the expected excess risk into two
parts:
c
N 76 (1- )1)
? 2k
R(K, N:n)
1
1 -
2 1=1
1
ja-b b
)1 2K
1
1 -
1
2
b b
ib
Sx S,(,NNm)
c
1
11-
1
(1-1)-
17 1bb
2k
2
ja
ja-b
i=
S S2(K,N.n)
The intuition behind our proof here is quite similar to what we do in Appendix G.5. We first separately simplify the expression of the excess risk when K = =(N= and K = w(N --n). ). The proofs for both the small-K and large-K K regimes proceed in parallel. We first control Sy S2(K, N) over a broad range of learning rates and identify a near-optimal 'y' for which S₁ is negligible compared to Sg. This allows us to approximate R (K, N) via R(K, N2r)) and S2 Nin").
1.2.1 PROOF OF THEOREM 5. 1: SMALI.-K CASE
The Expected Excess Risk Approximation.
Lemma 1.2. Suppose the assumptions in Theorem 5.2 hold. When K = o(N' and O(1), we define the estimator of (2, N;n) n) as
S,(K,
Σ
Ne
10
i=d++1
Then we have S2(K,N:n) = (,,KNN + o())) and S2(K, (KN)
Proof. By the fact that K = o(N -in)) there exists a constant N2 such that when N 2 N2, K S N
No'r. And we define F(x) = -² (1- (1 2 ))) Direct observation gives us that under Assumption 5.2, R(K, K, N: x Σi= F(i). Next we take the derivative of and analyze its maximizer.
F((x)=
ac
1
c
1
17
2K
N
Ia+1
b
ba-b
cN
c
c
1
2K
N-1
((x)
xa
z
b
x ba-b
b
b
2k
N-1
ra
b
ba-b
zbb]
2k
1
x
ba-
bbl
"1
2K
N-1
G(x).
h
ha- b
46

---

Published as a conference paper at ICLR 2026
where we define
77 2)2k)
G(x) = aa rxab c c
-²/)
(a - b)c - (a -bjc 1
17
2k
+
2cKbn
(1-
11
2k
x
x²
x
and
((x): = (a (a-ble b)c
(a - b)c
(1
!!
2k
2cKby
(1-
(1
2k -1-1
za-b+1 b+1
xb
ra
zbb
We denote the maximizer of F(x) by 2o. G( = 0. We claim that:
when N 2 N2. Fi 2 min
KN(a-bbjn
, (KN) 211
Proof of the claim. Notice that when N 2 N2.
1
I
x 6(KN)
6K
We assume that the claim is wrong, then
G(zo) 2 N (a b)c - (a b)c (1-
17
2k
a-b
KN b)en axx
xbb
KN b)en
2x
0,
which is a contradiction. The third inequality comes from Lemma J.3.
So 20 = 2 ((KN) Further pluging this into G(zn) = 0 that
G(xo) --x (1 o(1)) +N (2
(2K(a b)
(1 +1+ o())
2K(a b)en
(1 (1+ (1+)(1)) o.
z
gives
Zn θ ((KN))).
F(zo) =
KN
Then we have
K 0.5
(KN) 3-1.3
S2(K, N:
Σ
1
c
+
jn-b (1
1
2K
N
2
j0
b
76
+=
c
(1
2K
N
+
ja
ja-b
jo-b
oo (KNN 540.56 +1
K
J1 + Jz.
Furthermore, we have
0.5
K
0+0.55 55 (K N)
440.56
J1 x K 35 IKNo+t.. F(xa) S
KN
47

---

Published as a conference paper at ICLR 2026
and
1
c
(1
J2
1
+
2
ja-b
ja-b
(=K (KN)
0.6
a-0.0h +1
1
2Ken
K²
N
0
2
ja
ju+b
<= K 640.0
(KN) 0000 +1
d
c
N log
1-
2kez
+0
1048
2
ja
K #40.55 (KN) a40.55 +1
1
Nen +0 k22x
10110
2
k= #40.58 (KN)
o-b.o +1
d
1
e
2K Nen
(1 (1+)
2
ja
34 (K 0-0.3 i=
We define Ki (1)x)
NK x
We can derive that arg max Ki(x) - ((KN))).
and
max (x) = =0
So when d 2 3(KN) we have
KN
3(KN)
J2 2 Σ
(1 (1+)(1))
ja
i=
(KN
2 (KN)
ce
2on
(KN)
KN
KN
We verify that J1 o(J2) direct consequence. We define
d
(:n)
1
Σ
No
2
ja
i=d1
+1
K
(KN) F
1
Σ
2
imdi+1
i= 540.58 (K N) 240.35 +1
= Jn + J2.
We have J2 J2(1 + +((1), and
0.5 K
a-0.5b (KN) 240.68
Ju < K Kalow (KN) 3To.3 x max K1(x)
= =[].)).
KN
So S,(, = Nm]
The matching upper and lower bounds for (2K, N; comes directly from Lemma J.7.
By combining the expression of S2(K, N: with Lemma J.7, we get another lemma: Lemma L.3, Suppose the assumptions in Theorem 5.2 hold, and the expression of S2 N:n) is given in Lemma 1.2. Then we have 8n 52(K,, (K,KKNN, N;
(KN) =
48

---

Published as a conference paper at ICLR 2026
Proof.
8 On
S2 S2, = KKN
Σ
d
Ne
12a
i=
NKN) 1=1
where the second line comes from Lemma J.7.
Lemma L.4. Suppose the assumptions in Theorem 5.2 hold, and the expression of S2(K, N; is given in Lemma 1.2. Consider two learning rate options n/ = (1) satisfy n -1 = o(1) Then
we have (K, N; = N:(K,N;1)) o(1))
Proof.
(2(K, - N:nk) = On
Sz (K, 1 r/)1
(KN)* t=1 1(n n
S,(KK,N:'))(L)),
where 7 E [min(n, 7/), max(n, v/)] (1), and the first line comes from Lagrange's Mean Value Theorem. The secome line comes from Lemma I.3, and the last line comes from Lemma 1.2.
The Range Optimal Learning Rate. First, take n/== = (a- 1)d
log and we have
KN
2K
(1, < die
c
c
(a
1)d
log KN
1
+
1
2
di
p-b
di
ya-b
KN N
By a Taylor expansion argument, we have
KN (1 + o(1)) wv
SiKK N:,)) = dic
2Ke
(a -a-11 (a-11da--
log KN
x
2
di da-b
ac
dic
2(a 1) log KN (1 + o(1))
N
1
2
a
dic N log(1
2(a-1) lou (1+o(1)))
(KN) 0(S2(K,
where the last inequality comes from Lemma 1.2. Then we have
R(K, N:n'
S,(K, N:n/) Sa(K,N:1)
= =S2(K, (5
-aK
(1 + o(1).
ja
i= += +1
Then we prove that 17" E [2 -
2). We prove by contradiction, and assume that there exist a such that r)N(), 2 for all i 1. As we only
constant > 0 and sequence (N,) 20
49

---

Published as a conference paper at ICLR 2026
analyze with respect to the sequence (N)))=> without loss of generality, take (Ni)) IN. By Lemma 1.2 and the convexity of (2(K, n)) with respect to 17. have
Rs (K,N) 2 52(K,N: = ( N; (1+ o(1)
z (3(K,N:2)+22Bscc S,(K (1+)11)> R(K,N:1)
+ Ōn
when N is sufficiently large, which is contradiction. So
R² NK) Si(K,NN;")) + S,(,,
N. & N;K,
= S,KKK.N
Thus, Si(K,N:n") = (5)( and R',,, S2(,, N; + o()))
By Lemma 1.2 and Lemma J.7, there exist two constants C₁ and C2 such that R (K, S
C1
(KN)
and R*(K,N) 2 C2 when the condition d = I(T+) holds, For one-pass case, by Lemma 1.2
(KN)
and Lemma J.7, we have
(1, = R(1,T' 1f (1,
S R(,,T' 17 (1, laz=o))
R1, d=oc
1
4KNg
(1 (1+0
<
C2
(24)
ja
T
i=di+1
and
1 d 2 i=
R (1,T")
4KNo
(1+
C4 T
when d = 8 (T'
(25)
1.2.2 PROOF OF THEOREM 5.1: LARGE-K CASE
The Expected Excess Risk Approximation.
Lemma 1.5, Suppose the assumptions in Theorem 5.2 hold. When K = w(N= and nj = O(1),
we have n:
N
Proof. There exists N3 such that when N 2 N3, we have 2 No Then when d 3(KN) 2
3N o. v, we give the lower bound of the loss:
3N
S2(K
N
Σ
1
c
N
2
ja
ja-b
N=
1 2N +
(1
c N
2 (3N
)m
N
N
Then we derive the upper bound of the loss:
c
C
(1
71
2K
N
<
+
10
ja b
ja ja-b
5b
11 2K N
c
c
(1
+ 2
ja
ta
デ b
16
i=
+1
50

---

Published as a conference paper at ICLR 2026
When K = (NN= and i S No
(1
2k
2K
2K loR
1- 7
1
1
N p-ク
2
Nat
-2K
S e
ワ o(1)
Then there exists N4 such that (1 - # 2k have
I when N 2 N1. So when N > max(N3, Na), we
N カーー
52(K,N;1)
S
1
1
c
N
c
2
ja
2
ja
i= a-b +1
One can derive that max f. (1 -;
+
1
So
No
R* x
N
N
1
N
And we complete the proof.
The Range of Optimal Learning Rate.
First, take 1// 1.5, and have
N;,, v
dic
c
max
0.5,
1.5 di
2K
N
2
dq
pa-b
di-b
di
d1c
(1 - 0(1)) N
2
o(S2 (K, N:nn)),
where the last inequality comes from Lemma I.5. Then we have
R(K,N:1' = (K, N; + S2(,,
It is obvious that 17" < [1. We know that (K, S1 (K, Nim") + SK, - R(K,N:n)) -,((KNN)))(+
By Lemma 1.5, we have
S2(K, =(K and Sz(K,N:1)) = =
which directly implics that
(K, = ONN = R* = = (N
1.3 E(K, N) FOR POWER-LAW SPECTRUM: PROOF OF THEOREM 5.2
I.3.1 PROOF OF THEOREM 5.2, SMALL-K CASE
Let T' be defined implicitly by equating the averaged risks at their optimal step sizes:
R²(1TT") = N),
(26)
We claim that
C2 c
C3 T-1
T
S T <
T.
(27)
C2
51

---

Published as a conference paper at ICLR 2026
Proof. We argue by contradiction, considering two exclusive violations of Equation (27).
1. Case 1: T > ( By the risk bounds encoded by (C2, C3) for one-pass training with T" fresh data and by (Ci, C4) for K-epoch training with N fresh data, this inequality forces
(*,,, < (K, N),
which contradicts the defining equality Equation (26).
2. Case 2: T" < ( T. given = = we still have d = (/))) The same risk comparisons then yield
R R* (K,,
again contradicting Equation (26).
Both contradictions rule violations; hence Equation (27) holds.
Therefore, the desired characterization of N)) follows directly from Lemma J.8.
1.3.2 PROOF OF THEOREM 5.2, LARGE-K CASE
By Theorem 5.1, there exist constants C3 Cs > 0 such that, given ((T)))
Cs S (K, S
Css
(28)
N
N a
Let T' be defined by equating the averaged risks at their optimal step sizes:
R*(K,N) R' (1,
(29)
Combining Equation (28), Equation (29) with Equation (24), Equation (25), we claim that
C4
C3
N
S T <
No
(30)
C₁5
C
Proof of the claim. We argue by contradiction.
1. Upper violation. If bound),
Ca C6
N a.t then by Equation (24) and Equation (28) (lower
C3
Co
R" (1,
S R (K,
(T')
N
N
which contradicts Equation (29).
2. Lower violation. If
C
N बー
then the condition d' = 2((T)) gives
Cg
d = 2 1 N 2 (TT))
Using Equation (25) and Equation (28) (upper bound),
C2
Cs
(L,T")) 2
2 (K,
(T')
again contradicting Equation (29).
Both contradictions impossible; hence Equation (30) holds.
The characterization of F(K, N) follows directly by the claim.
52

---

Published as a conference paper at ICLR 2026
1.4 SCALING LAWS FOR LOGARITHMIC POWER-LAW SPECTRUM: PROOF OF THEOREM D.
Similar to the proof of Theorem 5.1, the proof of Theorem 5.3 consists of two parts: First part is the case when K = o(log" N), and the second part is the case when = w(log" N).
Before begin main part of the proof, note that for all dj ( and 1 S 2, there exists d2 = (1) such that (141)
" O when > d2. Then we divide the loss into two parts:
clog (i + 1)
clog (i 1)
2K
N;K,N;;)
1
7
ja
log (i 1)
i=
d2
clog (i
clog (i + 1)
2K
c
17
80
j
log (i +)
1=1
(i(K.No))
1
c
clog (i 1)
clog (i 1) 1
11
2A
N
+
2
ja
ja
log (i + 1)
i=d++1
Vi(KNNm)
1.4.1 PROOF OF THEOREM D.I: SMALL-K CASE
The Expected Excess Risk Approximization.
Lemma L.6. Suppose the assumptions in Theorem 5.3 hold. When K o(log" N). we define the estimate of ((K, N; as
(2(KNN;1) == 2 iml
c
NK
ja
Then we have (2(K, N;n) = V(K, N:n)( + +()) and (2( N; (K
Proof of Lemma 1.6. We first define a function
((x)=
(
clog loog"(( +
1- 11(1-
7
2K
N
xa
Ta
log (x + 1)
Direct observation gives us that under Assumption 5.3, R(K, N: x Σi= W(1). Simliarly we take the derivative of W.
2K' N
(((x)
ac
clog"(x (Ir 1) +
clog"(x + +x
(1
Ia+1
xa
ra
log" (xr
+ cN 1
clog" (x 1) clog" (x + 1) (1
77
2A
N-1
xaa
a.a
xaa
log" (xc + 1)
(aclog" (x
be log +1)
2K
17
1
p-+11
x= 1)
log" (x: +
2cK log (x +1) (1
2K-1
bn
x²
log
(x + 1) log
b+1 (5t
c
clooooooll clog"(x +1+
clog"
(oog"(+++) +1)
17
2K
N-1
1
220+1
za
za
log "x + 1)
2R
-a
T - clogo
(x ( + 1) + log"(ox +1)
log" 1)
53

---

Published as a conference paper at ICLR 2026
+N (( (acclog((o + - belog"
1) x
(1-(1-
1
7
2K
x +
log 0x 1)
2cKbn (1
2K-1
17
log(x +1)
log"(x + +)
x x+1
We define
2K
G(z) = -a x² clog (x+ + clog (or + 1)
1
7)
log" (x + +1
+ (( aaclog"(x + be log 6- (2 + 1)
11- (1-
77
2K
I x+1
log" log"(s:
(xr
1)
bcKbn
(1
71
2K-1
x
log(æ + 1)
log (x
I +
and De is defined to be the maximum of W (x), so G( =
G(x) 2 N Noog (o + 1) (ac- log(z + 1) x ++1 11
be
x
(1-(1-
?)
2K
ax
log"
h
2 N(a - b)clog (x 1 (1-(1-
2K
"
ar
log" (xr 1)
2K-1
log (x 11 1))) ax
= N(a b)clog (x (x+1)
1
Σ
log lx + 1)
1=
2 N(a - b)cn-annn
So To Ω ( is direct conclusion by G(zo) 0. Also, by solving G((xo) O, can get the approximation of un as
G((ro) = - ar o(())
2Kn
K log N
))
+ N ac aaclog (zo + 1)(1 + o(1) o())
(1+ o(()) +0
log" (Jr + 1)
= =-ar + o())) + 22222K Nacn + o(1) =
thus we have
To = ((KN))) W(xo) θ
1
KN
There exists a constant N₂ such that K < log N when N 2 N₃- So when N 2 N₂ and d 2 3(KN) 2 3(KN)
we have
Tog' N
(KN)
Ing
clog (i
+11 (i+1) (1 (1-(1- log"(i (i 1)
2K
V2(K, N:m) =
Σ
(=d++1
2K N
1
c log" + 1) 1-
17
+ 2
ja
ja
log (t 1)
NK
K
Iog" N
= 1 + 4/2.
Furthermore,
(KN)
K
20
w S (KN)
x W (2n) 2
log N
log
K N
54

---

Published as a conference paper at ICLR 2026
and
2K' N
c
clog
(i + 1)
clog
eiog"(i+ + 1)
(1
+
2
j
j0
log (i + 1)
im NKN)=
K
log"
2K
K²
N
1
+0
ja
10
log"(( + 1)
i=(KN)a
K
log" N
Σ
N log (00g(11 1- 2Ken +0
10 (xx1)
i=(K)) log" N
Nen
+0 k2 12u
+0
k2
i=(KN)a
=
e
Nen
(1+)
2
ja
i=(N)
N
We can verify that max Ki e ((KN)²)
We recall Ki (xr max (x) = θ
and
through direct calculation. So for the we have
KN
3(KN) Σ
2/2 2
(1 + o())
1
(=(N)
(KN)
KN
We can verify that wi o(1b2) as a direct consequence. We define
d
V2(K, N:
NKN
e
2
ja
(=d++1
(KN))
2a
1og"
Σ
-2KNen
Σ
-2KNo
80
70
d=
{=(KN)
K
Tog" N
= 21 + 45.
We have 1/2 = 51 + o(1)) and
(KN) !
K
20
log' N
1 x
0l122)
KN
So V2(K, N:n) VsKK N;K) +0)))
55

---

Published as a conference paper at ICLR 2026
Finally, we derive a matching upper and lower bound for (2(K, N) and conclude the proof:
V2(K, 2 J2 2 J2 2
(KN)
(KN) 2/2
d
V2KK,
Σ
NK
1
i=d++1
i=(KN)² +1
(KN) #
1
-2K Non
1
ja
2
i=(KN) a +1
(KN) a
KN
(KN)
NKN)
Then we complete the proof.
Notice that (2 and V2(K, are identical to each other, so we can directly apply Lemma 1.3 and Lemma 1.4 in the remainding proof of Theorem 5.3.
The Range of Optimal Learning Rate. First, take v/' = 2 log (2) - e, where e == and we have
()d1 log
ac
KN
d2c (1- (2) d2
clog((2) +
(1-
2K
N
KK N: =
c
2
dz
log"(2)
N
d2c
2K 2Kclog"
1
+ (1+)(1))
dz
12)
d2c
2(a 1) log KN 1
(1 + +(1)))
2
N
d2c N log(1
- 1) lax KN (I+a(1)))
2 e"
N
(KN) 2(--1)
where the last inequality comes from Lemma I.6. Then we have
R(K,N:n)) = Vi(K,N;;) + (2
= N1)( o(1)
= -12(K,N;2) (1))((+(1)))
d
c
4 Na (1+0(1)).
e
2
j0
i=
- o1), Then we prove that 17" (2))) 211,,,10g there exist constant > 0 and a sequence (N + co such that 17" (N,) S 2logx(2) (2) c for all
2ogg We prove by contradiction, and assume that
i 221 1. As we only analyze with respect to the sequence (N)) without loss of generality, we take
(N.) = IN. By Lemma 1.2, we have
R² N) 2 V2(K,N:n') Va(K, N: N:n')((+((())
② Vi2 b (K, (K.N:2108((21) (1+ > R(K,N:1))
V3(K, +5g
when is sufficiently large, which is a contradiction. So R-(K, N) = (K, N:v²") + V2(K, N: VVi(K, + V2,K,, ) (1 + o(1)
-VI(K, + V/
K, N: N.N:2logh log" 2o (1 + +o1)) & R(K,N.n))
56

---

Published as a conference paper at ICLR 2026
So Vi(K, = (vs (Kog; and (K, = V2; (2))( + +o()) ~
(KN)
1.4.2 PROOF THEOREM D.I, LARGE-K CASE
The Expected Excess Risk Approximation.
Lemma 1.7. Suppose the assumptions Theorem 5.3 hold. When K = w<logg N). we have V2(K, N:n)
N) a-T.
Proof of Lemma 1.7. By K wlog" N), there exists a constant No > such that K > log" N when N 2 No. We notice that when e ( (ooo'")) log(i + 1) elog N). Then, when N No and d 2 3(KN)* 23 (Nlog" N)² &
we have
3o 3(N log" N
N
1
clog clog"(i + 1)
V2(K,
i= N logh N)a
1 N log" 6 N)
1
(1
Cn ym
2
3 N log" N
N
1
A NNlog N)
For the upper bound, we have
2K N
clog" 1) +
clog (i- 1) (1
R(K,N; S
1
17
7a
ja
log" (i + 1)
(N log' N)
c
(i (i+1) 1) + clog
clog (i +1)
(1-
2K
5
1
(1-1og((++
2
ja
ja
log'(i (i + 1)
1=1
+
ja
i= log N) +
(N (Nlog" N)²
When K = wlog" N) and i
(1- Ligi(i (i +
1)
K
(1
(1
C12
K
K log (1- 1og
= e
log N
K log N o(1). ).
So there exists N7 such that when N 2 Nr. (1
K
S 1., and when N > max(No, N7),
Tog (1+1)
(N N)
N
R(K,N:n) <
c
1
log"
(i +11 1)
2
ja
2ia
ja
i=(N log' N N)
clog "log((zii (x+11) 2
N =
One can derive that max,
Nlog N
57

---

Published as a conference paper at ICLR 2026
So finally, we have
(2 & R(K,N;m)
N log N) a- +
N log N) a-1
x
N log" N) und
and we get the result.
The Range of Optimal Learning Rate.
First, take v/' = 1.5 1.5,,g((2), and we have
2 N
N; v d2c
clog" (2)
clog"
1.5 log" log'(d2 (d2 1)
1
max 0.5,
2
d2
d2
dic
(1- (11)
of VV22(K,
where the last inequality comes from Lemma I.5. Then we have
R(K,N:1)) ((K,NN;)) + V2(K,N:)))
It is obvious that ri" E log (2), (2), 2 log (2) We know that
R' R*KKNN) = Vi(K, V22 <((KN -1
N (Nlog" N)
T-I
1.5
E(K, N) FOR LOGARITHMIC POWER-LAW SPECTRUM: PROOF OF THEOREM 5.3
I.5.1
PROOF OF THEOREM 5.3, SMALL-K K CASE
The proof here is almost a reproduction the proof in Appendix I.2.1.
1.5.2
PROOF OF THEOREM 5.3, LARGE-K CASE
Consider the multi-epoch training setting with d Ω ((KN) ( ). By Lemmas 1.7 and J.7, there exist constants C7, C's > 0 such that
Cs
C N(log Nyb
S RK(K,N) < N(log NY
(31)
Let T' be defined by matching the expected risks:
R*(K R2(11T"
(32)
In the one-pass case, we use the constants C3, C4 (as defined the proof of Theorem 5.2) to
control R. R= (1,
We claim that
CA (GH)
C3
Nlog
< T
N (log NY¹.
(33)
C2
Cs
Proof of the claim. We argue by contradiction.
58

---

Published as a conference paper at ICLR 2026
Upper bound violation. If > ( (log N) then the one-pass upper bound together with Equation (31) (multi-epoch lower bound) imply
(K,,NN < (1,
which contradicts the defining equality Equation (32).
N (log N),, then d = 5 ( (KKN)
2. Lower bound violation.
T
yields
d = 22 (log (/) ((T'))/) the one-pass lower bound together with Equation (31) (multi-epoch upper bound) give > (L,
again contradicting Equation (32).
Both violations are impossible; hence Equation (33) holds.
Thus, in the large-K K multi-epoch regime, the matched one-epoch training time satisfies 7 (Noog N)) up to fixed constants. Therefore, the desired characterization of E(K,N) follows directly.
J ADDITIONAL TECHNICAL LEMMAS
Lemma J.1. For any PSD matrix A, it holds that
H A) S [n)H)))
Proof. We denote the PSD decomposition of H by
H
bpqy
where A; and are the eigenvalues and corresponding eigenvectors of H. So we get
(H. A)
d
X Ag.
A|
tr H A|
which completes the proof.
Lemma J.2. When 1 2 1, we have
(1+ < + 21x, x E [0, log 2
Proof. We define f(x) = (1 ()) - (1 2lx).. Calculating the derivative and notice the fact that 2d 2 (log 2)x, we obtain
(xx==((1 x) 21
< 2: -1) -
51x2 1-1 -1 5.
The above equation completes the proof.
59

---

Published as a conference paper at ICLR 2026
Lemma J.3. When I 1, we have
(1 (1-2) x) 2 1x, [0, 67
Proof. We define g(r)) = (1 x²)2 (1 lx). Calculating the derivative, we obtain
g'xx) = -2((1 - 21 +150 when E [0, 1 - 2 x
Notice that h(x) = is convex, so for æ E [0, 1], we have
h(- (1 =)) - xh( - +1 (1-=))((0))
that is
2 < 1 2
when E [0.
So
2 n
2(21 - 1)
1
1
2
when / 12 1,
2(21 - 1)
6l
which concludes the proof.
Lemma J.4. Given N data points such that Bo ... Rn-1
3.d N(0, H), and define A = (I
( 1ft010)) Then we have
(VDAYPNi)
E A EAI'
where ŌΛ == C log d for some absolute constant Ö >
Proof. We define Q
A E.A for convenience. We can obtain a concentration inequality for [[Q]]
due to the boundedness of æ according to Theorem 7.1 in Huang et al. (2022).
We define
Y, I - n
For any 1 siS N, choose mi 1, and we have
Y. EY, || H 20? == oi
So we know that MA = 1, UA = 2D N. and
P[I 2 < de žoيz de BDD when 12 > 8eD4,,
Furthermore, we have
PI
1e when t > 16 N log d.
So there exists a non-negative sub-Gaussian random variable Z, s.t
[[ 2 P(7205 1o when 12 > 1 N log d.
60

---

Published as a conference paper at ICLR 2026
Then for all / 1, get
E
Q = E|| @1|) /16. Nlogd (100)/1o/1
V /16ED4 log d
+ E|IQI'1
110 logd)
+.0
(V VI6ED4INN log
P[[Q 2 t)lt" dt
N log
+00
16
PfZ 2 t) dt
VI6eD4pN log
+ EZ
N
(VC16eD"/NNlogg d)
where C and Ö are absolute constants, the fifth inequality is due Proposition 2.5.2 in (Vershynin. 2018).
Lemma J.5. For any S K, we have
II A -EA)" S (VoAPRi + |EAI)) - |EA
E
where d is the same positive constant appearing in Lemma J.4.
Proof. Let |EA]] and c, N' log d for some Define the perturbation (
A (k) - E.A. Expanding the product as
II A (K)
II
(1(h + +EA+EAA Σ Σ Ps
m=0 SE (!!)
where Ps is the matrix product with Q()) at positions & E S and TEA elsewhere, preserving order. The difference is
II A (6) (EA)- Σ Σ Ps-
SE(!!)
By the triangle inequality and linearity expectation:
E
II A (k) k=1
(EA)"
Σ m=
E Psll-
(E((9))
For each S, decompose into maximal consecutive blocks Bi...., B. with sizes s s Ss m). By Hölder inequality and Lemma J.4:
E Psl < a' E
Q01
S < II
E 10)00)10))
< <a
1
Csp
i=1 jeB.
==1 jEB,
i=1
Since -V T8eD*n Ns sslog d is increasing in s and s, $ I:
Cx S ca
E|Ps
- d 1m
61

---

Published as a conference paper at ICLR 2026
Summing over all S with [S] m:
B|| - (1) a mm o
SE((M)
Thus the total bound is:
a' m o (a (a+ dd
m
m=
completing the proof.
Lemma J.6. For any S K, it holds that
II (
(RA) -(EA)
<(V22NNPN + |[EAI)) ||EA||]
where d is the same positive constant appearing in Lemma J.4.
Proof. Set a = ||EA||2 l| and c = N1 d. Define the perturbation ( = A -EA
Expand the matrix product as:
II
A T0) = II (Q + +AA)
Σ
Ps
m=0 Se
(!!)
where Ps denotes the ordered matrix product with ((k) at positions E and EA elsewhere. The target difference is:
A A
(BA)"
ΣΣ
Σ Ps.
1=/
m=1 SE(!.)
For the squared spectral norm, we have:
E
Σ
Ps
SE ΣΣ
Ps
ΣΣΣΣ
E Ps.,,
Ps. 1],
m=1n=11 Sm S.
where Sn and Sn range over all subsets of [1] with sizes m and n, respectively. For each pair (Sm, Sn), decompose the union U Sm. U.S, into maximal consecutive blocks Bi,..., B, with sizes s; [B,] (Ei=) 8; [u| m n). By Hölder inequality and Lemma J.4:
E Ps.. Ps.
<
m
|0
2= 1=1.ec JEB;
21-m-n
E (I|2) m++) min
1=1 JEB.
m++
21 m-
(V + +n) log
21 mallm-ndmmi
The combinatorial count satisfies:
ΣΣI-(")
S. m ..)
62

---

Published as a conference paper at ICLR 2026
Combining all terms:
E A - (EA))
EE
2
m mnn = [[a a) - ddj??
m=In=1
where the last equality follows from the binomial theorem applied (a cz)
Lemma J.7. Consider function of training time T given by
C(T) Σ
27m
7
i=d +1
where c, are some absolute constants, d1 = (1), and > Then we have:
+ 1. L(T) S T
Given d e (KN))) (() 2 T _
Proof.
Computing the derivative of f(x) = +/4 e
20
we have
arg max f(x) = (KKN)
1
max f(x) = +
(KN)
Then
1. For the upper bound, we have
(KN) a
((T) S 2 i=d +1
1
27
27en
c
2
2
i=d1+1
(=KKN
$ (KN)
S
(KN)
(KN)
(KN)
For the lower bound, when d 2 3T we have
3(KN)
((T) 2
27en
2en x 2(KN)= 2
23 (KN)
(KN)
(K
The above equation comletes the proof.
Lemma J.8. Given estimator of the excess risk for ME and OP cases
S2(K,
1
Nen
2
i=dit1
and
$2(1
Σ
imdi-1
for some di ([). the ME excess risk and OP excess risk satisfy that
R(K, N:n) N1) R(1,T" = $=(1.T":m)(+++(())
then give d = D(T') and when T' T, holds that
F(K,N) [K(1 - o()), K(1 o(1))
63

---

Published as a conference paper at ICLR 2026
Proof. We define HT) (2( M:n) and I' By definition of EKK, N), we have T E(K, N. Our goal is to prove that [1 - [1-
get oN (()))) We define 5(K, N) = m (.(K. o(1), and ((), - o(1). Then we (.(K
Solving R(K, N: ;))
(1,,TT
can derive that
-(1)(--((,,) (()) ((T)
which indicates that
- N) & -(
- ((
Notice that H(T) is strongly convex, and we have H(T)
(KN) and (T) =
NK
by Lemma J.7. We are now ready to prove that a E
(KN)
(1), [[]]
12 (T' - T) (T((((' H(T) H(T) S (TT')(T'T)) ((1,T')((T) ((K 8(1TT)
(T' T)
T2-
-(- + 8(K,N)
-( 2 o(1)
So
T T o(1)
1) }} T(1-2) d
o(1)
(T' -T)). T).
T 5
T
Direct calculation yields the result.
Lemma J.9 Hyper-Contractivityy Given d-dimension random vector x ~ DD satisfying that || S
D for some constant D, and the covariance matrix H : EE x T = diag(A ( X2 .2,.................. Aa).
where A A2 ... Xa 2 e ffor some constant > 0, then the following holds:
E [wxx' Pxx S Sai(HH))
for some constant independent of P.
Proof. By Dieuleveut et al. (2017), the above lemma holds for data distributions with bounded kurtosis along every direction, i.e., there exists a constant K. >> 0 such that
for every IRdd E (11, az) < K (v. Ho)?
So that it suffices to verify the above inequality. Since \a 2 we have
(v. Ho)² c² |||
For the left side, by the triangle inequality and that ||>||| is bounded
(v. x> < ||||| < D
Combining the above two inequalities gives
D4 < x (v. Hv)
E (u.
Now setting 1 2 completes the proof.
64

---

Published as a conference paper at ICLR 2026
K
THEORETICAL ANALYSIS UNDER LEARNING RATE DECAY
While the main body of this paper focuses on SGD with a constant learning rate, practical training almost always utilizes learning rate schedules. this section, we study multi-epoch versus one-pass training under class of polynomially decaying learning rate schedules. We show that one-pass training with a polynomial learning rate schedule is suboptimal relative to the statistical minimax rate N implied by the Cramér-Rac lower bound, which is odd (Jain et al., 2017). Meanwhile, 2N
o'd
multi- mpoth- training can almost attain this rate.
K.1 PROBLEM SETUP
We consider the same linear regression model, i.i.d. training data and the initial parameter value wy in Section In addition, we assume the label noise is bounded almost surely as | D' for technical convenience. We run SGD algorithm with a learning rate schedule E = ( J20 (with ? S 2) where the sampled index je defined as Section 3. The update
W wi The V w (wr J. M/.)) w. n x. (w: ww) + m,
Next, given K K-epoch SGD over N data points, with learning schedule E, we define WK,N,E to be the distribution of WKN. Based on this, we define the expected excess risk of given K Keepchh SGD over data points with learning rate schedule as R(K, .V E) := E [R(w)], We further assume that Assumption 4.1 holds, and x. has continuous probability density function p(æ) with upper bound M on a d-dimension ball with radius D. We also define Amiu == Ad. and KH A to be the condition number of H.
We then introduce polynomial learning rate schedule class that we consider.
Definition K.1 (Polynomial Learning-Rate Schedule Class). Given the K-epoch SGD trained with N fresh data samples, we define a learning rate schedule class r {E b, a.: > 0, 0.5 I a a 11, where E(To, = [mo b, a) 70 N
KN-1 that satisfies
1
K.2 SUB- OUB-OPTIMALITY ONE-PASS TRAINING
Theorem K.1 (Sub-Optimality of One-Pass Training). For one-pass SGD with dataset size of N. given any learning rate schedule E T, for some constant C, when N is sufficiently large, we have
Codd N
R(1,N;E)
KH.
Proof. This can be seen directly from the proof Theorem 1, strongly convex case in Ge al. (2019).
Theorem K.1 gives a lower bound for one pass training that scales proportionally to the condition odd number 6H, be specific, R(11 .N; > N Kи. Since the condition number can be arbitrarily large, the lower bound indicates that one-pass training may be arbitrarily far from the minimax rate, showing suboptimality.
K.3 OPTIMALITY OF MULTTI-EPOCH TRAINING
Theorem K.2 shows that multi-epoch training can remove the dependency on the condition number and reach the statistical minimax rate.
Theorem K.2 (Optimality Multi-Epoch Training). For multi-epoch SGD with dataset size N. there exists a learning rate schedule E = E( J 1, 1) E that satisfies R(oo, E) = (1++
Before we begin our main part of the proof, we first give some additional notations, and introduce some technical lemmas.
65

---

Published as a conference paper at ICLR 2026
Additional Notations. We denote w. wi and 1/, kr Ne. where in and ky are defined in Section 3. We view the SGD training dynamics as an empirical risk minimization (ERM) problem. To be specific, define fi(w) 1 (w, xz and the ERM problem can be written as
min F(w)
f(w)).
We write its solution as u.. Define the empirical covariance and its minimal cigenvalue H N Ei=1 a, 14 Amin Note that F(w) is u-strongly convex. As P(u 0) O, assume that μ > 0. Also, fa(w) is quadratic and L-smooth with L I D2, since fi is quadratic with its quadratic coefficient æ. X D²I. We write x D 0 t). Furthermore, we adopt the convention that w w
Technical Lemmas.
Lemma K.1. Define two events G = {1 2
Amin
NA2 j. = g9, and define 8N = 2d expl
32D
Then we have Pr(B)= S 8N.
Proof. Let
1
H
H
Zi
Z, := 2 H.
N
Then E| = and since 0.
> 0 and | 112 < D2, we have x. 3 D² and also H 3 D
(because Amax H
E| 1 ) Hence
-D²I v Z 1 DºI,
1z S D2 a.s.
By Theorem 1.3 in (Tropp, 2012),
N
N22
Pr
Zi
2t
2d. exp
(34)
N
8D4
1=1
Substituding t Amiu
Pr
1 N
Σ
Z₁
2
Amia
<
2d exp
NN
=8N-
N
2
32D4
i=1
Finally, since
1 Amin
> Amin H) H
Amin - | H|, H
the event {ur < Amin /2} implies H
H
> Amin/2. Therefore Pr(B) S 8N-
Lemma K.2 (Finite negative moments of ja for large N). Fix any > O. Then there exist constants No N and C < co, depending only (p, d, c, D, M) (in particular, independent of N), such that for all N 2 No.
El SC
Proof. Let Va-1 = ( 1)) be the volume of (d 1) -idimension unit ball, and define
A = 2M Va-1 D
Fix any u E gd-1 and DJ. Since p(z) M on [ $ D).
Pr (Iu 2 S sr) J Jellet SD. lu [
p(x) dx & M Vol ((1|a]) S D, uTaa S sr).
The set |||=|| < D, Iu æl I r} is a slab of thickness 2r intersected with the radius- ball, hence its volume at most 2r times the maximal (d dimmennsio cross-section d
Pr (Ix² x0 S Ar (u E sd-1 r (0, DI)-
(35)
66

---

Published as a conference paper at ICLR 2026
In particular, taking r D and using |u JuTan æ S | hence A 2 D/D. Fix E (0, [6A2N] and
S D a.s. yields Pr(|u x S D) AD,
VNt 8:=
r r: Nt,
D
Since A 2 1/D, we have 1642N
-
D I6N
hence S D/2 and S 1/4.
By the variational characterization,
Σ uu x;)²
min 1
N
[=1
If S 1, let u. E Sd-1 attain the minimum. Then for every i,
(u, ax2)
u 23) S Nt, so | x VNt 2
Ne be an g-net of gd-1 in Euclidean norm with We S (3/E)² Pick u E No with || u, Se. Using ||,||| D.
|u xu |u, æi + ||uu u. ||x||||| S + N Vi.
Therefore.
1s S U N a. Sr..
ueA. i=1
Using independence and equation 35 (note r < D),
sup Pr((u' T x S rTa (3) (Ar) ||
Pr(p t) S Wel-
3D
d
(2AVNT)* N (2A) N " M
(36)
N
By Lemma K.1, there exists constant 7 such that Pr(u S Aa/2) S d exp(->NN. For p> 0 and any nonnegative Y, we have
BI
2 =p
p-1 Pr(Y st)dt.
0
Apply this to Y = μ. Let
to 16.4
Choose Np == maxxf fd + 2p (8A7c) -1 '11.
Then when N 2 No. we have N + 2p and
We split the integral at to and Ag: la < Ay 2
Biu = p /
to
D2 S t) dt
t pー 1 S (t dt +
pーー g--1 Pr(μ S t) dt +
4
13 11 + Is.
Bound on Is. Since Pr(p S 51) $1,
D2
Is S
p-- dt =
Ad Ad (
(
4
2
Bound on I,. For S da Pr(p S 1) < Pr(u S 24), ) hence by Lemma K. 2
Ad / pー dt < Pr(u - Xd ) s de de- -N (16.
1 S p Pr(u - 2 0n
67

---

Published as a conference paper at ICLR 2026
Bound on Iz. Using equation 36 and N > d 2p.
N-d P 6o"
13 p(3D)
/ 1 -= - p-1 dt dt
2(3)) M=
N-d
2
Since N d + 2p + 2 implies N-d p 2 1, and to I6A-N a direct simplification gives I3 S p3D) 22d+44 Ad No 2
Combining the bounds for T3, 14 and Is. we obtain the result.
Lemma K.3 (Chung-type lemma for a < 3). Let (Ex)a20 be sequence of positive real numbers. Suppose there exist K > 0, A > 0 and 0, 0 with S 3 such that for all k 2 0.
A
Sk-1 S exp
EN
(37)
kn
(ko + k 1
Then for any K 2 1,
K
(a/(ko+1) A K (ko + K)
EK S exp
-0
Ko
i
5o +
Σ
(ko + k))-0-1
(38)
k=1
Moreover, when a < B, Equation (38) can be further simplified to:
ho +
ea/(ko+1)
3
Eo +
(39)
ko + K
B -
(No + K)
Proof. Define for 2 1
A
am := expl
Ko + mm)
Cm
(ko + m))+1
Then we can reweite equation 37 as Ek-1 S aK41EE + Ck+1.
Unrolling the recursion gives
K
K
K
εK s E aj
II
a
a3
Ck
1=1
j=1
k=1
3=1
Note IT a; = expl a E
Using the standard bound
kotil
No + m
Ko + m log
log
S
ko +1
Ko +
ko + 1
ko + 1
we obtain for all 2
kn a
m
ko 1 kig + m
a/(koo)1)
ag
kip + m
Hence (II a,) 11 s ea/(kot1) (otkk and therefore
K E[I
Oj)
Ca S (kott))
A
(Ki + 1---8-1
(ko + 1)aa
k=1 1=1
k=1
Multiplying by II a3 S
1 kotk
yields equation 38.
When a < 3, since x + 2--8-1 8-1 decreasing and convex,
K
Ko + -11 s (kip + 8-1 (hip + -30-8-1 dr
(ki + 1)a-8
(ko + K)a-8
(ki + 1)a-8-1
8
(ko + 1)a
8 - a +
< (ki + 1)a-8-1
1
8
8 a
Plugging this into equation 38 and using [ aj S
kot1 a gives equation 39. KotR)
68

---

Published as a conference paper at ICLR 2026
Lemma K.4. Define
G = sup
max iE(n)
[
Then we have
G S D sup
|5: + D²
|100 w0'l
V
D2
|
(40)
(E(n)
24
Proof. By Section A.I in (Ahn al., 2020), we have
(F(w) F(uno)) {1/w rBl1? 5 F(wo) - F(1o)
2/1
Note that
F(wo) - -F(i)) = (wD :)) A (wo i
D2 ||
2
and
[f((w)] = (1: (w, will = 11(w" w. w;)x; + E,æ,]]
D|
D2 w- w|l s DI6,1 + D2 (120* 2001 + 11 20 wll)
Therefore,
G
sup
max DIE + D (1|2* - ا001 + 1|20 will
sE|n|
||00
2u || SV
D2
D sup iE(n)
12 + D2
|| - w01 || + V
||+ا||
24
Combining Lemma K.3, Equation (40) and Proposition 16 in (Ahn et al., 2020), we derive the following corollary.
Corollary K.1. For any K 2 1,
((suDietn) (5.1)² + D211
|2bl12 +
12 Dr
(3 4K)
w01l +
D
1|2
2p
Em .h 11200 K+ 1//l
(NK)a
(41)
Proof. Let a
2D (0. <0.,)). B:
C2( +
4kl and G. = Bl w for the global De
iterates {x:)T= (T NK). By Proposition 16 in (Ahn et al., 2020), for each update with stepsize lt.
641 S (1 mT 3/ + 4
1/D² 14t we obtain
Using 1 - S - and 17-
1 1/D'
3G² G. + D4(1 +t²
4kLG
G++1 S expl
1
06(1+1))
With a 2i and [1+4}² (Ittjz this simplifies to
G+1 S expl
a
B = G²
4xL
G +
+
1+1
(1 t)2
DI
D5
69

---

Published as a conference paper at ICLR 2026
Now apply Lemma K.3 with
Kg O,
a a,
==1,
A B,
at K = T = NK. This yields that
1
10
2ca
B
E E
K+1
w
(N ( )a
1 - a (NK)
|| Wwo
ub 1|
4vEG"
(3 + 4k)
D
(NK)
Recall that wh Combining this inequality with Equation (40), and note that (a + b c)² < 3(a² + 12 + )²), we have the result.
Lemma K.5. Define == 1D Then there exists constant No such that when N > No. we have
Cg
Elllor - u0|1 S
Cio8
(42)
(KN)av
Proof. Define X (x11 xN)
, (y1, yN) = (E1,... ,N)) T. We have
= (x) T x) y
(XT x) X (Xw" +
w² +x' x) X.g.
(43)
Thus
S o²d
Eell w²112 or (x x) -1
and
20 d nN
Ee |611 < 2 (1/20 - 20 20011 1|2+1111 11|00=11 S
+ 2| 211
Consequently, we have
EelEat 1wo / - :0|² 2 Cui + C12H C13
(NK)a
Therefore,
E
i w
w0113]=
E[ll -w'1221] + B|lla w" 1='1211
On
(
Xe
2
+ C12
2 Ad
+ C13
E [ICC + C12f + C1s) 1s].
(KN)a
By Lemma K.2, we have 1] < co when N > d d+5 8. Thus by Hölder and Pr(B) < 6x. [[[gg] < 1// Pr(B)) 1-1/2
Plugging these bounds into the previous display proves equation 42.
Now we begin the main part of the proof of Theorem K.2.
Proof of Theorem K.2. Note that through direct calculation, we have L(w) (wT w² Then
we can upper bound R(K, N: E):
E (WT w²)
H (WT w²)
R(K,N;
2
[T
+ w w") H H(Wr + i w²)
-E (H, (H, (ru w0 (w w T) B 1
H. (WT w))( 1))T)
+ E(wr w) H H( w")
Is + I + Is.
70

---

Published as a conference paper at ICLR 2026
Next, we characterize I6, 17 and Is separately. By Equation (43), we have
d Is - 2N
o²d
[I+
H
2N
We view o²d of the error term be given follows:
2N as the main term, and view
o'd
H,
H H-1
H-1) as the enror term. A naive bound
2N
EDd
H
H
ED2
H
H H H-1
D2 Adp
D Xa
H
H
2 H
By Lemma K.2, Eu < for some constant C independent of N; by Equation (34) and Proposition 2.5.2 in (Vershynin, 2018), we have E| have Is
H| S -N50.5 for some constant C. Therefore, we
s²d + o(1).
2N
By Lemma K.5, we can derive an upper bound for I7:
D E WT u 12 1 (KN)
D
Co
+ CCoVoxN
I7 S
where ON = o (N-1).
Is be bounded by Is and 17 using the Cauchy-Schwarz/ing inequality:
Is H 0.5 (wr - w), H w²)) - /TT, 2V
By letting + oo and combining the characterizations of Ic. 17 and 1g. we obtain the result.
Theorem K.2 together with Theorem K.1 gives characterization for Fl N). Specifically, solve
add (1 o(1)) Ri N. E) B, E)) 2N
Co
N
Thus we have
Eloo, N) 2 2CRH-
E(oo, N) grows linearly with the condition number KH, which can be arbitrarily large. This proves that under practical training setups using polynomial learning rate schedules, multi-epoch training shows a significant advantage over one-pass training.
71


Reviews:
[{"review_id": "O7JXCqHYeE", "reviewer": "Reviewer_tXco", "summary": "This paper studies the question: how large of a dataset is required for one-pass training to match the loss of a dataset of size N trained for K epochs?\n\nThey theoretically characterize the scaling behavior for SGD in linear regression in two settings: strong convexity and Zipf-distributed data. In each settings, there are two phases, one phase where K is small and data can be repeated without harm to the performance, and one where K is large and reused data plateaus in usefulness. The point where this phase transition occurs depends on the setting (strongly convex vs Zipf-distributed data) and the data distribution.\n\nIn contrast to recent empirical work, their analysis supports a functional form where the number of times you can repeat the dataset grows with the size of the dataset. In other words, the practical takeaway is that larger datasets can be repeated more.\n\nThey perform LLM pretraining experiments where they take different size datasets, train them for 100 epochs, extract the loss after varying numbers of epochs, and compare to a 200B dataset trained for one epoch. The experiments validate the small K regime where data reuse doesn't hurt performance significantly, and that the larger datasets can be repeated more.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This is a very nice paper. The core question in the paper is important and well-framed and finding an interesting but tractable theoretical analysis is a valuable contribution. Solving the linear regression problem in both the strongly convex and Zipf distribution settings is valuable and illustrated the dependence on the data distribution exponent. The proof sketch gave nice intuition about the approach and which techniques were used to bound which terms. The LLM experiments give useful validation of the key takeaways (illustrating the small K regime where data reuse is not harmful, and showing that the effective reuse ratio increases with the dataset size).", "weaknesses": "All of the LLM experiments use a constant learning rate schedule with AdamW, rather than some form of learning rate decay (e.g. cosine) as is required for competitive performance in practice. This is a reasonable limitation of a primarily theoretical paper as using a time-horizon-dependent learning rate schedule would require training separate models for every different number of epochs, requiring substantially more compute.\n\n(Similarly, they use the same peak learning rate for all the training runs, and this should likely be tuned for each dataset size and number of epochs, but again this would require substantial compute.)\n\nIn particular, there may be an interaction between the learning rate decay and the bias-variance decomposition (i.e. the learning rate decay at the end of training reduces the gradient noise and \"reveals\" how much the model learned from the repeated data).\n\nTo capture the effects of learning rate decay without requiring significantly more compute, one approach would be to load the existing checkpoints (perhaps from a small number of steps before the end of training), then perform linear learning rate decay to zero across a small number of steps. This would produce a \"trapezoidal\" learning rate schedule for each setting without needing to train a model from scratch for each distinct number of epochs. Then the final decayed losses could be plotted / analyzed as is already done in Figure 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SzJw0akHp1", "reviewer": "Reviewer_V6sv", "summary": "This paper challenges prior work that assumed the effective reuse rate of data is independent of dataset size. Through rigorous theoretical analysis in linear regression, the authors demonstrate that larger datasets can be trained for more epochs before experiencing diminishing returns. Specifically, they show that the effective reuse rate E(K,N) depends not only on the number of epochs K, but critically on the dataset size N, which is a factor overlooked in previous empirical scaling laws.", "questions": "1. Could the authors provide a clearer distinction between this work and prior theoretical studies, especially Lin et al. (2025)? While the paper mentions providing \"o(1) relative error\" versus \"Θ(K)\" bounds, it would be helpful to understand what new insights or capabilities this precision enables.\n2. Could the authors clarify the practical utility of these theoretical findings? Specifically, how should practitioners use the E(K,N) ≈ log(N) saturation result to inform training decisions, given that most modern LLMs train for fewer than 5 epochs?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents rigorous theoretical analysis with precise characterizations of the effective reuse rate E(K,N) under both strongly convex and Zipf-distributed settings.\n2. The central insight that larger datasets can be repeated more times is clearly articulated and challenges existing assumptions in the field.\n3. The theoretical predictions are thoroughly validated through two complementary approaches: controlled simulations on synthetic data and large-scale LLM pretraining experiments (up to 200B tokens), both of which strongly support the main hypothesis.", "weaknesses": "1. The overall conclusions are very similar to the previous work \"Improved scaling laws in linear regression via data reuse\". \n2. And the paper still lacks sufficient practical evidence from LLMs. It is well established that LLM performance differs significantly between large and small models. A more meaningful experiment would be to scale across different model sizes and examine how the effective reuse rate varies with model capacity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xIVqKegPGT", "reviewer": "Reviewer_2N8u", "summary": "This paper presents a theoretical analysis of multi-epoch training for large-scale models, a common practice when high-quality training data is limited. The authors introduce a metric called the \"effective reuse rate,\" $E(K, N)$, to quantify how many additional \"fresh\" data samples one-pass training would need to match the performance of training for K epochs on a dataset of size N. Through a detailed analysis of Stochastic Gradient Descent (SGD) in linear regression, they demonstrate two key regimes: 1) for a small number of epochs (K), the benefit is nearly linear (E(K, N) ≈ K), meaning each pass is almost as good as seeing new data; 2) as K increases, the benefit saturates. Crucially, they prove that the saturation point itself grows with the dataset size N (e.g., logarithmically or as a power of N). This central finding—\"larger datasets can be repeated more\"—challenges previous empirical work that suggested the reuse rate was independent of N. The authors validate this theoretical insight with both synthetic data simulations and pre-training experiments on a large language model.", "questions": "n/a", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a principled and rigorous theoretical framework to analyze the widely used but poorly understood practice of multi-epoch training. The introduction of the \"effective reuse rate\" E(K, N) is a clear and valuable conceptual contribution. The key finding that the benefit of data reuse scales with the dataset size (N) is a significant insight. It provides a concrete guideline for practitioners: one can and should repeat larger datasets more times before expecting diminishing returns. This directly refutes a simpler assumption from prior empirical work, making a clear and important contribution to the field of scaling laws.\n\n2. While the core theoretical results are derived in the simplified setting of linear regression, the authors do an excellent job of validating their main qualitative finding with an actual LLM pre-training experiment (Section 6.3). This strengthens the paper's claims significantly and shows that the core intuition derived from theory holds in a much more complex, real-world scenario.\n\n3. The paper is well-written and structured.", "weaknesses": "1. The primary limitation is the gap between the theoretical setting (linear regression with SGD) and the practical setting of interest (Transformer-based LLMs trained with AdamW). Linear models cannot capture the complex, non-linear feature learning that occurs in deep networks. While the qualitative findings transfer, the exact quantitative predictions (e.g., the saturation point scaling as Θ(log N)) may not hold for Transformers. This is a standard and often necessary simplification in theoretical work, but it's an important caveat.\n\n2. The theory is developed for Mean Squared Error (MSE) loss, which is standard for regression. However, LLMs are almost universally trained using a cross-entropy loss. These two loss functions have different properties, and it's not immediately obvious if the scaling dynamics would be identical. \n\n3. While the inclusion of LLM experiments is a major strength, their scope is naturally limited by computational cost. The experiments use a 0.3B parameter model. While this provides strong evidence, it does not definitively prove the same scaling behavior would be observed in much larger, state-of-the-art models, where different phenomena might emerge.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DwPuDWrQK4", "reviewer": "Reviewer_H78L", "summary": "This paper presents a theoretical framework for understanding multi-epoch data reuse in the context of linear regression and its implications for data-scaling laws in large model training. It shows that larger datasets can be repeated more times effectively. Simulation and LLM pretraining experiments confirm the theory’s predictions.", "questions": "1. Theoretically, the paper suggests that a dataset of size N can be effectively “amplified” by a factor of log N through multi-epoch training.\nIf that interpretation is correct, why do modern LLMs only have 4 with billions of tokens?\nDoes this discrepancy imply that current LLMs operate beyond the idealized regime assumed in the theory (e.g., due to non-convexity, heavy-tailed data, or curriculum effects)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Valuable theoretical insights: The discussion of how larger datasets (N) allow more effective reuse is both novel and practically relevant.\n2. Solid theoretical foundation under two regimes: The analysis is carefully constructed for both strongly convex and Zipf-distributed settings.\n3. The experiment empirically confirms the theory’s predictions.", "weaknesses": "1. Limited discussion of “depends on the data size and distribution.”\nWhile the paper acknowledges that E(K, N) depends on both dataset size and distribution, the explanation remains mostly theoretical. More quantitative or illustrative examples—especially for large-scale LLM pretraining where data heterogeneity and long-tail effects dominate—would make this claim more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)