CS Paper Radar

New Multiple Descent Phenomena Induced by Heterogeneous Data

Mark-Anthony Moisescu-Pareja, Elvis Dohmatob

cs.LG stat.ML ·submitted 2026-10-27 21:53 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

When do data mixtures improve scaling laws? Insights from high-dimensional regression

cs.LG stat.ML ·2026-09-29 ·Diyuan Wu, Lehan Chen, Theodor Misiakiewicz, Marco Mondelli
similarity 0.71
Abstract

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.

0.44

Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult

cs.LG math.OC ·2026-09-15 ·Alexander Tyurin
similarity 0.61
Abstract

Modern large-scale machine learning tasks often require multiple workers, devices, CPUs, or GPUs to compute stochastic gradients in parallel and asynchronously to train model weights. Theoretical results typically distinguish between two settings: (i) the homogeneous setting, where all workers have access to the same data distribution, and (ii) the heterogeneous setting, where each worker operates on different data distributions. Known optimal time complexities in these settings reveal a significant gap, with far more pessimistic guarantees in the heterogeneous case. In this work, we investigate whether these pessimistic optimal time complexities can be overcome under different assumptions. Surprisingly, we show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm. We then turn to the interpolation regime and demonstrate that the weak interpolation assumption alone is also insufficient. Finally, we introduce a minimal combination of irreducible assumptions, strong interpolation and the local Polyak-Lojasiewicz condition, to derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting, without requiring identical data distributions.

0.20

Whitening Inverts the Hierarchy: What the Norm of a Whitened Embedding Measures

cs.LG cs.AI ·2026-09-19 ·Mohammed Ahnouch, Lotfi Elaachak
theory similarity 0.61
Abstract · 16 pages, 2 figures

Whitening a foundation-model embedding and using its squared norm as a training-free likelihood surrogate is motivated by the observation that whitened coordinates often appear approximately standard normal. We show that this observation follows from the projection central limit theorem and therefore does not imply a Gaussian joint distribution. Across multiple encoders and three training objectives, we find systematic over-dispersion of the whitened radius relative to the Gaussian reference, including against distributional clones with identical mean and covariance. We further show that the commonly reported agreement between empirical and theoretical norm statistics is an algebraic consequence of in-sample whitening and does not constitute evidence for Gaussianity. We identify the mechanism behind this behavior: whitening reverses the encoder's spectral hierarchy, shifting the contribution to the squared norm toward near-degenerate directions that encode predominantly noise. In these directions, the dominant variability is governed by a single input-dependent scale. We estimate this scale from two moments and use it to predict, without additional free parameters, the cross-dependence between disjoint spectral halves. These results indicate that the squared whitened norm is better interpreted as a Mahalanobis measure of semantic atypicality than as a log-likelihood. This interpretation explains both its practical effectiveness and its calibration failures: the statistic can rank and detect atypical samples consistently with nonparametric density estimates and across encoders trained with different objectives, while Gaussian tail thresholds can be inaccurate by orders of magnitude. etc.

0.34

Learning with Synthetic Data via SGD in High-Dimensional Linear Regression

cs.AI stat.MLcs.LG ·2026-09-09 ·Jichu li, Difan Zou
similarity 0.61
Abstract

Synthetic data has become a promising way to scale model training beyond limited human-generated data but it may also induce strong model collapse (Dohmatob et al., 2024), where any fixed fraction of synthetic data prevents model performance from improving under data scaling, leaving a non-vanishing excess risk floor. In this paper, we study how synthetic data affects the generalization of one-pass SGD in high-dimensional linear regression with model shift. We establish finite-sample risk bounds for mixed and two-stage training, separating standard bias and variance from source-mismatch effects, namely fluctuation and persistent drift under mixing and filtered initialization bias under two-stage. These bounds reveal a sharp contrast: mixed training induces strong model collapse, while two-stage training avoids the floor by using synthetic data only in the first stage, showing that collapse is not inevitable under a simple data curriculum. Under a random sketch model, we further obtain scaling laws for both protocols, with tight results for mixed training in the optimization-saturated regime. These laws show that larger models may amplify synthetic-induced degradation under mixing, and quantify how high-quality synthetic pretraining may reduce bias in two-stage training. Finally, we establish an exact finite-sample necessary-and-sufficient condition for two-stage training to strictly outperform real-only training under the same real-data budget and identical real-stage updates. Overall, our results highlight that synthetic data is neither inherently harmful nor beneficial; its effect depends critically on both its quality and the training protocol used to incorporate it.

0.33

A Theoretical Analysis of Generalization Dynamics in Neural Networks under Gradient Descent with Weight Decay

cs.LG math.OC ·2026-09-07 ·Yuqing Wang, Ioannis G. Kevrekidis, Mikhail Belkin
hot direction similarity 0.59
Abstract

Understanding generalization remains a central challenge in machine learning because it requires jointly considering data, architecture, and training dynamics. In this paper, we develop a theoretical framework that characterizes how these factors jointly shape generalization performance throughout training. More precisely, we study a broad class of neural networks trained under the $\ell^2$ loss by gradient descent (GD) with weight decay, and prove the convergence of GD to a neighbourhood of the global minimizers of the empirical loss. By partitioning the space based on the input data, we then decompose the population error into data error, optimization error, and prediction variation error, and bound them separately. In particular, for the prediction variation error, which measures the oscillations of the learned function, we propose (local) approximate homogeneity and derive explicit cellwise and layerwise bounds for its evolution along the training trajectory. These bounds yield two important implications: a necessary condition of improved generalization explains differences in layerwise generalization behavior; a sufficient condition describes delayed generalization and provides a theoretical characterization of grokking.

0.47

Benign Overfitting under Heterogeneous Input Fusion

cs.LG stat.ML ·2026-10-07 ·Houzhen Liu, Xiaobo Xia
similarity 0.59
Abstract · 51 pages, 6 figures

Benign overfitting is extensively studied when learning from a single high-dimensional input, but its behavior under heterogeneous input fusion remains largely unexplored. We study this question for minimum-norm linear interpolation under a heterogeneous Gaussian design, comparing two statistically dependent input blocks with their fusion while holding the underlying population task fixed. For regression, we identify a full-spectrum covariance certificate whose asymptotic status is independent of the cutoff threshold and prove that it is preserved by every positive-semidefinite joint covariance consistent with the two marginals. This protection is sharp, yet it does not extend to all benign regression problems: outside the certified regime, two benign marginals can have a harmful fusion. For one-sparse Gaussian classification, benignity in the regular regime is characterized by the balance between surviving predictive signal and nuisance contamination. Fusion can move these two quantities in opposite directions, and within this model class every marginal-to-joint benign/non-benign pattern is attainable. We further show that the same fused input can have qualitatively different effects on regression and classification. These results establish that benign overfitting under heterogeneous fusion is determined by the joint signal and spectral geometry created by input interaction, rather than by marginal benignity alone.

0.20

Learning Samples Importance: Parameterizing Dual Variables in Everywhere Learning

cs.LG eess.SP ·2026-09-28 ·Ignacio Boero, Jonathan Nixon, Alejandro Ribeiro
similarity 0.59
Abstract

Everywhere learning provides a principled framework for training AI models under constraints that must hold throughout the data distribution. In the dual domain, these pointwise constraints give rise to functional dual variables. In this work, we propose to learn these dual variables, motivated by the fact that their values encode useful information about the underlying constrained problem. By representing the dual variable as a parametric function of each sample, we enable the learned multiplier to be evaluated on new, unseen samples. This contrasts with standard empirical dual formulations, which assign an independent multiplier to each training sample. We characterize the error in the recovered primal solution induced by restricting the dual variable to a parametric function class and show that it is controlled by how well this class approximates the optimal statistical multiplier. Moreover, we show that the learned parametric multiplier retains the sensitivity interpretation of the optimal statistical multiplier, yielding approximate sensitivity guarantees that extend beyond the samples used for training. We empirically validate our theory across a variety of everywhere learning tasks, showing that the resulting constrained problems can be solved efficiently and that the learned dual variables provide meaningful representations of sample-level sensitivity.

0.28

Information-Theoretic Scaling Laws for Generative Diffusion Training

cs.LG ·2026-10-23 ·Druv Pai, Dejan Stancevic, Yi Ma, Luca Ambrogioni
code/data similarity 0.59
Abstract · 42 pages, 15 figures

Diffusion models trained on increasingly large datasets sampled from the same data distribution will converge to the same learned distribution. However, in practice, a model trained on finite data depends on the particular training dataset; this dependence is reflected in properties of the model's outputs, such as memorization and sample quality. To understand this dependence through an information-theoretic lens, we study \textit{model information}, a computationally tractable measure of how much samples from the trained model depend on the particular training dataset. We explore its scaling behavior as model size and training dataset size vary. Specifically, we uncover two qualitatively distinct scaling regimes: (1) a nonlinear model information regime marking the transition from pure memorization to imperfect generalization, and (2) a generalization regime characterized by linear scaling of the model information and progressively improved generalization and sample quality. We then posit an information-theoretically principled scaling law to quantify these two regimes, and show that this law yields induced scaling laws for memorization and sample quality. We finally demonstrate that these induced scaling laws extrapolate well outside the fit's domain. Our results demonstrate information-theoretic principles for memorization and sample quality scaling laws in diffusion models. Our code is publicly available on \href{https://github.com/DruvPai/diffusion_info_theory_scaling_law}{GitHub}.

0.20