This work proposes a multiple kernel learning (MKL) descent strategy based on multiple epochs of stochastic variance reduced gradients (i.e. multi-epochs SVRG). The proposed descent strategy takes place with a constant-size learning step, that is entangled to the kernel's combination coefficients evolution, and hence corrected in between epochs. This descending regime leads to an improved MKL bound that exhibit a linear dependency in the number of samples n, and sub-linear one in both the number of kernels F and precision of the solution e. In particular, for an Lp-norm MKL, the proposed method is able to find an e-accurate solution in a complexity O( F\textasciicircum{}(1/q) n log(1/e)). This matches the optimal convergence rate reported for (non-accelerated) strongly-convex objectives and improves over other state-of-the-art MKL solutions.
Alioscha-Perez, M, Oveneke, MC, Jiang, D & Sahli, H 2016, Multiple Kernel Learning via Multi-Epochs SVRG. in 9th NIPS Workshop on Optimization for Machine Learning. vol. 12, 34. <http://www.opt-ml.org/papers/OPT2016_paper_34.pdf>
Alioscha-Perez, M., Oveneke, M. C., Jiang, D., & Sahli, H. (2016). Multiple Kernel Learning via Multi-Epochs SVRG. In 9th NIPS Workshop on Optimization for Machine Learning (Vol. 12). Article 34 http://www.opt-ml.org/papers/OPT2016_paper_34.pdf
@inproceedings{34faecf6cd254b788432589acd4118b8,
title = "Multiple Kernel Learning via Multi-Epochs SVRG",
abstract = "This work proposes a multiple kernel learning (MKL) descent strategy based on multiple epochs of stochastic variance reduced gradients (i.e. multi-epochs SVRG). The proposed descent strategy takes place with a constant-size learning step, that is entangled to the kernel's combination coefficients evolution, and hence corrected in between epochs. This descending regime leads to an improved MKL bound that exhibit a linear dependency in the number of samples n, and sub-linear one in both the number of kernels F and precision of the solution e. In particular, for an Lp-norm MKL, the proposed method is able to find an e-accurate solution in a complexity O( F\textasciicircum{}(1/q) n log(1/e)). This matches the optimal convergence rate reported for (non-accelerated) strongly-convex objectives and improves over other state-of-the-art MKL solutions.",
author = "Mitchel Alioscha-Perez and Oveneke, \{Meshia C{\'e}dric\} and Dongmei Jiang and Hichem Sahli",
year = "2016",
month = dec,
language = "English",
volume = "12",
booktitle = "9th NIPS Workshop on Optimization for Machine Learning",
}