  Online deep learning solves the problem of learning from streams of data,
reconciling two opposing objectives: learn fast and learn deep. Existing work
focuses almost exclusively on exploring pure deep learning solutions, which are
much better suited to handle the "deep" than the "fast" part of the online
learning equation. In our work, we propose a different paradigm, based on a
hybrid multilearner approach. First, we develop a fast online logistic
regression learner. This learner does not rely on backpropagation. Instead, it
uses closed form recursive updates of model parameters, handling the fast
learning part of the online learning problem. We then analyze the existing
online deep learning theory and show that the widespread ODL approach,
currently operating at complexity $O(L^2)$ in terms of the number of layers
$L$, can be equivalently implemented in $O(L)$ complexity. This further leads
us to the cascaded multilearner design, in which multiple shallow and deep
learners are co-trained to solve the online learning problem in a cooperative,
synergistic fashion. We show that this approach achieves state-of-the-art
results on common online learning datasets, while also being able to handle
missing features gracefully. Our code is publicly available at
https://github.com/AntonValk/MODL.
