We consider the problem of learning a predictor by combining possibly infinitely many linear predictors whose weights are to be learned, too, an instance of multiple kernel learning. To control overfitting a group p-norm penalty is used to penalize the empirical loss. We consider a reformulation of the problem that lets us implement a randomized version of the proximal point algorithm. The key idea of the new algorithm is to use randomized computation to alleviate the problem of dealing with possibly uncountably many predictors. Finite-time performance bounds are derived that show that under mild conditions the method finds the optimum of the penalized criterion in an efficient manner. Experimental results confirm the effectiveness of the new algorithm.

研究了学习如何线性组合多个核的问题，并基于学习的核来学习一个好的预测器；针对多个核的组合，提出了一种随机化的镜像下降算法，利用低方差估计梯度，通过重要性采样估计，发现数据分布之间的关系，对于一个特定的核的情况，可以采样而不必重复观察，并提出多项式核系数的学习方法的组合结构可以在O(log(d))的时间内实现采样，从而使得该方法可以用于非常大的d；实验证明，该算法比最先进的算法具有更高的计算效率。

大规模多核学习的随机镜像下降算法