# A Randomized Mirror Descent Algorithm for Large Scale Multiple Kernel Learning

Arash Afkanpour, András György, Csaba Szepesvári, and Michael Bowling. A Randomized Mirror Descent Algorithm for Large Scale Multiple Kernel Learning. In Proceedings of the Thirtieth International Conference on Machine Learning (ICML), pp. 374–382, 2013.

## Abstract

We consider the problem of simultaneously learning to linearly combine a very large number of kernels and learn a good predictor based on the learnt kernel. When the number of kernels $d$ to be combined is very large, multiple kernel learning methods whose computational cost scales linearly in $d$ are intractable. We propose a randomized version of the mirror descent algorithm to overcome this issue, under the objective of minimizing the group $p$-norm penalized empirical risk. The key to achieve the required exponential speed-up is the computationally efficient construction of low-variance estimates of the gradient. We propose importance sampling based estimates, and find that the ideal distribution samples a coordinate with a probability proportional to the magnitude of the corresponding gradient. We show that in the case of learning the coefficients of a polynomial kernel, the combinatorial structure of the base kernels to be combined allows sampling from this distribution in $O(łog(d))$ time, making the total computational cost of the method to achieve an $\epsilon$-optimal solution to be $O(łog(d)/\epsilon^2)$, thereby allowing our method to operate for very large values of $d$. Experiments with simulated and real data confirm that the new algorithm is computationally more efficient than its state-of-the-art alternatives.

### BibTeX

@InProceedings(13icml-mkl,
Title = "A Randomized Mirror Descent Algorithm for Large Scale Multiple Kernel Learning",
Author = "Arash Afkanpour and Andr\'as Gy{\"o}rgy and Csaba Szepesv\'ari and Michael Bowling",
Booktitle = "Proceedings of the Thirtieth International Conference on Machine Learning (ICML)",
Pages = "374--382",
Year = "2013",
AcceptRate = "24\%",
AcceptNumbers = "283 of 1204"
)

Generated by bib2html.pl (written by Patrick Riley) on Fri Feb 13, 2015 15:54:26