Fast Second-Order Online Kernel Learning Through Incremental Matrix Sketching and Decomposition
Lists
Only you see this
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},
}Loading related content...