Topological generalization bounds for discrete-time stochastic optimization algorithms
Author(s)
Birdal, Tolga
Andreeva, Rayna
Dupuis, Benjamin
Sarkar, Rik
Simsekli, Umut
Type
Conference Paper
Abstract
We present a novel set of rigorous and computationally efficient topology-based complexity notions that exhibit a strong correlation with the generalization gap in modern deep neural networks (DNNs). DNNs show remarkable generalization properties, yet the source of these capabilities remains elusive, defying the established statistical learning theory. Recent studies have revealed that properties of training trajectories can be indicative of generalization. Building on this insight, state-of-the-art methods have leveraged the topology of these trajectories, particularly their fractal dimension, to quantify generalization. Most existing works compute this quantity by assuming continuous- or infinite-time training dynamics, complicating the development of practical estimators capable of accurately predicting generalization without access to test data. In this paper, we respect the discrete-time nature of training trajectories and investigate the underlying topological quantities that can be amenable to topological data analysis tools. This leads to a new family of reliable topological complexity measures that provably bound the generalization error, eliminating the need for restrictive geometric assumptions. These measures are computationally friendly, enabling us to propose simple yet effective algorithms for computing generalization indices. Moreover, our flexible framework can be extended to different domains, tasks, and architectures. Our experimental results demonstrate that our new complexity measures exhibit a strong correlation with generalization error in industry-standard architectures such as transformers and deep graph networks. Our approach consistently outperforms existing topological bounds across a wide range of datasets, models, and optimizers, highlighting the practical relevance and effectiveness of our complexity measures.
Date Issued
2024-12-10
Date Acceptance
2024-09-18
Citation
Advances in neural information processing systems, 2024, 37, pp.4765-4818
ISBN
9798331314385
ISSN
1049-5258
Publisher
Curran Associates, Inc.
Start Page
4765
End Page
4818
Journal / Book Title
Advances in neural information processing systems
Volume
37
Copyright Statement
© 2024 The Author(s).
Source
38th Conference on Neural Information Processing Systems (NeurIPS 2024)
Publication Status
Published
Start Date
2024-12-10
Finish Date
2024-12-15
Coverage Spatial
Vancouver, Canada