On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks
On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks
复制标题
DOI：
--
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
A. Backurs;P. Indyk;Ludwig Schmidt
中科院分区：
文献类型：
--
作者：
A. Backurs;P. Indyk;Ludwig Schmidt
经验风险最小化(ERM)在机器学习中普遍存在，是大多数监督学习方法的基础。尽管人们对各种ERM问题的算法做了大量的工作，但ERM的确切计算复杂性仍然不是很清楚。我们解决了多个流行的ERM问题，包括核支持向量机、核岭回归和训练神经网络的最后一层。特别地，我们基于复杂性理论的假设，如强指数时间假设，给出了这些问题的条件硬性结果。在这些假设下，我们证明了没有算法可以在次二次时间内高精度地解决上述ERM问题。对于经验损失的梯度的计算，我们也给出了类似的困难结果，经验损失是许多非凸学习任务中的主要计算负担。
Empirical risk minimization (ERM) is ubiquitous in machine learning and underlies most supervised learning methods. While there is a large body of work on algorithms for various ERM problems, the exact computational complexity of ERM is still not understood. We address this issue for multiple popular ERM problems including kernel SVMs, kernel ridge regression, and training the final layer of a neural network. In particular, we give conditional hardness results for these problems based on complexity-theoretic assumptions such as the Strong Exponential Time Hypothesis. Under these assumptions, we show that there are no algorithms that solve the aforementioned ERM problems to high accuracy in sub-quadratic time. We also give similar hardness results for computing the gradient of the empirical loss, which is the main computational burden in many non-convex learning tasks.