Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization
Authors:
- Mahdi HaghifamMHMahdi Haghifam
- Borja Rodríguez-GálvezBRBorja Rodríguez-Gálvez
- Ragnar ThobabenRTRagnar Thobaben
- Mikael SkoglundMSMikael Skoglund
- Daniel M. RoyDRDaniel M. Roy
- Gintare Karolina DziugaiteGDGintare Karolina Dziugaite
Preprint
Abstract
To date, no "information-theoretic" frameworks for reasoning about generalization error have been shown to establish minimax rates for gradient descent in the setting of stochastic convex optimization. In this work, we consider the prospect of establishing such rates via several existing information-theoretic frameworks: input-output mutual information bounds, conditional mutual information bounds and variants, PAC-Bayes bounds, and recent conditional variants thereof. We prove that none of these bounds are able to establish minimax rates. We then consider a common tactic employed in studying gradient methods, whereby the final iterate is corrupted by Gaussian noise, producing a noisy "surrogate" algorithm. We prove that minimax rates cannot be established via the analysis of such surrogates. Our results suggest that new ideas are required to analyze gradient descent using information-theoretic techniques.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Formal limitations of sample-wise information-theoretic generalization bounds2022
- Population Risk Improvement with Model Compression: An Information-Theoretic ApproachEntropy, 2021
- Upper Bounds on the Generalization Error of Private Algorithms for Discrete DataIEEE Transactions on Information Theory, 2021
- On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm2021
- Tightening Mutual Information-Based Bounds on Generalization ErrorIEEE Journal on Selected Areas in Information Theory, 2020
- How Much Does Your Data Exploration Overfit? Controlling Bias via Information UsageIEEE Transactions on Information Theory, 2019
- Adaptive estimation of a quadratic functional by model selectionThe Annals of Statistics, 2000
- Some PAC-Bayesian TheoremsMachine Learning, 1999