Upper Bounds on the Generalization Error of Deep Learning Models via Local Robustness and Stability
For deep learning practitioners and safety-critical applications, this work provides a practical and tighter generalization bound that links robustness to generalization, addressing the vacuousness issue of prior bounds.
The paper proposes a new generalization bound for deep learning models that scales the robustness term by the number of stable and unstable samples in sub-regions of the input space, yielding tighter and non-vacuous upper bounds on true error. On ImageNet, their bounds achieve the tightest estimates among existing methods, closely matching empirical performance.
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.