Timezone: »
In this paper we consider the problem of learning an n x n Kernel matrix from m similarity matrices under general convex loss. Past research have extensively studied the m =1 case and have derived several algorithms which require sophisticated techniques like ACCP, SOCP, etc. The existing algorithms do not apply if one uses arbitrary losses and often can not handle m > 1 case. We present several provably convergent iterative algorithms, where each iteration requires either an SVM or a Multiple Kernel Learning (MKL) solver for m > 1 case. One of the major contributions of the paper is to extend the well known Mirror Descent(MD) framework to handle Cartesian product of psd matrices. This novel extension leads to an algorithm, called EMKL, which solves the problem in O(m^2 log n) iterations; in each iteration one solves an MKL involving m kernels and m eigendecomposition of n x n matrices. By suitably defining a restriction on the objective function, a faster version of EMKL is proposed, called REKL, which avoids the eigendecomposition. An alternative to both EMKL and REKL is also suggested which requires only an SVM solver. Experimental results on real world protein data set involving several similarity matrices illustrate the efficacy of the proposed algorithms.
Author Information
Achintya Kundu (Indian Institute of Science)
Vikram Mukunda Rao Tankasali (Google Deepmind)
Chiranjib Bhattacharyya (Indian Institute of Science)
Aharon BenTal
More from the Same Authors

2015 Poster: Weighted Theta Functions and Embeddings with Applications to MaxCut, Clustering and Summarization »
Fredrik D Johansson · Ankani Chattoraj · Chiranjib Bhattacharyya · Devdatt Dubhashi 
2015 Poster: Spectral Norm Regularization of Orthonormal Representations for Graph Transduction »
Rakesh Shivanna · Bibaswan K Chatterjee · Raman Sankaran · Chiranjib Bhattacharyya · Francis Bach 
2014 Poster: Learning on graphs using Orthonormal Representation is Statistically Consistent »
Rakesh Shivanna · Chiranjib Bhattacharyya 
2014 Poster: A provable SVDbased algorithm for learning topics in dominant admixture corpus »
Trapit Bansal · Chiranjib Bhattacharyya · Ravindran Kannan 
2012 Poster: The Lovasz $\theta$ function, SVMs and finding large dense subgraphs »
Vinay Jethava · Anders Martinsson · Chiranjib Bhattacharyya · Devdatt Dubhashi 
2009 Poster: On the Algorithmics and Applications of a Mixednorm based Kernel Learning Formulation »
Saketha Nath Jagarlapudi · dinesh govindaraj · Raman S · Chiranjib Bhattacharyya · Aharon BenTal · K. R. Ramakrishnan 
2007 Poster: Kernels on Attributed Pointsets with Applications »
Mehul Parsana · Sourangshu Bhattacharya · Chiranjib Bhattacharyya · K. R. Ramakrishnan 
2007 Poster: A Randomized Algorithm for Large Scale Support Vector Learning »
Krishnan S Kumar · Chiranjib Bhattacharyya · Ramesh Hariharan