Stability and Generalization of Learning Algorithms that Converge to Global Optima
Stability and Generalization of Learning Algorithms that Converge to Global Optima
复制标题
DOI：
--
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Zachary B. Charles;Dimitris Papailiopoulos
中科院分区：
文献类型：
--
作者：
Zachary B. Charles;Dimitris Papailiopoulos
我们为收敛到全局最小值的学习算法建立了新的泛化界限。我们这样做是通过推导黑盒稳定性的结果，只依赖于学习算法的收敛性和几何周围的损失函数的最小值。结果表明，非凸损失函数满足Polyak-{\L}ojasiewicz（PL）和二次增长（QG）条件。我们进一步表明，这些条件出现一些神经网络的线性激活。我们使用我们的黑盒结果建立的稳定性的优化算法，如随机梯度下降（SGD），梯度下降（GD），随机坐标下降（RCD），和随机方差降低梯度法（SVRG），在PL和强凸设置。我们的研究结果匹配或改善国家的最先进的泛化范围，可以很容易地扩展到类似的优化算法。最后，我们表明，虽然我们的研究结果意味着在PL设置SGD和GD相当的稳定性，存在简单的神经网络与多个局部极小SGD是稳定的，但GD不是。
We establish novel generalization bounds for learning algorithms that converge to global minima. We do so by deriving black-box stability results that only depend on the convergence of a learning algorithm and the geometry around the minimizers of the loss function. The results are shown for nonconvex loss functions satisfying the Polyak-{\L}ojasiewicz (PL) and the quadratic growth (QG) conditions. We further show that these conditions arise for some neural networks with linear activations. We use our black-box results to establish the stability of optimization algorithms such as stochastic gradient descent (SGD), gradient descent (GD), randomized coordinate descent (RCD), and the stochastic variance reduced gradient method (SVRG), in both the PL and the strongly convex setting. Our results match or improve state-of-the-art generalization bounds and can easily be extended to similar optimization algorithms. Finally, we show that although our results imply comparable stability for SGD and GD in the PL setting, there exist simple neural networks with multiple local minima where SGD is stable but GD is not.