Overfitting Regimes of Nadaraya-Watson Interpolators

• URL: http://arxiv.org/abs/2502.07480v1
• Date: Tue, 11 Feb 2025 11:41:09 GMT
• Title: Overfitting Regimes of Nadaraya-Watson Interpolators
• Authors: Daniel Barzilai, Guy Kornowski, Ohad Shamir,
• Abstract summary: We revisit the classic interpolating Nadaraya-Watson (NW) estimator (also known as Shepard's method) We prove the existence of multiple overfitting behaviors, ranging non-monotonically from catastrophic, through benign, to tempered. Results highlight how even classical interpolating methods can exhibit intricate generalization behaviors.
• Score: 34.21221751079377
• License:
• Abstract: In recent years, there has been much interest in understanding the generalization behavior of interpolating predictors, which overfit on noisy training data. Whereas standard analyses are concerned with whether a method is consistent or not, recent observations have shown that even inconsistent predictors can generalize well. In this work, we revisit the classic interpolating Nadaraya-Watson (NW) estimator (also known as Shepard's method), and study its generalization capabilities through this modern viewpoint. In particular, by varying a single bandwidth-like hyperparameter, we prove the existence of multiple overfitting behaviors, ranging non-monotonically from catastrophic, through benign, to tempered. Our results highlight how even classical interpolating methods can exhibit intricate generalization behaviors. Numerical experiments complement our theory, demonstrating the same phenomena.

Related papers

• Enhancing Anomaly Detection Generalization through Knowledge Exposure: The Dual Effects of Augmentation [9.740752855568202]
  Anomaly detection involves identifying instances within a dataset that deviates from the norm and occur infrequently. Current benchmarks tend to favor methods biased towards low diversity in normal data, which does not align with real-world scenarios. We propose new testing protocols and a novel method called Knowledge Exposure (KE), which integrates external knowledge to comprehend concept dynamics.
  arXiv  Detail & Related papers  (2024-06-15T12:37:36Z)
• Generalized Laplace Approximation [23.185126261153236]
  We introduce a unified theoretical framework to attribute Bayesian inconsistency to model misspecification and inadequate priors. We propose the generalized Laplace approximation, which involves a simple adjustment to the Hessian matrix of the regularized loss function. We assess the performance and properties of the generalized Laplace approximation on state-of-the-art neural networks and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-22T11:11:42Z)
• A U-turn on Double Descent: Rethinking Parameter Counting in Statistical Learning [68.76846801719095]
  We show that double descent appears exactly when and where it occurs, and that its location is not inherently tied to the threshold p=n. This provides a resolution to tensions between double descent and statistical intuition.
  arXiv  Detail & Related papers  (2023-10-29T12:05:39Z)
• 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)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• Fluctuations, Bias, Variance & Ensemble of Learners: Exact Asymptotics for Convex Losses in High-Dimension [25.711297863946193]
  We develop a theory for the study of fluctuations in an ensemble of generalised linear models trained on different, but correlated, features. We provide a complete description of the joint distribution of the empirical risk minimiser for generic convex loss and regularisation in the high-dimensional limit.
  arXiv  Detail & Related papers  (2022-01-31T17:44:58Z)
• Interpolation can hurt robust generalization even when there is no noise [76.3492338989419]
  We show that avoiding generalization through ridge regularization can significantly improve generalization even in the absence of noise. We prove this phenomenon for the robust risk of both linear regression and classification and hence provide the first theoretical result on robust overfitting.
  arXiv  Detail & Related papers  (2021-08-05T23:04:15Z)
• The Role of Mutual Information in Variational Classifiers [47.10478919049443]
  We study the generalization error of classifiers relying on encodings trained on the cross-entropy loss. We derive bounds to the generalization error showing that there exists a regime where the generalization error is bounded by the mutual information.
  arXiv  Detail & Related papers  (2020-10-22T12:27:57Z)
• Learning from Aggregate Observations [82.44304647051243]
  We study the problem of learning from aggregate observations where supervision signals are given to sets of instances. We present a general probabilistic framework that accommodates a variety of aggregate observations. Simple maximum likelihood solutions can be applied to various differentiable models.
  arXiv  Detail & Related papers  (2020-04-14T06:18:50Z)

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.