A Data Processing Inequality Framework for Generalization Bounds

We propose a change-of-measure framework based on the data-processing inequality (DPI) for deriving novel high-probability generalization bounds for general learning algorithms. Compared to classical bounds based on Rademacher complexity or covering numbers, which often require sophisticated task-specific bounding techniques, our bounds are easy to evaluate and effective. Furthermore, our framework allows one to produce a family of generalization bounds by adopting different DPI-based change of measure inequalities and different assumptions on the loss function. We evaluate our bounds for examples of Gaussian mean estimation, linear regression, and multiclass classification with deep neural networks. Compared to state-of-the-art bounds from prior literature, our bounds provide significantly tighter guarantees at practically relevant sizes of the training dataset.