  Traditional online continual learning (OCL) research has primarily focused on
mitigating catastrophic forgetting with fixed and limited storage allocation
throughout an agent's lifetime. However, a broad range of real-world
applications are primarily constrained by computational costs rather than
storage limitations. In this paper, we target such applications, investigating
the online continual learning problem under relaxed storage constraints and
limited computational budgets. We contribute a simple algorithm, which updates
a kNN classifier continually along with a fixed, pretrained feature extractor.
We selected this algorithm due to its exceptional suitability for online
continual learning. It can adapt to rapidly changing streams, has zero
stability gap, operates within tiny computational budgets, has low storage
requirements by only storing features, and has a consistency property: It never
forgets previously seen data. These attributes yield significant improvements,
allowing our proposed algorithm to outperform existing methods by over 20% in
accuracy on two large-scale OCL datasets: Continual LOCalization (CLOC) with
39M images and 712 classes and Continual Google Landmarks V2 (CGLM) with 580K
images and 10,788 classes, even when existing methods retain all previously
seen images. Furthermore, we achieve this superior performance with
considerably reduced computational and storage expenses. We provide code to
reproduce our results at github.com/drimpossible/ACM.
