arXiv CSopen access

Upper Bounds on the Generalization Error of Deep Learning Models via Local Robustness and Stability

Upper Bounds on the Generalization Error of Deep Learning Models via Local Robustness and Stability Abdul-Rauf Nuhua , Parham M. Kebriaa , Vahid Hemmatia , Mahmoud Nabil Mahmoudb , Edward Tunstelc and and Abdollah Homaifara,∗ a North Carolina Agricultural and Technical State University, Dept. Electrical and Computer Engineering 1601 E Market St., Greensboro, 27411, NC, USA b University of Alabama, Dept. Computer Science, Tuscaloosa, 35487, AL, USA

arXiv:2606.16883v1 [cs.LG] 15 Jun 2026

c Southwest Research Institute, San Antonio, 78238, TX, USA

ARTICLE INFO

ABSTRACT

Keywords: Data-dependent bounds Generalization Model-dependent evaluation Robustness Robustness-based generalization

Generalization is a critical property of data-driven models, particularly deep learning models deployed in safety-critical applications. Robustness-based generalization bounds have gained attention as a principled way to link robustness properties to generalization performance, often in a data-dependent manner. However, most existing bounds suffer from vacuousness in practical settings, yielding loose upper bounds that greatly exceed the actual error rates and limiting their usefulness for real-world evaluation. While this issue is often attributed to the uncertainty term, a substantial part of the problem originates from the robustness term itself, particularly for the 0-1 loss. Existing approaches typically treat the robustness term as a global measure, ignoring its variation across different sub-regions of the input space. In this work, we propose a generalization bound that addresses this limitation by scaling the robustness term according to the number of stable and unstable samples within each sub-region. Our bounds incorporate both data- and model-dependent factors while maintaining practical relevance (yielding tighter upper bounds on true error). Experiments on models trained on the ImageNet dataset show that our bounds remain consistently non-vacuous and achieve the tightest estimates among existing methods, closely aligning with empirical performance across a range of robust deep neural networks.

1. Introduction Data-driven models, particularly deep learning classifiers, have recently achieved remarkable performance across a wide range of applications. These models have become integral to many safety-critical systems [28, 1, 16, 33, 22]. However, they remain vulnerable to common corruptions such as blur, noise, and adversarial examples [8, 23, 6]. Robustness enhancement methods, such as robust optimization [4, 7], have emerged as influential tools for addressing data uncertainty [6, 17]. These approaches leverage concepts from convexity and duality to derive feasible solutions for optimization problems. They have been successfully applied across various domains, including machine learning, to improve the robustness of deep neural networks [24, 15, 25]. Inspired by robust optimization, the authors in [32] demonstrated that robust algorithms generalize effectively to unseen data across different models, including deep learning architectures. This establishes robustness as an alternative perspective for studying generalization [26, 12, 11, 18, 2]. According to Definition (1), a learning algorithm  is considered robust if the loss 𝓁 of its output hypothesis  (a model returned by a learning algorithm  when trained on training dataset ) remains similar for nearby input samples. Building on this notion, prior work has shown that the generalization error of  can be upper bounded by two key components. The first is a robustness term, 𝜖() and the √ second is an uncertainty term, 𝐾∕𝑛. Where, 𝐾 represents the number of disjoint clusters that partition the input space,

and 𝑛 is the training sample size. More recently, authors in [13] refined this uncertainty term, thereby improving the practicality of robustness-based generalization bounds. Based on these developments, the robustness-based generalization framework has attracted significant attention in the machine learning community [6, 13, 30, 14]. This interest stems from the intuitive nature of the framework and the theoretically grounded definition of the robustness term 𝜖() [13]. Nevertheless, under the 0–1 loss, even a single misclassified sample can result in 𝜖() = 1, reducing the bound to that of the worst-case model and rendering it vacuous [31]. Although the supremum operator in the definition is designed to capture worst-case behavior, several theoretical studies impose restrictions to keep 𝜖() < 1 [3, 19]. However, such constraints are difficult to justify in practice, as even high-performing models may misclassify certain inputs. To address this issue, recent work proposes instance-aware modifications to the robustness definition to reduce the influence of outlier samples that disproportionately inflate 𝜖() [31]. This adjustment retains worst-case sensitivity while producing more meaningful generalization guarantees. Despite these advances, robustness-based generalization bounds remain limited when applied to specific trained models, especially in tasks such as model selection. Comparing models trained with different or stochastic algorithms remains challenging [32], highlighting the need for more model-sensitive generalization measures. In this context, authors in [31] introduce a localized robustness formulation

∗ Corresponding author: [email protected]

ORCID (s):

A.R Nuhu et al.: Preprint submitted to Elsevier

Page 1 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

(a) Original training data instances classified correctly as the (b) A perturbed version of the data instances in (a) misclastrue label "goldfish." sified to belong to different classes. Figure 1: A trained AllConvNet model classifies the original instances (a) correctly as the truth class, goldfish, while their perturbed variants are misclassified. Data instances with the majority of their neighbors misclassified are considered weak robust samples.

that decomposes the global robustness term into clusterspecific components 𝜖𝑗 (ℎ). Each 𝜖𝑗 (ℎ) quantifies the maximum change in loss between two similar samples within the same local neighborhood (e.g., cluster 𝑗 and model ℎ). This formulation avoids the unrealistic assumption of uniform robustness across the dataset and instead captures heterogeneous local behaviors. However, by scaling each cluster’s robustness contribution by the number of samples within it, their method implicitly assumes uniform influence from all instances in a cluster. In practice, stable samples in high-variance clusters can overshadow the effect of vulnerable ones, resulting in misleading robustness estimates. To address this, we refine the framework by explicitly identifying stable and unstable samples. We assign robustness contributions that reflect the stable and unstable samples behaviors. This adjustment ensures that the influence of highly variable or error-prone samples is appropriately captured in the generalization bound. To formalize this idea, we define a sample as stable if the model classifies the original input and its perturbed counterparts correctly. A sample is labeled unstable when the misclassification rate among its perturbed neighbors exceeds a predefined threshold [24]. As illustrated in Figure 1, the clean images in (a) are correctly labeled as "goldfish", while their perturbed versions in (b), though invisible, are misclassified. This exemplifies unstable behavior. These unstable samples often exhibit high loss variability and, under the robustness definition in (1), can cause 𝜖() to approach 1, producing vacuous generalization bounds. Figure 2 illustrates that stable samples maintain relatively constant loss values across iterations, whereas unstable samples exhibit significant volatility. Using a global average robustness term for the entire dataset can therefore overestimate the generalization bound. The same issue arises when local cluster robustness is scaled without distinguishing between stable and unstable samples. This overestimation occurs because unstable samples contribute the most to the generalization error [30]. When their effect is combined with stable samples, it becomes masked. This masking leads to an overestimation of the generalization bound. As a result, the bound becomes inflated and does not reflect the true behavior of a model. Our framework addresses this limitation by explicitly isolating unstable samples and systematically accounting for their A.R Nuhu et al.: Preprint submitted to Elsevier

Figure 2: Evolution of the average unnormalized cross-entropy loss for stable and unstable samples on the ImageNet dataset using a ResNet-50 model. Unstable samples consistently exhibit higher and more variable losses across iterations, whereas stable samples maintain low, consistent losses. This distinct behavior highlights the effectiveness of unstable samples as proxies for assessing generalization through robustness-based bounds.

influence. By disentangling their impact from that of stable samples, it produces tighter and more reliable robustnessbased generalization guarantees. To best of our knowledge, we are the first to use samples stability to provide empirical results on generalization guarantees measure. Our contributions in this paper are as follows: • Motivated by the observation in [31] that robustnessbased generalization bounds remain vacuous for classification problems with overlapping classes, wwe provide evidence that this limitation is linked to structural aspects of the formulation. Unlike prior approaches that uniformly treat all samples across clusters, our framework differentiates between stable and unstable regions, yielding significantly tighter and more meaningful generalization estimates in practice. • We propose a new class of model-dependent generalization bounds based on local model behavior across the input space. Our method separates stable and unstable clusters, allowing robustness contributions to reflect actual variations in the data. It does not require robustness assumptions about the model and Page 2 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

Figure 3: Data instances and the corresponding neighbors. The blue and gray triangles show the original instances; the green and red circles are the neighbors generated from perturbing an original instance.

yields bounds that are provably tighter than existing robustness-based approaches. • We empirically evaluate our proposed bounds on realworld datasets using modern neural network architectures and show that they correlate more strongly with actual model performance than existing baseline bounds. This improved alignment makes them a more reliable tool for model selection and comparative performance evaluation. The rest of the paper is structured as follows. Section 2 presents the key definitions and existing bounds that form the foundation for our proposed bounds. Section 3 presents the proposed bounds along with their implementation details. Section 4 summarizes the proposed framework for our theorems implementation. Section 5 describes the experimental setup and compares our results with existing bounds. Finally, Section 6 concludes the paper and outlines directions for future research. Proofs of our bounds are provided in A, while additional results are presented in B.

2. Preliminaries This section introduces key terminologies and notations. Then, it covers foundational definitions and theorems on robustness-based generalization bounds. Finally, it concludes with factors behind vacuousness of these bounds and prepares the ground for our proposed theorems.

2.1. Terminology Definitions We discuss the key terminologies used. Neighbors: Samples obtained by perturbing original instances from a given dataset. As illustrated in Figure 3, the blue and gray triangles denote original samples, while the green and red circles represent their corresponding neighbors, generated through random perturbations. Neighbors may also be generated using natural variations or adversarial perturbation techniques.

A.R Nuhu et al.: Preprint submitted to Elsevier

Unstable sample: A data instance is classified as an unstable sample if its local neighborhood exhibits high sensitivity under perturbations, i.e., a significant proportion of its perturbed neighbors are misclassified by the model. As illustrated in Figure 1, the original inputs in (a) are correctly classified, while their perturbed counterparts in (b) are frequently misclassified, indicating weak robustness. Formally, this behavior reflects regions where the loss function varies sharply under small input perturbations. Such samples are closely associated with small classification margins or brittle decision boundaries, as established in prior works on margin-based stability [32, 21, 24]. These works show that samples with low margins contribute disproportionately to instability and robustness degradation. Figure 2 further illustrates this distinction: stable samples maintain relatively constant loss values across iterations, whereas unstable samples exhibit significant volatility.

2.2. Notations Let  represents the sample space, and  ⊂  denotes a training set consisting of 𝑛 samples (𝑧1 , … , 𝑧𝑛 ), with 𝑛 = || and 𝑍𝑚 ⊂  represents an arbitrary test dataset (𝑍𝑚 ∩  = ∅) drawn from . 𝑧𝑖 denotes an arbitrary sample drawn from  while 𝑧 denotes an arbitrary sample drawn from  i.e 𝑧 ∈ ⧵. We define ̂ as the stable samples, and ̃ =  ⧵ ̂ as the unstable samples in the training set . The size of ̂ is denoted as 𝑛( ̂  ). Similarly, the size of ̃ is denoted as 𝑛̃( ). For a given 𝐾 ∈ ℕ with 𝐾 ≥ 1, we denote [𝐾] = {1, … , 𝐾}⋃as the number of clusters. Let 𝛽() ∶= 𝐾 𝑘=1 𝐶𝑘 be a partition of  into 𝐾 disjoint nonempty subsets. We assume that the input space  ⊆ ℝ𝑑 is a metric space, where local neighborhoods can be defined via small perturbations under a chosen norm. The notation || ⋅ ||𝑝 refers to the standard 𝑝-norm of a vector. Consider a learning problem defined by a hypothesis class  and a loss function 𝓁 ∶  ×  → ℝ. Given a distribution ℙ over , the generalization capability of  ∈ , a model returned by learning algorithm  on training set , is measured by its expected risk 𝑍 ( ) = 𝔼𝑧∼ℙ [𝓁( , 𝑧)]. Since this expectation cannot be computed directly, the empirical risk 𝑛 ∑ ̂  ( ) = 1 𝓁( , 𝑠𝑖 )  𝑛 𝑖=1

is typically used to approximate it [30, 5]. The expected risk is then upper bounded by the empirical risk plus additional terms, as given:

̂  ( ) +  𝑍 ( ) ≤ 

(√ ) 𝐶 𝑛

where C denotes the complexity of a model.

Page 3 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

2|𝑇𝑆 | ln(2𝐾∕𝛿) + 𝑛

2.3. Robustness-based generalization bounds Previous studies in [32, 13] used algorithmic robustness to bound the expected risk 𝑍 ( ). Definition 1 (Algorithmic Robustness). A learning algorithm  is said to be (𝐾, 𝜖(⋅))-robust, for some 𝐾 ∈ ℕ and a function 𝜖 ∶ 𝑛 → ℝ, if the sample space  can be partitioned into 𝐾 disjoint subsets {𝐶𝑘 }𝐾 such that the 𝑘=1 following holds: For all training samples  ∈ 𝑛 , and ∀𝑠 ∈ , ∀𝑧 ∈ , and 𝑘 ∈ [𝐾], if 𝑠, 𝑧 ∈ 𝐶𝑘 , then

with probability at least 1 − 𝛿, and 𝑛 samples 𝑆 = {𝑧1 , … , 𝑧𝑛 } drawn from an iid, the following generalization bound holds:

Theorem 1 (Xu & Mannor [32]). Let 𝓁(ℎ, 𝑧) be a nonnegative loss function upper bounded by 𝑀, i.e., 𝓁(ℎ, 𝑧) ≤ 𝑀 for all ℎ ∈  and 𝑧 ∈ . If the learning algorithm  is (𝐾, 𝜖(⋅))-robust, then for any 𝛿 > 0, √ 2𝐾 ln 2 + 2 ln(1∕𝛿) 𝑢1 (𝐾, , 𝛿) = 𝑀 𝑛 with probability of at least 1 − 𝛿, and 𝑛 samples 𝑆 = {𝑧1 , … , 𝑧𝑛 } drawn from an iid (independent and identically distributed), the following holds: ̂  ( ) + 𝜖() + 𝑢1 (𝐾, , 𝛿) 𝑍 ( ) ≤ 

(1)

It can be seen from Theorem 1 that the expected risk ̂  ( ) and 𝑍 ( ) is bounded by the empirical risk  some additional terms. The first term of these additional terms capture the robustness properties of the learned model  . The last√term of the additional terms in bound (1) scales with 𝐾 and has been the main disadvantage of this bound [13]. Through the concentration of multinomial random variables, authors in [13] proposed a theorem that reduces the 𝐾 dependence in Theorem 1. The theorem is as follows: Theorem 2 (Kawaguchi et al., [13]). Following the same assumptions and notations as in Theorem 1, for any 𝛿 > 0, denote ( √ √ |𝑇𝑆 | ln(2𝐾∕𝛿) 𝑢2 (𝐾, , 𝛿) = 𝜙( ) ( 2 + 1) 𝑛 A.R Nuhu et al.: Preprint submitted to Elsevier

(2)

̂  ( ) + 𝜖() + 𝑢2 (𝐾, , 𝛿) 𝑍 ( ) ≤  { } where 𝜙(𝐴𝑆 ) ∶= max 𝓁( , 𝑧) , 𝑧∈ { } || | 𝑇𝑆 ∶= 𝑘 ∈ [𝐾] | |𝑘𝑆 | ≥ 1 , || | 𝑆 𝑘 ∶= {𝑖 ∈ [𝑛] ∶ 𝑧𝑖 ∈ 𝐶𝑘 }

|𝓁( , 𝑠) − 𝓁( , 𝑧)| ≤ 𝜖(). | | Intuitively, algorithmic robustness means that the learned algorithm 𝑆 behaves consistently for samples that belong to the same partition of the sample space as the training data, as measured by the loss function 𝓁 [13]. In other words, samples that are similar to the training data incur comparable loss values. This provides intuition for why robustness can support generalization to nearby samples. To formalize the relation between robustness and generalization of a trained model, studies in [32, 13] incorporate the robustness properties of a learning algorithm in (1) and proposed the following theorems.

)

Theorem 2 significantly improves over the √previous bound (1). √ It has a far less dependency on 𝐾, as 𝐾 is reduced to ln 𝐾. 𝜙( ) replaces the maximum over the entire model family (hypothesis space) with a single hypothesis returned by the algorithm ( ). Compared with 𝑢1 (𝐾, , 𝛿), the uncertainty term 𝑢2 (𝐾, , 𝛿) becomes significantly smaller. Although this is a significant improvement, authors in [13] further showed that 𝑢2 (𝐾, , 𝛿) can be further improved with √ 𝑢3 (𝐾, , 𝛿) = 1

ln (2𝐾∕𝛿) 22 ln (2𝐾∕𝛿) + 𝑛 𝑛

where 1 ∶=

∑ ( 𝑘∈𝑇𝑆

) √ 𝛼 𝑐 (𝐴𝑆 ) + 2 𝛼𝑘 (𝐴𝑆 ) 𝑆

2 ∶= 𝛼 𝑐 (𝐴𝑆 ) ⋅ |𝑇𝑆 | + 𝑆

∑

√

|𝑘𝑆 | 𝑛

,

𝛼𝑘 (𝐴𝑆 ),

𝑘∈𝑇𝑆

{ } 𝑇𝑆 ∶= 𝑘 ∈ [𝐾] ∶ |𝑘𝑆 | ≥ 1 , { } 𝑘𝑆 ∶= 𝑖 ∈ [𝑛] ∶ 𝑧𝑖 ∈ 𝐶𝑘 , [ ] 𝛼𝑘 (ℎ) ∶= 𝔼𝑧 𝓁(ℎ, 𝑧) ∣ 𝑧 ∈ 𝐶𝑘 , 𝛼 𝑐 (𝐴𝑆 ) ∶= max𝑐 𝛼𝑘 (𝐴𝑆 ), 𝑆

𝑘∈𝑆

𝑆𝑐 ∶= [𝐾] ⧵ 𝑇𝑆 . Although the uncertainty term 𝑢1 (𝐾, , 𝛿) has improved to 𝑢3 (𝐾, , 𝛿), the robustness term 𝜖() remains the same across different proposed bounds [31]. As a result, there are still some issues with these bounds, and we discuss this matter in the following.

2.4. Vacuousness and its main causes The robustness-based generalization bounds can become vacuous, primarily due to the conservative nature of the robustness condition defined in Definition 1. This issue was first identified by the authors in [31]. Consider a model Page 4 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

 ∈  returned by a learning algorithm . Definition 1 implies that 𝜖() ≥ max 𝜖𝑗 ( ) 𝑗∈𝑇𝑆

any 𝛿 > 0, with probability at least 1 − 𝛿 of 𝑛 samples 𝑆 = {𝑧1 , … , 𝑧𝑛 } drawn from an iid, the following generalization bound holds: ̂  (𝐡) + 𝑍 (𝐡) ≤ 

where

∑ 𝑛𝑗 𝑗∈𝑇𝑆

𝜖𝑗 ( ) = max |𝓁( , 𝑧) − 𝓁( , 𝑠)| 𝑠,𝑧∈𝐶𝑗

Even for highly accurate models, bounds (1) and (2) can still become vacuous. In practice, it is possible to have incorrect predictions from a highly accurate model. Therefore, for losses normalized to [0,1], an incorrect prediction can result in 𝜖() = 1 and thus making the bounds vacuous. In a nutshell, Definition 1 requires the following specific operations: • Supremum operation: The robustness term 𝜖() is computed by taking the supremum of local robustness levels (𝜖𝑗 ) across all clusters of the input space that contains some training examples. This means that even a single unstable region, where the local robustness is poor (e.g., 𝜖𝑗 = 1 for 0 − 1 loss, indicating a region where misclassification is possible). This can inflate the global robustness measure and in practice, it is common for models to make at least a few mistakes. So, taking the supremum of local robustness levels will almost always result in vacuous bounds. • Stochasticity Inclusion Challenge: In practice, most learning algorithms  are stochastic, meaning that different runs, given the same training set  and hyperparameters, can yield different trained models. Consequently, evaluating the robustness metric 𝜖() must account for this randomness. A more realistic formulation is: 𝜖() ≥ sup 𝜖𝑗 ( (𝜁 )), 𝜁,𝑗

where 𝜁 denotes the source of stochasticity and 𝜖𝑗 measures the robustness of the 𝑗th cluster. Fully characterizing 𝜖() would therefore require considering all stochastic variations of , which is computationally infeasible in most settings. Moreover, some stochastic outcomes can produce models with substantially reduced robustness. In such cases, assuming a single global robustness term 𝜖() for the entire dataset, as in existing approaches, can render the bounds vacuous [31]. These challenges highlight the need for a more tractable and reliable approach to evaluate robustness under algorithmic stochasticity. To mitigate the vacuousness issues that stem from supremum operation and stochasticity inclusion, the authors in [31] proposed the following theorem: Theorem 3 (Khoat et al., [31] Theorem 4). Consider a model 𝐡 ∈  learned from  and a bounded loss 𝓁. For each 𝑗 ∈ [𝐾], let 𝜖𝑗 (ℎ) = max𝑠,𝑧∈𝐶𝑗 |𝓁(ℎ, 𝑧) − 𝓁(ℎ, 𝑠)|. For A.R Nuhu et al.: Preprint submitted to Elsevier

𝑛

𝜖𝑗 (𝐡) + 𝑢3 (𝐾, , 𝛿)

(3)

This theorem shows that the expected loss of a model can be bounded by 𝜖𝑗 (𝐡). 𝜖𝑗 (𝐡) describes the local robustness of 𝐡 at different regions and suggests that a model can generalize well when it is locally robust in those regions. This highlights that a model can have a small expected loss over the whole sample space if it has a small training loss and is locally robust. The global robustness term 𝜖() being ∑ 𝑛 replaced by a finer quantity 𝑗∈𝑇𝑆 𝑛𝑗 𝜖𝑗 (𝐡), capturing the “stochasticity inclusion” in bound (1) and (2). Authors in [31] provided an improved version of Theorem 3 (bound 4) by considering the averages of loss at the clusters (local regions). Theorem 4 (Khoat et al., [31] Theorem 5). Given the notions in Theorem 3 For any 𝛿 > 0, with probability at least 1 − 𝛿 over an iid draw of 𝑛 samples 𝑆 = {𝑧1 , … , 𝑧𝑛 }, the following generalization bound holds: ̂  (𝐡) + 𝑍 (𝐡) ≤ 

∑ 𝑛𝑗 𝑗∈𝑇𝑆

𝑛

𝜖̄𝑗 (𝐡) + 𝑢3 (𝐾, , 𝛿)

(4)

where: 𝜖̄𝑗 =

[ ] 1 ∑ 𝔼𝑧∈𝑍𝑗 |𝓁(𝐡, 𝑧) − 𝓁(𝐡, 𝑠)| |𝑛𝑗 | 𝑠∈𝐶 𝑗

3. Local Stability Behaviors and Generalization In this section, we discuss our novel bounds that connects local behaviors (per-input resilience) with the generalization ability of a given model. Our bounds are both model-specific and data-dependent, and they relax the strict robustness assumptions imposed by previous approaches [32, 13, 31].

3.1. Cluster Stability and Per-Input Robustness based Bounds In the previous section, the algorithmic robustness-based generalization bounds quantify model robustness across the entire data space through the term 𝜖(). This global measure is derived using a supremum [31], effectively capturing the worst-case local robustness of the model within individual regions or clusters of the input space. This robustness term is then assumed as the average (global) robustness term for the entire dataset [32, 13]. Consequently, this formulation often leads to vacuous generalization bound [31]. Since the supremum-based measure 𝜖() is dominated by worst-case local variations rather than representing the entire dataset, the robustness term should instead be scaled in proportion to the fraction of a cluster samples.

Page 5 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

We address the limitations of prior bounds by incorporating local robustness across the clusters into the generalization bound. Specifically, we decompose the supremum into two components: one from the stable subset and the other from the unstable subset. Unlike Theorems 1, 2, 3, and 4, our approach does not apply the global supremum value 𝜖() uniformly to all samples within a cluster. Instead, the supremum is separated into the stable and unstable parts and scaled according to their respective sample proportions. This results in a bound that is less conservative and more sensitive to the actual distribution of instability in the data. Our approach is computationally practical, as stable and unstable instances can be identified by measuring local loss differences or margin violations. It is based on the observation that unseen instances behave like similar training samples. When an unseen instance is close to stable samples, the model is likely to show low loss. Conversely, proximity to unstable samples leads the model to exhibit higher variations in loss [30]. By capturing this behavior, the bound reflects the model’s performance more accurately and supports better comparison and selection. The following theorems present our bounds. Theorem 5 (Cluster Stability-Based Robustness Decomposition). Let  be a model trained on a dataset  using a bounded loss function 𝓁. Assume the sample space  can ̃ where be partitioned into stable ̂ and unstable subsets , ̂ ̃  =  ∪ . We define clustering independently over each subset: • Let {𝐶̂𝑗 }𝐾 be the clusters formed over the stable set 𝑗=1 ̂ .

• 𝑛̂ 𝑗 ( ) denotes the number of training samples in the stable cluster 𝐶̂𝑗 , • 𝑛̃𝑗 ( ) denotes the number of training samples in the unstable cluster 𝐶̃𝑗 . Theorem 5 establishes that the robustness term in the previous bounds can be decomposed into separate contributions from stable and unstable samples within each cluster. For more general loss functions, this formulation underscores that stable samples, while exhibiting smaller errors [30], still make non-negligible contributions to the robustness term. To capture this distinction, we partition the training data into stable and unstable clusters: unstable clusters reflect regions of high sensitivity, whereas stable clusters account for consistently low-error regions. This partition also provides insight into how different regions contribute to the overall expected risk. In particular, by decomposing the input space into stable and unstable regions, Lemma 1 shows that, under 0-1 loss, the contribution of the stable subset ̂ to the expected risk is negligible, while ̃ the dominant contribution arises from the unstable subset . Following [30], where it has been stated that robust models achieve a vanishing robustness term 𝜖(𝑆) = 0 across the dataset, our stable subset ̂ plays an analogous role at a local level. In these regions, the model 𝑆 exhibits consistently correct predictions by construction (i.e., 𝛼1 ≈ 0), which justifies focusing on the contribution of unstable clusters in Corollary 1.

• Let {𝐶̃𝑗 }𝐾 be the clusters formed over the unstable 𝑗=1 ̃ set .

Lemma 1. (Risk Bound via Unstable Samples) Consider that the input space  is decomposed into 1 = ̂ and 2 = [ ] ̃ where  ̃ =  ⧵ . ̂ Given 𝛼𝑖 (𝐴𝑆 ) ∶= 𝔼𝑧∼ 𝓁(𝐴𝑆 , 𝑧) , , 𝑖 i.e., the expected loss restricted to the subset 𝑖 . Then, the expected risk under 0-1 loss can be decomposed as:

• 𝑇̂𝑆 as the clusters with at least one stable training instance.

 (𝑆 ) = ℙ(𝑧 ∈ 1 ) 𝛼1 (𝑆 ) + ℙ(𝑧 ∈ 2 ) 𝛼2 (𝑆 ).

• 𝑇̃𝑆 as the clusters with at least one unstable training instance. Define the local robustness margin within each cluster as follows: 𝜖̂𝑗 ( ) ∶= max ||𝓁( , 𝑧) − 𝓁( , 𝑠)|| 𝑧,𝑠∈𝐶̂𝑗

 (𝑆 ) ≤ ℙ(𝑧 ∈ 2 ) 𝛼2 (𝑆 ) ≤ 𝛼2 (𝑆 ).

𝜖̃𝑗 ( ) ∶= max ||𝓁( , 𝑧) − 𝓁( , 𝑠)|| 𝑧,𝑠∈𝐶̃𝑗

Then, for any 𝛿 > 0, with probability at least 1 − 𝛿 over an iid draw of 𝑛 training samples, the generalization error of  is bounded as: ̂  ( ) + 𝑍 ( ) ≤ 

∑ 𝑛̂ 𝑗 ( ) 𝑗∈𝑇̂𝑆

+

∑ 𝑛̃𝑗 ( ) 𝑗∈𝑇̃𝑆

𝑛

𝑛

⋅ 𝜖̂𝑗 ( )

⋅ 𝜖̃𝑗 ( ) + 𝑢3 (𝐾, , 𝛿)

where: A.R Nuhu et al.: Preprint submitted to Elsevier

By construction, ̂ represents the stable subset where the model 𝑆 predicts correctly with high probability. Under the 0-1 loss, correct predictions incur zero loss; therefore, the expected loss on 1 is negligible, i.e., 𝛼1 (𝑆 ) ≈ 0. Moreover, since the 0-1 loss is bounded in [0, 1], we have 𝛼2 (𝑆 ) ≤ 1. Consequently,

(5)

This implies that the expected risk can be bounded by the risk associated with the unstable samples in the dataset. Building on this lemma, we propose the following bounds. Corollary 1 (Per-Input Local Robustness). Under the setting and notations of Theorem 5, assume that the expected loss over the stable subset ̂ is negligible (e.g., under 0-1 loss where correct predictions incur zero loss). Suppose the ̃ can be clustered into unstable subset of the sample space  𝐾 ̃ 𝐾 disjoint subsets {𝐶𝑗 }𝑗=1 . Define: Page 6 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

• the worst-case local robustness variation within each unstable cluster as:

𝜖̃𝑗 ( ) ∶= max ||𝓁( , 𝑧) − 𝓁( , 𝑠)|| . 𝑠,𝑧∈𝐶̃𝑗

Then, for any 𝛿 > 0, with probability at least 1 − 𝛿 over the iid draw of the training dataset , the generalization error of  satisfies: ̂  ( ) + 𝑍 ( ) ≤ 

∑ 𝑛̃𝑗 ( ) 𝑗∈𝑇̃𝑆

𝑛

⋅ 𝜖̃𝑗 ( ) + 𝑢3 (𝐾, , 𝛿) (6)

where: • 𝑛̃𝑗 ( ) is as defined in Theorem 5. Corollary 1 establishes that the expected loss of a model ∑ 𝑛̃ ( )  ∈  can be bounded using 𝑗∈𝑇̃ 𝑗 𝑛  ⋅ 𝜖̃𝑗 ( ), 𝑆 which quantifies the local robustness of  based solely on unstable training instances across all the clusters. This result suggests that a model can achieve good generalization by maintaining local robustness specifically around unstable training points. By focusing on robustness efforts on these ̂  ( ), critical regions and ensuring a small empirical risk  the model can attain a low expected loss over the entire sample space. Like the bound in (3), our bound in Corollary 1 differs from the bounds in Theorems 1 and 2 in the following ways: • Firstly, our bound (6) (Corollary 1) relaxes the strict assumption of algorithmic robustness. Instead of requiring that a model exhibit uniformly small loss differences between all pairs of nearby training and test samples, our bound focuses only on the subset of training instances that exhibit unstable behavior. • Secondly, our bound introduces both model specificity and data dependency in computing the robustness term. It explicitly depends on the particular model  and the training dataset . This is a clear advantage over prior bounds that rely only on global, datadependent robustness terms. By capturing modelspecific behavior, our bound provides a more accurate evaluation of generalization performance. In addition, it enables meaningful model selection and comparison across different architectures or training settings. This makes it especially useful for benchmarking robust learning methods in real-world applications. • Thirdly, unlike prior bounds in (1) and (2) that rely on a global robustness level 𝜖(), our bound in (6) uses ∑ 𝑛̃ () localized terms 𝑗∈𝑇̃ 𝑗 𝑛 ⋅ 𝜖̃𝑗 ( ), which focus on 𝑆 unstable training instances. Unstable samples correspond to regions where the model is highly sensitive, and this sensitivity is a primary source of variability A.R Nuhu et al.: Preprint submitted to Elsevier

across different stochastic realizations of the learning algorithm. By concentrating on these regions, the formulation alleviates the “stochasticity inclusion” challenge, where global robustness measures require worst-case aggregation over both stable and unstable regions as well as stochastic variations. Instead, it provides a more tractable and targeted characterization of generalization by focusing on the dominant sources of variability. While this approach is motivated by stochastic training effects, it does not explicitly model stochasticity, but mitigates its impact by avoiding overly conservative global estimates. • Lastly, in real-world settings, generalization errors are often caused by a small subset of unstable or difficult training instances [30]. The bound in (6) accounts for this by weighting the worst-case margin according to the proportion of these unstable samples, resulting in a more accurate and tighter estimate of the expected loss. Worst-case generalization bounds that rely solely on unstable samples are tight under the 0-1 loss, since assigning the maximum error to all unstable samples directly corresponds to classification errors. However, beyond the 0-1 loss, our bound in Theorem 5 provides a more suitable framework for assessing the generalization of deep learning models. Next, remark 1 establishes the tightness of our bounds in Theorem 5 and Corollary 1. Finally, we relegate the proof of our bounds in Theorem 5 and Corollary 1 to A. Remark 1 (Comparison of Robustness Bounds). Under the same setting and notation as Theorems 5 and 1, the following holds: • First, the local cluster margins 𝜖̂𝑗 ( ) for stable clusters are often zero or negligibly small due to inherent robustness within stable regions. • Second, the per-input local robustness-based bound introduces finer granularity by scaling each intracluster supremum 𝜖̃𝑗 ( ) by the individual cluster size 𝑛̃𝑗 ( ). In contrast, the cluster stability-based bound captures the deviation stemming from the stables and unstable samples, thus making this bound general for different loss functions. Hence, the per-input local robustness-based bound (6) is often strictly tighter than the cluster stability-based bound (5). This is especially true for 0-1 loss. It also holds when most stable clusters have volatile loss behavior and the worst-case deviations are limited to a few unstable regions.

3.2. Our Bounds Comparison with Pseudo-Robustness Bounds Our proposed generalization bounds differ fundamentally from the pseudo-robustness framework introduced by [32, 13], both in form and in practical applicability. Both Page 7 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

bounds share a similar uncertainty term that captures the deviation from empirical to true risk due to finite sampling. However, they differ in how they use samples of interest and define robustness in the core decomposition. The pseudorobustness bound relies on a data-dependent subset of “stable” samples determined by fixed input-space clustering. It introduces two terms: one that accounts for the robustness over these stable regions, and another that penalizes the remaining “unstable” samples via worst-case deviations. However, this formulation assumes that robustness can be captured purely through properties of the data, independent of how the model interacts with it [32]. In contrast, our bounds adopt a joint data- and modeldependent formulation. Specifically, we partition the sample ̃ where the selection is informed not only set into ̂ and , by data structure but also by model behavior (e.g., local margins, confidence, or feature space concentration). The robustness terms 𝜖̂𝑗 (𝑆 ) and 𝜖̃𝑗 (𝑆 ) are similarly modelaware, capturing how the algorithm generalizes across these subsets. This allows the bound to better reflect the learning dynamics of complex models, particularly in high-capacity regimes such as deep neural networks. Moreover, instead of relying on a single global robustness term across all clusters, our formulation distributes contributions proportionally through structured model-aware error terms. This prevents overestimation of instability, resulting in a tighter and more interpretable generalization bound. As a result, the proposed approach maintains computational tractability while more rigorously characterizing the behavior of modern learning models under real-world complexity and uncertainty.

4. Implementation of the Proposed Framework In this section, we present the proposed framework for empirically estimating the upper bounds on the true error of learned models using our derived bounds. Although the theoretical results are defined over the sample space , their practical evaluation relies on finite datasets. Accordingly, we use the training dataset  and 𝑍𝑚 as representative samples from  to approximate the quantities involved, consistent with standard generalization assessment practices [31]. Our framework first partitions the training dataset into stable and unstable subsets, followed by a clustering procedure aligned with the bounds in (5) and (6). Unlike conventional approaches, this explicit separation enables a more targeted estimation of generalization behavior by focusing on robustness characteristics within each subset. To this end, we introduce the per-input resilient analyzer to perform the partitioning, and subsequently describe how stable and unstable clusters are constructed using the training dataset  together with the test samples 𝑍𝑚 .

4.1. Per-input resilient analyzer The concept of using a per-input resilient analyzer to partition a dataset into stable and unstable subsets was first introduced by authors in [24]. While they utilized the unstable A.R Nuhu et al.: Preprint submitted to Elsevier

samples to guide robustness enhancement, we examine how these subsets can be leveraged for generalization assessment. Algorithm 1 outlines the per-input resilient analyzer, which ranks data samples from least to most stable. The analyzer takes as input a trained model  and a given dataset . ̃ are initialized to store the Empty dictionaries ̂ and  stable and unstable samples respectively. For each instance 𝑥𝑖 in the given dataset, the analyzer generates 𝜅 perturbed neighbors through random sampling, with each perturbation constrained by a maximum perturbation magnitude 𝜖. Each perturbed neighbor 𝑥𝑞 (where 𝑞 ∈ 𝜅) is passed through  to obtain the predicted label 𝑦̂𝑞 . If the prediction is correct (𝑦̂𝑞 = 𝑦𝑖 ), the neighbor is assigned a misprediction score 𝑀𝑠 = 0; otherwise (𝑦̂𝑞 ≠ 𝑦𝑖 ), it is assigned 𝑀𝑠 = 1. This scoring scheme is formalized in Equation (7). The stability score 𝛾𝑖 for the original sample 𝑥𝑖 is computed as the average of its neighbors’ misprediction scores as shown in Equation (8). Once stability scores are computed for all instances in a class, the samples are sorted in descending order of 𝛾𝑖 , thereby ranking them from least to most stable. Algorithm 1 Per-input Resilient Analyzer Require:  , , 𝜅, 𝜖, 𝜏 ̃ containing stable and unstable training Ensure: Lists ̂ and  samples, respectively 1: function COMPUTEM ISPREDICTION S CORE(𝑥, 𝑦) 2: 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟_𝑠𝑢𝑚 ← 0 3: for 𝑞 = 1 to 𝜅 do 4: 𝑥𝑞 ← 𝑥 + 𝜖 ⋅ random(size(𝑥)) 5: 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟_𝑠𝑢𝑚 ← 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟_𝑠𝑢𝑚 + 𝑀𝑠 (𝑥𝑞 ) 6: end for 7: return 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟_𝑠𝑢𝑚 𝜅 8: end function ̂ ← [ ],  ̃←[] 9:  10: for each class 𝑦𝑖 ∈  do 11: Find 𝑣𝑐 : samples in  belonging to class 𝑦𝑖 12: Initialize list 𝑅 ← [ ] 13: for 𝑖 = 1 to |𝑣𝑐 | do 14: 𝛾𝑖 ← COMPUTEM ISPREDICTIONSCORE(𝑥𝑖 , 𝑦𝑖 ) 15: Append (𝑥𝑖 , 𝛾𝑖 ) to 𝑅 16: end for 17: Sort 𝑅 in descending order by 𝛾𝑖 18: for each (𝑥𝑖 , 𝛾𝑖 ) ∈ 𝑅 do 19: if 𝛾𝑖 ≥ 𝜏 then ̃ 20: Append 𝑥𝑖 to  21: else 22: Append 𝑥𝑖 to ̂ 23: end if 24: end for 25: end for ̂ ) ̃ 26: return (,

Finally, based on a predefined threshold 𝜏, the sorted dataset is partitioned into stable and unstable subsets. Samples with stability scores greater than or equal to 𝜏 are ̃ while those with scores assigned to the unstable subset , ̂ below 𝜏 are assigned to the stable subset .

Page 8 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

Algorithm 2 Stable and Unstable Clusters Formation

Figure 4: An overview of partitioning and clustering for the formation of stable and unstable clusters. 𝑍𝑚 and  represent a test and train dataset, respectively.

{ 𝑀𝑠 (𝑥𝑞 ) =

0, 1,

if 𝑦̂𝑞 = 𝑦𝑖 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

1∑ 𝑀 (𝑥 ) 𝜅 𝑞=1 𝑠 𝑞

(7)

𝜅

𝛾𝑖 =

(8)

4.2. Stable and Unstable Clusters Formation To construct stable and unstable clusters, we first identify the corresponding samples in each dataset split (training or test) using per-input resilient analyzer described in subsection (4.1). This partitions the training set  into stable sam̃ and the test set 𝑍𝑚 into stable ples ̂ and unstable samples , ̂ ̃ The overall framework, samples 𝑍 and unstable samples 𝑍. along with the resulting cluster structure, is illustrated in Fig. 4. Cluster formation is performed independently for each category: • Stable clusters: Centroids are selected from the stable ̂ High-level feature representations of test subset 𝑍. both 𝑍̂ and ̂ are extracted using the trained model  and subsequently reduced via Principal Component Analysis (PCA). K-means clustering is then applied to assign each stable training sample in ̂ to its nearest stable centroid, forming stable clusters {𝐶̂𝑗 }𝐾 . 𝑗=1 • Unstable clusters: Centroids are similarly selected ̃ PCA-reduced features from the unstable test subset 𝑍. ̃ and ̃ are computed, and K-means clusterof both 𝑍 ing is applied to assign each unstable training sample in ̃ to its nearest unstable centroid, forming unstable clusters {𝐶̃𝑗 }𝐾 . 𝑗=1 By constructing stable and unstable clusters separately, this approach ensures that the resulting partitions truly capture the local behavior of the model in both low-variation (stable) and high-sensitivity (unstable) regions. Although the clusters are formed independently, the procedure is conceptually equivalent to decomposing a cluster into stable and unstable components. In both cases, the goal is to distinguish regions of consistent model behavior from those exhibiting high variability. This structured partitioning provides a rigorous basis for robustness-based analysis and localized generalization assessment. The complete procedure is summarized in Algorithm 2. A.R Nuhu et al.: Preprint submitted to Elsevier

Require: Training set , test set 𝑍, model  , number of clusters 𝐾 Ensure: Stable and unstable clusters: {𝐶̂𝑗 }𝐾 , {𝐶̃𝑗 }𝐾 𝑗=1 𝑗=1 1: Use per-input resilient analyzer to partition  into ̂ (stable) and ̃ (unstable) ̃ (unstable) 2: Similarly partition 𝑍 into 𝑍̂ (stable) and 𝑍 ̂ } ̃ do 3: for each subset in {, 4: Extract high-level features using model  5: Apply PCA to reduce feature dimensionality 6: if subset is ̂ then 7: Extract PCA-reduced features from 𝑍̂ to serve as centroids 8: Apply K-means clustering to assign ̂ into {𝐶̂𝑗 }𝐾 𝑗=1 9: else ̃ to serve as cen10: Extract PCA-reduced features from 𝑍 troids 11: Apply K-means clustering to assign ̃ into {𝐶̃𝑗 }𝐾 𝑗=1 12: end if 13: end for 14: return {𝐶̂𝑗 }𝐾 , {𝐶̃𝑗 }𝐾 𝑗=1 𝑗=1

4.3. Computational Complexity We briefly analyze the computational cost of Algorithms 1 and 2. For Algorithm 1 (Per-input Resilient Analyzer), let 𝑛 = || denote the number of training samples and 𝜅 the number of perturbations per sample. The dominant cost arises from evaluating the model over perturbed inputs, resulting in a total complexity of 𝑂(𝑛𝜅). In addition, the sorting operation incurs a cost of 𝑂(𝑛 log 𝑛). Therefore, the overall time complexity of Algorithm 1 is 𝑂(𝑛𝜅 + 𝑛 log 𝑛). Notably, the perturbation-based evaluations are independent across samples, allowing Algorithm 1 to be efficiently parallelized across multiple computational units (e.g., GPUs or distributed systems), which significantly improves scalability in practice. For Algorithm 2 (Stable and Unstable Clusters Formation), let 𝑑 denote the input feature dimension, 𝑑 ′ denote the extracted input feature dimension, 𝑘 the number of clusters, and 𝑖 the number of iterations in the K-means algorithm. The main computational steps include feature extraction, dimensionality reduction, and clustering. Feature extraction requires 𝑂(𝑛), while PCA incurs 𝑂(𝑛𝑑 2 ) in general. The K-means clustering step has complexity 𝑂(𝑛𝐾𝑑 ′ 𝑖). Thus, the overall time complexity of Algorithm 2 is 𝑂(𝑛 + 𝑛𝑑 2 + 𝑛𝑘𝑑 ′ 𝑖). Overall, both algorithms scale linearly with the dataset size 𝑛, with the dominant cost driven by perturbation-based evaluations in Algorithm 1 and clustering operations in Algorithm 2.

Page 9 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

(a) Accuracy of different models on stable and unstable samples from the training dataset.

(b) Accuracy of different models on stable and unstable samples from the validation dataset. Figure 5: Performance of different models on stable and unstable samples from the training dataset (a) and validation dataset (b). While stable samples yield near-perfect accuracies, unstable samples reveal substantial performance degradation, highlighting their utility as a proxy for robustness-based generalization assessment under the 0–1 loss.

5. Experimental Setup In this section, we present an empirical evaluation of our proposed bounds and compare them against baseline methods using state-of-the-art deep learning models on standard classification datasets.

5.1. Bounds evaluation on ImageNet pretrained models 5.1.1. Models Architecture Utilized To ensure a fair and consistent comparison of the generalization bounds, we adopt the same set of models pretrained on ImageNet [27] utilized in the evaluation by [31]. Specifically, we employed 20 PyTorch-pretrained models1 drawn from four widely used deep neural network architectures: DenseNet [10], ResNet [9], Swin Transformer [20], and VGG [29]. All models are trained on the ImageNet-1K dataset, which comprises 1,281,167 training samples. 1 https://pytorch.org/vision/stable/models.html

A.R Nuhu et al.: Preprint submitted to Elsevier

5.1.2. Implementation details To group the training dataset into the stable and unstable samples we set the following parameters as follow: We perform a sensitivity analysis for 𝜅 by varying its value between 10 and 200. Following [23, 34], we set 𝜅 = 20, since the average numbers of stable and unstable samples stabilize at this point and remain consistent for larger values. This ensures reliable results while avoiding extra computational overhead. For the perturbation degree 𝜖, we adopt the value 0.1, as suggested in [11], for robustness analysis. We set the misprediction threshold 𝜏 to 0.2 (20%), meaning that a sample is considered stable if at least 80% of its neighbors are predicted correctly. This choice strikes a balance between sensitivity and specificity [23], ensuring that unstable samples capture meaningful misprediction patterns without being overly restrictive. While 𝜏 = 0.2 is effective in our setting, the threshold can be further tuned to optimize performance for different datasets or models. To evaluate the bounds in (5) and (6), we follow the methodology proposed in [13] by partitioning the input space into 10,000 regions. To compute 𝜖̃𝑗 (𝑆 ) and 𝜖 ∗ (𝑆 ) in (14), we first randomly

Page 10 of 17

Upper Bounds on the Generalization Error of Deep Learning Models Table 1 Different generalization bounds comparison for state-of-the-art models trained on ImageNet. Bounds given by (2), (3), (4), (5), and (6) correspond to distinct theoretical guarantees that upper bound the true error, Prob( (𝑥) ≠ 𝑦). Lower values (↓) indicate better performance. Best and second-best results are shown in bold and underlined, respectively. Std values from our bounds are consistently < 10−3 and reported as such for consistency with prior work.

Model

Error@1

Bound (2)

Bound (3)

Bound (4)

Bound (5)

Bound (6)

ResNet18 V1

0.302

1.527 ± 0.005

1.527 ± 0.005

0.917 ± 0.005

0.906 ± (< 10−3 )

𝟎.𝟖𝟔𝟗 ± (< 𝟏𝟎−𝟑 )

−3

ResNet34 V1

0.267

1.462 ± 0.005

1.462 ± 0.005

0.805 ± 0.004

0.767 ± (< 10 )

𝟎.𝟕𝟔𝟎 ± (< 𝟏𝟎−𝟑 )

ResNet50 V1

0.239

1.431 ± 0.004

1.430 ± 0.004

0.743 ± 0.004

0.712 ± (< 10−3 )

𝟎.𝟕𝟏𝟐 ± (< 𝟏𝟎−𝟑 )

−3

ResNet101 V1

0.226

1.401 ± 0.005

1.400 ± 0.005

0.688 ± 0.005

0.628 ± (< 10 )

𝟎.𝟔𝟐𝟖 ± (< 𝟏𝟎−𝟑 )

ResNet152 V1

0.217

1.395 ± 0.004

1.394 ± 0.004

0.673 ± 0.004

0.604 ± (< 10−3 )

𝟎.𝟔𝟎𝟒 ± (< 𝟏𝟎−𝟑 )

−3

ResNet50 V2

0.191

1.379 ± 0.004

1.377 ± 0.005

0.633 ± 0.004

0.544 ± (< 10 )

𝟎.𝟓𝟒𝟒 ± (< 𝟏𝟎−𝟑 )

ResNet101 V2

0.181

1.346 ± 0.004

1.344 ± 0.004

0.571 ± 0.004

0.502 ± (< 10−3 )

𝟎.𝟓𝟎𝟐 ± (< 𝟏𝟎−𝟑 )

−3

ResNet152 V2

0.177

1.337 ± 0.004

1.333 ± 0.004

0.552 ± 0.004

0.485 ± (< 10 )

𝟎.𝟒𝟖𝟓 ± (< 𝟏𝟎−𝟑 )

VGG13

0.301

1.500 ± 0.005

1.499 ± 0.005

𝟎.𝟖𝟕𝟗 ± 𝟎.𝟎𝟎𝟓

0.915 ± (< 10−3 )

0.914 ± (< 10−3 )

𝟎.𝟖𝟕𝟔 ± 𝟎.𝟎𝟎𝟒

−3

0.916 ± (< 10 )

0.914 ± (< 10−3 )

−3

VGG13 BN

0.284

1.504 ± 0.004

1.503 ± 0.005

VGG19

0.276

1.470 ± 0.005

1.469 ± 0.005

𝟎.𝟖𝟐𝟏 ± 𝟎.𝟎𝟎𝟓

0.828 ± (< 10 )

0.825 ± (< 10−3 )

VGG19 BN

0.258

1.464 ± 0.004

1.463 ± 0.005

0.803 ± 0.004

0.789 ± (< 10−3 )

𝟎.𝟕𝟖𝟗 ± (< 𝟏𝟎−𝟑 )

−3

DenseNet121

0.256

1.457 ± 0.005

1.457 ± 0.005

0.785 ± 0.005

0.739 ± (< 10 )

𝟎.𝟕𝟑𝟗 ± (< 𝟏𝟎−𝟑 )

DenseNet161

0.229

1.400 ± 0.004

1.398 ± 0.004

0.681 ± 0.004

0.612 ± (< 10−3 )

𝟎.𝟔𝟏𝟐 ± (< 𝟏𝟎−𝟑 )

−3

DenseNet169

0.244

1.422 ± 0.004

1.421 ± 0.004

0.725 ± 0.004

0.665 ± (< 10 )

𝟎.𝟔𝟔𝟓 ± (< 𝟏𝟎−𝟑 )

DenseNet201

0.231

1.393 ± 0.004

1.392 ± 0.004

0.673 ± 0.005

0.562 ± (< 10−3 )

𝟎.𝟓𝟔𝟐 ± (< 𝟏𝟎−𝟑 )

−3

Swin_b

0.164

1.347 ± 0.004

1.345 ± 0.004

0.563 ± 0.004

0.466 ± (< 10 )

𝟎.𝟒𝟔𝟔 ± (< 𝟏𝟎−𝟑 )

Swin_t

0.185

1.389 ± 0.004

1.387 ± 0.004

0.647 ± 0.004

0.536 ± (< 10−3 )

𝟎.𝟓𝟑𝟔 ± (< 𝟏𝟎−𝟑 )

−3

Swin_V2_b

0.159

1.345 ± 0.004

1.342 ± 0.004

0.551 ± 0.004

0.461 ± (< 10 )

𝟎.𝟒𝟔𝟏 ± (< 𝟏𝟎−𝟑 )

Swin_V2_t

0.179

1.373 ± 0.004

1.372 ± 0.004

0.613 ± 0.004

0.534 ± (< 10−3 )

𝟎.𝟓𝟑𝟒 ± (< 𝟏𝟎−𝟑 )

select 10,000 unstable validation samples to serve as centroids for forming unstable clusters. Using these centroids and following the procedure outlined in algorithm 2, we generated the unstable clusters {𝐶̃𝑗 }𝐾 . For each cluster 𝑗=1 𝑗 ∈ 𝐾, we compute 𝜖̃𝑗 (𝑆 ), and subsequently compute 𝜖 ∗ (𝑆 ). Similarly, to compute 𝜖̂𝑗 (𝑆 ), we randomly select 10,000 stable validation samples as centroids and following the procedure outlined in algorithm 2, we formed the stable clusters {𝐶̂𝑗 }𝐾 . For each cluster 𝑗 ∈ 𝐾, we compute 𝑗=1 𝜖̂𝑗 (𝑆 ). For bounds in Equations (2), (3) and (4), we reported the values provided in [31]. Following [31], we set 𝛿 = 0.01(99% confidence intervals) to compute the bounds. Also, we used 0 − 1 loss function and as usual any bound beyond 1 will be vacuous. The results for each model in Tables 1 and 2 are averaged over five independent runs. For each model, we report both the mean and the standard deviation (std). In Table 1, for all models, the standard deviation (std) of our bounds is smaller than three decimal places. To ensure a fair comparison with existing results, we report these values as (< 10−3 ). Finally, we excluded the generalization bound presented in Theorem 6 of [31] in our empirical comparison due to fundamental differences in formulation. Specifically, their bound eliminates the empirical risk term and instead relies on an average loss-based A.R Nuhu et al.: Preprint submitted to Elsevier

robustness measure computed over local regions. In contrast, our bound explicitly retains the empirical risk term and introduces a localized robustness characterization that distinguishes between stable and unstable regions. These structural differences lead to distinct interpretations of robustness and generalization behavior, making a direct quantitative comparison non-equivalent. Therefore, our evaluation focuses on methods with comparable formulations to ensure a consistent and meaningful comparison.

5.2. Results and discussion Figure 5a shows model performance on stable and unstable samples from the training dataset using 𝜅 = 20. Additional sensitivity analysis over randomly selected values of 𝜅 is provided in Appendix B. Specifically, we report the percentage of unstable samples for each model across five randomly selected values of 𝜅. Most models achieve nearperfect accuracy (∼ 100%) on stable samples, but performance drops substantially on unstable samples. Although drawn from the training set, these unstable samples are more challenging to classify as they lie near decision boundaries and exhibit high sensitivity to small perturbations [21]. This property makes them an effective proxy for evaluating generalization. Stable samples capture confident predictions, Page 11 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

whereas unstable samples expose the model’s behavior on challenging cases. The resulting performance gap underscores the importance of unstable samples for robustnessbased generalization assessment. A similar trend is observed across all model architectures on the validation dataset, as shown in Figure 5b. Table 1 compares prior bounds (Equations (2, 3, 4)) with our proposed bounds (Equations (5, 6)). The bound in (6) is a special case of the more general bound in (5). We present both to show that, while their differences are minimal in practice, they become important when considering specific loss functions. In particular, the bound in (6) is better suited for robustness-based generalization assessment under the 01 loss. We observe that the prior bounds in (2) and (3) yield vacuous results across all models. In contrast, the bound in (4) produces non-vacuous values; however, it relies on the average robustness value across clusters rather than the worst-case robustness within each region. Averaging can obscure weaknesses, making a model appear more reliable than it actually is, in terms of the generalization estimates. By contrast, worst-case robustness at clusters exposes these hidden vulnerabilities, leading to a more reliable generalization estimate. Our bound in (6), which leverages worst-case robustness at clusters, is non-vacuous in all cases and produces significantly better results, except for VGG13, VGG13 BN, and VGG19. In these VGG models, the average-loss approach in (4) smooths over rare, extreme failures, yielding a tighter but overly optimistic bound. Additionally, our bound tends to perform particularly well for models with lower error rates, such as ResNet V2 and SwinTransformers. These models have fewer unstable regions. As a result, this reduces the impact of the worst-case measure, keeping the bound tight while still capturing robustness. For models with higher error, unstable regions dominate, and the worstcase approach can naturally produce looser but more reliable bounds. Finally, it can be observed that our bound in (6) supports the point that, in the case of 0-1 loss, unstable samples alone are sufficient for generalization assessment. Indeed, except for a few cases, bounds (5) and (6) converge to the same values. Building on standard generalization assessment methods, we connect our theoretical bounds to practical estimation procedures by evaluating how well these bounds approximate the true risk of a trained model when the uncertainty terms are omitted. Specifically, the main generalization bounds, including Bounds (2) - (6), provide formal upper bounds on the expected risk over the sample space. Equations (9)–(11) correspond to existing methods that approximate the known test error, while Equations (12)–(13) implement our proposed estimation approach based on localized robustness. In particular, our method highlights how unstable samples can effectively approximate the upper bound of the model’s expected risk on the known test set 𝑍𝑚 , thereby providing a practical instantiation of the theoretical bounds. ̂  ( ) + 𝜖() Rob =  A.R Nuhu et al.: Preprint submitted to Elsevier

(9)

̂ 𝑆 ( ) + 𝐿𝑜𝑐𝑎𝑙𝑅𝑜𝑏 = 

𝑛𝑗 𝑛

∑ 𝑛𝑗

̂  ( ) + LocalSen = 

(10)

𝜖𝑗 (𝐡)

𝑗∈𝑇𝑆

𝑛

∑ 𝑛̃𝑗 ( )

̂  ( ) + LocalMax = 

(11)

𝜖̄𝑗 (𝐡)

𝜖̃𝑗 ( )

(12)

𝜖 ∗ ( )

(13)

𝜖 ∗ ( ) ∶= max max ||𝓁( , 𝑧) − 𝓁( , 𝑠)||

(14)

𝑗∈𝑇̃𝑆

̂  ( ) + GlobalMax = 

𝑛

∑ 𝑛̃( ) 𝑗∈𝑇̃𝑆

𝑛

where: 𝑗∈[𝐾] 𝑠,𝑧∈𝐶̃ 𝑗

Rob and LocalSen comes from prior work [31] whereas LocalMax comes from our bounds. GlobalMax is a conservative form of the LocalMax approach and it applies the single worst-case instability across all unstable samples. In contrast, LocalMax evaluates worst-case robustness within each cluster, weighted by the number of unstable samples, which yields a tighter and more precise estimate. While LocalMax is better suited for detailed expected risk estimation, GlobalMax remains useful as a quick coarse measure, providing an upper bound that complements LocalMax through fast estimation. Table 2 summarizes the results of different approaches for estimating the expected risk (i.e., the known test error) of the models. The estimate corresponding to bound (3) (Eqn. (10)) is equivalent to that of the Rob bound (9), which is derived from the base robustness-based generalization bound. Therefore, to avoid redundancy, we report only the results for the Rob bound. Both GlobalMax and LocalMax provide accurate estimates for most models when compared to LocalSen, with the exception of VGG13, VGG13 BN, and VGG19. This difference arises from the choice of robustness terms: LocalSen relies on the average local robustness within a cluster, whereas our approaches employ the worst-case robustness term. Because our method adopts a worst-case robustness perspective. Consequently, stable samples that are misclassified during the partitioning stage are classified as unstable. This increases the number of samples contributing to the robustness term. In such cases, the resulting bounds may be looser than those derived from prior approaches.

6. Conclusion In this paper, we examined prior work on robustnessbased generalization bounds and demonstrated empirically that their vacuousness can also stem from the robustness term. To address this limitation, we developed tighter robustnessbased bounds by partitioning the input space into stable and Page 12 of 17

Upper Bounds on the Generalization Error of Deep Learning Models Table 2 Upper generalization bounds on the true error (expected risk) (Prob( (𝑥) ≠ 𝑦)) of different deep neural networks (DNN) pretrained on the ImageNet dataset. The upper bounds estimates on the Error@1 is provided without considering the uncertain terms. Bold entries denote the best result for each model, and underlined entries indicate the second best.

Model

Err@1

Rob ↓

LocalSen ↓

GlobalMax ↓

LocalMax ↓

ResNet18 V1 ResNet34 V1 ResNet50 V1 ResNet101 V1 ResNet152 V1 ResNet50 V2 ResNet101 V2 ResNet152 V2 VGG13 VGG13 BN VGG19 VGG19 BN DenseNet121 DenseNet161 DenseNet169 DenseNet201 SwinTransformer B SwinTransformer T SwinTransformer B V2 SwinTransformer T V2

0.302 0.267 0.239 0.226 0.217 0.191 0.181 0.177 0.301 0.284 0.276 0.258 0.256 0.229 0.244 0.231 0.164 0.185 0.159 0.179

1.212 ± 4.0 × 10−5 1.157 ± 4.0 × 10−5 1.131 ± 6.0 × 10−5 1.105 ± 5.0 × 10−5 1.101 ± 4.0 × 10−5 1.089 ± 4.0 × 10−5 1.060 ± 2.0 × 10−5 1.052 ± 4.0 × 10−5 1.184 ± 5.0 × 10−5 1.192 ± 4.0 × 10−5 1.161 ± 6.0 × 10−5 1.159 ± 4.0 × 10−5 1.156 ± 4.0 × 10−5 1.105 ± 4.0 × 10−5 1.124 ± 4.0 × 10−5 1.098 ± 4.0 × 10−5 1.065 ± 4.0 × 10−5 1.100 ± 4.0 × 10−5 1.064 ± 2.0 × 10−5 1.087 ± 4.0 × 10−5

0.602 ± 1.9 × 10−4 0.499 ± 1.8 × 10−4 0.443 ± 3.0 × 10−4 0.392 ± 1.7 × 10−4 0.379 ± 2.4 × 10−4 0.344 ± 3.5 × 10−4 0.285 ± 3.0 × 10−4 0.267 ± 2.5 × 10−4 𝟎.𝟓𝟔𝟑 ± 𝟐.𝟔 × 𝟏𝟎−𝟒 𝟎.𝟓𝟔𝟒 ± 𝟐.𝟖 × 𝟏𝟎−𝟒 𝟎.𝟓𝟏𝟐 ± 𝟑.𝟑 × 𝟏𝟎−𝟒 0.499 ± 2.9 × 10−4 0.484 ± 1.9 × 10−4 0.386 ± 1.9 × 10−4 0.427 ± 1.6 × 10−4 0.378 ± 2.1 × 10−4 0.280 ± 1.0 × 10−4 0.358 ± 3.3 × 10−4 0.270 ± 2.4 × 10−4 0.327 ± 3.8 × 10−4

0.593 ± 1.4 × 10−5 0.455 ± 2.1 × 10−5 0.413 ± 2.3 × 10−5 0.334 ± 1.8 × 10−5 0.314 ± 3.0 × 10−5 0.258 ± 1.0 × 10−5 0.216 ± 2.6 × 10−5 0.200 ± 1.6 × 10−5 0.601 ± 6.5 × 10−5 0.605 ± 5.7 × 10−5 0.520 ± 4.5 × 10−5 0.488 ± 5.9 × 10−5 0.440 ± 4.1 × 10−5 0.318 ± 1.9 × 10−5 0.368 ± 4.3 × 10−5 0.316 ± 2.6 × 10−5 0.186 ± 1.8 × 10−5 0.298 ± 3.7 × 10−5 0.186 ± 5.3 × 10−5 0.250 ± 6.6 × 10−5

𝟎.𝟓𝟗𝟏 ± 𝟏.𝟏 × 𝟏𝟎−𝟓 𝟎.𝟒𝟓𝟒 ± 𝟏.𝟏 × 𝟏𝟎−𝟓 𝟎.𝟒𝟏𝟐 ± 𝟏.𝟔 × 𝟏𝟎−𝟓 𝟎.𝟑𝟑𝟐 ± 𝟒.𝟗 × 𝟏𝟎−𝟓 𝟎.𝟑𝟏𝟎 ± 𝟒.𝟑 × 𝟏𝟎−𝟓 𝟎.𝟐𝟓𝟓 ± 𝟑.𝟔 × 𝟏𝟎−𝟓 𝟎.𝟐𝟏𝟔 ± 𝟏.𝟒 × 𝟏𝟎−𝟓 𝟎.𝟐𝟎𝟎 ± 𝟏.𝟏 × 𝟏𝟎−𝟓 0.599 ± 1.1 × 10−5 0.602 ± 1.7 × 10−5 0.516 ± 2.4 × 10−5 𝟎.𝟒𝟖𝟓 ± 𝟏.𝟖 × 𝟏𝟎−𝟓 𝟎.𝟒𝟑𝟖 ± 𝟐.𝟏 × 𝟏𝟎−𝟓 𝟎.𝟑𝟏𝟕 ± 𝟏.𝟎 × 𝟏𝟎−𝟓 𝟎.𝟑𝟔𝟕 ± 𝟒.𝟏 × 𝟏𝟎−𝟓 𝟎.𝟑𝟏𝟐 ± 𝟏.𝟖 × 𝟏𝟎−𝟓 𝟎.𝟏𝟖𝟑 ± 𝟐.𝟒 × 𝟏𝟎−𝟓 𝟎.𝟐𝟒𝟕 ± 𝟑.𝟐 × 𝟏𝟎−𝟓 𝟎.𝟏𝟖𝟎 ± 𝟒.𝟐 × 𝟏𝟎−𝟓 𝟎.𝟐𝟒𝟖 ± 𝟐.𝟓 × 𝟏𝟎−𝟓

unstable samples, and further refining these into smaller clusters. Based on the model’s local behavior, we introduced a localized robustness term, decomposed into stable and unstable components. Our evaluations reveal that unstable samples are the dominant contributors to the robustness term. For classification tasks under the 0–1 loss, prior bounds [13] remain vacuous, while our proposed bound closely approximates the true error of classifiers. Unlike earlier approaches that rely solely on a data-dependent global robustness term, our bounds incorporate model properties to guide robustness, making them both model- and data-dependent. Moreover, our method relaxes the strict definition of robustness that traditionally constrains generalization assessment. As a result, our bounds yield sharper and more reliable generalization estimates, while also serving as effective tools for model comparison and selection. This work is not without limitations. Effectiveness of our bounds depends on the quality of the partitioning strategy. If the approach incorrectly classifies certain stable samples as unstable, the resulting bounds may become loose. Nonetheless, this limitation can be mitigated, as recent advances in partitioning methods [21] have shown strong effectiveness in handling training datasets. As a direction for future research, our treatment of the robustness term in robustness-based generalization bounds can be extended A.R Nuhu et al.: Preprint submitted to Elsevier

to refine the uncertainty component. Prior work [13] has demonstrated that the training dataset alone is sufficient to bound this uncertainty term. Building on this insight, a promising extension would be to decompose the uncertainty into stable and unstable components, which may yield tighter and more informative bounds. Finally, we plan to investigate how different loss functions influence the generalization behavior of various model architectures.

Acknowledgment This work was supported in part by NASA ULI under Grants No. 80NSSC20M0161 and 80NSSC25M7098, by the National Science Foundation under Grant No. 2301553, by the U.S. Department of Transportation University Transportation Center under Grant No. 69A3552348327, and by NC-DOT AAM and UAS under Grant No. RP 2025-43.

A. Proof of Theorem 5, Lemma 1 and Corollary 1 Proof of Theorem 5. for any 𝛿 > 0, with probability at least 1 − 𝛿 over an iid draw of 𝑛 training samples, the

Page 13 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

generalization error of  is bounded as: ̂  ( ) + 𝑍 ( ) ≤ 

∑ 𝑛̂ 𝑗 ( ) 𝑛

𝑗∈𝑇̂𝑆

+

∑ 𝑛̃𝑗 ( ) 𝑗∈𝑇̃𝑆

= ⋅ 𝜖̂𝑗 ( )

+

⋅ 𝜖̃𝑗 ( ) + 𝑢3 (𝐾, , 𝛿)

𝑛

( |𝑛𝑗 | ) 𝔼𝑧𝑗 [𝓁(ℎ, 𝑧𝑗 )] Pr(𝑧 ∈ 𝐶𝑗 ) − 𝑛 𝑗=1

𝐾 ∑

𝑗=1

(15)

To present the proof of our main theorem, we start with the following observations. We define

𝑛

𝔼𝑧𝑗 [𝓁(ℎ, 𝑧𝑗 )]

𝑗=1

and

1∑ 𝓁(ℎ, 𝑧𝑖 ) 𝑛 𝑖=1 𝑛

𝔼𝑧𝑗 [𝓁(ℎ, 𝑧𝑗 )] −

(17)

Secondly, we can expand each individual term in the second term of Equation (17) by decomposing them as follows: 𝐾 ∑

̂ 𝑛̂ 𝑗 ∶= 𝐼𝑗𝑆 ∶= { 𝑖 ∈ [𝑛( ̂  )] ∣ 𝑧𝑖 ∈ 𝐶̂𝑗 }

𝐾 ∑ |𝑛𝑗 |

|𝑛𝑗 | 𝑛

=

̃ 𝑛̃𝑗 ∶= 𝐼𝑗𝑆 ∶= { 𝑖 ∈ [̃ 𝑛( )] ∣ 𝑧𝑖 ∈ 𝐶̃𝑗 }

𝐾 ( 1∑ 𝔼 [𝓁(ℎ, 𝑧)] ̂ |𝑛̂ 𝑗 | 𝑛 𝑗=1 𝑧̂ ) + 𝔼𝑧̃[𝓁(ℎ, 𝑧̃)] |̃ 𝑛𝑗 | (18)

and

and [ ] | 𝛼𝑗 (ℎ) ∶= 𝔼𝑧 𝓁(ℎ, 𝑧) | 𝑧 ∈ 𝐶𝑗 | ] [ ] [ | | ̂ | 𝑧̂ ∈ 𝐶̂𝑗 + 𝔼𝑧̃ 𝓁(ℎ, 𝑧̃) | 𝑧̃ ∈ 𝐶̃𝑗 = 𝔼𝑧̂ 𝓁(ℎ, 𝑧) | | = 𝛼̂ 𝑗 (ℎ) + 𝛼 ̃𝑗 (ℎ) where

𝑛 𝐾 1∑∑ 1∑ 𝓁(ℎ, 𝑧𝑖 ) 𝓁(ℎ, 𝑧𝑖 ) = 𝑛 𝑖=1 𝑛 𝑗=1 𝑖∈𝑛 𝑗 ( ) 𝐾 ∑ 1∑ ∑ = 𝓁(ℎ, 𝑧̂ 𝑖 ) + 𝓁(ℎ, 𝑧̃𝑖 ) 𝑛 𝑗=1 𝑖∈𝑛̂ 𝑖∈̃ 𝑛 𝑗

(19)

𝐶̂𝑗 ∪ 𝐶̃𝑗 = 𝐶𝑗 We begin the proof with the following lemma that relates the generation gap to the concentration of multinomial distribution. Lemma 2. Consider a model ℎ ∈  and samples 𝑧𝑖 ∈  for all 𝑖 ∈ [𝑛]. Then, the generalization gap can be expressed as: 1∑ 𝓁(ℎ, 𝑧𝑖 ) 𝑛 𝑖=1 𝑛

𝔼𝑧 [𝓁(ℎ, 𝑧)] − =

( |𝑛𝑗 | ) 𝛼𝑗 (ℎ) Pr(𝑧 ∈ 𝐶𝑗 ) − 𝑛 𝑗=1 [ ] 𝐾 ∑ |𝑛𝑗 | 1 ∑ + 𝛼𝑗 (ℎ) − 𝓁(ℎ, 𝑧𝑖 ) 𝑛 |𝑛𝑗 | 𝑖∈𝑛 𝑗=1

(16)

𝑗

Where the expected error (𝔼𝑧 [𝓁(ℎ, 𝑧)]) is expressed as the sum of the conditional expected error: 𝐾 ∑

𝔼𝑧 [𝓁(ℎ, 𝑧)|𝑧 ∈ 𝐶𝑗 ] Pr(𝑧 ∈ 𝐶𝑗 )

𝑗=1

=

𝐾 ∑

𝔼𝑧𝑗 [𝓁(ℎ, 𝑧𝑗 )] Pr(𝑧 ∈ 𝐶𝑗 ),

𝑗=1

Here, 𝑧𝑗 is the random variable 𝑧 conditioned on the event 𝑧 ∈ 𝐶𝑗 . Based on this, first, we decompose the generalization gap into the following: 1∑ 𝓁(ℎ, 𝑧𝑖 ) 𝑛 𝑖=1

Now, the decomposed equation becomes this: 1∑ − 𝓁(ℎ, 𝑧𝑖 ) 𝔼𝑧𝑗 [𝓁(ℎ, 𝑧𝑗 )] 𝑛 𝑛 𝑖=1 𝑗=1 ( 𝐾 1∑ 𝔼𝑧̂ [𝓁(ℎ, 𝑧)]| ̂ 𝑛̂ 𝑗 | + 𝔼𝑧̃[𝓁(ℎ, 𝑧̃)]|̃ 𝑛𝑗 | = 𝑛 𝑗=1 ) ∑ ∑ 𝓁(ℎ, 𝑧̂ 𝑖 ) − 𝓁(ℎ, 𝑧̃𝑖 ) −

𝐾 ∑

A.R Nuhu et al.: Preprint submitted to Elsevier

(20)

𝑖∈̃ 𝑛𝑗

( 𝐾 ) 1∑ ( = 𝔼𝑧̂ [𝓁(ℎ, 𝑧)]| ̂ 𝑛̂ 𝑗 | + 𝔼𝑧̃[𝓁(ℎ, 𝑧̃)]|̃ 𝑛𝑗 | 𝑛 𝑗=1 ) ∑ ) (∑ − 𝓁(ℎ, 𝑧̂ 𝑖 ) + 𝓁(ℎ, 𝑧̃𝑖 ) 𝑖∈𝑛̂ 𝑗

(21)

𝑖∈̃ 𝑛𝑗

( 𝐾 ∑ ) 1∑ ( = 𝔼𝑧̂ [𝓁(ℎ, 𝑧)]| ̂ 𝑛̂ 𝑗 | − 𝓁(ℎ, 𝑧̂ 𝑖 ) 𝑛 𝑗=1 𝑖∈𝑛̂ 𝑗 ) ∑ ( ) + 𝔼𝑧̃[𝓁(ℎ, 𝑧̃)]|̃ 𝑛𝑗 | − 𝓁(ℎ, 𝑧̃𝑖 )

(22)

𝑖∈̃ 𝑛𝑗

Substituting these into Equation (17) yields the following:

𝑛

𝔼𝑧 [𝓁(ℎ, 𝑧)] −

𝑛

|𝑛𝑗 |

𝑖∈𝑛̂ 𝑗

𝐾 ∑

𝔼𝑧 [𝓁(ℎ, 𝑧)] =

𝑗

1∑ 𝓁(ℎ, 𝑧𝑖 ) 𝑛 𝑖=1 𝑛

𝔼𝑧 [𝓁(ℎ, 𝑧)] −

Page 14 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

=

( |𝑛𝑗 | ) 𝔼𝑧𝑗 [𝓁(ℎ, 𝑧𝑗 )] Pr(𝑧 ∈ 𝐶𝑗 ) − 𝑛 𝑗=1

𝐾 ∑

+

𝐾 ∑

|𝑛̂ 𝑗 | ( 𝑛

𝑗=1

+

𝐾 ∑

𝑗

) 1 ∑ 𝔼𝑧̂ [𝓁(ℎ, 𝑧)] ̂ − 𝓁(ℎ, 𝑧̂ 𝑖 ) |𝑛̂ 𝑗 | 𝑖∈𝑛̂

|̃ 𝑛𝑗 | ( 𝑛

𝑗

) 1 ∑ 𝔼𝑧̃[𝓁(ℎ, 𝑧̃)] − 𝓁(ℎ, 𝑧̃𝑖 ) (23) |̃ 𝑛𝑗 | 𝑖∈̃𝑛

𝑛 1∑

𝑛 𝑖=1

𝓁(ℎ, 𝑧𝑖 )

( |𝑛𝑗 | ) 𝛼𝑗 (ℎ) Pr(𝑧 ∈ 𝐶𝑗 ) − 𝑛 𝑗=1 𝐾 ∑ |𝑛̂ 𝑗 | (

𝑛

𝑗=1

+

=

𝛼̂ 𝑗 (ℎ) −

) 1 ∑ 𝓁(ℎ, 𝑧̂ 𝑖 ) |𝑛̂ 𝑗 | 𝑖∈𝑛̂ 𝑗

|̃ 𝑛𝑗 | ( 𝑛

𝑗=1

𝛼 ̃𝑗 (ℎ) −

) 1 ∑ 𝓁(ℎ, 𝑧̃𝑖 ) |̃ 𝑛𝑗 | 𝑖∈̃𝑛

𝐾 ∑ 𝑗=1

|̃ 𝑛𝑗 | 𝑛

(26)

𝜖̃𝑗 (ℎ)

Under the fixed partition of the sample space  into {𝐶𝑘 }𝐾 , each sample is assigned to a cluster according to 𝑗=1 the underlying data distribution. The corresponding cluster counts (𝑛1 , … , 𝑛𝐾 ) therefore follow a multinomial distribution with parameters 𝑛 and (Pr(𝐶1 ), … , Pr(𝐶𝐾 )). For each cluster 𝐶𝑗 , let the total number of samples be denoted by 𝑛𝑗 = 𝑛̂ 𝑗 + 𝑛̃𝑗 , where 𝑛̂ 𝑗 and 𝑛̃𝑗 represent the counts of stable and unstable samples within 𝐶𝑗 , respectively. Hence, according to Theorem 3 in [13], for any 𝛿 > 0, with probability at least 1 − 𝛿, the following holds:

𝐾 ∑

𝐾 ∑

1 𝜖̃ (ℎ) 𝑛 𝑗=1 𝑖∈̃𝑛 𝑗

≤

𝑗

𝔼𝑧 [𝓁(ℎ, 𝑧)] −

+

𝐾 ∑ ∑

𝑗

𝑗=1

=

𝐾 ( ) 1∑∑ max 𝓁(ℎ, 𝑧̃) − 𝓁(ℎ, 𝑧̃𝑖 ) 𝑛 𝑗=1 𝑖∈̃𝑛 𝑧̃∈𝑍𝑗

≤

(24)

𝑗

We can see that

( |𝑛𝑗 | ) ≤ 𝑢3 (𝐾, , 𝛿) 𝛼𝑗 (ℎ) Pr(𝑧 ∈ 𝐶𝑗 ) − 𝑛 𝑗=1

𝐾 ∑

Where

𝐾 ) ∑ |𝑛̂ 𝑗 | ( 1 ∑ 𝛼̂ 𝑗 (ℎ) − 𝓁(ℎ, 𝑧̂ 𝑖 ) 𝑛 |𝑛̂ 𝑗 | 𝑖∈𝑛̂ 𝑗=1

√

𝑢3 (𝐾, , 𝛿) = 1

ln(2𝐾∕𝛿) 22 ln(2𝐾∕𝛿) + 𝑛 𝑛

𝑗

) ∑ 1 𝓁(ℎ, 𝑧̂ 𝑖 ) = |𝑛̂ 𝑗 |𝛼̂ 𝑗 (ℎ) − 𝑛 𝑗=1 𝑖∈𝑛̂ 𝐾 ∑

(

1 ∶=

𝑗

∑ ( 𝑘∈𝑇𝑆

𝐾 ( ) 1∑∑ = 𝛼̂ 𝑗 (ℎ) − 𝓁(ℎ, 𝑧̂ 𝑖 ) 𝑛 𝑗=1 𝑖∈𝑛̂

(27)

) √ 𝛼 𝑐 (𝐴𝑆 ) + 2 𝛼𝑘 (𝐴𝑆 )

√

𝑛

𝑆

2 ∶= 𝛼 𝑐 (𝐴𝑆 ) ⋅ |𝑇𝑆 | + 𝑆

∑

|𝑘𝑆 |

,

𝛼𝑘 (𝐴𝑆 ),

𝑘∈𝑇𝑆

𝑗

≤

( ) 1 max 𝓁(ℎ, 𝑧) ̂ − 𝓁(ℎ, 𝑧̂ 𝑖 ) ̂ 𝑛 𝑗=1 𝑖∈𝑛̂ 𝑧∈𝑍 𝑗 𝐾 ∑ ∑

{ } 𝑇𝑆 ∶= 𝑘 ∈ [𝐾] ∶ |𝑘𝑆 | ≥ 1 , { } 𝑘𝑆 ∶= 𝑖 ∈ [𝑛] ∶ 𝑧𝑖 ∈ 𝐶𝑘 , [ ] 𝛼𝑘 (ℎ) ∶= 𝔼𝑧 𝓁(ℎ, 𝑧) ∣ 𝑧 ∈ 𝐶𝑘 ,

𝑗

≤

𝐾 ∑ ∑

1 𝜖̂ (ℎ) 𝑛 𝑗=1 𝑖∈𝑛̂ 𝑗

𝛼 𝑐 (𝐴𝑆 ) ∶= max𝑐 𝛼𝑘 (𝐴𝑆 ),

𝑗

=

𝐾 ∑ 𝑗=1

|𝑛̂ 𝑗 | 𝑛

𝑆

(25)

𝜖̂𝑗 (ℎ)

𝑗=1

=

𝑛

) 1 ∑ 𝛼 ̃𝑗 (ℎ) − 𝓁(ℎ, 𝑧̃𝑖 ) |̃ 𝑛𝑗 | 𝑖∈̃𝑛 𝑗

) ∑ 1 |̃ 𝑛𝑗 |̃ 𝛼𝑗 (ℎ) − 𝓁(ℎ, 𝑧̃𝑖 ) 𝑛 𝑗=1 𝑖∈̃ 𝑛

𝐾 ∑

𝑆𝑐 ∶= [𝐾] ⧵ 𝑇𝑆 . Combining (16), (25), (26), and (27) completes the proof of Theorem 5 in bound (5).

and similarly 𝐾 ∑ |̃ 𝑛𝑗 | (

𝑘∈𝑆

(

𝑗

𝐾 ( ) 1∑∑ = 𝛼 ̃𝑗 (ℎ) − 𝓁(ℎ, 𝑧̃𝑖 ) 𝑛 𝑗=1 𝑖∈̃𝑛 𝑗

A.R Nuhu et al.: Preprint submitted to Elsevier

Proof of Lemma 1. Recall that the input space  can be ̃ (undecomposed into 1 = ̂ (stable subset) and 2 =  stable subset), with 𝛼𝑖 (𝑆 ) ∶= 𝔼𝑧∼𝑖 [𝓁(𝑆 , 𝑧)] denoting the expected loss on subset 𝑖 . By the law of total expectation, the expected risk decomposes as  (𝑆 ) = 𝔼𝑧∼ [𝓁(𝑆 , 𝑧)] = 𝔼𝑧∼1 [𝓁(𝑆 , 𝑧)]ℙ(𝑧 ∈ 1 ) + 𝔼𝑧∼2 [𝓁(𝑆 , 𝑧)]ℙ(𝑧 ∈ 2 ) Page 15 of 17

Upper Bounds on the Generalization Error of Deep Learning Models

= 𝛼1 (𝑆 )ℙ(𝑧 ∈ 1 ) + 𝛼2 (𝑆 )ℙ(𝑧 ∈ 2 ). (28) Since ̂ is constructed as the stable subset where 𝑆 predicts correctly with high probability, we have 𝛼1 (𝑆 ) ≈ 0 under 0-1 loss. Moreover, ℙ(𝑧 ∈ 2 ) ≤ 1, so  (𝑆 ) ≤ ℙ(𝑧 ∈ 2 )𝛼2 (𝑆 ) (29)

≤ 𝛼2 (𝑆 ). This completes the proof of Lemma 1.

Proof of Corollary 1. In the case of 0-1 loss, or when the model exhibits smooth loss variations, the cumulative contribution of the stable clusters to the robustness term becomes negligible. Formally, this can be expressed as: 𝐾 ∑ |𝑛̂ 𝑗 | 𝑗=1

𝑛

𝜖̂𝑗 ( ) ≈ 0.

Consequently, the overall generalization bound in Theorem 5 simplifies to include only the contributions from the unstable clusters. By combining equations (16), (26), and (27), we obtain the desired bound in Corollary 1:

̂  ( ) + 𝑍 ( ) ≤ 

∑ 𝑛̃𝑗 ( ) 𝑗∈𝑇̃𝑆

𝑛

⋅ 𝜖̃𝑗 ( )

+ 𝑢3 (𝐾, , 𝛿)

(30)

This completes the proof of Corollary 1.

B. Additional results: sensitivity analysis of 𝜅 Table 3 demonstrates the robustness of our stability analysis across a broad range of neighborhood sizes 𝜅 ∈ 20, 30, 80, 120, 200. The proportion of unstable samples remains highly consistent for each model, with maximum variations below 0.2% across all values of 𝜅. For example, ResNet18 V1 exhibits a narrow range of 39.51%–39.54%, while Swin_V2_b varies only between 11.91% and 11.93%. This negligible sensitivity to 𝜅 indicates that the proposed stable/unstable partitioning is inherently robust to the choice of neighbors value. Consequently, the use of 𝜅 = 20 for neighborhood generation is well-justified and does not compromise the reliability of the analysis.

References [1] Agyapong, R.A., et al., 2021. Efficient detection of gps spoofing attacks on unmanned aerial vehicles using deep learning, in: 2021 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 01–08. doi. [2] Ballester, R., Clemente, X.A., Casacuberta, C., Madadi, M., Corneanu, C.A., Escalera, S., 2024. Predicting the generalization gap in neural networks using topological data analysis. Neurocomputing 596, 127787. doi. [3] Bellet, A., Habrard, A., 2015. Robustness and generalization for metric learning. Neurocomputing 151, 259–267. doi.

A.R Nuhu et al.: Preprint submitted to Elsevier

Table 3 Percentage of unstable samples (%) across 𝜅 ∈ {20, 30, 80, 120, 200} for various deep neural networks (DNNs) pretrained on the ImageNet dataset. The selected 𝜅 values span strict, practical, and asymptotic regimes, providing a comprehensive sensitivity analysis across neighborhood scales. Model

𝜿 = 𝟐𝟎 𝜿 = 𝟑𝟎 𝜿 = 𝟖𝟎 𝜿 = 𝟏𝟐𝟎 𝜿 = 𝟐𝟎𝟎

ResNet18 V1 ResNet34 V1 ResNet50 V1 ResNet101 V1 ResNet152 V1 ResNet50 V2 ResNet101 V2 ResNet152 V2 VGG13 VGG13 BN VGG19 VGG19 BN DenseNet121 DenseNet161 DenseNet169 DenseNet201 Swin_b Swin_t Swin_V2_b Swin_V2_t

39.53 30.19 28.79 26.32 24.64 17.14 15.57 10.98 42.32 42.29 36.47 33.43 27.63 20.68 23.69 21.08 12.65 15.58 11.93 16.62

39.51 30.19 28.78 26.33 24.64 17.16 15.55 10.98 42.30 42.28 36.46 33.42 27.63 20.66 23.68 20.84 12.65 15.58 11.93 16.62

39.52 30.17 28.77 26.34 24.62 17.15 15.55 10.96 42.29 42.27 36.45 33.43 27.62 20.66 23.69 20.83 12.65 15.58 11.91 16.63

39.53 30.18 28.79 26.31 24.64 17.16 15.57 10.96 42.28 42.26 36.44 33.41 27.61 20.68 23.67 20.83 12.62 15.57 11.92 16.61

39.54 30.17 28.80 26.33 24.63 17.16 15.56 10.95 41.96 42.26 36.46 33.41 27.63 20.67 23.67 20.83 12.63 15.56 11.91 16.62

[4] Ben-Tal, A., Nemirovski, A., 1998. Robust convex optimization. Mathematics of operations research 23, 769–805. [5] Cheng, X., Huang, K., Ma, S., 2025. Generalization and risk bounds for recurrent neural networks. Neurocomputing 616, 128825. URL: https://www.sciencedirect.com/science/article/pii/ S0925231224015960. doi. [6] Ding, X., Zhang, L., Bao, Q., Qian, Y., Wang, B., Gu, Z., Zhang, Y., 2025. Enhancing robust generalization through appropriate adversarial example attack intensity. Neurocomputing 657, 131599. doi. [7] Gabrel, V., Murat, C., Thiele, A., 2014. Recent advances in robust optimization: An overview. European Journal of Operational Research 235, 471–483. doi. [8] Guo, J., et al., 2023. A comprehensive evaluation framework for deep model robustness. Pattern Recognition 137, 109308. doi. [9] He, K., et al., 2016. Deep residual learning for image recognition, in: Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778. [10] Huang, G., et al., 2017. Densely connected convolutional networks, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). [11] Kawaguchi, K., Bengio, Y., Kaelbling, L., 2022a. Generalization in deep learning. Mathematical Aspects of Deep Learning , 112. [12] Kawaguchi, K., Huang, J., 2019. Gradient descent finds global minima for generalizable deep neural networks of practical sizes, in: 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 92–99. doi. [13] Kawaguchi, K., et al., 2022b. Robustness implies generalization via data-dependent generalization bounds, in: International conference on machine learning, PMLR. pp. 10866–10894. [14] Kebria, P.M., et al., 2018. Deep imitation learning: The impact of depth on policy performance, in: International Conference on Neural Information Processing, Springer. pp. 172–181. doi. [15] Kebria, P.M., et al., 2019a. Deep imitation learning for autonomous vehicles based on convolutional neural networks. IEEE/CAA Journal

Page 16 of 17

Upper Bounds on the Generalization Error of Deep Learning Models of Automatica Sinica 7, 82–95. doi. [16] Kebria, P.M., et al., 2019b. Evaluating architecture impacts on deep imitation learning performance for autonomous driving, in: 2019 IEEE International Conference on Industrial Technology (ICIT), IEEE. pp. 865–870. doi. [17] Kebria, P.M., et al., 2019c. Robust adaptive control of internet-based bilateral teleoperation systems with time-varying delay and model uncertainties, in: 2019 IEEE International Conference on Industrial Technology (ICIT), IEEE. pp. 187–192. doi. [18] Liu, C., Liu, Q., Li, R., Zhou, X., Kiran, M.S., Wang, X., 2025. A study on generalization of random weight network with flat loss. Neurocomputing 657, 131650. doi. [19] Liu, H., et al., 2017. Spectral ensemble clustering via weighted kmeans: Theoretical and practical evidence. IEEE Transactions on Knowledge and Data Engineering 29, 1129–1143. doi. [20] Liu, Z., et al., 2021. Swin transformer: Hierarchical vision transformer using shifted windows, in: Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 10012–10022. [21] Ngnawé, J., et al., 2024. Detecting brittle decisions for free: Leveraging margin consistency in deep robust classifiers, in: Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., Zhang, C. (Eds.), Advances in Neural Information Processing Systems, Curran Associates, Inc.. pp. 23301–23324. [22] Nuhu, A.R., et al., 2022. Negative selection approach to support formal verification and validation of blackbox models’ input constraints, in: 2022 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 413–420. doi. [23] Nuhu, A.R., et al., 2023. Local (per-input) robustness based guided adversarial training of deep neural networks, in: 2023 IEEE 14th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON), pp. 0182–0191. doi. [24] Nuhu, A.R., et al., 2026. A validation strategy for deep learning models: Evaluating and enhancing robustness. IEEE Open Journal of the Computer Society 7, 276–289. doi:doi: 10.1109/OJCS.2025.3650722. [25] Rice, L., et al., 2021. Robustness between the worst and average case, in: Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., Vaughan, J.W. (Eds.), Advances in Neural Information Processing Systems, Curran Associates, Inc.. pp. 27840–27851. [26] Rohlfs, C., 2025. Generalization in neural networks: A broad survey. Neurocomputing 611, 128701. doi:doi: https://doi.org/10.1016/j.neucom.2024.128701. doi. [27] Russakovsky, O., et al., 2015. Imagenet large scale visual recognition challenge. International journal of computer vision 115, 211–252. doi. [28] Sarkar, M., et al., 2025. A data-driven approach for performance evaluation of autonomous evtols. IEEE Transactions on Aerospace and Electronic Systems 61, 3626–3641. doi. [29] Simonyan, K., Zisserman, A., 2015. Very deep convolutional networks for large-scale image recognition, in: 3rd International Conference on Learning Representations (ICLR 2015), Computational and Biological Learning Society. pp. 1–14. [30] Sokolić, J., et al., 2017. Robust large margin deep neural networks. IEEE Transactions on Signal Processing 65, 4265–4280. doi. [31] Than, K., Phan, D., Vu, G., 2025. Gentle local robustness implies generalization. Machine Learning 114, 142. doi. [32] Xu, H., Mannor, S., 2012. Robustness and generalization. Machine learning 86, 391–423. doi. [33] Zeleke, L., et al., 2025. An integrated encounter modeling and simulation tool for a robust detect-and-avoid system evaluation. Aerospace Science and Technology , 110613doi. [34] Zhong, Z., Tian, Y., Ray, B., 2021. Understanding local robustness of deep neural networks under natural variations, in: Fundamental Approaches to Software Engineering: 24th International Conference, FASE 2021, Springer International Publishing. pp. 313–337. doi.

A.R Nuhu et al.: Preprint submitted to Elsevier

Page 17 of 17