When Do Early-Exit Networks Generalize? A PAC-Bayesian Theory of Adaptive Depth

• URL: http://arxiv.org/abs/2604.15764v1
• Date: Fri, 17 Apr 2026 07:08:33 GMT
• Title: When Do Early-Exit Networks Generalize? A PAC-Bayesian Theory of Adaptive Depth
• Abstract summary: Early-exit neural networks enable adaptive computation by allowing confident predictions to exit at intermediate layers.<n>Despite widespread deployment, their generalization properties lack theoretical understanding.<n>This paper establishes a unified PAC-Bayesian framework for adaptive-depth networks.
• Score: 13.891522069967507
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Early-exit neural networks enable adaptive computation by allowing confident predictions to exit at intermediate layers, achieving 2-8$\times$ inference speedup. Despite widespread deployment, their generalization properties lack theoretical understanding -- a gap explicitly identified in recent surveys. This paper establishes a unified PAC-Bayesian framework for adaptive-depth networks. (1) Novel Entropy-Based Bounds: We prove the first generalization bounds depending on exit-depth entropy $H(D)$ and expected depth $\mathbb{E}[D]$ rather than maximum depth $K$, with sample complexity $\mathcal{O}((\mathbb{E}[D] \cdot d + H(D))/ε^2)$. (2) Explicit Constructive Constants: Our analysis yields the leading coefficient $\sqrt{2\ln 2} \approx 1.177$ with complete derivation. (3) Provable Early-Exit Advantages: We establish sufficient conditions under which adaptive-depth networks strictly outperform fixed-depth counterparts. (4) Extension to Approximate Label Independence: We relax the label-independence assumption to $ε$-approximate policies, broadening applicability to learned routing. (5) Comprehensive Validation: Experiments across 6 architectures on 7 benchmarks demonstrate tightness ratios of 1.52-3.87$\times$ (all $p < 0.001$) versus $>$100$\times$ for classical bounds. Bound-guided threshold selection matches validation-tuned performance within 0.1-0.3%.

Related papers

• Quantum amplitude estimation beyond power-of-two schedules [0.0]
  Non-adaptive quantum amplitude estimation (QAE) fixes its Grover depths in advance, so every circuit can run in parallel.<n>We show that most of this gap comes from two conventional choices: subspace-based post-processing and power-of-two depth ladders.<n>We replace the first by the exact maximum-likelihood estimate, one matrix multiplication per batch of estimates, and the second by a geometric ladder with ratio $r approx 1.45$.
  arXiv  Detail & Related papers  (2026-09-02T15:20:50Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  We show that a lower bound holds for every admissible function and follows from a convex relaxation giving stronger bounds.<n>A theory verifies each agent one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point in the interval.
  arXiv  Detail & Related papers  (2026-06-30T06:10:25Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Exploring Sparsity and Smoothness of Arbitrary $\ell_p$ Norms in Adversarial Attacks [4.366212978228445]
  We show that the choice of $ell_p$ norms with $pin [1.3, 1.5]$ yields the best trade-off between sparse and smooth attacks.<n>These findings highlight the importance of principled norm selection when designing and evaluating adversarial attacks.
  arXiv  Detail & Related papers  (2026-02-06T10:19:14Z)
• Constructive Lyapunov Functions via Topology-Preserving Neural Networks [0.0]
  ONN achieves order-optimal performance on convergence rate, edge efficiency, and computational complexity.<n> Empirical validation on 3M-node semantic networks demonstrates 99.75% improvement over baseline methods.<n>ORTSF integration into transformers achieves 14.7% perplexity reduction and 2.3 faster convergence.
  arXiv  Detail & Related papers  (2025-10-10T17:46:52Z)
• Architecture-Aware Generalization Bounds for Temporal Networks: Theory and Fair Comparison Methodology [8.006116553957659]
  We provide the first non-vacuous, architecture-aware generalization bounds for deep temporal models.<n>For exponentially $beta$-mixing sequences, we derive bounds scaling as $ O!Bigl(R,sqrttfracD,p,n,log NNBigr), $ where $D$ is network depth, $p$ kernel size, $n$ input dimension, and $R$ weight norm.<n>Our delayed-feedback blocking mechanism transforms dependent samples into effectively independent ones while discarding only $O (1/log N
  arXiv  Detail & Related papers  (2025-08-08T06:57:49Z)
• LLMs are Bayesian, in Expectation, not in Realization [0.0]
  Large language models adapt to new tasks without parameter updates.<n>Recent empirical findings reveal a fundamental contradiction: transformers systematically violate the martingale property.<n>This violation challenges the theoretical foundations underlying uncertainty quantification in critical applications.
  arXiv  Detail & Related papers  (2025-07-15T22:20:11Z)
• Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification [83.25968588249776]
  We present a novel framework that combines over-approximation techniques from LiRPA-based approaches with a sampling-based method to compute tight intermediate reachable sets.<n>With negligible computational overhead, $textttPT-LiRPA$ exploiting the estimated reachable sets, significantly tightens the lower and upper linear bounds of a neural network's output.
  arXiv  Detail & Related papers  (2025-07-07T18:45:53Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION converges iterations of $cal(sqrtdK-)$ measured by gradient Karush-Kuhn-T (sqrtdK-)$. We show that LION can achieve lower loss and higher performance compared to standard SGD.
  arXiv  Detail & Related papers  (2024-11-12T11:30:53Z)
• Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep ReLU Networks [0.0]
  We show that any dataset with $N$ distinct points in $mathbbRd$ and $M$ output classes can be exactly classified.<n>We also prove a universal approximation theorem in $Lp(Omega; mathbbRm)$ for any bounded domain.<n>Our results offer a unified and interpretable framework connecting controllability, expressivity, and training dynamics in deep neural networks.
  arXiv  Detail & Related papers  (2024-09-10T14:31:21Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.