An Extended Level Method for Efficient Multiple Kernel Learning

The extended level method is extended, which was originally designed for optimizing non-smooth objective functions, to convex-concave optimization, and applies it to multiple kernel learning, and overcomes the drawbacks of SILP and SD.

Abstract

We consider the problem of multiple kernel learning (MKL), which can be for-mulated as a convex-concave problem. In the past, two efficient methods, i.e., Semi-Infinite Linear Programming (SILP) and Subgradient Descent (SD), have been proposed for large-scale multiple kernel learning. Despite their success, both methods have their own shortcomings: (a) the SD method utilizes the gradient of only the current solution, and (b) the SILP method does not regularize the approx-imate solution obtained from the cutting plane model. In this work, we extend the level method, which was originally designed for optimizing non-smooth ob-jective functions, to convex-concave optimization, and apply it to multiple kernel learning. The extended level method overcomes the drawbacks of SILP and SD by exploiting all the gradients computed in past iterations and by regularizing the solution via a projection to a level set. Empirical study with eight UCI datasets shows that the extended level method can significantly improve efficiency by sav-ing on average 91.9 % of computational time over the SILP method and 70.3% over the SD method. 1