Learning Additive Models Online with Fast Evaluating Kernels
We develop three new techniques to build on the recent advances in online learning with kernels. First,w e show that an exponential speed-up in prediction time per trial is possible for such algorithms as the Kernel-Adatron,the Kernel-Perceptron,and ROMMA for specific additive models. Second,w e show that the techniques of the recent algorithms developed for online linear prediction when the best predictor changes over time may be implemented for kernel-based learners at no additional asymptotic cost. Finally,w e introduce a new online kernel-based learning algorithm for which we give worst-case loss bounds for the Ɛ-insensitive square loss.