Coresets for Data-efficient Training of Machine Learning Models
Coresets for Data-efficient Training of Machine Learning Models
复制标题
DOI：
--
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Baharan Mirzasoleiman;J. Bilmes;J. Leskovec
中科院分区：
文献类型：
--
作者：
Baharan Mirzasoleiman;J. Bilmes;J. Leskovec
增量梯度（IG）方法，例如随机梯度下降及其变体，通常用于机器学习中的大规模优化。尽管人们不断努力提高 IG 方法的数据效率，但如何选择在理论上和实践上与完整数据集性能相当的训练数据子集仍然是一个悬而未决的问题。在这里，我们开发了 CRAIG，一种选择训练数据的加权子集（或核心集）的方法，该方法通过最大化子模函数来密切估计完整梯度。我们证明，将 IG 应用于该子集可以保证收敛到（接近）最优解，其收敛速度与 IG 凸优化的收敛速度相同。结果，CRAIG 实现了与子集大小成反比的加速。据我们所知，这是第一个对通用机器学习模型进行数据高效训练的严格方法。我们大量的实验表明，CRAIG 在实现几乎相同的解决方案的同时，将各种 IG 方法的逻辑回归速度提高了 6 倍，将训练深度神经网络的速度提高了 3 倍。
Incremental gradient (IG) methods, such as stochastic gradient descent and its variants are commonly used for large scale optimization in machine learning. Despite the sustained effort to make IG methods more data-efficient, it remains an open question how to select a training data subset that can theoretically and practically perform on par with the full dataset. Here we develop CRAIG, a method to select a weighted subset (or coreset) of training data that closely estimates the full gradient by maximizing a submodular function. We prove that applying IG to this subset is guaranteed to converge to the (near)optimal solution with the same convergence rate as that of IG for convex optimization. As a result, CRAIG achieves a speedup that is inversely proportional to the size of the subset. To our knowledge, this is the first rigorous method for data-efficient training of general machine learning models. Our extensive set of experiments show that CRAIG, while achieving practically the same solution, speeds up various IG methods by up to 6x for logistic regression and 3x for training deep neural networks.