A randomized mirror descent algorithm for large scale multiple kernel learning
- Arash Afkanpour
- Andras Gyorgy
- Csaba Szepesvari, Department of Computing Science; PI of AICML
- Michael Bowling, University of Alberta
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(log(d)) time, making the total computational cost of the method to achieve an epsilon-optimal solution to be O(log(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.
Citation
A. Afkanpour, A. Gyorgy, C. Szepesvari, M. Bowling. "A randomized mirror descent algorithm for large scale multiple kernel learning". International Conference on Machine Learning (ICML), pp 374–382, June 2013.| Keywords: | |
| Category: | In Conference |
| Web Links: | PMLR |
BibTeX
@incollection{Afkanpour+al:ICML13,
author = {Arash Afkanpour and Andras Gyorgy and Csaba Szepesvari and Michael
Bowling},
title = {A randomized mirror descent algorithm for large scale multiple
kernel learning},
Pages = {374–382},
booktitle = {International Conference on Machine Learning (ICML)},
year = 2013,
}Last Updated: October 29, 2020Submitted by Sabina P
