On the Minimal Degree Bias in Generalization on the Unseen for non-Boolean Functions
This work addresses theoretical understanding of generalization in machine learning models, particularly for non-Boolean functions, but is incremental as it builds on prior Boolean case results.
The paper investigates out-of-domain generalization for random feature models and Transformers, showing that in the 'generalization on the unseen' setting, these models converge to minimal degree interpolators in specific regimes like small features or with q-ary data embedded as roots of unities, but not in more general integer or real-valued settings.
We investigate the out-of-domain generalization of random feature (RF) models and Transformers. We first prove that in the `generalization on the unseen (GOTU)' setting, where training data is fully seen in some part of the domain but testing is made on another part, and for RF models in the small feature regime, the convergence takes place to interpolators of minimal degree as in the Boolean case (Abbe et al., 2023). We then consider the sparse target regime and explain how this regime relates to the small feature regime, but with a different regularization term that can alter the picture in the non-Boolean case. We show two different outcomes for the sparse regime with q-ary data tokens: (1) if the data is embedded with roots of unities, then a min-degree interpolator is learned like in the Boolean case for RF models, (2) if the data is not embedded as such, e.g., simply as integers, then RF models and Transformers may not learn minimal degree interpolators. This shows that the Boolean setting and its roots of unities generalization are special cases where the minimal degree interpolator offers a rare characterization of how learning takes place. For more general integer and real-valued settings, a more nuanced picture remains to be fully characterized.