Scalable Kernel Methods via Doubly Stochastic Gradients
Scalable Kernel Methods via Doubly Stochastic Gradients
复制标题
DOI：
--
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Bo Dai;Bo Xie;Niao He;Yingyu Liang;Anant Raj;Maria-Florina Balcan;Le Song
中科院分区：
文献类型：
--
作者：
Bo Dai;Bo Xie;Niao He;Yingyu Liang;Anant Raj;Maria-Florina Balcan;Le Song
一般的看法是，核方法是不可扩展的，所以神经网络成为大规模非线性学习问题的选择。我们是否已经为内核方法做了足够的努力？在本文中，我们提出了一种方法，扩大核方法使用一种新的概念，称为“双随机功能梯度”。基于这一事实，许多核方法可以表示为凸优化问题，我们的方法解决了优化问题，使两个无偏随机近似的功能梯度-一个使用随机训练点，另一个使用随机功能与内核-和执行下降步骤与此嘈杂的功能梯度。我们的算法很简单，不需要提交预设数量的随机特征，并且允许函数类的灵活性随着我们在流设置中看到更多的传入数据而增长。我们证明了通过这种方法学习的函数在t次迭代后以O（1/t）的速度收敛到再生核Hilbert空间中的最优函数，并达到O（1/t）的推广界。我们的方法可以很容易地扩展核方法的制度，这是由神经网络占主导地位。与神经网络相比，我们的方法在数据集中表现出了竞争力，例如来自MolecularSpace的230万种能量材料，来自MNIST的800万个手写数字，以及来自ImageNet的100万张照片。
The general perception is that kernel methods are not scalable, so neural nets become the choice for large-scale nonlinear learning problems. Have we tried hard enough for kernel methods? In this paper, we propose an approach that scales up kernel methods using a novel concept called "doubly stochastic functional gradients". Based on the fact that many kernel methods can be expressed as convex optimization problems, our approach solves the optimization problems by making two unbiased stochastic approximations to the functional gradient—one using random training points and another using random features associated with the kernel—and performing descent steps with this noisy functional gradient. Our algorithm is simple, need no commit to a preset number of random features, and allows the flexibility of the function class to grow as we see more incoming data in the streaming setting. We demonstrate that a function learned by this procedure after t iterations converges to the optimal function in the reproducing kernel Hilbert space in rate O(1/t), and achieves a generalization bound of O(1/√t). Our approach can readily scale kernel methods up to the regimes which are dominated by neural nets. We show competitive performances of our approach as compared to neural nets in datasets such as 2.3 million energy materials from MolecularSpace, 8 million handwritten digits from MNIST, and 1 million photos from ImageNet using convolution features.