---
title: "Fast Second-Order Online Kernel Learning Through Incremental Matrix Sketching and Decomposition"
authors:
  - "Dongxie Wen"
  - "Xiao Zhang"
  - "Zhewei Wei"
  - "Chenping Hou"
  - "Shuai Li"
  - "Weinan Zhang"
doi: "10.24963/ijcai.2025/729"
url: "https://ijcai.org/proceedings/2025/729"
pdf: "https://ijcai.org/proceedings/2025/0729.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "6552-6560"
track: "Main Track"
keywords:
  - "Machine Learning: ML: Online learning"
  - "Machine Learning: ML: Incremental learning"
  - "Machine Learning: ML: Kernel methods"
---

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

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

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 6552-6560. DOI: [10.24963/ijcai.2025/729](https://doi.org/10.24963/ijcai.2025/729)

## 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.