Towards an Optimal Control Foundation of Early Exits - Turnpikes and ResNets
Authors: Jens Püttschneider, Simon Heilig, Asja Fischer, Timm Faulwasser
Organizations: Institute of Control Systems, Hamburg University of Technology, Hamburg, Germany · Faculty of Computer Science, Ruhr University Bochum, Bochum, Germany
The feed-forward propagation through neural networks is crucial for training and inference. To trade off efficiency and accuracy, it has been proposed to consider intermediate outputs of hidden states as data-dependent regularization during training and, ultimately, as early-exits during inference. In this work, we analyze the joint optimization of loss functions computed for the output layer and intermediate layers using optimal control theory. We prove that ResNets trained in this joint fashion exhibit the so-called turnpike phenomenon, this implies that the number of layers required to reach a prescribed loss level is bounded from above independently of the overall network depth. This induces a similarity property across the internal representations of early-exiting networks of varying depths. We connect the turnpike to the overthinking phenomenon, and provide theoretical insights into the success of early-exit criteria derived from softmax probabilities, specifically entropy and max-probability. In a range of experiments, we demonstrate the existence and effect of turnpikes and the resulting similarity in the early-exit performance for ResNets of varying depths.
Figures & tables
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.
Figure 2: Example of optimal trajectories of the OCP ( 2 ) for varying horizons N=5,10,…,40 . The red dashed lines indicate the turnpike (xs⋆,ws⋆)=(1,−1) .
Figure 3: The fundamental connection between early-exiting joint training formulation and training as an optimal control problem.
Figure 4: Accuracies on CIFAR-10 for ResNets with residual blocks N∈{18,36,54} with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
Figure 5: Training and test loss trajectories across network depth, conditioned on the final prediction outcome on CIFAR-10 with ResNet N=54 and early exits placed at every block ( M=1 ).
Figure 6: Cardinality of the turnpike set #Q^ε and fitted curves A/γ+B in dashed over the stage cost loss weight γ for fixed loss thresholds ε . Results are for CIFAR-10, ResNet with N=54 residual blocks and exits at every block ( M=1 ).
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
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} and with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
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} and with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( 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} and with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
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} and with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
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,M=1 .
Figure 12: Early-exiting results with the max softmax probability complement as exiting criterion on CIFAR-10 for ResNets with residual blocks N∈{18,36,54} with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
Figure 13: Early-exiting results with the entropy as exiting criterion on CIFAR-10 for ResNets with residual blocks N∈{18,36,54} with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
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} and early-exits at every residual block ( M=1 ).
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 residual blocks trained with varying stage-cost weights and early-exits at every residual block ( M=1 ).
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.
Figure 17: Overview of the main theoretical contributions.
Figure 18: Illustration construction of the infinite-depth ResNet that ensures exponential decay of the cross-entropy loss. First, Theorem E.3 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.
Early-exit neural networks stop processing inputs at intermediate layers when predictions are sufficiently reliable, trading accuracy for lower latency and energy.
ORFE Department, Princeton University, Princeton, NJ 08544, USA · Racah Institute of Physics, The Hebrew University of Jerusalem, Jerusalem 91904, Israel