{"ID":2896547,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.06775","arxiv_id":"2507.06775","title":"Stability, Complexity and Data-Dependent Worst-Case Generalization Bounds","abstract":"Providing generalization guarantees for stochastic optimization algorithms remains a key challenge in learning theory. Recently, numerous works demonstrated the impact of the geometric properties of optimization trajectories on generalization performance. These works propose worst-case generalization bounds in terms of various notions of intrinsic dimension and/or topological complexity, which were found to empirically correlate with the generalization error. However, most of these approaches involve intractable mutual information terms, which limit a full understanding of the bounds. In contrast, some authors built on algorithmic stability to obtain worst-case bounds involving geometric quantities of a combinatorial nature, which are impractical to compute. In this paper, we address these limitations by combining empirically relevant complexity measures with a framework that avoids intractable quantities. To this end, we introduce the concept of \\emph{random set stability}, tailored for the data-dependent random sets produced by stochastic optimization algorithms. Within this framework, we show that the worst-case generalization error can be bounded in terms of (i) the random set stability parameter and (ii) empirically relevant, data- and algorithm-dependent complexity measures of the random set. Moreover, our framework improves existing topological generalization bounds by recovering previous complexity notions without relying on mutual information terms. Through a series of experiments in practically relevant settings, we validate our theory by evaluating the tightness of our bounds and the interplay between topological complexity and stability.","short_abstract":"Providing generalization guarantees for stochastic optimization algorithms remains a key challenge in learning theory. Recently, numerous works demonstrated the impact of the geometric properties of optimization trajectories on generalization performance. These works propose worst-case generalization bounds in terms of...","url_abs":"https://arxiv.org/abs/2507.06775","url_pdf":"https://arxiv.org/pdf/2507.06775v2","authors":"[\"Mario Tuci\",\"Lennart Bastian\",\"Benjamin Dupuis\",\"Nassir Navab\",\"Tolga Birdal\",\"Umut Şimşekli\"]","published":"2025-07-09T12:03:25Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"math.AT\",\"stat.ML\"]","methods":"[]","has_code":false}