Why More Data Can Degrade Generalization Performance

130 concepts73 papers1 proposal

The foundational assumption of machine learning is that data is a strict asset: the more samples a model observes, the better it should generalize. Traditional statistical frameworks like Probably Approximately Correct (PAC) learning reinforce this view by providing upper bounds on error that shrink as the dataset grows.

However, as Tom J. Viering et al. point out in Open Problem: Monotonicity of Learning, these classical bounds only guarantee that the worst-case ceiling decreases. They do not guarantee that the actual, instantaneous expected risk decreases at every step. In fact, across a wide variety of standard algorithms—including empirical risk minimization with squared, absolute, or hinge losses—learning curves routinely exhibit non-monotonic behavior, where adding more training data paradoxically increases test error (Minimizers of the Empirical Risk and Risk Monotonicity by Marco Loog et al.).

Understanding why this happens requires moving past holistic averages and looking at how data interacts with model capacity, regularization, and inductive biases.

The Geometry of Sample-Wise Double Descent

The most prominent manifestation of non-monotonicity in modern deep learning is sample-wise double descent. While classical double descent describes performance fluctuations as a model's size changes, a parallel phenomenon occurs when model size is held constant and the dataset size increases.

To build intuition, consider a model with a fixed capacity (e.g., a fixed number of parameters $P$).

  • The Underdetermined Regime ($N \ll P$): When the number of training samples $N$ is very small, the model has far more parameters than constraints. It can easily interpolate the data. Under implicit regularization (such as the minimum-norm solution in linear regression or gradient descent paths in neural networks), the model chooses the smoothest possible function that fits the points, leading to decent generalization.
  • The Critical Threshold ($N \approx P$): As you add more data points, you introduce more constraints. When $N$ approaches $P$, the model is forced to use every ounce of its capacity to fit the training data exactly. It no longer has the freedom to choose a smooth interpolating function; instead, it must contort violently to pass through every noisy training point. This causes the variance of the estimator to explode.
  • The Overdetermined Regime ($N \gg P$): Once $N$ significantly exceeds $P$, the model can no longer interpolate the training set. It shifts to an averaging regime, smoothing out noise and causing the test error to decrease again.

Gal Kaplun et al. demonstrated in Deep Double Descent: Where Bigger Models and More Data Hurt that this peak is a robust property of modern deep learning, driven by what they term Effective Model Complexity. By analyzing the components of this error, Edgar Dobriban et al. showed via ANOVA that the spike in test error at the interpolation boundary is primarily driven by the volatile interaction between the specific training data sample and the random initialization of the network, rather than simple bias or variance alone (What causes the test error? Going beyond bias-variance via ANOVA).

Model Mismatch and the Dipping Phenomenon

Non-monotonicity is not exclusive to over-parameterized neural networks or parameter-counting thresholds. It also appears in simpler, classical settings due to a structural mismatch between the model's hypothesis space and the true data distribution—often called the "unrealizable" setting.

Robert P. W. Duin et al. characterized this in The Dipping Phenomenon, where a classifier reaches its peak accuracy at a finite training set size and degrades as the sample size approaches infinity.

Why does more data hurt an unrealizable model? When data is scarce, the learning algorithm focuses on the most dominant, coarse-grained features of the data distribution that align well with its inductive biases. However, as the dataset grows, the empirical risk minimizer is forced to account for fine-grained details or unmodelable components of the true distribution. Because the model lacks the capacity or structural flexibility to represent these components correctly, trying to fit them introduces conflicting gradients.

As Glenn Marion et al. demonstrated in Hyperparameters Evidence and Generalisation for an Unrealisable Rule, the model undergoes a non-monotonic "hump" in generalization error as it struggles to fit unmodelable features before eventually settling on the best global approximation its limited space allows.

Objective Mismatches and Unsupervised Degradation

Another driver of non-monotonic learning curves is a disconnect between what the model optimizes during training and what we actually care about during evaluation.

In a comprehensive review of learning curve shapes, Tom J. Viering et al. highlighted that when a mismatch exists between the training surrogate loss (e.g., cross-entropy) and the evaluation metric (e.g., zero-one classification error), adding data can lower the training loss while simultaneously causing the evaluation metric to degrade (The Shape of Learning Curves: a Review).

This counterintuitive behavior extends to unsupervised learning as well. Marco Loog et al. discovered that in K-means clustering, providing more data can cause clustering quality to significantly deteriorate (Counterintuitive Behavior of Clustering Quality: Findings for K-Means on Synthetic and Real Data). The additional data forces the cluster centers into configurations that are mathematically optimal for the internal variance objective function, but structurally incorrect for the actual underlying categories.

Restoring Monotonicity

If more data can hurt, practitioners cannot safely assume that data collection always yields positive returns. Researchers have pursued two main avenues to enforce monotone learning curves.

1. Optimal Regularization

The sample-wise double descent peak is often an artifact of fixed or sub-optimal hyperparameters. Preetum Nakkiran et al. demonstrated that optimal regularization can entirely mitigate double descent, turning the non-monotonic risk curve into a monotonically decreasing one (Optimal Regularization can Mitigate Double Descent).

Extending this to high-dimensional out-of-distribution settings, Jin-Hong Du et al. proved in Optimal Ridge Regularization for Out-of-Distribution Prediction that allowing the ridge penalty parameter to become zero or even negative can smooth out the risk curve completely, ensuring that more data always helps.

2. Algorithmic Wrappers

When the underlying learning algorithm cannot be altered, researchers use statistical gating. Tom J. Viering et al. proposed wrapper algorithms that use hypothesis testing to decide whether to accept a model trained on a larger dataset or stick to a model trained on a smaller subset, guaranteeing monotonicity with high probability (Making Learners (More) Monotone).

On the foundational side, Amit Daniely et al. resolved a long-standing open question by proving that any multiclass classification algorithm can be transformed into a strictly monotone version without sacrificing its core asymptotic accuracy (Monotone Learning).

By understanding that non-monotonicity arises from the delicate interplay of capacity thresholds, model mismatches, and optimization objectives, modern frameworks like Broken Neural Scaling Laws (Ethan Caballero et al. in Broken Neural Scaling Laws) can better extrapolate performance, preventing costly training failures before they occur.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_monotonic_learning_curves_da3fd003,
  title = {non-monotonic learning curves},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-monotonic-learning-curves/rdr_da3fd0030d3e45c68eef35256e859255},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_monotonic_learning_curves_da3fd003_v1,
  title = {non-monotonic learning curves},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-monotonic-learning-curves/rdr_da3fd0030d3e45c68eef35256e859255/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake