What is the relation between any suitable measure of model complexity, number of training examples and network size in deep learning?

Understanding the Trade‑off: Model Complexity, Training Data, and Network Size in Deep Learning

One of the most fundamental questions in deep learning research is how the size of a neural network, the amount of training data, and a measure of model complexity interact to determine a model’s generalisation performance. While many factors come into play, several theoretical concepts provide a clear framework for reasoning about this relationship.

1. What Do We Mean by Model Complexity?

In statistical learning theory, model complexity is quantified by capacity measures such as:

• VC dimension – the largest set of inputs that can be shattered by the hypothesis class.
• Rademacher complexity – the ability of a model class to fit random noise.
• Norm‑based measures – e.g., the spectral norm or Frobenius norm of weight matrices, which bound Lipschitz constants.
• Parameter count – a crude but often used proxy for capacity, especially for fully‑connected networks.

All of these measures increase as the network becomes “larger” (more layers, more units per layer, or larger weight magnitudes). A higher complexity class can represent more intricate functions, but it also risks over‑fitting if the data are insufficient.

2. Classical Generalisation Bounds

For many capacity measures, a generic bound on the generalisation error ε takes the form:

ε ≤ O( √( (C(H) + log(1/δ)) / n ) )

where:

• C(H) is a complexity term for hypothesis class H (e.g., VC dimension or Rademacher complexity).
• n is the number of training examples.
• δ is the confidence level.

This inequality tells us that, for a fixed model complexity, increasing the number of training examples reduces the bound on the generalisation error at a rate of 1/√n. Conversely, for a fixed dataset size, raising the complexity term raises the bound.

3. Parameter Count vs. Effective Complexity

Deep nets often have millions of parameters, yet they can generalise well even when n is much smaller than the parameter count. This apparent paradox is resolved by recognising that:

• Standard bounds based solely on raw parameter count are loose.
• Training with stochastic gradient descent (SGD) implicitly bias‑es the solution toward low‑norm regions of parameter space, effectively reducing the Rademacher complexity.
• Architectural constraints (e.g., convolutions, weight sharing, residual connections) limit the expressive power relative to an unrestricted fully‑connected network of the same size.

4. The Double‑Descent Phenomenon

Empirical studies have discovered a double‑descent curve when plotting test error against model size (or parameter count):

1. In the under‑parameterised regime (parameters < n), test error follows the classic bias‑variance trade‑off, decreasing as we add parameters.
2. At the interpolation threshold (the point where the model can perfectly fit the training data), test error spikes.
3. Beyond this threshold, in the over‑parameterised regime (parameters » n), test error drops again, often reaching values lower than the best under‑parameterised model.

Recent theoretical work relates this to the fact that, once a network can interpolate the data, optimisation dynamics (e.g., SGD) tend to select the “simplest” interpolating solution—one with minimal norm—thereby controlling effective complexity.

5. Scaling Laws for Neural Networks

Large‑scale experiments (e.g., language models, vision transformers) have uncovered simple empirical scaling laws:

Loss ≈ a·N−α + b·D−β + c·L−γ

where:

• N = number of model parameters (proxy for network size).
• D = number of training tokens (dataset size).
• L = compute budget (flops).
• α, β, γ are positive exponents found empirically (typically around 0.3–0.5).

These laws suggest a **smooth trade‑off**: increasing model size can compensate for a smaller dataset, and vice‑versa, as long as the total “effective compute” remains balanced.

6. Practical Takeaways

1. Match model capacity to data. If you have limited labelled data, favour architectures with built‑in inductive biases (e.g., convolutions, attention with relative positional encodings) rather than simply scaling up parameters.
2. Use regularisation that directly controls complexity. Weight decay, norm constraints, or spectral normalisation shrink the effective Rademacher / covering‑number terms.
3. Leverage data‑efficiency tricks. Data augmentation, semi‑supervised learning, and self‑supervision effectively increase n without collecting more labelled examples.
4. Don’t fear over‑parameterisation. In modern deep learning, training in the over‑parameterised regime often yields better generalisation, provided optimisation is stable and regularisation is present.

7. A Simple Guideline

For a quick sanity check, many practitioners use the rule of thumb:

n ≳ 10 × (effective parameters / 10⁶)

In words, aim for roughly ten training examples per million “effective” parameters (after accounting for architecture‑induced reductions). This heuristic is far from rigorous but aligns with empirical observations across vision and language tasks.

Conclusion

The relationship between model complexity, training data, and network size is not linear but governed by capacity measures, optimisation dynamics, and empirical scaling laws. While classical theory predicts a straightforward trade‑off (more data → better generalisation for a fixed model), deep learning expands this picture: over‑parameterised networks can still generalise well, and increasing model size can offset a modest amount of data, provided we control effective complexity through regularisation and architecture choice.

Understanding these intertwined factors helps practitioners design models that are both powerful and data‑efficient, steering the field toward more principled and scalable deep learning systems.