Learning To Stop While Learning To Predict

Xinshi Chen, Hanjun Dai, Yu Li, Xin Gao, Le Song

Most deep learning models use a fixed number of layers for every input, regardless of its difficulty. This paper introduces a variational framework to learn an instance-specific stopping policy, allowing models to "stop thinking" once they reach an optimal prediction. This dynamic approach improves both accuracy and computational efficiency across diverse tasks like sparse recovery, meta-learning, and image denoising.

The Fixed-Depth Dilemma

In traditional iterative algorithms—such as those used in optimization or signal processing—we rely on stopping criteria to decide when a result is "good enough." However, modern deep learning architectures typically use a "fixed-depth" approach. Every input, whether a simple digit or a complex natural scene, passes through the exact same number of layers.

Comparison between fixed-depth learned algorithms and dynamic-depth traditional algorithms.

This rigid structure leads to two main issues:

  1. Computational Waste: The model spends unnecessary cycles "over-thinking" simple inputs that converged to a correct prediction many layers ago.
  2. Over-thinking (Overfitting): In many inverse problems, such as image denoising, processing an input through too many layers can actually degrade performance. The model begins to fit to noise rather than the underlying signal, illustrating a classic variance-bias tradeoff.

To resolve this, the authors propose a "steerable architecture" capable of sequentially determining the optimal number of layers to execute for each specific input instance.

A Variational Framework for Early Stopping

The proposed framework consists of two core components: a predictive model ($F_\theta$) that generates a sequence of hidden states, and a stopping policy ($\pi_\phi$) that evaluates whether to halt computation at the current layer.

To train these components jointly, the authors utilize Variational Bayes, treating the stopping time $t$ as a latent variable. They define a training objective based on the $\beta$-VAE (Variational Autoencoder) framework. Because training this via standard Expectation-Maximization (EM) is notoriously unstable and slow, they introduce a clever two-stage training procedure:

  • Stage I: Oracle Model Learning. An "oracle" distribution is defined, which has access to the ground-truth labels. This oracle identifies the absolute best layer to stop at for every training sample. The predictive model is then trained to perform optimally under the assumption of this perfect stopping behavior.
  • Stage II: Imitation Learning. Because the oracle requires ground-truth labels (which are unavailable at test time), the stopping policy ($\pi_\phi$) is trained to mimic the oracle's behavior using only the input and intermediate hidden states.

The authors also demonstrate a fascinating theoretical link: minimizing the divergence between the learned policy and the oracle is mathematically equivalent to solving a maximum-entropy Reinforcement Learning problem.

Experimental Validation

The researchers evaluated their dynamic-depth method across four distinct domains:

  1. Sparse Recovery: Using synthetic data following the LISTA (Learned Iterative Soft-Thresholding Algorithm) setup, with varying signal-to-noise ratios (SNR).
  2. Few-shot Meta-learning: Modifying standard Omniglot and MiniImagenet benchmarks into a "task-imbalanced" setting where different tasks have varying numbers of training examples (shots).
  3. Image Denoising: Training on the BSD500 dataset and evaluating on BSD68.
  4. Image Recognition: Utilizing Tiny-ImageNet with a VGG16 backbone.
Task-imbalanced meta-learning setup where different tasks require different numbers of adaptation steps.

Key Insights and Results

  • The Power of the Oracle: The most striking insight is the performance gap revealed by the Oracle. On Tiny-ImageNet, a standard VGG16 achieves ~58% accuracy. If an oracle simply picks the best internal layer to stop at for each image, that same model's accuracy jumps to over 83%. This suggests that "correct" answers are often formed in intermediate layers but are "lost" by the time they reach the final output.
  • Efficiency in Sparse Recovery: The proposed model (LISTA-stop) achieved better recovery accuracy with only 20 iterations than traditional FISTA algorithms achieved with 100 iterations.
  • Meta-Learning Gains: On imbalanced MiniImagenet tasks, MAML-stop improved accuracy by 3.5% over the standard MAML algorithm, proving that some tasks inherently benefit from more (or fewer) adaptation steps than others.
  • Denoising Robustness and Adaptive Regularization: The stopping policy acts as a per-instance regularizer. For high-noise images, DnCNN-stop outperformed the standard fixed-depth DnCNN. It generalized significantly better to out-of-distribution noise levels (e.g., $\sigma=65, 75$ when trained on $\sigma \le 55$), maintaining a much higher Peak Signal-to-Noise Ratio (PSNR) by avoiding the "over-thinking" that amplifies noise.

Limitations and Future Work

While the framework shows immense promise, the authors note a few key areas for future development:

  • The Imitation Gap: While the Oracle demonstrates massive potential (e.g., the 83% accuracy ceiling on Tiny-ImageNet), the actual learned policy ($\pi_\phi$) often struggles to fully capture that potential in complex recognition tasks. Closing this "imitation gap" remains a primary challenge.
  • Training Complexity: Although the two-stage approach is more efficient than standard EM, it still requires computing multiple layers during training, which is memory-intensive. Stochastic sampling is suggested as a workaround, but more optimized training kernels are needed.
  • Policy Architecture: The current stopping policy is relatively simple. More sophisticated policy architectures or better reward shaping in the RL formulation might be required to tackle high-level vision tasks effectively.

Summary updated

Abstract

There is a recent surge of interest in designing deep architectures based on the update steps in traditional algorithms, or learning neural networks to improve and replace traditional algorithms. While traditional algorithms have certain stopping criteria for outputting results at different iterations, many algorithm-inspired deep models are restricted to a ``fixed-depth'' for all inputs. Similar to algorithms, the optimal depth of a deep architecture may be different for different input instances, either to avoid ``over-thinking'', or because we want to compute less for operations converged already. In this paper, we tackle this varying depth problem using a steerable architecture, where a feed-forward deep model and a variational stopping policy are learned together to sequentially determine the optimal number of layers for each input instance. Training such architecture is very challenging. We provide a variational Bayes perspective and design a novel and effective training procedure which decomposes the task into an oracle model learning stage and an imitation stage. Experimentally, we show that the learned deep model along with the stopping policy improves the performances on a diverse set of tasks, including learning sparse recovery, few-shot meta learning, and computer vision tasks.
BibTeX
@inproceedings{chen2020learning,
  author = {Xinshi Chen and Hanjun Dai and Yu Li and Xin Gao and Le Song},
  title = {{Learning To Stop While Learning To Predict}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
}
Figure