Information-Theoretic Generalization Bounds for Transductive Learning and its Applications
Not on the map. Why?
Abstract (arXiv)
In this paper, we establish generalization bounds for transductive learning algorithms in the context of information theory and PAC-Bayes, covering both the random sampling and the random splitting setting. First, we show that the transductive generalization gap can be controlled by the mutual information between training label selection and the hypothesis. Next, we propose the concept of transductive supersample and use it to derive transductive information-theoretic bounds involving conditional mutual information and different information measures. We further establish transductive PAC-Bayesian bounds with weaker assumptions on the type of loss function and the number of training and test data points. Lastly, we use the theoretical results to derive upper bounds for adaptive optimization algorithms under the transductive learning setting. We also apply them to semi-supervised learning and transductive graph learning scenarios, meanwhile validating the derived bounds by experiments on synthetic and real-world datasets.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 84 of its 147 references that are in the map. First posted on arXiv 8 Nov 2023.
Builds on
84 of 147 references.
References · 84
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Graph Attention Networkscited by 8,854
- 2017Neural Message Passing for Quantum Chemistrycited by 3,460
- 2016Wide Residual Networkscited by 3,057
- 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,404
- 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,134
- 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
- 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
- 2020Simple and Deep Graph Convolutional Networkscited by 857
- 2015Deep Learning and the Information Bottleneck Principlecited by 793
- 2019Neural Graph Collaborative Filteringcited by 660
- 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
38 more
- 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
- 2017Opening the Black Box of Deep Neural Networks via Informationcited by 494
- 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
- 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
- 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
- 2021User-friendly introduction to PAC-Bayes boundscited by 234
- 2020Spatial-Temporal Fusion Graph Neural Networks for Traffic Flow Forecastingcited by 212
- 2018Formal Limitations on the Measurement of Mutual Informationcited by 189
- 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
- 2018Contextual Stochastic Block Modelscited by 134
- 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 125
- 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
- 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
- 2020Tighter risk certificates for neural networkscited by 112
- 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
- 2023How Does Information Bottleneck Help Deep Learning?cited by 92
- 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
- 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
- 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
- 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
- 2022Fisher SAM: Information Geometry and Sharpness Aware Minimisationcited by 84
- 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
- 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 79
- 2020Molecular graph generation with Graph Neural Networkscited by 79
- 2022PAC-Bayes Compression Bounds So Tight That They Can Explain Generalizationcited by 75
- 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
- 2023Generalization Bounds: Perspectives from Information Theory and PAC-Bayescited by 60
- 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
- 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
- 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
- 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
- 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
- 2021Generalization Bounds For Meta-Learning: An Information-Theoretic Analysiscited by 45
- 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
- 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
- 2022Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guaranteescited by 34
- 2020Information-Theoretic Generalization Bounds for Meta-Learning and Applicationscited by 32
- 2020Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networkscited by 31
50 most cited of 84 All 84 (JSON)
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.