Low-Dimension-to-High-Dimension Generalization And Its Implications for Length Generalization

• URL: http://arxiv.org/abs/2410.08898v1
• Date: Fri, 11 Oct 2024 15:18:43 GMT
• Title: Low-Dimension-to-High-Dimension Generalization And Its Implications for Length Generalization
• Authors: Yang Chen, Yitao Liang, Zhouchen Lin,
• Abstract summary: We show that LDHD generalization is generally unattainable without exploiting prior knowledge to provide appropriate inductive bias. Applying the insights from LDHD generalization to length generalization, we explain the effectiveness of CoT as changing the structure latent space. We also propose a principle for position embedding design to handle both the inherent LDHD generalization and the nuisances such as the data format.
• Score: 61.51372812489661
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Low-Dimension-to-High-Dimension (LDHD) generalization is a special case of Out-of-Distribution (OOD) generalization, where the training data are restricted to a low-dimensional subspace of the high-dimensional testing space. Assuming that each instance is generated from a latent variable and the dimension of the latent variable reflects the problem scale, the inherent scaling challenge in length generalization can be captured by the LDHD generalization in the latent space. We theoretically demonstrate that LDHD generalization is generally unattainable without exploiting prior knowledge to provide appropriate inductive bias. Specifically, we explore LDHD generalization in Boolean functions. We verify that different architectures trained with (S)GD converge to \emph{min-degree interpolators w.r.t. different independent sets}. LDHD generalization is achievable if and only if the target function coincides with this inductive bias. Applying the insights from LDHD generalization to length generalization, we explain the effectiveness of CoT as changing the structure latent space to enable better LDHD generalization. We also propose a principle for position embedding design to handle both the inherent LDHD generalization and the nuisances such as the data format. Following the principle, we propose a novel position embedding called RPE-Square that remedies the RPE for dealing with the data format nuisance.

Related papers

• PDE+: Enhancing Generalization via PDE with Adaptive Distributional Diffusion [66.95761172711073]
  generalization of neural networks is a central challenge in machine learning. We propose to enhance it directly through the underlying function of neural networks, rather than focusing on adjusting input data. We put this theoretical framework into practice as $textbfPDE+$ ($textbfPDE$ with $textbfA$daptive $textbfD$istributional $textbfD$iffusion)
  arXiv  Detail & Related papers  (2023-05-25T08:23:26Z)
• 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)
• Generalization Error of GAN from the Discriminator's Perspective [9.975163460952045]
  We consider a simplified GAN model with the generator replaced by a density, and analyze how the discriminator contributes to generalization. We show that with early stopping, the generalization error measured by Wasserstein metric escapes from the curse of dimensionality, despite that in the long term, memorization is inevitable.
  arXiv  Detail & Related papers  (2021-07-08T06:58:43Z)
• Double Descent and Other Interpolation Phenomena in GANs [2.7007335372861974]
  We study the generalization error as a function of latent space dimension in generative adversarial networks (GANs) We develop a novel pseudo-supervised learning approach for GANs where the training utilizes pairs of fabricated (noise) inputs in conjunction with real output samples. While our analysis focuses mostly on linear models, we also apply important insights for improving generalization of nonlinear, multilayer GANs.
  arXiv  Detail & Related papers  (2021-06-07T23:07:57Z)
• Measuring Generalization with Optimal Transport [111.29415509046886]
  We develop margin-based generalization bounds, where the margins are normalized with optimal transport costs. Our bounds robustly predict the generalization error, given training data and network parameters, on large scale datasets.
  arXiv  Detail & Related papers  (2021-06-07T03:04:59Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• When Does Preconditioning Help or Hurt Generalization? [74.25170084614098]
  We show how the textitimplicit bias of first and second order methods affects the comparison of generalization properties. We discuss several approaches to manage the bias-variance tradeoff, and the potential benefit of interpolating between GD and NGD.
  arXiv  Detail & Related papers  (2020-06-18T17:57:26Z)

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.