Generalization Error Bounds for Optimization Algorithms via Stability

By Qi Meng, Zhiming Ma, Tie-Yan Liu. 2016

10 citations recorded by the source corpus.

Many machine learning tasks can be formulated as Regularized Empirical Risk Minimization (R-ERM), and solved by optimization algorithms such as gradient descent (GD), stochastic gradient descent (SGD), and stochastic variance reduction (SVRG). Conventional analysis on these optimization algorithms focuses on their convergence rates during the training process, however, people in the machine learning community may care more about the generalization performance of the learned model on unseen test data. In this paper, we investigate on this issue, by using stability as a tool. In particular, we decompose the generalization error for R-ERM, and derive its upper bound for both convex and nonconvex cases. In convex cases, we prove that the generalization error can be bounded by the convergence rate of the optimization algorithm and the stability of the R-ERM process, both in expectation (in the order of

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, methodology): “Several prior works [10, 65, 52, 54] study the stability property for empirical risk minimization.”
Why ResNet Works? Residuals Generalize (2019, methodology): “These theoretical tools have been widely applied to analyze many algorithms (see, e.g., [31, 17, 36, 48]).”