Learning under concept drift with follow the regularized leader and adaptive decaying proximal

Propose a new adaptive learning algorithm to address the problem of concept drift.Use a decaying factor to discount previous learning examples.Use a concept drift detector to reset the learning process upon major concept drift.The proposed algorithm was theoretically proved to have sublinear regret bound. Concept drift is the problem that the statistical properties of the data generating process change over time. Recently, the Time Decaying Adaptive Prediction (TDAP) algorithm11Scalable Time-Decaying Adaptive Prediction Algorithm. (Tan etal., 2016). was proposed to address the problem of concept drift. TDAP was designed to account for the effect of drifting concepts by discounting the contribution of previous learning examples using an exponentially decaying factor. The drawback of TDAP is that the rate of its decaying factor is required to be manually tuned. To address this drawback, we propose a new adaptive online algorithm, called Follow-the-Regularized-Leader with Adaptive Decaying Proximal (FTRL-ADP). There are two novelties in our approach. First, we derive a rule to automatically update the decaying rate, based on a rigorous theoretical analysis. Second, we use a concept drift detector to identify major drifts and reset the update rule accordingly. Comparative experiments with 14 datasets and 6 other online algorithms show that FTRL-ADP is most advantageous in noisy environments with real drifts.