Learning under feature evolution data streams has attracted widespread attention in recent years. Existing methods usually assume that the model predicts and learns from all instances in the data stream. However, when the data stream rate is faster than the model update rate, the model can only learn from some instances. Therefore, this assumption may not always hold in practical scenarios. Additionally, existing methods often update based only on the current instance, ignoring the impact of data stream changes, which further limits their application in practical data streams. This paper proposes a novel learning paradigm to solve this problem: Online Learning under Feature Evolution data streams with A Fast Rate, called OLFE-FR. Specifically, OLFE-FR introduces the concept of relative rate to adaptively determine the prediction mode and update node of the model in the data stream. Additionally, OLFE-FR proposes an adaptive learning rate adjustment strategy based on the upper bound of dynamic regret minimization. This strategy enables the model to find a suitable learning rate based on weights change induced by known data stream variations before using the instance update. Theoretical analysis and experimental results show that OLFE-FR can effectively handle feature evolution data streams with a fast rate.

Many real-world streaming data are sequentially collected over time and with skew-distributed classes. In this situation, online learning models may tend to favor samples from majority classes, making the wrong decisions for those from minority classes. Previous methods try to balance the instance number of different classes or assign asymmetric cost values. They usually require data-buffers to store streaming data or pre-defined cost parameters. This study alternatively shows that the imbalance of instances can be implied by the imbalance of gradients. Then, we propose the Online Harmonizing Gradient Descent (OHGD) for one-pass online classification. By harmonizing the gradient magnitude occurred by different classes, the method avoids the bias of the proposed method in favor of the majority class. Specifically, OHGD requires no data-buffer, extra parameters, or prior knowledge. It also handles imbalanced data streams the same way that it would handle balanced data streams, which facilitates its easy implementation. On top of a few common and mild assumptions, the theoretical analysis proves that OHGD enjoys a satisfying sub-linear regret bound. Extensive experimental results demonstrate the high efficiency and effectiveness in handling imbalanced data streams.