High-probability generalization bounds for pointwise uniformly stable algorithms

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 stabl...

Full description

Saved in:
Bibliographic Details
Published in:Applied and computational harmonic analysis 2024-05, Vol.70, p.101632, Article 101632
Main Authors: Fan, Jun, Lei, Yunwen
Format: Article
Language:English
Subjects:
Algorithmic stability
Generalization analysis
Learning theory
Stochastic gradient descent
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 pointwise uniform stability by considering the sensitivity of the algorithm with respect to the perturbation of each training example. We show this weaker pointwise uniform stability guarantees almost optimal bounds, and gives the first high-probability bound for the generalization gap as measured by gradients. Sharper bounds 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 summation of weakly-dependent vector-valued random variables.
ISSN:1063-5203
1096-603X
DOI:10.1016/j.acha.2024.101632