Diving into the shallows: a computational perspective on large-scale shallow learning
Diving into the shallows: a computational perspective on large-scale shallow learning
复制标题
DOI：
--
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Siyuan Ma;M. Belkin
中科院分区：
文献类型：
--
作者：
Siyuan Ma;M. Belkin
在本文中，我们首先确定了基于梯度下降的优化方法与平滑核结合使用时的基本限制。基于核的谱特性的分析表明，经过多项式梯度下降迭代后，只能达到函数空间的一小部分。这种近似功效的缺乏极大地限制了固定计算预算的梯度下降，导致严重的过度正则化/欠拟合。这个问题纯粹是算法问题，即使在无限数据的限制下也仍然存在。为了解决实践中的这一缺点，我们引入了 EigenPro 迭代，该迭代基于使用少量近似计算的特征向量的预处理方案。它也可以被视为学习针对梯度下降优化的新内核。事实证明，注入少量（计算成本低廉且与 SGD 兼容）的近似二阶信息可以带来收敛方面的重大改进。对于大数据，这意味着比标准内核方法的性能显着提升。特别是，我们能够用其计算预算的一小部分来持续匹配或改进文献中最近报告的最先进的结果。最后，我们认为这些结果表明现代大规模学习需要更广泛的计算视角，以补充更传统的统计和收敛分析。特别是，大规模高维推理的许多现象可以通过无限维希尔伯特空间的优化来最好地理解，其中标准算法有时可能具有与有限维直觉不一致的属性。专注于此类算法在计算预算内的近似能力的系统分析可能会带来理论和实践的进步。
In this paper we first identify a basic limitation in gradient descent-based optimization methods when used in conjunctions with smooth kernels. An analysis based on the spectral properties of the kernel demonstrates that only a vanishingly small portion of the function space is reachable after a polynomial number of gradient descent iterations. This lack of approximating power drastically limits gradient descent for a fixed computational budget leading to serious over-regularization/underfitting. The issue is purely algorithmic, persisting even in the limit of infinite data. To address this shortcoming in practice, we introduce EigenPro iteration, based on a preconditioning scheme using a small number of approximately computed eigenvectors. It can also be viewed as learning a new kernel optimized for gradient descent. It turns out that injecting this small (computationally inexpensive and SGD-compatible) amount of approximate second-order information leads to major improvements in convergence. For large data, this translates into significant performance boost over the standard kernel methods. In particular, we are able to consistently match or improve the state-of-the-art results recently reported in the literature with a small fraction of their computational budget. Finally, we feel that these results show a need for a broader computational perspective on modern large-scale learning to complement more traditional statistical and convergence analyses. In particular, many phenomena of large-scale high-dimensional inference are best understood in terms of optimization on infinite dimensional Hilbert spaces, where standard algorithms can sometimes have properties at odds with finite-dimensional intuition. A systematic analysis concentrating on the approximation power of such algorithms within a budget of computation may lead to progress both in theory and practice.