On the Minimal Degree Bias in Generalization on the Unseen for non-Boolean Functions

• URL: http://arxiv.org/abs/2406.06354v1
• Date: Mon, 10 Jun 2024 15:14:33 GMT
• Title: On the Minimal Degree Bias in Generalization on the Unseen for non-Boolean Functions
• Authors: Denys Pushkin, Raphaël Berthier, Emmanuel Abbe,
• Abstract summary: 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, the convergence takes place to interpolators of minimal degree. We then consider the sparse target regime and explain how this regime relates to the small feature regime.
• Score: 19.203590688200777
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Generalization error of min-norm interpolators in transfer learning [2.7309692684728617]
  Min-norm interpolators emerge naturally as implicit regularized limits of modern machine learning algorithms. In many applications, a limited amount of test data may be available during training, yet properties of min-norm in this setting are not well-understood. We establish a novel anisotropic local law to achieve these characterizations.
  arXiv  Detail & Related papers  (2024-06-20T02:23:28Z)
• Generalization on the Unseen, Logic Reasoning and Degree Curriculum [25.7378861650474]
  This paper considers the learning of logical (Boolean) functions with a focus on the generalization on the unseen (GOTU) setting. We study how different network architectures trained by (S)GD perform under GOTU. More specifically, this means an interpolator of the training data that has minimal Fourier mass on the higher degree basis elements.
  arXiv  Detail & Related papers  (2023-01-30T17:44:05Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  We introduce an energy constrained diffusion model which encodes a batch of instances from a dataset into evolutionary states. We provide rigorous theory that implies closed-form optimal estimates for the pairwise diffusion strength among arbitrary instance pairs. Experiments highlight the wide applicability of our model as a general-purpose encoder backbone with superior performance in various tasks.
  arXiv  Detail & Related papers  (2023-01-23T15:18:54Z)
• Do highly over-parameterized neural networks generalize since bad solutions are rare? [0.0]
  Empirical Risk Minimization (ERM) for learning leads to zero training error. We show that under certain conditions the fraction of "bad" global minima with a true error larger than epsilon decays to zero exponentially fast with the number of training data n.
  arXiv  Detail & Related papers  (2022-11-07T14:02:07Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures [44.87247707099189]
  This paper considers the Pointer Value Retrieval (PVR) benchmark introduced in [ZRKB21], where a'reasoning' function acts on a string of digits to produce the label. It is first shown that in order to learn logical functions with gradient descent on symmetric neural networks, the generalization error can be lower-bounded in terms of the noise-stability of the target function.
  arXiv  Detail & Related papers  (2022-05-26T21:53:47Z)
• Imputing Missing Observations with Time Sliced Synthetic Minority Oversampling Technique [0.3973560285628012]
  We present a simple yet novel time series imputation technique with the goal of constructing an irregular time series that is uniform across every sample in a data set. We fix a grid defined by the midpoints of non-overlapping bins (dubbed "slices") of observation times and ensure that each sample has values for all of the features at that given time. This allows one to both impute fully missing observations to allow uniform time series classification across the entire data and, in special cases, to impute individually missing features.
  arXiv  Detail & Related papers  (2022-01-14T19:23:24Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• Predicting Unreliable Predictions by Shattering a Neural Network [145.3823991041987]
  Piecewise linear neural networks can be split into subfunctions. Subfunctions have their own activation pattern, domain, and empirical error. Empirical error for the full network can be written as an expectation over subfunctions.
  arXiv  Detail & Related papers  (2021-06-15T18:34:41Z)
• On the Minimal Error of Empirical Risk Minimization [90.09093901700754]
  We study the minimal error of the Empirical Risk Minimization (ERM) procedure in the task of regression. Our sharp lower bounds shed light on the possibility (or impossibility) of adapting to simplicity of the model generating the data.
  arXiv  Detail & Related papers  (2021-02-24T04:47:55Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.