Large-scale online kernel learning with random feature reparameterization

Tu Dinh Nguyen, Trung Le, Hung Bui, Dinh Phung

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

19 Citations (Scopus)

Abstract

A typical online kernel learning method faces two fundamental issues: the complexity in dealing with a huge number of observed data points (a.k.a the curse of kernelization) and the difficulty in learning kernel parameters, which often assumed to be fixed. Random Fourier feature is a recent and effective approach to address the former by approximating the shift-invariant kernel function via Bocher's theorem, and allows the model to be maintained directly in the random feature space with a fixed dimension, hence the model size remains constant w.r.t. data size. We further introduce in this paper the reparameterized random feature (RRF), a random feature framework for large-scale online kernel learning to address both aforementioned challenges. Our initial intuition comes from the so-called 'reparameterization trick' [Kingma and Welling, 2014] to lift the source of randomness of Fourier components to another space which can be independently sampled, so that stochastic gradient of the kernel parameters can be analytically derived. We develop a well-founded underlying theory for our method, including a general way to reparameterize the kernel, and a new tighter error bound on the approximation quality. This view further inspires a direct application of stochastic gradient descent for updating our model under an online learning setting. We then conducted extensive experiments on several large-scale datasets where we demonstrate that our work achieves state-of-the-art performance in both learning efficacy and efficiency.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)
EditorsCarles Sierra
Place of PublicationMarina del Rey CA USA
PublisherInternational Joint Conferences on Artificial Intelligence
Pages2543-2549
Number of pages7
ISBN (Electronic)9780999241103
ISBN (Print)9780999241110
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes
EventInternational Joint Conference on Artificial Intelligence 2017 - Melbourne, Australia
Duration: 19 Aug 201725 Aug 2017
Conference number: 26th
https://ijcai-17.org/
https://www.ijcai.org/Proceedings/2017/ (Proceedings)

Conference

ConferenceInternational Joint Conference on Artificial Intelligence 2017
Abbreviated titleIJCAI 2017
CountryAustralia
CityMelbourne
Period19/08/1725/08/17
Internet address

Cite this