Online learning with kernels

By Jyrki Kivinen, Alex Smola, Robert C. Williamson. 2001

1,155 citations recorded by the source corpus.

Kernel-based algorithms such as support vector machines have achieved considerable success in various problems in batch setting, where all of the training data is available in advance. Support vector machines combine the so-called kernel trick with the large margin idea. There has been little use of these methods in an online setting suitable for real-time applications. In this paper, we consider online learning in a reproducing kernel Hilbert space. By considering classical stochastic gradient descent within a feature space and the use of some straightforward tricks, we develop simple and computationally efficient algorithms for a wide range of problems such as classification, regression, and novelty detection. In addition to allowing the exploitation of the kernel trick in an online setting, we examine the value of large margins for classification in the online setting with a drifting target. We derive worst-case loss bounds, and moreover, we show the convergence of the hypothesis to the minimizer of the regularized risk functional. We present some experimental results that support the theory as well as illustrating the power of the new algorithms for online novelty detection.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Task-Free Continual Learning (2018, background): “Online learning with kernels [14] extends this line of work to non-linear models, but the models remain shallow and their performance lags behind the modern deep neural networks.”
Scalable Kernel Methods via Doubly Stochastic Gradients (2014, methodology): “We will pick a few representative algorithms for comparison, namely, (i) NORMA [13]: kernel methods trained with stochastic functional gradients; (ii) k-SDCA [12]: kernelized version of stochastic dual coordinate ascend; (iii) r-SDCA: ﬁrst approximate the kernel function with random features, and th”
Large Scale Machine Learning (2004, background): “A study of stochastic gradient descent in the dual space has already been presented by Kivinen et al. (2002), who re-discovered gradient descent in the case of SVMs.”
Support vector machines (2008, positive): “Significant effort has been spent in the recent years on the development of online SVM learning algorithms (e.g. Rüping, 2002; Kivinen et al., 2001; Ralaivola and d’Alché Buc, 2001).”
Quantized Kernel Least Mean Square Algorithm (2012, methodology): “The online kernel learning (OKL) provides more efficient alternatives that approximate the desired nonlinearity incrementally, usually with gradient descent techniques [9].”
Large-scale Online Kernel Learning with Random Feature Reparameterization (2017, methodology): “It exceedingly attracts research and application interest (e.g., [Kivinen et al., 2004; Lu et al., 2015]) due to its seamless capacity in handling large stream of data.”
Online Kernel Principal Component Analysis: A Reduced-Order Model (2012, background): “Most of the work in that direction has been focused on classification and regression problems [19], [20], [21], [22], [23]; only a few attempts have been made for unsupervised learning.”
Change-Point Detection in Time-Series Data by Relative Density-Ratio Estimation (2012, background): “Recently, an online learning technique for kernel methods has been addressed [21].”
Fast Stochastic Frank-Wolfe Algorithms for Nonlinear SVMs (2010, methodology): “Stochastic programming techniques have shown to be very efficient for large-scale learning problems, both theoretically and empirically [16][17][18][19].”
Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison (2012, background): “Other approaches such as online learning [9] and budget learning [7] have also been developed for large-scale kernel learning, but they tend to yield performance worse performance than batch learning.”
Max-margin additive classifiers for detection (2009, methodology): “These fast evaluation strategies can accelerate standard SVM training as in [41] which uses our previous work [26] to speed up stochastic gradient descent based SVM training [23].”
Training Invariant Support Vector Machines using Selective Sampling (2005, background): “To address those limitations, there has been a lot of clever studies on solving quadratic optimization problems [7] [18], on online learning [4] [19] [11], on sparse solutions [39], and on active learning [9] [6].”
Continual Learning in Neural Networks (2019, background): “Online learning with kernels [70] extends this line of work to non-linear models, but the models remain shallow and their performance lags behind the modern deep neural networks.”
Online customization of teleoperation interfaces (2012, methodology): “1 We adopt the same principle, and use an extension to Online Learning with Kernel Machines [16] as the function approximator.”
On-line quantile regression in the RKHS (Reproducing Kernel Hilbert Space) for operational probabilistic forecasting of wind power (2016, methodology): “18 The developed algorithm is based on the stochastic descent gradient intro19 duced in [28], here generalised for the case of including a bias term.”
Recursive Aggregation of Estimators by the Mirror Descent Algorithm with Averaging (2005, neutral): “Recently, online analogues of SVM and boosting-type methods using convex losses have been proposed in [16, 38].”