Abstract: Why and when is deep better than shallow? We answer this question in a framework that is agnostic to network implementation. We formulate a deep model as an abstract state-transition semigroup acting on a general metric space, and separate the implementation (e.g., ReLU nets, transformers, and chain-of-thought) from the abstract state transition. We prove a bias-variance decomposition in which the variance depends only on the abstract depth-$k$ network and not on the implementation (Theorem 1). We further split the bounds into output and hidden parts to tie the depth dependence of the variance to the metric entropy of the state-transition semigroup (Theorem 2). We then investigate implementation-free conditions under which the variance grow polynomially or logarithmically with depth (Section 4). Combining these with exponential or polynomial bias decay identifies four canonical bias-variance trade-off regimes (EL/EP/PL/PP) and produces explicit optimal depths $k^\ast$. Across regimes, $k^\ast>1$ typically holds, giving a rigorous form of depth supremacy. The lowest generalization error bound is achieved under the EL regime (exp-decay bias + log-growth variance), explaining why and when deep is better, especially for iterative or hierarchical concept classes such as neural ODEs, diffusion/score-matching models, and chain-of-thought reasoning.
1. Introduction
In modern machine learning, deeper neural networks consistently outperform shallow ones across diverse domains. However, this empirical success contradicts classical statistical learning theory, which suggests that increasing model depth—and thus complexity—should lead to overfitting and poor generalization. Existing theoretical attempts to resolve this "depth supremacy" often rely on architecture-specific assumptions, such as norm-constrained ReLU networks. This paper introduces a universal, implementation-agnostic framework to explain why depth is beneficial for models ranging from CNNs and Transformers to Neural ODEs and Chain-of-Thought (CoT) reasoning.
2. Theoretical Framework: Abstract State-Transitions
To achieve a universal theory, we abstract away specific architectural details like weights and activation functions. Instead, we model a deep network as a sequence of transformations within an abstract state-transition semigroup acting on a metric space.
In this view, a network of depth $k$ is a composition of $k$ hidden state transitions followed by a readout function. Our analysis centers on an implementation-agnostic bias-variance decomposition (Theorem 1). Crucially, we prove that the variance component depends solely on the abstract depth $k$ and the geometric properties of the state-transition semigroup, rather than the specific implementation. By applying Rademacher complexity and Dudley’s entropy integral, we decompose the variance into hidden and output layer contributions, allowing us to study how complexity scales with depth.
3. The Four Regimes of Depth Supremacy
The interplay between the rate of approximation (bias decay) and the growth of statistical complexity (variance growth) defines the generalization performance. We identify four canonical regimes based on whether bias decays exponentially (E) or polynomially (P), and whether variance grows logarithmically (L) or polynomially (P).
As shown in the figure above, each regime exhibits a distinct bias-variance trade-off. The optimal depth $k^*$ is found at the minimum of the generalization error curve (green line).
- EL Regime (Exponential Bias, Logarithmic Variance): This is the "sweet spot" for deep learning. The model rapidly approximates the target concept while its capacity to overfit grows very slowly with depth.
- EP/PL/PP Regimes: These represent scenarios where either approximation is slower or complexity grows faster, leading to higher overall generalization error.
4. Key Results and Implications
Our mathematical analysis yields several critical insights into depth supremacy:
- Optimal Depth is Rarely One: Across all regimes, the optimal depth $k^*$ typically grows with the sample size $n$. For instance, in the EL regime, $k^* \approx \frac{1}{2\alpha} \log n$. This provides a rigorous theoretical foundation for the empirical preference for deep architectures.
- Superiority of Iterative Models: The EL regime naturally describes concepts with hierarchical or iterative structures. This explains the exceptional performance of models like diffusion models, neural ODEs, and LLM Chain-of-Thought prompting, where deep composition is fundamental to the task.
- Generalization Hierarchy: We prove a strict hierarchy in generalization performance: $EL < EP < PL < PP$. Tasks involving traditional non-smooth functions (e.g., Sobolev spaces) often fall into the less efficient PL or PP regimes, making depth supremacy harder to prove in those classical contexts.
- Contractive Dynamics: We find that "contractive" hidden layers—those that map inputs closer together—lead to logarithmic variance growth, facilitating the highly efficient EL regime.
5. Conclusion
This work provides a novel bridge between dynamical systems, coarse geometry, and deep learning theory. By moving beyond implementation-specific bounds, we show that depth supremacy is a fundamental property of how complex concepts are approximated through composed transitions. While this theoretical framework assumes successful optimization, it sets the stage for future research into architectural designs that leverage favorable state-transition properties to maximize generalization.
Summary updated