Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Raef Bassily;V. Feldman;Crist'obal Guzm'an;Kunal Talwar
中科院分区：
文献类型：
--
作者：
Raef Bassily;V. Feldman;Crist'obal Guzm'an;Kunal Talwar
一致稳定性是算法稳定性的一个概念，当数据集中的单个数据点被替换时，它限制了算法输出的模型中的最坏情况变化。Hardt等人（2016）的一项有影响力的工作提供了随机梯度下降（SGD）算法在充分光滑凸损失上的一致稳定性的强上界。这些结果导致了重要的进展，在理解的推广性质的SGD和几个应用程序的差异私人凸优化光滑损失。我们的工作是第一个解决一致稳定性的SGD {\emnonsmooth}凸损失。具体来说，我们提供了尖锐的上限和下限的几种形式的SGD和全批GD任意Lipschitz非光滑凸损失。我们的下界表明，在非光滑的情况下，（S）GD可以是固有的稳定性比在光滑的情况下。另一方面，我们的上界表明，（S）GD是足够稳定的推导新的和有用的范围的推广误差。最值得注意的是，我们得到了第一个维度独立的推广界多通SGD在非光滑的情况下。此外，我们的界限允许我们推导出一个新的算法差分私人非光滑随机凸优化与最优超额人口风险。对于非光滑情况，我们的算法比最著名的算法更简单，更有效。Feldman et al.（2020）。
Uniform stability is a notion of algorithmic stability that bounds the worst case change in the model output by the algorithm when a single data point in the dataset is replaced. An influential work of Hardt et al. (2016) provides strong upper bounds on the uniform stability of the stochastic gradient descent (SGD) algorithm on sufficiently smooth convex losses. These results led to important progress in understanding of the generalization properties of SGD and several applications to differentially private convex optimization for smooth losses. Our work is the first to address uniform stability of SGD on {\em nonsmooth} convex losses. Specifically, we provide sharp upper and lower bounds for several forms of SGD and full-batch GD on arbitrary Lipschitz nonsmooth convex losses. Our lower bounds show that, in the nonsmooth case, (S)GD can be inherently less stable than in the smooth case. On the other hand, our upper bounds show that (S)GD is sufficiently stable for deriving new and useful bounds on generalization error. Most notably, we obtain the first dimension-independent generalization bounds for multi-pass SGD in the nonsmooth case. In addition, our bounds allow us to derive a new algorithm for differentially private nonsmooth stochastic convex optimization with optimal excess population risk. Our algorithm is simpler and more efficient than the best known algorithm for the nonsmooth case Feldman et al. (2020).