Larger Datasets Can Be Repeated More: A Theoretical Analysis of Multi-Epoch Scaling in Linear Regression

• URL: http://arxiv.org/abs/2511.13421v1
• Date: Mon, 17 Nov 2025 14:34:03 GMT
• Title: 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,
• Abstract summary: This paper presents a theoretical analysis of how a common workaround, training for epochs, reshapes training in linear regression.<n>We quantify this using the textiteffective reuse rate of the data, $E(K, N)$, which we define as the multiplicative factor by which the dataset must grow.<n>Our results reveal that the maximum $K$ value for which $E(K, N) approx K$ in fact depends on the data size and distribution.
• Score: 18.692159157168803
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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$ ($Θ(\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 (Muennighoff et al. (2023)), 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.

Related papers

• Improved Scaling Laws in Linear Regression via Data Reuse [36.110514249309254]
  We show that data reuse can improve existing scaling laws in linear regression.<n>This suggests an improved scaling law via data reuse (i.e., choosing $L>N$) in data-constrained regimes.
  arXiv  Detail & Related papers  (2025-06-10T03:39:29Z)
• Data Selection for ERMs [67.57726352698933]
  We study how well can $mathcalA$ perform when trained on at most $nll N$ data points selected from a population of $N$ points.<n>Our results include optimal data-selection bounds for mean estimation, linear classification, and linear regression.
  arXiv  Detail & Related papers  (2025-04-20T11:26:01Z)
• Nearly Optimal Differentially Private ReLU Regression [18.599299269974498]
  We investigate one of the most fundamental non learning problems, ReLU regression, in the Differential Privacy (DP) model.<n>We relax the requirement of $epsilon$ and public data by proposing and analyzing a one-pass mini-batch Generalized Model Perceptron algorithm.
  arXiv  Detail & Related papers  (2025-03-08T02:09:47Z)
• Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification [50.717692060500696]
  Next-token prediction with the logarithmic loss is a cornerstone of autoregressive sequence modeling.<n>Next-token prediction can be made robust so as to achieve $C=tilde O(H)$, representing moderate error amplification.<n>No computationally efficient algorithm can achieve sub-polynomial approximation factor $C=e(log H)1-Omega(1)$.
  arXiv  Detail & Related papers  (2025-02-18T02:52:00Z)
• One-Bit Quantization and Sparsification for Multiclass Linear Classification with Strong Regularization [18.427215139020625]
  We show that the best classification is achieved when $f(cdot) = |cdot|2$ and $lambda to infty$. It is often possible to find sparse and one-bit solutions that perform almost as well as one corresponding to $f(cdot) = |cdot|_infty$ in the large $lambda$ regime.
  arXiv  Detail & Related papers  (2024-02-16T06:39:40Z)
• Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations [51.14495595270775]
  We adapt the Frank-Wolfe algorithm for $L_1$ penalized linear regression to be aware of sparse inputs and to use them effectively. Our results demonstrate that this procedure can reduce runtime by a factor of up to $2,200times$, depending on the value of the privacy parameter $epsilon$ and the sparsity of the dataset.
  arXiv  Detail & Related papers  (2023-10-30T19:52:43Z)
• You can't pick your neighbors, or can you? When and how to rely on retrieval in the $k$NN-LM [65.74934004876914]
  Retrieval-enhanced language models (LMs) condition their predictions on text retrieved from large external datastores. One such approach, the $k$NN-LM, interpolates any existing LM's predictions with the output of a $k$-nearest neighbors model. We empirically measure the effectiveness of our approach on two English language modeling datasets.
  arXiv  Detail & Related papers  (2022-10-28T02:57:40Z)
• Easy Differentially Private Linear Regression [16.325734286930764]
  We study an algorithm which uses the exponential mechanism to select a model with high Tukey depth from a collection of non-private regression models. We find that this algorithm obtains strong empirical performance in the data-rich setting.
  arXiv  Detail & Related papers  (2022-08-15T17:42:27Z)
• $p$-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets [74.37849422071206]
  We study the $p$-generalized probit regression model, which is a generalized linear model for binary responses. We show how the maximum likelihood estimator for $p$-generalized probit regression can be approximated efficiently up to a factor of $(1+varepsilon)$ on large data.
  arXiv  Detail & Related papers  (2022-03-25T10:54:41Z)
• Datamodels: Predicting Predictions from Training Data [86.66720175866415]
  We present a conceptual framework, datamodeling, for analyzing the behavior of a model class in terms of the training data. We show that even simple linear datamodels can successfully predict model outputs.
  arXiv  Detail & Related papers  (2022-02-01T18:15:24Z)
• Dynamics of Local Elasticity During Training of Neural Nets [7.9140338281956835]
  "Local elasticity" attempts to quantify the propagation of the influence of a sampled data point on the prediction at another data. We show that our new proposal of $S_rm rel$, as opposed to the original definition, much more sharply detects the property of the weight updates.
  arXiv  Detail & Related papers  (2021-11-01T18:00:14Z)
• A Neural Scaling Law from the Dimension of the Data Manifold [8.656787568717252]
  When data is plentiful, the loss achieved by well-trained neural networks scales as a power-law $L propto N-alpha$ in the number of network parameters $N$. The scaling law can be explained if neural models are effectively just performing regression on a data manifold of intrinsic dimension $d$. This simple theory predicts that the scaling exponents $alpha approx 4/d$ for cross-entropy and mean-squared error losses.
  arXiv  Detail & Related papers  (2020-04-22T19:16:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.