Scaling laws for learning with real and surrogate data

Authors: ayush  jain
andrea  montanari
eren  sasoglu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:50:38

Abstract: Collecting large quantities of high-quality data can be  prohibitively expensive or impractical, and a bottleneck in machine learning. One may instead augment a small set of $n$ data points from the target distribution with data from more accessible sources, e.g. data collected under different circumstances or synthesized by generative models. We refer to such data  as `surrogate data'. We study a weighted empirical risk minimization (ERM) approach for integrating surrogate data into training. We analyze mathematically this method under several classical statistical models, and validate our findings empirically on datasets from different domains. Our main findings are: $(i)$ Integrating surrogate data can significantly reduce the test error on the original distribution. Surprisingly, this can happen even when the surrogate data is unrelated to the original ones. We trace back this behavior to the classical Stein's paradox. $(ii)$ In order to reap the benefit of surrogate data, it is crucial to use optimally weighted ERM. $(iii)$ The test error of models trained on mixtures of real and surrogate data is approximately described by a scaling law. This scaling law can be used to predict the optimal weighting scheme, and to choose the amount of surrogate data to add.

Main paper: 
 introduction and overview 1.motivation and formulation: 
 Consider a standard learning setting where we are given n i.i.d. points z i from a target distribution D. Given a family of parametric models governed by the parameters' vector θ, the goal is to find θ that minimizes the expected test loss R test (θ) incurred by the model predictions, where expectation is taken over the distribution D. In many application domains, the available data Z = (z i ) i≤n from the target distribution, referred to as either real or original data, may be difficult or expensive to acquire. One may then attempt to supplement these data with a different, cheaper source. Examples of such cheaper sources are (i) publicly available datasets; (ii) datasets owned by the same research group or company but acquired in different circumstances, e.g. in a different location; (iii) synthetic data produced by a generative model.We will denote the data points obtained from this source by z s i , and assume we have m of them. We assume the 'surrogate' data Z s = (z s i ) i≤m to be i.i.d. samples with distribution D s . In general, we will not assume the distribution D s of synthetic data to be close to the original data distribution D. However we assume that these distributions are over the same domain. A number of questions arise: (i) How should we use the surrogate data in training? (ii) How many surrogate samples should we add to the original data? (iii) Can we predict the improvement in test error achieved by adding surrogate samples to the training?A natural approach would be to add the surrogate data to the original one in the usual training procedure, and indeed many authors have explored this approach (see Section 1.3). Namely, one attempts to minimize the overall empirical risk R naive n+m (θ) = n i=1 ℓ(θ; z i ) + m i=1 ℓ(θ; z s i ), where ℓ(z, θ) is a train loss function.However, a moment of reflection reveals that this approach has serious shortcomings. Consider a simple mean estimation problem, whereby z i ∼ N(θ * , I d ), z s i ∼ N(θ s * , I d ), ℓ(θ; z) = ∥θ -z∥ 2 , and R test (θ) = ∥θ -θ * ∥ 2 . A straightforward calculation yields that the test error of the empirical risk minimizer θnaive n+m := arg min R naive n+m (θ) isEQUATIONAs m increases the variance (the second term) decreases, but the bias due to the difference ∥θ s * -θ * ∥ increases, and the error approaches ∥θ s * -θ * ∥ 2 , i.e. the model will be only as good as if training only on surrogate data.In order to overcome these limitations, we study a weighted ERM approach, and will show that the weight plays a crucial role. Namely, we consider the following regularized empirical risk:EQUATIONwhere α ∈ [0, 1] is the weight of the surrogate dataset and Ω : R d → R ≥0 is a regularizer, e.g. a ridge Ω(θ) = λ∥θ∥ 2 2 . We denote by θn,m (α) := arg min θ R n,m (θ; α)the corresponding empirical risk minimizer, and by R test ( θn,m (α)) the corresponding test error.For supervised learning tasks, a sample z is represented as z = (y, x), where x ∈ R d is covariate vector and y ∈ R is response variable and θ parametrizes a family of models f (x; θ) that predict the response y given covariate vector x. We consider losses of the form ℓ(θ, z) = L(y, f (x; θ)) and R test (θ) := E z∼D L test (y, f (x; θ)) for some functions L and L test . We allow for the test loss L test to be different from the train loss L, but we will omit the subscript 'test' from the risk R and the loss L whenever clear from the context.Figure 1 provides a preview of our results, for a sentiment analysis task. (Technical details provided in Section 4 and Appendix A.3). Each frame corresponds to a different combination of n and m, and we report the test error of our approach as a function of the weight parameter α (red circles). Solid lines report the prediction of a scaling law that will be one of the main results presented below.We observe that the weighted ERM approach systematically achieves better test error than either training only on original data (α → 0) or on surrogate data (α → 1). Further the error for optimal α is always monotone decreasing both in m and n, and the approach outperforms the naive unweighted approach. This is shown more clearly in Figure 2 , which also shows that the performance of unweighted ERM can degrade with more surrogate data. Also, while scaling laws typically do not capture the dependence on hyperparameters, the scaling law presented below predicts the dependence on α reasonably well. This is particularly useful, because such a scaling law can be used to tune α optimally and to predict the amount of surrogate data needed.We study the method outlined above both mathematically and via numerical experiments. Our mathematical results are developed in four different settings: (i) The Gaussian sequence model (Section 3.1); (ii) A non-parametric function estimation setting (Section 3.2); (iii) Low-dimensional empirical-risk minimization (Section 3.3); (iv) High dimensional ridge regression (Section 3.4);We carry out experiments with the following data sources. (1) Simulated data from linear or Gaussian mixture models: this allows us to explicitly control the distribution shift between the original and Figure 2 : Performance of unweighted vs weighted ERM approach for the setting in Figure 1 surrogate datasets, as well as check our theoretical results in a controlled setting.(2) Real natural language processing (NLP) data for sentiment analysis, with the role of original dataset played by IMDB reviews and the role of surrogate datasets played respectively by Rotten Tomatoes review and Goodreads book reviews.(3) Progression-free survival analysis using Lasso on TCGA PanCancer dataset with female patients data and male patients data as original and surrogate data, respectively.(4) Real image classification data, with CIFAR-10 and CIFAR-100 datasets respectively playing the role of original and surrogate data. Our results support the following conclusions:Surrogate data improve test error. Including surrogate data in training generally improves the test error on the original data, even if the surrogate data distribution is far from the original one. In agreement with the interpretation of surrogate data as a regularizer (see also Sec. 2), the improvement is generally positive, although its size depend on the data distributions.Tuning of α. The above conclusion holds under the condition that α can be tuned (nearly) optimally.For each of the theoretical settings already mentioned, we characterize this optimal value. We verify that nearly optimal α can be effectively selected by minimizing the error on a validation split of the original data. An attractive alternative is to use the scaling law we discuss next.Scaling law. We propose a scaling law that captures the behavior of the test error with n, m, α:R( θn,m (α)) -R * ≈ α 2 R ex su (∞) + α 2 R ex su (m) -R ex su (∞) 1/β + (1 -α) 2 R ex or (n) 1/β β . (4) Here R * is the minimal (Bayes) error, R ex su (m) := R( θ0,m (1)) -R * is the excess test error when training on the surrogate data (and testing on original), R ex or (n) := R( θn,0 (0)) -R * is the excess test error1 when training on original data (and testing on original), and β is a scaling exponent as described in Section 4. The above scaling admits natural generalizations; see Section 5.Practical uses of the scaling law. Given data {z i } i≤n and a source of surrogate data, we would like to predict how much the test error can be decreased by including any number m of surrogate samples in the mix. The scaling law (4) suggests a simple approach: (1) Learn models on purely original data to extract the behavior of test loss R( θn,0 (0)).; (2) Learn models on purely surrogate data to extract the behavior of R( θ0,m (1)). (A relatively small sample is sufficient for this step.) (3) Use the minimum over α of Eq. (4) to predict the test error at any given pair n, m.We can further leverage the scaling law to achieve the desired error by: (I) Using the scaling law to determine the number of surrogate samples needed to achieve the desired performance. (II) Acquiring the surrogate samples and train the model using weighted ERM with optimal weighting predicted by scaling law.The use of surrogate data to enhance training has attracted increasing research effort, also because of the recent progresses in generative modeling. This line of work has largely focused on the techniques to generate synthetic data that are well suited for training. A wide variety of methods have been demonstrated to be useful in generating data for computer vision tasks, ranging from object classification to semantic segmentation [RSM + 16, JRBM + 17, AAMM + 18, TPA + 18, CLCG19, HSY + 22, MPT + 22, YCFB + 22]. We refer to [SLW20] for a review. More recently, synthetic data have been used for training in natural language processing [HNK + 22, MHZH22].Scaling laws have been broadly successful in guiding the development of large machine learning models [HNA + 17, RRBS19, HKK + 20, KMH + 20, TDR + 21, HKHM21, HBM + 22, ANZ22, MRB + 23]. We expect them to be similarly useful for integrating heterogeneous data into training. The change in scaling laws when training on synthetic data was the subject of a recent empirical study [FCK + 23]. On the other hand, no systematic attempt was made at integrating real and synthetic data.In data augmentation [KSH12, SK19], the original samples are supplemented with transformed or noisy version of the same. In contrast, we assume that surrogate data is obtained from a different source than the original one, and the surrogate samples are independent of the original samples.The problem we consider was also studied within 'domain adaptation', a subarea of transfer learning [MPRP16, TJJ20]. Among others, [BDBC + 10] establishes bounds on the generalization error of weighted ERM via uniform convergence. However these bounds do not reveal the full advantage achieved by this approach and are not precise enough to justify the scaling laws that we derive. Recent works in domain adaptation study the behavior of test error error [Has21, KJSJ24, YLS + 24] and its scaling laws [Has21] , but only consider vanilla ERM, a special of weighted ERM considered here.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: These claims are justified by our theorems and the experimental results.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
regularization, gaussian mean estimation, stein paradox: 
 The role of the parameter α can be understood by considering the limit m → ∞:R n,∞ (θ; α) = 1-α n n i=1 ℓ(θ; z i ) + α R s (θ) + Ω(θ) ,and R s (θ) = E z s ∼D s ℓ(θ; z s ) is the population risk for surrogate data. This suggests to think of the surrogate data as an additional (highly non-trivial) regularizer, with parameter α. This leads to a simple yet important insight: adding surrogate data to the original data is beneficial if α is chosen optimally, and large m reduces statistical fluctuations in this regularizer. This contrasts with the unweighted approach whose test error in general deteriorates for large m.As a toy example, reconsider the mean estimation problem mentioned in the introduction:z i ∼ N(θ * , I d ) and z s i ∼ N(θ s * , I d ), ℓ(θ; z) = ∥θ -z∥ 2 and R test (θ) = ∥θ -θ * ∥ 2 . We have θn,m (α) = (1 -α) i≤n z i /n + α i≤m z s i /m.In other words, the weighted ERM shrinks the mean of the original data towards the mean of the surrogate data. For a given α, the resulting test errors areEQUATIONand for the optimum value α * = arg min α R( θn,m (α)), this yieldsEQUATIONNote that 1/n is the error of training only on original data and the prefactor is always strictly smaller than one. Hence, weighted ERM always achieves better error than training only on original data, regardless of the distance between original and surrogate data, although the improvement is larger for small R ex su (∞). This might seem paradoxical at first. As mentioned above, we are shrinking towards an arbitrary point given by the empirical mean of the surrogate data: how can this help?In fact, this is a disguised version of the celebrated Stein paradox [EM77, Ste81] : in estimating a Gaussian mean, a procedure that shrinks the empirical mean towards an arbitrary point by a carefully chosen amount outperforms the naive empirical mean. In our toy example, the naive empirical mean corresponds to estimation purely based on the original data, and we shrink it towards the mean of the surrogate data. Of course, the improvement over empirical mean is only possible if α is chosen optimally. Equation (6) assumes α = α * is chosen by an oracle that knows the value of R ex su (∞). Stein's analysis implies that in the Gaussian mean problem, α can be chosen empirically as long as the dimension of θ is d ≥ 3. In the settings we are interested in, α can be chosen via cross-validation.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: We discuss it in Section 5.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
gaussian sequence model: 
 The sequence model captures the behavior of many models in non-parametric statistics while being simpler to analyze [Tsy09, GN21] . It is also known to approximate the behavior of overparametrized linear regression [CM22] . The unknown target is θ * ∈ R d (with potentially d = ∞), and we observeEQUATIONwhere θ s * is also unknown, and g i , g s i ∼ N(0, I d ) are i.i.d. We study the penalized estimator θn,m (α) := arg min θEQUATIONwhere ∥θ∥ 2 Ω = ⟨θ, Ωθ⟩ and Ω ⪰ 0 is a regularization weight matrix. We will be concerned with the expected riskEQUATION)The proof of the next result is presented in Appendix C. Theorem 1. Let ω 1 ≤ ω 2 ≤ •≍ k µ , µ > 1/2, ∥θ * ,>k ∥ 2 ≤ C θ k -2ρ, ρ ̸ = µ, and let ∆ k be such that (for all k): µ∧ρ) . Then the following hold:∆ k := ω -1 k |⟨θ * ,≤k -θ s * ,≤k , θ * ,≤k ⟩ Ω | ≤ C 0 k -2((a) There exists an explicit λ * (α) such that, lettingEQUATION) (b) If µ > 2ρ -1/2, there exists C ′ > 0 and there exist θ * , θ s * satisfying the assumptions in point (a), such that,EQUATIONNote that since the theorem also implies R ex su (m) -R ex su (∞) ≍ (σ 2 s /m) β and R ex or (m) ≍ (σ 2 /n) β , this result confirms the scaling law (4).In this section we consider the classic non-parametric regression model. We assume that n = Q d for some integer Q ≥ 2, and the original data (x i , y i ) i≤n are defined throughEQUATIONwhere ε i are independent of x i and of each other, and {x i } i≤n equally spaced grid points in the d-dimensional unit-cube, i.e. X n = {q/Q : q ∈ [Q] d }. Surrogate data have a similar distribution, with m = Q d s equally spaced points x s i in the unit cube, and y s i = f * ,s (x s i )+ε s i , where ε s i ∼ N(0, σ 2 s ). We assume that f * has small Sobolev norm, that is,∥f * ∥ 2 r,2 := [0,1] d |f * (t)| 2 + ∥f (r) * (t)∥ 2 dt ≤ 1 .Recall that ∥f ∥ 2 r,2 is a special reproducing kernel Hilbert space (RKHS) norm: we expect some of the considerations below to generalize to other RKHS norms.Following our general methodology, we use the estimatorEQUATIONWe are interested in R(f ) = E{(f (x) -f * (x)) 2 }, which is the excess squared loss for a test pointx ∼ Unif([0, 1] d ).In order to avoid technical burden we will carry out the analysis for a continuous model, the socalled white noise model, where we observe the function f at all points x ∈ [0, 1] d , perturbed by d-dimensional white noise:EQUATIONand similarly for Y s . We use an estimator that naturally generalizes (13) to the continuous case. Our results for the white noise model are as follows.Theorem 2. Let β = (2p ∧ 4r)/(d + (2p ∧ 4r)). If r > d/4 and λ = (δK n,m σ 2 ) 2r/(d+(2p∧4r)) , then for every δ ∈ (0, 1) there exists a constantEQUATIONwith high probability, where With the given choice of λ, r, the derivation of (15) also impliesK n,m := (1 -α) 2 /n + α 2 /m. RemarkR ex su (m) -R ex su (∞) ≥ C ′ (σ 2 s /m) β , R ex or (n) ≥ C ′ (σ/n) β (for the least favorable f [Tsy09]). Hence (15) is consistent with the scaling law (4).We study the estimator of Eqs. (2), (3) under the classical asymptotics n, m → ∞ at d fixed. Since this type of analysis is more standard, we defer it to Appendix B. The main result of this analysis is that the scaling law (4) holds in this setting, with the classical parametric exponent β = 1, for α ∈ [0, α max ] for a suitable α max ∈ (0, 1). Importantly, the interval [0, α max ] includes the optimal choice of the weight α.In this section, we study ridge regression in the high-dimensional regime in which the number of samples is proportional to the number of parameters. Denoting the original data by (y, X) (with y ∈ R n the vector of responses and X ∈ R n×d the matrix of covariates), and the surrogate data by (y s , X s ) (with y s ∈ R m and X s ∈ R m×d ), we minimize the regularized empirical riskEQUATIONWe assume a simple distribution, whereby the rows of X, X s (denoted by x i , x s i ) are standard normal vectors andEQUATION) for ε ∼ N(0, σ 2 I n ), ε s ∼ N(0, σ 2 s I m ).Note that the two data distributions differ in the true coefficient vectors θ * versus θ s * as well as in the noise variance. We will denote by θn,m (α) the ridge estimator, θn,m (α) = arg min θ∈R d R n,m (θ; α).The excess test error (for square loss) is given by R( θ) := E ⟨x, θ * ⟩ -⟨x, θ⟩ 2 = ∥ θ -θ * ∥ 2 .The next result characterizes this error in the proportional asymptotics.Theorem 3. Consider the ridge regression estimator θn,m (α). Let r := ∥θ * ∥ 2 , r s := ∥θ s * ∥ 2 andγ := cos -1 (⟨θ * , θ s * ⟩/(∥θ * ∥ 2 ∥θ s * ∥ 2 )). Assume n, m, d → ∞ such that n/d → δ, m/d → δ s , with δ + δ s > 1 2 . For R(.) defined in Appendix E.1, let ξ * (α), ξ * ⊥ (α), ω * (α) = argmin ξ,ξ ⊥ ≥0,ω≥0 R(ξ, ξ ⊥, ω; α), be the unique minimizer. Then for any ε, ε 0 > 0, there exist c > 0 such that, for all nP sup α∈[ε0,1-ε0] R( θn,m (α)) -R test (α) ≤ ε ≥ 1 -2 e -cn ,where R test (α) := (ξ * (α) -r)2 + (ξ * ⊥ (α)) 2 + (ω * (α)) 2 . Further, we can take ε 0 = 0 if δ, δ s > 1. Remark 3.2 (Optimizing α over the validation set). Note that the concentration of R( θn,m (α)) around the theoretical prediction R test (α) in Theorem 3 is uniform over α ∈ [ε 0 , 1 -ε 0 ]. This means that we can find the optimal α by computing θn,m (α) over a grid of α values, estimating R( θn,m (α)) over the validation set and choosing the optimal α. The uniform guarantee insures that this procedure will achieve risk min α∈[0,1] R test (α) + o P (1).Remark 3.3 (Relation to scaling laws). An analysis of the equations for (ξ * , ξ * ⊥ , ω * ) reveals that, for large δ, δ s , the predicted excess risk behaves asR test (α) = α 2 R * s,∞ + α 2 C 1 /δ s + (1 -α) 2 C 2 /δ + o(1/δ, 1/δ s ) (for some constants R * s,∞ , C 1 , C 2 ). This matches the low-dimensional asymptotics and our scaling law (4) with β = 1. In practice, we find that, for moderate δ, δ s , the behavior of R test (α) is better approximated by a different value of β (see Appendix A.)Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
empirical results: 
 In this section, we present experiments validating that the scaling law (4) is a good approximation both for simulated and real-world data. For simulated data, we select two different distributions for the original and surrogate datasets. The test and validation sets are generated from the same distribution as the original dataset. In case of real-world data, we choose two different datasets as the original and surrogate datasets. We split the original dataset into train, test, and validation sets, while all examples in the surrogate datasets are allocated solely to the train split.For each dataset and model discussed in this section, we carry out the same experiment: (i) We use models trained on original data to fit the scaling curve R( θn,0 (0)) = A or + B or n -βor and obtain A or and β or (ii) We use models trained on purely surrogate data to fit the scaling curve R( θ0,m (1)) = A su + B su m -βsu to obtain A su and β su . (iii) Since assume R * = R( θ∞,0 (0)), we letR * = A or and excess risk estimates R ex or (n) = R( θn,0 (0)) -A or , R ex su (m) = R( θ0,m (1)) -A or and R ex su (∞) = A su -Aor , and we use β = β or , the fit exponent obtained from original data); (iv) For each combination of n, m, we use our estimates of R ex su (m), R ex or (n) (as measured empirically on the test set), β, R ex su (∞), and R * to plot the predicted R( θn,m (α)) as a function of α using scaling law (4). (v) We then train the model using n original and m surrogate examples with weights (1 -α) and, α for the two datasets, respectively. We average the results of 10 independent runs to compare it against those predicted by the scaling law. For ridge regression, we also compare with exact high-dimensional asymptotics from Theorem 3.Let us emphasize that these plots probe the dependence on the hyperparameter α. These are much more demanding tests that the usual ones in scaling laws. We generally observe that the scaling law captures well the behavior of the test error for data mixtures. Furthermore, we perform experiments for variety of loss functions to show these scaling laws hold more widely than the theoretical settings we considered.Binary classification with Gaussian mixture data This is a simple simulated setting. The original dataset consists of independent and identically distributed examples(y i , x i ) ∈ R × R d , d = 200, where y i is uniform over {+1, -1}, and x i yi ∼ N(y i θ * , I d ), where θ * ∈ R d , ∥θ * ∥ = 1. Surrogate data have the same distribution, with a different unit vector θ * ,s . This data distribution is parametrized by d and the angle γ between the original and surrogate parameters, cos γ := ⟨θ * , θ * ,s ⟩. We use γ = π/10 in our experiments. For each (n, m, α), we averaged the results over 10 independent runs.(2) A one-hidden layer neural network with 32 hidden ReLU neurons. The results for both models are presented in Appendix A.1.Linear regression with Gaussian mixture data For the Gaussian mixture data generation setup described above, we also perform ridge regression. The results (presented in Appendix A.2) demonstrate that classification loss and square loss often have a similar qualitative behavior as a function of weight α, as seen by comparing the classification loss in Figure 7 and the squared loss in Figure 11 for the same setup. Although our theoretical results do not apply directly to classification loss, we believe that our qualitative conclusions generalize. This is confirmed by the similar behavior between the two losses and the successful prediction of actual risk by scaling laws in our classification experiments. As original data, we use the IMDB dataset (link) which has 25k reviews for training, each labeled as positive or negative. For validation and testing, we split the IMDB test dataset of 25k reviews into a validation set of 10k reviews and test set of 15k reviews.We experiment with two different surrogate datasets: 1) Rotten Tomatoes dataset of movie reviews (link): these are data with different distribution but within the same domain. This dataset contains movie reviews and the corresponding sentiments, 2) Goodreads book reviews (link): these are data from a substantially different domain. This dataset has reviews and their ratings. We choose 10k reviews each with a rating of 5 and 1, and label them as positive and negative, respectively.We convert reviews into feature vectors with d = 884 dimensions as explained in Appendix A.3. We use logistic regression and neural network models with the same set of parameters as in the Gaussian mixture experiments (except for the input dimension).Results with neural nets and Rotten Tomatoes as synthetic dataset are presented in Figure 1 and the remaining results are in Appendix A.3.We use 50,000 CIFAR10 training images as original data, its 10 classes for the classification task, and test on the 10,000 CIFAR10 test images. We use 50,000 CIFAR100 training images as surrogate data. We train a 9-layer ResNet model for classification. Appendix A.4 presents details on the data pre-processing and mapping of labels.Results are shown in Figure 3 . Note that CIFAR10 and CIFAR100 datasets are quite different from each other, as they have no overlap either in the images or in their label sets. Yet, the test error on training on their mixture is well predicted by the scaling law (4).Lasso-based Cox regression on TCGA PanCancer dataset We use the public domain TCGA pancancer dataset [GCH + 20] (link), with gene expressions as covariates and progression-free survival (PFS) as response. After filtering and feature selection, we are left with 3580 female patients, which we use as original data, and 3640 male patients, which we use as surrogate data. We fit CoxPHFitter model (link) with 500 selected genes and use "1-concordance score" as our loss function. The results are shown in Figure 4 . The details of pre-processing and experiment parameters3 are in Appendix A.5.We simulate the data distribution in Section 3.4, i.e., . Under these settings, the model is parametrized by the angle γ between θ * and θ * ,s , where cos γ := ⟨θ * , θ * ,s ⟩. We used γ = π/6 and π/2 in our experiments. 4The theoretical predictions of Theorem 3 for these curves in high-dimensional asymptotics n, m, d → ∞, with n/d → δ, m/d → δ s are reported as blue lines, and match remarkably well with the empirical data. The simple scaling law (4) nevertheless provides a good approximation of these (more complicated) theoretical formulas.y i = ⟨θ * , x i ⟩ + ε i , i ≤ n; y s i = ⟨θ * ,s , x s i ⟩ + ε s i , i ≤ m; with x i , x s i ∼ N(0, I d ), ε i ∼ N(0, σ 2 ),Note in particular that in the top row of Figure 5 , we have ⟨θ * , θ * ,s ⟩ = 0, i.e. the surrogate data are as far as possible from the original ones. Nevertheless, the induced regularization effect leads to smaller test error on the original distribution.We observe proposed scaling law (4) predicts well the behavior of the experiments, across of the datasets above, and for most combinations of original and surrogate examples we have tested.Finally, we emphasize that the scaling law is only an empirical approximation of reality. This is clearly illustrated by the example of ridge regression: in this case, we use Theorem 3 to precisely predict the discrepancy between precise asymptotics and scaling law, see Appendix A.6. 
discussion: 
 We conclude by discussing two possible generalizations of the scaling law (4), and its applicability. First, throughout this paper we assumed that R ex or (∞) = 0, namely that we can achieve the Bayes error by training on infinitely many original samples. In practice this will not hold because of the limited model complexity. Following standard scaling laws [KMH + 20, HBM + 22], this effect can be accounted for by an additional term C • N -ω , where N is the model size (number of parameters). Second, the scaling law (4) implies as special cases that R ex or (n) ≈ A or n -β , R ex su (m) ≈ R ex su (∞) + A su m -β .In particular, the exponent β is the same when training on real or surrogate data. In practice, we observe often two somewhat different exponents β or ̸ = β su . In these cases, we set β = β or , and this appears to work reasonably well. However, we can imagine cases in which the difference between β or and β su is significant enough (4) will stop being accurate. We use the scikit-learn implementation with the lbfgs solver, fitting the intercept, with maximum iterations set to 10k. For each run of each (n, m, α) combination, we set the ℓ 2 penalty (parameter C in scikit-learn) to 2 i , i = -8, ..., 8 and 10 i , i = -6, -5, -4, -3, 3, 4, 5, 6, and only report the test result for the value that achieves the best validation error. The results of the individual scaling law estimates and the comparison of joint training results with the scaling law predictions are shown in Figures 6 and 7 .Neural network: The network has one hidden layer with 32 ReLU neurons, and an output neuron using sigmoid. For training, we use the binary cross entropy loss, a constant learning rate of 0.05, and batch size 64. We train the network for 1,000 epochs. Similar to the procedure in logistic regression, we use ℓ 2 regularization (weight decay) and use the validation set to choose the best regularization parameter from the set {0, 10 -5 , 10 -4 , 10 -3 , 2• 10 -3 , 4 • 10 -3 , 10 -2 , 2 • 10 -2 , 4 • 10 -2 , 10 -1 , 2 • 10 -1 , 4 • 10 -1 }.The results of the individual scaling law estimates and the comparison of joint training results with the scaling law predictions are shown in Figures 8 and 9 .For the Gaussian mixture data, described in the previous section, we perform weighted ridge regression experiments according to equation ( 16) and plot the square loss. As before, we choose the best regularizer for the ridge regression of the set 2 i , i = -8, ..., 8 and 10 i , i = -6, -5, -4, -3, 3, 4, 5, 6, and report the test result for the value that achieves the best validation error. The results are presented in Figures 10 and 11 .To convert the movie reviews and book reviews to vectors, we use a combination of two different embedding: We use all the reviews in the training data and then use nltk tagger [Bir06] to find the most frequent 500 adjectives appearing in the samples used for training. Then we use the common Tfidf vectorizer (we used scikit-learn's implementation of tfidf vectorizer) for which we use the list of these most common 500 adjectives as vocabulary. This gives us a vector of length 500 dimension for each review. In addition, we also apply "Paraphrase-MiniLM-L6-v2" sentence transformer which is based on BERT with 6 Transformer Encoder Layers, and return a 384 dimension vector representation of the reviews. For each movie review we concatenate the results of tfidf vectorizer and sentence transformer to get a 884 dimensional representation that we use as our input vector. We use logistic regression and neural networks with the same set of parameters as in the Gaussian mixture experiments (except for the input dimension). We plot the average loss over 10 independent runs.Results omitted from the main text are presented in Figures 12 13 14 15 16 .We largely use the model and the training procedure described at https://jovian.ml/aakashns/05b-cifar10-resnet. We normalize the images for mean and standard deviation. We train a 9-layer ResNet model for classification, using Adam for optimization, weight decay, and gradient clipping, trained over 16 epochs with a one-cycle learning rate scheduling policy, minimizing cross entropy loss. For each combination of m, n, and α, we report the average test error over 10 runs. Since there is no overlap between the label sets of CIFAR10 and CIFAR100, the latter dataset needs to be relabeled. We do this by training a separate 9-layer ResNet model on 10,000 randomly chosen CIFAR10 images from the training set of 50,000 examples (without creating a separate split for them), and use its predictions on CIFAR100 images as labels.Scaling curves are presented in Figure 17 and 3 . We used public domain TCGA pancancer dataset. After, filtering samples with incomplete values we are left with 9220 patients, each having 20,531 gene expression values and the outcome was PFS (progression-free survival). Out of these we used a group of 2000 patients, splitted into train and test set of 1000 each to select 500 genes having the largest absolute Cox PH score. We also used the mean and standard deviation of gene expression values of these 2000 patients to normalize the gene expression columns for the remaining 7220 patients. Among the remaining of 7220 patients 3580 were females. We treated the female patients data as original data, and split them into train (50%), test (25%) and validation split (25%). The remaining 3640 patients data was used as surrogate dataset. We fit CoxPHFitter model (link) with 500 selected genes and use "1-concordance score" as our loss function. We used the validation split to choose best value of ℓ 1 penalty parameter from 2 i , i = 2, 0, -2, -4, -6, -8, -10, -12, -14, -16 in the model. We observed discontinuity at α = 1. To avoid this discontinuity, we approximated R( θn,m (1)) by R( θn,m (1 -ϵ)) if n > 0 and by R( θm/2,m (1 -ϵ)) if n = 0, where we choose ϵ = 0.05. We plot the average loss over 10 independent runs. The results are presented in Figures 18 and 4 .We present additional ridge regression experiments here in Figs. 19-30. We plot the average loss over 10 independent runs. In these experiments, as in the main paper, we set d = 500, σ 2 = σ 2 s = 1, ∥θ * ∥ = 1, ∥θ * ,s ∥ = 1, except for the last four Figs. 27 28 29 30 , where we use ∥θ * ,s ∥ = 1/2. We used angle γ = π/6 and π/2 in our experiments.We consider two methods: (1) Fix λ to a very small value 2 -10 , and (2) For each random draw of datasets select λ that achieves the best validation performance. For the latter method, we try λ = 2 i , where i = -10, -8, -6, . . . , 8, 10. For ridge regression simulations, we directly plot the excess test risks, as the parameter θ for original data is known and for any θ the excess test risk in this model is ∥θ -θ∥ 2 .In this appendix, we present our results on the estimator of Eqs. (2), (3) under the classical asymptotics n, m → ∞ at d fixed. For simplicity, we assume no regularizer is used in this regime. Beyond classical regularity assumptions of low-dimensional asymptotics, in this section we will make the following assumption which guarantees that original and surrogate distribution are 'not arbitrarily far.' Recall that R s (θ) denotes the population error on surrogate data. Assumption 1 (Distribution shift for low-d asymptotics). There exists a constantEQUATIONThe regularity conditions are similar to the ones in [vdV00] . Here and in the following B(θ * , r) is the ball of radius r centered at θ * . Assumption 2 ('Classical' regularity).(a) The original population risk R(θ) is uniquely minimized at a point θ * .(b) θ → ℓ(θ; z) is non-negative lower semicontinuous. Further, define the following limit inEQUATION)Then we assume inf u∈S d-1 Eℓ ∞ (u; z) ≥ R(θ * ) + c for some c > 0. (c) θ → ℓ(θ; z) is differentiable at θ * almost surely, both under z ∼ P and under z ∼ P s . Further, there exists r > 0 such that, letting B := B(θ * , r), the following holds for a constant C:EQUATION) (d)The functions θ → R(θ), θ → R s (θ), are twice differentiable in a neighborhood of θ * , with Lipschitz continuous Hessian. Further ∇ 2 R(θ * ) ≻ 0 (strictly positive definite). Proposition B.1. Under Assumption 1 and Assumption 2, define the following d × d matricesEQUATIONEQUATIONEQUATION)where Cov, Cov s denote the covariances, respectively, with respect to the original data (i.e., with respect to z ∼ P), and with respect to the surrogate data (i.e., with respect to z s ∼ P s ). Further define the d-dimensional vectorEQUATION)Then there exists α max ∈ (0, 1] (depending only on the constants in the assumptions) such that, for all α ∈ [0, α max ], the excess risk of the estimator θn,m (α) satisfies (forD := ∥g s ∥ bounded by a constant) R θn,m (α) -R θ * = α 2 ⟨g s , H -1 g s ⟩ + (1 -α) 2 n • Tr H -1 K (25) + α 2 m • Tr H -1 K s + O 1 m ∨ n + Dα 2 1 (m ∨ n) 1/2 + Dα .(Here the big O hides dependence on the constants in Assumptions 1 and 2.) Remark B.1. For economy of notation we stated Proposition B.1 in the case in which the excess risk is measured by using the same loss as for training, i.e. ℓ test = ℓ. However the same result Eq. ( 25) applies with minor modifications to the case ℓ test ̸ = ℓ (and thus, with R replaced by R test ), provided R test is also twice differentiable with Lipschitz Hessian, and ∇R test (θ * ) = 0. In this case, (25) has to be modified replacing H -1 by H -1 ∇ 2 R test (θ * )H -1 . Remark B.2. The error terms in Eq. ( 25) are negligible under two conditions: (i) m and n are large, which is the classical condition for low-dimensional asymptotics to hold; (ii) ∥g s ∥ 2 = ∥∇R s (θ * )∥ 2 α is small. In particular, the latter condition will hold in two cases. First, when ∥∇R s (θ * )∥ 2 is of order one (i.e. the distribution shift is large), but α is small (surrogate data are downweighted). Note that, when the distribution shift is large, and the sample size n is large enough, we expect small α to be optimal and therefore Eq. ( 25) covers the 'interesting' regime.Second, when ∥∇R s (θ * )∥ 2 is small (i.e. the shift is small) and α is of order one. If in addition we have ∇ 2 R s (θ * ) ≈ ∇ 2 R s (θ * ), it can be shown that the range of validity of Eq. ( 25) covers the whole interval α ∈ [0, 1]. Remark B.3. Note that the distribution shift is measured in Eq. ( 25) by the first term ⟨g s , H -1 g s ⟩.The original and surrogate distribution can be very different in other metrics (e.g. in total variation or transportation distance), but as long as g s is small (as measured in the norm defined by H -1 ), surrogate data will reduce test error.is R ex or (n) := R( θn,0 (0)) -R(θ * ) = Tr H -1 K /n + o(1/n), while R ex su (m) := R( θn,m (0)) - R(θ * ) = ⟨g s , H -1 g s ⟩ + Tr H -1 K s /m + o(1/m).Hence Eq. (B.1) can be recast in the form of our general scaling law (4), namely:R( θn,m (α)) -R θ * ≈ α 2 R ex su (∞) + α 2 R ex su (m) -R ex su (∞) + (1 -α) 2 R ex or (n), which (as expected) corresponds to the parametric scaling exponent β = 1.An immediate consequence of Proposition B.1 is that surrogate data do not hurt, and will help if their distribution is close enough to the original one (under the assumption of optimally chosen α).B.1, let R or (n) := Tr H -1 K /n, and R su (m) := ⟨g s , H -1 g s ⟩ + Tr H -1 K s /m. For α * n,m = R or (n)/(R su (m) + R or (n)), we have R θn,m (α * n,m ) -R * = R or (n) -1 + R su (m) -1 -1 + ∆ n,m, with ∆ n,m of the same order as the error in Prop. B.1.Lemma B.3. Under the assumptions of Proposition B.1 (Assumption 1 and Assumption 2) there exists α max ∈ (0, 1], depending only on the constants appearing there such that the following holds:(i) The function θ → R(θ; α) := (1 -α) R(θ) + α R s (θ) has a unique minimizer θ * (α) ∈ R d .Further θ * (α) ∈ B(θ * , r), and θ * (α) → θ * as α ↓ 0.(ii) We have θn,m (α) → θ * in probability as n, m → ∞.Proof. Fix r 0 ∈ (0, r] By Assumption 2.(a), inf θ̸ ∈B(θ * ;r0) R(θ) > R(θ * ) + δ 0 for some constant δ 0 . Hence, using Assumption 1, for any θ ̸ ∈ B(θ * ; r)R(θ; α) ≥ R(θ) -K * α 1 + R(θ) ≥ (1 -K * α)R(θ) -K * α ≥ (1 -K * α)(R(θ * ) + δ 0 ) -K * α .In the other hand R(θ * ; α)≤ (1 + K * α)R(θ * ) + K * α, whence R(θ; α) -R(θ * ; α) ≥ (1 -K * α)δ 0 -2K * αR(θ * ) -2K * α, ,which is strictly positive for α < α max (r 0 ) := δ 0 /(4K * (1 + R(θ * )). Hence the minimum must be achieved in B(θ * ; r 0 ) (note that since R(θ), R s (θ) are lower semicontinuous, the minimum is achieved).By Assumption 2.(d), for r 0 sufficiently small, θ → ∇R(θ; α) is strictly convex in B(θ * ; r 0 ) and therefore the minimizer is unique. This proves point (i).Point (ii) follows from a modification of Theorem 5.14 in [vdV00] . Namely, for a diverging sequence{(n(k), m(k)) : k ∈ N}, we consider to R * ,k (u) := R n(k),m(k) (c(u)u; α), where c(u) := (1 + ∥u∥ 2 ) -1/2 . This function is lower semicontinuous on the compact set B(0; 1) and converges almost surely to its expectation for every fixed u in this set, and hence the argument of Theorem 5.14 [vdV00] applies here.Proof of Proposition B.1. By a modification of Theorem 5.39 in [vdV00] (here θ * (α) is defined as in Lemma B.3)EQUATIONEQUATIONwhereH(α) := (1 -α)∇ 2 R(θ * (α)) + α∇ 2 R s (θ * (α)).Note that in the present setting the error is of order m -1 + n -1 because we assume the Hessian to be Lipschitz continuous.The population minimizer θ * (α) solvesEQUATIONWe now estimate various sums by breaking them by the value of kB n,m ≤ k1 k=1 (α + λω k )θ * ,k -αθ s * ,k 2 + ∞ k=k1+1 1 (λω k ) 2 (α + λω k )θ * ,k -αθ s * ,k 2 ≤ k1 k=1 α 2 (θ * ,k -θ s * ,k ) 2 + 2α(θ * ,k -θ s * ,k )λω k θ * ,k + (λω k ) 2 θ 2 * ,k + ∞ k=k1+1 α 2 (λω k ) 2 (θ * ,k -θ s * ,k ) 2 - 2α λω k (θ * ,k -θ s * ,k )θ * ,k + θ 2 * ,k ≤ α 2 ∥θ * ,≤k1 -θ s * ,≤k1 ∥ 2 + 2α ω k1 |⟨θ * ,≤k1 -θ s * ,≤k1 , θ * ,≤k1 ⟩ Ω | + 1 ω 2 k1 ∥θ * ,≤k1 ∥ 2 Ω 2 + α 2 ω 2 k1+1 ∥θ * ,>k1 -θ s * ,>k1 ∥ 2 Ω -2 + 2αω k1+1 ⟨θ * ,>k1 -θ s * ,>k1 , θ * ,>k1 ⟩ Ω -1 + ∥θ * ,>k1 ∥ 2 , and V n,m ≤ k 1 + k>k1 ω 2 k1+1 ω 2 k ≤ (k 1 + c # ) , since under the assumption ω k ≍ k µ , µ > 1/2, we have k>k1 (ω k1+1 /ω k ) 2 ≤ c # .Recalling the definitions in the theorem, and lettingδ k := max ω k+1 ⟨θ * ,>k -θ s * ,>k , θ * ,>k ⟩ Ω -1 ; ω 2 k+1 ∥θ * ,>k -θ s * ,>k ∥ 2 Ω -2 ,we haveB n,m ≤ α 2 ∥θ * -θ s * ∥ 2 + ∥θ * ,>k1 ∥ 2 + 1 ω 2 k1 ∥θ * ,≤k ∥ 2 Ω 2 + 3δ k1 + 2∆ k1 , whence R n,m (α, λ) ≤ α 2 ∥θ * -θ s * ∥ 2 + ∥θ * ,>k1 ∥ 2 + 1 ω 2 k1 ∥θ * ,≤k1 ∥ 2 Ω 2 + (k 1 + c # ) • s n,m (α) + 3δ k1 + 2∆ k1 = α 2 R ex su (∞) + ∥θ * ,>k1 ∥ 2 + 1 ω 2 k1 ∥θ * ,≤k1 ∥ 2 Ω 2 + (k 1 + c # ) • s n,m (α) + 3δ k1 + 2∆ k1 .Next we specialize to the case ∥θ * ,>k µ∧ρ) , and therefore, by suitably adjusting the constant∥ 2 ≤ C θ k -2ρ , ω k ≍ k µ µ ̸ = ρ. In this case we have ω -2 k ∥θ * ,≤k ∥ 2 Ω 2 ≤ Ck -2(C R n,m (α, λ) ≤ α 2 R ex su (∞) + Ck -2(µ∧ρ) 1 + (k 1 + c # ) • s n,m (α) + 3δ k1 + 2∆ k1 .We now bound δ k . By Cauchy-Schwarz and monotonicity of ω,ω k+1 ⟨θ * ,>k -θ s * ,>k , θ * ,>k ⟩ Ω -1 ≤ ∥θ * ,>k -θ s * ,>k ∥ 2 ∥θ * ,>k ∥ 2 ≤ 2C θ k -2ρ, and furtherEQUATIONTherefore,R n,m (α, λ) ≤ α 2 R ex su (∞) + Ck -2(µ∧ρ) 1 + (k 1 + c # ) • s n,m (α) + 2∆ k1 .Proof of claim (a). The stated assumption on ∆ k imply that (eventually adjusting the constant C):EQUATION.We now select λ * (α) so that k 1 ≍ s n,m (α) -1+β where β = 2(µ ∧ ρ)/(1 + 2(µ ∧ ρ)). (this is possible for all n, m large enough under the assumption on ω k ), to A straightforward calculation yields:R n,m (α, λ * (α)) ≤ α 2 R ex su (∞) + C • s n,m (α) β , which proves claim (a). Proof of Claim (b). We choose ω k = k µ , θ * ,k = k -ρ ′ -1/2 , θ s * ,k = θ * ,k + a k k -ρ-1/2, with a k ∼ Unif({-A, +A}) . We will choose A ≤ 1 a sufficiently small numerical constant. Note that, for µ > 2ρ + 1/2∆ k = k -µ k ℓ=1 a ℓ ℓ µ-2ρ-1 ≤ CAk -µ+ε k ℓ=1 ℓ 2µ-4ρ-2 1/2 ≤ CAk -2ρ-1/2+ε ′ ,where, for any ε > 0, the first inequality holds with probability at least 1/2 for all k > k 0 (ε). We can therefore select the a ℓ , so that∆ k ≤ C ′′ Ak -2ρ-ε for some C ′′ < ∞.Following the calculation at point (a) decompose the bias term asB n,m = ∞ k=1 1 1 + λω k 2 α 2 (θ * ,k -θ s * ,k ) 2 + (λω k ) 2 θ 2 * ,k + 2αE n,m , E n,m := ∞ k=1 1 1 + λω k 2 (θ * ,k -θ s * ,k )λω k θ * ,k . Note that |E n,m | ≤ δ k1 + ∆ k1 ≤ CAk -2(µ∧ρ) 1 . Therefore B n,m -α 2 ∥θ * -θ s * ∥ 2 ≥ ∞ k=1 λω k 1 + λω k 2 θ 2 * ,k -α 2 ∞ k=1 1 - 1 1 + λω k 2 (θ * ,k -θ s * ,k ) 2 -CAk -2(µ∧ρ) 1 ≥ 1 4ω 2 k1+1 ∥θ * ,≤k1 ∥ 2 Ω 2 + 1 4 ∥θ * ,>k1 ∥ 2 - A 4ω k1+1 ∥θ * ,≤k1 ∥ 2 Ω - A 4 ∥θ * ,>k1 ∥ 2 -CAk -2(µ∧ρ) 1 ≥ C k -2(µ∧ρ) 1.By a similar calculation, we also obtainV n,m ≥ C k 1 ,and thereforeR n,m (α, λ) ≥ α 2 R ex su (∞) + Ck -2(µ∧ρ) 1 + Ck 1 • s n,m (α) .The proof is completed by minimizing over k 1 .This appendix is devoted to proving Theorem 2. Recall that this is established within the white noise model of Eq. ( 14), which we copy here for the readers' convenienceEQUATIONThe adaptation of the estimator (13) to this continuous setting is given explicitly below fn,m,α = arg minEQUATIONThe proof of Theorem 2 is based on a reduction to a suitable 'sequence model' via the Fourier transform, defined asEQUATIONfor q ∈ Q d := {2πq : q ∈ Z d }, where ι = √ -1. The inverse Fourier transform is defined asEQUATIONWe let θ * , θ * ,s , and θλ,p,n,m,α respectively denote the Fourier transform of f * , f * ,s , and fλ,p,n,m,α .The Fourier transforms of the observations are given byEQUATIONwhere G(q) and G s (q) are i.i.d. standard Gaussian. It then follows thatEQUATIONwhere we abuse the notation to define ∥θ∥ 2 p,2 :=EQUATION)with c p,q := 1 + ∥q∥ 2r . Minimizing (50) we get θn,m (q; α) = 1 1 + λc p,q(1 -α) Ŷ (q) + α Ŷs (q) . (Taking the inverse Fourier transform and plugging it into the excess risk formula we getEQUATIONwhereEQUATIONThe convexity of x → x 2 impliesEQUATIONfor γ ∈ (0, 1) and therefore we can upper bound the first sum in (53) by taking γ = 1/(1 + δ) for any δ > 0, which yieldsR(f n,m,α ) ≤ (1+δ)α 2 ∥θ * ,s -θ * ∥ 2 2 + 1 + δ δ q∈Q d λc p,q 1 + λc p,q 2 |θ * (q)| 2 +V n,m q∈Q d 1 (1 + λc p,q ) 2 .(56)We now upper bound the first sum above. We note that, defining q 0 via λc r (q 0 ) = 1 (with an abuse of notation c r (t) = 1 + t 2r ), whence q 0 ≥ (λ/2) -1/2r for all λ < 1:q∈Q d λc p,q 1 + λc r,q 2 • |θ * (q)| 2 ≤ q∈Q d ,∥q∥2≤q0 λ 2 c r (q) 2 |θ * (q)| 2 + q∈Q d ,∥q∥2>q0 |θ * (q)| 2 ≤ λ 2 max ∥q∥2≤q0 c r (q) 2 c s (q) q∈Q d ,∥q∥2≤q0 c s (q)|θ * (q)| 2 + max ∥q∥2>q0 1 c s (q) q∈Q d ,∥q∥2>q0 c s (q)|θ * (q)| 2 (a) ≤ λ 2 max ∥q∥2≤q0 c r (q) 2 c s (q) max ∥q∥2>q0 1 c s (q) ≤ λ 2 max 1, c r (q 0 ) 2 c s (q 0 ) + 1 c s (q 0 ) ≤ C max(λ 2 , λ p/r ) + Cλ p/r ≤ Cλ 2∧(p/r) ,where in (a) we used the fact that ∥f * ∥ 2 2,p = q c s (q)|θ * (q)|. Letting C i (d) be constants depending on d, we haveq∈Q d 1 (1 + λc r,q ) 2 ≤ C 1 (d) R d 1 (1 + λc r,q ) 2 dq ≤ C 1 (d) R d 1 (1 + λ∥q∥ 2r )) 2 dq ≤ C 2 (d) ∞ 0 t d-1 (1 + λt 2r ) 2 dt ≤ C 2 (d) λ -1/2r 0 t d-1 dt + C 2 (d)λ -2 ∞ λ -1/2r t d-1-4r dt .For convergence we requite r > d/4, in which caseEQUATION)E Analysis of high-dimensional regression: Proofs for Section 3.4E.1 Auxiliary definition for Theorem 3Our characterization is given in terms of a variational principle. For δ, δ s ∈ (0, ∞), define R(•; α) :EQUATION- δρ 2 2(1 -α) - δ s ρ 2 s 2α + λ 2 ξ 2 + ξ 2 ⊥ + ω 2 ,where τ, τ s are defined byEQUATION)EQUATION)and ρ = ρ/ √ 1 + t 2 , ρ s = ρt/ √ 1 + t 2 , with ρ solving the polynomial equationEQUATION)and t is given byEQUATIONTheorem 3 states that the asymptotics of the test error is determined by the minimizer of R.The proof is based on Gordon Gaussian comparison inequality [Gor85, Ver18] , and follow a standard route, see e.g. [TOH15, TAH18, MM21]. We will limit ourselves to outlining the main steps of the calculation. Throughout, we consider the case ε 0 > 0, δ + δ s > 1 because the other one (ε 0 = 0 and δ, δ s > 1) is analogous and less interesting.We begin by rewriting the ridge cost function in terms of a LagrangianEQUATIONL n,m (θ, u, u s ; α) :=⟨u, X(θθ * )⟩ + ⟨u s , X s (θ -θ * ,s )⟩ -⟨u, ε⟩ -⟨u s , ε s ⟩ (64)- n∥u∥ 2 2 2(1 -α) - m∥u s ∥ 2 2 2α + λ 2 ∥θ∥ 2 2 .Let ∆(θ, u, u s ) := ∥u∥ 2 ∥θ-θ * ∥ 2 G+∥u s ∥ 2 ∥θ-θ * ,s ∥ 2 G s ., where G, G s are independent standard normal random variables, independent of X, X s . By Gordon's inequality [Gor85] , we can compare the Gaussian process L n,m (θ, u, u s ; α) + ∆(θ, u, u s ) toL G n,m (θ, u, u s ; α) :=∥u∥⟨g, θ -θ * ⟩ + ∥θ -θ * ∥⟨h, u⟩ + ∥u s ∥⟨g s , θ -θ * ,s ⟩ + ∥θ -θ * ,s ∥⟨h, u s ⟩ (65) -⟨u, ε⟩ -⟨u s , ε s ⟩ - n∥u∥ 2 2 2(1 -α) - m∥u s ∥ 2 2 2α + λ 2 ∥θ∥ 2 2 .Next we define the orthonormal vectorsEQUATION)where P ⊥ θ * = I -P θ * := Iv * v T * is the projector orthogonal to θ * . We then decomposeEQUATIONwhere ⟨v * , θ ⊥ ⟩ = ⟨v ⊥ * , θ ⊥ ⟩ = 0, and define ω := ∥θ ⊥ ∥ 2 . Defining τ 2 = ∥θ -θ * ∥ 2 2 , τ 2 s = ∥θ -θ * ,s ∥ 2 2 , Eq. ( 60) follows. With these notations, and lettingEQUATIONEQUATION- δρ 2 2(1 -α) - δ s ρ s 2α + λ 2 ξ 2 + ξ 2 ⊥ + ω 2 .We finally decompose g = g ∥ +g ⊥ where g ∥ ∈ span(v * , v ⊥ * ) and g ∥ ⊥ span(v * , v ⊥ * ), and similarly for g s , and defineEQUATION) Defining ι via ∥ρg ⊥ / √ n + ρ s g s,⊥ / √ m∥ = (1 + ι) ρ 2 + ρ 2 s , we obtain L G n,m (ξ, ξ ⊥ , ω, ρ, ρ s ; α) = -(1 + ι) ρ 2 + ρ 2 s • ω + ∆ + ρ δ(τ 2 + σ2 ) + ρ s δ s (τ 2 s + σ2 s ) (71) - δρ 2 2(1 -α) - δ s ρ 2 s 2α + λ 2 ξ 2 + ξ 2 ⊥ + ω 2 ,where ∆ is the contribution of the perpendicular components. Simple concentration estimates imply that for any ε > 0 there exist c(ε) > 0 such thatEQUATIONEQUATIONEQUATION)We can then estimate L G n,m (ξ, ξ ⊥ , ω, ρ, ρ s ; α) byL G (ξ, ξ ⊥ , ω, ρ, ρ s ; α) = -ρ 2 + ρ 2 s • ω + ρ δ(τ 2 + σ 2 ) + ρ s δ s (τ 2 s + σ 2 s ) (75) - δρ 2 2(1 -α) - δ s ρ 2 s 2α + λ 2 ξ 2 + ξ 2 ⊥ + ω 2 ,Differentiating with respect to ρ and ρ s and setting the derivatives to 0 yields ρ = ρ/ √ 1 + t 2 , ρ s = ρt/ √ 1 + t 2 , with ρ, t given by Eqs. ( 61), (62). By computing second derivatives, one obtain that this is a local maximum. Since L G (ξ, ξ ⊥ , ω, ρ, ρ s ; α) → -∞ as ρ 2 + ρ 2 s → ∞, the maximum over ρ, ρ s is either achieved at this point or at the boundary {ρ = 0} ∪ {ρ s = 0}. By checking the signs of partial derivatives along this boundary, the only other possibility is ρ = ρ s = 0.For economy of notation, write F (ρ, ρ s ) := L G (ξ, ξ ⊥ , ω, ρ, ρ s ; α). For any unit vector v = (v 1 , v 2 ) ≥ 0, the directional derivative is∇ v F (r) r=0 = -ω + v 1 δ(τ 2 + σ 2 ) + v 2 δ s (τ 2 s + σ 2 s ) ≥ ω -1 + v 1 √ δ + v 2 δ s .By maximizing over the direction, we see that v can be chosen so that ∇ v F (0) ≥ ω[-1 + √ δ + δ s . Hence ρ = ρ s = 0 cannot be the global aximum for δ + δ s > 1.Hence, we getEQUATIONWe further note that, for fixed ρ, ρ s > 0, the function (ξ, ξ ⊥ , ω) → L G (ξ, ξ ⊥ , ω, ρ, ρ s ; α) is jointly strictly convex for λ > 0. Hence (ξ, ξ ⊥ , ω) → R(ξ, ξ ⊥ , ω; α) is also strictly convex for λ > 0.Therefore, it has a unique minimizer, which we denote by (ξ * , ξ * ⊥ , ω * ). Proceeding as in [MM21], we obtain the following result.Proposition E.1. Under the assumptions of Proposition 3, for any ε, ε 0 > 0 there existsEQUATIONIn particular, the last proposition implies (a weaker form of) Theorem 3 whereby the supremum is taken over a finite net. Namely for η > 0, we defineN (ε 0 , η) := [ε 0 , 1 -ε 0 ] ∩ ηZ .Recalling that, in the present case, R( θ) = ∥ θ -θ∥ 2 2 , we obtain (after adjusting the constant c) we have therefore:EQUATIONFinally, let X + ∈ R (m+n)×d be the matrix obtained by stacking X and X s . Given constants C 1 , C 2 , C 3 , define the good eventEQUATIONBy a standard bound on eigenvalues of Wishart matrices [Ver18] , for δ + δ s > 1, we can chooseEQUATIONFurther on G, θ n,m (α) is bounded (in ℓ 2 norm, and Lipschitz continuous in α). As a consequence, for a sufficiently large constant L,EQUATION)The claim follows by using this estimate together with Eq. (78). We ran all experiments on a single machine with 2 RTX 4090 GPUs and a 24-core Intel Xeon E5 CPU. All experiments completed in less than 24 hours.NeurIPS Paper Checklist 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not release any new dataset or model.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: All of the third-party dataset used in the paper are well-known, publicly available datasets. In Section F, we cite the original papers, link to the datasets, and when available, cite the licenses.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: We do not release any new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024).We assume here that limn→∞ R( θn,0(0)) = R * , i.e. that we achieve Bayes risk with infinitely many original samples. See Section 5.The same proof, with some additional technical work, yields a characterization for δ + δs ≤ 1 as well. We omit it here for brevity.We observe that training at α = 1 yields a somewhat singular behavior: we use a α = 0.95 as a proxy of α = 1, see appendices.For ridge regression simulations, we directly plot the excess test risks, as the parameter θ for original data is known. For any θ the excess test risk in this model is simply ∥θ -θ∥ 2 . 
 
 Appendix:  


Decision: This paper addresses the challenge of augmenting limited real data with surrogate data, particularly in scenarios where high-quality data is scarce or expensive to obtain. The authors propose a weighted empirical risk minimization (ERM) approach to integrate surrogate data into training processes. The primary contribution is the introduction of a new scaling law that optimizes the weighting scheme for combining real and surrogate data, validated both theoretically and empirically. The key finding is that integrating surrogate data, even when unrelated to the original data, can significantly reduce test error, a result linked to Stein's paradox.
The paper is technically sound, offering both theoretical analysis and empirical validation across various domains.

Reviewer XfMG gave the lowest score of 3, primarily citing concerns about the literature review, notation clarity, practical utility, and format. After reviewing the discussion chain, I believe these comments are not entirely fair.

Reviewer 3jgb gave the second-lowest score of 4, with concerns centered on the theory-simulation gap, the need for a more detailed discussion of regularization, and the assumptions underlying the theorems. I believe these issues can be addressed with minor revisions and should not prevent the paper from being published.

The other scores are 6, 8, and 9, very high indeed.

Reviews: review: paper_summary: paper_summary: In the context of linear regression, this paper proposes to complement training data with surrogate data (generated / synthesized, or from an unrelated task / domain). For an optimal combination of real and surrogate data, new scaling laws are derived which show that that surrogate data can can help reduce the text error.
strength_weakness: strength_weakness: NaN
questions: questions: - In practice, how is the optimal value of the weighting paramater $\alpha_*$ to be set ? Is there a consistent estimator for it which only depends on the input training data ? Without such a prescription, the proposed scheme might fall short of practical usefulness.

- My understanding is that the proof of the main result uses the Gordon comparison theorem. If a nontrivial covariance matrix for the features $x$ is introduced, major modifications might be required, or an entirely different approach (e.g via RMT) might be required. I'd be glad if the the authors can comment on this.

- I wonder what this work could tell us about the "model collapse" phenomenon [1,2,3], where a model trained on synthetic data eventually breaks down (becomes biased towards a trivial / useless estimator).

[1] Shumailov et al. "The Curse of Recursion: Training on Generated Data Makes Models Forget" (2023)
[2]  Alemohammad et al. "Self-Consuming Generative Models Go MAD" (2023)
[3] Dohmatob et al. "A Tale of Tails: Model Collapse as a Change of Scaling Laws" (ICML 2024)
limitations: limitations: The setup considered is extremely: linear regression with Gaussian data with no covariance structure (i.e isotropic covariates)
paper_summary: paper_summary: This is a technical report on predicting training loss for a model trained on a weighted combination of real (in-distribution) and surrogate (out-of-distribution) data. The report proposes a parametric function for predicting how the training loss scales with the amount of real and surrogate data. The report first conducts theoretical analysis with a number of standard models on stylized cases, such as Gaussian sequence model, high-dimensional linear regression, etc., and derivated conditions for the proposed scaling relationship to hold. The report conducts empirical validation of the proposed scaling law on a range of classic tasks such as Sentiment analysis for the IMDB dataset, ResNet for CIFAR-10 classification, etc., and shows the training loss consistent with the proposed scaling function.
strength_weakness: strength_weakness: I'm not sure whether this technical report format is suitable for a NeurIPS paper. The lack of context or background is not a critical problem, though the lack of context may make it less accessible to broader audiences. What I found most concerning is the complete lack of comparison with existing works and a serious literature review.

The practice of data augmentation or/and using synthetic data from generative models/simulation, etc. is prevalent in the field and has a long history. This also seems not also the first paper to propose the idea of weighted training with real and surrogate data.

It is essential for any paper contributing to this topic to first
1. organize and list previous efforts on this topic;
2. introduce the current progress and research landscape; identify and justify there exists a valid research gap;
3. how this paper moves forward compared to previous efforts.

All of these are missing from this paper. Section 1.3 simply listed a number of potentially relevant references without commenting on each one or explaining how they relate to or are different from this paper. It is not actually informative.

---
The problem definition does not appear rigorous. Though problem formulation and notations come early on in the paper, many are not clearly introduced or defined.

Some vague arguments mismatch with the math-heavy writing style of the paper. For example, in the abstract, the authors emphasized 

> "Integrating surrogate data can significantly reduce the test error on the original distribution. Surprisingly, this can happen even when the surrogate data is unrelated to the original ones. "

The word 'unrelated' makes it a very strong argument. Surprisingly, I did not find it clearly defined in the main paper.

Actually, I don't think learning with unrelated surrogate data will always reduce model loss. Imagine training the model with mislabeled data. It will only degrade the validation performance. My guess is what the authors are trying to say might be "training the model with not directly related data may also contribute positively due to regularization effect or knowledge transfer". But this is well-known to the community. So I am confused.
questions: questions: See Weaknesses.
limitations: limitations: The work does not have a standalone discussion for its limitations.
paper_summary: paper_summary: This study addresses the challenge of computational scenarios where true data are scarce, and surrogate data are available to assist in building statistical models. The authors provide novel theoretical and empirical insights demonstrating that training models with both true and surrogate data, with appropriated selected coefficient $\alpha$, could improve empirical risk reduction on test sets, even when the surrogate data is unrelated.
strength_weakness: strength_weakness: - The discussion is limited to certain loss functions, specifically $\lVert \theta_\ast - \theta\rVert^2$ and $\lVert f_\ast - f\rVert^2_{L^2}$. Extending these results to include more common loss functions like L-1/L-inf norms or classification-driven losses could broaden the applicability of the findings.

- Some notations are unclear or undefined, which could hinder understanding for readers unfamiliar with the symbols or concepts. For example, the symbol $\asymp$ used in Line 152 and $\Lambda(\alpha)$ in Line 207 require definitions.

- Some minor errors: 
    - Line 50 introduces the test error $R_\text{test}$ but this subscript is not used in the following context, e.g. Equation (4). Please make sure the test error notations are consistent;
    - Line 226: $R_\ast=R(\hat\theta_{0, \infty}(0))$ should be $R_\ast=R(\hat\theta_{\infty, 0}(0))$
questions: questions: - Equation (4) appears to lack a variable that quantifies the "closeness" between the surrogate and true data, such as the $\gamma$ parameter defined in Theorem 3. Could the authors clarify the absence of such a metric in this model formulation?

Note: I realize that $R_\text{su}^\text{ex}(\infty)$ can represent the deviation from surrogate data to true data (indirectly). But let's keep this in case others share similar questions.
limitations: limitations: The limitation is included and no negative societal impact should be considered.
paper_summary: paper_summary: This work investigates the effects of augmenting training datasets with lower quality data, under a weighted ERM scheme. It is shown that introducing this surrogate data to optimally weighted training can improve predictive performance on the original data distribution, as measured by test error, even when the surrogate data is unrelated to the dataset of interest. A corresponding scaling law is derived, giving insight into both the optimal weighting and the amount of surrogate data that can be used. Numerical examples are provided.
strength_weakness: strength_weakness: The theory of this paper is developed for a squared loss function. However, most of the numerics are done on classification tasks without mention of this discrepancy. This should be addressed, with justification provided if possible.
The role of the regularizer is barely mentioned, however it appears to play a crucial role in the relatively clean form of the relevant quantities given in the result statements. Analysis of sensitivity of the results to the regularization parameters would seem important and be appreciated. Further, growth estimates on its spectrum do not match the usual ridge regression setup (i.e. setting $\Omega$ to be the identity) in a way that's independent of parameter dimension. This makes the assumption highly artificial, and somewhat redundant (compared to just using the largest eigenvalue), and impacts the statement of the theorems.
Clear discussion on the rationale for a scaling law and its specific form is not given.
questions: questions: Can you please address the above weaknesses?
limitations: limitations: While the phenomena is framed as analogous to a regularization technique, I do not feel that adequate care is taken to ensure that non-expert readers are not encouraged to add junk data to their training regimes without adequate care being taken.
paper_summary: paper_summary: This work addresses the challenge of augmenting limited data with more accessible surrogate data to improve generalization. The authors proposed a weighted ERM approach for integrating surrogate data into training and analyzed its performance under various statistical models. It was shown that incorporating surrogate data provably reduces test error, even when the surrogate data is far from the original ones. The paper introduced a scaling law that predicts the optimal weighting scheme and the amount of surrogate data to use, supported by both theories and experiments across different domains.
strength_weakness: strength_weakness: Weighted ERM is a simple and arguably the most intuitive way to incorporate surrogate data. This is a strength rather than a weakness on its own. However, given the ubiquity of such methods, the discussion on related works could be more comprehensive.
- For example, in addition to synthetic data from generative models, data augmentations also seem to fall into the category of surrogate data considered in the paper. The results on sample complexities of data augmentation methods could be relevant. 
- Another potentially related topic is distributionally robust optimization. Despite the different optimization problems, the idea of finding a near-optimal weight for different groups of samples shares a similar high-level goal.
- Instead of "introducing weighted ERM", the contribution of this work seems to be more about providing a theoretical underpinning for the effectiveness of weighted ERM with an insight on the choice of weight. This could be made clearer in the paper.
questions: questions: - In Eq (4), is there any reason for using $\approx$ instead of $\asymp$?
- In Theorem 1 and 2, how to interpret $\beta$ intuitively, the difficulty of the learning problem?
- In the Sobolev class example (line 161), what's the particular reason for assuming $n=Q^d$? Is this essential or just for simplicity?
limitations: limitations: - Some limitations are listed in the Weaknesses section.
- It would be helpful to provide more intuitions for Theorem 3 given the complexity of the notations and the distinct form of the result in the asymptotic regime (cf. the clear sample complexities in Theorems 1 and 2). Remark 3.3 on the connection with the scaling law provides some insights but doesn't seem to be clear enough.

Comments: title: Response
thank you very much!
Discussion
Thanks for the responses
Thanks for the responses.
Response
request for clarification
discussion
discussion
comment: Thanks for your response. I have raised my score as a result of these proposed changes.
Thank you very much for the clarification.
Regarding regularization.  The effect of regularization can be viewed as a special type of surrogate data, but there are very important differences that we also emphasized in our response to the area chair. These differences are subtle and require careful analysis, which is what we do in the paper.
1. The surrogate sample size m is finite. The effect of finite m in the scaling laws we derive (Eq (4), Eq (10), Eq (11), etc) is important, and would not be modeled by treating the surrogate data as regularization: the first error term in the square brackets in Eq. (4) would disappear. On the other hand,it is very important to capture this effect. In practice, the scaling law (4) can be used to decide how much surrogate data to acquire, and this is only possible if we model the effect of finite m.
2. The regularization effect produced by surrogate data depends of course on the distribution of the surrogate data itself. In particular, while a regularization typically shrinks the parameters of the model towards 0, surrogate data shrink it towards a value theta** that is determined by the data distribution. Also, the form of this shrinkage effect depends in subtle ways on the data distribution. 
3. Finally, the value of this ‘center’ theta** is of course very important, and can significantly change the behavior of the weighted ERM scheme. In practical settings, we cannot construct a regularizer which contains a reasonable guess of theta** with a meaningful guess without surrogate data.
Finally, augmented data can be regarded as consisting of samples dependent on the original samples. This of course can be modeled mathematically. The difficulty is in analyzing and obtaining non-trivial results in such a model. We do not do it in this paper, and in fact we are not aware of any works doing it in a general rigorous way.


Regarding weighting. This is a great question. In synthesis, the two schemes proposed by the referee are equivalent only for what concerns the expected (or population) risk. However, analysis at the level of expected risk is only accurate when the number of original and surrogate examples are very large or infinite. But in this extreme case adding surrogate data is already pointless. In more practical scenarios, where the number of original examples is small, we can achieve a lot more with weighted ERM than vanilla ERM. 
This can be seen already in Eq. (1).
A practical illustration.
Consider the case where we have 400 original examples and 1,000,000 surrogate examples.
Suppose we want to give (on average) a weight of 80% to original and 20% to surrogate.
With weighted ERM we can use all 1,000,000 surrogate examples and assign the surrogate dataset a weight of 0.2 to it and weight 0.8 to the original dataset. 
In the “vanilla ERM” alternative, we must limit ourselves to 100 surrogate examples. This is a very small number and the statistical noise introduced by the surrogate examples may be dominating the signal they provide.
Overall,  adding surrogate examples in a vanilla ERM fashion may hurt the model performance. On the other hand adding a large number of surrogate examples with a weight 0.2 will help the model if surrogate data and the original data distributions are not too far in expectation.
My concerns have mostly been addressed. Thanks. I'll keep my current score.
Thanks for the responses.

Adding surrogate data, by the idea of Stein's example, suggests improving the quality of estimation for a random variable by leveraging other sources of randomness, related or not. For that purpose, the effect of adding regularization or data augmentation seems also to align with the idea. Why we cannot model these effects with the same model for surrogate data?  Can we treat regularization as an independent source of randomness or consider augmented data as a related random variable?

As for mixing data, why is "vanilla ERM" different from "weighted ERM for modeling purposes? For example, is training on [80% real data mixed with 20% surrogate data with vanilla ERM] the same as training on [50% real data mixed with 50% surrogate data with an 8:2 weighted ERM]?
Thank you, we will do our best to improve the presentation and comparison with earlier work, as recommended.
Thanks for the comment. Concretely, we plan the following changes.
To address the generalization to other loss functions:
1. We will add a discussion of classification loss, referring to the papers mentioned in our rebuttal. We will draw explicit consequence of these results for the surrogate data setting.
2. We will plot an empirical comparison of classification and regression losses. For this plot, we will consider one example with binary labels, and fit either cross-entropy loss or least square loss, plotting the resulting test error versus alpha in the two cases.
3. We have mathematical results on classification loss for under-parametrized settings in which the sample size is much larger than the number of parameters. These are currently given in Appendix B. We will instantiate these general results for classification, and state these consequences in the main text.

To address readers blindly adding bad surrogate data:
1. We will add a new subsection to Section 1, to discuss the practical use of the scaling law. (This will expand the paragraph beginning on line 93.)
2. In this subsection we will outline an explicit flowchart of how practitioners can use the proposed weighting scheme and scaling law.
3. We will add a figure demonstrating the evolution of test error with added surrogate data using our approach, and a naive approach (comparing for “good” and “bad” surrogate data). This figure should clarify that if ‘bad’ surrogate data are added to the training in a naive way, it can dramatically hurt the model test error. On the other hand, if the same data is added with weight that is optimized via cross-validation, then this effect is significantly mitigated and potentially reversed (“bad” data can help). 
4. The same figure will be used to illustrate the robustness of the method with respect to changes in the regularization parameter.

Finally, we will add motivations for the setting of Theorem 3.1 by connecting it to classical nonparametric regression models.
Thanks for your questions:

a. The analysis of this type of regularization (l2 penalty centered at theta**) could be carried out in the same setting as the one we do. Indeed, it can sometimes be viewed as a special case of the analysis we do. However, there are three important differences:

1. We consider the surrogate sample size m to be finite. The effect of finite m in the scaling laws we derive (Eq (4), Eq (10), Eq (11), etc) is important, and would not be modeled by the setting proposed by the AE: the first error term in the square brackets in Eq. (4) would disappear. On the other hand, we believe it is very important to capture this effect. In practice, the scaling law (4) can be used to decide how much surrogate data to acquire, and this is only possible if we model the effect of finite m.

2. The regularization effect produced by surrogate data depends of course on the distribution of the surrogate data itself. While thinking of it as an l2 penalty can provide useful intuition, it is not generally correct even in very simple models. For instance, in the Gaussian sequence model of Section 3.1, if the model is heteroscedastic, then the regularization will be a weighted l2, depending on the noise distribution. Similarly for our other theoretical results. These examples can be treated as corollaries of our results, and we plan to add them to our revision.

3. Finally, the choice of theta** is of course very important, and can significantly change the behavior of the weighted ERM scheme. While in very simple models and/or theoretical work, we can pretend that we have a good guess, in large high-dimensional models, there is typically no practical way to come up with a meaningful guess without surrogate data.

b. Thank you very much for these points. Indeed the $\Lambda(\alpha)$ is a typo: this should be $R_{test}(\alpha)$. The uniformity interval $[\epsilon_0,1-\epsilon_0]$ can be replaced by $[0,1]$ when $\delta,\delta_s>1$. This is also confirmed visually in Figure 4. If $\delta$ or $\delta_s<1$, then a `phase transition’ can occur at $\alpha=0$ or $\alpha=1$, which is why we focus on the interval $[\epsilon_0,1-\epsilon_0]$. While this phase transition phenomenon is quite interesting, we do not have space to elaborate on it in this submission.
We know however that when this phase transition occurs, the test error is typically higher at $\alpha=0$ or $\alpha=1$. Therefore, from a practical point of view, there is no loss of generality in focusing on $[\epsilon_0,1-\epsilon_0]$.
Finally, the test error $R_{test}(\theta)$ is defined in line 54, and for the specific case at hand in line 199.
As witnessed by the references provided by the reviewers, adding surrogate data to training is a practice of great current interest in itself. This is different from data augmentation, which uses transformations of the original data, and from regularization, which does not use surrogate data. We will emphasize the relation to and distinction from  these lines of work in our revision.

The referee also mentions three related works. All of these papers are very different and cannot be compared to ours. 

The most important difference is all of these papers use vanilla ERM instead of weighted ERM. As a consequence, if the surrogate data sample is sufficiently large, the effect of surrogate data will drown the original data, and the resulting model will perform poorly. In other words, if we compare our approach to theirs in a setting in which the surrogate dataset is significantly larger than the original one, our approach will outperform theirs by a multiplicative factor that can be arbitrarily large. 
(Of course, the naive solution to this problem is to add only a small fraction of surrogate data, but this is suboptimal.)

Overcoming this fundamental problem is the very starting point of our work. Hence our work takes the next step beyond what is accomplished in these papers.

We remark the following additional differences:
1. Hashimoto, T., 2021, July. Model performance scaling with multiple data sources. This paper derives a low-dimensional scaling result for data mixtures. However, the settings studied are such that the exponent is always equal to one.  
2. Kang, F., Just, H.A., Sahu, A.K. and Jia, R., 2024. Performance scaling via optimal transport: Enabling data selection from partially revealed sources.  
This paper is entirely empirical. It assumes without mathematical justification that the error is an affine function of the Optimal Transport distance. Coefficients are fitted to this postulated relation without providing insights into how the scaling behavior depends on the mixture proportion. The only theorem assumes that the postulated scaling law holds exactly, which is obviously unrealistic.
In conclusion, the real problem addressed in this paper is actually very different from ours. Given a certain postulated law, they optimize the proportion (which they do by gradient descent). Our work is about deriving a correct scaling law.
3. Ye, J., Liu, P., Sun, T., Zhou, Y., Zhan, J. and Qiu, X., 2024. ‘Data mixing laws: Optimizing data mixtures by predicting language modeling performance’. 
This paper was posted on arxiv on March 24. As such, it is concurrent or follow-up work. Also, our work implies that the “mixing law” they suggest does not hold in any of the  models that we can analyze mathematically.  (The law they propose in Eq (1) is exponential in a linear combination of the proportions, while we prove a different relationship.)
Thanks for the responses. I have seriously re-read the manuscript, attempted derivations myself, and read additional references. 

I admit that some of my previous reviews are inaccurate (on the evaluation loss and training with "unrelated data"). The quoted theories are indeed interesting.

I like the idea of this paper. I feel the limitations are these stylized cases, generalized from Stein's phenomenon, still have gaps from practical use cases. For example, the paper will greatly improve its impact and attractiveness to readers beyond theory people if it can connect to commonly used practices such as regularization, data augmentation, etc.

It is unclear whether the currently proposed scaling laws are practically useful. For example, a number of papers exist studying the problem of mixing data from different distributions to improve model performance, providing scaling functions with high accuracy and applying them to broad use cases including foundation models.
E.g.,
[Model performance scaling with multiple data sources]
[Performance scaling via optimal transport: Enabling data selection from partially revealed sources]
[Data mixing laws: Optimizing data mixtures by predicting language modeling performance]

Do the authors think the proposed methods are practically competitive compared with these works?

My current opinion is [weak reject] for the presentation issue outweighs the merit of the theoretical results.
I thank the authors for their clarification. I do realize that these losses behave similarly, however in a paper such as this I think it should be addressed when presenting theory and should be explicitly mentioned in the paper. The authors have briefly commented regarding the regularization parameter, setting of Theorem 3.1, and my concerns about partitioners blindly using dummy data. However, they have not provided any indication on whether they intend to address these concerns in their paper, and if so, detailed discussion on how the changes to the document, its framing, and experiments will be made. Without this, I cannot adjust my score.
Dear Author(s),

I am curious about the following points. Could you please provide some comments? Thank you very much.

1. Would the theoretical analysis still hold if we were to replace the surrogate data loss term with an l2 penalty centered at θ** (whether carefully designed or arbitrarily selected)? If not, could you please elaborate on the challenges this would pose for the proof? If it would, considering that this substitution could significantly simplify the problem, could you provide insights on why the use of surrogate data remains essential?

2. I notice that Theorem 3 characterizes the concentration of the risk to R_test(α). By the way, could 'Λ(α)' possibly be a typo? Additionally, I didn't see a definition for R(θ). Would the concentration weaken or perhaps improve if α were to fall outside this interval [ε0, 1−ε0]?
Dear Reviewer 3jgb,

Thank you very much for submitting your review report. The author(s) have posted responses to your review. Could you kindly provide comments on whether your concerns have been adequately addressed?

AC
Dear Reviewer XfMG,

Thank you very much for submitting your review report. The author(s) have posted responses to your review. Could you kindly provide comments on whether your concerns have been adequately addressed?

AC
Many thanks for the clarifications. My concerns are addressed. Conditioned on a better presentation and a more comprehensive literature review, I will raise my score and vote for acceptance.
Thank you for the clarification. Good luck!