Data-Dependent Stability of Stochastic Gradient Descent

By Ilja Kuzborskij, Christoph H. Lampert. 2017

192 citations recorded by the source corpus.

We establish a data-dependent notion of algorithmic stability for Stochastic Gradient Descent (SGD), and employ it to develop novel generalization bounds. This is in contrast to previous distribution-free algorithmic stability results for SGD which depend on the worst-case constants. By virtue of the data-dependent argument, our bounds provide new insights into learning with SGD on convex and non-convex problems. In the convex case, we show that the bound on the generalization error depends on the risk at the initialization point. In the non-convex case, we prove that the expected curvature of the objective function around the initialization point has crucial influence on the generalization error. In both cases, our results suggest a simple data-driven strategy to stabilize SGD by pre-screening its initialization. As a corollary, our results allow us to show optimistic generalization bounds that exhibit fast convergence rates for SGD subject to a vanishing empirical risk and low noise of stochastic gradient.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Stable and Fair Classification (2019, background): “[40], [49] and [47] showed that the stochastic gradient descent method is stable.”
Generalization in Deep Learning (2017, methodology): “L ) and if the codomain of L is in [0 , M ] , we have (Bousquet and Elisseeff, 2002) that for any δ > 0 , with probability at least 1 − δ , Based on previous work on stability (e.g., Hardt et al. 2015; Kuzborskij and Lampert 2017; Gonen and Shalev-Shwartz 2017), one may conjecture some reason for ge”
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data (2017, background): “Stability bounds for SGD in non-convex settings were given in Hardt et al. (2016); Kuzborskij & Lampert (2017).”
Hierarchically Structured Meta-learning (2019, methodology): “According to Theorem 2 in (Kuzborskij & Lampert, 2017), a base learner fθTi is (Si, θ0)-on-average stable if its generalization is bounded by (Si, θ0), i.e., ESiEfθTi [R(fθTi (D tr Ti))−R̂DtrTi (fθTi (D tr Ti))]≤ (Si, θ0). θ0 is the initialization of SGD to reach θTi , and R(·) and R̂DtrTi (·)…”
Understanding Generalization through Visualizations (2019, unknown): “This line of work considers B to be proportional to the stability of the model (Hardt et al., 2016; Kuzborskij and Lampert, 2018; Gonen and Shalev-Shwartz, 2017), which is a measure of how much changing a data point in S changes the output of the model (Sokolic et al.”
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses (2020, background): “Recent applications of this approach can be found for example in (Koren and Levy, 2015; Charles and Papailiopoulos, 2018; Feldman et al., 2020).”
On the Intrinsic Privacy of Stochastic Gradient Descent (2019, background): “[22] more recently built on and expanded these results, relating them to modern deep learning techniques and hyperparameters of SGD such as the number of training iterations; [29] extend the analysis to data-dependent notions of stability.”
Generalization Bounds for Uniformly Stable Algorithms (2018, result): “and Guedj [CG16] gives high-probability generalization bounds similar to those in [BE02] but using a bound on a high-order moment of stability instead of the uniform stability. Kuzborskij and Lampert [KL18] give data-dependent generalization bounds for SGD on smooth convex and non-convex losses base”
SGD on Neural Networks Learns Functions of Increasing Complexity (2019, background): “(2016) and Kuzborskij & Lampert (2017) [17, 24] argue that generalization is due to stability.”
On the Effectiveness of Parameter-Efficient Fine-Tuning (2022, result): “Stability has been studied in a lot of previous research works (Bousquet and Elisseeff 2002; Shalev-Shwartz et al. 2010; Shalev-Shwartz and Ben-David 2014; Hardt, Recht, and Singer 2016; Kuzborskij and Lampert 2018; Charles and Papailiopoulos 2018; Fu et al. 2021) in many different forms.”
AN EMPIRICAL STUDY (2022, unknown): “Hardt, Recht, and Singer [19] expanded these results, relating them to modern deep learning techniques and hyper-parameters of SGD; Kuzborskij and Lampert [28] extend the analysis to data-dependent stability and generalisation bounds.”