Generalization Bound

Generalization bounds in machine learning aim to quantify a model's ability to perform well on unseen data, based on its performance on training data. Current research focuses on developing tighter bounds for various architectures, including neural networks (especially deep and "nearly-linear" networks), large language models, and graph neural networks, often employing techniques like sample compression, PAC-Bayesian analysis, and information-theoretic approaches. These advancements are crucial for understanding and improving the reliability and robustness of machine learning models, particularly in high-stakes applications where generalization is paramount. The development of practically computable and informative bounds remains a significant challenge and active area of investigation.

Papers

February 21, 2023

Generalization Bounds for Adversarial Contrastive Learning
Xin Zou, Weiwei Liu
Adversarial Attack Adversarial Training Generalization Bound Adversarial Risk Adversarial Contrastive Learning

February 18, 2023

Generalization and Stability of Interpolating Neural Networks with Minimal Width
Hossein Taheri, Christos Thrampoulidis
Neural Network Strong Generalization Gradient Descent Core Stability Learning Rate Generalization Bound Shallow Neural Network Minimum Width

February 17, 2023

PAC-Bayesian Generalization Bounds for Adversarial Generative Models
Sokhna Diarra Mbacke, Florence Clerc, Pascal Germain
Generative Model Generalization Bound Wasserstein Gan PAC Bayesian Generalization Bound Non Vacuous Generalization Bound

February 9, 2023

Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion
Haotian Ju, Dongyue Li, Aneesh Sharma, Hongyang R. Zhang
Graph Neural Network Strong Generalization Generalization Bound Generalization Gap Graph Diffusion Graph Level Classification Graph Isomorphism Network PAC Bayesian Bound Message Passing Network

February 6, 2023

Generalization Bounds with Data-dependent Fractal Dimensions
Benjamin Dupuis, George Deligiannidis, Umut Şimşekli
Generalization Bound Generalization Guarantee Fractal Structure Fractal Dimension

January 28, 2023

Norm-based Generalization Bounds for Compositionally Sparse Neural Networks
Tomer Galanti, Mengjia Xu, Liane Galanti, Tomaso Poggio
Deep Neural Network Sparsity Increase Generalization Bound Sparse Neural Network Sparse Deep Norm Based Generalization Bound

January 27, 2023

Algorithmic Stability of Heavy-Tailed SGD with General Loss Functions
Anant Raj, Lingjiong Zhu, Mert Gürbüzbalaban, Umut Şimşekli
Stochastic Gradient Descent Generalization Bound Algorithmic Stability Novel Loss

January 17, 2023

Transformers as Algorithms: Generalization and Stability in In-context Learning
Yingcong Li, M. Emrullah Ildiz, Dimitris Papailiopoulos, Samet Oymak
Strong Generalization Transformer Megatron Decepticons Practical Algorithm Context Learning Core Stability Generalization Bound Multitask Learning Attention Based Architecture Online Inference

December 23, 2022

Generalization Bounds for Few-Shot Transfer Learning with Pretrained Classifiers
Tomer Galanti, András György, Marcus Hutter
Transfer Learning Generalization Bound Feature Embeddings Unseen Class Dimensional Collapse Pre Trained Classifier

December 16, 2022

Generalization Bounds for Inductive Matrix Completion in Low-noise Settings
Antoine Ledent, Rodrigo Alves, Yunwen Lei, Yann Guermeur, Marius Kloft
Generalization Bound Matrix Completion Robust Recovery Inductive Matrix Completion

December 12, 2022

On Generalization and Regularization via Wasserstein Distributionally Robust Optimization
Qinyu Wu, Jonathan Yu-Meng Li, Tiantian Mao
Strong Generalization Generalization Bound Robust Optimization Risk Minimization Wasserstein Distributionally Robust

November 24, 2022

PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization
Sanae Lotfi, Marc Finzi, Sanyam Kapoor, Andres Potapczynski, Micah Goldblum, Andrew Gordon Wilson
Deep Learning Deep Neural Network Strong Generalization Generalization Bound Upper Bound PAC Bayes Bound Non Vacuous Generalization Bound

November 19, 2022

Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal States
Ziqiao Wang, Yongyi Mao
Strong Generalization Stochastic Gradient Descent Generalization Bound Information Theoretic Stochastic Differential Equation Diffusion SDE Training Trajectory

November 12, 2022

A Generalized Doubly Robust Learning Framework for Debiasing Post-Click Conversion Rate Prediction
Quanyu Dai, Haoxuan Li, Peng Wu, Zhenhua Dong, Xiao-Hua Zhou, Rui Zhang, Rui zhang, Jie Sun
Generalization Performance Generalization Bound Doubly Robust Conversion Rate Prediction Robustness Bias Post Click

November 2, 2022

Instance-Dependent Generalization Bounds via Optimal Transport
Songyan Hou, Parnian Kassraie, Anastasis Kratsios, Andreas Krause, Jonas Rothfuss
Strong Generalization Stochastic Gradient Descent Optimal Transport Generalization Bound Generalization Problem

October 24, 2022

PAC-Bayesian Offline Contextual Bandits With Guarantees
Otmane Sakhi, Pierre Alquier, Nicolas Chopin
Contextual Bandit Generalization Bound Formal Guarantee Moral Tractability Offline Contextual Bandit