In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors

Understand

We propose to study the generalization error of a learned predictor $\hat h$ in terms of that of a surrogate (potentially randomized) predictor that is coupled to $\hat h$ and designed to trade empirical risk for control of generalization error.

• In the case where $\hat h$ interpolates the data, it is interesting to consider theoretical surrogate classifiers that are partially derandomized or rerandomized, e.g., fit to the training data but with modified label noise.
• We also show that replacing $\hat h$ by its conditional distribution with respect to an arbitrary $\sigma$-field is a convenient way to derandomize.
• We study two examples, inspired by the work of Nagarajan and Kolter (2019) and Bartlett et al.