conference paper
Data-dependent stability of stochastic gradient descent
published
yes
Ilja
Kuzborskij
author
Christoph
Lampert
author 40C20FD2-F248-11E8-B48F-1D18A9856A870000-0001-8622-7887
ChLa
department
ICML: International Conference on Machine Learning
Lifelong Learning of Visual Scene Understanding
project
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.
International Machine Learning Society2018Stockholm, Sweden
eng
Proceedings of the 35 th International Conference on Machine Learning
1703.01678
802815-2824
Kuzborskij, Ilja, and Christoph Lampert. “Data-Dependent Stability of Stochastic Gradient Descent.” <i>Proceedings of the 35 Th International Conference on Machine Learning</i>, vol. 80, International Machine Learning Society, 2018, pp. 2815–24.
Kuzborskij, Ilja, and Christoph Lampert. “Data-Dependent Stability of Stochastic Gradient Descent.” In <i>Proceedings of the 35 Th International Conference on Machine Learning</i>, 80:2815–24. International Machine Learning Society, 2018.
Kuzborskij, I., & Lampert, C. (2018). Data-dependent stability of stochastic gradient descent. In <i>Proceedings of the 35 th International Conference on Machine Learning</i> (Vol. 80, pp. 2815–2824). Stockholm, Sweden: International Machine Learning Society.
Kuzborskij I, Lampert C. Data-dependent stability of stochastic gradient descent. In: <i>Proceedings of the 35 Th International Conference on Machine Learning</i>. Vol 80. International Machine Learning Society; 2018: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.
I. Kuzborskij and C. Lampert, “Data-dependent stability of stochastic gradient descent,” in <i>Proceedings of the 35 th International Conference on Machine Learning</i>, Stockholm, Sweden, 2018, vol. 80, pp. 2815–2824.
I. Kuzborskij, C. Lampert, in:, Proceedings of the 35 Th International Conference on Machine Learning, International Machine Learning Society, 2018, pp. 2815–2824.
60112019-02-14T14:51:57Z2019-08-02T12:39:08Z