Adapting to Online Distribution Shifts in Deep Learning: A Black-Box Approach

Dheeraj Baby, Boran Han, Shuai Zhang, Cuixiong Hu, Yuyang Wang, Yu-Xiang Wang

Abstract

We address the challenge of online distribution shift, where data arrives in batches and the underlying distribution changes arbitrarily over time. Traditional deep learning models struggle with a "Goldilocks" dilemma: using too much historical data leads to sluggish adaptation, while using too little results in poor statistical power. We propose Accuracy Weighted Ensemble (AWE), a meta-algorithm that adaptively selects the optimal "attention span" for any given network architecture. By maintaining a logarithmic number of Online Learner (OL) instances and employing a novel cross-validation-through-time technique, AWE provides a computationally efficient, black-box solution for non-stationary environments. Experiments on real-world datasets across text and image modalities demonstrate that AWE consistently improves the performance of various base learners.

1. Introduction

In real-world applications, such as news classification or satellite imagery analysis, data distributions are rarely static. This phenomenon, known as online distribution shift or non-stationarity, poses a significant hurdle for deep learning models. A model trained on 2010 data may fail to generalize to 2024 due to evolving vocabularies and shifting contexts.

To maintain accuracy, a learner must decide how much historical data to incorporate. If the shift is abrupt, the model should focus on the most recent samples; if the shift is gradual or the data is noisy, a longer historical window is preferable. Most existing solutions rely on convexity assumptions that do not apply to deep neural networks or are too computationally intensive for high-speed streams. We introduce AWE, a meta-algorithm designed to work with any neural network architecture as a "black box," automatically adapting its historical window to maximize performance.

2. The AWE Meta-Algorithm

AWE relies on two primary algorithmic innovations to balance efficiency with adaptability: Multi-Resolution Instances (MRI) and Cross-Validation-Through-Time (CVTT).

2.1 Multi-Resolution Instances (MRI)

Instead of maintaining a single model or an exhaustive set of models for every possible window size, AWE maintains a pool of $O(\log T)$ Online Learner instances. This design is inspired by wavelet theory, ensuring that at any timestamp $T$, there is at least one instance in the pool that has been trained on a window of data that is "just right"—specifically, an instance that has seen at least 25% of the data from the current distribution. This logarithmic scaling keeps the computational and memory overhead manageable for real-time deployment.

2.2 Cross-Validation-Through-Time (CVTT)

To determine which instance in the pool is currently the most reliable, AWE uses a small portion of each data batch as a hold-out validation set. However, a single batch is often too small to provide a stable performance estimate. CVTT addresses this by pooling validation data from adjacent timestamps where the distribution appears stable. This provides a high-confidence estimate of each model's current accuracy, allowing AWE to pivot quickly to the best-performing instance when a shift is detected.

3. Experimental Evaluation

We evaluated AWE using the WildTime benchmark, which focuses on real-world distribution shifts over time. The datasets included:

  • FMOW (Functional Map of the World): Satellite imagery for land-use classification over several years.
  • Huffpost: News category classification based on headlines and descriptions.
  • Arxiv: Classification of research paper abstracts into subject categories.

AWE was tested as a wrapper for five different base learners, including Synaptic Intelligence (SI), Invariant Risk Minimization (IRM), and CORAL. This allowed us to test its effectiveness as a general-purpose meta-algorithm.

4. Results and Discussion

Our experiments yielded several key insights into the efficacy of AWE:

  • Consistent Performance Gains: AWE improved the accuracy of every base learner tested. For instance, when applied to the CORAL algorithm on the FMOW dataset, AWE increased average classification accuracy by 3.24%.
  • Superiority Over Existing Baselines: AWE significantly outperformed SAOL, a previous state-of-the-art black-box adaptation method. While SAOL occasionally degraded the performance of deep learning models, AWE consistently provided improvements or maintained baseline performance.
  • Reliability: In the FMOW dataset, AWE improved or maintained performance in 100% of the tested timestamps for the majority of base learners, demonstrating its robustness against both sudden and gradual shifts.
  • Efficiency: Despite running multiple instances, the $O(\log T)$ design ensures that the system remains practical for real-world applications where memory and processing time are constrained.

5. Conclusion and Limitations

AWE provides a versatile, efficient framework for adapting deep learning models to non-stationary data streams. By treating the underlying learner as a black box, it bypasses the theoretical constraints of previous methods and offers immediate utility for modern neural architectures.

However, some limitations remain. AWE requires storing hold-out data for cross-validation, which may be a concern in extremely memory-constrained or privacy-sensitive environments. Additionally, the current framework assumes the availability of true labels for every batch and focuses on instantaneous accuracy rather than long-term "backward transfer" (remembering older distributions). Future work will explore these settings, including limited feedback (bandit) scenarios and privacy-preserving adaptation.

Summary updated

Abstract

We study the well-motivated problem of online distribution shift in which the data arrive in batches and the distribution of each batch can change arbitrarily over time. Since the shifts can be large or small, abrupt or gradual, the length of the relevant historical data to learn from may vary over time, which poses a major challenge in designing algorithms that can automatically adapt to the best ``attention span'' while remaining computationally efficient. We propose a meta-algorithm that takes any network architecture and any Online Learner (OL) algorithm as input and produces a new algorithm which provably enhances the performance of the given OL under non-stationarity. Our algorithm is efficient (it requires maintaining only $O(\log(T))$ OL instances) and adaptive (it automatically chooses OL instances with the ideal ``attention'' length at every timestamp). Experiments on various real-world datasets across text and image modalities show that our method consistently improves the accuracy of user specified OL algorithms for classification tasks. Key novel algorithmic ingredients include a \emph{multi-resolution instance} design inspired by wavelet theory and a cross-validation-through-time technique. Both could be of independent interest.
BibTeX
@inproceedings{baby2025adapting,
  author = {Dheeraj Baby and Boran Han and Shuai Zhang and Cuixiong Hu and Yuyang Wang and Yu-Xiang Wang},
  title = {{Adapting to Online Distribution Shifts in Deep Learning: A Black-Box Approach}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=Jfc4iqIiHt},
}
Figure