Introduction
Training deep neural networks is arguably the tipping point of today’s success of deep learning models. Key techniques are residual connections and intermediate output heads informing the network’s hidden layers about their current performance [47 ] (He et al. 2016b). What was initially used only as training scheme [26 ] , quickly evolved as inference method to save computation on instances handled equally well by shallower parts of the network [48 ] and has since been applied to early-exiting language models and vision transformers [44 , 51 , 45 , 6 ] . Without early-exiting, a key failure mode of deep neural networks is overthinking [21 ] : samples correctly classified by earlier layers are propagated further, incurring unnecessary computation and potentially degrading predictions at later stages. At the core of training these early-exit networks lies an optimization problem considering a combined loss of all auxiliary and final output heads, as illustrated in Figure 1 a. As we show in this work, it is precisely this joint training formulation that gives rise to the turnpike phenomenon from optimal control, offering a principled explanation for why early-exit classifiers perform well and why overthinking can be avoided. With the turnpike phenomenon at hand, we are able to show that the early-exit depth required to reach a prescribed loss level is independent of the overall backbone depth. Consequently, the early-exit losses of networks of different depths are similar, as illustrated in Figure 1 b.
Figure 1. Illustration of a ResNet with early-exits (EE), the joint training formulation induces the turnpike phenomenon from optimal control, which implies that early-exiting ResNets of different depths have similar trajectories of the early-exit losses along the network depth.
Prior theoretical work has analyzed early-exit training either under restrictive assumptions such as strong convexity [26 ] or focused on layer-wise supervision regimes that lack the upstream gradient signal of joint optimization [43 ] . Consequently, a fundamental understanding of how joint early-exit training behaves and why one can expect intermediate classifiers to perform well has remained elusive; a gap this work addresses through the lens of optimal control theory.
Motivated by residual connection-based neural networks (ResNets) and their connection to neural ODEs [He et al., 2016b,a, Chen et al., 2018], research started using tools from optimal control to investigate these deep learning models, where trainable parameters act as control inputs that steer hidden states towards a target representation determined by the loss function [11 , 12 , 42 ] . A central technique is to use a stage cost over the full forward trajectory accumulating (loss-) penalties along the trajectory the data takes through the network. This can be understood as shaping the transient loss behavior, which enables stronger convergence guarantees and explicit depth bounds [11 , 14 ] . A commonality of these works is the turnpike phenomenon: hidden representations tend to cluster around the loss minimizer for the majority of layers, independent of network depth. However, while existing analyses focus on continuous space-time networks [11 ] , the application of this framework to standard ResNets architectures remains an open problem. In addition, our novel optimal control perspective on early-exiting enables new avenues towards formal analysis of training formulations.
In this work, we exploit the close relation between stage cost terms in discrete-time optimal control problems and the joint optimization formulation of early-exit neural networks. This allows us to show under which conditions this approach leads to the turnpike phenomenon. In turn this helps to uncover the fundamental mechanisms of joint training of early-exit neural networks. In short, our paper makes the following contributions:
A turnpike-based foundation of early-exit-based ResNet training and inference.
Novel asymptotic upper bounds on the cross-entropy loss during forward propagation revealing the loss turnpike phenomenon.
Theoretical bounds on guaranteeing correct classification and bounded early-exiting depths, derived for entropy and maximum softmax probability criteria.
Empirical support of the turnpike analysis and a principled approach to obtain the intermediate outputs in standard ResNets.
Preliminaries
We begin with a review of the concepts of early-exiting neural networks and optimal control theory.
Early-Exiting ResNets
Early-exiting, as proposed by Teerapittayanon et al. [ [48 ] , augments a neural network with intermediate classifiers that provide predictions before the final layer. The inference process is interrupted as soon as an intermediate prediction is deemed sufficiently confident, thereby reducing computational cost and preventing the model from overthinking [21 ] .
In this work, we consider standard ResNets [10 ] (He et al. 2016a) with N N N x ( i ) x^{(i)} x ( i ) y ^ ( i ) \hat{y}^{(i)} y ^ ( i )
x ( i ) = V ( x ( i ) , w V ) , x k + 1 ( i ) = S k ( x k ( i ) , w S , k ) + F k ( x k ( i ) , w F , k ) , y ^ ( i ) = O ( x N ( i ) , w O ) . (1) x^{(i)} = \mathcal{V}\left(x^{(i)},\mathbf{w}_{\mathcal{V}}\right), \quad x_{k+1}^{(i)} = S_k\left(x_k^{(i)},\mathbf{w}_{S,k}\right) + F_k\left(x_k^{(i)},\mathbf{w}_{F,k}\right), \quad\hat{y}^{(i)} = \mathcal{O}\left(x_N^{(i)},\mathbf{w}_{\mathcal{O}}\right). \tag*{(1)} x ( i ) = V ( x ( i ) , w V ) , x k + 1 ( i ) = S k ( x k ( i ) , w S , k ) + F k ( x k ( i ) , w F , k ) , y ^ ( i ) = O ( x N ( i ) , w O ) . (1) This architecture includes the input block V \mathcal{V} V w V \mathbf{w}_{\mathcal{V}} w V N N N S k S_k S k F k F_k F k w S , k \mathbf{w}_{S,k} w S , k w F , k \mathbf{w}_{F,k} w F , k w k = [ w S , k , w F , k ] \mathbf{w}_k = [\mathbf{w}_{S,k},\mathbf{w}_{F,k}] w k = [ w S , k , w F , k ] O \mathcal{O} O w O \mathbf{w}_{\mathcal{O}} w O w = [ w V , w 0 , … , w N − 1 , w O ] \mathbf{w} = [\mathbf{w}_{\mathcal{V}},\mathbf{w}_0,\ldots,\mathbf{w}_{N-1},\mathbf{w}_{\mathcal{O}}] w = [ w V , w 0 , … , w N − 1 , w O ] § 9 .
In the classical case, the output head produces the final prediction y ^ ( i ) \hat{y}^{(i)} y ^ ( i ) O k \mathcal{O}_k O k w O , k \mathbf{w}_{\mathcal{O},k} w O , k k k k k ∈ K O ⊆ N [ 0 , N − 1 ] k \in\mathcal{K}_{\mathcal{O}} \subseteq\mathbb{N}_{[0,N-1]} k ∈ K O ⊆ N [ 0 , N − 1 ] intermediate predictions : y ^ k ( i ) = O k ( x k ( i ) , w O , k ) \hat{y}^{(i)}_k = \mathcal{O}_k\left(x^{(i)}_k,\mathbf{w}_{\mathcal{O},k}\right) y ^ k ( i ) = O k ( x k ( i ) , w O , k ) H ( y ^ k ( i ) ) \mathcal{H}(\hat{y}^{(i)}_k) H ( y ^ k ( i ) ) p ^ max ( y ^ k ( i ) ) \hat{p}_{\max}(\hat{y}^{(i)}_k) p ^ m a x ( y ^ k ( i ) ) [20 , 36 , 29 ] .
To train the backbone network and the early-exits, different strategies have been proposed [25 , 41 ] (Rahmath P et al. 2024). In this work, we set out to study the joint training formulation through its intrinsic connection to optimal control theory, considering a supervised classification problem with labeled training data D = { ( x ( 1 ) , y ( 1 ) ) , … , ( x ( D ) , y ( D ) ) } \mathbb{D} = \{(x^{(1)},y^{(1)}),\ldots,(x^{(D)},y^{(D)})\} D = {( x ( 1 ) , y ( 1 ) ) , … , ( x ( D ) , y ( D ) )} x = [ x ( 1 ) , x ( 2 ) , … , x ( D ) ] \mathbf{x} = [x^{(1)},x^{(2)},\ldots,x^{(D)}] x = [ x ( 1 ) , x ( 2 ) , … , x ( D ) ] y ^ \hat{\mathbf{y}} y ^ L ( y ^ ) \mathcal{L}(\hat{\mathbf{y}}) L ( y ^ ) 2 joint training objective , a weighted sum of intermediate and final losses,
∑ k ∈ K O γ L ( y ^ k ) + L ( y ^ ) , \sum_{k\in\mathcal{K}_{\mathcal{O}}} \gamma\mathcal{L}(\hat{\mathbf{y}}_k) + \mathcal{L}(\hat{\mathbf{y}}), k ∈ K O ∑ γ L ( y ^ k ) + L ( y ^ ) , where the scalar hyperparameter γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] γ \gamma γ
The Turnpike Phenomenon in Optimal Control
Control theory aims to determine input signals or feedback policies for dynamic systems to induce a desired trajectory behavior. Optimal control, in particular, determines these control inputs by solving an optimization problem.
Consider the dynamic system x k + 1 = f ( x k , w k ) x_{k+1} = f(x_k,w_k) x k + 1 = f ( x k , w k ) x 0 = x 0 x_0 = x^0 x 0 = x 0 x k ∈ R n x_k \in\mathbb{R}^n x k ∈ R n k k k w k ∈ R m w_k \in\mathbb{R}^m w k ∈ R m w k w_k w k x k x_k x k N ∈ N N \in\mathbb{N} N ∈ N
min w 0 , … , w N − 1 ∑ k = 0 N − 1 ℓ ( x k , w k ) + J f ( x N ) s.t. x k + 1 = f ( x k , w k ) , x 0 = x 0 , ∀ k = 0 , … , N − 1. (2) \min_{w_0,\ldots,w_{N-1}} \sum_{k=0}^{N-1} \ell(x_k,w_k) + J_f(x_N) \quad\text{s.t. } x_{k+1}=f(x_k,w_k),\quad x_0=x^0,\quad\forall k=0,\ldots,N-1. \tag*{(2)} w 0 , … , w N − 1 min k = 0 ∑ N − 1 ℓ ( x k , w k ) + J f ( x N ) s.t. x k + 1 = f ( x k , w k ) , x 0 = x 0 , ∀ k = 0 , … , N − 1. (2) The objective entails the stage cost ℓ : R n × R m → R \ell:\mathbb{R}^n \times\mathbb{R}^m \to\mathbb{R} ℓ : R n × R m → R J f : R n → R J_f:\mathbb{R}^n \to\mathbb{R} J f : R n → R x N x_N x N f f f [4 ] . Figure 2 shows solutions of the simple OCP (2) with x k + 1 = 2 x k + w k x_{k+1}=2x_k+w_k x k + 1 = 2 x k + w k x 0 = 0 x^0=0 x 0 = 0 ℓ ( x k , w k ) = ( x k − 2 ) 2 + w k 2 \ell(x_k,w_k)=(x_k-2)^2+w_k^2 ℓ ( x k , w k ) = ( x k − 2 ) 2 + w k 2 J f ( x N ) = 0 J_f(x_N)=0 J f ( x N ) = 0 N = 5 , 10 , … , 40 N=5,10,\ldots,40 N = 5 , 10 , … , 40 x s ⋆ = 1 x_s^\star=1 x s ⋆ = 1 w s ⋆ = − 1 w_s^\star=-1 w s ⋆ = − 1 x s ⋆ = 1 x_s^\star=1 x s ⋆ = 1 w s ⋆ = − 1 w_s^\star=-1 w s ⋆ = − 1 (2) , i.e., the steady state pair that minimizes the stage cost ( x s ⋆ , w s ⋆ ) = argmin ( x s , w s ) ℓ ( x s , w s ) (x_s^\star,w_s^\star)=\operatorname*{argmin}_{(x_s,w_s)}\ell(x_s,w_s) ( x s ⋆ , w s ⋆ ) = argmin ( x s , w s ) ℓ ( x s , w s ) x s = f ( x s , w s ) x_s=f(x_s,w_s) x s = f ( x s , w s ) leaving arc .
Figure 2. Example of optimal trajectories of the OCP (2) for varying horizons N = 5 , 10 , … , 40 N=5,10,\ldots,40 N = 5 , 10 , … , 40 ( x s ⋆ , w s ⋆ ) = ( 1 , − 1 ) (x_s^\star,w_s^\star)=(1,-1) ( x s ⋆ , w s ⋆ ) = ( 1 , − 1 )
This characteristic clustering of optimal trajectories close to the optimal steady state is known as the turnpike property , early observations of which can be traced back to von Neumann [ [50 ] , predating the fundamental works of Bellman [ [2 ] and Boltyanskii et al. [ [5 ] . The term turnpike has been coined in the book by Dorfman et al. [ [9 ] and it has received widespread attention in control, cf. McKenzie [ [32 ] , Trélat and Zuazua [ [49 ] . Indeed, the turnpike property is a similarity property of the OCP solutions, i.e., the input and state trajectories remain close to the optimal steady state for most of the time independent of the initial conditions x 0 x_0 x 0 N N N
Definition 2.1 (Turnpike phenomenon). The OCP (2) is said to exhibit the turnpike phenomenon with respect to ( x s ⋆ , w s ⋆ ) = c o n s t (x_s^\star,w_s^\star)=const ( x s ⋆ , w s ⋆ ) = co n s t ε > 0 \varepsilon>0 ε > 0 κ < ∞ \kappa<\infty κ < ∞ ε \varepsilon ε ( x s ⋆ , w s ⋆ ) (x_s^\star,w_s^\star) ( x s ⋆ , w s ⋆ ) # { k = 0 , … , N ∣ ∥ ( x k , w k ) − ( x s ⋆ , w s ⋆ ) ∥ > ε } ≤ κ \#\{k=0,\ldots,N\mid\|(x_k,w_k)-(x_s^\star,w_s^\star)\|>\varepsilon\}\leq\kappa # { k = 0 , … , N ∣ ∥ ( x k , w k ) − ( x s ⋆ , w s ⋆ ) ∥ > ε } ≤ κ N N N x 0 x^0 x 0
Indeed, there exist different approaches on how turnpikes can be analyzed, we refer to Trélat and Zuazua [ [49 ] and Faulwasser and Grüne [ [13 ] for recent overviews.
Optimal Control Theory for Early-Exiting
We now formalize the joint training formulations for early-exiting ResNets from an optimal control perspective. We begin by considering ResNets as dynamic systems and view early exit training as optimal control problem in § 3.1 . Our main contributions are twofold: in § 3.2 , we introduce a novel turnpike notion, and in § 3.3 , we extend this analysis to early-exit criteria.
Training Early-Exit ResNets as Optimal Control
ResNets with constant state dimension can be regarded as a discrete-time dynamic system x k + 1 = f k ( x k , w k ) = x k + F k ( x k , w k ) x_{k+1}=f_k(x_k,w_k)=x_k+F_k(x_k,w_k) x k + 1 = f k ( x k , w k ) = x k + F k ( x k , w k ) x 0 = x x_0=x x 0 = x k = 0 , … , N − 1 k=0,\ldots,N-1 k = 0 , … , N − 1 number of residual blocks . The hidden state x k x_k x k state of the system while the trainable parameters w k w_k w k control inputs , see also Li et al. [2017] and Ruiz-Balet and Zuazua [ [42 ] . An important property of ResNets is that zero parameters reduce a residual block to an identity mapping via the skip connection x k + 1 = f k ( x k , 0 ) = x k + F k ( x k , 0 ) = x k x_{k+1}=f_k(x_k,0)=x_k+F_k(x_k,0)=x_k x k + 1 = f k ( x k , 0 ) = x k + F k ( x k , 0 ) = x k w k = 0 = const w_k=0=\operatorname{const} w k = 0 = const
Next, we phrase the early-exit joint training formulation for ResNets as an OCP. We begin with the joint training formulation for an early-exiting neural network based on ResNet He et al. [2016a]. Our insights are summarized in Figure 3. We use a constant weight 0 < γ ≤ 1 0<\gamma\le1 0 < γ ≤ 1
In contrast to classical OCPs, where the state dimension of the dynamical system is fixed, in standard ResNets the hidden-state dimension varies with depth He et al. [2016a]. In principle, these ResNets can still strictly be considered as a dynamic system with constant state dimension by embedding the entire network dynamic into a fixed state space corresponding to the maximum dimension in the network. Here, however, we allow the state dimension to vary and instead focus our analysis on the outputs, which have a fixed dimension and are used to obtain predictions and evaluate the loss function. In classification tasks, this dimension typically equals the number of classes over which softmax probabilities are computed.
It remains to cast the early-exit joint training problem (4) as an OCP in the form of (3), cf. Figure 3. To this end, we define the stage cost as the loss function for the intermediate outputs, i.e., ℓ k ( x k , w k ) = γ L ( O k ( x k , w O , k ) ) \ell_k(x_k,w_k)=\gamma\mathcal{L}(\mathcal{O}_k(x_k,w_{\mathcal{O},k})) ℓ k ( x k , w k ) = γ L ( O k ( x k , w O , k )) k ∈ K O k\in\mathcal{K}_{\mathcal{O}} k ∈ K O w k w_k w k ℓ k ( x k , w k ) = 0 \ell_k(x_k,w_k)=0 ℓ k ( x k , w k ) = 0 k ∉ K O k\notin\mathcal{K}_{\mathcal{O}} k ∈ / K O J f ( x N ) = L ( O ( x N , w O ) ) J_f(x_N)=\mathcal{L}(\mathcal{O}(x_N,w_{\mathcal{O}})) J f ( x N ) = L ( O ( x N , w O )) x 0 = V ( x , w V ) x_0=\mathcal{V}(x,w_{\mathcal{V}}) x 0 = V ( x , w V )
Turnpikes in Early-Exiting ResNets
With the optimal control formulation of the joint training for early exiting ResNets at hand, we analyze the implications of this perspective. Since the joint training (4) with the cross-entropy loss might not attain its minimum, we analyze δ \delta δ J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ J_N(\mathbf{w})\le\inf_{\mathbf{w}'}J_N(\mathbf{w}')+\delta J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ 0 ≤ δ < ∞ 0\le\delta<\infty 0 ≤ δ < ∞
Assumption 3.1 (Exponential loss decay). For the given training dataset D \mathbb{D} D ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) β > 0 \beta>0 β > 0 w ~ V \widetilde{\mathbf{w}}_{\mathcal{V}} w V w ~ k \widetilde{\mathbf{w}}_k w k k ∈ N [ 0 , ∞ ) k\in\mathbb{N}_{[0,\infty)} k ∈ N [ 0 , ∞ ) w ~ O , k \widetilde{\mathbf{w}}_{\mathcal{O},k} w O , k y ~ k \widetilde{\mathbf{y}}_k y k L ( y ~ k ) ≤ β ρ k \mathcal{L}(\widetilde{\mathbf{y}}_k)\le\beta\rho^k L ( y k ) ≤ β ρ k k ∈ N [ 0 , ∞ ) k\in\mathbb{N}_{[0,\infty)} k ∈ N [ 0 , ∞ )
Intuitively, this assumption reflects the idea that, with increasing depth the achievable loss improves. In addition, the constants β \beta β ρ \rho ρ ℓ 2 \ell_2 ℓ 2 [17 , 35 , 22 ] . However, for the cross-entropy loss this decay requires the logits to diverge which we show in Theorem E.5 for fully connected ResNets with ReLU activations by extending memorization results of Hardt and Ma [ [17 ] . Hence this assumption is not overly restrictive. Consequently, in the following loss turnpike results, in contrast to classical turnpike results in optimal control, the outputs do not become stationary; rather, they diverge to further reduce the cross-entropy loss. Under this assumption we obtain the following result.
Theorem 3.2 (Loss turnpike in ResNet training). Suppose that Assumption 3.1 holds. Let a ResNet (1) with depth N N N 0 < γ ≤ 1 0 < \gamma\le1 0 < γ ≤ 1 K O \mathcal{K}_O K O w \mathbf{w} w δ \delta δ 0 ≤ δ < ∞ 0 \le\delta< \infty 0 ≤ δ < ∞ J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ J_N(\mathbf{w}) \le\inf_{\mathbf{w}'} J_N(\mathbf{w}') + \delta J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ N N N K O \mathcal{K}_O K O
J N ( w ) ≤ J ˉ = γ β 1 − ρ + β + δ , J_N(\mathbf{w}) \le\bar{J} = \frac{\gamma\beta}{1-\rho} + \beta+ \delta, J N ( w ) ≤ J ˉ = 1 − ρ γ β + β + δ , *and the ResNet exhibits a loss turnpike on the training data. More precisely, for a loss level ε > 0 \varepsilon> 0 ε > 0 ε \varepsilon ε Q ^ ε ≔ { k ∈ K O ∪ { N } ∣ L ( y ^ k ) > ε } \widehat{Q}_{\varepsilon} \coloneqq\{k \in\mathcal{K}_O \cup\{N\} \mid\mathcal{L}(\widehat{\mathbf{y}}_k) > \varepsilon\} Q ε : = { k ∈ K O ∪ { N } ∣ L ( y k ) > ε } ε > 0 \varepsilon> 0 ε > 0 κ ( ε ) < ∞ \kappa(\varepsilon) < \infty κ ( ε ) < ∞ N N N K O \mathcal{K}_O K O Q ^ ε \widehat{Q}_{\varepsilon} Q ε # Q ^ ε ≤ κ ( ε ) = J ˉ γ ε \#\widehat{Q}_{\varepsilon} \le\kappa(\varepsilon) = \frac{\bar{J}}{\gamma\varepsilon} # Q ε ≤ κ ( ε ) = γ ε J ˉ
Proof sketch. By Assumption 3.1, there exists an infinite-depth network with early-exits at every residual block whose training losses are bounded by the convergent sequence β ρ k \beta\rho^k β ρ k K O ⊆ N [ 0 , N − 1 ] \mathcal{K}_O \subseteq\mathbb{N}_{[0,N-1]} K O ⊆ N [ 0 , N − 1 ] N N N K O \mathcal{K}_O K O K O ⊆ N [ 0 , ∞ ) \mathcal{K}_O \subseteq\mathbb{N}_{[0,\infty)} K O ⊆ N [ 0 , ∞ ) J ˉ \bar{J} J ˉ J N ( w ) ≤ J ˉ J_N(\mathbf{w}) \le\bar{J} J N ( w ) ≤ J ˉ k ∈ Q ^ ε k \in\widehat{Q}_{\varepsilon} k ∈ Q ε γ ε \gamma\varepsilon γ ε J ˉ = γ β 1 − ρ + β + δ \bar{J} = \frac{\gamma\beta}{1-\rho} + \beta+ \delta J ˉ = 1 − ρ γ β + β + δ # Q ^ ε ≤ κ ( ε ) = J ˉ γ ε \#\widehat{Q}_{\varepsilon} \le\kappa(\varepsilon) = \frac{\bar{J}}{\gamma\varepsilon} # Q ε ≤ κ ( ε ) = γ ε J ˉ § 12 .
This loss turnpike ensures that, for any prescribed loss level, only a limited forward propagation steps are needed in a jointly trained early-exit ResNet. Consequently, each sample is correctly classified after a finite depth implying that the turnpike not only occurs in the loss but also in the accuracy, which we formalize in Theorem E.7 . This result provides a theoretical explanation for the overthinking phenomenon in deep networks by showing that the depth at which a training sample enters the stable classification regime is bounded independently of the total network depth [21 ] .
Early-Exiting the Turnpike
We now investigate the implications for early-exiting inference, where inference is terminated once an uncertainty measure falls below a threshold [20 , 36 , 29 ] . At a block k ∈ K O k \in\mathcal{K}_O k ∈ K O ϕ ( y ^ k ( i ) ) ≤ T \phi(\widehat{\mathbf{y}}_k^{(i)}) \le T ϕ ( y k ( i ) ) ≤ T ϕ ( y ^ k ( i ) ) = H ( y ^ k ( i ) ) \phi(\widehat{\mathbf{y}}_k^{(i)}) = \mathcal{H}(\widehat{\mathbf{y}}_k^{(i)}) ϕ ( y k ( i ) ) = H ( y k ( i ) ) ϕ ( y ^ k ( i ) ) = 1 − p ^ max ( y ^ k ( i ) ) \phi(\widehat{\mathbf{y}}_k^{(i)}) = 1 - \widehat{p}_{\max}(\widehat{\mathbf{y}}_k^{(i)}) ϕ ( y k ( i ) ) = 1 − p m a x ( y k ( i ) ) ε > 0 \varepsilon> 0 ε > 0 ε \varepsilon ε Theorem E.10 ) and maximum softmax probability complement (Theorem E.12 ) on the training data. Consequently, using these quantities as exit criteria yields that for any exiting threshold T > 0 T > 0 T > 0 T > 0 T > 0 T > 0
Theorem 3.3 (Bounded and correct early-exiting with turnpikes). Let Assumption 3.1 hold and consider a ResNet of depth N N N K O \mathcal{K}_{\mathcal{O}} K O 0 < γ ≤ 1 0 < \gamma\le1 0 < γ ≤ 1 w \mathbf{w} w δ \delta δ 0 ≤ δ < ∞ 0 \le\delta< \infty 0 ≤ δ < ∞ J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ J_N(\mathbf{w}) \le\inf_{\mathbf{w}'} J_N(\mathbf{w}') + \delta J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ T > 0 T > 0 T > 0 κ \kappa κ i = 1 , … , D i = 1, \ldots, D i = 1 , … , D ( κ + 1 ) (\kappa+ 1) ( κ + 1 )
{ k ∈ K O ∪ { N } ∣ ϕ ( y ^ k ( i ) ) > T } ≤ κ , \left\{ k \in\mathcal{K}_{\mathcal{O}} \cup\{N\} \mid\phi\left(\hat{y}^{(i)}_k\right) > T \right\} \le\kappa, { k ∈ K O ∪ { N } ∣ ϕ ( y ^ k ( i ) ) > T } ≤ κ , independent of the depth N N N
k ( i ) = min ( { k ∈ K O ∣ ϕ ( y ^ k ( i ) ) ≤ T } ∪ { N } ) ≤ seq ( K O ∪ { N } ) κ + 1 . k^{(i)} = \min\left(\left\{ k \in\mathcal{K}_{\mathcal{O}} \mid\phi\left(\hat{y}^{(i)}_k\right) \le T \right\} \cup\{N\}\right) \le\operatorname{seq}\left(\mathcal{K}_{\mathcal{O}} \cup\{N\}\right)_{\kappa+1}. k ( i ) = min ( { k ∈ K O ∣ ϕ ( y ^ k ( i ) ) ≤ T } ∪ { N } ) ≤ seq ( K O ∪ { N } ) κ + 1 . Additionally, if a sample exits before the final output, i.e., ϕ ( y ^ k ( i ) ) ≤ T \phi\left(\hat{y}^{(i)}_k\right) \le T ϕ ( y ^ k ( i ) ) ≤ T k ∈ K O k \in\mathcal{K}_{\mathcal{O}} k ∈ K O c ^ ( y ^ k ( i ) ) = y ( i ) \hat{c}\left(\hat{y}^{(i)}_k\right) = y^{(i)} c ^ ( y ^ k ( i ) ) = y ( i )
We prove this result separately for each criterion in Theorem E.15 (entropy) and Theorem E.16 (max softmax probability complement), respectively. Note that if these early-exits are placed with fixed spacing M ≥ 1 M \ge1 M ≥ 1 K O = { 0 , M , 2 M , … , N − M } \mathcal{K}_{\mathcal{O}} = \{0, M, 2M, \ldots, N - M\} K O = { 0 , M , 2 M , … , N − M } i = 1 , … , D i = 1, \ldots, D i = 1 , … , D
k ( i ) = min ( { k ∈ K O ∣ ϕ ( y ^ k ( i ) ) ≤ T } ∪ { N } ) ≤ κ ⋅ M , k^{(i)} = \min\left(\left\{ k \in\mathcal{K}_{\mathcal{O}} \mid\phi\left(\hat{y}^{(i)}_k\right) \le T \right\} \cup\{N\}\right) \le\kappa\cdot M, k ( i ) = min ( { k ∈ K O ∣ ϕ ( y ^ k ( i ) ) ≤ T } ∪ { N } ) ≤ κ ⋅ M , independent of the depth N N N § 11 .
Experiments
To underscore our turnpike analysis for early-exit networks, we conduct experiments3 [26 ] supervising every hidden state and the partially supervised approach of Kaya et al. [ [21 ] . We detail the early-exit architectures used in § 4.1 . Then, in Section 4.2 we examine whether the turnpike similarity predicted by Theorem 3.2 and Theorem E.7 is observable in practice for ResNets of different depth trained via gradient-based optimization. In Section 4.3 we analyze how the turnpike behavior empirically relates to overthinking [21 ] and how it translates to the inference time and demonstrate that the turnpike similarity from Theorem 3.3 in the early-exit inference. Finally, Section 4.4 evaluates the influence of the stage cost loss weight and its influence of the turnpike bound from Theorem 3.2.
Early-Exit Architecture
Instead of having independent exit paths, we design the intermediate outputs O k \mathcal{O}_k O k x k ( i ) x_k^{(i)} x k ( i )
y ^ k ( i ) = O k ( x k ( i ) , w O , k ) = O ( S N − 1 ( ⋯ S k ( x k ( i ) , w S , k ) , … , w S , N − 1 ) , w O ) . \hat{y}^{(i)}_k = \mathcal{O}_k\left(x^{(i)}_k,\mathbf{w}_{\mathcal{O},k}\right) = \mathcal{O}\left(\mathcal{S}_{N-1}\left(\cdots\mathcal{S}_k\left(x^{(i)}_k,\mathbf{w}_{\mathcal{S},k}\right),\ldots,\mathbf{w}_{\mathcal{S},N-1}\right),\mathbf{w}_{\mathcal{O}}\right). y ^ k ( i ) = O k ( x k ( i ) , w O , k ) = O ( S N − 1 ( ⋯ S k ( x k ( i ) , w S , k ) , … , w S , N − 1 ) , w O ) . This architecture of exits ensures that if from some layer k < N k < N k < N k k k Theorem E.2 that the training loss of the final output exceeds the loss of any intermediate output by at most the suboptimality δ \delta δ
Since most skip connections are identity mappings and only at stage transitions a 1 × 1 1 \times1 1 × 1 § 8 .4.
Can we Observe the Turnpike?
To examine the turnpike phenomenon for varying depths, we conduct experiments on CIFAR-10, CIFAR-100, and TinyImagenet (Appendix § 8 .§ 2 ) [23 , 8 ] using ResNet-110 (N = 54 N=54 N = 54 N = 18 N=18 N = 18 N = 36 N=36 N = 36 M = 1 M = 1 M = 1 M = 6 M = 6 M = 6 [26 ] and Kaya et al. [ [21 ] . The experimental setup is further outlined in Appendix § 8 .§ 1 and we plan to release experimental code publicly for the camera-ready version.
In Figure 1 , we show the loss trajectories obtained at the respective early-exits of the trained networks and averaged over all samples. The training losses of all networks decrease very sharply with depth and converge to near-zero values, indicating that the networks enter the interpolation regime and thereby verifying the exponential loss decrease from Assumption 3.1. Moreover, the training loss improves with the backbone depth and over the depth of the early-exits for all networks. The qualitatively similar training-loss trajectories observed for ResNets of different depths and early-exit placements are consistent with the loss turnpike behavior predicted by Theorem 3.2. The monotonic decrease of the loss implies that the corresponding trajectories do not exhibit a leaving arc, which is expected for this choice of intermediate outputs and a near optimal training by Theorem E.2. In addition, due to the different stages, the rate at which the loss decays increase for the deeper stages, which possess more trainable parameters per residual block, leading to kinks in the plot. For a detailed discussion of the influence of the architecture, we refer to Appendix § 8 .§ 2 .
Figure 4 a shows the corresponding accuracy trajectories. Within numerical precision, all models reach almost 100 % accuracy at their terminal output, confirming a perfect fit to the CIFAR-10 training data. Across all backbone depths and early-exit placements, this is preceded by a steep initial rise in the first early-exits, with the accuracy turnpike reached within at most 30 residual blocks, consistent with the accuracy turnpike of Theorem E.7. Reaching this turnpike enables correct early-exit predictions; however, remaining on the turnpike without exiting constitutes wasteful overthinking.
Figure 4. Accuracies on CIFAR-10 for ResNets with residual blocks N ∈ { 18 , 36 , 54 } N \in\{18, 36, 54\} N ∈ { 18 , 36 , 54 } M = 1 M = 1 M = 1 M = 6 M = 6 M = 6
Turnpikes during Test-Time and Early Exiting?
To answer this questions, we take the test splits of CIFAR-10, CIFAR-100, and TinyImageNet (in Appendix § 8 .§ 2 ) as in-distribution samples. Since our theoretical guarantees only hold for the training data, we investigate empirically how they transfer to the test data. The test accuracies in Figure 4 a show a similar convergence behavior as the training accuracies, albeit with the well-reported generalization gap of the ResNets of about 7 % points on CIFAR-10 [He et al., 2016a]. In line with the empirical findings of Huang et al. [ [20 ] , providing the model with fewer (every M = 6 M = 6 M = 6
While the test accuracy trajectories behave similarly to their training counterparts, the test loss shows a different pattern: it initially decreases but then increases again, and none of the networks attain their minimum test loss at the final layer. As shown in Figure 5 , falsely classified test samples become increasingly overconfident in their incorrect predictions, incurring much larger loss than correctly classified samples, which saturate near zero. Hence, test samples exhibit similar turnpike behavior as their training counterparts, but for misclassified samples the turnpike drives predictions toward the wrong class with growing confidence. This overconfidence of misclassified samples may help explain why destructive overthinking occurs primarily at the first exits [21 ] .
Figure 5. Training and test loss trajectories across network depth, conditioned on the final prediction outcome on CIFAR-10 with ResNet N = 54 N = 54 N = 54 M = 1 M = 1 M = 1
Building on the turnpike analysis, we now investigate its implications for early-exit inference, using the max softmax probability complement as the uncertainty-based exiting criterion. Figure 4 b shows the early-exiting accuracy over the thresholds for varying ResNet depths and early-exit placements. As the threshold increases, and exiting is allowed at lower confidences, the accuracies decrease for all networks, strikingly, the accuracies are nearly identical across the network depths N N N Theorem 3.3 . In addition, the decrease is more pronounced for exits at every block M = 1 M = 1 M = 1 M = 6 M = 6 M = 6 M = 1 M = 1 M = 1 § 8 .§ 3 .
Effect of Stage-Cost Weight on the Turnpike Behavior?
The stage-cost loss weight γ > 0 \gamma> 0 γ > 0 γ \gamma γ ε > 0 \varepsilon> 0 ε > 0 # Q ^ ε ≤ \#\widehat{Q}_{\varepsilon} \le # Q ε ≤
1 ε γ [ γ β 1 − γ ρ + β + δ ] = 1 ε [ A γ + B ] , \frac{1}{\varepsilon\gamma}\left[\frac{\gamma\beta}{1-\gamma\rho}+\beta+\delta\right] = \frac{1}{\varepsilon}\left[\frac{A}{\gamma}+B\right], ε γ 1 [ 1 − γ ρ γ β + β + δ ] = ε 1 [ γ A + B ] , where A A A B B B β \beta β ρ \rho ρ δ \delta δ γ → 0 \gamma\to0 γ → 0
To investigate the effect of γ \gamma γ Figure 6 shows # Q ^ ε \#\widehat{Q}_{\varepsilon} # Q ε γ \gamma γ γ ≥ 0.2 \gamma\ge0.2 γ ≥ 0.2 γ → 0 \gamma\to0 γ → 0 B B B A / γ A/\gamma A / γ γ \gamma γ f ( γ ) = A / γ + B f(\gamma) = A/\gamma+ B f ( γ ) = A / γ + B ε \varepsilon ε R 2 ∈ [ 0.627 , 0.916 ] R^2 \in[0.627, 0.916] R 2 ∈ [ 0.627 , 0.916 ] 1 / γ 1/\gamma 1/ γ ε = 0.3 \varepsilon= 0.3 ε = 0.3 § 8 .5.
Figure 6. Cardinality of the turnpike set # Q ^ ε \#\widehat{Q}_{\varepsilon} # Q ε A / γ + B A/\gamma+B A / γ + B γ \gamma γ ε \varepsilon ε N = 54 N = 54 N = 54 M = 1 M = 1 M = 1
Early-Exit Neural Networks The field of early-exit neural networks has seen an evolution from initial deeply supervised nets [26 ] and sparse supervision [48 ] to more advanced architecture like MSDNet [20 ] connecting latent features across depth and scale, and SDN [21 ] leveraging intermediate classifiers to avoid overthinking, i.e., unnecessary and even destructive feature processing, and anticipate misclassifications early on. Han et al. [ [16 ] argues that poor performance of early classifiers affects the final output and hence introduces a knowledge distillation path of the final classifier to the intermediate ones. All of these works optimize the network and additional classifiers via a joint training regime and consider entropy based confidence thresholds as exit policy. Recently, Regol et al. [ [41 ] introduced jointly trained gating networks that decide when to exit based on a fixed early-exit backbone network. Bajpai and Hanawal [ [1 ] moved beyond static thresholds relying on multi-arm bandit policies to adapt to test time distributions. Kubaty et al. [ [24 ] showed that even calibrated models can lead to an insufficient compute-accuracy trade-off and suggested to focus instead on failure prediction metrics. These gating-based training regimes are not considered in this work as they can not be cast into our theoretical framework [44 , 25 ] .
Optimal Control for Deep Learning The intrinsic connections between time-continuous Neural ODEs and time-discrete ResNets lead to numerous advances both theoretically and practically. Benning et al. [ [3 ] studied numerical methods for deep learning models and constrains the time discretization to lie on a simplex to form sparse time steps. Understanding the forward pass as integration time horizon also lead to works aiming for minimal time neural ODEs [34 ] . Studying asymptotic behavior of neural networks in terms of depth is crucial to guide design choices even for finite time implementations. Typically, the goal is to drive a dynamic system to a desired set of states, which in asymptotics, will be spent most of the time. These turnpikes have been investigated by Esteve-Yagüe and Geshkovski [ [12 ] for ℓ 1 \ell_1 ℓ 1 [14 ] for ResNets. Püttschneider and Faulwasser [2026] use the label smoothing to ensure finite minimizers of the cross-entropy loss and show turnpike behavior with respect to these minimizers. Püttschneider et al. [ [37 ] study the implications of the steady-state property of ResNets in settings without reachability properties. For the cross-entropy loss and ℓ 1 \ell_1 ℓ 1 [12 ] show that the hidden states converge to a stationary point representing a trade-off between the minimization of the loss and the weight decay. However, previous work did not explore the close relations of early-exiting and the optimal control perspective on deep learning. In particular, our turnpike results for entropy and early-exiting criteria appear to be the first of their kind.
Conclusion
In this paper, we analyze the joint training of early-exit ResNets taking an optimal control perspective. To this end, we formulate their training as an optimal control problem and we link early exiting to the occurrences of the turnpike phenomenon. Under a mild asymptotic reachability assumption, we derive new turnpike notions for the cross-entropy loss, the accuracy, and the early-exiting criteria entropy and maximum softmax probability. These turnpike guarantees yield explicit bounds on the exit depth sufficient for correct classification of the training data, independent of the total network depth. This provides a theoretical explanation for the success of jointly trained early-exiting networks and justify their ability to avoid overthinking through depth-bounded, confidence-driven inference. We support these findings with experiments on CIFAR-10/100 and TinyImageNet, showing that the turnpike similarity manifests in both the hidden-state trajectories and the resulting early-exit inference behavior.
Future work should broaden the reachability assumptions to architectures beyond fully connected ResNets with ReLU activation. Moreover, the formal verification of these assumptions is of major interest. We remark that while our theoretical analysis extends to other residual-based architectures, such as vision transformers [10 ] , their reachability and turnpike behavior should be investigated experimentally. Furthermore, given the relevance of early-exiting in transformer-based large language models [46 ] , applying the proposed framework to such architectures is a promising direction.
Similarly, the analysis of turnpike properties for architectures without skip connections, such as VGG networks, is an interesting direction for future work, for a first step, we refer to Püttschneider et al. [ [39 ] . In addition, while our theoretical results are centered around training performance, future research will aim to close the gap to statistical learning theory and to provide generalization guarantees. An interesting avenue in this regard is the analysis via out-of-distribution methods like [33 ] .
Acknowledgments
This work has been partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) via the TRR 391 Spatio-temporal Statistics for the Transition of Energy and Transport (project 520388526) and the research unit Active Learning for Systems and Control (ALeSCo) (project 535860958).
Experimental Supplements
This appendix supplements the experiments of Section 4 with additional results and ablations. Section A.1 details the experimental setup. Section A.2 extends the turnpike observations to homogeneous ResNets and additional datasets (CIFAR-100, TinyImageNet). Section A.3 complements the inference-time analysis with entropy and SDN confusion score trajectories, showing how intermediate predictions progressively converge toward the final output across network depth, and extends the early-exiting results by examining exit depths for varying backbone depths, demonstrating that these also exhibit the characteristic turnpike similarity across network depths and supervision frequencies. Section A.4 examines parameter sharing in early-exits enabled by the proposed exit architecture. Finally, Section A.5 ablates the stage-cost weight γ \gamma γ
Setup
The experimental setup is based on He et al. [2016a]. The networks used in our experiments use a pre-activation ResNet with N = 54 N = 54 N = 54 3 × 3 3 \times3 3 × 3 N = 54 N = 54 N = 54 N = 36 N = 36 N = 36 N = 18 N = 18 N = 18 α = 0.1 \alpha= 0.1 α = 0.1 μ = 0.9 \mu= 0.9 μ = 0.9
In the joint training formulations, we use a constant weight of γ = 0.02 \gamma= 0.02 γ = 0.02 γ = 0.12 \gamma= 0.12 γ = 0.12 α / γ \alpha/\gamma α / γ
For homogeneous ResNets with constant state dimension, the number of convolutional filters is kept constant at 64 for CIFAR-10/CIFAR-100 across all residual blocks as well as the input embedding. Apart from this modification, their architecture is identical to the standard ResNet.
All results were obtained using PyTorch (version 2.4.1) on an NVIDIA RTX A6000 (48 GB) and NVIDIA A40 (48 GB).
Can We Observe the Turnpike for Further Architectures and Datasets? (cont. from Section 4.2)
In addition to the results on CIFAR-10 presented in the main paper, we also conduct experiments on CIFAR-100 [23 ] and TinyImageNet [8 ] and consider a homogeneous ResNet architecture with a fixed number of filters per residual block.
The kinks observed in the loss and accuracy curves of the standard ResNets in Figure 4 coincide with stage transitions, at which the feature dimension (number of channels) changes and spatial downsampling is applied. At these transitions, the number of trainable parameters per residual block increases by a factor of four, while the state dimension is reduced by a factor of two. Such abrupt changes in representational capacity likely underlie the observed non-smoothness in the training trajectories. To isolate the effect of these stage-wise architectural changes, we also consider homogeneous ResNets with a constant number of convolutional filters, 64, across all residual blocks. For CIFAR-10, the resulting loss and accuracy trajectories are shown in Figure 7 and for CIFAR-100 in Figure 9 . In contrast to the standard architecture, the homogeneous networks yield markedly smoother curves without visible kinks, supporting the interpretation that the artifacts arise from stage-wise architectural variation.
Figure 7. (a) Loss and (b) Accuracy trajectories for CIFAR-10 for the homogeneous ResNet architecture over the depth in terms of residual blocks obtained for ResNets with residual blocks N ∈ { 18 , 36 , 54 } N \in\{18, 36, 54\} N ∈ { 18 , 36 , 54 } M = 1 M = 1 M = 1 M = 6 M = 6 M = 6
Figure 9. (a) Loss and (b) Accuracy trajectories for CIFAR-100 for the homogeneous ResNet architecture over the depth in terms of residual blocks obtained for ResNets with residual blocks N ∈ { 18 , 36 , 54 } N \in\{18, 36, 54\} N ∈ { 18 , 36 , 54 } M = 1 M = 1 M = 1 M = 6 M = 6 M = 6
Due to their increased capacity, the homogeneous ResNets reach substantially lower training losses than their standard counterparts. Interestingly, the similarity between the depth-36 and depth-54 trajectories becomes even more pronounced in the homogeneous setting. However, despite having more parameters compared to the standard ResNets, the homogeneous models achieve lower test accuracy, indicating poorer generalization.
Figure 8 and Figure 9 present the loss and accuracy curves on CIFAR-100 for the standard and homogeneous ResNet architectures, respectively. The observed behavior closely resembles that of CIFAR-10 in both loss and accuracy. Owing to the larger number of classes and the increased task difficulty, CIFAR-100 yields higher training and test losses and lower accuracies than CIFAR-10, and the corresponding loss and accuracy curves converge more slowly. In particular, losses decrease and accuracies increase at a reduced rate compared to CIFAR-10. Nevertheless, consistent convergence patterns across network depth and early-exit configurations persist at this reduced performance level. These observations indicate that both CIFAR-10 and CIFAR-100 ResNets exhibit turnpike behavior consistent with our theoretical analysis.
Figure 8. (a) Loss and (b) Accuracy trajectories for CIFAR-100 for the standard ResNet architecture over the depth in terms of residual blocks obtained for ResNets with residual blocks N ∈ { 18 , 36 , 54 } N \in\{18, 36, 54\} N ∈ { 18 , 36 , 54 } M = 1 M = 1 M = 1 M = 6 M = 6 M = 6
Figure 10 presents the loss and accuracy trajectories for the TinyImageNet dataset [8 ] . Unlike in the CIFAR experiments, the increased task difficulty prevents any network from reaching perfect training accuracy within the available depth, with losses remaining above 10 − 1 10^{-1} 1 0 − 1 Assumption 3.1 throughout all layers, and even exceeds it toward the final layers. From the optimal control perspective, this implies that these depths does not suffice to fully reach the turnpike, suggesting that increasing network depth would lead to continued performance gains. Nevertheless, the characteristic signature of the turnpike phenomenon persists, the trajectories of the training metrics from networks of different depths and supervision densities follow a markedly similar path through the intermediate layer, before diverging near the final blocks. This divergence near the end reflects a more fundamental issue: due to the limited capacity of these networks, the joint training formulation in early-exiting imposes a much stronger trade-off between intermediate outputs and the final prediction than in the CIFAR setting, ultimately constraining the performance of the final classifier.
Figure 10. (a) Loss and (b) Accuracy trajectories for TinyImageNet for ResNet over the depth in terms of residual blocks obtained for ResNets with residual blocks N ∈ { 18 , 36 , 54 } N \in\{18, 36, 54\} N ∈ { 18 , 36 , 54 } M = 1 M = 1 M = 1 M = 6 M = 6 M = 6
Despite the larger gaps in training performance, the test accuracies are remarkably similar across networks of varying depth and supervision frequencies and exhibit a much stronger turnpike behavior than the corresponding training trajectories. In addition, due to the limited capacity of the network, the trade-off between intermediate output and final classifier of the joint training introduces a notable gap between the final test accuracies. The ResNets-110 with N = 54 N = 54 N = 54 M = 1 M = 1 M = 1 M = 6 M = 6 M = 6 [28 ] , Table 3.
Turnpikes during Test-Time and Early Exiting?
In this section, we further analyze the turnpike behavior on test data and during early-exit inference, considering the exit depth and entropy as the exit criterion.
We begin by examining the convergence of entropy for test samples. In Figure 11 a, and similar to Figure 5 , we plot the average entropy of samples conditioned on their final prediction outcome for the CIFAR-10 dataset split by training and test samples. The plot shows that the entropy consistently decreases for both the training and test samples, which implies that all samples that are finally classified correctly become increasingly confident in their final correct classification. Thus, these samples are amenable to early-exit by an entropy threshold, thereby reducing the computational demand for inference. The incorrectly classified samples exhibit on average a higher entropy values, implying that they do not reach the confidence threshold required for early-exiting. Thus, a well tuned early-exiting threshold can early-exit the correctly classified samples and avoid overthinking of samples that can be classified correctly before the final layer [21 ] .
Figure 11. (a) Entropy and (b) SDN confusion for training and test data across network depth, conditioned on the final prediction outcome on CIFAR-10 with ResNet N = 54 N = 54 N = 54 M = 1 M = 1 M = 1
To quantify this overthinking effect, Kaya et al. [ [21 ] introduced a confusion score measuring the difference in predicted softmax probabilities between intermediate exits and the final layer. Figure 11 b plots the corresponding trajectories, which shows the convergence of the intermediate predictions toward the final prediction, consistent with the turnpike phenomenon. This provides an explanation for why overthinking primarily manifests between the earlier intermediate outputs and the deeper layers, samples are already committed to their final prediction well before the terminal layer is reached.
We now analyze the turnpike behavior of the early-exit depths, complementing our previous analysis of early-exit accuracies. Figure 12 shows the exit depths and accuracies on CIFAR-10 using the max softmax probability complement as the exit criterion. Most notably, however, the exit depth for low thresholds start close to the full backbone depths, with increasing exit thresholds, they rapidly decrease and converge toward one another. Notably, the trade-off between accuracy and computational cost is clearly visible when comparing the supervision levels. Networks with exits placed every M = 6 M = 6 M = 6 M = 1 M = 1 M = 1 M = 6 M = 6 M = 6 M = 1 M = 1 M = 1
Figure 12. (a) Early-exit depths for varying thresholds. (b) Early-exit accuracies for varying thresholds. Early-exiting results with the max softmax probability complement as exiting criterion on CIFAR-10 for ResNets with residual blocks N ∈ { 18 , 36 , 54 } N \in\{18, 36, 54\} N ∈ { 18 , 36 , 54 } M = 1 M = 1 M = 1 M = 6 M = 6 M = 6
Early-exiting results for the entropy as exiting criterion are shown in Figure 13 , which show the same turnpike behavior as the max softmax probability criterion. From an optimal control perspective, both criteria robustly detect the turnpike at inference time. As the turnpike corresponds to the overthinking regime, this enables early exits upon reaching it, avoiding unnecessary computation.
Figure 13. (a) Early-exit depths for varying thresholds. (b) Early-exit accuracies for varying thresholds. Early-exiting results with the entropy as exiting criterion on CIFAR-10 for ResNets with residual blocks N ∈ { 18 , 36 , 54 } N \in\{18, 36, 54\} N ∈ { 18 , 36 , 54 } M = 1 M = 1 M = 1 M = 6 M = 6 M = 6
Shared Early-Exit Parameters
The early-exit architecture
y ^ k ( i ) = O k ( x k ( i ) , w O , k ) = O ( S N − 1 ( ⋯ S k ( x k ( i ) , w S , k ) , ⋯ , w S , N − 1 ) , w O ) \hat{y}_k^{(i)} = \mathcal{O}_k(x_k^{(i)}, \mathbf{w}_{O,k}) = \mathcal{O}(\mathcal{S}_{N-1}(\cdots\mathcal{S}_k(x_k^{(i)}, \mathbf{w}_{S,k}), \cdots, \mathbf{w}_{S,N-1}), \mathbf{w}_O) y ^ k ( i ) = O k ( x k ( i ) , w O , k ) = O ( S N − 1 ( ⋯ S k ( x k ( i ) , w S , k ) , ⋯ , w S , N − 1 ) , w O ) admits two design choices regarding parameterization. Since the layers used by the early-exits are already part of the backbone ResNet, the corresponding parameters can either be shared with the backbone or instantiated separately for each early-exit. We note that reusing parameters of later skip connections in the stage cost of earlier residual blocks formally breaks the causal structure of the OCP, though this does not affect the training objective and its analysis, which is the focus of this work. Sharing the early-exit parameters with the backbone network allows for earlier exiting without introducing additional trainable parameters. However this comes at the cost of reduced model capacity. Figure 14 shows the loss and accuracy trajectories on CIFAR-10 for the standard ResNet when parameters are shared between the backbone and the early-exits. While the training loss is comparable to that obtained with separate early-exit parameters as presented in the main Figure 4 a, the test accuracy is significantly lower. This degradation in performance is consistent with the reduced model capacity induced by parameter sharing and indicates inferior generalization compared to the separate-parameter configuration.
Effect of Stage-Cost Weight on the Turnpike Behavior?
We continue our ablation of the stage-cost weight from Section 4.4 using the same networks as before, ResNets with N = 54 N = 54 N = 54 M = 1 M = 1 M = 1 γ ∈ { 0.0002 , 0.002 , 0.012 , 0.02 , 0.12 , 0.2 , 0.4 , 0.6 , 0.8 , 1.0 } \gamma\in\{0.0002, 0.002, 0.012, 0.02, 0.12, 0.2, 0.4, 0.6, 0.8, 1.0\} γ ∈ { 0.0002 , 0.002 , 0.012 , 0.02 , 0.12 , 0.2 , 0.4 , 0.6 , 0.8 , 1.0 }
The resulting accuracies and loss curves in Figure 15 show the trade-off between the intermediate outputs and the final classifier. For weights γ ≥ 0.2 \gamma\geq0.2 γ ≥ 0.2 γ ≤ 0.002 \gamma\leq0.002 γ ≤ 0.002 γ = 0.02 \gamma= 0.02 γ = 0.02
Figure 15. (a) Loss and (b) Accuracy trajectories for CIFAR-10 for the ResNet over the depth in terms of residual blocks obtained for ResNets with N = 54 N = 54 N = 54 M = 1 M = 1 M = 1
Figure 14. (a) Loss and (b) Accuracy trajectories for CIFAR-10 for the standard ResNet architecture with shared early-exit parameters over the depth in terms of residual blocks obtained for ResNets with residual blocks N ∈ { 18 , 36 , 54 } N \in\{18, 36, 54\} N ∈ { 18 , 36 , 54 } M = 1 M = 1 M = 1
ResNet Basics
We briefly revisit the core components of the ResNet-v2 architecture [He et al., 2016a,b] which is considered here.
As illustrated in Figure 16 , in the forward pass a sample x ( i ) x^{(i)} x ( i ) V ( x ( i ) , w V ) \mathcal{V}(x^{(i)}, \mathbf{w}_{V}) V ( x ( i ) , w V ) N N N x N ( i ) x_{N}^{(i)} x N ( i ) O ( x N ( i ) , w O ) \mathcal{O}(x_{N}^{(i)}, \mathbf{w}_{O}) O ( x N ( i ) , w O ) w = [ w V , w 0 , . . . , w N − 1 , w O ] \mathbf{w} = [\mathbf{w}_{V}, \mathbf{w}_{0}, ..., \mathbf{w}_{N-1}, \mathbf{w}_{O}] w = [ w V , w 0 , ... , w N − 1 , w O ] w k = [ w F , k , w S , k ] \mathbf{w}_{k} = [\mathbf{w}_{F,k}, \mathbf{w}_{S,k}] w k = [ w F , k , w S , k ] k k k f k ( x k ( i ) , w k ) f_{k}(x_{k}^{(i)}, \mathbf{w}_{k}) f k ( x k ( i ) , w k ) F k ( x k ( i ) , w F , k ) \mathcal{F}_{k}(x_{k}^{(i)}, \mathbf{w}_{F,k}) F k ( x k ( i ) , w F , k ) S k ( x k ( i ) , w S , k ) S_k(x_k^{(i)}, w_{S,k}) S k ( x k ( i ) , w S , k ) w S , k w_{S,k} w S , k K S \mathcal{K}_S K S N N N
Figure 16. Illustration of a ResNet-v2 architecture while training with our proposed stage cost regularizer penalizing intermediate outputs. We propose to forward the hidden states through the network’s non-trivial skip connections to account for dimensionality projections.
x 0 ( i ) = V ( x ( i ) , w V ) , x_0^{(i)}=\mathcal{V}(x^{(i)},\mathbf{w}_{\mathcal{V}}), x 0 ( i ) = V ( x ( i ) , w V ) , x k + 1 ( i ) = f k ( x k ( i ) , w k ) = { x k ( i ) + F k ( x k ( i ) , w F , k ) , k ∉ K S S k ( x k ( i ) , w S , k ) + F k ( x k ( i ) , w F , k ) , k ∈ K S , ∀ k = 0 , … , N − 1 , x_{k+1}^{(i)}=f_k(x_k^{(i)},\mathbf{w}_k)=
\begin{cases}
x_k^{(i)}+F_k(x_k^{(i)},\mathbf{w}_{F,k}), & k\notin\mathcal{K}_S\\
S_k(x_k^{(i)},\mathbf{w}_{S,k})+F_k(x_k^{(i)},\mathbf{w}_{F,k}), & k\in\mathcal{K}_S,
\end{cases}
\quad\forall k=0,\ldots,N-1, x k + 1 ( i ) = f k ( x k ( i ) , w k ) = { x k ( i ) + F k ( x k ( i ) , w F , k ) , S k ( x k ( i ) , w S , k ) + F k ( x k ( i ) , w F , k ) , k ∈ / K S k ∈ K S , ∀ k = 0 , … , N − 1 , y ^ ( i ) = O ( x N ( i ) , w O ) . (3) \hat{y}^{(i)}=\mathcal{O}(x_N^{(i)},\mathbf{w}_{\mathcal{O}}). \tag*{(3)} y ^ ( i ) = O ( x N ( i ) , w O ) . (3) Joint Training of Early-Exit ResNets
In this work, we consider standard ResNet-v2 [He et al., 2016a] trained on classification datasets consisting of D D D x ( i ) x^{(i)} x ( i ) y ( i ) y^{(i)} y ( i )
D = { ( x ( 1 ) , y ( 1 ) ) , … , ( x ( D ) , y ( D ) ) } . \mathbb{D}=\left\{\left(x^{(1)},y^{(1)}\right),\ldots,\left(x^{(D)},y^{(D)}\right)\right\}. D = { ( x ( 1 ) , y ( 1 ) ) , … , ( x ( D ) , y ( D ) ) } . with C C C
For training the ResNet on the entire dataset, we denote the propagation of all samples by boldface variables, e.g., x = [ x ( 1 ) , x ( 2 ) , … , x ( D ) ] \mathbf{x}=[x^{(1)},x^{(2)},\ldots,x^{(D)}] x = [ x ( 1 ) , x ( 2 ) , … , x ( D ) ] x k + 1 = f k ( x k , w k ) = x k + F k ( x k , w F , k ) \mathbf{x}_{k+1}=f_k(\mathbf{x}_k,\mathbf{w}_k)=\mathbf{x}_k+F_k(\mathbf{x}_k,\mathbf{w}_{F,k}) x k + 1 = f k ( x k , w k ) = x k + F k ( x k , w F , k ) x k \mathbf{x}_k x k w k \mathbf{w}_k w k L \mathcal{L} L ℓ k ( x k , w k ) \ell_k(\mathbf{x}_k,\mathbf{w}_k) ℓ k ( x k , w k ) x k \mathbf{x}_k x k [11 , 14 , 34 ] . This leads to the training objective
J ( w ) = ∑ k = 0 N − 1 ℓ k ( x k , w k ) + L ( y ^ ) . J(\mathbf{w})=\sum_{k=0}^{N-1}\ell_k(\mathbf{x}_k,\mathbf{w}_k)+\mathcal{L}(\hat{\mathbf{y}}). J ( w ) = k = 0 ∑ N − 1 ℓ k ( x k , w k ) + L ( y ^ ) . This corresponds to the typical joint training formulations for the training of early-exits [48 , 31 ]
inf w J N ( w ) = ∑ k ∈ K O γ L ( y ^ k ) + L ( y ^ ) subject to ( 5 ) , ( A .4 ) , ∀ k = 0 , … , N − 1 , \inf_{\mathbf{w}} J_N(\mathbf{w})=\sum_{k\in\mathcal{K}_{\mathcal{O}}}\gamma\mathcal{L}(\hat{\mathbf{y}}_k)+\mathcal{L}(\hat{\mathbf{y}})\quad\text{subject to}\quad(5),\ (A.4),\ \forall k=0,\ldots,N-1, w inf J N ( w ) = k ∈ K O ∑ γ L ( y ^ k ) + L ( y ^ ) subject to ( 5 ) , ( A .4 ) , ∀ k = 0 , … , N − 1 , if the stage cost for residual blocks with an early-exits defined as the loss of the intermediate prediction weighted by γ > 0 \gamma>0 γ > 0 ℓ k ( x k , w k ) = γ L ( y ^ k ) \ell_k(\mathbf{x}_k,\mathbf{w}_k)=\gamma\mathcal{L}(\hat{\mathbf{y}}_k) ℓ k ( x k , w k ) = γ L ( y ^ k ) k ∈ K O k\in\mathcal{K}_{\mathcal{O}} k ∈ K O ℓ k ( x k , w k ) = 0 \ell_k(\mathbf{x}_k,\mathbf{w}_k)=0 ℓ k ( x k , w k ) = 0
For classification tasks, we first compute probabilities for each class using the softmax activation function from the output y ^ ( i ) \hat{\mathbf{y}}^{(i)} y ^ ( i ) p ^ ( y ^ ) ∈ ( 0 , 1 ) C \hat{p}(\hat{\mathbf{y}})\in(0,1)^C p ^ ( y ^ ) ∈ ( 0 , 1 ) C
[ p ^ ( y ^ ) ] c = e [ y ^ ] c ∑ i = 1 C e [ y ^ ] i , [\hat{p}(\hat{\mathbf{y}})]_c=\frac{\mathrm{e}^{[\hat{\mathbf{y}}]_c}}{\sum_{i=1}^{C}\mathrm{e}^{[\hat{\mathbf{y}}]_i}}, [ p ^ ( y ^ ) ] c = ∑ i = 1 C e [ y ^ ] i e [ y ^ ] c , where by [ x ] j [x]_j [ x ] j j j j x x x y y y y y y
L ( y ^ ) = − log ( [ p ^ ( y ^ ) ] y ) . \mathcal{L}(\hat{\mathbf{y}})=-\log\left([\hat{p}(\hat{\mathbf{y}})]_y\right). L ( y ^ ) = − log ( [ p ^ ( y ^ ) ] y ) . Here, we omit the ground-truth label as an additional argument of the loss function. For the full dataset, we compute the empirical loss by averaging the loss over the dataset
L ( y ^ ) = 1 D ∑ i = 1 D L ( y ^ ( i ) ) . \mathcal{L}(\hat{\mathbf{y}})=\frac{1}{D}\sum_{i=1}^{D}\mathcal{L}(\hat{\mathbf{y}}^{(i)}). L ( y ^ ) = D 1 i = 1 ∑ D L ( y ^ ( i ) ) . The entropy of the softmax probability distribution reads
H ( y ^ ) = − ∑ c = 1 C [ p ^ ( y ^ ) ] c log ( [ p ^ ( y ^ ) ] c ) . \mathcal{H}(\hat{y})=-\sum_{c=1}^{C}[\hat{p}(\hat{y})]_{c}\log\left([\hat{p}(\hat{y})]_{c}\right). H ( y ^ ) = − c = 1 ∑ C [ p ^ ( y ^ ) ] c log ( [ p ^ ( y ^ ) ] c ) . Similar to the cross-entropy loss, the entropy H \mathcal{H} H y ^ \hat{y} y ^
H ( y ^ ) = 1 D ∑ i = 1 D H ( y ^ ( i ) ) . \mathcal{H}(\hat{y})=\frac{1}{D}\sum_{i=1}^{D}\mathcal{H}(\hat{y}^{(i)}). H ( y ^ ) = D 1 i = 1 ∑ D H ( y ^ ( i ) ) . The class with the maximum softmax probability gives the class prediction
c ^ ( y ^ ) = argmax c [ p ^ ( y ^ ) ] c . \hat{c}(\hat{y})=\underset{c}{\operatorname{argmax}}\ [\hat{p}(\hat{y})]_{c}. c ^ ( y ^ ) = c argmax [ p ^ ( y ^ ) ] c . For binary classification, C = 2 C=2 C = 2 { y ^ : [ p ^ ( y ^ ) ] 1 = [ p ^ ( y ^ ) ] 2 } ⊂ R 2 \{\hat{y}:[\hat{p}(\hat{y})]_{1}=[\hat{p}(\hat{y})]_{2}\}\subset\mathbb{R}^{2} { y ^ : [ p ^ ( y ^ ) ] 1 = [ p ^ ( y ^ ) ] 2 } ⊂ R 2 R 2 \mathbb{R}^{2} R 2
A ( y ^ ) = # { i = 1 , … , D ∣ c ^ ( y ^ ( i ) ) = y ( i ) } D . \mathcal{A}(\hat{y})=\frac{\#\left\{i=1,\ldots,D\mid\hat{c}(\hat{y}^{(i)})=y^{(i)}\right\}}{D}. A ( y ^ ) = D # { i = 1 , … , D ∣ c ^ ( y ^ ( i ) ) = y ( i ) } . For the early-exit placement and the final output K O ∪ { N } = { k 1 , … , k m } \mathcal{K}_{\mathcal{O}}\cup\{N\}=\{k_{1},\ldots,k_{m}\} K O ∪ { N } = { k 1 , … , k m } k 1 < k 2 < ⋯ < k m = N k_{1}<k_{2}<\cdots<k_{m}=N k 1 < k 2 < ⋯ < k m = N seq ( K O ∪ { N } ) j = k min { j , m } \operatorname{seq}(\mathcal{K}_{\mathcal{O}}\cup\{N\})_{j}=k_{\min\{j,m\}} seq ( K O ∪ { N } ) j = k m i n { j , m } j j j N N N j > m j>m j > m
Intermediate Output Architecture
In early-exiting, intermediate outputs must remain shallow for efficiency. ResNets provide a natural mechanism for this: if the parameters of the residual branches for M ≤ k ≤ N − 1 M\leq k\leq N-1 M ≤ k ≤ N − 1 w F , k = 0 \mathbf{w}_{F,k}=0 w F , k = 0 F k ( x k ( i ) ) = 0 F_{k}(x^{(i)}_{k})=0 F k ( x k ( i ) ) = 0 x ( i ) x^{(i)} x ( i ) x M ( i ) x^{(i)}_{M} x M ( i )
y ^ ( i ) = O ( S N − 1 ( ⋯ S M ( x M ( i ) , w S , M ) , … , w S , N − 1 ) , w O ) . \hat{y}^{(i)}=\mathcal{O}(\mathcal{S}_{N-1}(\cdots\mathcal{S}_{M}(x^{(i)}_{M},\mathbf{w}_{S,M}),\ldots,\mathbf{w}_{S,N-1}),\mathbf{w}_{O}). y ^ ( i ) = O ( S N − 1 ( ⋯ S M ( x M ( i ) , w S , M ) , … , w S , N − 1 ) , w O ) . Moreover, since most residual blocks have identity skip connections, the remaining number of layers the state x M ( i ) x^{(i)}_{M} x M ( i ) x M ( i ) x^{(i)}_{M} x M ( i ) [31 ] (Rahmath P et al. 2024).
In addition, since the layers contained in this intermediate output architecture are already part of the backbone network, their parameters can either be shared with the backbone network or can be additional parameters for increased representational capacity. This way, we can re-interpret or fine-tune ResNets trained without our intermediate outputs, since all necessary parameters are at hand.
This leads to the definition of intermediate output heads O k \mathcal{O}_{k} O k y ^ k ( i ) \hat{y}^{(i)}_{k} y ^ k ( i ) x k ( i ) x^{(i)}_{k} x k ( i )
y ^ k ( i ) = O k ( x k ( i ) , w O , k ) = O ( S N − 1 ( ⋯ S k ( x k ( i ) , w S , k ) , … , w S , N − 1 ) , w O ) , ∀ k = 0 , … , N − 1. \hat{y}^{(i)}_{k}=\mathcal{O}_{k}(x^{(i)}_{k},\mathbf{w}_{O,k})=\mathcal{O}(\mathcal{S}_{N-1}(\cdots\mathcal{S}_{k}(x^{(i)}_{k},\mathbf{w}_{S,k}),\ldots,\mathbf{w}_{S,N-1}),\mathbf{w}_{O}),\qquad\forall k=0,\ldots,N-1. y ^ k ( i ) = O k ( x k ( i ) , w O , k ) = O ( S N − 1 ( ⋯ S k ( x k ( i ) , w S , k ) , … , w S , N − 1 ) , w O ) , ∀ k = 0 , … , N − 1. Figure 16 illustrates the proposed flow of data through the skip connections of the original residual blocks.
This choice of intermediate output architecture enables the following theoretical guarantee, which establishes a connection to steady states (or controlled equilibria) of dynamic systems.
Theorem C.1 (Identity mapping). Consider the ResNet (3) , with the intermediate outputs chosen according to (A.4). Let the intermediate outputs of residual block M M M produce the prediction y ^ M \hat{y}_M y ^ M and let the parameters of all following residual terms be zero, w F , k = 0 w_{F,k}=0 w F , k = 0 k = M , … , N − 1 k=M,\ldots,N-1 k = M , … , N − 1 Then all subsequent intermediate outputs and the final output are equal
y ^ = y ^ k = y ^ M , (4) \hat{y}=\hat{y}_k=\hat{y}_M, \tag*{(4)} y ^ = y ^ k = y ^ M , (4) for all k = M , … , N k=M,\ldots,N k = M , … , N
Proof. If w F , k = 0 w_{F,k}=0 w F , k = 0 k = M , … , N − 1 k=M,\ldots,N-1 k = M , … , N − 1 F k ( x k , 0 ) = 0 F_k(x_k,0)=0 F k ( x k , 0 ) = 0 x k + 1 = S k ( x k , w S , k ) x_{k+1}=S_k(x_k,w_{S,k}) x k + 1 = S k ( x k , w S , k ) k = M , … , N − 1 k=M,\ldots,N-1 k = M , … , N − 1 y ^ = O ( x N , w O ) \hat{y}=O(x_N,w_O) y ^ = O ( x N , w O ) (4) .
Asymptotic Early-Exiting
In early-exit architectures, determining the placement of intermediate classifiers is a critical hyperparameter choice. Common practice is to distribute these exits uniformly across the network depth.
Similar, when considering the asymptotic-depth regime in our later turnpike analysis, the question of how early-exit placement should scale with network depth arises naturally. One may fix the number of early-exits while letting the depth tend to infinity, which leads to asymptotically sparse exit positions. Alternatively, one may maintain a fixed spacing between exits, thereby preserving a dense placement; in this case, the number of early-exits increases asymptotically with the network depth.
Consider a sparse placement of M M M N N N M + 1 M+1 M + 1
∑ k = 1 M γ L ( y ^ k N M + 1 ) + L ( y ^ N ) , \sum_{k=1}^{M}\gamma\mathcal{L}\left(\hat{y}_{\frac{kN}{M+1}}\right)+\mathcal{L}\left(\hat{y}_N\right), k = 1 ∑ M γ L ( y ^ M + 1 k N ) + L ( y ^ N ) , where the spacing N M + 1 \frac{N}{M+1} M + 1 N M M M
∑ k = 1 N M − 1 γ L ( y ^ k M ) + L ( y ^ N ) . \sum_{k=1}^{\frac{N}{M}-1}\gamma\mathcal{L}\left(\hat{y}_{kM}\right)+\mathcal{L}\left(\hat{y}_N\right). k = 1 ∑ M N − 1 γ L ( y ^ k M ) + L ( y ^ N ) . In the first variant, the depth of the first early-exit is N M + 1 \frac{N}{M+1} M + 1 N M M M
Turnpike Analysis of Early-Exiting
In this section, we present our main theoretical results on the turnpike behavior of early-exiting ResNets and provide their proofs.
In deep ResNets the later layers primarily act as refinements of the features. This behavior is further emphasized when using a stage cost loss, i.e., a regularization for the hidden states dependent on the considered loss function. Below, we prove specifically that a ResNet trained with a stage cost loss exhibits the turnpike phenomenon with respect to the loss from optimal control, i.e., for any given loss threshold, only a bounded number of intermediate outputs exceed this threshold. We establish this loss turnpike behavior under the assumption of exponential loss decay, which we subsequently verify for a specific ResNet architecture in Section E.1. This implies that, for most of the depth of the network, the hidden states remain near an optimal representation resulting in near zero loss for their intermediate outputs. Moreover, the loss turnpike directly implies that a trained ResNet also exhibits an accuracy turnpike , i.e., the number of intermediate outputs with less than perfect accuracy is bounded from above. These implications are illustrated in Figure 17 .
Figure 17. Overview of the main theoretical contributions.
Finally, in Appendix § 12 .5, we show that combining accuracy turnpikes with the early-exit criterion guarantees the existence of an early-exit threshold that ensures both bounded early-exit depth and correct classification on the training data.
Assumption E.1 (Exponential loss decay). For the given training dataset D \mathbb{D} D ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) β > 0 \beta> 0 β > 0 w ~ V \widetilde{w}_{V} w V w ~ k \widetilde{w}_{k} w k k ∈ N [ 0 , ∞ ) k \in\mathbb{N}_{[0,\infty)} k ∈ N [ 0 , ∞ ) w ~ O , k \widetilde{w}_{O,k} w O , k y ~ k \widetilde{y}_{k} y k L ( y ~ k ) ≤ β ρ k \mathcal{L}(\widetilde{y}_{k}) \leq\beta\rho^{k} L ( y k ) ≤ β ρ k k ∈ N [ 0 , ∞ ) k \in\mathbb{N}_{[0,\infty)} k ∈ N [ 0 , ∞ )
In essence, this assumption requires that any finite positive loss can be achieved with some network of finite depth. Next, we will show that under this assumption, the ResNet trained with stage cost loss exhibits the turnpike phenomenon. In Appendix E.1, we show that this Assumption holds for a specific ResNet architecture with fully connected layers. Moreover, a similar result for neural ODEs can be found in [15 Proposition 7.4] .
Theorem 3.2 (Loss turnpike in ResNet training). Suppose that Assumption 3.1 holds. Let a ResNet (1) with depth N N N 0 < γ ≤ 1 0 < \gamma\leq1 0 < γ ≤ 1 K O \mathcal{K}_{O} K O w w w δ \delta δ 0 ≤ δ < ∞ 0 \leq\delta< \infty 0 ≤ δ < ∞ J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ J_{N}(w) \leq\inf_{w'} J_{N}(w') + \delta J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ N N N K O \mathcal{K}_{O} K O
J N ( w ) ≤ J ˉ = γ β 1 − ρ + β + δ , J_{N}(w) \leq\bar{J} = \frac{\gamma\beta}{1-\rho} + \beta+ \delta, J N ( w ) ≤ J ˉ = 1 − ρ γ β + β + δ , and the ResNet exhibits a loss turnpike on the training data. More precisely, for a loss level ε > 0 \varepsilon> 0 ε > 0 ε \varepsilon ε Q ^ ε = { k ∈ K O ∪ { N } ∣ L ( y ^ k ) > ε } \widehat{\mathcal{Q}}_{\varepsilon} = \{k \in\mathcal{K}_{O} \cup\{N\} \mid\mathcal{L}(\widehat{y}_{k}) > \varepsilon\} Q ε = { k ∈ K O ∪ { N } ∣ L ( y k ) > ε } ε > 0 \varepsilon> 0 ε > 0 κ ( ε ) < ∞ \kappa(\varepsilon) < \infty κ ( ε ) < ∞ N N N K O \mathcal{K}_{O} K O Q ^ ε \widehat{\mathcal{Q}}_{\varepsilon} Q ε # Q ^ ε ≤ κ ( ε ) = J ˉ γ ε \#\widehat{\mathcal{Q}}_{\varepsilon} \leq\kappa(\varepsilon) = \frac{\bar{J}}{\gamma\varepsilon} # Q ε ≤ κ ( ε ) = γ ε J ˉ
Proof. First, Assumption 3.1 gives that there exist ResNet parameters w ~ \widetilde{w} w β \beta β ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) y ~ k \widetilde{y}_{k} y k
L ( y ~ k ) ≤ β ρ k , \mathcal{L}(\widetilde{y}_{k}) \leq\beta\rho^{k}, L ( y k ) ≤ β ρ k , for early-exits attached to every residual block k ∈ K ~ O ∪ { N } = { 0 , … , N } k \in\widetilde{\mathcal{K}}_{O} \cup\{N\} = \{0,\ldots,N\} k ∈ K O ∪ { N } = { 0 , … , N } J N J_{N} J N
inf w ′ J N ( w ′ ) ≤ ∑ k ∈ K O γ L ( y ~ k ) + L ( y ~ ) ≤ ∑ k ∈ K O γ β ρ k + β ρ N ≤ ∑ k = 0 N − 1 γ β ρ k + β ρ N , (5) \inf_{w'} J_{N}(w') \leq\sum_{k \in\mathcal{K}_{O}} \gamma\mathcal{L}(\widetilde{y}_{k}) + \mathcal{L}(\widetilde{y}) \leq\sum_{k \in\mathcal{K}_{O}} \gamma\beta\rho^{k} + \beta\rho^{N} \leq\sum_{k=0}^{N-1} \gamma\beta\rho^{k} + \beta\rho^{N}, \tag*{(5)} w ′ inf J N ( w ′ ) ≤ k ∈ K O ∑ γ L ( y k ) + L ( y ) ≤ k ∈ K O ∑ γ β ρ k + β ρ N ≤ k = 0 ∑ N − 1 γ β ρ k + β ρ N , (5) where y ~ k \widetilde{y}_{k} y k y ~ \widetilde{y} y w ~ \widetilde{w} w ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) N ≥ 0 N \geq0 N ≥ 0 ρ N ≤ 1 \rho^{N} \leq1 ρ N ≤ 1
∑ k ∈ K O γ β ρ k + β ρ N ≤ ∑ k = 0 N − 1 γ β ρ k + β ρ N ≤ γ β 1 − ρ N 1 − ρ + β ρ N ≤ γ β 1 − ρ + β = : J ˉ i n f . \sum_{k \in\mathcal{K}_{O}} \gamma\beta\rho^{k} + \beta\rho^{N} \leq\sum_{k=0}^{N-1} \gamma\beta\rho^{k} + \beta\rho^{N} \leq\gamma\beta\frac{1-\rho^{N}}{1-\rho} + \beta\rho^{N} \leq\frac{\gamma\beta}{1-\rho} + \beta=: \bar{J}_{\mathrm{inf}}. k ∈ K O ∑ γ β ρ k + β ρ N ≤ k = 0 ∑ N − 1 γ β ρ k + β ρ N ≤ γ β 1 − ρ 1 − ρ N + β ρ N ≤ 1 − ρ γ β + β =: J ˉ inf . Hence, the infimum of the training objective satisfies inf w ′ J N ( w ′ ) ≤ J ˉ i n f \inf_{w'} J_{N}(w') \leq\bar{J}_{\mathrm{inf}} inf w ′ J N ( w ′ ) ≤ J ˉ inf N N N K O \mathcal{K}_{O} K O δ \delta δ w w w J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ ≤ J ˉ i n f + δ = : J ˉ J_{N}(w) \leq\inf_{w'} J_{N}(w') + \delta\leq\bar{J}_{\mathrm{inf}} + \delta=: \bar{J} J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ ≤ J ˉ inf + δ =: J ˉ 0 < γ ≤ 1 0 < \gamma\leq1 0 < γ ≤ 1 L ( y ~ ) ≥ γ L ( y ~ ) = γ L ( y ^ N ) \mathcal{L}(\widetilde{y}) \geq\gamma\mathcal{L}(\widetilde{y}) = \gamma\mathcal{L}(\widehat{y}_{N}) L ( y ) ≥ γ L ( y ) = γ L ( y N )
∑ k ∈ K O ∪ { N } γ L ( y ^ k ) ≤ ∑ k ∈ K O γ L ( y ^ k ) + L ( y ^ ) = J N ( w ) ≤ J ˉ . \sum_{k \in\mathcal{K}_{O} \cup\{N\}} \gamma\mathcal{L}(\widehat{y}_{k}) \leq\sum_{k \in\mathcal{K}_{O}} \gamma\mathcal{L}(\widehat{y}_{k}) + \mathcal{L}(\widehat{y}) = J_{N}(w) \leq\bar{J}. k ∈ K O ∪ { N } ∑ γ L ( y k ) ≤ k ∈ K O ∑ γ L ( y k ) + L ( y ) = J N ( w ) ≤ J ˉ . Moreover, with Q ^ ε = { k ∈ K O ∪ { N } ∣ L ( y ^ k ) > ε } \widehat{Q}_{\varepsilon} = \{k \in K_{\mathcal{O}} \cup\{N\} \mid\mathcal{L}(\widehat{y}_k) > \varepsilon\} Q ε = { k ∈ K O ∪ { N } ∣ L ( y k ) > ε } k ∈ Q ^ ε k \in\widehat{Q}_{\varepsilon} k ∈ Q ε L ( y ^ k ) > ε \mathcal{L}(\widehat{y}_k) > \varepsilon L ( y k ) > ε γ ε # Q ^ ε < ∑ k ∈ K O ∪ { N } γ L ( y ^ k ) \gamma\varepsilon\#\widehat{Q}_{\varepsilon} < \sum_{k \in K_{\mathcal{O}} \cup\{N\}} \gamma\mathcal{L}(\widehat{y}_k) γ ε # Q ε < ∑ k ∈ K O ∪ { N } γ L ( y k ) Q ^ ε \widehat{Q}_{\varepsilon} Q ε
γ ε # Q ^ ε < ∑ k ∈ K O ∪ { N } γ L ( y ^ k ) ≤ J ‾ , (6) \gamma\varepsilon\#\widehat{Q}_{\varepsilon} < \sum_{k \in K_{\mathcal{O}} \cup\{N\}} \gamma\mathcal{L}(\widehat{y}_k) \le\overline{J}, \tag*{(6)} γ ε # Q ε < k ∈ K O ∪ { N } ∑ γ L ( y k ) ≤ J , (6) and hence # Q ^ ε ≤ κ ( ε ) ≔ J ‾ γ ε = 1 γ ε [ γ β 1 − ρ + β + δ ] \#\widehat{Q}_{\varepsilon} \le\kappa(\varepsilon) \coloneqq\frac{\overline{J}}{\gamma\varepsilon} = \frac{1}{\gamma\varepsilon}\left[\frac{\gamma\beta}{1-\rho} + \beta+ \delta\right] # Q ε ≤ κ ( ε ) : = γ ε J = γ ε 1 [ 1 − ρ γ β + β + δ ]
Next, we consider the influence of our proposed architecture for the loss trajectories of the intermediate outputs (A.4).
Theorem E.2 (Decreasing loss behavior). Consider a ResNet of depth N N N γ > 0 \gamma> 0 γ > 0 w \mathbf{w} w δ \delta δ 0 ≤ δ < ∞ 0 \le\delta< \infty 0 ≤ δ < ∞ J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ J_N(\mathbf{w}) \le\inf_{\mathbf{w}'} J_N(\mathbf{w}') + \delta J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ
L ( y ^ ) ≤ L ( y ^ k ) + δ , \mathcal{L}(\widehat{\mathbf{y}}) \le\mathcal{L}(\widehat{\mathbf{y}}_k) + \delta, L ( y ) ≤ L ( y k ) + δ , compared to all intermediate outputs k ∈ K O k \in K_{\mathcal{O}} k ∈ K O
Proof. Consider a ResNet trained by joint training with the δ \delta δ w = [ w V , w 0 , … , w N − 1 , w O ] \mathbf{w} = [\mathbf{w}_{\mathcal{V}}, \mathbf{w}_0, \ldots, \mathbf{w}_{N-1}, \mathbf{w}_{\mathcal{O}}] w = [ w V , w 0 , … , w N − 1 , w O ] j = max arg min k ∈ K O L ( y ^ k ) j = \max\operatorname*{arg\,min}_{k \in K_{\mathcal{O}}} \mathcal{L}(\widehat{\mathbf{y}}_k) j = max arg min k ∈ K O L ( y k )
Next, we construct parameters w ~ \widetilde{\mathbf{w}} w δ \delta δ w \mathbf{w} w w ~ \widetilde{\mathbf{w}} w w \mathbf{w} w j j j w ~ F , k \widetilde{\mathbf{w}}_{F,k} w F , k k = j , … , N − 1 k = j, \ldots, N-1 k = j , … , N − 1 Theorem C.1 the zero parameters for the residual blocks leads to an identity mapping for the following intermediate outputs y ~ k = y ^ j \widetilde{\mathbf{y}}_k = \widehat{\mathbf{y}}_j y k = y j k ∈ { k ∈ K O ∣ k ≥ j } k \in\{k \in K_{\mathcal{O}} \mid k \ge j\} k ∈ { k ∈ K O ∣ k ≥ j } y ~ = y ^ j \widetilde{\mathbf{y}} = \widehat{\mathbf{y}}_j y = y j j j j y ~ k = y ^ k \widetilde{\mathbf{y}}_k = \widehat{\mathbf{y}}_k y k = y k k ∈ { k ∈ K O ∣ k < j } k \in\{k \in K_{\mathcal{O}} \mid k < j\} k ∈ { k ∈ K O ∣ k < j }
J N ( w ~ ) = ∑ k ∈ K O γ L ( y ~ k ) + L ( y ~ ) = ∑ k ∈ K O k ≤ j γ L ( y ^ k ) + ∑ k ∈ K O k > j γ L ( y ^ j ) + L ( y ^ j ) . J_N(\widetilde{\mathbf{w}}) = \sum_{k \in K_{\mathcal{O}}} \gamma\mathcal{L}(\widetilde{\mathbf{y}}_k) + \mathcal{L}(\widetilde{\mathbf{y}}) = \sum_{\substack{k \in K_{\mathcal{O}} \\ k \le j}} \gamma\mathcal{L}(\widehat{\mathbf{y}}_k) + \sum_{\substack{k \in K_{\mathcal{O}} \\ k > j}} \gamma\mathcal{L}(\widehat{\mathbf{y}}_j) + \mathcal{L}(\widehat{\mathbf{y}}_j). J N ( w ) = k ∈ K O ∑ γ L ( y k ) + L ( y ) = k ∈ K O k ≤ j ∑ γ L ( y k ) + k ∈ K O k > j ∑ γ L ( y j ) + L ( y j ) . The difference between the joint training objectives of the parameters w \mathbf{w} w w ~ \widetilde{\mathbf{w}} w
J N ( w ) − J N ( w ~ ) = L ( y ^ ) − L ( y ^ j ) + ∑ k ∈ K O k > j γ ( L ( y ^ k ) − L ( y ^ j ) ) . J_N(\mathbf{w}) - J_N(\widetilde{\mathbf{w}}) = \mathcal{L}(\widehat{\mathbf{y}}) - \mathcal{L}(\widehat{\mathbf{y}}_j) + \sum_{\substack{k \in K_{\mathcal{O}} \\ k > j}} \gamma\left(\mathcal{L}(\widehat{\mathbf{y}}_k) - \mathcal{L}(\widehat{\mathbf{y}}_j)\right). J N ( w ) − J N ( w ) = L ( y ) − L ( y j ) + k ∈ K O k > j ∑ γ ( L ( y k ) − L ( y j ) ) . Since inf w ′ J N ( w ′ ) ≤ J N ( w ~ ) \inf_{\mathbf{w}'} J_N(\mathbf{w}') \le J_N(\widetilde{\mathbf{w}}) inf w ′ J N ( w ′ ) ≤ J N ( w ) δ \delta δ w \mathbf{w} w J N ( w ) − J N ( w ~ ) ≤ inf w ′ J N ( w ′ ) + δ − J N ( w ~ ) ≤ δ J_N(\mathbf{w}) - J_N(\widetilde{\mathbf{w}}) \le\inf_{\mathbf{w}'} J_N(\mathbf{w}') + \delta- J_N(\widetilde{\mathbf{w}}) \le\delta J N ( w ) − J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ − J N ( w ) ≤ δ j j j L ( y ^ k ) − L ( y ^ j ) ≥ 0 \mathcal{L}(\widehat{\mathbf{y}}_k) - \mathcal{L}(\widehat{\mathbf{y}}_j) \ge0 L ( y k ) − L ( y j ) ≥ 0 k ∈ K O k \in K_{\mathcal{O}} k ∈ K O L ( y ^ ) − L ( y ^ j ) ≤ δ \mathcal{L}(\widehat{\mathbf{y}}) - \mathcal{L}(\widehat{\mathbf{y}}_j) \le\delta L ( y ) − L ( y j ) ≤ δ L ( y ^ j ) ≤ L ( y ^ k ) \mathcal{L}(\widehat{\mathbf{y}}_j) \le\mathcal{L}(\widehat{\mathbf{y}}_k) L ( y j ) ≤ L ( y k ) k ∈ K O k \in K_{\mathcal{O}} k ∈ K O L ( y ^ ) ≤ L ( y ^ k ) + δ \mathcal{L}(\widehat{\mathbf{y}}) \le\mathcal{L}(\widehat{\mathbf{y}}_k) + \delta L ( y ) ≤ L ( y k ) + δ
From the optimal control point of view, together with the turnpike results from Theorem 3.2, the immediate implication of the previous result is that the leaving arc of the ResNet is bounded by its suboptimality δ \delta δ Figure 2 , where the trajectories towards the end of the horizon depart from the optimal steady state. For more details on turnpike and leaving arcs, we refer to Faulwasser and Grüne [ [13 ] .
Exponential Loss Decay
We now consider a specific ResNet architecture for which the exponential decay of the training loss, as stated in Assumption 3.1, can be guaranteed. This ResNet architecture consists of fully connected layers with ReLU activations, σ ( x ) = max { 0 , x } \sigma(x) = \max\{0, x\} σ ( x ) = max { 0 , x } [17 ] to the intermediate outputs
x 0 ( i ) = V ( x ( i ) , w V ) = E x ( i ) , (7) x^{(i)}_0 = \mathcal{V}(x^{(i)}, \mathbf{w}_{\mathcal{V}}) = E x^{(i)}, \tag*{(7)} x 0 ( i ) = V ( x ( i ) , w V ) = E x ( i ) , (7) x k + 1 ( i ) = f k ( x k ( i ) , w k ) = x k ( i ) + W k σ ( A k x k ( i ) + b k ) , k = 0 , … , N − 1 , (8) x^{(i)}_{k+1} = f_k(x^{(i)}_k, \mathbf{w}_k) = x^{(i)}_k + W_k \sigma(A_k x^{(i)}_k + b_k), \qquad k = 0, \ldots, N-1, \tag*{(8)} x k + 1 ( i ) = f k ( x k ( i ) , w k ) = x k ( i ) + W k σ ( A k x k ( i ) + b k ) , k = 0 , … , N − 1 , (8) y ^ k ( i ) = O k ( x k ( i ) , w O , k ) = T k x k ( i ) , k = 0 , … , N . (9) \widehat{y}^{(i)}_k = \mathcal{O}_k(x^{(i)}_k, \mathbf{w}_{\mathcal{O},k}) = T_k x^{(i)}_k, \qquad k = 0, \ldots, N. \tag*{(9)} y k ( i ) = O k ( x k ( i ) , w O , k ) = T k x k ( i ) , k = 0 , … , N . (9) The ResNet starts with the input layer V \mathcal{V} V w V = [ E ] \mathbf{w}_{\mathcal{V}} = [E] w V = [ E ] x ( i ) ∈ R d i n x^{(i)} \in\mathbb{R}^{d_{\mathrm{in}}} x ( i ) ∈ R d in x 0 ( i ) ∈ R d x_0^{(i)} \in\mathbb{R}^{d} x 0 ( i ) ∈ R d E ∈ R d × d i n E \in\mathbb{R}^{d \times d_{\mathrm{in}}} E ∈ R d × d in d d d x k ( i ) ∈ R d x_k^{(i)} \in\mathbb{R}^{d} x k ( i ) ∈ R d k = 0 , … , N k = 0,\ldots,N k = 0 , … , N f k f_k f k A k A_k A k b k b_k b k W k W_k W k w k = [ A k , b k , W k ] \mathbf{w}_k = [A_k,b_k,W_k] w k = [ A k , b k , W k ] O k \mathcal{O}_k O k w O , k = [ T k ] \mathbf{w}_{\mathcal{O},k} = [T_k] w O , k = [ T k ] y ^ k ( i ) ∈ R C \hat{y}_k^{(i)} \in\mathbb{R}^{C} y ^ k ( i ) ∈ R C k = 0 , … , N k = 0,\ldots,N k = 0 , … , N T k ∈ R C × d T_k \in\mathbb{R}^{C \times d} T k ∈ R C × d y ^ = y ^ N \hat{y} = \hat{y}_N y ^ = y ^ N
The realizability results for this ResNet rely on the following assumption on the regularity of the training dataset.
Assumption E.3 (Regular dataset). Consider the training dataset D = { ( x ( 1 ) , y ( 1 ) ) , … , ( x ( D ) , y ( D ) ) } \mathbb{D} = \{(x^{(1)},y^{(1)}),\ldots,(x^{(D)},y^{(D)})\} D = {( x ( 1 ) , y ( 1 ) ) , … , ( x ( D ) , y ( D ) )} i , j = 1 , … , D i,j = 1,\ldots,D i , j = 1 , … , D i ≠ j i \ne j i = j ∥ x ( i ) − x ( j ) ∥ ≥ ρ \lVert x^{(i)} - x^{(j)} \rVert\ge\rho ∥ x ( i ) − x ( j ) ∥ ≥ ρ ρ > 0 \rho> 0 ρ > 0
Given this assumption, we now prove a slightly adapted version of the realizability results by Hardt and Ma [ [17 ] .
Theorem E.4 (Finite depth reachability for ResNets). Let the training data D \mathbb{D} D c = 1 , … , C c = 1,\ldots,C c = 1 , … , C y ˉ c ∈ R C \bar{y}_c \in\mathbb{R}^{C} y ˉ c ∈ R C d < ∞ d < \infty d < ∞ N < ∞ N < \infty N < ∞ w \mathbf{w} w i = 1 , … , D i = 1,\ldots,D i = 1 , … , D y ^ ( i ) \hat{y}^{(i)} y ^ ( i )
y ^ N ( i ) = y ˉ y ( i ) . \hat{y}_N^{(i)} = \bar{y}_{y^{(i)}}. y ^ N ( i ) = y ˉ y ( i ) . Furthermore, the first C C C x N ( i ) x_N^{(i)} x N ( i )
[ x N ( i ) ] j = { 1 if y ( i ) = j , 0 if y ( i ) ≠ j , j = 1 , … , C . [x_N^{(i)}]_j =
\begin{cases}
1 & \text{if } y^{(i)} = j,\\
0 & \text{if } y^{(i)} \ne j,
\end{cases}
\qquad j = 1,\ldots,C. [ x N ( i ) ] j = { 1 0 if y ( i ) = j , if y ( i ) = j , j = 1 , … , C . Proof. Consider the alternative ResNet with width d ~ \tilde{d} d ~ N ~ \tilde{N} N ~
x ~ 0 ( i ) = V ~ ( x ( i ) , w ~ V ) = E ~ x ( i ) , x ~ k + 1 ( i ) = f ~ k ( x ~ k ( i ) , w ~ k ) = x ~ k ( i ) + W ~ k σ ( A ~ k x ~ k ( i ) + b ~ k ) , k = 0 , … , N ~ − 1 , y ~ ( i ) = O ~ ( x ~ N ~ ( i ) , w ~ O ) = W ~ N ~ σ ( A ~ N ~ x ~ N ~ ( i ) + b ~ N ~ ) , (10) \begin{aligned}
\tilde{x}_0^{(i)} = \tilde{\mathcal{V}}(x^{(i)},\tilde{\mathbf{w}}_{\mathcal{V}}) &= \tilde{E}x^{(i)}, \\
\tilde{x}_{k+1}^{(i)} = \tilde{f}_k(\tilde{x}_k^{(i)},\tilde{\mathbf{w}}_k) &= \tilde{x}_k^{(i)} + \tilde{W}_k \sigma(\tilde{A}_k\tilde{x}_k^{(i)}+\tilde{b}_k), \qquad k = 0,\ldots,\tilde{N}-1, \\
\tilde{y}^{(i)} = \tilde{\mathcal{O}}(\tilde{x}_{\tilde{N}}^{(i)},\tilde{\mathbf{w}}_{\mathcal{O}}) &= \tilde{W}_{\tilde{N}}\sigma(\tilde{A}_{\tilde{N}}\tilde{x}_{\tilde{N}}^{(i)}+\tilde{b}_{\tilde{N}}), \tag*{(10)}
\end{aligned} x ~ 0 ( i ) = V ~ ( x ( i ) , w ~ V ) x ~ k + 1 ( i ) = f ~ k ( x ~ k ( i ) , w ~ k ) y ~ ( i ) = O ~ ( x ~ N ~ ( i ) , w ~ O ) = E ~ x ( i ) , = x ~ k ( i ) + W ~ k σ ( A ~ k x ~ k ( i ) + b ~ k ) , k = 0 , … , N ~ − 1 , = W ~ N ~ σ ( A ~ N ~ x ~ N ~ ( i ) + b ~ N ~ ) , (10) where the output block projects the hidden state dimension to the number of classes C C C A ~ N ~ ∈ R C × d ~ \tilde{A}_{\tilde{N}} \in\mathbb{R}^{C \times\tilde{d}} A ~ N ~ ∈ R C × d ~ b ~ N ~ ∈ R C \tilde{b}_{\tilde{N}} \in\mathbb{R}^{C} b ~ N ~ ∈ R C W ~ N ~ ∈ R C × C \tilde{W}_{\tilde{N}} \in\mathbb{R}^{C \times C} W ~ N ~ ∈ R C × C w ~ O = [ A ~ N ~ , b ~ N ~ , W ~ N ~ ] \tilde{\mathbf{w}}_{\mathcal{O}} = [\tilde{A}_{\tilde{N}},\tilde{b}_{\tilde{N}},\tilde{W}_{\tilde{N}}] w ~ O = [ A ~ N ~ , b ~ N ~ , W ~ N ~ ]
By the reachability results of Hardt and Ma [ [17 ] , 4 d ~ \tilde{d} d ~ N ~ \tilde{N} N ~ w ~ = [ w ~ V , w ~ 0 , … , w ~ N ~ − 1 , w ~ O ] \tilde{\mathbf{w}} = [\tilde{\mathbf{w}}_{\mathcal{V}},\tilde{\mathbf{w}}_0,\ldots,\tilde{\mathbf{w}}_{\tilde{N}-1},\tilde{\mathbf{w}}_{\mathcal{O}}] w ~ = [ w ~ V , w ~ 0 , … , w ~ N ~ − 1 , w ~ O ] i = 1 , … , D i = 1,\ldots,D i = 1 , … , D
[ y ~ ( i ) ] j = { 1 if y ( i ) = j , 0 if y ( i ) ≠ j . (11) [\tilde{y}^{(i)}]_j =
\begin{cases}
1 & \text{if } y^{(i)} = j,\\
0 & \text{if } y^{(i)} \ne j.
\end{cases} \tag*{(11)} [ y ~ ( i ) ] j = { 1 0 if y ( i ) = j , if y ( i ) = j . (11) To transfer these reachability results to the architecture (9), we embed the dynamics of the alternative ResNet (10) into (9). In particular, we introduce an additional residual block to account for the output residual block, leading to the total depth N = N ~ + 1 N = \tilde{N} + 1 N = N ~ + 1 d = 2 d ~ + C d = 2\tilde{d} + C d = 2 d ~ + C w ~ \tilde{\mathbf{w}} w ~ [17 ] , we construct parameters w \mathbf{w} w C C C [ x N ( i ) ] 1 : C = y ~ ( i ) [x_N^{(i)}]_{1:C} = \tilde{y}^{(i)} [ x N ( i ) ] 1 : C = y ~ ( i ) i = 1 , … , D i = 1,\ldots,D i = 1 , … , D w \mathbf{w} w
Input embedding
E = [ E ~ 0 d − d ~ × d i n ] . (12) E = \begin{bmatrix} \widetilde{E} \\ 0_{d-\widetilde{d}\times d_{\mathrm{in}}} \end{bmatrix}. \tag*{(12)} E = [ E 0 d − d × d in ] . (12) First residual blocks k = 0 , … , N − 2 k = 0,\ldots,N-2 k = 0 , … , N − 2
A k = [ A ~ k 0 d ~ × d − d ~ 0 d − d ~ × d ~ 0 d − d ~ × d − d ~ ] b k = [ b ~ k 0 d − d ~ ] W k = [ W ~ k 0 d ~ × d − d ~ 0 d − d ~ × d ~ 0 d − d ~ × d − d ~ ] . A_k = \begin{bmatrix} \widetilde{A}_k & 0_{\widetilde{d}\times d-\widetilde{d}} \\ 0_{d-\widetilde{d}\times\widetilde{d}} & 0_{d-\widetilde{d}\times d-\widetilde{d}} \end{bmatrix}
\qquad
b_k = \begin{bmatrix} \widetilde{b}_k \\ 0_{d-\widetilde{d}} \end{bmatrix}
\qquad
W_k = \begin{bmatrix} \widetilde{W}_k & 0_{\widetilde{d}\times d-\widetilde{d}} \\ 0_{d-\widetilde{d}\times\widetilde{d}} & 0_{d-\widetilde{d}\times d-\widetilde{d}} \end{bmatrix}. A k = [ A k 0 d − d × d 0 d × d − d 0 d − d × d − d ] b k = [ b k 0 d − d ] W k = [ W k 0 d − d × d 0 d × d − d 0 d − d × d − d ] . Last residual block k = N − 1 = N ~ k = N-1 = \widetilde{N} k = N − 1 = N
A N − 1 = [ A ~ N ~ 0 C × d − d ~ I d ~ × d ~ 0 d − d ~ × d − d ~ − I d ~ × d ~ 0 d − d ~ × d − d ~ ] b N − 1 = [ b ~ N ~ 0 d ~ 0 d ~ ] W N − 1 = [ W ~ N ~ − I C × d ~ I C × d ~ 0 d ~ × C 0 d ~ × d ~ 0 d ~ × d ~ 0 d ~ × C 0 d ~ × d ~ 0 d ~ × d ~ ] . A_{N-1} =
\begin{bmatrix}
\widetilde{A}_{\widetilde{N}} & 0_{C\times d-\widetilde{d}} \\
I_{\widetilde{d}\times\widetilde{d}} & 0_{d-\widetilde{d}\times d-\widetilde{d}} \\
-I_{\widetilde{d}\times\widetilde{d}} & 0_{d-\widetilde{d}\times d-\widetilde{d}}
\end{bmatrix}
\qquad
b_{N-1} =
\begin{bmatrix}
\widetilde{b}_{\widetilde{N}} \\
0_{\widetilde{d}} \\
0_{\widetilde{d}}
\end{bmatrix}
\qquad
W_{N-1} =
\begin{bmatrix}
\widetilde{W}_{\widetilde{N}} & -I_{C\times\widetilde{d}} & I_{C\times\widetilde{d}} \\
0_{\widetilde{d}\times C} & 0_{\widetilde{d}\times\widetilde{d}} & 0_{\widetilde{d}\times\widetilde{d}} \\
0_{\widetilde{d}\times C} & 0_{\widetilde{d}\times\widetilde{d}} & 0_{\widetilde{d}\times\widetilde{d}}
\end{bmatrix}. A N − 1 = A N I d × d − I d × d 0 C × d − d 0 d − d × d − d 0 d − d × d − d b N − 1 = b N 0 d 0 d W N − 1 = W N 0 d × C 0 d × C − I C × d 0 d × d 0 d × d I C × d 0 d × d 0 d × d . where we denote by I C × d ~ ∈ R C × d ~ I_{C\times\widetilde{d}} \in\mathbb{R}^{C\times\widetilde{d}} I C × d ∈ R C × d [ I C × d ~ ] i , j = 1 [I_{C\times\widetilde{d}}]_{i,j}=1 [ I C × d ] i , j = 1 i = j i=j i = j [ I C × d ~ ] i , j = 0 [I_{C\times\widetilde{d}}]_{i,j}=0 [ I C × d ] i , j = 0 i = 1 , … , C i=1,\ldots,C i = 1 , … , C j = 1 , … , d ~ j=1,\ldots,\widetilde{d} j = 1 , … , d x = σ ( x ) − σ ( − x ) x=\sigma(x)-\sigma(-x) x = σ ( x ) − σ ( − x ) x ∈ R x\in\mathbb{R} x ∈ R
Output projector matrix
T N = [ y ‾ 1 … y ‾ C 0 C × d − C ] . T_N = [\overline{y}_1 \quad\ldots\quad\overline{y}_C \quad0_{C\times d-C}]. T N = [ y 1 … y C 0 C × d − C ] . These parameters embed the dynamics of the alternative ResNet (10) into ResNet (9). The resulting hidden states are
x k ( i ) = [ x ~ k ( i ) 0 d − d ~ ] x_k^{(i)} = \begin{bmatrix} \widetilde{x}_k^{(i)} \\ 0_{d-\widetilde{d}} \end{bmatrix} x k ( i ) = [ x k ( i ) 0 d − d ] for every data sample i = 1 , … , D i=1,\ldots,D i = 1 , … , D k = 0 , … , N − 1 k=0,\ldots,N-1 k = 0 , … , N − 1
[ x N ( i ) ] 1 , … , C = y ~ ( i ) . [x_N^{(i)}]_{1,\ldots,C}=\widetilde{y}^{(i)}. [ x N ( i ) ] 1 , … , C = y ( i ) . Hence, by (11) , the first C C C
[ x N ( i ) ] j = { 1 if j = y ( i ) 0 if j ∈ { 1 , … , C } ∖ { y ( i ) } , j = 1 , … , C . [x_N^{(i)}]_j =
\begin{cases}
1 & \text{if } j=y^{(i)} \\
0 & \text{if } j\in\{1,\ldots,C\}\setminus\{y^{(i)}\},
\end{cases}
\qquad j=1,\ldots,C. [ x N ( i ) ] j = { 1 0 if j = y ( i ) if j ∈ { 1 , … , C } ∖ { y ( i ) } , j = 1 , … , C . Multiplication with the output projector matrix T N T_N T N y ‾ y ( i ) \overline{y}_{y^{(i)}} y y ( i )
y ^ N ( i ) = T N x N ( i ) = y ‾ y ( i ) . \widehat{y}_N^{(i)}=T_Nx_N^{(i)}=\overline{y}_{y^{(i)}}. y N ( i ) = T N x N ( i ) = y y ( i ) . This result shows that any label-dependent targets y ‾ y \overline{y}_y y y y ‾ y \overline{y}_y y y L 2 L_2 L 2 [14 ] . However, the most commonly used loss, the cross-entropy with one-hot labels, has no finite minimizer; rather, it approaches its infimum at zero only as the network outputs (logits) grow exponentially in absolute value, thereby asymptotically ensuring maximal separation between the classes. We now extend these finite depth reachability results as a starting point to design parameters that ensure exponentially diverging states such that the cross-entropy loss decays exponentially.
Theorem E.5 (Exponential decrease of cross-entropy). Consider the ResNet architecture (9), and let the training data D \mathbb{D} D L \mathcal{L} L d < ∞ d<\infty d < ∞ y ~ k \widetilde{y}_k y k Assumption 3.1 .
Proof. The cross-entropy loss has no finite minimizer but converges to zero as the network states diverge to infinity [Püttschneider and Faulwasser, 2026, Lemma 2]. To establish exponential loss decay, we construct an infinite-depth ResNets for which the states diverge exponentially. This construction leverages the finite-depth reachability results from Theorem E.4 . The finite-depth
ResNet are extended to an infinite-depth ResNet using a simple choice of parameters that induces the required exponential divergence of the states for cross-entropy loss decay. The construction of the infinite-depth ResNet is illustrated in Figure 18 .
Figure 18. Illustration construction of the infinite-depth ResNet that ensures exponential decay of the cross-entropy loss. First, Theorem E.4 guarantees that all hidden states can be moved to the illustrated configuration in finite depth, where the state of each data point corresponds to the unity vector of its label. Then, the infinite-depth ResNet causes the hidden states to diverge exponentially along the axes of their label thereby ensuring an exponential decay of the cross-entropy loss.
Throughout the remainder of this proof, we use the constant output projector matrix T ~ k \widetilde{T}_k T k k = P , … , ∞ k = P, \ldots, \infty k = P , … , ∞
T ~ k = [ I C × C 0 C × ( d − C ) ] . \widetilde{T}_k = \begin{bmatrix} I_{C \times C} & 0_{C \times(d-C)} \end{bmatrix}. T k = [ I C × C 0 C × ( d − C ) ] . With this choice, the network output corresponds to the first C C C
By Theorem E.4 , there exists a ResNet with finite width d < ∞ d < \infty d < ∞ P < ∞ P < \infty P < ∞ w ~ \widetilde{w} w P P P i = 1 , … , D i = 1, \ldots, D i = 1 , … , D j = 1 , … , C j = 1, \ldots, C j = 1 , … , C
[ x ~ P ( i ) ] j = { 1 if j = y ( i ) , 0 if j ≠ y ( i ) . [\widetilde{x}^{(i)}_P]_j =
\begin{cases}
1 & \text{if } j = y^{(i)},\\
0 & \text{if } j \ne y^{(i)}.
\end{cases} [ x P ( i ) ] j = { 1 0 if j = y ( i ) , if j = y ( i ) . That is, after P P P
On the finite horizon k = 0 , … , P k = 0, \ldots, P k = 0 , … , P y ~ k \widetilde{y}_k y k L ( y ~ k ) \mathcal{L}(\widetilde{y}_k) L ( y k ) β 1 ≥ 0 \beta_1 \ge0 β 1 ≥ 0 ρ 1 ∈ [ 0 , 1 ) \rho_1 \in[0, 1) ρ 1 ∈ [ 0 , 1 )
L ( y ~ k ) ≤ β 1 ρ 1 k . \mathcal{L}(\widetilde{y}_k) \le\beta_1 \rho_1^k. L ( y k ) ≤ β 1 ρ 1 k . With the states x ~ P ( i ) \widetilde{x}^{(i)}_P x P ( i ) P P P k = P , … , ∞ k = P, \ldots, \infty k = P , … , ∞ W ~ k = I \widetilde{W}_k = I W k = I A ~ k = 2 I \widetilde{A}_k = 2I A k = 2 I b ~ k = − 0.51 \widetilde{b}_k = -0.51 b k = − 0.51
x ~ k + 1 ( i ) = x ~ k ( i ) + σ ( 2 x ~ k ( i ) − 0.5 ) , \widetilde{x}^{(i)}_{k+1} = \widetilde{x}^{(i)}_k + \sigma(2\widetilde{x}^{(i)}_k - 0.5), x k + 1 ( i ) = x k ( i ) + σ ( 2 x k ( i ) − 0.5 ) , for k ≥ P k \ge P k ≥ P i = 1 , … , D i = 1, \ldots, D i = 1 , … , D
To show the exponential growth of the states, we consider the dynamics component-wise, which for the j j j
[ x ~ k + 1 ( i ) ] j = [ x ~ k ( i ) ] j + σ ( 2 [ x ~ k ( i ) ] j − 0.5 ) , [\widetilde{x}^{(i)}_{k+1}]_j = [\widetilde{x}^{(i)}_k]_j + \sigma(2[\widetilde{x}^{(i)}_k]_j - 0.5), [ x k + 1 ( i ) ] j = [ x k ( i ) ] j + σ ( 2 [ x k ( i ) ] j − 0.5 ) , for all residual blocks k ≥ P k \ge P k ≥ P i = 1 , … , D i = 1, \ldots, D i = 1 , … , D [ x ~ k + 1 ( i ) ] j ≥ 2 [ x ~ k ( i ) ] j [\widetilde{x}^{(i)}_{k+1}]_j \ge2[\widetilde{x}^{(i)}_k]_j [ x k + 1 ( i ) ] j ≥ 2 [ x k ( i ) ] j j = y ( i ) j = y^{(i)} j = y ( i ) [ x ~ k + 1 ( i ) ] j = 0 [\widetilde{x}^{(i)}_{k+1}]_j = 0 [ x k + 1 ( i ) ] j = 0 j ≠ y ( i ) j \ne y^{(i)} j = y ( i )
First, for the state dimension corresponding to the label, j = y ( i ) j = y^{(i)} j = y ( i ) [ x ~ k ( i ) ] j ≥ 1 [\tilde{x}^{(i)}_k]_j \ge1 [ x ~ k ( i ) ] j ≥ 1 2 [ x ~ k ( i ) ] j − 0.5 ≥ 0 2[\tilde{x}^{(i)}_k]_j - 0.5 \ge0 2 [ x ~ k ( i ) ] j − 0.5 ≥ 0 σ ( 2 [ x ~ k ( i ) ] j − 0.5 ) = 2 [ x ~ k ( i ) ] j − 0.5 \sigma(2[\tilde{x}^{(i)}_k]_j - 0.5) = 2[\tilde{x}^{(i)}_k]_j - 0.5 σ ( 2 [ x ~ k ( i ) ] j − 0.5 ) = 2 [ x ~ k ( i ) ] j − 0.5 2 [ x ~ k ( i ) ] j − 0.5 ≥ [ x ~ k ( i ) ] j 2[\tilde{x}^{(i)}_k]_j - 0.5 \ge[\tilde{x}^{(i)}_k]_j 2 [ x ~ k ( i ) ] j − 0.5 ≥ [ x ~ k ( i ) ] j
[ x ~ k + 1 ( i ) ] j = [ x ~ k ( i ) ] j + σ ( 2 [ x ~ k ( i ) ] j − 0.5 ) = [ x ~ k ( i ) ] j + 2 [ x ~ k ( i ) ] j − 0.5 ≥ [ x ~ k ( i ) ] j + [ x ~ k ( i ) ] j = 2 [ x ~ k ( i ) ] j . [\tilde{x}^{(i)}_{k+1}]_j = [\tilde{x}^{(i)}_k]_j + \sigma(2[\tilde{x}^{(i)}_k]_j - 0.5) = [\tilde{x}^{(i)}_k]_j + 2[\tilde{x}^{(i)}_k]_j - 0.5 \ge[\tilde{x}^{(i)}_k]_j + [\tilde{x}^{(i)}_k]_j = 2[\tilde{x}^{(i)}_k]_j. [ x ~ k + 1 ( i ) ] j = [ x ~ k ( i ) ] j + σ ( 2 [ x ~ k ( i ) ] j − 0.5 ) = [ x ~ k ( i ) ] j + 2 [ x ~ k ( i ) ] j − 0.5 ≥ [ x ~ k ( i ) ] j + [ x ~ k ( i ) ] j = 2 [ x ~ k ( i ) ] j . For the other state dimensions, j ≠ y ( i ) j \ne y^{(i)} j = y ( i ) [ x ~ k ( i ) ] j = 0 [\tilde{x}^{(i)}_k]_j = 0 [ x ~ k ( i ) ] j = 0 σ ( 2 [ x ~ k ( i ) ] j − 0.5 ) = 0 \sigma(2[\tilde{x}^{(i)}_k]_j - 0.5) = 0 σ ( 2 [ x ~ k ( i ) ] j − 0.5 ) = 0 j ≠ y ( i ) j \ne y^{(i)} j = y ( i )
[ x ~ k + 1 ( i ) ] j = [ x ~ k ( i ) ] j + σ ( 2 [ x ~ k ( i ) ] j − 0.5 ) = [ x ~ k ( i ) ] j + 0 = 0. [\tilde{x}^{(i)}_{k+1}]_j = [\tilde{x}^{(i)}_k]_j + \sigma(2[\tilde{x}^{(i)}_k]_j - 0.5) = [\tilde{x}^{(i)}_k]_j + 0 = 0. [ x ~ k + 1 ( i ) ] j = [ x ~ k ( i ) ] j + σ ( 2 [ x ~ k ( i ) ] j − 0.5 ) = [ x ~ k ( i ) ] j + 0 = 0. With the constant output projector T ~ k = [ I C × C 0 C × ( d − C ) ] \tilde{T}_k = [I_{C \times C}\quad0_{C \times(d-C)}] T ~ k = [ I C × C 0 C × ( d − C ) ] C C C
y ~ k + 1 ( i ) = [ x ~ k + 1 ( i ) ] 1 : C . \tilde{y}^{(i)}_{k+1} = [\tilde{x}^{(i)}_{k+1}]_{1:C}. y ~ k + 1 ( i ) = [ x ~ k + 1 ( i ) ] 1 : C . This implies that for k ≥ P k \ge P k ≥ P [ y ~ k + 1 ( i ) ] j ≥ 2 [ y ~ k ( i ) ] j [\tilde{y}^{(i)}_{k+1}]_j \ge2[\tilde{y}^{(i)}_k]_j [ y ~ k + 1 ( i ) ] j ≥ 2 [ y ~ k ( i ) ] j [ y ~ k ( i ) ] j ≥ 1 [\tilde{y}^{(i)}_k]_j \ge1 [ y ~ k ( i ) ] j ≥ 1 j = y ( i ) j = y^{(i)} j = y ( i ) [ y ~ k + 1 ( i ) ] j = 0 [\tilde{y}^{(i)}_{k+1}]_j = 0 [ y ~ k + 1 ( i ) ] j = 0 j ≠ y ( i ) j \ne y^{(i)} j = y ( i )
Now we consider the effect on the cross-entropy loss and show that this leads to exponentially decreasing loss, i.e., there exists ρ 2 ∈ [ 0 , 1 ) \rho_2 \in[0,1) ρ 2 ∈ [ 0 , 1 ) L ~ ( [ y ~ k + 1 ( i ) ] y ( i ) ) ≤ ρ 2 L ~ ( [ y ~ k ( i ) ] y ( i ) ) \tilde{\mathcal{L}}([\tilde{y}^{(i)}_{k+1}]_{y^{(i)}}) \le\rho_2\tilde{\mathcal{L}}([\tilde{y}^{(i)}_k]_{y^{(i)}}) L ~ ([ y ~ k + 1 ( i ) ] y ( i ) ) ≤ ρ 2 L ~ ([ y ~ k ( i ) ] y ( i ) ) k = P , … , ∞ k = P,\ldots,\infty k = P , … , ∞ i = 1 , … , D i = 1,\ldots,D i = 1 , … , D [ y ~ k ( i ) ] j = 0 [\tilde{y}^{(i)}_k]_j = 0 [ y ~ k ( i ) ] j = 0 j ≠ y ( i ) j \ne y^{(i)} j = y ( i ) L ~ \tilde{\mathcal{L}} L ~ [ y ~ k ( i ) ] y ( i ) [\tilde{y}^{(i)}_k]_{y^{(i)}} [ y ~ k ( i ) ] y ( i )
L ~ ( y ~ ( i ) ) = − log ( e [ y ~ k ( i ) ] y ( i ) ∑ j = 1 C e [ y ~ k ( i ) ] j ) = log ( ∑ j = 1 C e [ y ~ k ( i ) ] j − [ y ~ k ( i ) ] y ( i ) ) = log ( 1 + ∑ j = 1 j ≠ y ( i ) C e [ y ~ k ( i ) ] j − [ y ~ k ( i ) ] y ( i ) ) = log ( 1 + ∑ j = 1 j ≠ y ( i ) C e − [ y ~ k ( i ) ] y ( i ) ) = log ( 1 + ( C − 1 ) e − [ y ~ k ( i ) ] y ( i ) ) : = L ~ ( [ y ~ k ( i ) ] y ( i ) ) . \begin{aligned}
\tilde{\mathcal{L}}(\tilde{y}^{(i)}) = -\log\left(\frac{e^{[\tilde{y}^{(i)}_k]_{y^{(i)}}}}{\sum_{j=1}^{C}e^{[\tilde{y}^{(i)}_k]_j}}\right) = \log\left(\sum_{j=1}^{C}e^{[\tilde{y}^{(i)}_k]_j-[\tilde{y}^{(i)}_k]_{y^{(i)}}}\right) \\
&= \log\left(1 + \sum_{\substack{j=1 \\ j\ne y^{(i)}}}^{C} e^{[\tilde{y}^{(i)}_k]_j-[\tilde{y}^{(i)}_k]_{y^{(i)}}}\right) = \log\left(1 + \sum_{\substack{j=1 \\ j\ne y^{(i)}}}^{C} e^{-[\tilde{y}^{(i)}_k]_{y^{(i)}}}\right) \\
&= \log\left(1 + (C-1)e^{-[\tilde{y}^{(i)}_k]_{y^{(i)}}}\right) := \tilde{\mathcal{L}}([\tilde{y}^{(i)}_k]_{y^{(i)}}).
\end{aligned} L ~ ( y ~ ( i ) ) = − log ∑ j = 1 C e [ y ~ k ( i ) ] j e [ y ~ k ( i ) ] y ( i ) = log ( j = 1 ∑ C e [ y ~ k ( i ) ] j − [ y ~ k ( i ) ] y ( i ) ) = log 1 + j = 1 j = y ( i ) ∑ C e [ y ~ k ( i ) ] j − [ y ~ k ( i ) ] y ( i ) = log 1 + j = 1 j = y ( i ) ∑ C e − [ y ~ k ( i ) ] y ( i ) = log ( 1 + ( C − 1 ) e − [ y ~ k ( i ) ] y ( i ) ) := L ~ ([ y ~ k ( i ) ] y ( i ) ) . The loss L ~ ( [ y ~ k ( i ) ] y ( i ) ) \tilde{\mathcal{L}}([\tilde{y}^{(i)}_k]_{y^{(i)}}) L ~ ([ y ~ k ( i ) ] y ( i ) ) [ y ~ k ( i ) ] y ( i ) [\tilde{y}^{(i)}_k]_{y^{(i)}} [ y ~ k ( i ) ] y ( i ) [ y ~ k ( i ) ] y ( i ) [\tilde{y}^{(i)}_k]_{y^{(i)}} [ y ~ k ( i ) ] y ( i ) L ~ \tilde{\mathcal{L}} L ~ [ y ~ k + 1 ( i ) ] y ( i ) ≥ 2 [ y ~ k ( i ) ] y ( i ) [\tilde{y}^{(i)}_{k+1}]_{y^{(i)}} \ge2[\tilde{y}^{(i)}_k]_{y^{(i)}} [ y ~ k + 1 ( i ) ] y ( i ) ≥ 2 [ y ~ k ( i ) ] y ( i )
L ~ ( [ y ~ k + 1 ( i ) ] y ( i ) ) ≤ L ~ ( 2 [ y ~ k ( i ) ] y ( i ) ) . \tilde{\mathcal{L}}([\tilde{y}^{(i)}_{k+1}]_{y^{(i)}}) \le\tilde{\mathcal{L}}(2[\tilde{y}^{(i)}_k]_{y^{(i)}}). L ~ ([ y ~ k + 1 ( i ) ] y ( i ) ) ≤ L ~ ( 2 [ y ~ k ( i ) ] y ( i ) ) . Next we show that there exists ρ 2 ∈ [ 0 , 1 ) \rho_2 \in[0,1) ρ 2 ∈ [ 0 , 1 ) L ~ ( [ y ~ k + 1 ( i ) ] y ( i ) ) ≤ ρ 2 L ~ ( [ y ~ k ( i ) ] y ( i ) ) \tilde{\mathcal{L}}([\tilde{y}^{(i)}_{k+1}]_{y^{(i)}}) \le\rho_2\tilde{\mathcal{L}}([\tilde{y}^{(i)}_k]_{y^{(i)}}) L ~ ([ y ~ k + 1 ( i ) ] y ( i ) ) ≤ ρ 2 L ~ ([ y ~ k ( i ) ] y ( i ) ) k = P , … , ∞ k = P,\ldots,\infty k = P , … , ∞
L ~ ( [ y ~ k + 1 ( i ) ] y ( i ) ) L ~ ( [ y ~ k ( i ) ] y ( i ) ) ≤ L ~ ( 2 [ y ~ k ( i ) ] y ( i ) ) L ~ ( [ y ~ k ( i ) ] y ( i ) ) = log ( 1 + ( C − 1 ) e − 2 [ y ~ k ( i ) ] y ( i ) ) log ( 1 + ( C − 1 ) e − [ y ~ k ( i ) ] y ( i ) ) . \frac{\tilde{\mathcal{L}}([\tilde{y}^{(i)}_{k+1}]_{y^{(i)}})}{\tilde{\mathcal{L}}([\tilde{y}^{(i)}_k]_{y^{(i)}})} \le\frac{\tilde{\mathcal{L}}(2[\tilde{y}^{(i)}_k]_{y^{(i)}})}{\tilde{\mathcal{L}}([\tilde{y}^{(i)}_k]_{y^{(i)}})} = \frac{\log\left(1+(C-1)e^{-2[\tilde{y}^{(i)}_k]_{y^{(i)}}}\right)}{\log\left(1+(C-1)e^{-[\tilde{y}^{(i)}_k]_{y^{(i)}}}\right)}. L ~ ([ y ~ k ( i ) ] y ( i ) ) L ~ ([ y ~ k + 1 ( i ) ] y ( i ) ) ≤ L ~ ([ y ~ k ( i ) ] y ( i ) ) L ~ ( 2 [ y ~ k ( i ) ] y ( i ) ) = log ( 1 + ( C − 1 ) e − [ y ~ k ( i ) ] y ( i ) ) log ( 1 + ( C − 1 ) e − 2 [ y ~ k ( i ) ] y ( i ) ) . The numerator and denominator only differ by the additional factor 2 in the exponent of the numerator, which causes the numerator to decrease faster than the denominator, hence the ratio attains its maximum for the smallest possible [ y ~ k ( i ) ] y ( i ) [\tilde{y}^{(i)}_k]_{y^{(i)}} [ y ~ k ( i ) ] y ( i ) [ y ~ k ( i ) ] y ( i ) = 1 [\tilde{y}^{(i)}_k]_{y^{(i)}} = 1 [ y ~ k ( i ) ] y ( i ) = 1 k = P , … , ∞ k = P,\ldots,\infty k = P , … , ∞
L ~ ( [ y ~ k + 1 ( i ) ] y ( i ) ) L ~ ( [ y ~ k ( i ) ] y ( i ) ) ≤ log ( 1 + ( C − 1 ) e − 2 [ y ~ k ( i ) ] y ( i ) ) log ( 1 + ( C − 1 ) e − [ y ~ k ( i ) ] y ( i ) ) ≤ log ( 1 + ( C − 1 ) e − 2 ) log ( 1 + ( C − 1 ) e − 1 ) = ρ 2 < 1. \frac{\tilde{\mathcal{L}}([\tilde{y}^{(i)}_{k+1}]_{y^{(i)}})}{\tilde{\mathcal{L}}([\tilde{y}^{(i)}_k]_{y^{(i)}})} \le\frac{\log\left(1+(C-1)e^{-2[\tilde{y}^{(i)}_k]_{y^{(i)}}}\right)}{\log\left(1+(C-1)e^{-[\tilde{y}^{(i)}_k]_{y^{(i)}}}\right)} \le\frac{\log\left(1+(C-1)e^{-2}\right)}{\log\left(1+(C-1)e^{-1}\right)} = \rho_2 < 1. L ~ ([ y ~ k ( i ) ] y ( i ) ) L ~ ([ y ~ k + 1 ( i ) ] y ( i ) ) ≤ log ( 1 + ( C − 1 ) e − [ y ~ k ( i ) ] y ( i ) ) log ( 1 + ( C − 1 ) e − 2 [ y ~ k ( i ) ] y ( i ) ) ≤ log ( 1 + ( C − 1 ) e − 1 ) log ( 1 + ( C − 1 ) e − 2 ) = ρ 2 < 1. We obtain an exponential bound on the deeper residual blocks as β 2 = L ( y ^ P ( i ) ) ρ 2 P \beta_2=\mathcal{L}(\hat{y}^{(i)}_P)\rho_2^P β 2 = L ( y ^ P ( i ) ) ρ 2 P L ( y ^ k ( i ) ) ≤ β 2 ρ 2 k \mathcal{L}(\hat{y}^{(i)}_k)\leq\beta_2\rho_2^k L ( y ^ k ( i ) ) ≤ β 2 ρ 2 k k = P , … , ∞ k=P,\ldots,\infty k = P , … , ∞ i = 1 , … , D i=1,\ldots,D i = 1 , … , D
L ( y ~ k ) = 1 D ∑ i = 1 D L ( y ^ k ( i ) ) ≤ 1 D ∑ i = 1 D β 2 ρ 2 k = β 2 ρ 2 k . \mathcal{L}(\tilde{y}_k)=\frac{1}{D}\sum_{i=1}^{D}\mathcal{L}(\hat{y}^{(i)}_k)\leq\frac{1}{D}\sum_{i=1}^{D}\beta_2\rho_2^k=\beta_2\rho_2^k. L ( y ~ k ) = D 1 i = 1 ∑ D L ( y ^ k ( i ) ) ≤ D 1 i = 1 ∑ D β 2 ρ 2 k = β 2 ρ 2 k . For the entire depth, k = 0 , … , ∞ k=0,\ldots,\infty k = 0 , … , ∞ L ( y ~ k ) ≤ β 1 ρ 1 k \mathcal{L}(\tilde{y}_k)\leq\beta_1\rho_1^k L ( y ~ k ) ≤ β 1 ρ 1 k k = 0 , … , P k=0,\ldots,P k = 0 , … , P L ( y ~ k ) ≤ β 2 ρ 2 k \mathcal{L}(\tilde{y}_k)\leq\beta_2\rho_2^k L ( y ~ k ) ≤ β 2 ρ 2 k k = P , … , ∞ k=P,\ldots,\infty k = P , … , ∞ β = max { β 1 , β 2 } \beta=\max\{\beta_1,\beta_2\} β = max { β 1 , β 2 } ρ = max { ρ 1 , ρ 2 } < 1 \rho=\max\{\rho_1,\rho_2\}<1 ρ = max { ρ 1 , ρ 2 } < 1
L ( y ~ k ) ≤ β ρ k , \mathcal{L}(\tilde{y}_k)\leq\beta\rho^k, L ( y ~ k ) ≤ β ρ k , for the entire depth k = 0 , … , ∞ k=0,\ldots,\infty k = 0 , … , ∞ Assumption 3.1 is satisfied.
Accuracy Turnpike
After showing that turnpikes exist for the cross-entropy loss, we now show turnpikes also occur for other metrics, in this section, we start with the accuracy. We start by showing that an upper bound on the loss provides a lower bound on the accuracy.
Lemma E.6 (Loss bound implies accuracy bound). Let D \mathcal{D} D D D D y ^ \hat{y} y ^ B ∈ N [ 0 , D ] B\in\mathbb{N}_{[0,D]} B ∈ N [ 0 , D ]
L ( y ^ ) ≤ B + 1 2 D log ( 2 ) , \mathcal{L}(\hat{y})\leq\frac{B+1}{2D}\log(2), L ( y ^ ) ≤ 2 D B + 1 log ( 2 ) , then at most B B B A ( y ^ ) ≥ 1 − B D \mathcal{A}(\hat{y})\geq1-\frac{B}{D} A ( y ^ ) ≥ 1 − D B
Proof. First, we show that, for a single sample with prediction y ^ \hat{y} y ^ y y y
L ( y ^ ) < log ( 2 ) . \mathcal{L}(\hat{y})<\log(2). L ( y ^ ) < log ( 2 ) . ensures correct classification of this sample, i.e., argmax c [ p ^ ( y ^ ) ] c = y \operatorname*{argmax}_{c}[\hat{p}(\hat{y})]_c=y argmax c [ p ^ ( y ^ ) ] c = y L ( y ^ ) = − log ( [ p ^ ( y ^ ) ] y ) < log ( 2 ) \mathcal{L}(\hat{y})=-\log([\hat{p}(\hat{y})]_y)<\log(2) L ( y ^ ) = − log ([ p ^ ( y ^ ) ] y ) < log ( 2 ) [ p ^ ( y ^ ) ] y > 0.5 [\hat{p}(\hat{y})]_y>0.5 [ p ^ ( y ^ ) ] y > 0.5 [ p ^ ( y ^ ) ] c < 0.5 [\hat{p}(\hat{y})]_c<0.5 [ p ^ ( y ^ ) ] c < 0.5 c ∈ { 1 , … , C } ∖ { y } c\in\{1,\ldots,C\}\setminus\{y\} c ∈ { 1 , … , C } ∖ { y } [ p ^ ( y ^ ) ] y > [ p ^ ( y ^ ) ] c [\hat{p}(\hat{y})]_y>[\hat{p}(\hat{y})]_c [ p ^ ( y ^ ) ] y > [ p ^ ( y ^ ) ] c c ∈ { 1 , … , C } ∖ { y } c\in\{1,\ldots,C\}\setminus\{y\} c ∈ { 1 , … , C } ∖ { y }
For the empirical risk on the full dataset, this implies that each misclassified sample must incur a loss larger or equal to log ( 2 ) \log(2) log ( 2 )
L ( y ^ ) = 1 D ∑ i = 1 D L ( y ^ ( i ) ) < B + 1 D log ( 2 ) , \mathcal{L}(\hat{y})=\frac{1}{D}\sum_{i=1}^{D}\mathcal{L}(\hat{y}^{(i)})<\frac{B+1}{D}\log(2), L ( y ^ ) = D 1 i = 1 ∑ D L ( y ^ ( i ) ) < D B + 1 log ( 2 ) , then at most B B B B + 1 2 D < B + 1 D \frac{B+1}{2D}<\frac{B+1}{D} 2 D B + 1 < D B + 1 B ≥ 0 B\geq0 B ≥ 0 D ≥ 1 D\geq1 D ≥ 1 L ( y ^ ) ≤ B + 1 2 D log ( 2 ) \mathcal{L}(\hat{y})\leq\frac{B+1}{2D}\log(2) L ( y ^ ) ≤ 2 D B + 1 log ( 2 )
With this relation between the loss and the accuracy, we now show that the loss turnpike implies an accuracy turnpike.
Theorem E.7 (Accuracy turnpike). Suppose that Assumption 3.1 holds, and consider a ResNet of depth N N N with early-exits attached to set the set of residual blocks K O \mathcal{K}_{\mathcal{O}} K O trained with stage cost loss and weight 0 < γ ≤ 1 0<\gamma\leq1 0 < γ ≤ 1 by the optimal control training (4), and let its parameters w w w be δ \delta δ -suboptimal for some fixed 0 < δ < ∞ 0<\delta<\infty 0 < δ < ∞ i.e., J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ J_N(w)\leq\inf_{w'}J_N(w')+\delta J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ Then the following hold:
Then the ResNet exhibits an accuracy turnpike on the training data: for any number of misclassified samples B ∈ N [ 0 , D ] B\in\mathbb{N}_{[0,D]} B ∈ N [ 0 , D ] B B B K < ∞ K<\infty K < ∞ N N N K O ⊆ N [ 0 , N − 1 ] \mathcal{K}_{\mathcal{O}}\subseteq\mathbb{N}_{[0,N-1]} K O ⊆ N [ 0 , N − 1 ]
(ii) For the set of early-exits with accuracy A ( y ^ k ) < 1 − B D \mathcal{A}(\hat{y}_k) < 1 - \frac{B}{D} A ( y ^ k ) < 1 − D B this implies
# { k ∈ K O ∪ { N } ∣ A ( y ^ k ) < 1 − B D } ≤ κ , \#\left\{k \in\mathcal{K}_{\mathcal{O}} \cup\{N\} \mid\mathcal{A}(\hat{y}_k) < 1 - \frac{B}{D}\right\} \le\kappa, # { k ∈ K O ∪ { N } ∣ A ( y ^ k ) < 1 − D B } ≤ κ , where y ^ k \hat{y}_k y ^ k k = 0 , … , N k = 0, \ldots, N k = 0 , … , N
Proof. By Lemma E.6, L ( y ^ k ) ≤ B + 1 2 D log ( 2 ) \mathcal{L}(\hat{y}_k) \le\frac{B+1}{2D}\log(2) L ( y ^ k ) ≤ 2 D B + 1 log ( 2 ) A ( y ^ k ) ≥ 1 − B D \mathcal{A}(\hat{y}_k) \ge1 - \frac{B}{D} A ( y ^ k ) ≥ 1 − D B A ( y ^ k ) < 1 − B D \mathcal{A}(\hat{y}_k) < 1 - \frac{B}{D} A ( y ^ k ) < 1 − D B L ( y ^ k ) > B + 1 2 D log ( 2 ) \mathcal{L}(\hat{y}_k) > \frac{B+1}{2D}\log(2) L ( y ^ k ) > 2 D B + 1 log ( 2 ) 1 − B D 1 - \frac{B}{D} 1 − D B
# { k ∈ K O ∣ A ( y ^ k ) < 1 − B D } ≤ # { k ∈ K O ∣ L ( y ^ k ) > B + 1 2 D log ( 2 ) } . \#\left\{k \in\mathcal{K}_{\mathcal{O}} \mid\mathcal{A}(\hat{y}_k) < 1 - \frac{B}{D}\right\} \le\#\left\{k \in\mathcal{K}_{\mathcal{O}} \mid\mathcal{L}(\hat{y}_k) > \frac{B+1}{2D}\log(2)\right\}. # { k ∈ K O ∣ A ( y ^ k ) < 1 − D B } ≤ # { k ∈ K O ∣ L ( y ^ k ) > 2 D B + 1 log ( 2 ) } . Under Assumption 3.1, by Theorem 3.2 the jointly trained ResNet exhibits a loss turnpike and therefore, there exists κ < ∞ \kappa< \infty κ < ∞
# { k ∈ K O ∣ L ( y ^ k ) > B + 1 2 D log ( 2 ) } ≤ κ , \#\left\{k \in\mathcal{K}_{\mathcal{O}} \mid\mathcal{L}(\hat{y}_k) > \frac{B+1}{2D}\log(2)\right\} \le\kappa, # { k ∈ K O ∣ L ( y ^ k ) > 2 D B + 1 log ( 2 ) } ≤ κ , and therefore # { k ∈ K O ∣ A ( y ^ k ) < 1 − B D } ≤ κ \#\left\{k \in\mathcal{K}_{\mathcal{O}} \mid\mathcal{A}(\hat{y}_k) < 1 - \frac{B}{D}\right\} \le\kappa # { k ∈ K O ∣ A ( y ^ k ) < 1 − D B } ≤ κ
Entropy Turnpike
In this section, we show that the cross-entropy loss turnpike also induces a turnpike in the entropy, a commonly used criterion for early-exiting [31 ] . We begin by establishing a relationship between the cross-entropy loss and the entropy.
Theorem E.8 (Bound on cross-entropy implies bound on entropy). Let D D D D D D y ^ \hat{y} y ^
L ( y ^ ) ≤ L ˉ \mathcal{L}(\hat{y}) \le\bar{\mathcal{L}} L ( y ^ ) ≤ L ˉ for L ˉ > 0 \bar{\mathcal{L}} > 0 L ˉ > 0 H \mathcal{H} H
H ( y ^ ) ≤ H ˉ ( D L ˉ ) , \mathcal{H}(\hat{y}) \le\bar{\mathcal{H}}(D\bar{\mathcal{L}}), H ( y ^ ) ≤ H ˉ ( D L ˉ ) , where
H ˉ ( L ˉ ) = { log ( C ) , L ˉ ≥ log ( C ) , L ˉ e − L ˉ − ( 1 − e − L ˉ ) log ( 1 − e − L ˉ C − 1 ) , L ˉ < log ( C ) . (13) \bar{\mathcal{H}}(\bar{\mathcal{L}}) =
\begin{cases}
\log(C), & \bar{\mathcal{L}} \ge\log(C),\\
\bar{\mathcal{L}}e^{-\bar{\mathcal{L}}} - \left(1-e^{-\bar{\mathcal{L}}}\right)\log\left(\frac{1-e^{-\bar{\mathcal{L}}}}{C-1}\right), & \bar{\mathcal{L}} < \log(C).
\end{cases} \tag*{(13)} H ˉ ( L ˉ ) = { log ( C ) , L ˉ e − L ˉ − ( 1 − e − L ˉ ) log ( C − 1 1 − e − L ˉ ) , L ˉ ≥ log ( C ) , L ˉ < log ( C ) . (13) Moreover, the entropy for every sample i = 1 , … , D i = 1, \ldots, D i = 1 , … , D
H ( y ^ ( i ) ) ≤ H ˉ ( D L ˉ ) . \mathcal{H}(\hat{y}^{(i)}) \le\bar{\mathcal{H}}(D\bar{\mathcal{L}}). H ( y ^ ( i ) ) ≤ H ˉ ( D L ˉ ) . Proof. First, we consider a single sample with label y y y p ∈ [ 0 , 1 ] C p \in[0,1]^C p ∈ [ 0 , 1 ] C
L p ( p ) = − log ( [ p ] y ) ≤ L ˉ \mathcal{L}_p(p) = -\log([p]_y) \le\bar{\mathcal{L}} L p ( p ) = − log ([ p ] y ) ≤ L ˉ with L ˉ ≥ 0 \bar{\mathcal{L}} \ge0 L ˉ ≥ 0 H ˉ ( L ˉ ) \bar{\mathcal{H}}(\bar{\mathcal{L}}) H ˉ ( L ˉ )
H p ( p ) = − ∑ c = 1 C [ p ] c log ( [ p ] c ) ≤ H ˉ ( L ˉ ) . \mathcal{H}_p(p) = -\sum_{c=1}^{C}[p]_c\log([p]_c) \le\bar{\mathcal{H}}(\bar{\mathcal{L}}). H p ( p ) = − c = 1 ∑ C [ p ] c log ([ p ] c ) ≤ H ˉ ( L ˉ ) . First, we rewrite the upper bound on the cross-entropy L p ( p ) = − log ( [ p ] y ) ≤ L ˉ \mathcal{L}_p(p) = -\log([p]_y) \le\bar{\mathcal{L}} L p ( p ) = − log ([ p ] y ) ≤ L ˉ y y y [ p ] y ≥ e − L ˉ [p]_y \ge e^{-\bar{\mathcal{L}}} [ p ] y ≥ e − L ˉ [ p ] y ≥ e − L ˉ [p]_y \ge e^{-\bar{\mathcal{L}}} [ p ] y ≥ e − L ˉ
H ˉ ( L ˉ ) = max p ∈ R C H p ( p ) = − ∑ c = 1 C [ p ] c log ( [ p ] c ) (14) \bar{\mathcal{H}}(\bar{\mathcal{L}}) = \max_{p \in\mathbb{R}^{C}} \mathcal{H}_p(p) = -\sum_{c=1}^{C}[p]_c\log([p]_c) \tag*{(14)} H ˉ ( L ˉ ) = p ∈ R C max H p ( p ) = − c = 1 ∑ C [ p ] c log ([ p ] c ) (14) subject to ∑ c = 1 C [ p ] c = 1 , (15) \text{subject to}\quad\sum_{c=1}^{C}[p]_c = 1, \tag*{(15)} subject to c = 1 ∑ C [ p ] c = 1 , (15) [ p ] c ≥ 0 , c = 1 , … , C , (16) [p]_c \ge0,\qquad c = 1,\ldots,C, \tag*{(16)} [ p ] c ≥ 0 , c = 1 , … , C , (16) [ p ] y ≥ e − L ˉ . (17) [p]_y \ge e^{-\bar{\mathcal{L}}}. \tag*{(17)} [ p ] y ≥ e − L ˉ . (17) The feasible set of this optimization problem is
P = { p ∈ [ 0 , 1 ] C | [ p ] y ≥ e − L ˉ , ∑ c = 1 C [ p ] c = 1 } . \mathcal{P}=\left\{p\in[0,1]^C\ \middle|\ [p]_y\ge e^{-\bar{\mathcal{L}}},\ \sum_{c=1}^{C}[p]_c=1\right\}. P = { p ∈ [ 0 , 1 ] C [ p ] y ≥ e − L ˉ , c = 1 ∑ C [ p ] c = 1 } . We define a candidate probability vector p ∈ P p\in\mathcal{P} p ∈ P
[ p ] i = { 1 C if L ˉ ≥ log ( C ) , e − L ˉ if L ˉ < log ( C ) and i = y , 1 − e − L ˉ C − 1 if L ˉ < log ( C ) and i ≠ y . [p]_i=
\begin{cases}
\frac{1}{C} & \text{if }\bar{\mathcal{L}}\ge\log(C),\\
e^{-\bar{\mathcal{L}}} & \text{if }\bar{\mathcal{L}}<\log(C)\text{ and }i=y,\\
\frac{1-e^{-\bar{\mathcal{L}}}}{C-1} & \text{if }\bar{\mathcal{L}}<\log(C)\text{ and }i\ne y.
\end{cases} [ p ] i = ⎩ ⎨ ⎧ C 1 e − L ˉ C − 1 1 − e − L ˉ if L ˉ ≥ log ( C ) , if L ˉ < log ( C ) and i = y , if L ˉ < log ( C ) and i = y . The probability distribution vector p p p q ∈ P q\in\mathcal{P} q ∈ P [ q ] ↓ [q]_{\downarrow} [ q ] ↓ [ p ] ↓ [p]_{\downarrow} [ p ] ↓ q q q p p p
∑ c = 1 j [ q ] ↓ c ≥ ∑ c = 1 j [ p ] ↓ c for all j = 1 , … , C − 1 , \sum_{c=1}^{j}[q]_{\downarrow c}\ge\sum_{c=1}^{j}[p]_{\downarrow c}\qquad\text{for all }j=1,\ldots,C-1, c = 1 ∑ j [ q ] ↓ c ≥ c = 1 ∑ j [ p ] ↓ c for all j = 1 , … , C − 1 , with equality for j = C j=C j = C H p \mathcal{H}_p H p [30 ] it follows that H p ( p ) ≥ H p ( q ) \mathcal{H}_p(p)\ge\mathcal{H}_p(q) H p ( p ) ≥ H p ( q ) q ∈ P q\in\mathcal{P} q ∈ P p p p H ˉ ( L ˉ ) \bar{\mathcal{H}}(\bar{\mathcal{L}}) H ˉ ( L ˉ ) (13) .
With the softmax probability distribution p ^ ( y ^ ) \hat{p}(\hat{y}) p ^ ( y ^ ) y ^ \hat{y} y ^ L ( y ^ ) = L p ( p ^ ( y ^ ) ) ≤ L ˉ \mathcal{L}(\hat{y})=\mathcal{L}_p(\hat{p}(\hat{y}))\le\bar{\mathcal{L}} L ( y ^ ) = L p ( p ^ ( y ^ )) ≤ L ˉ H ( y ^ ) = H p ( p ^ ( y ^ ) ) ≤ H ˉ ( L ˉ ) \mathcal{H}(\hat{y})=\mathcal{H}_p(\hat{p}(\hat{y}))\le\bar{\mathcal{H}}(\bar{\mathcal{L}}) H ( y ^ ) = H p ( p ^ ( y ^ )) ≤ H ˉ ( L ˉ ) y ^ \hat{y} y ^
Next, we prove that an upper bound on the empirical loss
L ( y ^ ) = 1 D ∑ i = 1 D L ( y ^ ( i ) ) ≤ L ˉ \mathcal{L}(\hat{y})=\frac{1}{D}\sum_{i=1}^{D}\mathcal{L}(\hat{y}^{(i)})\le\bar{\mathcal{L}} L ( y ^ ) = D 1 i = 1 ∑ D L ( y ^ ( i ) ) ≤ L ˉ implies a corresponding bound on the entropy averaged over the dataset
H ( y ^ ) = 1 D ∑ i = 1 D H ( y ^ ( i ) ) ≤ H ˉ ( D L ˉ ) . \mathcal{H}(\hat{y})=\frac{1}{D}\sum_{i=1}^{D}\mathcal{H}(\hat{y}^{(i)})\le\bar{\mathcal{H}}(D\bar{\mathcal{L}}). H ( y ^ ) = D 1 i = 1 ∑ D H ( y ^ ( i ) ) ≤ H ˉ ( D L ˉ ) . Since the loss function is non-negative, it follows that for each sample, i = 1 , … , D i=1,\ldots,D i = 1 , … , D L ( y ^ ( i ) ) ≤ D L ˉ \mathcal{L}(\hat{y}^{(i)})\le D\bar{\mathcal{L}} L ( y ^ ( i ) ) ≤ D L ˉ i = 1 , … , D i=1,\ldots,D i = 1 , … , D H ( y ^ ( i ) ) ≤ H ˉ ( D L ˉ ) \mathcal{H}(\hat{y}^{(i)})\le\bar{\mathcal{H}}(D\bar{\mathcal{L}}) H ( y ^ ( i ) ) ≤ H ˉ ( D L ˉ )
H ( y ^ ) = 1 D ∑ i = 1 D H ( y ^ ( i ) ) ≤ 1 D ∑ i = 1 D H ˉ ( D L ˉ ) = H ˉ ( D L ˉ ) . \mathcal{H}(\hat{y})=\frac{1}{D}\sum_{i=1}^{D}\mathcal{H}(\hat{y}^{(i)})\le\frac{1}{D}\sum_{i=1}^{D}\bar{\mathcal{H}}(D\bar{\mathcal{L}})=\bar{\mathcal{H}}(D\bar{\mathcal{L}}). H ( y ^ ) = D 1 i = 1 ∑ D H ( y ^ ( i ) ) ≤ D 1 i = 1 ∑ D H ˉ ( D L ˉ ) = H ˉ ( D L ˉ ) . Theorem E.9 (Entropy bound from loss bound). For every T > 0 T>0 T > 0 ε > 0 \varepsilon>0 ε > 0 L ( y ^ ) ≤ ε \mathcal{L}(\hat{y})\le\varepsilon L ( y ^ ) ≤ ε H ( y ^ ) ≤ T \mathcal{H}(\hat{y})\le T H ( y ^ ) ≤ T
Proof. By Theorem E.8 , the entropy satisfies the bound
H ( y ^ ) ≤ H ˉ ( D L ( y ^ ) ) , \mathcal{H}(\hat{y})\le\bar{\mathcal{H}}(D\mathcal{L}(\hat{y})), H ( y ^ ) ≤ H ˉ ( D L ( y ^ )) , where H ˉ \bar{\mathcal{H}} H ˉ
lim L ˉ → 0 H ˉ ( D L ˉ ) = 0. \lim_{\bar{\mathcal{L}}\to0}\bar{\mathcal{H}}(D\bar{\mathcal{L}})=0. L ˉ → 0 lim H ˉ ( D L ˉ ) = 0. Therefore, for any T > 0 T>0 T > 0 H ˉ \bar{\mathcal{H}} H ˉ ε > 0 \varepsilon>0 ε > 0 L ( y ^ ) ≤ ε \mathcal{L}(\hat{y})\le\varepsilon L ( y ^ ) ≤ ε H ˉ ( D L ( y ^ ) ) ≤ T \bar{\mathcal{H}}(D\mathcal{L}(\hat{y}))\le T H ˉ ( D L ( y ^ )) ≤ T
Theorem E.10 (Entropy turnpike). Suppose that Assumption 3.1 holds, and consider a ResNet of depth N N N with early-exit attached to the set of residual blocks K O \mathcal{K}_{O} K O trained with stage cost loss 0 < γ ≤ 1 0 < \gamma\le1 0 < γ ≤ 1 by the optimal control training (4) and L \mathcal{L} L as the cross-entropy loss, and let its parameters w \mathbf{w} w be δ \delta δ suboptimal for some fixed 0 ≤ δ < ∞ 0 \le\delta< \infty 0 ≤ δ < ∞ i.e., J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ J_{N}(\mathbf{w}) \le\inf_{\mathbf{w}^{\prime}} J_{N}(\mathbf{w}^{\prime})+\delta J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ Then, the ResNet exhibits an entropy turnpike on the training data, i.e., for any entropy threshold T > 0 T>0 T > 0 there exists a depth bound κ < ∞ \kappa<\infty κ < ∞ such that
# { k ∈ K O ∪ { N } ∣ H ( y ^ k ) > T } ≤ κ , (18) \#\{k\in\mathcal{K}_{O}\cup\{N\}\mid\mathcal{H}(\hat{\mathbf{y}}_{k})>T\}\le\kappa, \tag*{(18)} # { k ∈ K O ∪ { N } ∣ H ( y ^ k ) > T } ≤ κ , (18) where y ^ k \hat{\mathbf{y}}_{k} y ^ k denotes the intermediate outputs on the training data.
Proof. By Theorem E.9, for any T > 0 T>0 T > 0 ε > 0 \varepsilon>0 ε > 0 L ( y ^ ) ≤ ε \mathcal{L}(\hat{\mathbf{y}})\le\varepsilon L ( y ^ ) ≤ ε H ( y ^ ) ≤ T \mathcal{H}(\hat{\mathbf{y}})\le T H ( y ^ ) ≤ T H ( y ^ k ) > T \mathcal{H}(\hat{\mathbf{y}}_{k})>T H ( y ^ k ) > T L ( y ^ k ) > ε \mathcal{L}(\hat{\mathbf{y}}_{k})>\varepsilon L ( y ^ k ) > ε
# { k ∈ K O ∪ { N } ∣ H ( y ^ k ) > T } ≤ # { k ∈ K O ∪ { N } ∣ L ( y ^ k ) > ε } . \#\{k\in\mathcal{K}_{O}\cup\{N\}\mid\mathcal{H}(\hat{\mathbf{y}}_{k})>T\}\le\#\{k\in\mathcal{K}_{O}\cup\{N\}\mid\mathcal{L}(\hat{\mathbf{y}}_{k})>\varepsilon\}. # { k ∈ K O ∪ { N } ∣ H ( y ^ k ) > T } ≤ # { k ∈ K O ∪ { N } ∣ L ( y ^ k ) > ε } . Moreover, under Assumption 3.1 by Theorem 3.2, the ResNet trained with stage cost loss weight 0 < γ ≤ 1 0<\gamma\le1 0 < γ ≤ 1 ε > 0 \varepsilon>0 ε > 0 κ < ∞ \kappa<\infty κ < ∞
# { k ∈ K O ∪ { N } ∣ L ( y ^ k ) > ε } ≤ κ , \#\{k\in\mathcal{K}_{O}\cup\{N\}\mid\mathcal{L}(\hat{\mathbf{y}}_{k})>\varepsilon\}\le\kappa, # { k ∈ K O ∪ { N } ∣ L ( y ^ k ) > ε } ≤ κ , and hence # { k ∈ K O ∪ { N } ∣ H ( y ^ k ) > T } ≤ κ \#\{k\in\mathcal{K}_{O}\cup\{N\}\mid\mathcal{H}(\hat{\mathbf{y}}_{k})>T\}\le\kappa # { k ∈ K O ∪ { N } ∣ H ( y ^ k ) > T } ≤ κ
Maximum Softmax Probability Turnpike
In this section, we show that the cross-entropy loss turnpike also induces a turnpike in the maximum softmax probability, another commonly used criterion for early-exiting Matsubara et al. [ [31 ] . We begin by establishing a relationship between the cross-entropy loss and the maximum softmax probability.
Theorem E.11 (Maximum softmax probability bound by loss bound). For every p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) if the cross-entropy loss L ( y ^ ) \mathcal{L}(\hat{\mathbf{y}}) L ( y ^ ) for some network output y ^ \hat{\mathbf{y}} y ^ satisfies
L ( y ^ ) ≤ L ˉ = 1 D min { log ( 2 ) , − log ( 1 − p ) } , \mathcal{L}(\hat{\mathbf{y}})\le\bar{\mathcal{L}}=\frac{1}{D}\min\{\log(2),-\log(1-p)\}, L ( y ^ ) ≤ L ˉ = D 1 min { log ( 2 ) , − log ( 1 − p )} , then for every sample i = 1 , … , D i=1,\ldots,D i = 1 , … , D the maximum predicted class probability is bounded from below by
max c [ p ^ ( y ^ ( i ) ) ] c ≥ 1 − p , \max_{c}\left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{c}\ge1-p, c max [ p ^ ( y ^ ( i ) ) ] c ≥ 1 − p , and moreover, the predicted class is the label class, i.e.,
argmax c [ p ^ ( y ^ ( i ) ) ] c = y ( i ) . \underset{c}{\operatorname{argmax}}\left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{c}=y^{(i)}. c argmax [ p ^ ( y ^ ( i ) ) ] c = y ( i ) . Proof. Suppose that the averaged cross-entropy loss satisfies
L ( y ^ ) = 1 D ∑ i = 1 D L ( y ^ ( i ) ) ≤ L ˉ . \mathcal{L}(\hat{\mathbf{y}})=\frac{1}{D}\sum_{i=1}^{D}\mathcal{L}(\hat{\mathbf{y}}^{(i)})\le\bar{\mathcal{L}}. L ( y ^ ) = D 1 i = 1 ∑ D L ( y ^ ( i ) ) ≤ L ˉ . Since the cross-entropy is nonnegative for each sample, L ( y ^ ( i ) ) ≥ 0 \mathcal{L}(\hat{\mathbf{y}}^{(i)})\ge0 L ( y ^ ( i ) ) ≥ 0
L ( y ^ ( i ) ) = − log ( [ p ^ ( y ^ ( i ) ) ] y ( i ) ) ≤ D L ˉ , \mathcal{L}(\hat{\mathbf{y}}^{(i)})=-\log\left(\left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{y^{(i)}}\right)\le D\bar{\mathcal{L}}, L ( y ^ ( i ) ) = − log ( [ p ^ ( y ^ ( i ) ) ] y ( i ) ) ≤ D L ˉ , and hence
[ p ^ ( y ^ ( i ) ) ] y ( i ) ≥ e − D L ˉ . \left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{y^{(i)}}\ge e^{-D\bar{\mathcal{L}}}. [ p ^ ( y ^ ( i ) ) ] y ( i ) ≥ e − D L ˉ . Since D L ˉ ≤ log ( 2 ) D\bar{\mathcal{L}}\le\log(2) D L ˉ ≤ log ( 2 ) [ p ^ ( y ^ ( i ) ) ] y ( i ) ≥ 1 2 \left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{y^{(i)}}\ge\frac{1}{2} [ p ^ ( y ^ ( i ) ) ] y ( i ) ≥ 2 1 [ p ^ ( y ^ ( i ) ) ] c > 0 \left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{c}>0 [ p ^ ( y ^ ( i ) ) ] c > 0 c = 1 , … , C c=1,\ldots,C c = 1 , … , C argmax c [ p ^ ( y ^ ( i ) ) ] c = y ( i ) \underset{c}{\operatorname{argmax}}\left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{c}=y^{(i)} c argmax [ p ^ ( y ^ ( i ) ) ] c = y ( i ) [ p ^ ( y ^ ( i ) ) ] y ( i ) = max c [ p ^ ( y ^ ( i ) ) ] c \left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{y^{(i)}}=\max_{c}\left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{c} [ p ^ ( y ^ ( i ) ) ] y ( i ) = max c [ p ^ ( y ^ ( i ) ) ] c L ˉ = 1 D min { log ( 2 ) , − log ( 1 − p ) } \bar{\mathcal{L}}=\frac{1}{D}\min\{\log(2),-\log(1-p)\} L ˉ = D 1 min { log ( 2 ) , − log ( 1 − p )} i = 1 , … , D i=1,\ldots,D i = 1 , … , D
max c [ p ^ ( y ^ ( i ) ) ] c = [ p ^ ( y ^ ( i ) ) ] y ( i ) ≥ e − D L ˉ = max { 1 2 , 1 − p } ≥ 1 − ε . \max_{c}\left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{c}=\left[\hat{p}(\hat{\mathbf{y}}^{(i)})\right]_{y^{(i)}}\ge e^{-D\bar{\mathcal{L}}}=\max\left\{\frac{1}{2},1-p\right\}\ge1-\varepsilon. c max [ p ^ ( y ^ ( i ) ) ] c = [ p ^ ( y ^ ( i ) ) ] y ( i ) ≥ e − D L ˉ = max { 2 1 , 1 − p } ≥ 1 − ε . :::
Theorem E.12 (Maximum softmax probability turnpike). Let Assumption 3.1 hold. Consider the ResNet of depth N N N K O \mathcal{K}_{O} K O 0 < γ ≤ 1 0 < \gamma\le1 0 < γ ≤ 1 L \mathcal{L} L w \mathbf{w} w δ \delta δ 0 ≤ δ < ∞ 0 \le\delta< \infty 0 ≤ δ < ∞ J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ J_{N}(\mathbf{w}) \le\inf_{\mathbf{w}'} J_{N}(\mathbf{w}') + \delta J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) κ < ∞ \kappa< \infty κ < ∞ 1 − p 1-p 1 − p
# { k ∈ K O ∪ { N } ∣ ∃ i = 1 , … , D , max c [ p ^ ( y ^ k ( i ) ) ] c < 1 − p } ≤ κ . (19) \#\left\{k \in\mathcal{K}_{O} \cup\{N\} \mathrel{\big|} \exists i = 1,\ldots,D,\ \max_{c}\left[\hat{p}\left(\hat{y}_{k}^{(i)}\right)\right]_{c} < 1-p\right\} \le\kappa. \tag*{(19)} # { k ∈ K O ∪ { N } ∃ i = 1 , … , D , c max [ p ^ ( y ^ k ( i ) ) ] c < 1 − p } ≤ κ . (19) Proof. By Theorem E.11, for any p > 0 p > 0 p > 0 ε > 0 \varepsilon> 0 ε > 0 L ( y ^ k ) ≤ ε \mathcal{L}(\hat{y}_{k}) \le\varepsilon L ( y ^ k ) ≤ ε
max c [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p \max_{c}\left[\hat{p}\left(\hat{y}_{k}^{(i)}\right)\right]_{c} \ge1-p c max [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p for all samples i = 1 , … , D i = 1,\ldots,D i = 1 , … , D i = 1 , … , D i = 1,\ldots,D i = 1 , … , D
max c [ p ^ ( y ^ k ( i ) ) ] c < 1 − p , \max_{c}\left[\hat{p}\left(\hat{y}_{k}^{(i)}\right)\right]_{c} < 1-p, c max [ p ^ ( y ^ k ( i ) ) ] c < 1 − p , then L ( y ^ k ) > ε \mathcal{L}(\hat{y}_{k}) > \varepsilon L ( y ^ k ) > ε
# { k ∈ K O ∪ { N } ∣ ∃ i = 1 , … , D , max c [ p ^ ( y ^ k ( i ) ) ] c < 1 − p } ≤ # { k ∈ K O ∪ { N } ∣ L ( y ^ k ) > ε } . \#\left\{k \in\mathcal{K}_{O} \cup\{N\} \mathrel{\big|} \exists i = 1,\ldots,D,\ \max_{c}\left[\hat{p}\left(\hat{y}_{k}^{(i)}\right)\right]_{c} < 1-p\right\}
\le\#\left\{k \in\mathcal{K}_{O} \cup\{N\} \mathrel{\big|} \mathcal{L}(\hat{y}_{k}) > \varepsilon\right\}. # { k ∈ K O ∪ { N } ∃ i = 1 , … , D , c max [ p ^ ( y ^ k ( i ) ) ] c < 1 − p } ≤ # { k ∈ K O ∪ { N } L ( y ^ k ) > ε } . Moreover, under Assumption 3.1 by Theorem 3.2, the ResNet trained with stage cost weight 0 < γ ≤ 1 0 < \gamma\le1 0 < γ ≤ 1 ε > 0 \varepsilon> 0 ε > 0 κ < ∞ \kappa< \infty κ < ∞
# { k ∈ K O ∪ { N } ∣ ∃ i = 1 , … , D , max c [ p ^ ( y ^ k ( i ) ) ] c < 1 − p } ≤ # { k ∈ K O ∪ { N } ∣ L ( y ^ k ) > ε } ≤ κ , \#\left\{k \in\mathcal{K}_{O} \cup\{N\} \mathrel{\big|} \exists i = 1,\ldots,D,\ \max_{c}\left[\hat{p}\left(\hat{y}_{k}^{(i)}\right)\right]_{c} < 1-p\right\}
\le\#\left\{k \in\mathcal{K}_{O} \cup\{N\} \mathrel{\big|} \mathcal{L}(\hat{y}_{k}) > \varepsilon\right\} \le\kappa, # { k ∈ K O ∪ { N } ∃ i = 1 , … , D , c max [ p ^ ( y ^ k ( i ) ) ] c < 1 − p } ≤ # { k ∈ K O ∪ { N } L ( y ^ k ) > ε } ≤ κ , which gives (19) .
:::
Implication of Turnpikes on Early-Exiting
Next, we analyze the implications of the turnpikes in the entropy and the maximum softmax probabilities on the early-exiting schemes, which use entropy and maximum softmax probability threshold as the early-exit criterion. First we show that under an upper bound on the loss, there exists an entropy threshold that guarantees correct classification.
Theorem E.13 (Entropy threshold for correct classification under loss bound). Suppose that the loss function satisfies
L ( y ^ ) ≤ L ˉ , \mathcal{L}(\hat{\mathbf{y}}) \le\bar{\mathcal{L}}, L ( y ^ ) ≤ L ˉ , for L ˉ > 0 \bar{\mathcal{L}} > 0 L ˉ > 0
T ( L ˉ ) = { ∞ L ˉ < 1 D log ( 2 ) D L ˉ e − D L ˉ − ( 1 − e − D L ˉ ) log ( 1 − e − D L ˉ ) L ˉ ≥ 1 D log ( 2 ) , (20) T(\bar{\mathcal{L}}) =
\begin{cases}
\infty& \bar{\mathcal{L}} < \frac{1}{D}\log(2) \\
D\bar{\mathcal{L}}e^{-D\bar{\mathcal{L}}} - \left(1-e^{-D\bar{\mathcal{L}}}\right)\log\left(1-e^{-D\bar{\mathcal{L}}}\right) & \bar{\mathcal{L}} \ge\frac{1}{D}\log(2),
\end{cases} \tag*{(20)} T ( L ˉ ) = { ∞ D L ˉ e − D L ˉ − ( 1 − e − D L ˉ ) log ( 1 − e − D L ˉ ) L ˉ < D 1 log ( 2 ) L ˉ ≥ D 1 log ( 2 ) , (20) guarantees that if a sample i = 1 , … , D i = 1,\ldots,D i = 1 , … , D
H ( y ^ ( i ) ) < T ( L ˉ ) , \mathcal{H}\left(\hat{\mathbf{y}}^{(i)}\right) < T(\bar{\mathcal{L}}), H ( y ^ ( i ) ) < T ( L ˉ ) , then this sample is classified correctly
c ^ ( y ^ ( i ) ) = y ( i ) . \hat{c}\left(\hat{\mathbf{y}}^{(i)}\right) = y^{(i)}. c ^ ( y ^ ( i ) ) = y ( i ) . Proof. The bound
L ( y ^ ) = 1 D ∑ i = 1 D L ( y ^ ( i ) ) ≤ L ˉ \mathcal{L}(\hat{\mathbf{y}}) = \frac{1}{D}\sum_{i=1}^{D}\mathcal{L}\left(\hat{\mathbf{y}}^{(i)}\right) \le\bar{\mathcal{L}} L ( y ^ ) = D 1 i = 1 ∑ D L ( y ^ ( i ) ) ≤ L ˉ implies, that for each sample i = 1 , … , D i = 1,\ldots,D i = 1 , … , D L ( y ^ ( i ) ) ≤ D L ˉ \mathcal{L}\left(\hat{\mathbf{y}}^{(i)}\right) \le D\bar{\mathcal{L}} L ( y ^ ( i ) ) ≤ D L ˉ L p ( p ) = − log ( [ p ] y ) ≤ D L ˉ \mathcal{L}_{p}(p) = -\log([p]_{y}) \le D\bar{\mathcal{L}} L p ( p ) = − log ([ p ] y ) ≤ D L ˉ [ p ] y ≥ e − D L ˉ [p]_{y} \ge e^{-D\bar{\mathcal{L}}} [ p ] y ≥ e − D L ˉ L ˉ < 1 D log ( 2 ) \bar{\mathcal{L}} < \frac{1}{D}\log(2) L ˉ < D 1 log ( 2 ) [ p ] y > 0.5 [p]_{y} > 0.5 [ p ] y > 0.5
Consequently, we only need to consider the nontrivial case where L ˉ ≥ 1 D log ( 2 ) \bar{\mathcal{L}} \ge\frac{1}{D}\log(2) L ˉ ≥ D 1 log ( 2 ) p ∈ [ 0 , 1 ] C \mathbf{p} \in[0,1]^{C} p ∈ [ 0 , 1 ] C [ p ] y ≥ e − D L ˉ [p]_{y} \ge e^{-D\bar{\mathcal{L}}} [ p ] y ≥ e − D L ˉ j ∈ N [ 1 , C ] ∖ { y } j \in\mathbb{N}_{[1,C]} \setminus\{y\} j ∈ N [ 1 , C ] ∖ { y } [ p ] j ≥ [ p ] y [p]_j \ge[p]_y [ p ] j ≥ [ p ] y p ∈ [ 0 , 1 ] C p \in[0,1]^C p ∈ [ 0 , 1 ] C
T ( L ˉ ) = min p H p ( p ) (21) T(\bar{L}) = \min_{p} \mathcal{H}_p(p) \tag*{(21)} T ( L ˉ ) = p min H p ( p ) (21) s.t. [ p ] y ≥ e − D L ˉ (22) \text{s.t.}\quad[p]_y \ge e^{-D\bar{L}} \tag*{(22)} s.t. [ p ] y ≥ e − D L ˉ (22) [ p ] j ≥ [ p ] y (23) [p]_j \ge[p]_y \tag*{(23)} [ p ] j ≥ [ p ] y (23) [ p ] c ≥ 0 c ∈ { 1 , … , C } ∖ { j , y } (24) [p]_c \ge0 \qquad c \in\{1,\ldots,C\} \setminus\{j,y\} \tag*{(24)} [ p ] c ≥ 0 c ∈ { 1 , … , C } ∖ { j , y } (24) ∑ i = 1 C [ p ] i = 1. (25) \sum_{i=1}^{C} [p]_i = 1. \tag*{(25)} i = 1 ∑ C [ p ] i = 1. (25) The feasible set of this optimization problem is
P = { p ∈ [ 0 , 1 ] C | [ p ] y ≥ e − D L ˉ , [ p ] j ≥ [ p ] y , ∑ c = 1 C [ p ] c = 1 } . \mathcal{P} = \left\{p \in[0,1]^C \,\middle|\, [p]_y \ge e^{-D\bar{L}},\ [p]_j \ge[p]_y,\ \sum_{c=1}^{C} [p]_c = 1\right\}. P = { p ∈ [ 0 , 1 ] C [ p ] y ≥ e − D L ˉ , [ p ] j ≥ [ p ] y , c = 1 ∑ C [ p ] c = 1 } . Define the feasible distribution p ∈ P p \in\mathcal{P} p ∈ P P \mathcal{P} P
[ p ] i = { e − D L ˉ , i = y , 1 − e − D L ˉ , i = j ≠ y , 0 , i ∉ { y , j } . [p]_i =
\begin{cases}
e^{-D\bar{L}}, & i=y,\\
1-e^{-D\bar{L}}, & i=j\ne y,\\
0, & i\notin\{y,j\}.
\end{cases} [ p ] i = ⎩ ⎨ ⎧ e − D L ˉ , 1 − e − D L ˉ , 0 , i = y , i = j = y , i ∈ / { y , j } . Then p p p q ∈ P q \in\mathcal{P} q ∈ P [ q ] c ↓ [q]^\downarrow_c [ q ] c ↓ [ p ] c ↓ [p]^\downarrow_c [ p ] c ↓ q q q p p p
∑ c = 1 j [ p ] c ↓ ≥ ∑ c = 1 j [ q ] c ↓ for all j = 1 , … , C − 1 , \sum_{c=1}^{j} [p]^\downarrow_c \ge\sum_{c=1}^{j} [q]^\downarrow_c \qquad\text{for all } j=1,\ldots,C-1, c = 1 ∑ j [ p ] c ↓ ≥ c = 1 ∑ j [ q ] c ↓ for all j = 1 , … , C − 1 , with equality for j = C j=C j = C H p \mathcal{H}_p H p [30 ] it follows that H p ( p ) ≤ H p ( q ) \mathcal{H}_p(p) \le\mathcal{H}_p(q) H p ( p ) ≤ H p ( q ) q ∈ P q \in\mathcal{P} q ∈ P p p p p p p entropy p ( p ) < entropy p ( q ) \operatorname{entropy}_p(p) < \operatorname{entropy}_p(q) entropy p ( p ) < entropy p ( q ) q ∈ P ∖ { p } q \in\mathcal{P} \setminus\{p\} q ∈ P ∖ { p } (20) .
Hence, if a probability distribution p ∈ [ 0 , 1 ] C p \in[0,1]^C p ∈ [ 0 , 1 ] C [ p ] y ≥ e − D L ˉ [p]_y \ge e^{-D\bar{L}} [ p ] y ≥ e − D L ˉ H p ( p ) < T ( L ˉ ) \mathcal{H}_p(p) < T(\bar{L}) H p ( p ) < T ( L ˉ ) [ p ] c < [ p ] y [p]_c < [p]_y [ p ] c < [ p ] y c ∈ { 1 , … , C } ∖ { y } c \in\{1,\ldots,C\} \setminus\{y\} c ∈ { 1 , … , C } ∖ { y }
This gives that if L ( y ^ ) ≤ L ˉ \mathcal{L}(\hat{y}) \le\bar{L} L ( y ^ ) ≤ L ˉ H ( y ^ ( i ) ) < T ( L ˉ ) \mathcal{H}(\hat{y}^{(i)}) < T(\bar{L}) H ( y ^ ( i ) ) < T ( L ˉ ) y ^ ( i ) \hat{y}^{(i)} y ^ ( i ) c ^ ( y ^ ( i ) ) = y ( i ) \hat{c}(\hat{y}^{(i)}) = y^{(i)} c ^ ( y ^ ( i ) ) = y ( i )
Theorem E.14 (Max softmax probability threshold for correct classification under loss bound). Suppose that the loss function satisfies
L ( y ^ ) ≤ L ˉ , \mathcal{L}(\hat{y}) \le\bar{L}, L ( y ^ ) ≤ L ˉ , for L ˉ > 0 \bar{L} > 0 L ˉ > 0
ρ ( L ˉ ) = { 1 L ˉ < 1 D log ( 2 ) , e − D L ˉ L ˉ ≥ 1 D log ( 2 ) , (26) \rho(\bar{L}) =
\begin{cases}
1 & \bar{L} < \frac{1}{D}\log(2),\\
e^{-D\bar{L}} & \bar{L} \ge\frac{1}{D}\log(2),
\end{cases} \tag*{(26)} ρ ( L ˉ ) = { 1 e − D L ˉ L ˉ < D 1 log ( 2 ) , L ˉ ≥ D 1 log ( 2 ) , (26) guarantees that if a sample i = 1 , … , D i=1,\ldots,D i = 1 , … , D
max c [ p ^ ( y ^ ( i ) ) ] c > 1 − ρ ( L ˉ ) , \max_c \left[\hat{p}(\hat{y}^{(i)})\right]_c > 1-\rho(\bar{L}), c max [ p ^ ( y ^ ( i ) ) ] c > 1 − ρ ( L ˉ ) , then that sample is classified correctly
c ^ ( y ^ ( i ) ) = y ( i ) . \hat{c}(\hat{y}^{(i)}) = y^{(i)}. c ^ ( y ^ ( i ) ) = y ( i ) . Proof. The loss bound
L ( y ^ ) = 1 D ∑ i = 1 D L ( y ^ ( i ) ) ≤ L ˉ \mathcal{L}(\hat{y}) = \frac{1}{D}\sum_{i=1}^{D}\mathcal{L}(\hat{y}^{(i)}) \le\bar{L} L ( y ^ ) = D 1 i = 1 ∑ D L ( y ^ ( i ) ) ≤ L ˉ implies, that for each sample, i = 1 , … , D i = 1, \ldots, D i = 1 , … , D L ( y ^ ( i ) ) ≤ D L ˉ \mathcal{L}(\hat{y}^{(i)}) \le D\bar{\mathcal{L}} L ( y ^ ( i ) ) ≤ D L ˉ L p ( p ) = − log ( [ p ] y ) ≤ D L ˉ \mathcal{L}_p(p) = -\log([p]_y) \le D\bar{\mathcal{L}} L p ( p ) = − log ([ p ] y ) ≤ D L ˉ [ p ] y ≥ e − D L ˉ [p]_y \ge e^{-D\bar{\mathcal{L}}} [ p ] y ≥ e − D L ˉ L ˉ < 1 D log ( 2 ) \bar{\mathcal{L}} < \frac{1}{D}\log(2) L ˉ < D 1 log ( 2 ) [ p ] y > 0.5 [p]_y > 0.5 [ p ] y > 0.5
Consequently, we only need to consider the nontrivial case where L ˉ ≥ 1 D log ( 2 ) \bar{\mathcal{L}} \ge\frac{1}{D}\log(2) L ˉ ≥ D 1 log ( 2 ) [ p ] y ≥ e − D L ˉ [p]_y \ge e^{-D\bar{\mathcal{L}}} [ p ] y ≥ e − D L ˉ c ≠ y ( i ) c \ne y^{(i)} c = y ( i ) [ p ] c ≤ 1 − e − D L ˉ [p]_c \le1-e^{-D\bar{\mathcal{L}}} [ p ] c ≤ 1 − e − D L ˉ max c [ p ^ ( y ^ ( i ) ) ] c > 1 − p ( L ˉ ) \max_c[\hat{p}(\hat{y}^{(i)})]_c > 1-p(\bar{\mathcal{L}}) max c [ p ^ ( y ^ ( i ) ) ] c > 1 − p ( L ˉ ) c ^ ( y ^ ( i ) ) = argmax c [ p ^ ( y ^ ( i ) ) ] c = y ( i ) \hat{c}(\hat{y}^{(i)}) = \operatorname*{argmax}_c[\hat{p}(\hat{y}^{(i)})]_c = y^{(i)} c ^ ( y ^ ( i ) ) = argmax c [ p ^ ( y ^ ( i ) ) ] c = y ( i )
Theorem E.15 (Bounded and correct early-exiting with entropy by turnpikes). Let Assumption 3.1 hold. And consider the ResNet with depth N N N K O \mathcal{K}_{\mathcal{O}} K O 0 < γ ≤ 1 0 < \gamma\le1 0 < γ ≤ 1 L \mathcal{L} L w \mathbf{w} w δ \delta δ 0 ≤ δ < ∞ 0 \le\delta< \infty 0 ≤ δ < ∞ J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ J_N(\mathbf{w}) \le\inf_{\mathbf{w}'}J_N(\mathbf{w}') + \delta J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ T T T x ( i ) x^{(i)} x ( i ) k k k y ^ k ( i ) \hat{y}^{(i)}_k y ^ k ( i ) H ( y ^ k ( i ) ) ≤ T \mathcal{H}(\hat{y}^{(i)}_k) \le T H ( y ^ k ( i ) ) ≤ T T > 0 T > 0 T > 0 i = 1 , … , D i = 1, \ldots, D i = 1 , … , D H ( y ^ k ( i ) ) ≤ T \mathcal{H}(\hat{y}^{(i)}_k) \le T H ( y ^ k ( i ) ) ≤ T k ∈ K O k \in\mathcal{K}_{\mathcal{O}} k ∈ K O
c ^ ( y ^ k ( i ) ) = y ( i ) . \hat{c}(\hat{y}^{(i)}_k) = y^{(i)}. c ^ ( y ^ k ( i ) ) = y ( i ) . Moreover, there exists κ \kappa κ i = 1 , … , D i = 1, \ldots, D i = 1 , … , D ( κ + 1 ) (\kappa+ 1) ( κ + 1 )
# { k ∈ K O ∪ { N } ∣ H ( y ^ k ( i ) ) > T } ≤ κ , \#\left\{k \in\mathcal{K}_{\mathcal{O}} \cup\{N\} \mid\mathcal{H}(\hat{y}^{(i)}_k) > T\right\} \le\kappa, # { k ∈ K O ∪ { N } ∣ H ( y ^ k ( i ) ) > T } ≤ κ , independent of the depth N N N
k ( i ) = min ( { k ∈ K O ∪ { N } ∣ H ( y ^ k ( i ) ) ≤ T } ∪ { N } ) ≤ seq ( K O ∪ { N } ) κ + 1 . k^{(i)} = \min\left(\left\{k \in\mathcal{K}_{\mathcal{O}} \cup\{N\} \mid\mathcal{H}(\hat{y}^{(i)}_k) \le T\right\} \cup\{N\}\right) \le\operatorname{seq}(\mathcal{K}_{\mathcal{O}} \cup\{N\})_{\kappa+1}. k ( i ) = min ( { k ∈ K O ∪ { N } ∣ H ( y ^ k ( i ) ) ≤ T } ∪ { N } ) ≤ seq ( K O ∪ { N } ) κ + 1 . Proof. We begin by showing that there exists an entropy threshold that guarantees correct classification, which requires deriving an upper bound on the intermediate losses. By Assumption 3.1 and Theorem 3.2, there exists a constant J ˉ \bar{J} J ˉ N N N K O \mathcal{K}_{\mathcal{O}} K O δ \delta δ w \mathbf{w} w
J N ( w ) ≤ J ˉ . J_N(\mathbf{w}) \le\bar{J}. J N ( w ) ≤ J ˉ . Hence, we have
∑ k ∈ K O γ L ( y ^ k ) + L ( y ^ ) ≤ J ˉ , \sum_{k \in\mathcal{K}_{\mathcal{O}}} \gamma\mathcal{L}(\hat{y}_k) + \mathcal{L}(\hat{y}) \le\bar{J}, k ∈ K O ∑ γ L ( y ^ k ) + L ( y ^ ) ≤ J ˉ , where y ^ k \hat{y}_k y ^ k y ^ \hat{y} y ^ γ ≤ 1 \gamma\le1 γ ≤ 1 L ( y ^ ) ≥ γ L ( y ^ ) \mathcal{L}(\hat{y}) \ge\gamma\mathcal{L}(\hat{y}) L ( y ^ ) ≥ γ L ( y ^ )
∑ k ∈ K O ∪ { N } γ L ( y ^ k ) ≤ ∑ k ∈ K O γ L ( y ^ k ) + L ( y ^ ) ≤ J ˉ . \sum_{k \in\mathcal{K}_{\mathcal{O}} \cup\{N\}} \gamma\mathcal{L}(\hat{y}_k) \le\sum_{k \in\mathcal{K}_{\mathcal{O}}} \gamma\mathcal{L}(\hat{y}_k) + \mathcal{L}(\hat{y}) \le\bar{J}. k ∈ K O ∪ { N } ∑ γ L ( y ^ k ) ≤ k ∈ K O ∑ γ L ( y ^ k ) + L ( y ^ ) ≤ J ˉ . Moreover, due to the non-negativity of the loss function, each intermediate loss is individually bounded:
L ( y ^ k ) ≤ J ˉ γ , k ∈ K O ∪ { N } , \mathcal{L}(\hat{y}_k) \le\frac{\bar{J}}{\gamma}, \quad k \in\mathcal{K}_{\mathcal{O}} \cup\{N\}, L ( y ^ k ) ≤ γ J ˉ , k ∈ K O ∪ { N } , for any ResNet depth N N N K O \mathcal{K}_{\mathcal{O}} K O
By Theorem E.13 , if the loss of an intermediate output satisfies L ( y ^ k ) ≤ J ˉ γ \mathcal{L}(\hat{y}_k) \le\frac{\bar{J}}{\gamma} L ( y ^ k ) ≤ γ J ˉ T ( J ˉ γ ) T\left(\frac{\bar{J}}{\gamma}\right) T ( γ J ˉ ) H ( y ^ k ( i ) ) < T ( J ˉ γ ) \mathcal{H}(\hat{y}^{(i)}_k) < T\left(\frac{\bar{J}}{\gamma}\right) H ( y ^ k ( i ) ) < T ( γ J ˉ ) i = 1 , … , D i = 1, \ldots, D i = 1 , … , D c ^ ( y ^ k ( i ) ) = y ( i ) \hat{c}(\hat{y}^{(i)}_k) = y^{(i)} c ^ ( y ^ k ( i ) ) = y ( i ) T = 1 2 T ( J ˉ γ ) T = \frac{1}{2}T\left(\frac{\bar{J}}{\gamma}\right) T = 2 1 T ( γ J ˉ ) H ( y ^ k ( i ) ) ≤ T \mathcal{H}(\hat{y}^{(i)}_k) \le T H ( y ^ k ( i ) ) ≤ T
H ( y ^ ) = 1 D ∑ i = 1 D H ( y ( i ) ^ ) ≤ 1 D T . \mathcal{H}(\hat{\mathbf{y}})=\frac{1}{D}\sum_{i=1}^{D}\mathcal{H}(\hat{\mathbf{y}^{(i)}})\leq\frac{1}{D}T. H ( y ^ ) = D 1 i = 1 ∑ D H ( y ( i ) ^ ) ≤ D 1 T . Then, since entropy of each individual sample is non-negative H ( y ( i ) ^ ) ≥ 0 \mathcal{H}(\hat{\mathbf{y}^{(i)}})\geq0 H ( y ( i ) ^ ) ≥ 0 i = 1 , … , D i=1,\ldots,D i = 1 , … , D i = 1 , … , D i=1,\ldots,D i = 1 , … , D H ( y ( i ) ^ ) ≤ T \mathcal{H}(\hat{\mathbf{y}^{(i)}})\leq T H ( y ( i ) ^ ) ≤ T Assumption 3.1 , a ResNet trained by (4) exhibits an entropy turnpike by Theorem E.10 . That is, there exists constant κ < ∞ \kappa<\infty κ < ∞
# { k ∈ K O ∪ { N } ∣ H ( y ^ k ) > 1 D T } ≤ κ , \#\left\{k\in\mathcal{K}_{\mathcal{O}}\cup\{N\}\mathrel{\big|}\mathcal{H}(\hat{\mathbf{y}}_k)>\frac{1}{D}T\right\}\leq\kappa, # { k ∈ K O ∪ { N } H ( y ^ k ) > D 1 T } ≤ κ , and hence, the early-exit depth for all samples i = 1 , … , D i=1,\ldots,D i = 1 , … , D ( κ + 1 ) (\kappa+1) ( κ + 1 )
k ( i ) = min ( { k ∈ K O ∪ { N } ∣ H ( y ^ k ( i ) ) ≤ T } ∪ { N } ) ≤ seq ( K O ∪ { N } ) κ + 1 . k^{(i)}=\min\left(\left\{k\in\mathcal{K}_{\mathcal{O}}\cup\{N\}\mathrel{\big|}\mathcal{H}(\hat{\mathbf{y}}_k^{(i)})\leq T\right\}\cup\{N\}\right)\leq\operatorname{seq}(\mathcal{K}_{\mathcal{O}}\cup\{N\})_{\kappa+1}. k ( i ) = min ( { k ∈ K O ∪ { N } H ( y ^ k ( i ) ) ≤ T } ∪ { N } ) ≤ seq ( K O ∪ { N } ) κ + 1 . Theorem E.16 (Bounded and correct early-exiting with max softmax probabilities by turnpikes). Let Assumption 3.1 hold. And consider the ResNet with depth N N N 0 < γ ≤ 1 0<\gamma\leq1 0 < γ ≤ 1 L \mathcal{L} L w \mathbf{w} w δ \delta δ 0 ≤ δ < ∞ 0\leq\delta<\infty 0 ≤ δ < ∞ J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ J_N(\mathbf{w})\leq\inf_{\mathbf{w}'}J_N(\mathbf{w}')+\delta J N ( w ) ≤ inf w ′ J N ( w ′ ) + δ p p p x ( i ) \mathbf{x}^{(i)} x ( i ) k ∈ K O k\in\mathcal{K}_{\mathcal{O}} k ∈ K O y ^ k ( i ) \hat{\mathbf{y}}_k^{(i)} y ^ k ( i ) max c [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p \max_c[\hat{p}(\hat{\mathbf{y}}_k^{(i)})]_c\geq1-p max c [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p p > 0 p>0 p > 0 κ \kappa κ i = 1 , … , D i=1,\ldots,D i = 1 , … , D N N N
# { k ∈ K O ∪ { N } ∣ max c [ p ^ ( y ^ k ( i ) ) ] c < 1 − p } ≤ κ . (27) \#\left\{k\in\mathcal{K}_{\mathcal{O}}\cup\{N\}\mathrel{\big|}\max_c[\hat{p}(\hat{\mathbf{y}}_k^{(i)})]_c<1-p\right\}\leq\kappa. \tag*{(27)} # { k ∈ K O ∪ { N } c max [ p ^ ( y ^ k ( i ) ) ] c < 1 − p } ≤ κ . (27) Moreover, the early-exit depth in terms of the residual block is bounded by
k ( i ) = min ( { k ∈ K O ∪ { N } ∣ max c [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p } ∪ { N } ) ≤ seq ( K O ∪ { N } ) κ + 1 . (28) k^{(i)}=\min\left(\left\{k\in\mathcal{K}_{\mathcal{O}}\cup\{N\}\mathrel{\big|}\max_c[\hat{p}(\hat{\mathbf{y}}_k^{(i)})]_c\geq1-p\right\}\cup\{N\}\right)\leq\operatorname{seq}(\mathcal{K}_{\mathcal{O}}\cup\{N\})_{\kappa+1}. \tag*{(28)} k ( i ) = min ( { k ∈ K O ∪ { N } c max [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p } ∪ { N } ) ≤ seq ( K O ∪ { N } ) κ + 1 . (28) and if a sample exits before the final output, i.e., max c [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p \max_c[\hat{p}(\hat{\mathbf{y}}_k^{(i)})]_c\geq1-p max c [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p k ∈ K O k\in\mathcal{K}_{\mathcal{O}} k ∈ K O
c ^ ( y ^ k ( i ) ) = y ( i ) . \hat{c}(\hat{\mathbf{y}}_k^{(i)})=y^{(i)}. c ^ ( y ^ k ( i ) ) = y ( i ) . Proof. We begin by showing that there exists an max softmax probability threshold that guarantees correct classification, which requires deriving an upper bound on the intermediate losses. By Assumption 3.1 and Theorem 3.2, there exists a constant J ˉ \bar{J} J ˉ N N N δ \delta δ w \mathbf{w} w
J N ( w ) ≤ J ˉ . J_N(\mathbf{w})\leq\bar{J}. J N ( w ) ≤ J ˉ . Hence, we have
∑ k ∈ K O γ L ( y ^ k ) + L ( y ^ ) ≤ J ˉ , \sum_{k\in\mathcal{K}_{\mathcal{O}}}\gamma\mathcal{L}(\hat{\mathbf{y}}_k)+\mathcal{L}(\hat{\mathbf{y}})\leq\bar{J}, k ∈ K O ∑ γ L ( y ^ k ) + L ( y ^ ) ≤ J ˉ , where y ^ k \hat{\mathbf{y}}_k y ^ k y ^ = y ^ N \hat{\mathbf{y}}=\hat{\mathbf{y}}_N y ^ = y ^ N γ ≤ 1 \gamma\leq1 γ ≤ 1 L ( y ^ ) ≥ γ L ( y ^ ) \mathcal{L}(\hat{\mathbf{y}})\geq\gamma\mathcal{L}(\hat{\mathbf{y}}) L ( y ^ ) ≥ γ L ( y ^ )
∑ k ∈ K O ∪ { N } γ L ( y ^ k ) ≤ ∑ k ∈ K O γ L ( y ^ k ) + L ( y ^ ) ≤ J ˉ . \sum_{k\in\mathcal{K}_{\mathcal{O}}\cup\{N\}}\gamma\mathcal{L}(\hat{\mathbf{y}}_k)\leq\sum_{k\in\mathcal{K}_{\mathcal{O}}}\gamma\mathcal{L}(\hat{\mathbf{y}}_k)+\mathcal{L}(\hat{\mathbf{y}})\leq\bar{J}. k ∈ K O ∪ { N } ∑ γ L ( y ^ k ) ≤ k ∈ K O ∑ γ L ( y ^ k ) + L ( y ^ ) ≤ J ˉ . Moreover, due to the non-negativity of the loss function, each intermediate loss is individually bounded:
L ( y ^ k ) ≤ J ˉ γ , k ∈ K O ∪ { N } , \mathcal{L}(\hat{\mathbf{y}}_k)\leq\frac{\bar{J}}{\gamma},\quad k\in\mathcal{K}_{\mathcal{O}}\cup\{N\}, L ( y ^ k ) ≤ γ J ˉ , k ∈ K O ∪ { N } , for any ResNet depth N N N K O \mathcal{K}_{\mathcal{O}} K O Theorem E.14 , if the loss of an intermediate output satisfies L ( y ^ k ) ≤ J ˉ γ \mathcal{L}(\hat{y}_k) \le\frac{\bar{J}}{\gamma} L ( y ^ k ) ≤ γ J ˉ p ( J ˉ γ ) p\left(\frac{\bar{J}}{\gamma}\right) p ( γ J ˉ ) max c [ p ^ ( y ^ k ( i ) ) ] c > 1 − p ( J ˉ γ ) \max_c\left[\hat{p}(\hat{y}_k^{(i)})\right]_c > 1-p\left(\frac{\bar{J}}{\gamma}\right) max c [ p ^ ( y ^ k ( i ) ) ] c > 1 − p ( γ J ˉ ) i = 1 , … , D i=1,\ldots,D i = 1 , … , D c ^ ( y ^ k ( i ) ) = y ( i ) \hat{c}(\hat{y}_k^{(i)})=y^{(i)} c ^ ( y ^ k ( i ) ) = y ( i ) p = 1 2 p ( J ˉ γ ) p=\frac{1}{2}p\left(\frac{\bar{J}}{\gamma}\right) p = 2 1 p ( γ J ˉ ) max c [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p \max_c\left[\hat{p}(\hat{y}_k^{(i)})\right]_c \ge1-p max c [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p
Secondly, under Assumption 3.1 a ResNet trained by (4) exhibits a max softmax probability turnpike by Theorem E.12 . That is, there exists a κ \kappa κ i = 1 , … , D i=1,\ldots,D i = 1 , … , D 1 − p 1-p 1 − p
# { k ∈ K O ∪ { N } ∣ ∃ i = 1 , … , D , max c [ p ^ ( y ^ k ( i ) ) ] c < 1 − p } ≤ κ , (29) \#\left\{k\in\mathcal{K}_{\mathcal{O}}\cup\{N\}\mid\exists i=1,\ldots,D,\ \max_c\left[\hat{p}(\hat{y}_k^{(i)})\right]_c<1-p\right\}\le\kappa, \tag*{(29)} # { k ∈ K O ∪ { N } ∣ ∃ i = 1 , … , D , c max [ p ^ ( y ^ k ( i ) ) ] c < 1 − p } ≤ κ , (29) independent of the depth N N N K O \mathcal{K}_{\mathcal{O}} K O Assumption 3.1 , a ResNet trained by (4) exhibits an max softmax probability turnpike by Theorem E.10 . That is, since 1 − p > 0 1-p>0 1 − p > 0 κ < ∞ \kappa<\infty κ < ∞
k ( i ) = min ( { k ∈ K O ∪ { N } ∣ max c [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p } ∪ { N } ) ≤ seq ( K O ∪ { N } ) κ + 1 \begin{aligned}
k^{(i)}=\min\left(\left\{k\in\mathcal{K}_{\mathcal{O}}\cup\{N\}\mid\max_c\left[\hat{p}(\hat{y}_k^{(i)})\right]_c\ge1-p\right\}\cup\{N\}\right) \\
&\le\operatorname{seq}(\mathcal{K}_{\mathcal{O}}\cup\{N\})_{\kappa+1}
\end{aligned} k ( i ) = min ( { k ∈ K O ∪ { N } ∣ c max [ p ^ ( y ^ k ( i ) ) ] c ≥ 1 − p } ∪ { N } ) ≤ seq ( K O ∪ { N } ) κ + 1 for all samples i = 1 , … , D i=1,\ldots,D i = 1 , … , D seq ( K O ∪ { N } ) κ + 1 \operatorname{seq}(\mathcal{K}_{\mathcal{O}}\cup\{N\})_{\kappa+1} seq ( K O ∪ { N } ) κ + 1
Scope and Limitations
Our findings and theoretical insights contribute to our understanding of early-exit neural networks. Crucially, by connecting practical training concepts to optimal control theory, we are able to introduce the turnpike phenomenon to the deep learning community and utilize the tools to uncover a systematic similarity behavior of the latent dynamics involved in joint training early-exits of ResNets. We want to highlight, that the analysis involved common assumptions about the asymptotic optimality of the data problem leading us to the starting point of our reasoning in Assumption 3.1 . As noted in the main text, we were able to prove it for a realistic scenario of cross-entropy loss and fully connected ResNets with ReLU activations. It remains to future work, to extend this loss decay result to other classes of networks, commonly employed for early-exiting, i.e., Transformer backbones and even networks without the residual connection. Even though our experimental suite strongly supports our theoretical findings, we want to highlight the inevitable gap between asymptotic statements for networks trained to global optimality and the finite precision of the stochastic gradient training. We believe that our work contributes greatly to the rigor involved in bridging the gap between optimal control theory and practical deep learning experiments.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?
Answer: [Yes]
Justification: The main claims of the abstract are supported: the theoretical contributions are described in § 3.2 and § 3.3 , with proofs provided in Appendix § 12 . The experimental findings supporting these claims are presented in Section 4 and further supplemented in Appendix § 8 .
Guidelines:
The answer [N/A] means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Appendix § 13 , we discuss the limitations of this work.
Guidelines:
The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate “Limitations” section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]
Justification: The paper provides the full proofs and the assumptions in Appendix § 12 .
Guidelines:
The answer [N/A] means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper discloses all information necessary to reproduce the main experimental results. We use standard ResNet architectures as backbone networks and evaluate on standard benchmark datasets, with full details — including hyperparameters, training configuration, and dataset splits — provided in Appendix § 8 .§ 1 . The early-exit architecture is described in § 4.1 .
Guidelines:
The answer [N/A] means that the paper does not include experiments.
If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code and instructions to reproduce our results is available at https://github.com/OptCon/early-exit-turnpike . All datasets used in this work are publicly available and are established benchmark datasets in the community.
Guidelines:
The answer [N/A] means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy ) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy ) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?
Answer: [Yes]
Justification: All training and test details are specified. We follow standard data splits for all benchmarks. Hyperparameters and optimizer settings follow established conventions for ResNet architectures, with full details in Appendix § 8 .§ 1 . The early-exit architecture and its additional hyperparameters are described in § 4.1 and Appendix § 8 .§ 1 , and ablated in Section 4.4 and Appendix § 8 .5.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars and formal statistical significance tests are not reported, as the primary contribution of this paper is theoretical and our extensive ResNet trainings impose across all configurations and datasets an infeasible computational overhead. Nevertheless, the robustness of our findings is supported by consistent results across multiple datasets (Section A.2) and the ablation of the hyperparameter stage cost weight in Appendix § 8 .5.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: GPU resources used in our experiments are reported in Appendix § 8 .§ 1 . Execution times are not reported, as our primary contribution is a theoretical analysis of hidden representations, which is independent of the underlying hardware.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines ?
Answer: [Yes]
Justification: This research conforms with the NeurIPS Code of Ethics. Our primary contribution is theoretical, and all experiments are conducted on publicly available benchmark datasets, raising no ethical concerns regarding data privacy, fairness, or misuse.
Guidelines:
The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [N/A]
Justification: As our primary contribution is a theoretical analysis of hidden representations in early-exit networks, we do not foresee any direct negative societal impacts. A broader discussion of the societal implications of early-exit networks in general is beyond the scope of this work.
Guidelines:
The answer [N/A] means that there is no societal impact of the work performed.
If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?
Answer: [N/A]
Justification: This paper presents a theoretical analysis and experiments on standard benchmark datasets. No new data, pre-trained models, or other high-risk assets are released, so safeguards are not applicable.
Guidelines:
The answer [N/A] means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes]
Justification: All assets used in this work are properly credited. The benchmark datasets are referenced in Section 4 and Appendix § 8 .§ 1 , and the PyTorch version used for implementation is specified in Appendix § 8 .§ 1 . All assets are used in accordance with their respective licenses.
Guidelines:
The answer [N/A] means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset’s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The only new asset introduced in this paper is our code, which will be publicly released with the camera-ready version and will include documentation sufficient to reproduce our experimental results.
Guidelines:
The answer [N/A] means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [N/A]
Justification: This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [N/A]
Justification: This paper does not involve crowdsourcing or research with human subjects, and therefore requires no IRB approval.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required?
Answer: [N/A]
Justification: No LLMs were used as a component of the core methods in this research. Any use of LLMs was limited to writing and editing assistance, which does not impact the methodology or scientific contributions of the paper.
Guidelines:
The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.
