High-probability generalization bounds for pointwise uniformly stable algorithms

Abstract

<p>Algorithmic stability is a fundamental concept in statistical learning theory to understand the generalization behavior of optimization algorithms. Existing high-probability bounds are developed for the generalization gap as measured by function values and require the algorithm to be uniformly stable. In this paper, we introduce a novel stability measure called <a href="https://www.sciencedirect.com/topics/mathematics/pointwise" title="Learn more about pointwise from ScienceDirect's AI-generated Topic Pages">pointwise</a> uniform stability by considering the sensitivity of the algorithm with respect to the perturbation of each training example. We show this weaker <a href="https://www.sciencedirect.com/topics/mathematics/pointwise" title="Learn more about pointwise from ScienceDirect's AI-generated Topic Pages">pointwise</a> uniform stability guarantees almost optimal bounds, and gives the first high-probability bound for the generalization gap as measured by gradients. <a href="https://www.sciencedirect.com/topics/mathematics/sharp-bound" title="Learn more about Sharper bounds from ScienceDirect's AI-generated Topic Pages">Sharper bounds</a> are given for strongly convex and smooth problems. We further apply our general result to derive improved generalization bounds for stochastic gradient descent. As a byproduct, we develop concentration inequalities for a <a href="https://www.sciencedirect.com/topics/mathematics/summation" title="Learn more about summation from ScienceDirect's AI-generated Topic Pages">summation</a> of weakly-dependent vector-valued random variables.</p>