Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective

The recent surge in contrastive learning has intensified the interest in understanding the generalization of non-pointwise learning paradigms. While information-theoretic analysis achieves remarkable success in characterizing the generalization behavior of learning algorithms, its applicability is largely confined to pointwise learning, with extensions to the simplest pairwise settings remaining unexplored due to the challenges of noni.i.d losses and dimensionality explosion. In this paper, we develop the first series of informationtheoretic bounds extending beyond pointwise scenarios, encompassing pointwise, pairwise, triplet, quadruplet, and higher-order scenarios, all within a unified framework. Specifically, our hypothesisbased bounds elucidate the generalization behavior of iterative and noisy learning algorithms via gradient covariance analysis, and our predictionbased bounds accurately estimate the generalization gap with computationally tractable lowdimensional information metrics. Comprehensive numerical studies then demonstrate the effectiveness of our bounds in capturing the generalization dynamics across diverse learning scenarios.