Data-dependent stability of stochastic gradient descent

I. Kuzborskij, C. Lampert, in:, Proceedings of the 35 Th International Conference on Machine Learning, International Machine Learning Society, 2018, pp. 2815–2824.

Conference Paper | Published | English
Author
;
Department
Abstract
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.
Publishing Year
Date Published
2018-02-01
Proceedings Title
Proceedings of the 35 th International Conference on Machine Learning
Volume
80
Page
2815-2824
Conference
ICML: International Conference on Machine Learning
Conference Location
Stockholm, Sweden
Conference Date
2018-07-10 – 2018-07-15
IST-REx-ID

Cite this

Kuzborskij I, Lampert C. Data-dependent stability of stochastic gradient descent. In: Proceedings of the 35 Th International Conference on Machine Learning. Vol 80. International Machine Learning Society; 2018:2815-2824.
Kuzborskij, I., & Lampert, C. (2018). Data-dependent stability of stochastic gradient descent. In Proceedings of the 35 th International Conference on Machine Learning (Vol. 80, pp. 2815–2824). Stockholm, Sweden: International Machine Learning Society.
Kuzborskij, Ilja, and Christoph Lampert. “Data-Dependent Stability of Stochastic Gradient Descent.” In Proceedings of the 35 Th International Conference on Machine Learning, 80:2815–24. International Machine Learning Society, 2018.
I. Kuzborskij and C. Lampert, “Data-dependent stability of stochastic gradient descent,” in Proceedings of the 35 th International Conference on Machine Learning, Stockholm, Sweden, 2018, vol. 80, pp. 2815–2824.
Kuzborskij I, Lampert C. 2018. Data-dependent stability of stochastic gradient descent. Proceedings of the 35 th International Conference on Machine Learning. ICML: International Conference on Machine Learning vol. 80. 2815–2824.
Kuzborskij, Ilja, and Christoph Lampert. “Data-Dependent Stability of Stochastic Gradient Descent.” Proceedings of the 35 Th International Conference on Machine Learning, vol. 80, International Machine Learning Society, 2018, pp. 2815–24.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1703.01678

Search this title in

Google Scholar