Modern machine learning models are often trained on large datasets assembled from many different sources, whose statistical properties can differ substantially. Understanding how this heterogeneity affects generalization performance is therefore important for explaining how model performance changes as model size increases. In this work, we study this question in linear random-feature models and show that mixtures of datasets with different covariance structures can give rise to a range of multiple-descent phenomena. We derive exact asymptotic expressions for the test error of each data source in the high-dimensional regime, and show how heterogeneity in covariance scale and spectral structure can introduce additional, group-dependent interpolation thresholds as model size increases. These phenomena arise even with noiseless labels and linear activations, showing that neither label noise nor activation nonlinearity is necessary for multiple-descent. Our results therefore provide a different perspective from classical explanations of multiple descent. More broadly, our results have potential implications for algorithmic fairness by showing that model scaling can affect different data groups unevenly, amplifying disparities in their generalization errors. We validate our theoretical results on synthetic Gaussian mixtures and real-world datasets, including MNIST and CIFAR-10.
Figures & tables
Figure 1: Triple descent in a linear RF model. Cartoon bias curves for a heterogeneous mixture of n1 samples with power-law covariance Σ1=Σ=diag(1,1/2,…,1/d) and n2 samples with rescaled covariance Σ2=εΣ , where ε≪1 . The group-wise bias terms B1 ( left ) and B2 ( right ) are plotted against ψ=m/n , with network width m and total sample size n=n1+n2 . For small ε , the peaks near ψ=p1:=n1/n ( m=n1 ) have respective heights asymptotic to B(ε):=2η(p1/ϕ)p2εp1 and εB(ε) , as predicted by Corollary 7 . Here, ϕ=d/n>1 , d is the input dimension, and η is the explicit function defined in that corollary. Both curves diverge at the classical interpolation threshold ψ=1 ( m=n ). Horizontal dotted lines mark the large-width limits η(1/ϕ) and εη(1/ϕ) .
Figure 2: Triple-descent in linear RF on synthetic data mixture with different spectral exponents. We train a linear RF model ( 3 ) on a mixture of two Gaussian groups ( 1 )–( 2 ) with total sample size n=1000 . Group 1 has covariance matrix Σ1=diag(λ1(1),…,λd(1)) , where λi(1)∝i−α and α=1 . Group 2 is defined analogously with λi(2)∝i−β and β=2.2 . Thus, Group 1 has the flatter spectrum and corresponds to the harder-to-learn population. We plot the test error of Group 1 ( left ) and Group 2 ( right ) versus the model’s width m for different mixture proportions p1∈{1/4,1/2,3/4} , over 20 runs (error bars). In addition to the classical interpolation threshold at m=1000 , each curve exhibits an additional peak near the group-specific threshold m=n1=p1n as predicted by Corollary 7 .
Figure 3: Multiple-descent in linear RF on synthetic data mixture with different scales. We train a linear RF model ( 3 ) on a mixture of four Gaussian groups with total sample size n=600 . For Group k, the inputs are sampled as x(k)∼N(0,Σk) , with isotropic covariance Σk=εkId . The four groups have sizes (n1,n2,n3,n4)=(50,100,200,250) and scales (ε1,ε2,ε3,ε4)=(1,10−3,10−5,10−7) . We plot the test error of Group 2 versus the model’s width m over 20 runs (error bars). As predicted by Theorem 6 , the test error of Group 2 exhibits multiple interpolation peaks near the cumulative sample sizes m=n1=50 , m=n1+n2=150 , m=n1+n2+n3=350 , and m=n=600 . An extended figure with test error curves for all 4 groups is presented in Appendix A.1 .
Figure 4: Triple-descent in linear RF model on MNIST & CIFAR-10 mixtures with different scales. We train linear RF models ( 3 ) on two-group mixtures constructed from MNIST and CIFAR-10. For each dataset, Group 1 consists of the original inputs, while Group 2 is obtained by re-scaling the inputs by ε , so that Σ2=εΣ1 . We use ε=10−3 for MNIST and ε=10−5 for CIFAR-10. In all experiments, the total training sample size is fixed at n=500 , and we vary the mixture proportion p1∈{1/4,1/2,3/4} . We plot the test error of Group 2 derived from MNIST ( left ) and derived from CIFAR-10 ( right ) as a function of model size m , over 10 runs (error bars). For both groups, an additional interpolation peak appears near the group-specific threshold m=n1=p1n , shifting with the mixture proportion, while the classic interpolation peak remains fixed at m=n=500 . An extended figure (with Group 1 for both datasets) can be found in Appendix A.2 .
Figure 5: Triple-descent in linear RF model on MNIST & CIFAR-10 mixtures with different exponents. We train linear RF models ( 3 ) on two-group mixtures constructed from MNIST and CIFAR-10. For each dataset, Group 1 consists of the original inputs, while Group 2 is obtained through a nonlinear transformation that produces a flatter empirical covariance spectrum. All experiments fix n=300 and vary p1∈{1/4,1/2,3/4} . We plot the test error of Group 2 derived from MNIST ( left ) and derived from CIFAR-10 ( right ) as a function of model size m , over 50 runs for MNIST and 30 runs for CIFAR-10 (error bars). In both groups, an additional peak appears near the group-specific threshold m=n1=p1n predicted by our theory (Corollary 7 ), while the classical interpolation peak remains fixed at m=n=300 . Additional results are provided in Appendix A.2 .
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Multiple-descent in linear RF on synthetic data mixture with different scales. For this experiment, we train a linear random-features model on a mixture of four Gaussian groups with total sample size n=600 . For Group k, the inputs are sampled as x(k)∼N(0,Σk) , with isotropic covariance Σk=εkId . The four groups have sizes (n1,n2,n3,n4)=(50,100,200,250) and scales (ε1,ε2,ε3,ε4)=(1,10−3,10−5,10−7) , so that the groups differ only in the overall scale of their input covariances. The labels in each group are generated noiselessly by the same ground-truth weights (i.e. w∗(1)=w∗(2)=w∗(3)=w∗(4)=w∗ ). We plot the test error of Group 1 ( upper left ), Group 2 ( upper right ), Group 3 ( bottom left ), and Group 4 ( bottom right ) versus the model’s width m over 20 runs (error bars). As predicted by Theorem 6 , the test error of each group exhibits multiple interpolation peaks near the cumulative sample sizes m=n1=50 , m=n1+n2=150 , m=n1+n2+n3=350 , and m=n=600 , demonstrating that strong heterogeneity in covariance scale can generate arbitrarily many interpolation peaks (that is dependent on the number of mixtures in the data source).
Figure 7: Power-law spectra for MNIST. We plot the trace-normalized eigenvalues of the empirical covariance matrices against eigenvalue rank k for Group 1 (original MNIST inputs) and Group 2 (nonlinearly transformed inputs). Solid lines denote the empirical spectra, while dashed lines denote the corresponding power-law fits.
Figure 8: Power-law spectra for CIFAR-10. We plot the trace-normalized eigenvalues of the empirical covariance matrices against eigenvalue rank k for Group 1 (original CIFAR-10 inputs) and Group 2 (nonlinearly transformed inputs). Solid lines denote the empirical spectra, while dashed lines denote the corresponding power-law fits.
Figure 9: Triple-descent in linear RF on MNIST & CIFAR-10 mixtures with different scales. We train linear random-features models on two-group mixtures constructed from MNIST ( top row ) and CIFAR-10 ( bottom row ). For each dataset, Group 1 consists of the original inputs, while Group 2 is obtained by re-scaling the inputs by ϵ , so that Σ2=ϵΣ1 . We use ϵ=10−3 for MNIST and ϵ=10−5 for CIFAR-10. In both experiments, the total training sample size is fixed at n=500 , and we vary the mixture proportion p1∈{1/4,1/2,3/4} , corresponding to n1∈{125,250,375} . We plot the test error of Group 1 ( left column ) and Group 2 ( right column ) as a function of model size m , over 10 runs (error bars). For both MNIST and CIFAR-10, an additional interpolation peak appears near the group-specific threshold m=n1=p1n , shifting with the mixture proportion, while the classic interpolation peak remains fixed at m=n=500 .
Figure 10: Triple-descent in linear RF on MNIST & CIFAR-10 mixtures with different exponents. We train linear random-features models on two-group mixtures derived from MNIST ( top row ) and CIFAR-10 ( bottom row ). For each dataset, Group 1 consists of the original inputs, while Group 2 is obtained through a nonlinear transformation that produces a flatter empirical covariance spectrum. In both experiments, the total training sample size is fixed at n=300 , and we vary the mixture proportion p1∈{1/4,1/2,3/4} , corresponding to n1∈{75,150,225} . We plot the test error of Group 1 ( left column ) and Group 2 ( right column ) as a function of model size m , over 50 runs for MNIST and 30 runs for CIFAR-10 (error bars). For both MNIST and CIFAR-10, an additional interpolation peak appears near the group-specific threshold m=n1=p1n predicted by our theory (Corollary 7 ), while the classic interpolation peak remains fixed at m=300 .
Modern machine learning systems are trained on mixtures of data from different domains, and choosing the right mixture can substantially improve downstream performance. Despite an extensive literature on data mixing and reweighting, existing work is largely empirical and it remains unclear when auxiliary data genuinely improves scaling laws rather than merely providing more samples. To gain insight into this question, we study a high-dimensional mixed-data regression model with a shared regression function, heterogeneous covariances and noise levels, and dataset sizes that may grow at different rates. We establish the minimax risk under an ellipsoidal parameter constraint for the general covariance structure and derive deterministic equivalents for the test error of ridge regression under commutative covariances. We then specialize to a target domain and an auxiliary domain with aligned power-law covariance spectra, where the theory yields explicit scaling laws in terms of spectral decay, target regularity, and the relative growth of the two datasets. These laws identify regimes in which combining data mixtures provably yields a faster scaling rate than using either dataset alone. In particular, improving the scaling law requires a specific interplay between spectra and relative sample sizes of the domains. Our numerical experiments on language models exhibit the same qualitative phenomenon: appropriate data mixtures yield a faster decrease in target-domain test loss than training on either domain alone.
Diyuan Wu, Lehan Chen, Theodor Misiakiewicz +1
Institute of Science and Technology Austria (ISTA). · Department of Applied and Computational Mathematics, Yale University. · Department of Statistics and Data Science, Yale University.
In modern parametric model training, full-batch gradient descent (and its variants) suffers due to progressively stronger biasing towards the exact realization of training data; this drives the systematic ``generalization gap'', where the train error becomes an unreliable proxy for test error. Existing approaches either argue this gap is benign through complex analysis or sacrifice data to a validation set. In contrast, we introduce decoupled descent (DD), a novel theory-based training algorithm that satisfies a train-test identity -- enforcing the train error to asymptotically track the test error for stylized Gaussian mixture models. Within this specific regime, leveraging approximate message passing theory, DD iteratively cancels the biases due to data reuse, rigorously demonstrating the feasibility of zero-cost validation and 100% data utilization. Moreover, DD is governed by a low-dimensional state evolution recursion, rendering the dynamics of the algorithm transparent and tractable. We validate DD on XOR classification, yielding superior performance compared to GD; additionally, we implement noisy MNIST and non-linear probing of CIFAR-10, demonstrating that even when our stylized assumptions are relaxed, DD narrows the generalization gap compared to GD.
Delayed generalization, where training accuracy becomes nearly perfect substantially before test accuracy, has often been studied in the context of the depth and compositional structure of deep networks. In this paper, we ask whether delayed generalization can occur in simpler settings. We show that it can arise in a linear model trained with gradient descent and an exponential-tail loss on linearly separable data. We characterize the finite-time hyperplane dynamics into three phases: a population phase, a support vector dominated unlearning phase and a generalization phase. The convergence of the residual beyond the maximum-margin direction is sufficient for the unlearning phase to begin. In the support vector dominated phase, we characterize the hyperplane dynamics. The time scale in these dynamics causes delayed generalization. We validate our theory through controlled experiments varying population and support-vector distributions, and further verify the predicted bias behavior in a deep model with a single output neuron on MNIST. Our results provide a unified characterization of the asymptotic and finite-time dynamics underlying delayed generalization in linear models.