Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms

We thank the reviewer for their time spent on the paper and their insightful comments.

We address below the main questions (alongside weaknesses).

Could you give (for, say, theorem 3.4) a sort of "sketch of proof" and more intuition on "why this should be true"?

First, we would like to point our that even though the appendix is long, most of it is dedicated to additional empirical results and figures, while the proofs are a relatively short portion of the appendix.

Including a sketch of proof is a very good suggestion from the reviewer. In the next version of the paper, we now include a sketch of proof of Theorem 3.4. The general idea is the following: we build on Corollaries 26 and 27 of the reference [18] of our paper, to get a bound of the worst-case generalization error as (this is an informal statement, in particular we omit absolute constants and less relevant terms, refer to the paper for more details):

$$G \lesssim \sqrt{\frac{N_\delta}{n}} + \sqrt{\frac{\mathrm{IT}}{n}},$$

where $N_\delta$ is a covering number of the trajectory and $\mathrm{IT}$ is an information-theoretic term. First, we use lemma 16 of [11] to show that $\mathrm{IT}\leq I_\infty$, where $I_\infty$ is the mutual information term appearing in Theorem 3.4. Second, we bound $N_\delta$ in terms of packing numbers, denoted $P_\delta$ (see Definition A.15), which we further bound in terms of $E_1$ (or in general $E_\alpha$ for $\alpha \leq 1$) using a geometric construction displayed on Figure 2.b (rebuttal pdf). We have now included this figure to the paper to provide more intuition on the proof technique, which is based on this geometric observation.

For theorem 3.5, we can mention that the key difference is Lemma B.13, whose proof is short but contains the essential ideas behind this theorem. It relies on properties of magnitude that are detailed in the appendix.

Related to above, in Thm 3.4 (and 3.5), the r.h.s. depends on many parameters on which the l.h.s. doesn't. For instance, it seems that I could pick a different $\rho$ or $\alpha$ without affecting the l.h.s. Is that correct? Could I just try to find a $\rho$ that makes $E_\alpha^\rho$ close to $1$ in order to improve my bound?

It is true that some of our bounds depend on free parameters. As noted by the reviewer, this is in particular true for the constant $\alpha \in [0,1]$ and the pseudometric $\rho$, as soon as $\rho$ satisfies the regularity condition given by Definition 3.1. Let us discuss these two quantities separately.

Choice of $\alpha$

First, regarding the choice of $\alpha$, the only pertinent choice in general seems to be $\alpha=1$, which is what we choose in our experiments. The reason why this choice is natural is that the $\alpha$-weighted lifetime sums tend to be higher when $\alpha$ gets smaller. In the case where the random set is finite, $E_0$ even corresponds to the cardinality of the set and does not capture any meaningful topological behavior (moreover, it goes to infinity when the size of the set goes to infinity). The reviewer may consult [61] for better intuition about the behavior of this quantity.

Choice of $\rho$ and $q$

Second, for the choice of $\rho$, the possibilities might not always be numerous. Indeed, $\rho$ must satisfy a $(q,L,\rho)$ condition as in Definition 3.1. The choice of $\rho$ impacts the bound both by affecting the topological quantity ($E_\alpha^\rho$ in the case of Theorem 3.4) and the value of $q$ and $L$. It should be noted that the pseudometrics $\rho_S^{(q)}$ (with $q\geq 1$) appear in Example 3.2 always satisfy the $(q,1,\rho_S^{(p)})$-Lipschitz condition. In that particular case, it seems that choosing $\rho_S := \rho_S^{(1)}$ is the best choice because of Hölder's inequality: $\forall q \geq 1,~ \rho_S \leq \rho_S^{(q)}$. The fact that $q=1$ is a good choice is particularly apparent in the proof of Theorem 3.5, for this exact reason. When more pseudometrics are admissible, the reviewer is right to notice that there could be an optimal choice giving the best bound. In the final version of the paper, we discuss in more detail the choice of these parameters.

I cannot understand the role of $\tau$ and $T$

The meaning of these parameters is that we collect the training trajectory between iterations $\tau$ and $T$. While it is technically possible to chose $\tau=T$, it means that the trajectory would be reduced to a single point and therefore it does not contain any interesting topological information. Similarly, taking $T\to\infty$ seems to be possible under mild assumptions, even though it is not our focus.

Note that our topological complexities also depends implicitly on $\tau$ and $T$, as they are evaluated on the trajectory between iterations $\tau$ and $T$.

Still in Thm 3.4, would it be in some sense possible that we pick $\alpha$ below the PH-dim of (roughly speaking) the possible support of the random set $W$, in which case (here again, this is informal) it may be possible that $E_\alpha$ is unbounded?

This is a pertinent question from the reviewer. In the case that is of more interest for our experiments, the random set $W$ is finite, which makes the $\alpha$-weighted lifetime sums bounded for any value of $\alpha$. That being said, if one extends our theory to infinite sets (which is technically possible for most aspects, even though some statements should be reformulated), the value of $\alpha$ should indeed be carefully chosen with respect to the dimension of the set. Even in our experimental setting, if the size of the set goes to infinity, it might be pertinent to take into account the dimension of the "limiting set" to tune the value of $\alpha$, keeping in mind that it must satisfy $\alpha \in [0,1]$. However, this setting is largely theoretical as the sets are large but finite in practice. In the final version of the paper, we added a discussion about this interesting question from the reviewer.

We thank the reviewer for their time and their insightful comments on our work.

Some of the benchmarking was more intuitive as the complexity compared to generalization charts as opposed to the Table 1 for instance, I don't know if that could be simplified in some fashion

We believe that Table 1 is quite informative (though compact) as it summarizes a lot of our empirical findings. In order to provide more visual representations of our results, we provided in Fig. 4.c a graphical representation of the performance of our topological complexities in the plane $(\psi_{\mathrm{bs}},\psi_{\mathrm{lr}})$. This figure contains part of the information of Table 1 along with additional pair (model, dataset). Fig. 1.c is also a graphical representations of the values of $\Psi$ reported in the table. These two figures therefore contain most of the information from the table. In the next version of the paper, we have completed them by additional plots similar to Fig. 1.c (see Fig. 2.a in the rebuttal pdf for an example). Note moreover that a wide range of plots in the appendix represent the topological complexities against the generalization error.

It is hard be this reviewer to fully assess the theoretical merit of the derivations

In order to improve the clarity of the paper, we now added to the main text (thanks to the additional page) a sketch of proof for our main results in the next version of the paper.

Can you further clarify your use of the term "connected components"?

Indeed, our use of the term "connected components" in Section 2 might not have been clear enough. It should be understood as follows: given a distance parameter $\delta>0$ and a point cloud $W$ (which could be one of our training trajectories for instance), we can construct a graph by connecting each pair of points at distance at most $\delta$ and count the number of connected components of the obtained graph. What we meant by "tracking the “connected components” of a finite set at different scales" consists in observing the evolution of these connected components when varying $\delta$. While this is just an informal introduction to the concept of persistent homology, we provide in Appendix A a more formalized description. In the next version of the paper, we are now more precise about it.

Should we interpret that as the number or ratio of weights impacted by a gradient update step? Am I interpretting correctly that with increased connectivity we could expect improved generatlization or is that too simplistic?

The reviewer is right in noticing that if only a ratio of weights are affected by the gradient steps, then the trajectory will be lower dimensional, which might make our topological complexities smaller. However, this is only a particular case and a too simple view of what is happening during training. The topological properties of the trajectory are the consequence of a complex iterative algorithm (see for instance reference [11] in the paper), and capture information that is more complicated than the ratio of updated weights. The emergence of connected components is considered in a complex recursive way, it is not related to the ratio of weights that are updated. Finally, the NTK is a specific limit with a particular scaling scheme, we do not believe that it can be compared to the observed behavior in our paper.

Do you expect that the generalization bounds are asymptotic towards scale of foundation models or can such assumptions be comparably extended to models of limited scope and scale?

While our work was the first to compute topological generalization measures on neural architecture with real practical interest, applying the same procedures on large language models or other foundation models would still be far too computationally expensive.

However, one could imagine a setup where neural networks are embedded in a lower dimensional representation and compute the topological quantities associated with the trajectories in this lower dimensional space. While additional theory would be necessary to understand the true impact of this compression procedure, this might open the door to the computation of topological measures for foundation models. This could be a direction for future research.

Can you clarify how training may be conducted in this form, eg for a simple supervised learning setup, am I correct in assuming that it would it be possible to replace the performance metric but the labels corresponding to training data still be required?

Regardless of the training procedure, the dataset, and the model, we need two things to compute our topological complexities: a training trajectory and a pseudometric satisfying the condition of Definition 3.1. If the metric is chosen carefully, it could theoretically be applied to any large model as soon as suitable computational resources are available. An interesting setting happens when a large model (eg, a foundation model) is finetuned on a dataset different from the dataset used for pretraining. In that case, to compute our topological complexities, one would only need the dataset used for the fine-tuning procedure and the training data for the inital large model would not be needed.

We thank the reviewer for their insightful review. Below we address all the raised concerns. We hope that the reviewer reconsiders their score in the light of our comments.

Before delving further, we would like to point out that our main focus is to obtain not just theoretical insights but also empirically meaningful quantities. We stress the importance of the latter, the extensive suite of evaluations proving that our topological quantities are meaningful and exhibit strong correlations. Our paper presents the first topological measures with an extensive set of experiments, obtained on practical models and complex data domains.

We have now included additional discussion on all the points listed below.

Validity of the assumptions.

Bounded loss

Let us emphasize that the bounded loss assumption is realistic in several practical settings (eg, for the $0-1$ loss) and that it has been largely used in the literature on topological bounds [17,18,29].

In Thm. 3.4, the scaling of $B$ will not affect the correlation. Indeed, if we multiply the loss by $c>0$, ie, $\ell':=c\ell$, and consider the data-dependent pseudometric $\rho_S$, then $E_1$ is also multiplied by $c$, hence the observed correlation is independent of the scaling factor. We now expand on these details in the paper.

Lipschitz assumption & applicability

First the $(1,1,\rho_S)$-Lipschitz condition is always satisfied for the data-dependent pseudometric $\rho_S$. Indeed, by definition, $\Vert L_S(w) - L_S(w') \Vert = n \rho_S(w,w')$. The $(1,L,\rho)$-Lipschitz condition becomes non-trivial when $\rho$ is the Euclidean distance. In that case, it requires $\ell(w,z)$ to be Lipschitz, which is relatively standard.

In our paper, we encapsulated both scenarios inside a single condition to identify the more general structure and pave the way for the use of other distances between models. Thus, our Lipschitz condition should not be seen as a limitation but rather a generalization.

Mutual Information. The MI term measures the dependence between the data $S$ and a random set $\mathcal{W}$. Its presence is inherited from prior topology-based generalization studies, which face the same issues [17,18,8,11,69,29]. These bounds can be decomposed as the sum of a topological and an MI part, yet, in prior works the topological part suffered from major drawbacks, which is the main focus of our paper. We aim at improving the topological part of the bound. Obtaining a clearer understanding of the remaining part is an important direction for our future research.

No method to estimate the MI term

We agree with the reviewer that the very complex structure of the MI term raises several difficulties. (1) we are not aware of existing techniques to evaluate MI between random sets and (2) the dimensionality of $\mathcal{W}$ (billions of parameters), could make a direct computation intractable. While these render the MI term uncomputable (as we mention in the limitations), our work focuses on the topological part. Our experiments show that these complexities are important and meaningful in addition to being amplified in the first part of the bound, as the dependence is explicit.

Nevertheless, as acknowledged by the reviewer, our definition of MI is much simpler than the prior works making it intuitive to understand.

Can this ensure uniform convergence?

We thank the reviewer for this very pertinent question. Let us first highlight that our use of the term "uniform" refers to the bound being uniform over the trajectory, i.e., we look at the worst-case error over the trajectory. In this context, our convergence is uniform.

As mentioned above, convergence can be ensured with similar information-theoretic terms (which we could use in our work) for particular algorithms, like SGLD [18]. However, in the most general case (eg, a deterministic algorithm), it could lead to vacuous bounds. We acknowledged this lack of understanding in the limitations and we will add further comments.

Sensitivity to hyperparameters. We thank the reviewer for suggesting this interesting sensitivity experiment. We performed an analysis of the sensitivity to $s$ for the ViT and CIFAR10 in Fig. 1.a (rebuttal pdf). We observe that the correlation is relatively stable near the two values of $s$ used in our study.

Note that our choice of $\sqrt{n}$ is theoretically motivated (see lines 216 to 221), and the choice of small $s$ comes from evidence in prior work. We have added these sensitivity experiments in the paper.

We introduced the parameter $\tau$ for two reasons: (1) to allow the use of pretrained weights and (2) to capture the geometric properties of the trajectory near a local minimum. Therefore, $\tau$ is chosen to ensure that the training is near convergence. We did not try to tune the parameter $\tau$ in any way.

Thank you for catching the conflict of notations, we will replace $\tau$ by $t_0$.

Comparison with other terms. As suggested by the reviewer, we conducted a small-scale experiment to compare our complexities with the gradient variance [31] in Fig. 1.b (rebuttal pdf). These preliminary results indicate a comparable correlation performance while slightly favoring our method. We have now included this experiment with gradient variance in the final version and will extend it to further settings.

On the other hand, the numerical comparison with conditional mutual information (CMI) bounds requires a rigorous re-adaptation of our models and datasets to the CMI analysis, which is not doable within the rebuttal period, but we will consider to try this experiment for the final version. We also point out that our complexities are expected to be much less computationally demanding than CMI. Indeed, one can evaluate them based on a single training and no supersample of data is necessary.

Finally, let us reiterate that, as opposed to most existing works, our measures are meant for the worst-case generalization error (see Section 4).

We thank the reviewer for their interesting comments.

Maybe I get this wrong but in line 113, is $Y\subset X$ or $Y\subset A$?

We thank the reviewer for pointing out this minor typo in the definition of the PH dimension. Indeed, we have replaced $Y\subset X$ by $Y\subset A$ in the final version of the paper.

1.- Have you explore the situation of use compact metric spaces?

We thank the reviewer for this interesting question/comment. Since we are interested in discrete optimizers, the most pertinent setting is that of discrete (even finite in practice) trajectories. However, it is interesting to ask whether our theory extends to random compact sets. As we hinted in Remark B.15 in the appendix, Theorem 3.5 (for positive magnitude) could be extended to such a compact setting. On the other hand, the extension of Theorem 3.4, involving $\alpha$-weighted lifetime sums, might be more complicated as the definition of $E_\alpha$ makes an explicit use of the finiteness of the set. However, we believe the main ideas of Theorem 3.4 could still be used to obtain interesting bounds in the compact setting and leave this question for future work. We have now added a further remark about it in the revision.

2.- Have you explore the situation of change the metric to a non-euclidean one?

As we explain in Section 3.1 (about the mathematical setup), our framework encompasses a wide range of metrics and pseudometrics, as long as they satisfy the condition given by Definition 3.1. In particular, an important part of our experiments uses the so-called data-dependent pseudometrics on $\mathbb{R}^d$, which we denote by $\rho_S^{(p)}$ in the paper. These pseudometrics are typically non-Euclidean on $\mathbb{R}^d$. While we use these non-Euclidean metrics, one can see in Example 3.2 that $\rho_S^{(p)}$ results from the Euclidean distance on $\mathbb{R}^n$ applied on the embedding $L_S(w)$ of $w$. It could be interesting to explore other non-Euclidean possibilities, which we leave for future work. For instance, if the loss is supported on a Riemannian manifold, then the associated metric could serve as a non-Euclidean metric to compute the topological complexities. One of the goals of our works is to leave the door open to such possibilities.

In line 182, what do you mean by $\mu_z^{\otimes n}$?

First, as defined in the introduction, the notation $\mu_z$ corresponds to the unknown data distribution. We used the notation $\mu_z^{\otimes n}$ as a shortcut for the product measure $\mu_z \otimes \dots \otimes \mu_z$. Therefore, the notation $(z_1,\dots,z_n) \sim \mu_z^{\otimes n}$ means that the data points $z_i$ are sampled i.i.d. from the distribution $\mu_z$. We now made these notations more precise in the paper.