A Sharper Picture of Generalization in Transformers
For researchers studying transformer generalization, this provides a new theoretical framework (PAC-Bayes) yielding non-vacuous bounds, though the setting is restricted to boolean domains.
The authors derive non-vacuous generalization bounds for transformers on boolean functions by showing that sparse, low-degree Fourier spectra enable flat minima, and validate their theoretical construction empirically.
We study transformers' generalization behavior on boolean domains from the perspective of the Fourier Spectra of their target functions. In contrast to prior work (Edelman et al., 2022; Trauger and Tewari, 2024), which derived generalization bounds from Rademacher complexity, we investigate the feasibility of obtaining generalization bounds via PAC-Bayes theory. We show that sparse spectra concentrated on low-degree components enable low-sharpness constructions with good generalization properties. Our idea is to show the existence of flat minima implementing any boolean function of sparsity no greater than the context length, and then apply a PAC-Bayes bound to an idealized low-sharpness learner, resulting in a non-vacuous generalization bound. We evaluate predictions empirically and conduct a mechanistic interpretability study to support the realism of our theoretical construction in real transformers.