Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds

2023/10/31 by Ziqiao Wang, Wang, Ziqiao, Yongyi Mao +1
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Domain Adaptation and Few-Shot Learning #Distributed Sensor Networks and Detection Algorithms

paper · pdf · doi:10.48550/arxiv.2310.20102

Abstract

We present new information-theoretic generalization guarantees through the a novel construction of the "neighboring-hypothesis" matrix and a new family of stability notions termed sample-conditioned hypothesis (SCH) stability. Our approach yields sharper bounds that improve upon previous information-theoretic bounds in various learning scenarios. Notably, these bounds address the limitations of existing information-theoretic bounds in the context of stochastic convex optimization (SCO) problems, as explored in the recent work by Haghifam et al. (2023).

Related

• Information Theoretic Lower Bounds for Information Theoretic Upper Bounds
• Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization
• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
• Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization
• Data-Dependent Stability of Stochastic Gradient Descent