Class-wise Generalization Error: an Information-Theoretic Analysis
Firas Laakom Yuheng Bu Moncef Gabbouj
Existing generalization theories of supervised learning typically take a
holistic approach and provide bounds for the expected generalization over the
whole data distribution, which implicitly assumes that the model generalizes
similarly for all the classes. In practice, however, there are significant
variations in generalization performance among different classes, which cannot
be captured by the existing generalization bounds. In this work, we tackle this
problem by theoretically studying the class-generalization error, which
quantifies the generalization performance of each individual class. We derive a
novel information-theoretic bound for class-generalization error using the KL
divergence, and we further obtain several tighter bounds using the conditional
mutual information (CMI), which are significantly easier to estimate in
practice. We empirically validate our proposed bounds in different neural
networks and show that they accurately capture the complex class-generalization
error behavior. Moreover, we show that the theoretical tools developed in this
paper can be applied in several applications beyond this context.