PAC-Chernoff Bounds: Understanding Generalization in the Interpolation Regime

• URL: http://arxiv.org/abs/2306.10947v3
• Date: Mon, 29 Apr 2024 08:47:57 GMT
• Title: PAC-Chernoff Bounds: Understanding Generalization in the Interpolation Regime
• Authors: Andrés R. Masegosa, Luis A. Ortega,
• Abstract summary: This paper introduces a distribution-dependent PAC-Chernoff bound that exhibits perfect tightness for interpolators. We present a unified theoretical framework revealing why certain interpolators show an exceptional generalization, while others falter.
• Score: 6.645111950779666
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This paper introduces a distribution-dependent PAC-Chernoff bound that exhibits perfect tightness for interpolators, even within over-parameterized model classes. This bound, which relies on basic principles of Large Deviation Theory, defines a natural measure of the smoothness of a model, characterized by simple real-valued functions. Building upon this bound and the new concept of smoothness, we present an unified theoretical framework revealing why certain interpolators show an exceptional generalization, while others falter. We theoretically show how a wide spectrum of modern learning methodologies, encompassing techniques such as $\ell_2$-norm, distance-from-initialization and input-gradient regularization, in combination with data augmentation, invariant architectures, and over-parameterization, collectively guide the optimizer toward smoother interpolators, which, according to our theoretical framework, are the ones exhibiting superior generalization performance. This study shows that distribution-dependent bounds serve as a powerful tool to understand the complex dynamics behind the generalization capabilities of over-parameterized interpolators.

Related papers

• Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms [15.473123662393169]
  Deep neural networks (DNNs) show remarkable generalization properties. The source of these capabilities remains elusive, defying the established statistical learning theory. Recent studies have revealed that properties of training trajectories can be indicative of generalization.
  arXiv  Detail & Related papers  (2024-07-11T17:56:03Z)
• A PAC-Bayesian Perspective on the Interpolating Information Criterion [54.548058449535155]
  We show how a PAC-Bayes bound is obtained for a general class of models, characterizing factors which influence performance in the interpolating regime. We quantify how the test error for overparameterized models achieving effectively zero training error depends on the quality of the implicit regularization imposed by e.g. the combination of model, parameter-initialization scheme.
  arXiv  Detail & Related papers  (2023-11-13T01:48:08Z)
• A Unified Approach to Controlling Implicit Regularization via Mirror Descent [18.536453909759544]
  Mirror descent (MD) is a notable generalization of gradient descent (GD) We show that MD can be implemented efficiently and enjoys fast convergence under suitable conditions.
  arXiv  Detail & Related papers  (2023-06-24T03:57:26Z)
• 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)
• Towards Principled Disentanglement for Domain Generalization [90.9891372499545]
  A fundamental challenge for machine learning models is generalizing to out-of-distribution (OOD) data. We first formalize the OOD generalization problem as constrained optimization, called Disentanglement-constrained Domain Generalization (DDG) Based on the transformation, we propose a primal-dual algorithm for joint representation disentanglement and domain generalization.
  arXiv  Detail & Related papers  (2021-11-27T07:36:32Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Posterior Differential Regularization with f-divergence for Improving Model Robustness [95.05725916287376]
  We focus on methods that regularize the model posterior difference between clean and noisy inputs. We generalize the posterior differential regularization to the family of $f$-divergences. Our experiments show that regularizing the posterior differential with $f$-divergence can result in well-improved model robustness.
  arXiv  Detail & Related papers  (2020-10-23T19:58:01Z)
• Generalization Properties of Optimal Transport GANs with Latent Distribution Learning [52.25145141639159]
  We study how the interplay between the latent distribution and the complexity of the pushforward map affects performance. Motivated by our analysis, we advocate learning the latent distribution as well as the pushforward map within the GAN paradigm.
  arXiv  Detail & Related papers  (2020-07-29T07:31:33Z)
• Stochastic spectral embedding [0.0]
  We propose a novel sequential adaptive surrogate modeling method based on "stochastic spectral embedding" (SSE) We show how the method compares favorably against state-of-the-art sparse chaos expansions on a set of models with different complexity and input dimension.
  arXiv  Detail & Related papers  (2020-04-09T11:00:07Z)

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.