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 architecture is built on three innovative pillars:
- 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.
- 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.
- 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.
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