Why and When Deep is Better than Shallow: An Implementation-Agnostic State-Transition View of Depth Supremacy

Sho Sonoda, Yuka Hashimoto, Isao Ishikawa, Masahiro IkedaSubmission to ICLR 2026 · Rejected

TL;DR

This paper develops an implementation-agnostic theoretical framework explaining why and when deep architectures outperform shallow ones by treating deep learning as an abstract state-transition semigroup. By proving that statistical variance depends strictly on the geometry of the transition semigroup rather than the specific network implementation (e.g., ReLU networks vs. Transformers), the authors derive optimal network depths across four canonical bias-variance regimes. They show that optimal depth typically satisfies $k^* > 1$ ("depth supremacy"), with deep models offering the greatest advantage when tasks possess iterative or hierarchical structure, such as diffusion models, neural ODEs, and chain-of-thought reasoning.

What Problem Does This Paper Address?

Despite the undeniable empirical success of deep architectures, classical learning theory suggests that making networks deeper increases model complexity and should degrade generalization. While prior works have used VC-dimension, norm-based capacity controls, and compression bounds to explain depth, their analyses almost always rely on restrictive, implementation-specific assumptions (e.g., feedforward ReLU networks with tight norm constraints).

This paper tackles a fundamental theoretical question: Why and when is deep strictly better than shallow, independent of specific architectural implementations?

Methods

The authors formulate deep models through an algebraic and geometric lens:

  • Abstract State-Transition Semigroups: The data domain $\mathcal{X}$ is treated as an abstract metric space. Hidden layers are transitions $f \in \mathcal{F} \subset C(\mathcal{X}, \mathcal{X})$, the output layer is a readout $h \in \mathcal{H} \subset C(\mathcal{X}, \mathbb{R})$, and depth-$k$ networks form an abstract hypothesis class $\mathcal{H}_k = \mathcal{H} \circ B(k, \mathcal{F})$, where $B(k, \mathcal{F})$ is the word ball of length at most $k$.
  • Implementation-Decoupled Bias-Variance Decomposition (Theorem 1): The excess risk is split into implementation approximation error ($\varepsilon_{\text{imp}}$), model bias ($\varepsilon_{\text{model}}$), and estimation variance ($\hat{\mathfrak{R}}_S(\mathcal{H}_k)$). Crucially, the variance term depends solely on the abstract depth-$k$ composition, not on whether it is realized by a ReLU network, a CNN, or an LLM.
  • Hidden-Output Complexity Decomposition (Theorem 2): Using Dudley’s chaining on non-real-valued transition maps, the Rademacher complexity of $\mathcal{H}_k$ is bounded by the complexity of the readout layer $\mathcal{H}$ plus Dudley's entropy integral over the word ball $B(k, \mathcal{F})$ in an empirical metric $d_S$.
  • Covering Number Growth Rates via Dynamical/Group Theory: The authors establish algebraic conditions governing how the metric entropy of word balls scales with depth $k$:
  • Saturating / Polynomial covering numbers (Condition P1 & P2): Arzelà–Ascoli equicontinuity leads to saturation (no depth growth), while actions embedding into nilpotent Lie groups exhibit polynomial covering number growth governed by the Guivarc'h–Bass homogeneous dimension $D$.
  • Exponential / Super-exponential covering numbers (Conditions E1, E2, E3): Free actions, ping-pong dynamics, and uniformly expanding maps drive exponential to double-exponential covering growth.

Datasets

Not discussed in the paper. The work is purely theoretical and does not utilize empirical datasets or experimental benchmarks.

Key Insights and Ideas

  • Variance is implementation-agnostic: Generalization variance is dictated by how the semigroup generated by $\mathcal{F}$ transports points in state space $\mathcal{X}$, rather than by parameter counts or specific activation functions.
  • Rigorous Depth Supremacy ($k^* > 1$): By balancing bias decay (Exponential or Polynomial) against variance growth (root-Logarithmic or root-Polynomial), the authors delineate four canonical regimes: EL, EP, PL, and PP. In all regimes, balancing estimation and approximation errors leads to an optimal depth $k^*$ that grows with sample size $n$, proving shallow models ($k=1$) are generally suboptimal.
  • The "EL" Sweet Spot: The greatest statistical advantage of depth occurs in the EL regime (exponential bias decay coupled with logarithmic variance growth). Here, generalization error scales as $\mathcal{O}(\sqrt{\log(\log n)/n})$ at an optimal depth $k^* \sim \frac{\log n}{2\alpha}$. This regime naturally characterizes iterative and compositional processes such as contractive teacher-student setups, Neural ODEs, Picard iterations, diffusion models, and chain-of-thought reasoning.
  • Approximation efficiency dominates model complexity: Regimes with exponential bias decay yield shallow optimal depths ($k^* = \mathcal{O}(\log n)$), whereas polynomial bias decay requires deeper architectures ($k^* = \mathcal{O}(n^{\text{poly}})$).

Key Results

The paper provides closed-form asymptotic balances for optimal depth $k^*$ and the resulting generalization error:

Regime Bias Decay $\text{bias}(k)$ Variance Growth $\text{var}(k, n)$ Optimal Depth $k^*$ Optimal Generalization Bound $\text{gen}(k^*, n)$
EL $\exp(-\alpha k)$ $\sqrt{\log(k) / n}$ $\frac{\log n}{2\alpha} + \tilde{o}(1)$ $\asymp \sqrt{\frac{\log(\log n)}{n}}$
EP $\exp(-\alpha k)$ $\sqrt{k^\gamma / n}$ $\frac{\log n}{2\alpha} + \tilde{\mathcal{O}}(1)$ $\asymp \sqrt{\frac{(\log n)^\gamma}{(2\alpha)^\gamma n}}$
PL $k^{-\beta}$ $\sqrt{\log(k) / n}$ $\sim \left(\frac{2\beta n}{\log(2\beta n)}\right)^{1/(2\beta)}$ $\asymp \sqrt{\frac{\log n}{2\beta n}}$
PP $k^{-\beta}$ $\sqrt{k^\gamma / n}$ $\asymp n^{1 / (2\beta + \gamma)}$ $\asymp n^{-\beta / (2\beta + \gamma)}$
  • Across all settings, optimal depth grows monotonically with sample size $n$, formally demonstrating that larger datasets warrant deeper architectures.
  • Standard smoothness classes (Hölder, Sobolev, Besov) paired with ReLU nets typically fall into the less efficient PP or PL regimes, whereas compositional problems natively unlock the superior EL regime.

Limitations and Future Work

  • Optimization Gap: The analysis assumes an idealized two-stage learning process (exact empirical risk minimization over abstract maps followed by embedding), setting aside the non-convex optimization dynamics and gradient-based training hurdles found in practice.
  • Uniform and Worst-Case Bounds: Covering numbers are analyzed primarily under the supremum metric $d_\infty$ rather than data-dependent empirical pseudo-metrics $d_S$, which may yield conservative bounds for specific data distributions.
  • Concrete Architectures: While the framework conceptually covers transformers, CNNs, and LLM reasoning steps, working out explicit homogeneous dimensions or expansion constants for specific transformer architectures remains an open direction for future research.

Summary updated

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.
BibTeX
@misc{sonoda2025why,
  author = {Sho Sonoda and Yuka Hashimoto and Isao Ishikawa and Masahiro Ikeda},
  title = {{Why and When Deep is Better than Shallow: An Implementation-Agnostic State-Transition View of Depth Supremacy}},
  year = {2025},
  eprint = {2505.15064},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.15064},
}
Figure