A Local Online Learning Approach for Non-linear Data (SCW-LOL)

Abstract

Online learning is attractive for large‑scale real‑time data due to its efficiency and scalability. Most existing methods rely on a single global model and assume linear separability, which limits performance on non‑linear data. To address this, we propose SCW‑LOL, a local online learning algorithm that expands the Soft Confidence Weighted (SCW) classifier into multiple local SCW classifiers, forming a multi‑classifier model without kernel tricks.

Introduction

Online learning processes streaming instances one at a time, updating the model after each prediction, which reduces training cost and memory usage. Early algorithms such as Perceptron and Passive‑Aggressive are first‑order; later second‑order methods like Confidence Weighted (CW), AROW, and SCW improve performance by using covariance information. However, they still assume (near) linear separability. Kernel‑based online methods handle non‑linearity but are computationally expensive, while offline local classifiers avoid kernels but are not suited for online settings. SCW‑LOL combines the benefits of local classifiers with online learning.

Problem Analysis

The online learning process at time t receives a sample

and makes a prediction

. After receiving the true label (shown in the following image), the loss is computed

and used to update the model parameters, aiming to minimize the cumulative error.

Method

SCW‑LOL consists of a primary classifier with mean vector

and covariance matrix

. Each local sub‑classifier also has its own mean

and covariance

. The SCW objective is extended to multiple classifiers (see the formula image below).

For each incoming sample, an online K‑Means algorithm assigns it to the nearest local classifier based on its centroid

. The centroid is then updated:

The training and update procedures are illustrated in the following diagram:

Experimental Results

Performance is evaluated using cumulative error rate

and test error rate on ten datasets (five binary, five multi‑class). The results (shown in the three tables below) indicate that SCW‑LOL achieves the lowest error on most datasets, especially in multi‑class prediction.

Conclusion

SCW‑LOL solves the non‑linear data problem in online learning by maintaining both global and local models, assigning samples to appropriate local classifiers, and leveraging second‑order information for higher accuracy. Theoretical analysis shows its loss bound does not exceed that of SCW, guaranteeing convergence. Experiments confirm its outstanding performance on streaming data, particularly for multi‑class tasks.