Stability of SGD: Tightness Analysis and Improved Bounds
Stability of SGD: Tightness Analysis and Improved Bounds
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Yikai Zhang;Wenjia Zhang-;Sammy Bald;Vamsi Pingali;Chao Chen;Mayank Goswami
中科院分区：
文献类型：
--
作者：
Yikai Zhang;Wenjia Zhang-;Sammy Bald;Vamsi Pingali;Chao Chen;Mayank Goswami
基于随机梯度下降（SGD）的方法已被广泛用于训练大规模机器学习模型，这些模型在实践中也具有良好的泛化能力。对于这种泛化性能，已经提供了几种解释，其中一个突出的是算法稳定性[18]。然而，没有已知的平滑损失函数的例子，可以证明分析是严密的。此外，除了损失函数的性质之外，数据分布也被证明是泛化性能的重要因素。这就提出了一个问题：文[18]的稳定性分析对于光滑函数是否是紧的，如果不是，对于什么样的损失函数和数据分布，稳定性分析可以改进？在本文中，我们首先解决开放的问题，在数据无关设置的边界的紧密性：我们表明，对于一般的数据集，现有的分析凸和强凸损失函数是紧的，但它可以改善非凸损失函数。接下来，我们给出了一个新的和改进的数据相关的边界：我们显示了一个大类的凸正则化损失函数的稳定性上界，可以忽略不计的正则化参数，并改善现有的数据相关的边界在非凸设置。我们希望我们的研究结果将启动进一步的努力，以更好地理解非凸损失函数下的数据依赖设置，从而提高对深度网络泛化能力的理解。
Stochastic Gradient Descent (SGD) based methods have been widely used for training large-scale machine learning models that also generalize well in practice. Several explanations have been offered for this generalization performance, a prominent one being algorithmic stability [18]. However, there are no known examples of smooth loss functions for which the analysis can be shown to be tight. Furthermore, apart from the properties of the loss function, data distribution has also been shown to be an important factor in generalization performance. This raises the question: is the stability analysis of [18] tight for smooth functions, and if not, for what kind of loss functions and data distributions can the stability analysis be improved? In this paper we first settle open questions regarding tightness of bounds in the data-independent setting: we show that for general datasets, the existing analysis for convex and strongly-convex loss functions is tight, but it can be improved for non-convex loss functions. Next, we give a novel and improved data-dependent bounds: we show stability upper bounds for a large class of convex regularized loss functions, with negligible regularization parameters, and improve existing data-dependent bounds in the non-convex setting. We hope that our results will initiate further efforts to better understand the data-dependent setting under non-convex loss functions, leading to an improved understanding of the generalization abilities of deep networks.