Introduction
In standard machine learning, Empirical Risk Minimization (ERM) is the dominant paradigm, typically involving training on a fixed dataset and testing on a held-out split. However, ERM relies on the assumption that data is independent and identically distributed (i.i.d.), an assumption that often fails in real-world, non-stationary data streams.
Minimum Description Length (MDL) offers a robust alternative by formalizing Occam’s Razor: the best model is the one that compresses the data most effectively. Specifically, prequential MDL measures how well a model predicts the next data point given all prior observations. While theoretically elegant, calculating prequential MDL for deep neural networks has historically been computationally prohibitive, requiring models to be retrained thousands of times as datasets grow. This work introduces methods to make computing these description lengths practical and efficient for modern deep learning.
Methods: Practical Sequential Learning
The authors move away from expensive "train-from-scratch" (block-wise) approaches, instead leveraging techniques from Continual Learning (CL). Their core framework, Mini-batch Incremental Training with Replay Streams (MI/RS), enables massive-scale data rehearsal without exhausting system memory.
Key innovations include:
- Forward-Calibration: To address the overconfidence typical of neural networks, the authors use a "temperature" parameter ($\beta$) in the softmax layer, optimized via gradient descent on the fly. This ensures probability estimates match the observed distribution, which is critical for minimizing log-loss.
- Replay-Streams: Rehearsal is essential to prevent catastrophic forgetting. By using multiple file pointers ("streams") to read data sequentially from disk and stochastically resetting them, the authors achieve approximate random sampling with minimal RAM usage.
- Optimization Stability: Techniques such as Exponential Moving Averages (EMA) of parameters, label smoothing, and weight standardization were found to be vital for stable sequential learning.
MDL as a Complexity Filter
A primary advantage of MDL is its natural ability to handle model selection and complexity. In a synthetic benchmark using RGB-MNIST, the authors demonstrated how MDL handles "distractor" features better than ERM. While ERM-trained models might perform similarly regardless of whether they process one color channel or three, MDL clearly prefers the simpler model (one channel), as it naturally penalizes the complexity of processing irrelevant information.
Key Results and Efficiency
The MI/RS approach achieved state-of-the-art compression results across several benchmarks. On CIFAR-10, the method reached a description length of ~22.1k nats, a significant improvement over the ~31.4k nats reported in prior work. On the massive CLOC (Continual Geo-Localization) dataset, which contains 39 million chronologically sorted images, forward-calibration proved essential for maintaining compression performance in a highly non-stationary environment.
Furthermore, the authors found that for a fixed compute budget, online learning with rehearsal consistently achieves shorter description lengths than traditional block-wise training. Interestingly, deeper and wider models (like ResNet-101) were found to provide better compression from the very beginning of a sequence, despite their higher parameter counts.
Limitations and Future Work
Despite these successes, the "plasticity problem" remains: models fine-tuned on new data eventually lose their ability to learn as effectively as a model started from scratch. Additionally, standard ERM optimization tricks, such as cosine decay learning rates, do not translate easily to infinite or unknown data streams. Future research is needed to develop truly "anytime" learning rate schedules and to close the performance gap between continual and batch-trained models.
Summary updated