Stability, Complexity and Data-Dependent Worst-Case Generalization Bounds

## Abstract

Abstract Providing generalization guarantees for stochastic optimization algorithms is a major challenge in modern learning theory.
Recently, several studies highlighted the impact of the geometry of training trajectories on the generalization error, both theoretically and empirically.
Among these works, a series of topological generalization bounds have been proposed, relating the generalization error to notions of topological complexity that stem from topological data analysis (TDA).
Despite their empirical success, these bounds rely on intricate information-theoretic (IT) terms that can be bounded in specific cases but remain intractable for practical algorithms (such as ADAM), potentially reducing the relevance of the derived bounds.
In this paper, we seek to formulate comprehensive and interpretable topological generalization bounds free of intractable mutual information terms.
To this end, we introduce a novel learning theoretic framework that departs from the existing strategies via proof techniques rooted in algorithmic stability.
By extending an existing notion of hypothesis set stability , to trajectory stability , we prove that the generalization error of trajectory-stable algorithms can be upper bounded in terms of (i) TDA quantities describing the complexity of the trajectory of the optimizer in the parameter space, and (ii) the trajectory stability parameter of the algorithm.
Through a series of experimental evaluations, we demonstrate that the TDA terms in the bound are of great importance, especially as the number of training samples grows.
This ultimately forms an explanation of the empirical success of the topological generalization bounds.

## 1 Introduction

The generalization capabilities of deep learning models play a crucial role in our understanding of modern machine learning. Explaining generalization and, thus, the success of current neural networks is still an open problem and an active research area [ZBH^+17, ZBH^+21].
Following classical statistical learning theory [SSBD14], supervised learning tasks can be framed as a population risk minimization problem, defined as:

$$ $\displaystyle\min_{w\in\mathbb{R}^{d}}\left\{\mathcal{R}(w):=\mathbb{E}_{z\sim \mu_{z}}[\ell(w,z)]\right\},$ (1) $$

where $z\in\mathcal{Z}$ denotes the data, distributed according to a probability distribution $\mu_{z}$ on the data space $\mathcal{Z}$ and $\ell:\mathbb{R}^{d}\times\mathcal{Z}\to\mathbb{R}$, the composed loss function. In practice, we have $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$, where $\mathcal{X}$ denotes a feature space and $\mathcal{Y}$ is a label space.
Since the data distribution $\mu_{z}$ is unknown, it is in general not possible to directly solve ([1](https://arxiv.org/html/2507.06775v1#S1.E1)); instead, we typically solve the empirical risk minimization problem ([2](https://arxiv.org/html/2507.06775v1#S1.E2)): for $n$ given data points $S:=(z_{1},\dots,z_{n})\sim\mu_{z}^{\otimes n}:=\mu_{z}\otimes\dots\otimes\mu_{z}$ independently sampled from the data distribution $\mu$, we consider:

$$ $\displaystyle\min_{w\in\mathbb{R}^{d}}\left\{\widehat{\mathcal{R}}_{S}(w):= \frac{1}{n}\sum_{i=1}^{n}\ell(w,z_{i})\right\}$ (2) $$

In most applications, the problem ([2](https://arxiv.org/html/2507.06775v1#S1.E2)) is solved by the means of stochastic optimization algorithms, such as stochastic gradient descent (SGD) or ADAM [KB14].
These algorithms often take an iterative form and we denote $w_{k}$ the parameter that is learned after $k$ iterations.

Recent studies suggest that the training trajectory, i.e., the set of iterates $w_{k}$ obtained by the algorithm, may be paramount in explaining the generalization ability of modern machine learning models [XTYY24, FZY^+24, ADS^+24]. Indeed, since the empirical risk ([2](https://arxiv.org/html/2507.06775v1#S1.E2)) can contain many (typically infinitely many) local minima with different generalization properties, the trajectories of the optimization algorithm *near* a local minimum offer a concise way to assess the quality of the local minimum: they inherently reflect the influence of the optimization algorithm, the choice of hyperparameters, and the dataset—factors that are all essential for deriving meaningful generalization bounds.

More precisely, the trajectory of the optimizer is essentially a random subset of $\mathbb{R}^{d}$, that is defined as follows: $\mathcal{W}_{S,U}:=\{w_{t}:t_{0}\leq t\leq T\}\subset\mathbb{R}^{d}$, where $t_{0}$ is chosen such that $w_{t_{0}}$ is near a local minimum that is found by the optimizer, say $w_{\star}$, $U$ represents the algorithmic randomness (e.g., batch indices), which is independent of the other random variables. In essence, $\mathcal{W}_{S,U}$ is the part of the basin corresponding to $w_{\star}$ that is *accessible* to the optimization algorithm. To measure the quality of the local minimum $w_{\star}$ by using the structure of the trajectory $\mathcal{W}_{S,U}$, the main quantity of interest has been the *worst-case generalization error* over $\mathcal{W}_{S,U}$ , defined as follows:

$$ $\displaystyle G_{S}(\mathcal{W}_{S,U}):=\sup_{w\in\mathcal{W}_{S,U}}\left( \mathcal{R}(w)-\hat{\mathcal{R}}_{S}(w)\right).$ (3) $$

Upper-bounding $G_{S}(\mathcal{W}_{S,U})$ requires uniform convergence results on the *random, data-dependent hypothesis set* $\mathcal{W}_{S,U}$, which is a notoriously challenging problem [FGK^+19, SvEH^+23, DVDS24].

In this context, recent studies [SSDE20, DDS23, ALRS23, HSKM22, DVDS24, BLGS21, ADS^+24] have established upper-bounds on ([3](https://arxiv.org/html/2507.06775v1#S1.E3)) and drawn rigorous links between the *topological structure* of $\mathcal{W}_{S,U}$ and $G_{S}(\mathcal{W}_{S,U})$. These bounds are of the following form(^1^11We use the notation $\lesssim$ in informal statements where absolute constants have been omitted.):

$$ $\displaystyle G_{S}(\mathcal{W}_{S,U})\lesssim\sqrt{\frac{\mathbf{C}(\mathcal{ W}_{S,U})+\mathrm{IT}+\log(1/\zeta)}{n}},$ (4) $$

with probability at least $1-\zeta$. The bound in ([4](https://arxiv.org/html/2507.06775v1#S1.E4)) has two main ingredients: (i) The first term $\mathbf{C}(\mathcal{W}_{S})$, which we call the *topological complexity* in accordance with [ADS^+24], is a geometric quantity of the trajectory, measuring some notion of complexity of $\mathcal{W}_{S}$. Several topological complexities have been proposed, inspired by fractal geometry [SSDE20, DDS23, DV23] and topological data analysis (TDA) [BLGS21, ALRS23, ADS^+24]. (ii) The second term, $\mathrm{IT}$, is an *information-theoretic* (IT) term, typically the *total* mutual information between the dataset $S$ and the trajectory $\mathcal{W}_{S}$; measuring the statistical dependence between $S$ and $\mathcal{W}_{S,U}$ [DVDS24].

The topological complexity term $\mathbf{C}(\mathcal{W}_{S,U})$ appearing in these bounds are both computable and practically informative. In contrast, the $\mathrm{IT}$ term remains opaque and computationally intractable; its behavior with respect to the sample size $n$ is not even well understood in the general case [DVDS24]. As a result, prior studies have adopted a *heuristic* approach by entirely discarding the IT term in their empirical evaluations and concentrating solely on $\mathbf{C}(\mathcal{W}_{S,U})$. These studies reported striking empirical results, demonstrating a strong correlation between the generalization error and the proposed topological complexity measures (an observation we will also report in our experiments)(^2^22While [TGRW^+24] recently raised some concerns about the practical validity of certain fractal dimension–based bounds, [ADS^+24] showed that specific topological descriptors—such as positive magnitude and $\alpha$-weighted lifetime sums, which we will detail in the next section, consistently yield strong empirical performance across a wide range of modern deep learning scenarios.). However, the exclusion of the IT term renders such evaluations theoretically incomplete, and the underlying reason for the empirical success of the topological complexity measures remains unclear.

To address this issue, an initial step was taken in [SvEH^+23], where the authors introduced the notion of ‘algorithm-dependent Rademacher complexity’ (ARC) and derived generalization bounds with a topological flavor, notably avoiding the $\mathrm{IT}$ term. However, ARC is based on combining parameters in a combinatorial fashion (similar to the approach that has been used for conditional mutual information-based bounds [SZ20]). As a result, the associated topological quantities were not tied to the data-dependent optimization trajectory $\mathcal{W}_{S,U}$, but rather to an abstract, theoretically constructed hypothesis set. Consequently, while the bounds are insightful from a theoretical standpoint, they fall short of explaining why $\mathbf{C}(\mathcal{W}_{S,U})$ proves effective in practice.

In this study, our goal is to bridge the gap between topological generalization bounds and the aforementioned empirical observations, by deriving generalization bounds that are directly expressed in terms of the $\mathbf{C}(\mathcal{W}_{S,U})$ while entirely avoiding the information-theoretic terms.

#### Contributions

Our main contributions are summarized below.

- •
Inspired by [FGK^+19], we define the notion of *trajectory stability*, that is adapted to stochastic learning algorithms, i.e., producing random trajectories.
Based on this stability condition, we prove expected topological generalization bounds of the form:
$\displaystyle\mathbb{E}\left[\sup_{w\in\mathcal{W}_{S,U}}\left(\mathcal{R}(w)-
\widehat{\mathcal{R}}_{S}(w)\right)\right]\lesssim\beta_{n}^{1/3}\left(1+
\mathbb{E}\left[\sqrt{\mathbf{C}(\mathcal{W}_{S,U})}\right]\right),$
where $\beta_{n}$ is the stability parameter and $\mathbf{C}(\mathcal{W}_{S,U})$ is a topological complexity identical to some of the TDA-inspired terms used in [BLGS21, ADS^+24].
In particular, we recover the so-called $\alpha$-weighted lifetime sums and positive magnitude based on the Euclidean distance (see [Section 2](https://arxiv.org/html/2507.06775v1#S2)).
- •
We further investigate our new trajectory stability condition and show that a variant of the classical notion of algorithmic stability [HRS16] implies trajectory stability.
Hence, if the optimization algorithm is algorithmically stable in a more classical sense, existing algorithmic stability results imply that, in various cases, the trajectory stability parameter $\beta_{n}$ will be of order $\mathcal{O}(1/n)$, rendering our bounds $\mathcal{O}(n^{-1/3}\sqrt{\mathbf{C}(\mathcal{W}_{S})})$.
- •
We extend recent empirical studies on topological generalization bounds and explain the interplay between stability and topology, emphasizing the role of sample size as a key factor in the analysis of topological generalization bounds.

Our results demonstrate that, if the optimizer is trajectory-stable, the information-theoretic terms in the bound [Equation 4](https://arxiv.org/html/2507.06775v1#S1.E4) can be safely omitted, at the expense of a reduced convergence rate(^3^33A similar convergence rate was also reported in [DDS23] in an attempt to reduce the impact of the IT terms.), i.e., from $n^{-1/2}$ to $n^{-1/3}$.
We believe that our findings reduce the gap between theory and practice, paving the way for even more practical topological generalization bounds with new empirical insights for large-scale datasets. The implementation will be made publicly available at [https://github.com/bastianlb/MI-free-topo-bounds](https://github.com/bastianlb/MI-free-topo-bounds).
All the proofs are provided in the appendix.

## 2 Preliminaries Technical Background

We now introduce technical background regarding the topological complexities used in this work ([Section 2.1](https://arxiv.org/html/2507.06775v1#S2.SS1)) and algorithmic stability ([Section 2.2](https://arxiv.org/html/2507.06775v1#S2.SS2)).

### 2.1 Topological Complexity Measures

#### α 𝛼 \alpha italic_α -Weighted lifetime sum

The $\alpha$-weighted lifetime sum is one of the building blocks of the persistent homology dimension [Sch20, BLGS21]. Lifetime intervals encode how long topological features (like connected components) persist across scales [BGND^+19, HKNU17, HKND19]. Informally, it
tracks a finite set’s “connected components” at different scales.
For simplicity and readability, we provide an equivalent formulation based on minimum spanning trees [Sch20, KLS06].

Let $X$ be a finite set of points endowed with a metric $\rho$. A tree over X is a connected acyclic undirected graph whose vertices are the points in X.
Given an edge $e$ linking the points a and b, we define its cost as $|e|:=\rho(a,b)$
The $\alpha$-weighted lifetime sums are defined as:

$$ $\forall\alpha\geq 0,\quad\textbf{E}_{\rho}^{\alpha}(X):=\sum_{e\in\mathrm{MST} (X)}|e|^{\alpha},$ $$

where $\mathrm{MST}(X)$ denotes a minimum spanning tree over the graph defined by $X$.

#### Positive magnitude

The concept of metric magnitude was introduced in [Lei13], it is critical in geometric measure theory and integral geometry [Mec13].
In [ADS^+24] a variant called *positive magnitude* was introduced and rigorously linked to generalization error. Informally, (positive) magnitude can be interpreted as the effective number of distinct points in a space at a given scale. We now give the definition of positive magnitude.
For a “scale” parameter $s>0$ and a finite metric space $(X,\rho)$, we define a *weighting* of the scaled space $(s\cdot X,\rho)$ as a vector $\gamma_{s}:X\to\mathbb{R}$ such that for any $a\in X$, we have $\sum_{b\in X}e^{-s\rho(a,b)}\gamma_{s}(b)=1$.
The existence of such weighting is ensured in the finite Euclidean setting [Mec15].
The positive magnitude of $(s\cdot X,\rho)$ is then defined as:

$$ $\displaystyle\mathbf{PMag}_{\rho}(s\cdot X):=\sum_{b\in X}\gamma_{s}(b)_{+},$ (5) $$

where $\gamma_{+}:=\max\{0,\gamma\}$.
The parameter $s$ can be seen as a scale through which we look at $(X,\rho)$.

### 2.2 Algorithmic stability

Algorithmic stability is a fundamental concept in learning theory [BE02, BKZ20]. It has proven successful in providing generalization guarantees for widely used stochastic optimization algorithms [BFGT20, FV19, ZGRS23, HRS16].
In this paper, we consider a variant of algorithmic stability, called *uniform argument stability*, introduced by [BFGT20].

In all the following, we say that two datasets $S,S^{\prime}\in\mathcal{Z}^{n}$ are neighboring datasets if they differ by one element, which we denote $S\simeq S^{\prime}$.

###### Definition 2.1 (Uniform argument stability [ BFGT20 ] ) .

Let $\mathcal{A}(S,U)\in\mathbb{R}^{d}$ be a randomized algorithm where $S\in\mathcal{Z}^{n}$ is a dataset and $U$ represent the algorithm randomness. We say that $\mathcal{A}$ satisfies uniform parameter stability with coefficient $\beta>0$ if for any neighboring datasets $S\simeq S^{\prime}$, we have:

$$ $\displaystyle\mathbb{E}_{U}\left[\left\|\mathcal{A}(S,U)-\mathcal{A}(S^{\prime },U)\right\|\right]\leq\beta.$ $$

If $\ell(w,z)$ is $L$-Lipschitz continuous in $w$, this implies the classical algorithmic stability [HRS16]:

$$ $\displaystyle\sup_{S\simeq S^{\prime}}\sup_{z\in\mathcal{Z}}\mathbb{E}_{U} \left[\ell(\mathcal{A}(S,U),z)-\ell(\mathcal{A}(S^{\prime},U),z)\right]\leq L\beta.$ (6) $$

Unfortunately, in the context of worst case generalization bounds (i.e., upper bounds on $G_{S}(\mathcal{W}_{S})$), this assumption is not of much use as one needs to specify the stability of the entire set $\mathcal{W}_{S}$ and not just one parameter inside it.
To address this issue, a first step was taken by [FGK^+19], who introduced the following notion of hypothesis set stability.

###### Definition 2.2 ( [ FGK + 19 ] ) .

A family $(\mathcal{W}_{S})_{S\in\mathcal{Z}^{n}}$ of data-dependent hypothesis sets is said to be $\beta$-uniformly stable if for any $S\simeq S^{\prime}$ in $\mathcal{Z}^{n}$ and any $w\in\mathcal{W}_{S}$, if there exists $w^{\prime}\in\mathcal{W}_{S^{\prime}}$ such that:

$$ $\textstyle\sup_{z\in\mathcal{Z}}|\ell(w,z)-\ell(w^{\prime},z)|\leq\beta.$ $$

Note that the classical algorithmic stability (as described in [HRS16] for instance) is a particular case of [Definition 2.2](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition2).
The correctness of this assumption in several settings was studied in [FGK^+19], such as strongly convex optimization. In [Section 3](https://arxiv.org/html/2507.06775v1#S3), we will extend this condition to noisy algorithms.

In the context of topological generalization bounds, a different stability assumption was already used in [DDS23] to obtain generalization bounds with slightly simpler information-theoretic terms, but without removing the need for such terms. The main technical novelty of our study is to exploit stability to prove IT-free topological generalization bounds, as we present in the next section.

###### Definition 2.1 (Uniform argument stability [ BFGT20 ] ) .

###### Definition 2.2 ( [ FGK + 19 ] ) .

## 3 Main Theoretical Results

We now present our main theoretical contributions, which are expected topological generalization bounds on the generalization error $G_{S}(\mathcal{W}_{S})$ defined in [Equation 3](https://arxiv.org/html/2507.06775v1#S1.E3).
Our core technical contribution is based on a variation of the hypothesis set stability of [FGK^+19] (see [Definition 2.2](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition2)), which we present in [Section 3.1](https://arxiv.org/html/2507.06775v1#S3.SS1).
First, we specify some notation. Let $\mathrm{CL}(\mathbb{R}^{d})$ denote the closed subsets of $\mathbb{R}^{d}$ and $\Omega$ denote an arbitrary probability space, we see a learning algorithm as a mapping:

$$ $\displaystyle\mathcal{A}:\bigcup_{n=1}^{\infty}\mathcal{Z}^{n}\times\Omega \longrightarrow\mathrm{CL}(\mathbb{R}^{d}),$ (7) $$

which we denote $\mathcal{A}(S,U)=\mathcal{W}_{S,U}$, where $S$ is the dataset and $U$ is an independent random variable representing the algorithm randomness. In practice, $\mathcal{W}_{S,U}$ is the trajectory of the optimizer in the parameter space, as specified in [Section 1](https://arxiv.org/html/2507.06775v1#S1). This framework has been adopted by previous studies [HSKM22, DDS23]. Note that the dependence on $U$ will be omitted when the context is clear.

### 3.1 Random trajectory stability

The main drawback of [Definition 2.2](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition2) is that it does not explicitly account for the algorithm randomness (e.g., batch indices), as opposed to the classical algorithmic stability [BE02, HRS16].

In order to address this issue, we propose a variant of the assumption of [FGK^+19], accounting for the presence of randomness. The main difficulty that arises here is to give a meaning to the expressions such as $w\in\mathcal{W}_{S}$, when $\mathcal{W}_{S}$ is a random set. To do so, we define the notion of data-dependent selection [Mol17].

###### Definition 3.1 .

A data-dependent selection of $\mathcal{W}_{S,U}$ is a deterministic mapping
$\omega:\mathrm{CL}(\mathbb{R}^{d})\times\mathcal{Z}^{n}\to\mathbb{R}^{d}$ such that $\omega(\mathcal{W}_{S,U},S)\in\mathcal{W}_{S,U}$ almost surely with respect to the joint distribution of $(S,\mathcal{W}_{S,U})$.

We are mostly interested in the following “argmax selection”. In the rest of the paper, given $S_{1},S_{2}\in\mathcal{Z}^{n}$, we assume the existence of a random variable $\omega(\mathcal{W}_{S_{1}},S_{2})$ such that, almost surely:

$$ $\displaystyle\omega(\mathcal{W}_{S_{1}},S_{2})\in\operatorname*{arg\,max}_{w \in\mathcal{W}_{S_{1}}}G_{S_{2}}(w).$ (8) $$

Note that the existence of such a random variable is ensured under mild conditions [Mol17].
Equipped with this definition, we now introduce our stability assumption.

###### Assumption 3.1 (Trajectory stability) .

Algorithm $\mathcal{A}$ is $\beta_{n}$-trajectory-stable if for any $J\in\mathbb{N}^{\star}$ and any data-dependent selection $\omega$ of $\mathcal{W}_{S,U}$, there exists a mapping $\omega^{\prime}:\mathrm{CL}(\mathbb{R}^{d})\times\mathbb{R}^{d}\to\mathbb{R}^{d}$ such that:

- •
almost surely, for any $S$ and $w$, $\omega^{\prime}(W_{S},w)\in\mathcal{W}_{S}$ .
- •
For all $z\in\mathcal{Z}$ and two datasets $S,S^{\prime}\in\mathcal{Z}^{n}$ differing by $J$ elements we have:
$\displaystyle\mathbb{E}_{U}[|\ell(\omega(\mathcal{W}_{S,U},S),z)-\ell(\omega^{
\prime}(\mathcal{W}_{S^{\prime},U},\omega(\mathcal{W}_{S,U},S)),z)|]\leq\beta_
{n}J.$

In the absence of algorithmic randomness, that is, when each $U$ is constant, [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1) is a particular case of [Definition 2.2](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition2).
Stability assumptions are usually enounced for neighboring datasets, here we present a variant with datasets differing by $J$ elements. These two variants are equivalent and we chose this presentation to simplify subsequent proofs and notations.
The presence of the mapping $\omega^{\prime}$ might be intriguing: $\omega^{\prime}$ corresponds to the parameter denoted $w^{\prime}$ in [Definition 2.2](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition2) and is denoted this way to make explicit its dependence on the different random variables.

The main advantage of [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1) is to take the expectation over the algorithm randomness.
A natural question arises as to whether this assumption can be satisfied in practice. We answer this question by the following lemma, which shows that [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1) is implied by [Definition 2.1](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition1).

###### Lemma 3.2 .

Consider a fixed $K\in\mathbb{N}^{\star}$, $1\leq k\leq K$, and algorithms(^4^44$\mathcal{A}_{k}$ is an algorithm with values in $\mathbb{R}^{d}$, i.e., its output is the $k$-th iterate of the optimization algorithm.)
$\mathcal{A}_{k}(S,U):=w_{k}$.
Let $\mathcal{A}(S,U)=\mathcal{W}_{S,U}=\{\mathcal{A}_{k}(S,U)\}_{k=1}^{K}$ be an algorithm in the sense of [Equation 7](https://arxiv.org/html/2507.06775v1#S3.E7). Assume that for all $k$, $\mathcal{A}_{k}$ is $\delta_{k}$-uniformly argument-stable in the sense of [Definition 2.1](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition1) and that the loss $\ell(w,z)$ is $L$-Lipschitz-continuous in $w$. Then, $\mathcal{A}$ is trajectory-stable with parameter at most $\beta_{n}=L\sum_{k=1}^{K}\delta_{k}$.

This result shows that [Definition 2.1](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition1) implies trajectory stability, in the sense of [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1). While uniform argument stability differs from the classical notion of algorithmic stability, it can be noted that many stability-based studies rely on a Lipschitz assumption and prove uniform argument stability to derive algorithmic stability parameters [HRS16], as noted by [BFGT20]. Therefore, we see that the conditions of [Lemma 3.2](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem2) can be satisfied in numerous cases, such as optimization of convex, smooth, and Lipschitz continuous functions [HRS16]. Under these conditions, it is obtained that the stability parameter is of order $\beta_{k}=\mathcal{O}(k/n)$, hence, yielding random trajectory stability with a parameter of order $\mathcal{O}(T^{2}/n)$, in the worst case. In the appendix, we present a corollary to Lemma [3.2](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem2) showing that projected SGD on a non-convex problem is $\mathcal{O}(1/n)$-trajectory-stable.

This finding is key to our approach. Indeed, combined with the topological generalization bounds as we do in the next section, a stability parameter of order $\mathcal{O}(1/n)$ will yield a complete bound of the form $\mathcal{O}(n^{-1/3}\sqrt{\mathbf{C}(\mathcal{W}_{S})})$, where $\mathbf{C}(\mathcal{W}_{S})$ is a topological complexity term.

###### Definition 3.1 .

###### Assumption 3.1 (Trajectory stability) .

###### Lemma 3.2 .

### 3.2 Topological generalization bounds for trajectory-stable algorithms

We now leverage our random trajectory stability assumption to prove new topological generalization bounds without IT terms.
We assume that the trajectories $\mathcal{W}_{S}$ are almost surely finite throughout, i.e., they correspond to the trajectory of the optimizer for a finite number of iterations.

As in previous work [DVDS24, ADS^+24], our proofs are centered around the notion of Rademacher complexity [BM02] (formally defined in the appendix).
One of our key technical contributions is deriving a Rademacher complexity bound for trajectory-stable algorithms.
For the sake of simplicity, we postpone the technical details to the appendix and present our main results hereafter.

Our new topological generalization bounds rely on regularity conditions of the loss function (namely, Lipschitz continuity and boundedness), which we now present.

###### Assumption 3.3 .

The loss function $\ell\colon\mathbb{R}^{d}\times\mathcal{Z}\to\mathbb{R}$ is $L$-Lipschitz continuous with respect to its first argument, i.e., for all $w,w^{\prime}\in\mathbb{R}^{d}$ and any $z\in\mathcal{Z}$, $|\ell(w,z)-\ell(w^{\prime},z)|\leq L\|w-w^{\prime}\|$.

Such Lipschitz assumptions were already used in previous topology-based studies [SSDE20, BLGS21, ALRS23].
Subsequent works [DDS23] mitigated these assumptions, albeit through the incorporation of intricate IT terms, which we avoid in our stability-based framework.
As is typical in this literature [ADS^+24, DVDS24, BLGS21], we also assume the boundedness of the loss function.

###### Assumption 3.4 .

We assume that the loss $\ell$ is bounded in $[0,B]$, with $B>0$ being a constant.

We remark that this assumption holds; for instance, for the 0 0-$1$ loss. As demonstrated in [DDS23, ADS^+24], the proposed theory remains experimentally valid even for unbounded losses. Our experimental results support extending this observation to our setting.

Equipped with these assumptions, we can now present our new stability-based topological generalization bounds. We present two results, depending on the topological complexity of interest. The first result is a topological bound based on $\alpha$-weighted lifetime sums.

###### Theorem 3.5 .

Suppose that Assumptions [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1), [3.3](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem3), and [3.4](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem4) hold and define $K_{n,\alpha}:=2(2L\sqrt{n}/B)^{\alpha}$. Without loss of generality(^5^55Not making this assumption only yields changes in the absolute constants of the bound.), assume that $\beta_{n}^{-2/3}$ is an integer divisor of $n$. For any $\alpha\in(0,1]$, we have:

$$ $\displaystyle\mathbb{E}\bigg{[}\sup_{w\in\mathcal{W}_{S,U}}(\mathcal{R}(w)- \widehat{\mathcal{R}}_{S}(w))\bigg{]}\leq\beta_{n}^{1/3}\left(2+2B+2B\mathbb{E }\left[\sqrt{2\log(1+K_{n,\alpha}\mathbf{E}^{\alpha}_{\left\|\cdot\right\|}( \mathcal{W}_{S,U}))}\right]\right).$ $$

The detailed proof is postponed to the appendix.
By building on the results on positive magnitude of [ADS^+24], this leads to the following positive magnitude-based generalization bound for trajectory-stable algorithms.

###### Theorem 3.6 .

Suppose that Assumptions [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1), [3.3](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem3), and [3.4](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem4) hold and define $s(\lambda):=\lambda L\beta_{n}^{-1/3}/B$ . Without loss of generality, assume that $\beta_{n}^{-2/3}$ is an integer divisor of $n$. For any $\lambda>0$ we have:

$$ $\displaystyle\mathbb{E}\bigg{[}\sup_{w\in\mathcal{W}_{S,U}}(\mathcal{R}(w)- \widehat{\mathcal{R}}_{S}(w))\bigg{]}\leq\beta_{n}^{1/3}\left(2+\lambda B+ \frac{2B}{\lambda}\mathbb{E}\left[\log\mathbf{PMag}_{\left\|\cdot\right\|} \left(s(\lambda)\cdot\mathcal{W}_{S,U}\right)\right]\right).$ $$

This result suggests that a theoretically justified choice of the magnitude scale would be $s(\lambda)\approx\beta_{n}^{-1/3}$, which amounts to $\Theta(n^{1/3})$ in the event that $\beta_{n}=\mathcal{O}(1/n)$.
This is an interesting observation, as the results in [ADS^+24] suggested an optimal scale parameter of order $s=\Theta(\sqrt{n})$.

Note moreover that it was also observed by that small values of $s(\lambda)$ can give satisfactory correlation with the generalization error, indicating that better choices of $\lambda$ might be available in certain cases. We leave the investigation of this matter to future studies.

In [Theorems 3.5](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem5) and [3.6](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem6), we focus on two topological complexities: the weighted lifetime sums and the positive magnitude.
This choice is motivated by the empirical results of [ADS^+24], who demonstrated that they have better correlation with the generalization error compared to previously introduced dimension-based complexities [SSDE20]. Nevertheless, our approach can trivially recover bounds based on other complexities, such as the persistent homology dimension [BLGS21].

Our bounds show that for trajectory-stable algorithms, the topological complexities (i.e., lifetime sums and positive magnitude) have an important impact on the worst-case generalization error.
As opposed to existing trajectory-dependent topological bounds [SSDE20, BLGS21, DDS23, ADS^+24], our bounds do not feature any IT terms.
In addition to replacing IT terms with a stability assumption, the stability parameter $\beta_{n}$ acts as a multiplying constant in the bound, hence increasing the impact of the topological complexity on the bound.
Compared to the IT terms, $\beta_{n}$ is easily interpretable and can be expected to decrease with $n$ at a polynomial rate, as discussed above.

Despite being the first mutual information-free topological bounds, [Theorems 3.5](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem5) and [3.6](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem6) have three main disadvantages: (i) we only provide expected bounds, (ii) we obtain a slightly worse convergence rate in $n$ and (iii) our framework only allows for Euclidean-based topological complexity, and we typically do not cover the case of the data-dependent pseudometric introduced by [DDS23].
Regarding (ii), our results should be compared with [DDS23, Theorem 3.8], which employed a stability-like assumption to obtain smaller IT terms than existing works at the time. They obtained a convergence rate that is similar to [Theorems 3.5](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem5) and [3.6](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem6) but our results do not feature any IT term.

Stability parameters are expected to be affected by the sample size, hence, these results suggest to study the correlation between generalization error and topological complexity for several values of $n$, which forms a part of our empirical study.

###### Assumption 3.3 .

###### Assumption 3.4 .

###### Theorem 3.5 .

###### Theorem 3.6 .

## 4 Empirical Evaluations

We conduct all experiments with a Vision Transformer (ViT) [DBK^+21] on CIFAR-100 [KH^+09]. Additional implementation details are left for the appendix.

#### Experimental design

We follow the protocol of previous works [DDS23, ADS^+24] and train models until convergence ($>93\%$ training accuracy), and use this checkpoint as a starting point for analysis of topological quantities.
Our empirical analysis is then structured over a $4\times 4\times 5$ grid based on the following free variables: the number of training samples $n\in\{100,500,1000,5000,10000\}$, learning rates $\eta\in[10^{-6},10^{-4}]$, and batch sizes $b\in\{32,64,128,256\}$. We further investigated the stability parameter using a fixed learning rate of $10^{-6}$ and a batch size of $64$, testing across 10 different random seeds.
These analyses are conducted without any further regularization techniques or learning rate scheduling to minimize the effect of confounding factors.
All models are implemented in pytorch and trained with the ADAM optimizer.

#### Generalization error

As our theoretical results (see [Section 3](https://arxiv.org/html/2507.06775v1#S3)) provide bounds on the worst-case generalization gap $G_{S}(\mathcal{W}_{S,U})$, we seek to approximate this gap in practical settings.
Prior work has typically used one of two proxies: the generalization gap at the final iteration, computed as final test risk $-$ final train risk [BLGS21], or the worst observed test risk over time, computed as worst-case test risk $-$ final train risk [ADS^+24], where test risk was logged every $100$ iterations.
To improve granularity, we assess both train and test risk every iteration and report worst-case (test risk - train risk) over all iterations.

#### Computing topological complexity

We employ the Krylov subspace approximation method to compute $\mathbf{PMag}(\mathcal{W}_{S,U})$, utilizing the preconditioned conjugate gradient (PCG) algorithm [Sal21]. Our computation of the $\mathbf{E}^{\alpha}(\mathcal{W}_{S,U})$ is based on the giotto-ph library [PHL^+21], following the implementation of [ADS^+24], using $\alpha=1$, which they argue is the most empirically relevant.
In contrast to previous works [BLGS21, DDS23, ADS^+24], which focus on detailed correlation analysis, our goal is to investigate how different topological quantities behave as a function of the sample size $n$, and how they relate instead of correlate to generalization gap. Hence, we refrain from introducing the granulated Kendall coefficients [JNM^+19] and employ Pearson correlation coefficients to capture linear relationships. We present further correlation analysis in the appendix.

#### Distance matrix

The topological complexities that we consider in [Section 3](https://arxiv.org/html/2507.06775v1#S3) are based on the Euclidean metric over the weight trajectory.
Given a trajectory $\mathcal{W}_{S,U}$, the estimation of these quantities requires computing the distance matrix on all $\mathcal{W}_{S,U}$.
To make this tractable, we uniformly sample $1500$ points from the full training trajectory, which consists of $5000$ iterations.
Based on this sampled trajectory, we define the distance matrix using the Euclidean norm $\rho(w,w^{\prime}):=\left\|w-w^{\prime}\right\|$.

### 4.1 Results and Discussion

While previous works on topological generalization bounds [BLGS21, DDS23, ADS^+24] analyzed the correlation between generalization and topological complexities, the intractability of IT components has thus far prevented a more complete analysis of the bounds.
As our bound does not contain IT terms, relying primarily on the stability parameter defined by [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1) and the topological quantities introduced in Theorems [3.5](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem5) and [3.6](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem6), all the terms they contain are amenable to numerical estimation, which is a unique feature among topological bounds.
Next, we empirically characterize the interplay between stability and the topological complexities $\mathbf{E}^{\alpha}$ and $\mathbf{PMag}$.

Figure: Figure 1: Trajectory stability of the ViT for different training sample sizes $n$, for models with and without unseen injected samples $J$, for varying random seeds. The plot depicts models trained from a random initialization and converged pretrained models. We experiment with $\mathbf{Z}$ containing either validation or training points.
Refer to caption: x1.png

#### Stability Analysis

Our theoretical results depend on [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1), which involves the stability of the trajectories $\mathcal{W}_{S,U}$ and provides a noisy variant of [Definition 2.2](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition2).
In our experiments, we assessed the assumption by a direct estimation of the stability coefficient.
We focus on a condition similar to [Definition 2.2](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition2) to avoid technical complications.
Note that assuming the latter almost surely over $U$ is stronger than [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1) so that the experiments can serve as an upper bound of [Theorems 3.5](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem5) and [3.6](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem6).

To estimate the trajectory stability of each network, we replace a subset $\mathbf{J}$ of unseen samples for each training set $S\in\mathcal{Z}^{n}$ [Section 4](https://arxiv.org/html/2507.06775v1#S4), where $|\mathbf{J}|=50$.
After retraining the model with these perturbed datasets, we analyze the resulting trajectories $\mathcal{W}_{S,U}$ (original) and $\mathcal{W}_{S^{\prime},U}$ (perturbed).
We quantify stability by computing the worst-case deviation in model losses across all iterations, analogous to a Haussdorf distance across the trajectories: $\max_{w\in\mathcal{W}_{S,U}}\min_{w^{\prime}\in\mathcal{W}_{S^{\prime},U}}\sup
_{Z\in\mathbf{Z}}|\ell(w,Z)-\ell(w^{\prime},Z)|$, with $M:=\min\{n,500\}$ and $\mathbf{Z}:=\{Z_{1},\dots,Z_{M}\}$ a batch disjoint from $\mathbf{J}$, containing points either from the training or validation sets.
[Figure 1](https://arxiv.org/html/2507.06775v1#S4.F1) shows the results for different sample sizes, where other hyperparameters are fixed.
Note that we consider the loss difference over a batch $\mathbf{Z}$ of $m$ samples instead of taking the supremum over the whole dataset as in [Definition 2.2](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition2). This procedures forms a tractable empirical substitute for [Definition 2.2](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition2).
To contextualize with [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1) we report both the metric difference for train and validation sets.

The results are depicted in [Figure 1](https://arxiv.org/html/2507.06775v1#S4.F1).
With increasing $n$, and thus, a decreasing proportion of the replaced samples, we observe that the per-iteration loss difference decreases, which is in accordance with established theoretical results [HRS16, BFGT20] and [Lemma 3.2](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem2).
Importantly, we observe a stable behavior when computing the loss differences for both the training and validation sets, suggesting that trajectory stability could be attained in practical settings with non-convex objectives.

This experiment shows that trajectory stability can be expected to hold in such settings. This observation might serve as a basis to understand the empirical success of previous studies [BLGS21, DDS23, ADS^+24], in which the presence of the IT terms induced a discrepancy between theory and experiments.
Our framework bridges this gap by rendering the bounds tractable.
Moreover, [Figure 1](https://arxiv.org/html/2507.06775v1#S4.F1) suggests that stability holds when the experiment is started from a pre-trained weight, supporting previous findings that topological complexities correlate with $G_{S}(\mathcal{W}_{S,U})$ near convergence.
ve that when the model is pretrained to full convergence, the per-iteration loss differences reflect a built-in stability, more so than for randomly initialized models.

#### Topological Complexity Analysis

Figure: Figure 2: Evolution of $\mathbf{E}^{1}(\mathcal{W}_{S,U})$ and $\mathbf{PMag}(100)$ with increasing sample size $n$, for learning rates $\eta=10^{-4}$ and $\eta=10^{-5}$.
Refer to caption: x2.png

Our stability analysis shows that our assumptions hold both for large sample sizes $n$ as well as for randomly initialized and converged models. While the stability parameter is expected to decrease with increasing sample size, the behavior of the topological complexity as a function of $n$ has not been empirically studied in the literature.
We analyze the behavior of $\mathbf{E}^{1}(\mathcal{W}_{S,U})$ and $\mathbf{PMag}(100\cdot\mathcal{W}_{S,U})$ in [Figure 3](https://arxiv.org/html/2507.06775v1#S4.F3).
While our theory suggests letting the scale in $\mathbf{PMag}$ vary with $n$, we fix the scale to $100$, which is on the order of magnitude suggested by the theory.
This allows us to isolate the effect that $n$ has on $\mathcal{W}_{S,U}$ when observing the variations of the reported quantity.
We report these quantities for fixed learning rates to avoid confounding with large differences in generalization.
We observe that, with increasing sample size $n$, the values of $\mathbf{E}^{1}$ and $\mathbf{PMag}$ increase and seem to stabilize for large values of $n$.
This interesting observation leads to an interdependence between the sample size and the topology of the training trajectory, a notion that has not been reflected in prior works. We leave a detailed theoretical investigation as future work.

The behavior of $\mathbf{E}^{1}(\mathcal{W}_{S,U})$ as a function of $n$ might be puzzling at first, as we expect the generalization error and, hence, our bound to decrease with $n$. There is no contradiction here as the topological complexities $\mathbf{C}(\mathcal{W}_{S,U})$ should increase at most polynomially with $n$. Indeed, the positive magnitude is always bounded in terms of the number of iterations, and, based on persistent homology dimension and limiting arguments as $n\to\infty$, $\mathbf{E}^{\alpha}(\mathcal{W}_{S,U})$ also has sub-polynomial growth as $n\to\infty$ under mild assumptions (e.g., bounded trajectories), see for instance [BLGS21]. As argued in [Section 3](https://arxiv.org/html/2507.06775v1#S3), the stability coefficient $\beta_{n}$ decreases polynomially in many cases. As [Theorems 3.5](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem5) and [3.6](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem6) are logarithmic in $\mathbf{C}(\mathcal{W}_{S,U})$, this ensures that the bounds cannot be vacuous as $n\to\infty$.

In [Figure 3](https://arxiv.org/html/2507.06775v1#S4.F3), we observe that the sensitivity of $\mathbf{E}^{1}(\mathcal{W}_{S,U})$ with respect to the generalization gap (i.e., the slope of the affine regression of $\mathbf{E}^{1}(\mathcal{W}_{S,U})$ by the value of $G_{S}(\mathcal{W}_{S,U})$) increases when $n$ gets larger, which is what is predicted by our theory. Indeed, our main theorems assert that $\log\mathbf{E}^{1}(\mathcal{W}_{S,U})$ should be (approximately) of order at least $\beta_{n}^{-1/3}G_{S}(\mathcal{W}_{S,U})$, which amounts to $n^{1/3}G_{S}(\mathcal{W}_{S,U})$ in the event that $\beta_{n}=\Theta(1/n)$. Therefore, our experimental results strongly support [Theorem 3.5](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem5).

Together, these observations unveil a strong coupling between stability and the topological complexity of the training trajectories.
Moreover, the topological complexities increase for large $n$ and therefore become more relevant to the bound.
The empirically observed coupling is supported by the theoretical results of [Section 3](https://arxiv.org/html/2507.06775v1#S3), through the product of the stability parameter $\beta_{n}$ and the topological complexities.

## 5 Concluding Remarks

In this work, we present novel topological generalization bounds by making an assumption on the stability of training trajectories, demonstrating that this condition holds under practical settings.
Based on this new framework, we obtain the first mutual information-free topological generalization bounds, which are, for the first time, tractable.
This addresses one of the key theoretical issues in an emerging area of research.
We empirically evaluate the interaction between the topological complexities, unveiling new connections between the sample size and the topology of the training trajectories.
Our results show a strong coupling between stability and topological complexity and reveal compelling new behavior for varying sample size $n$.
Empirical evidence supports our theoretical findings, suggesting a nuanced interplay between the stability-related and topological quantities that bound neural network generalization.

#### Limitations & future work

While our bounds are more tractable than previous approaches with IT terms, $\beta_{n}$ is still challenging to quantify in the general case.
Exploring suitable strategies to approximate this term poses exciting opportunities. On the theoretical side, the topological complexities based on the data-dependent pseudometric used in [ADS^+24] are still not compatible with our approach and incorporating them is an object of future studies.

#### Broader impact

Due to its generality, our framework of provable generalization bounds based on topological quantities and trajectory stability is not anticipated to have any specific negative impact.

#### Acknowledgements

The authors are grateful for the support of the Excellence Strategy of local and state governments, including computational resources of the LRZ AI service infrastructure provided by the Leibniz Supercomputing Center (LRZ), the German Federal Ministry of Education and Research (BMBF), and the Bavarian State Ministry of Science and the Arts (StMWK).
T. B. was supported by a UKRI Future Leaders Fellowship (MR/Y018818/1) as well as a Royal Society Research Grant (RG/R1/241402).
U.Ş. is partially supported by the French government under the management of Agence Nationale de la Recherche as part of the “Investissements d’avenir” program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). B.D. and U.Ş. are partially supported by the European Research Council Starting Grant DYNASTY – 101039676.

## References

- [ADS^+24]
Rayna Andreeva, Benjamin Dupuis, Rik Sarkar, Tolga Birdal, and Umut Simsekli.
Topological generalization bounds for discrete-time stochastic
optimization algorithms.
Advances in Neural Information Processing Systems,
37:4765–4818, 2024.
- [ALRS23]
Rayna Andreeva, Katharina Limbeck, Bastian Rieck, and Rik Sarkar.
Metric space magnitude and generalisation in neural networks.
In Topological, Algebraic and Geometric Learning Workshops
2023, pages 242–253. PMLR, 2023.
- [BE02]
Olivier Bousquet and André Elisseeff.
Stability and generalization.
J. Mach. Learn. Res., pages 499–526, 2002.
- [BFGT20]
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar.
Stability of stochastic gradient descent on nonsmooth convex losses.
In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin,
editors, Advances in Neural Information Processing Systems, volume 33,
pages 4381–4391. Curran Associates, Inc., 2020.
- [BGND^+19]
Rickard Brüel-Gabrielsson, Bradley J Nelson, Anjan Dwaraknath, Primoz
Skraba, Leonidas J Guibas, and Gunnar Carlsson.
A topology layer for machine learning.
arXiv preprint arXiv:1905.12200, 2019.
- [BKZ20]
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy.
Sharper bounds for uniformly stable algorithms.
In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of
Thirty Third Conference on Learning Theory, volume 125 of Proceedings
of Machine Learning Research, pages 610–626. PMLR, 09–12 Jul 2020.
- [BLGS21]
Tolga Birdal, Aaron Lou, Leonidas J Guibas, and Umut Simsekli.
Intrinsic dimension, persistent homology and generalization in neural
networks.
Advances in Neural Information Processing Systems,
34:6776–6789, 2021.
- [BM02]
Peter Bartlett and Shahar Mendelson.
Rademacher and Gaussian Complexities: Risk Bounds and Structural
Results.
Journal of Machine Learning Research, 2002.
- [DBK^+21]
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn,
Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg
Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.
An image is worth 16x16 words: Transformers for image recognition at
scale.
In International Conference on Learning Representations, 2021.
- [DDS23]
Benjamin Dupuis, George Deligiannidis, and Umut Simsekli.
Generalization bounds using data-dependent fractal dimensions.
In International conference on machine learning, pages
8922–8968. PMLR, 2023.
- [DV23]
Benjamin Dupuis and Paul Viallard.
From mutual information to expected dynamics: New generalization
bounds for heavy-tailed sgd, 2023.
- [DVDS24]
Benjamin Dupuis, Paul Viallard, George Deligiannidis, and Umut Simsekli.
Uniform generalization bounds on data-dependent hypothesis sets via
PAC-bayesian theory on random sets.
Journal of Machine Learning Research, 25(409):1–55, 2024.
- [FGK^+19]
Dylan J Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, and
Karthik Sridharan.
Hypothesis set stability and generalization.
Advances in Neural Information Processing Systems, 32, 2019.
- [FV19]
Vitaly Feldman and Jan Vondrak.
High probability generalization bounds for uniformly stable
algorithms with nearly optimal rate.
In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the
Thirty-Second Conference on Learning Theory, volume 99 of Proceedings
of Machine Learning Research, pages 1270–1279. PMLR, 25–28 Jun 2019.
- [FZY^+24]
Jingwen Fu, Zhizheng Zhang, Dacheng Yin, Yan Lu, and Nanning Zheng.
Learning trajectories are generalization indicators.
Advances in Neural Information Processing Systems, 36, 2024.
- [HKND19]
Christoph Hofer, Roland Kwitt, Marc Niethammer, and Mandar Dixit.
Connectivity-optimized representation learning via persistent
homology.
In International conference on machine learning, pages
2751–2760. PMLR, 2019.
- [HKNU17]
Christoph Hofer, Roland Kwitt, Marc Niethammer, and Andreas Uhl.
Deep learning with topological signatures.
Advances in neural information processing systems, 30, 2017.
- [HRS16]
Moritz Hardt, Ben Recht, and Yoram Singer.
Train faster, generalize better: Stability of stochastic gradient
descent.
In International conference on machine learning, pages
1225–1234. PMLR, 2016.
- [HSKM22]
Liam Hodgkinson, Umut Simsekli, Rajiv Khanna, and Michael Mahoney.
Generalization bounds using lower tail exponents in stochastic
optimizers.
In International Conference on Machine Learning, pages
8774–8795. PMLR, 2022.
- [HYL17]
Will Hamilton, Zhitao Ying, and Jure Leskovec.
Inductive representation learning on large graphs.
In Advances in neural information processing systems, pages
1024–1034, 2017.
- [JNM^+19]
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy
Bengio.
Fantastic generalization measures and where to find them.
arXiv preprint arXiv:1912.02178, 2019.
- [KB14]
Diederik P Kingma and Jimmy Ba.
Adam: A method for stochastic optimization.
arXiv preprint arXiv:1412.6980, 2014.
- [KH^+09]
Alex Krizhevsky, Geoffrey Hinton, et al.
Learning multiple layers of features from tiny images.
2009.
- [KLS06]
Gady Kozma, Zvi Lotker, and Gideon Stupp.
The minimal spanning tree and the upper box dimension.
Proceedings of the American Mathematical Society,
134(4):1183–1187, 2006.
- [Lei13]
Tom Leinster.
The magnitude of metric spaces.
Documenta Mathematica, 18:857–905, 2013.
- [MBM^+17]
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan
Svoboda, and Michael M Bronstein.
Geometric deep learning on graphs and manifolds using mixture model
cnns.
In Proceedings of the IEEE conference on computer vision and
pattern recognition, pages 5115–5124, 2017.
- [Mec13]
Mark W Meckes.
Positive definite metric spaces.
Positivity, 17(3):733–757, 2013.
- [Mec15]
Mark W Meckes.
Magnitude, diversity, capacities, and dimensions of metric spaces.
Potential Analysis, 42:549–572, 2015.
- [Mol17]
Ilya Molchanov.
Theory of Random Sets.
Number 87 in Probability Theory and Stochastic Modeling. Springer,
second edition edition, 2017.
- [PHL^+21]
Julián Burella Pérez, Sydney Hauke, Umberto Lupo, Matteo Caorsi, and
Alberto Dassatti.
giotto-ph: a python library for high-performance computation of
persistent homology of vietoris-rips filtrations.
arXiv preprint arXiv:2107.05412, 2021.
- [Sal21]
Shilan Salim.
The q-spread dimension and the maximum diversity of square grid
metric spaces.
PhD thesis, University of Sheffield, 2021.
- [Sch20]
Benjamin Schweinhart.
Fractal dimension and the persistent homology of random geometric
complexes.
Advances in Mathematics, 372:107291, 2020.
Publisher: Elsevier.
- [SSBD14]
Shai Shalev-Shwartz and Shai Ben-David.
Understanding machine learning: From theory to algorithms.
Cambridge university press, 2014.
- [SSDE20]
Umut Simsekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu.
Hausdorff dimension, heavy tails, and generalization in neural
networks.
Advances in Neural Information Processing Systems,
33:5138–5151, 2020.
- [SvEH^+23]
Sarah Sachs, Tim van Erven, Liam Hodgkinson, Rajiv Khanna, and Umut
Şimşekli.
Generalization guarantees via algorithm-dependent rademacher
complexity.
In The Thirty Sixth Annual Conference on Learning Theory, pages
4863–4880. PMLR, 2023.
- [SZ20]
Thomas Steinke and Lydia Zakynthinou.
Reasoning About Generalization via Conditional Mutual Information.
In Conference on Learning Theory (COLT), 2020.
- [TGRW^+24]
Charlie Tan, Inés García-Redondo, Qiquan Wang, Michael M. Bronstein,
and Anthea Monod.
On the limitations of fractal dimension as a measure of
generalization.
In Proceedings of the 38th Conference on Neural Information
Processing Systems (NeurIPS), 2024.
- [XTYY24]
Jing Xu, Jiaye Teng, Yang Yuan, and Andrew Yao.
Towards data-algorithm dependent generalization: a case study on
overparameterized linear regression.
Advances in Neural Information Processing Systems, 36, 2024.
- [ZBH^+17]
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.
Understanding deep learning requires rethinking generalization.
ICLR, 2017.
- [ZBH^+21]
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.
Understanding deep learning (still) requires rethinking
generalization.
Communications of the ACM, 64(3):107–115, 2021.
Publisher: ACM New York, NY, USA.
- [ZGRS23]
Lingjiong Zhu, Mert Gurbuzbalaban, Anant Raj, and Umut Simsekli.
Uniform-in-time wasserstein stability bounds for (noisy) stochastic
gradient descent.
In Thirty-seventh Conference on Neural Information Processing
Systems, 2023.

## Appendix A Trajectory Stability of Projected SGD on Nonconvex Problems

In [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1), we empirically demonstrate that [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1) is practical for modern neural networks like the Vision Transformer.
What follows is a formal result demonstrating that [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1) holds generally for projected Stochastic Gradient Descent (SGD) under a gradient Lipschitz condition.

Let us consider the projected SGD recursion on a loss function $\ell$, which can be non-convex. In particular, given a dataset $S=(z_{1},\dots,z_{n})\in\mathcal{Z}^{n}$, consider the following recursion:

$$ $\displaystyle w_{k+1}=\Pi_{R}\left[w_{k}-\eta_{k}\nabla\ell(w_{k},z_{i_{k+1}}) \right],$ (9) $$

where $i_{k}\in\{1,\dots,n\}$ is an index chosen at random at each iteration $k$ and $\Pi_{R}$ denotes the projection operator on the ball centered around 0 0 with radius $R$.
Here, we fix the batch size to $1$ for clarity.

The next result establishes the trajectory-stability of SGD on Lipschitz and smooth (i.e., gradient Lipschitz) loss functions and is an adaptation of [HRS16, Theorem 3.12] to our setting.

###### Corollary A.1 .

Fix $T\in\mathbb{N}$.
Suppose that Assumption [3.3](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem3) holds, $\ell$ is gradient Lipschitz:

$$ $\|\nabla\ell(w,z)-\nabla\ell(w^{\prime},z)\|\leq G\|w-w^{\prime}\|,$ $$

for some $G<\infty$ and the step-size satisfies $\eta_{k}\leq c/k$ for some $c<1/G$. Then the SGD recursion on $K$ iterations in ([9](https://arxiv.org/html/2507.06775v1#A1.E9)) is trajectory-stable with the stability parameter:

$$ $\displaystyle\beta_{n}=\frac{4LR}{n-1}\left(\frac{L}{GR}\right)^{\frac{1}{Gc+1 }}\sum_{k=1}^{T}k^{\frac{Gc}{Gc+1}}.$ $$

###### Proof.

To show the trajectory-stability of SGD, we will first show that it is argument-stable in the sense of Definition [2.1](https://arxiv.org/html/2507.06775v1#S2.Thmdefinition1), then we will use Lemma [3.2](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem2) to establish the trajectory stability.

To prove the argument stability, we almost exactly follow the steps in [HRS16, Theorem 3.12]. Let us consider a neighboring dataset $S^{\prime}=(z^{\prime}_{1},\dots,z^{\prime}_{n})\in\mathcal{Z}^{n}$ that differs from $S$ by one element, i.e., $z_{i}=z^{\prime}_{i}$ except one element. Consider the SGD recursion on $S^{\prime}$:

$$ $\displaystyle w^{\prime}_{k+1}=\Pi_{R}\left[w^{\prime}_{k}-\eta_{k}\nabla\ell( w^{\prime}_{k},z^{\prime}_{i_{k+1}})\right].$ $$

Since most of $S$ and $S^{\prime}$ coincide, at the first iterations it is highly likely that $w_{k}$ and $w^{\prime}_{k}$ will be identical, since they will pick the same data points. Let us denote the random variable $\kappa\geq 1$ that is the first time $z_{i_{\kappa}}\neq z^{\prime}_{i_{\kappa}}$. Consider $K\in\mathbb{N}$ with $1\leq K\leq T$. By using this construction, we have:

$$ $\displaystyle\mathbb{E}_{U}[\|w_{K}-w^{\prime}_{K}\|]=$ $\displaystyle\mathbb{E}_{U}\left[\|w_{K}-w^{\prime}_{K}\|\>\mathds{1}_{\kappa \leq t_{0}}\right]+\mathbb{E}_{U}\left[\|w_{K}-w^{\prime}_{K}\|\>\mathds{1}_{ \kappa>t_{0}}\right].$ $$

We now focus on the first term in the right-hand-side of the above equation:

$$ $\displaystyle\mathbb{E}_{U}\left[\|w_{K}-w^{\prime}_{K}\|\right]\leq$ $\displaystyle\mathbb{E}_{U}\left[(\|w_{K}\|+\|w^{\prime}_{K}\|)\>\mathds{1}_{ \kappa\leq t_{0}}\right]$ $\displaystyle\leq$ $\displaystyle 2R\>\mathbb{P}(\kappa\leq t_{0})$ $\displaystyle=$ $\displaystyle\frac{2Rt_{0}}{n}.$ (10) $$

The second parameter is upper-bounded in the proof of [HRS16, Theorem 3.12], which reads as follows:

$$ $\displaystyle\mathbb{E}_{U}\left[\|w_{K}-w^{\prime}_{K}\|\>\mathds{1}_{\kappa> t_{0}}\right]\leq\frac{2L}{G(n-1)}\left(\frac{K}{t_{0}}\right)^{Gc}.$ $$

By combining these two estimates, we obtain:

$$ $\displaystyle\mathbb{E}_{U}[\|w_{K}-w^{\prime}_{K}\|]\leq$ $\displaystyle\frac{2Rt_{0}}{n}+\frac{2L}{G(n-1)}\left(\frac{K}{t_{0}}\right)^{ Gc}.$ $$

Choosing

$$ $\displaystyle t_{0}=\left(\frac{L}{GR}\right)^{\frac{1}{Gc+1}}K^{\frac{Gc}{Gc+ 1}}$ $$

yields

$$ $\displaystyle\mathbb{E}_{U}[\|w_{K}-w^{\prime}_{K}\|]$ $\displaystyle\leq\frac{4R}{n-1}\left(\frac{L}{GR}\right)^{\frac{1}{Gc+1}}K^{ \frac{Gc}{Gc+1}}$ $\displaystyle=:\delta_{K}.$ $$

Since $\delta_{K}$ is independent of $S$ and $S^{\prime}$, this shows that the $k$-th iterate of SGD is $\delta_{k}$ argument-stable. Finally, we conclude by Lemma [3.2](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem2), that SGD is trajectory-stable with parameter

$$ $\displaystyle\beta_{n}=L\sum_{k=1}^{K}\delta_{k}.$ $$

This concludes the proof.
∎

Combining [Corollary A.1](https://arxiv.org/html/2507.06775v1#A4.EGx15) with our empirical evidence from [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1.SSS0.Px1), we demonstrate the practical validity of our assumption. In the subsequent analysis we provide the reasoning behind our main results, which are based on [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1).

###### Corollary A.1 .

###### Proof.

## Appendix B Omitted Proofs

In this section, we present in full details the omitted proofs of our main results in [Section 3](https://arxiv.org/html/2507.06775v1#S3).

Recent advances on topological generalization bounds are based on a data-dependent Rademacher complexity, leveraging PAC-Bayesian theory on random sets [DVDS24].
In our stability-based approach, the Rademacher complexity also plays a central role.
We define the standard Rademacher complexity [SSBD14, BM02] as:

###### Definition B.1 (Rademacher complexity) .

Let $\mathcal{W}$ be a set, $S\in\mathcal{Z}^{n}$, and $\boldsymbol{\epsilon}:=(\epsilon_{1},\dots,\epsilon_{n})\sim\mathcal{U}(\{-1,1
\})^{\otimes n}$ be i.i.d. Rademacher random variables (i.e., centered Bernoulli variables). We define:

$$ $\displaystyle\mathbf{Rad}_{S}(\mathcal{W}):=\mathbb{E}_{\boldsymbol{\epsilon}} \left[\sup_{w\in\mathcal{W}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\ell(w,z_{i}) \right].$ $$

Intuitively, the Rademacher complexity measures the ability of a model to fit random labels. Using this definition, we now establish our main result.

###### Definition B.1 (Rademacher complexity) .

### B.1 A key technical lemma: Rademacher bound for trajectory-stable algorithms

A key technical element of our approach is the following theorem, which presents an expected Rademacher complexity bound for the worst-case generalization error of trajectory-stable algorithms.

###### Theorem B.1 .

Let $S\sim\mu_{z}^{\otimes n}$ be a dataset. Let $J,K\in\mathbb{N}^{\star}$ be such that $n=JK$, and $\tilde{S}_{J}\in\mathcal{Z}^{J}$ be independent of $S$. Assume that algorithm $\mathcal{A}$ satisfies [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1) with parameter $\beta_{n}>0$, then:

$$ $\displaystyle\mathbb{E}\left[\sup_{w\in\mathcal{W}_{S,U}}(\mathcal{R}(w)- \widehat{\mathcal{R}}_{S}(w))\right]\leq 2\mathbb{E}\left[\mathbf{Rad}_{\tilde {S}_{J}}(\mathcal{W}_{S,U})\right]+2J\beta_{n}.$ $$

The proof is inspired by the data splitting technique used in [DDS23, Theorem 3.8], which we adapt to our purpose of using the trajectory stability assumption to remove the need for information-theoretic terms.

###### Proof.

In the following, we consider tree independent datasets $S,S^{\prime},S^{\prime\prime}\sim\mu_{z}^{\otimes n}$, with $S=(z_{1},\dots,z_{n})$ (and similar notation for $S^{\prime}$ and $S^{\prime\prime}$). Up to a slight change in the constant, we can without loss of generality consider $J,K\in\mathbb{N}^{\star}$ such that $n=JK$. We write the index et as a disjoint union as follows:

$$ $\displaystyle\{1,\dots,n\}=\coprod_{k=1}^{K}N_{k},$ $$

with for all $k$, $|N_{K}|=J$, where $\coprod$ denotes the disjoint union. We also introduce the notation $S_{k}\in\mathcal{Z}^{n}$, with:

$$ $\displaystyle\forall i\in\{1,\dots,n\},~{}(S_{k})_{i}=\left\{\begin{array}[]{ ll}z_{i}^{\prime},\quad i\in N_{k}\\ z_{i},\quad i\notin N_{k}\end{array}\right.$ $$

Given two datasets $S_{1},S_{2}\in\mathcal{Z}^{n}$, we also consider a measurable mapping $w(S_{1},S_{2})$ (whose existence is satisfied in our setting [Mol17]) such that, almost surely:

$$ $\displaystyle\omega(\mathcal{W}_{S_{1}},S_{2})\in\operatorname*{arg\,max}_{w \in\mathcal{W}_{S_{1}}}\left(\mathcal{R}(w)-\widehat{\mathcal{R}}_{S_{2}}(w) \right).$ $$

Recall that $\mathcal{W}_{S}\in\mathrm{CL}(\mathbb{R}^{d})$ (where $\mathrm{CL}(\mathbb{R}^{d})$ denotes the closed subsets of $\mathbb{R}^{d}$) is a data-dependent random trajectory, which we assume is a random compact set [Mol17].
Finally we recall the notation:

$$ $\displaystyle G_{S}(\mathcal{W}_{S,U}):=\sup_{w\in\mathcal{W}_{S,U}}\left( \mathcal{R}(w)-\widehat{\mathcal{R}}_{S}(w)\right).$ $$

We have:

$$ $\displaystyle\mathbb{E}\left[G_{S}(\mathcal{W}_{S,U})\right]$ $\displaystyle=\mathbb{E}\left[\mathcal{R}(\omega(\mathcal{W}_{S,U},S))- \widehat{\mathcal{R}}_{S}(\omega(\mathcal{W}_{S,U},S)))\right]$ $\displaystyle=\frac{1}{n}\mathbb{E}\left[\sum_{k=1}^{K}\sum_{i\in N_{k}}\left( \ell(\omega(\mathcal{W}_{S,U},S),z_{i}^{\prime\prime})-\ell(\omega(\mathcal{W} _{S,U},S),z_{i})\right)\right].$ $$

By Assumption [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1) there exists a measurable function $\omega^{\prime}:\mathrm{CL}(\mathbb{R}^{d})\times\mathcal{Z}^{n}\to\mathbb{R}^
{d}$ such that for any $z\in\mathcal{Z}$

$$ $\displaystyle\mathbb{E}_{U}[|\ell(\omega(\mathcal{W}_{S,U},S),z)-\ell(\omega^{ \prime}(\mathcal{W}_{S_{k},U},\omega(\mathcal{W}_{S,U}),S),z)|]\leq J\beta_{n}.$ $$

We now apply the stability assumption on each term of the sum to get:

$$ $\displaystyle\mathbb{E}\left[G_{S}(\mathcal{W}_{S,U})\right]$ $\displaystyle\leq 2J\beta_{n}+\frac{1}{n}\mathbb{E}\left[\sum_{k=1}^{K}\sum_{i \in N_{k}}\left(\ell(\omega^{\prime}(\mathcal{W}_{S_{k},U},\omega(\mathcal{W}_ {S,U},S)),z_{i}^{\prime\prime})-\ell(\omega^{\prime}(\mathcal{W}_{S_{k},U}, \omega(\mathcal{W}_{S,U},S)),z_{i})\right)\right]$ $\displaystyle\leq 2J\beta_{n}+\frac{1}{K}\mathbb{E}\left[\sum_{k=1}^{K}\sup_{w \in\mathcal{W}_{S_{k},U}}\frac{1}{J}\sum_{i\in N_{k}}\left(\ell(w,z_{i}^{ \prime\prime})-\ell(w,z_{i})\right)\right]$ $\displaystyle\leq 2J\beta_{n}+\frac{1}{K}\mathbb{E}\left[\sum_{k=1}^{K}\sup_{w \in\mathcal{W}_{S,U}}\frac{1}{J}\sum_{i\in N_{k}}\left(\ell(w,z_{i}^{\prime \prime})-\ell(w,z_{i}^{\prime})\right)\right],$ $$

where the last equation follows by linearity of the expectation independence by interchanging $z_{i}$ and $z_{i}^{\prime}$ for all $i\in N_{k}$. By noting that all the terms inside the first sum have the same distribution, we have:

$$ $\displaystyle\mathbb{E}\left[G_{S}(\mathcal{W}_{S,U})\right]$ $\displaystyle\leq 2J\beta_{n}+\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[\sup_{w \in\mathcal{W}_{S,U}}\frac{1}{J}\sum_{i\in N_{k}}\left(\ell(w,z_{i}^{\prime \prime})-\ell(w,z_{i}^{\prime})\right)\right]$ $\displaystyle=2J\beta_{n}+\mathbb{E}\left[\sup_{w\in\mathcal{W}_{S,U}}\frac{1} {J}\sum_{i\in N_{1}}\left(\ell(w,z_{i}^{\prime\prime})-\ell(w,z_{i}^{\prime}) \right)\right],$ $$

As $\mathcal{W}_{S,U}$ is independent of $S^{\prime}$ and $S^{\prime\prime}$, we can apply the classical symmetrization argument. More precisely, let $(\epsilon_{1},\dots,\epsilon_{n})\sim\mathcal{U}(\{-1,1\})^{\otimes n}$ be i.i.d. Rademacher random variables (i.e., centered Bernoulli random variables), independent from the other random variable. We have:

$$ $\displaystyle\mathbb{E}\left[G_{S}(\mathcal{W}_{S,U})\right]$ $\displaystyle\leq 2J\beta_{n}+\mathbb{E}\left[\sup_{w\in\mathcal{W}_{S,U}} \frac{1}{J}\sum_{i\in N_{1}}\epsilon_{i}\left(\ell(w,z_{i}^{\prime\prime})- \ell(w,z_{i}^{\prime})\right)\right]$ $\displaystyle\leq 2J\beta_{n}+\mathbb{E}\left[\sup_{w\in\mathcal{W}_{S,U}} \frac{1}{J}\sum_{i\in N_{1}}\epsilon_{i}\ell(w,z_{i}^{\prime\prime})\right]+ \mathbb{E}\left[\sup_{w\in\mathcal{W}_{S,U}}\frac{1}{J}\sum_{i\in N_{1}}(- \epsilon_{i})\ell(w,z_{i}^{\prime})\right]$ $\displaystyle=2J\beta_{n}+2\mathbb{E}\left[\sup_{w\in\mathcal{W}_{S,U}}\frac{1 }{J}\sum_{i\in N_{1}}\epsilon_{i}\ell(w,z_{i}^{\prime})\right].$ $$

Therefore, by denoting $\tilde{S}_{J}=(z_{i}^{\prime})_{i\in N_{1}}$, we obtain by definition of the Rademacher complexity that:

$$ $\displaystyle\mathbb{E}\left[G_{S}(\mathcal{W}_{S,U})\right]$ $\displaystyle\leq 2J\beta_{n}+2\mathbb{E}\left[\mathbf{Rad}_{\tilde{S}_{J}}( \mathcal{W}_{S,U})\right],$ $$

which is the desired result.
∎

This result is based on leveraging our stability assumption to enable the use of the classical symmetrization argument [SSBD14].
Compared to previously proposed modified Rademacher complexity bounds, [FGK^+19, SvEH^+23], the above theorem has the advantage of directly involving the Rademacher complexity of the data-dependent hypothesis set $\mathcal{W}_{S}$, which tightens the bound and makes it significantly more empirically relevant.

Compared to previous studies [FGK^+19, DVDS24], a drawback of our bound compared to these studies is that it only holds in expectation.
Moreover, while we directly involve the data-dependent trajectory $\mathcal{W}_{S}$, our Rademacher $\mathbf{Rad}_{\tilde{S}}(\mathcal{W}_{S})$ term uses an independent copy of the dataset, hence, losing some data dependence compared to the term $\mathbf{Rad}_{S}(\mathcal{W}_{S})$ obtained by [DVDS24]. That being said, we show that our techniques still recover certain topological complexities, at the cost of requiring an additional Lipschitz continuity assumption.
The Rademacher complexity term appearing in [Theorem B.1](https://arxiv.org/html/2507.06775v1#A2.Thmtheorem1) uses the data-dependent trajectory $\mathcal{W}_{S}$ and an independent dataset $\tilde{S}$ of size $J$. Following classical arguments [SSBD14, ADS^+24], we expect this term to behave as $\mathcal{O}(1/\sqrt{J})$, hence, optimizing the value of $J$ yields a bound of order $\mathcal{O}(\beta_{n}^{1/3})$.

###### Theorem B.1 .

###### Proof.

### B.2 Proof of Theorems 3.5 and 3.6

Before presenting the proof of [Theorems 3.5](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem5) and [3.6](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem6), we present two technical lemma, whose proof can be found in [ADS^+24]. The first lemma relates the Rademacher complexity to the $\alpha$-weighted lifetime sums.

###### Lemma B.2 .

Let $m\in\mathbb{N}^{\star}$, $S\in\mathcal{Z}^{m}$, and $\mathcal{W}\subset\mathbb{R}^{d}$ be a finite set. Assume that [3.4](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem4) and [3.3](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem3) hold. For any $\alpha\in(0,1]$, we have:

$$ $\displaystyle\mathbf{Rad}_{S}(\mathcal{W})\leq\frac{B}{\sqrt{m}}+B\sqrt{\frac{ 2\log(1+K_{n,\alpha}\mathbf{E}^{\alpha}_{\left\|\cdot\right\|}(\mathcal{W}))}{ m}},$ $$

with $K_{n,\alpha}:=2(2L\sqrt{n}/B)^{\alpha}$.

###### Proof.

This result is a particular case of a bound by [ADS^+24] as part of the proof of their Theorem 3.4. The assumptions of [ADS^+24, Theorem 3.4] are satisfied by [3.4](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem4) and [3.3](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem3), and by considering the Euclidean distance of $\mathbb{R}^{d}$ as a pseudometric on $\mathcal{W}$.
∎

The second lemma relates the Rademacher complexity to the positive magnitude introduced by [ADS^+24].

###### Lemma B.3 .

Let $m\in\mathbb{N}^{\star}$, $S\in\mathcal{Z}^{m}$, and $\mathcal{W}\subset\mathbb{R}^{d}$ be a finite set. Assume that [3.4](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem4) and [3.3](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem3) hold. Then, we have for any $\lambda>0$ that:

$$ $\displaystyle\mathbf{Rad}_{S}(\mathcal{W})\leq\frac{\lambda B^{2}}{2m}+\frac{1 }{\lambda}\log\left(\mathbf{PMag}(L\lambda\mathcal{W})\right).$ $$

This result was obtained in the proof of [ADS^+24, Theorem 3.5] under a quite general Lipschitz regularity condition. For the sake of completeness, we present the proof in our particular case, as it might be more concrete for some readers.

###### Proof.

Let us fix $S:=(z_{1},\dots,z_{m})\in\mathcal{Z}^{m}$.

The proof follows the same strategy as the proof of [ADS^+24, lemma B.13], with the difference that we use the definition of magnitude fo compact sets.
It was shown by [Mec15] that a finite set $\mathcal{W}$ has magnitude. More precisely, for any $\lambda>0$ there exists a vector $\beta_{s}:\mathcal{W}\to\mathbb{R}$, such that for any $a\in\mathcal{W}$ we have:

$$ $\displaystyle 1=\sum_{b\in\mathcal{W}}e^{-\lambda\left\|a-b\right\|}\beta_{ \lambda}(b).$ $$

Let $\epsilon=(\epsilon_{1},\dots,\epsilon_{m})\sim\mathcal{U}(\{-1,1\})^{\otimes m}$ be Rademacher random variables. By [3.3](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem3) we have for all $a\in\mathcal{W}$:

$$ $\displaystyle 1$ $\displaystyle\leq\sum_{b\in\mathcal{W}}e^{-\lambda L\left\|a-b\right\|}\beta_{ \lambda L}(b)_{+}$ $\displaystyle\leq\sum_{b\in\mathcal{W}}\exp\left(-\frac{\lambda}{m}\sum_{i=1}^ {m}|\ell(a,z_{i})-\ell(b,z_{i})|\right)\beta_{\lambda L}(b)_{+}$ $\displaystyle\leq\sum_{b\in\mathcal{W}}\exp\left(-\frac{\lambda}{m}\sum_{i=1}^ {m}\epsilon_{i}(\ell(a,z_{i})-\ell(b,z_{i}))\right)\beta_{\lambda L}(b)_{+}.$ $$

Therefore:

$$ $\displaystyle\exp\left(\frac{\lambda}{m}\sum_{i=1}^{m}\epsilon_{i}\ell(a,z_{i} )\right)\leq\sum_{b\in\mathcal{W}}\exp\left(\frac{\lambda}{m}\sum_{i=1}^{m} \epsilon_{i}\ell(b,z_{i})\right)\beta_{\lambda L}(b)_{+}.$ (11) $$

We apply it to the following choice of $a$:

$$ $\displaystyle a=a(\epsilon):=\operatorname*{arg\,max}_{a\in\mathcal{W}}\frac{ \lambda}{m}\sum_{i=1}^{m}\epsilon_{i}\ell(a,z_{i}).$ $$

Thus, by Jensen’s inequality, we have:

$$ $\displaystyle\mathbf{Rad}_{S}(\mathcal{W})$ $\displaystyle=\mathbb{E}_{\epsilon}\left[\max_{a\in\mathcal{W}}\frac{1}{m}\sum _{i=1}^{m}\epsilon_{i}\ell(a,z_{i})\right]$ $\displaystyle=\mathbb{E}_{\epsilon}\left[\frac{1}{m}\sum_{i=1}^{m}\epsilon_{i} \ell(a(\epsilon),z_{i})\right]$ $\displaystyle\leq\frac{1}{\lambda}\log\mathbb{E}_{\epsilon}\left[\exp\left( \frac{\lambda}{m}\sum_{i=1}^{m}\epsilon_{i}\ell(a(\epsilon),z_{i})\right)\right]$ $\displaystyle\leq\frac{1}{\lambda}\log\mathbb{E}_{\epsilon}\left[\sum_{b\in \mathcal{W}}\exp\left(\frac{\lambda}{m}\sum_{i=1}^{m}\epsilon_{i}\ell(b,z_{i}) \right)\beta_{\lambda L}(b)_{+}\right].$ $$

By [3.4](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem4), independence, and Hoeffding’s lemma, we obtain:

$$ $\displaystyle\mathbf{Rad}_{S}(\mathcal{W})$ $\displaystyle\leq\frac{1}{\lambda}\log\sum_{b\in\mathcal{W}}\prod_{i=1}^{m} \exp\left(\frac{4B^{2}\lambda^{2}}{8m^{2}}\right)\beta_{\lambda L}(b)_{+}$ $\displaystyle=\frac{1}{\lambda}\log\left(\exp\left(\frac{B^{2}\lambda^{2}}{2m} \right)\sum_{b\in\mathcal{W}}\beta_{\lambda L}(b)_{+}\right)$ $\displaystyle=\frac{\lambda B^{2}}{2m}+\frac{1}{\lambda}\log\mathbf{PMag}(L \lambda\cdot\mathcal{W}),$ $$

which is the desired result.
∎

We can finally prove [Theorems 3.5](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem5) and [3.6](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem6).

See [3.5](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem5)

###### Proof.

By [Theorem B.1](https://arxiv.org/html/2507.06775v1#A2.Thmtheorem1), we have (recall that $G_{S}$ has been defined in [Equation 3](https://arxiv.org/html/2507.06775v1#S1.E3)):

$$ $\displaystyle\mathbb{E}\left[G_{S}(\mathcal{W}_{S,U})\right]\leq 2\mathbb{E} \left[\mathbf{Rad}_{\tilde{S}_{J}}(\mathcal{W}_{S,U})\right]+2J\beta_{n},$ $$

with the notations of [Theorem B.1](https://arxiv.org/html/2507.06775v1#A2.Thmtheorem1) for $\tilde{S}_{J}$.
Now we can apply [Lemma B.2](https://arxiv.org/html/2507.06775v1#A2.Thmtheorem2) to obtain that:

$$ $\displaystyle\mathbb{E}\left[G_{S}(\mathcal{W}_{S,U})\right]\leq 2\left(\frac{ B}{\sqrt{J}}+B\mathbb{E}\left[\sqrt{\frac{2\log(1+K_{n,\alpha}\mathbf{E}^{ \alpha}_{\left\|\cdot\right\|}(\mathcal{W}_{S,U}))}{J}}\right]\right)+2J\beta_ {n},$ $$

We make the choice $J:=\beta_{n}^{-2/3}$, which we assumed for simplicity is an integer dividing $n$, so that it is a valid choice. This immediately gives the result.
∎

See [3.6](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem6)

###### Proof.

By [Theorem B.1](https://arxiv.org/html/2507.06775v1#A2.Thmtheorem1), we have (recall that $G_{S}$ has been defined in [Equation 3](https://arxiv.org/html/2507.06775v1#S1.E3)):

$$ $\displaystyle\mathbb{E}\left[G_{S}(\mathcal{W}_{S,U})\right]\leq 2\mathbb{E} \left[\mathbf{Rad}_{\tilde{S}_{J}}(\lambda L\mathcal{W}_{S,U})\right]+2J\beta_ {n},$ $$

with the notations of [Theorem B.1](https://arxiv.org/html/2507.06775v1#A2.Thmtheorem1) for $\tilde{S}_{J}$.
Now we can apply [Lemma B.2](https://arxiv.org/html/2507.06775v1#A2.Thmtheorem2) to obtain that for any $\lambda>0$, we have:

$$ $\displaystyle\mathbb{E}\left[G_{S}(\mathcal{W}_{S,U})\right]\leq 2\left(\frac{ \lambda B^{2}}{2J}+\frac{1}{\lambda}\log\left(\mathbf{PMag}(\lambda L\mathcal{ W}_{S,U})\right)\right)+2J\beta_{n}.$ $$

We make the change of variable $\lambda\to\lambda\sqrt{J}/B$, which gives that for any $\lambda>0$, we have:

$$ $\displaystyle\mathbb{E}\left[G_{S}(\mathcal{W}_{S,U})\right]\leq\frac{\lambda B }{\sqrt{J}}+\frac{2B}{\lambda\sqrt{J}}\log\mathbf{PMag}(\frac{\lambda L\sqrt{J }}{B}\mathcal{W}_{S,U})+2J\beta_{n}.$ $$

We make the choice $J:=\beta_{n}^{-2/3}$, which we assumed for simplicity is an integer dividing $n$, so that it is a valid choice. This immediately gives the result.
∎

###### Lemma B.2 .

###### Proof.

###### Lemma B.3 .

###### Proof.

###### Proof.

###### Proof.

### B.3 Proof of Lemma 3.2

See [3.2](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem2)

###### Proof.

Consider a data-dependent selection of $\mathcal{A}$, denoted $\omega(\mathcal{W},S)$, in the sense of [Definition 3.1](https://arxiv.org/html/2507.06775v1#S3.Thmdefinition1).
We consider a measurable mapping $\omega^{\prime}:\mathrm{CL}(\mathbb{R}^{d})\times\mathbb{R}^{d}\to\mathbb{R}^{d}$ such that for any closed set $\mathcal{W}\subset\mathbb{R}^{d}$ and any $w\in\mathbb{R}^{d}$, we have:

$$ $\displaystyle\omega^{\prime}(\mathcal{W},w)\in\operatorname*{arg\,min}_{w^{ \prime}\in\mathcal{W}}\left(\sup_{z\in\mathcal{Z}}|\ell(w,z)-\ell(w^{\prime},z )|\right).$ $$

Such a mapping can be constructed in our setting where the sets are compact and the loss continuous.
Consider two datasets $S,S^{\prime}$ in $\mathcal{Z}^{n}$ differing by $J$ elements. Let us denote:

$$ $\displaystyle\varepsilon:=\sup_{z\in\mathcal{Z}}\mathbb{E}_{U}\left[\left|\ell (\omega(\mathcal{W}_{S,U},S),z)-\ell(\omega^{\prime}(\mathcal{W}_{S^{\prime},U },\omega(\mathcal{W}_{S,U},S)),z)\right|\right]$ $$

We use the definition of $\omega^{\prime}$ and the Lipschitz-continuity of $\ell$ to obtain that:

$$ $\displaystyle\varepsilon$ $\displaystyle\leq\sup_{z\in\mathcal{Z}}\mathbb{E}_{U}\left[\max_{1\leq k\leq K }\left|\ell(\mathcal{A}_{k}(S,U),z)-\ell(\omega^{\prime}(\mathcal{W}_{S^{ \prime},U},\mathcal{A}_{k}(S,U)),z)\right|\right]$ $\displaystyle\leq\sup_{z\in\mathcal{Z}}\sum_{k=1}^{K}\mathbb{E}_{U}\left[\left |\ell(\mathcal{A}_{k}(S,U),z)-\ell(\omega^{\prime}(\mathcal{W}_{S^{\prime},U}, \mathcal{A}_{k}(S,U)),z)\right|\right]$ $\displaystyle\leq\sum_{k=1}^{K}\mathbb{E}_{U}\left[\sup_{z\in\mathcal{Z}}\left |\ell(\mathcal{A}_{k}(S,U),z)-\ell(\omega^{\prime}(\mathcal{W}_{S^{\prime},U}, \mathcal{A}_{k}(S,U)),z)\right|\right]$ $\displaystyle\leq\sum_{k=1}^{K}\mathbb{E}_{U}\left[\sup_{z\in\mathcal{Z}}\left |\ell(\mathcal{A}_{k}(S,U),z)-\ell(\mathcal{A}_{k}(S^{\prime},U),z)\right|\right]$ $\displaystyle\leq L\sum_{k=1}^{K}\mathbb{E}_{U}\left[\left\|\mathcal{A}_{k}(S, U)-\mathcal{A}_{k}(S^{\prime},U)\right\|\right]$ $\displaystyle=LJ\sum_{k=1}^{K}\delta_{k},$ $$

where the last step follows by applying the stability assumption $J$ times and the triangle inequality. The result follows by definition of the random trajectory stability assumption.
∎

###### Proof.

## Appendix C Additional Experimental Details

This section expands on our experimental analyis, providing additional discussion of the methodology, implementation details, and technical setup.

### C.1 Implementation Details

We implement training and validation loops in PyTorch Lightning Version $2.4$ using pytorch version $2.4.1$.
Both models are trained using the AdamW optimizer with a cosine annealing learning rate scheduler.

#### Vision Transformer (ViT)

The ViT is configured for image classification on the CIFAR100 dataset.
For the Vision Transformer on CIFAR100, we utilize a model with approximately 1.2 million parameters.
This represents a reduction in size compared to the ViT experiments in [ADS^+24], as the empirical analyses we conduct require substantially more experiments due to the expansion of training set size $n$ and thus storage of weight iterates.

The ViT processes 32x32 pixel images with 3 color channels, and a patch size of 4x4.
The transformer backbone consists of 6 layers, 8 attention heads and an MLP dimension of 512.
Dropout rates are set to 0.1 within the transformer blocks.
Training is performed with a base learning rate of $0.0005$, decaying to a minimum of $10^{-5}$ via cosine annealing.

#### GraphSage

In addition to the main paper results, we analyze GraphSAGE [HYL17] on the graph classification task for MNISTSuperpixels [MBM^+17].
It processes graphs where each node has a single input feature.
These features are initially projected to a hidden dimension of 128.
For graph-level predictions, node embeddings are aggregated using ‘mean’ global pooling, followed by a linear layer for classification into 10 classes.
The model uses 2-dimensional positional encodings (representing x,y coordinates), which are added to the node features.
We use 4 GraphSAGE convolutional layers with a dropout rate of 0.05, a base learning rate of 0.001, and weight decay of $0.0005$ to achieve an adequate generalization gap.

### C.2 Stability Analysis

We first elaborate on our procedure to estimate trajectory stability in [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1.SSS0.Px1).
The overall algorithm, a proxy to asses [3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1), is summarized in [Algorithm 1](https://arxiv.org/html/2507.06775v1#alg1).
Stability experiments were performed with a fixed learning rate ($\eta$) and batch size ($b$), while varying random seeds, as described in [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1.SSS0.Px1).
To ensure we capture two distinct training regimes, we analyze both randomly initialized and locally converged models; the latter is standard for the analysis of topological invariants [ADS^+24].
We train each model for 500 additional iterations when analyzing trajectory stability.

The same setup is then conducted twice: once with the replacement set $J$ [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1.SSS0.Px1), and once without.
Trajectory stability ([3.1](https://arxiv.org/html/2507.06775v1#S3.Thmtheorem1)) is then estimated through the Hausdorf distance over each pair of trajectories where all model parameters are fixed except for the replacement set $J$.

Figure: Algorithm 1 Stability Parameter Estimation

### C.3 Topological Complexity Analysis

In this section we detail our approach for weight trajectory analysis in terms of topological quantities, particularly experiments which demonstrate the relationship between stability and our topological complexity.

Following [ADS^+24], we fine-tune each model from a local minimum for an additional 5000 iterations after training to convergence.
We use a reduced parameter grid of $4\times 4$ for $\eta$ and $b$ ([ADS^+24] use $6\times 6$), due to computational constraints arising from the varying the training set size $n$.
Detailed hyperparameters are listed in [Table 1](https://arxiv.org/html/2507.06775v1#A3.T1).

**Table 1: Summary of hyperparameter configurations for Vision Transformer and GraphSage models.**
| Hyperparameter | Vision Transformer | GraphSage |
| --- | --- | --- |
| Sample Size ($n$) | $\{100,500,1000,5000,10000\}$ | $\{100,500,1000,5000,10000\}$ |
| Learning Rate ($\eta$) | $\{10^{-6},10^{-5},5\times 10^{-5},10^{-4}\}$ | $\{10^{-5},10^{-4},5\times 10^{-4},10^{-3}\}$ |
| Batch Size ($b$) | $\{32,64,128,256\}$ | $\{32,64,128,256\}$ |

### C.4 Hardware and Runtime

Models are trained on a cluster with 40GB A40/A100 GPUs; although the experiments are reproducible with lower memory requirements. For our grid experiments, computing topological features alongside hyperparameter variations (sample size, learning rate, and batch size) demanded approximately 57 GPU hours for GraphSage and 140 GPU hours for the Vision Transformer (ViT). In contrast, the stability analysis on the ViT required about 50 total GPU hours.

## Appendix D Additional Empirical Results

In this section, we present additional empirical analyses and further substantiate the main paper analysis in [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1.SSS0.Px1) and [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1.SSS0.Px2).

### D.1 Stability Estimation

In this section, we continue with the analysis of [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1.SSS0.Px1).
We observe that, for both seen and unseen samples, an increase in sample size leads to a decrease in the estimated stability parameter (see [Table 2](https://arxiv.org/html/2507.06775v1#A4.T2)).
As shown in [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1.SSS0.Px1) and [Table 2](https://arxiv.org/html/2507.06775v1#A4.T2), the locally converged model demonstrates comparable stability between seen and unseen samples, with values similar to those of the randomly initialized model. This empirical evidence suggests that our trajectory stability assumptions are both theoretically sound and practically achievable in real-world applications.

Table: Table 2: Stability Analysis of Loss Differences Across Pretraining Iterations and Dataset Sizes for ViT Cifar100 (1.2M).

### D.2 Topological Complexity Analysis

Building on the empirical analysis in [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1.SSS0.Px2), we elaborate further on how our topological complexities evolve with dataset size $n$.

#### Vision Transformer

[Table 3](https://arxiv.org/html/2507.06775v1#A4.T3) reports topological quantities for multiple scaling parameters of the positive magnitude, as well as $\mathbf{E}^{1}$.
We observe a consistent trend across all topological features, mirroring the patterns identified in [Section 4.1](https://arxiv.org/html/2507.06775v1#S4.SS1.SSS0.Px2).
This suggests that the observed behavior is not isolated to a specific topological quantity.

#### GraphSage

In addition to the experiments on the Vision Transformer, we validate our observation on a conceptually different model.
We conduct the same experiment for GraphSage, as introduced in [Section C.1](https://arxiv.org/html/2507.06775v1#A3.SS1).
In these experiments, we similarly observe an increase in the magnitude of topological complexities with increasing sample size $n$.
[Figure 5](https://arxiv.org/html/2507.06775v1#A4.F5) depicts a representative example.

While a similar behavior of increasing slope is apparent for GraphSage, the overall pattern is less apparent.
This can be partially attributed to the larger discrepancies in the generalization gap, which are more difficult to modulate precisely by varying $\eta$ and $b$.

Nevertheless, as seen in the relationship between the generalization gap and $\mathbf{E}^{1}$ [Figure 5](https://arxiv.org/html/2507.06775v1#A4.F5), the slope similarly trends upwards with sample size $n$.

We additionally report positive magnitude for scaling that is theoretically supported ($\sqrt[3]{n}$), and the fixed scale $\mathbf{PMag}(100\cdot\mathcal{W_{S}})$.
For the theoretically supported scales of $\mathbf{PMag}(\sqrt[3]{n}\cdot\mathcal{W_{S}})$, we observe a similar tendency of an increase in slope.
Because the positive magnitude intuitively represents the effective number of distinct points in a space at a given scale $\lambda$, excessively large values of $\lambda$ can produce distorted and uninformative quantities.
This occurs as fine-grained structural details are lost when the scale exceeds meaningful topological variations.

Figure: Figure 4: Topological invariants $\mathbf{E}^{1}$ and PMag for GraphSage on MNISTSuperpixel. PMag is depicted for the fixed scale of 100. The mean and std. err. over the batch sizes are shown for learning rates $10^{-4},10^{-3}$.
Refer to caption: x4.png

Table: Table 3: We report the Kendall correlation coefficient $\tau$, the Pearson correlation coefficient $r$, and the slope for the Vision Transformer model on Cifar100. Bolded values denote the theoretically optimal scaling parameter of $\mathbf{PMag}$ corresponding to sample size n.

Table: Table 4: We report the Kendall correlation coefficient $\tau$, the Pearson correlation coefficient $r$, and the slope for the GraphSage model on MNISTSuperpixel. Bolded values denote the theoretically optimal scaling parameter of $\mathbf{PMag}$ corresponding to sample size n.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Could you please explain the advantage of your defined random set stability in detail compared with others? What if you change $\omega'$ in Assumption 3.1 into $\omega(\mathcal{W}_{S',U},S')$?
2. Is there any possibility of deriving high-probability generalization bounds?
3. Have you explored any efficient estimation methods for the stability parameter $\beta_n$ that avoid complete retraining after sample replacement?
soundness: 3
strengths: 1. This paper introduces the novel concept of random set stability, creatively integrates algorithmic stability with a data-dependent random set framework, successfully avoids intractable mutual information terms in existing methods, and offers a fresh approach to deriving generalization bounds.
2. Through rigorous mathematical deductions, this paper completes theorem proofs and the recovery of classical bounds, while conducting systematic experiments on real datasets using ViT and GraphSage models to validate the effectiveness and tightness of the proposed bounds.
3. This paper provides the first fully computable topological/fractal generalization bounds free of mutual information terms, addresses the core limitation of previous related studies where complexity measures were hard to implement, and advances the application of learning theory in practical algorithms.
summary: This paper addresses the challenge of deriving practical worst-case generalization bounds for stochastic optimization algorithms. It introduces random set stability, a novel framework tailored to data-dependent random sets (e.g., optimization trajectories), avoiding intractable mutual information terms in prior works. The framework bounds generalization error via the stability parameter and Rademacher complexity, recovering classical bounds and yielding computable topological bounds.
weaknesses: 1. This paper only provides expected generalization bounds instead of high-probability bounds, which limits the reliability of the framework in practical scenarios where probabilistic guarantees with strict confidence levels are needed.
2. Estimating the stability parameter requires replacing part of the training samples and retraining, leading to high computational costs in large-sample scenarios without proposing efficient optimization schemes.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: I am afraid I am by no means an expert in this field so my review will have pretty low confidence, but I would love it if the authors could clarify the following:

* Having a slower convergence rate seems like a really big downside. Can the authors please justify why they think this is an acceptable trade-off just to get rid of the information-theoretic terms in the bounds?
* Is the estimation procedure of $\beta_n$ defensible? Assumption 3.1 says that the stability parameter must hold for _any_ value $z \in \mathcal{Z}$, but algorithm 1 simply calculates the maximum over 1000 samples drawn from the training distribution (half seen, half unseen). This seems like a very optimistic estimate. What about points that fall outside of the training distribution? And is 1000 points really enough to estimate this supremum given the high dimensionality of the data? Would it be better to do some sort of hill climbing/optimization to find points for which the difference is large? My concern is that if this estimate is an under-estimate, than all the empirical results will seem much tighter than they actually are, right?
soundness: 3
strengths: * Novel stability framework that unifies point-wise points and uniform convergence bounds (by interpolating $J$)
* Computable components
summary: This paper proposes a new theoretical framework to explain generalization in deep learning by analyzing the entire training trajectory. To avoid often uncomputable "information-theoretic" (IT) terms found in previous work the authors introduce "random set stability", a measure of how much the worst-case loss along the whole trajectory changes when training data is changed. They show that common algorithms (such as projected SGD) are stable, and then they derive a generalization bound that combines this random set stability parameter and a Rademacher complexity term, recovering some previous bounds as special cases. They claim this offers the first fully computable bound and validate the approach empirically on ViT and GraphSAGE, showing correlations between their bound's components and actual generalization gaps.
weaknesses: * Bound has convergence rate of $O(n^{−1/3})$ rather than the usual $O(n^{−1/2})$
* The empirical validation relies on a seemingly very optimistic estimate of the $\beta_n$ parameter
* Empirical results seem to suggest a bound > 1 on a 0-1 loss

---

confidence: 3
contribution: 2
initial_rating: 2
presentation: 1
questions: I have two technical clarification questions. 
(1) In Lemma 3.4 you assume ~S_J is independent of S, but in the symmetrization step (and later discussion) it seems you need ~S_J to be independent of the random set W_{S,U}, which depends on both S and the algorithmic randomness U. Should the assumption be ~S_J ⟂ (S,U)? If not, how do you justify symmetrization when the index class is random and data-dependent? 

(2) In the projected-SGD corollary, the text summarizes the stability as O(T²/n), but the displayed expression appears to scale like (∑_t η_t)(∑_s η_s L²)/n; how does this reconcile with classical uniform-stability rates O((∑_t η_t)/n)? Could you clarify the precise assumptions (Lipschitz/smoothness/convexity), step-size regime, and whether there’s a typo in the exponents/summary rate?
soundness: 3
strengths: This paper studies an important and fundamental problem in generalization theory.
summary: This paper introduces random set stability, a notion tailored for data-dependent, stochastic hypothesis sets like optimization trajectories. The authors derive an expected worst-case generalization bound that combines this stability parameter (beta_n) with a Rademacher complexity term. This term is computed on the observed random set Cal W_{S,U} using an auxiliary, independent sample. The central claim is that this framework provides computable, trajectory-based bounds without relying on the intractable mutual information (MI) terms that are common in related topological and fractal-based analyses.
weaknesses: The main weakness of the paper is the writing: it is very dense and the authors don't spend time in giving intuitions etc. Lets consider introduction. The summary of contribution involves discussion on beta_n without precisely defining it. Another example is Definition 3.1, what is G_S'(w)? the definitions need to be self-contained! Lemma 3.2 talks about trajectory-stability. IT hasn't defined clearly. How one can understand the statements?

In this version of the paper, it is very difficult to judge the contribution of this paper.


The other drawback is that this paper mentions that mutual information based bounds are difficult to estimate. For many optimization algorithms, we have results that implies mutual information terms in the bounds can be upper-bounded by simple quantities. For example, look at the following papers:

Negrea, Jeffrey, et al. "Information-theoretic generalization bounds for SGLD via data-dependent estimates." Advances in Neural Information Processing Systems 32 (2019).

Neu, Gergely, et al. "Information-theoretic generalization bounds for stochastic gradient descent." Conference on Learning Theory. PMLR, 2021.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: - See weaknesses
- l. 125: unclear what is z_{i,j}
soundness: 2
strengths: 1. The paper is clearly structured and articulated.
2. The ability to numerically evaluate these bounds presents a clear advantage over Mutual Information based relatives.
summary: This work introduces an interesting class of generalization bounds based on “random set stability”, which is tied to the stability across the parameter trajectory of the algorithm. The aim of these bounds is to bound the worst-case generalization gap across a given window of the trajectory. Crucially, this bound is, unlike information-theoretic relatives, rather straightforward to compute. The authors conclude with experiments on Vision Transformers and GraphSage.
weaknesses: 1. Unless one employs early stopping, the trajectory window at the end of training (assuming near convergence in parameter space) should be essentially a single point, plus tiny fluctuations. I believe that this might lead the presented bounds to be overtly optimistic in near-convergence training settings which is an important and prevalent setting in machine learning. This seems to be consistent to what is written around line 428.
2. In deep learning, Lipschitz constants are typically very large (roughly exponential in the depth). This might further subtract from the achievable accuracy of the presented generalization bounds.
3. I appreciate the inclusion of experiments. However, the results left me a bit confused. It is claimed (and seems to be experimentally supported) that a magnitude scale $\approx \beta_n^{-1/3}$ is a sound choice. This suggests that the bounds in Thm. 4.4 should become better as $n$ increases. However it seems that the bounds in fact become worse for larger sample size (e.g. Pearson correlation $0.28$ for GraphSage with n=10k). Could you please give me your thoughts on this?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - Aside from uniform stability that considers the upperbound of hypothesis/loss change, there has been on-average stability that replaces $\sup$ with expectation (eg, [4]), which is usually tighter and easier to estimate. Is it possible to integrate this on-average form into the random-set stability. Will that improve both tightness and estimation (related to my Weakness 4)?




### References

[4] Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pp. 5809–5819, 2020.
soundness: 3
strengths: - This paper reveals valuable problems in existing works of worst-case generalization, and thereby is well motivated. This problem is interested not only for worst-case bounds, but also in other topics, eg, generalization bounds using mutual information.  
- This paper provides novel stability-based worst-case bounds with tractable quantities. The bounds not only recover several classic bounds, but also can be used with recent fractal-based complexities.
- In experiments, the bounds are non-vacuous in many cases. 
- The paper is well written and clear to follow.
summary: This paper focuses on worst-case generalization on the weight trajectory/data-dependent set. The paper identifies that existing worst-case bounds have the following problems: They involve intractable information-theoretic or combinatorial nature quantities that are hard to compute, or they ignore the randomness of the algorithms.
This paper then develops random-set stability that considers algorithmic randomness and proves worst-case generalization gap can be bounded together by the stability and Rademacher complexity or fractal-based complexities. Empirical results show that the bounds are non-vacuous in many cases and successfully predict the interplay between the stability and fractal-based complexities.
weaknesses: 1. The auto-satisfaction of local Lipschitzness in Line 315 seems incorrect because the Lipschitzness is not local wrt $z$. For example, for loss $\\ell(w, z) = \\|w - z\\|\_2^2$ and some unbounded $\\mathcal{Z} \\subseteq \\mathbb{R}^d$, then one would have infinite $L_{S, U}$. More practically, one may have very large $L_{S, U}$ thanks to some samples $z$ (eg, $z$ that is out of distribution so that the trained weights drastically disagree on them, as in domain generalization scenes). 
 2. The paper has provided comprehensive discussion on existing works in trajectory-worst-case generalization bounds and reveals the problem of them. However, beyond these works, mutual-information-based bounds have also tried to solve similar problems of having unbounded IT quantities, which are not cited and discussed in this paper. For example, see [1,2,3] listed below. They essentially inject virtual random (which is also emphasized in this paper) noise and transform unbounded MI terms into bounded and easy-to-estimate MI terms (similar to stability in some sense) and robustness against the noises (similar to complexity and local Lipschitzness). Their drawbacks at least include reliance on local approximation, and assumptions or reliances on testing loss robustness which requires extra samples (like $\tilde{S}$ to estimate Rademacher complexity).
 3. One motivation of the paper is that algorithmic randomness is "paramount to deriving stability-based bounds". However, what specific benefits randomness brings are fully buried in the proof instead of being explained in the main text. 
     - I skimmed the proof of Lemma 3.4, where it seems that $U$ does not play important role. Indeed, if one sets $U$ to constant to remove randomness, the proof of course still goes well. It seems the improvement of Lemma 3.4 (eg, the form of empirically relevant Rad + stability) over existing bounds mainly come from some detailed technical improvement instead of exploitation of randomness $U$ (please correct me if wrong). 
     - Nevertheless, it seems that randomness $U$ indeed plays important role in reducing $\beta_n$: If randomness is not used, then one has to incorporate randomness by seeing training algorithm instances with seed $U$ (like partial application) as fixed algorithms with different (Foster-style) stability $\beta_{n, U}$, and taking expectation over $U$ (sth like $\\mathbb{E}\_{U} \\mathbb{E}[G_S(\\mathcal{A}\_U(S))] \\le \\mathbb{E}\_{U}[\\dots]$). Then one has to take maximum of $\beta_{n, U}$ over $U$, where some bad $U$ brings extreme looseness. In contrast, with this paper's random-set stability, one essentially replaces this maximum with expectation, which significantly down-weights those bad $U$s.
 4. In experiments, the uniform stability is estimated by taking empirical maximum over hundreds of samples, which is obviously negatively biased. 
 5. The motivation and goal of "interplay" experiments are not quite clear to me. Is it validating the theoretical prediction that generalization is approximately proportionate to the complexity with the random-set stability as the factor that decreases as the training set increases? But from Table 1, learning rate, which is altered in the interplay experiments, can drastically change stability, and we should not expect a stable proportionate relation at all.
 6. Minor typos:
     - Lines 035,059,083,167,169,189...: one should use `\citep{}` for these citations
     - Line 866: "index et" -> "index set"?
     - Line 877: "$\omega(S_1, S_2)$" -> "$\omega(\mathcal{W}_{S_1}, S_2)$"?
     - A lot of missing $U$ in the proof of Lemma 3.4?



### References

[1] Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M. Roy. Information-theoretic generalization bounds for Stochastic Gradient Descent. In Proceedings of Thirty Fourth Conference on Learning Theory, pp. 3526–3545. PMLR, 2021.

[2] Ziqiao Wang and Yongyi Mao. On the generalization of models trained with SGD: Information-theoretic bounds and implications. In International Conference on Learning Representations. ICLR, 2022.

[3] Ze Peng, Jian Zhang, Yisen Wang, Lei Qi, Yinghuan Shi, and Yang Gao. Leveraging Flatness to Improve Information-Theoretic Generalization Bounds for SGD. In International Conference on Learning Representations. ICLR, 2025.


Decision: Reject