Timezone: »
Spotlight
Multiple Kernel Learning and the SMO Algorithm
S.V.N. Vishwanathan · Zhaonan sun · Nawanol T Ampornpunt · Manik Varma
Our objective is to train $p$-norm Multiple Kernel Learning (MKL) and,
more generally, linear MKL regularised by the Bregman divergence,
using the Sequential Minimal Optimization (SMO) algorithm. The SMO
algorithm is simple, easy to implement and adapt, and efficiently
scales to large problems. As a result, it has gained widespread
acceptance and SVMs are routinely trained using SMO in diverse real
world applications. Training using SMO has been a long standing goal
in MKL for the very same reasons. Unfortunately, the standard MKL dual
is not differentiable, and therefore can not be optimised using SMO
style co-ordinate ascent. In this paper, we demonstrate that linear
MKL regularised with the $p$-norm squared, or with certain Bregman
divergences, can indeed be trained using SMO. The resulting algorithm
retains both simplicity and efficiency and is significantly faster
than the state-of-the-art specialised $p$-norm MKL solvers. We show
that we can train on a hundred thousand kernels in approximately seven
minutes and on fifty thousand points in less than half an hour on a
single core.
more generally, linear MKL regularised by the Bregman divergence,
using the Sequential Minimal Optimization (SMO) algorithm. The SMO
algorithm is simple, easy to implement and adapt, and efficiently
scales to large problems. As a result, it has gained widespread
acceptance and SVMs are routinely trained using SMO in diverse real
world applications. Training using SMO has been a long standing goal
in MKL for the very same reasons. Unfortunately, the standard MKL dual
is not differentiable, and therefore can not be optimised using SMO
style co-ordinate ascent. In this paper, we demonstrate that linear
MKL regularised with the $p$-norm squared, or with certain Bregman
divergences, can indeed be trained using SMO. The resulting algorithm
retains both simplicity and efficiency and is significantly faster
than the state-of-the-art specialised $p$-norm MKL solvers. We show
that we can train on a hundred thousand kernels in approximately seven
minutes and on fifty thousand points in less than half an hour on a
single core.
Author Information
S.V.N. Vishwanathan (UCSC)
Zhaonan sun (Purdue University)
Nawanol T Ampornpunt (Purdue University)
Manik Varma (Microsoft Research India)
Related Events (a corresponding poster, oral, or spotlight)
-
2010 Poster: Multiple Kernel Learning and the SMO Algorithm »
Tue. Dec 7th 08:00 -- 08:00 AM Room
More from the Same Authors
-
2020 Poster: RNNPool: Efficient Non-linear Pooling for RAM Constrained Inference »
Oindrila Saha · Aditya Kusupati · Harsha Vardhan Simhadri · Manik Varma · Prateek Jain -
2020 Spotlight: RNNPool: Efficient Non-linear Pooling for RAM Constrained Inference »
Oindrila Saha · Aditya Kusupati · Harsha Vardhan Simhadri · Manik Varma · Prateek Jain -
2018 Poster: FastGRNN: A Fast, Accurate, Stable and Tiny Kilobyte Sized Gated Recurrent Neural Network »
Aditya Kusupati · Manish Singh · Kush Bhatia · Ashish Kumar · Prateek Jain · Manik Varma -
2017 : Introduction by Manik Varma »
Manik Varma -
2017 Workshop: Extreme Classification: Multi-class & Multi-label Learning in Extremely Large Label Spaces »
Manik Varma · Marius Kloft · Krzysztof Dembczynski -
2016 Workshop: Extreme Classification: Multi-class and Multi-label Learning in Extremely Large Label Spaces »
Moustapha Cisse · Manik Varma · Samy Bengio -
2015 Workshop: Extreme Classification 2015: Multi-class and Multi-label Learning in Extremely Large Label Spaces »
Manik Varma · Moustapha M Cisse -
2015 Poster: Sparse Local Embeddings for Extreme Multi-label Classification »
Kush Bhatia · Himanshu Jain · Purushottam Kar · Manik Varma · Prateek Jain -
2015 Poster: A Structural Smoothing Framework For Robust Graph Comparison »
Pinar Yanardag · S.V.N. Vishwanathan -
2013 Workshop: Extreme Classification: Multi-Class & Multi-Label Learning with Millions of Categories »
Manik Varma · John Langford -
2011 Poster: t-divergence Based Approximate Inference »
Nan Ding · S.V.N. Vishwanathan · Yuan Qi -
2010 Poster: t-logistic regression »
Nan Ding · S.V.N. Vishwanathan -
2010 Poster: Lower Bounds on Rate of Convergence of Cutting Plane Methods »
Xinhua Zhang · Ankan Saha · S.V.N. Vishwanathan -
2010 Poster: Multitask Learning without Label Correspondences »
Novi Quadrianto · Alexander Smola · Tiberio Caetano · S.V.N. Vishwanathan · James Petterson