We propose a fast algorithm for multiple kernel learning (MKL). More specifically, we use the matrix multiplicative weight update (MMWU) technique to solve the MKL problem formulated as a semi-definite program (SDP). Taking advantage of the structure of the MKL formulation, we considerably simplify the original problem which leads to an efficient algorithm. Our method avoids the use of commercial nonlinear solvers, and scales efficiently to much larger data sets than most prior methods can handle. Empirical evaluation on eleven datasets shows that we are significantly faster and even compare favorably with an uniform unweighted combination of kernels.

Our approach employs a geometric interpretation of the MWU method that might be of independent interest.