Algorithmic stability and hypothesis complexity
It addresses generalization error analysis for learning algorithms, providing theoretical tools for stability-based bounds, but appears incremental as it builds on existing stability concepts.
The paper introduces a notion of algorithmic stability called argument stability to capture hypothesis stability in normed function spaces, and bounds generalization error in terms of this stability using martingale inequalities in Banach spaces, applying the bounds to algorithms like empirical risk minimization and stochastic gradient descent.
We introduce a notion of algorithmic stability of learning algorithms---that we term \emph{argument stability}---that captures stability of the hypothesis output by the learning algorithm in the normed space of functions from which hypotheses are selected. The main result of the paper bounds the generalization error of any learning algorithm in terms of its argument stability. The bounds are based on martingale inequalities in the Banach space to which the hypotheses belong. We apply the general bounds to bound the performance of some learning algorithms based on empirical risk minimization and stochastic gradient descent.