Fast Second-Order Online Kernel Learning Through Incremental Matrix Sketching and Decomposition

Dongxie Wen, Xiao Zhang, Zhewei Wei, Chenping Hou, Shuai Li, Weinan Zhang

Introduction

Online learning requires models to update continuously as new data arrives. Online Kernel Learning (OKL) is a popular approach for capturing non-linear patterns by mapping data into high-dimensional feature spaces. However, traditional second-order OKL methods—which utilize curvature information for faster convergence—suffer from the "curse of dimensionality." These methods typically scale quadratically with the number of samples ($O(t^2)$) or the memory budget ($O(B^2)$), making them impractical for large-scale streaming applications. Additionally, maintaining an explicit feature mapping often requires computationally expensive Singular Value Decomposition (SVD) at each step.

The FORKS Framework

To address these scalability issues, researchers introduced FORKS (Fast Second-Order Online Kernel Learning Using Incremental Sketching). The algorithm achieves logarithmic regret—the theoretical gold standard—while maintaining linear time complexity relative to the memory budget.

The FORKS framework architecture.

The FORKS architecture is built on three innovative pillars:

  1. Incremental Matrix Sketching: Instead of storing the entire kernel matrix, FORKS maintains a compact approximation using randomized sketching techniques like the Sparse Johnson-Lindenstrauss Transform.
  2. Truncated Incremental SVD (TISVD): This novel update mechanism allows the model to update singular vectors and values using low-rank modifications rather than recomputing SVD from scratch. This reduces complexity from $O(s_p^3)$ to $O(s_pk + k^3)$, where $s_p$ is the sketch size and $k$ is the rank.
  3. Two-Stage Learning with Resets: The algorithm initially uses a first-order method to populate a buffer before switching to second-order updates. Periodic "resets" of the Hessian matrix prevent the model from becoming stagnant or being misled by adversarial concept drift.

Experimental Evaluation

The authors evaluated FORKS against several state-of-the-art methods, including BOGD, NOGD, and PROS-N-KONS, across standard and adversarial benchmarks.

Performance trade-off between running time and mistake rate for various OKL methods.

Efficiency and Accuracy

FORKS demonstrates a significant leap in efficiency. On the codrna dataset, it achieved a 125x speedup over PROS-N-KONS while maintaining a lower mistake rate. As shown in the performance trade-off plots, FORKS consistently occupies the "sweet spot" of low running time and low mistake rates compared to both first-order and second-order competitors.

Robustness and Scalability

In adversarial settings where labels were flipped to simulate attacks, FORKS maintained a mistake rate of approximately 6.7%, whereas competing methods saw spikes up to 29%. On the large-scale KuaiRec dataset (4.5 million instances), FORKS provided a 3x speedup over other methods for the same accuracy level, proving its readiness for real-world production environments.

Conclusion

FORKS successfully bridges the gap between the high predictive power of second-order kernel methods and the efficiency requirements of big data streams. By replacing quadratic bottlenecks with linear-time incremental updates, it provides a robust, scalable solution for non-linear online learning. Future work may extend the TISVD approach to multi-kernel learning and online clustering.

Summary updated

Abstract

Second-order Online Kernel Learning (OKL) has attracted considerable research interest due to its promising predictive performance in streaming environments. However, existing second-order OKL approaches suffer from at least quadratic time complexity with respect to the pre-set budget, rendering them unsuitable for large-scale datasets. Moreover, the singular value decomposition required to obtain explicit feature mapping is computationally expensive due to the complete decomposition process. To address these issues, we propose FORKS, a fast incremental matrix sketching and decomposition approach tailored for second-order OKL. FORKS constructs an incremental maintenance paradigm for second-order kernelized gradient descent, which includes incremental matrix sketching for kernel approximation and incremental matrix decomposition for explicit feature mapping construction. Theoretical analysis demonstrates that FORKS achieves a logarithmic regret guarantee on par with other second-order approaches while maintaining a linear time complexity w.r.t. the budget, significantly enhancing efficiency over existing methods. We validate the performance of our method through extensive experiments conducted on real-world datasets, demonstrating its superior scalability and robustness against adversarial attacks.
BibTeX
@inproceedings{wen2025fast,
  author = {Dongxie Wen and Xiao Zhang and Zhewei Wei and Chenping Hou and Shuai Li and Weinan Zhang},
  title = {{Fast Second-Order Online Kernel Learning Through Incremental Matrix Sketching and Decomposition}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/729},
}
Figure