Information-Theoretic Generalization Bounds for the Subtask Problem

This paper focuses on the generalization error of the subtask problem, which is a specific instance of distribution shift in supervised learning. Here, the training data generated from the source domain consists of multiple classes or labels, while the data for the target domain only encompasses a specific subset of the classes encountered during training. We study the generalization error for this problem using information-theoretic tools. We start by considering the conditional mutual information (CMI) based bounds, and we show that tighter results can be obtained for the subtask problem compared to the bounds designed for general domain shifts. Then, we consider the PAC-Bayesian setting and provide a high probability bound. Furthermore, we focus on the Gibbs algorithm, which achieves the tightest PAC-Bayesian bound, and we can obtain an exact characterization of the generalization error of the subtask problem with this Gibbs algorithm.