Implicit Online Learning with Kernels

TitleImplicit Online Learning with Kernels
Publication TypeJournal Article
Year of Publication2007
AuthorsL. Cheng, S. Vishwanathan, D. Schuurmans, Shaojun Wang, Terry Caelli

We present two new algorithms for online learning in reproducing kernel Hilbert spaces. Our first algorithm, ILK (implicit online learning with kernels), employs a new, implicit update technique that can be applied to a wide variety of convex loss functions. We then introduce a bounded memory version, SILK (sparse ILK), that maintains a compact representation of the predictor without compromising solution quality, even in non-stationary environments. We prove loss bounds and analyze the convergence rate of both. Experimental evidence shows that our proposed algorithms outperform current methods on synthetic and real data.

Full Text

L. Cheng, S. Vishwanathan, D. Schuurmans, S. Wang and T, Caelli, "Implicit Online Learning with Kernels," Advances in Neural Information Processing (NIPS), 249-256, 2007.