Online Deep Learning: Learning Deep Neural Networks on the FlyDoyen Sahoo, Quang Pham, Jing Lu, Steven C.H. HoiSchool of Information Systems, Singapore Management Univeristy{doyens,hqpham,jing.lu.2014,chhoi}@smu.edu.sgAbstractDeep Neural Networks (DNNs) are typically trained by back-propagation in a batch learning setting, which requires theentire training data to be made available prior to the learn-ing task. This is not scalable for many real-world scenarioswhere new data arrives sequentially in a stream form. Weaim to address an open challenge of “Online Deep Learn-ing” (ODL) for learning DNNs on the f l y in an online setting.Unlike traditional online learning that often optimizes someconvex objective function with respect to a shallow model(e.g., a linear/kernel-based hypothesis), ODL is signif i cantlymore challenging since the optimization of the DNN ob-jective function is non-convex, and regular backpropagationdoes not work well in practice, especially for online learningsettings. In this paper, we present a new online deep learningframework that attempts to tackle the challenges by learningDNN models of adaptive depth from a sequence of trainingdata in an online learning setting. In particular, we propose anovel Hedge Backpropagation (HBP) method for online up-dating the parameters of DNN effectively, and validate the ef-f i cacy of our method on large-scale data sets, including bothstationary and concept drifting scenarios.IntroductionRecent years have witnessed tremendous success of deeplearning techniques in a wide range of applications (LeCun,Bengio, and Hinton 2015; Bengio, Courville, and Vincent2013; Bengio, Goodfellow, and Courville 2015; Krizhevsky,Sutskever, and Hinton 2012; He et al. 2016). Learning DeepNeural Networks (DNN) faces many challenges, including(but not limited to) vanishing gradient, diminishing fea-ture reuse (Srivastava, Greff, and Schmidhuber 2015), sad-dle points (and local minima) (Choromanska et al. 2015;Dauphin et al. 2014), immense number of parameters tobe tuned, internal covariate shift during training (Ioffe andSzegedy 2015), diff i culties in choosing a good regularizer,choosing hyperparameters, etc. Despite many promising ad-vances (Nair and Hinton 2010; Ioffe and Szegedy 2015;He et al. 2016; Srivastava, Greff, and Schmidhuber 2015),etc., which are designed to address specif i c problems for op-timizing deep neural networks, most of these existing ap-proaches assume that the DNN models are trained in a batchlearning setting which requires the entire training data set tobe made available prior to the learning task. This is not pos-sible for many real world tasks where data arrives sequen-tially in a stream, and may be too large to be stored in mem-ory. Moreover, the data may exhibit concept drift (Gama etal. 2014). Thus, a more desired option is to learn the modelsin an online setting.Unlike batch learning, online learning (Zinkevich 2003;Cesa-Bianchi and Lugosi 2006) represents a class of learn-ing algorithms that learn to optimize predictive models overa stream of data instances sequentially. The on-the-f l y learn-ing makes online learning highly scalable and memory ef-f i cient. However, most existing online learning algorithmsare designed to learn shallow models (e.g., linear or ker-nel methods (Crammer et al. 2006; Kivinen, Smola, andWilliamson 2004; Hoi et al. 2013)) with online convex op-timization, which cannot learn complex nonlinear functionsin complicated application scenarios.In this work, we attempt to bridge the gap between onlinelearning and deep learning by addressing the open problemof “Online Deep Learning” (ODL) — how to learn DeepNeural Networks (DNNs) from data streams in an onlinesetting. A possible way to do ODL is to put the process oftraining DNNs online by directly applying a standard Back-propagation training on only a single instance at each onlineround.Suchanapproachissimplebutfallsshortduetosomecritical limitations in practice. One key challenge is how tochoose a proper model capacity (e.g., depth of the network)before starting to learn the DNN online. If the model istoo complex (e.g., very deep networks), the learning processwill converge too slowly (vanishing gradient and diminish-ing feature reuse), thus losing the desired property of onlinelearning. On the other extreme, if the model is too simple,the learning capacity will be too restricted, and without thepower of depth, it would be diff i cult to learn complex pat-terns. In batch learning literature, a common way to addressthis issue is to do model selection on validation data. Unfor-tunately, it is not realistic to have validation data in onlinesettings, and is thus infeasible to apply traditional model se-lection in online learning scenarios. In this work, we presenta novel framework for online deep learning, which is able tolearn DNN models from data streams sequentially, and moreimportantly, is able to adapt its model capacity from simpleto complex over time, nicely combining the merits of bothonline learning and deep learning.
