Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability

We give the first sample complexity characterizations for outcome indistinguishability, a theoretical framework of machine learning recently introduced by Dwork, Kim, Reingold, Rothblum, and Yona (STOC 2021). In outcome indistinguishability, the goal of the learner is to output a predictor that cannot be distinguished from the target predictor by a class D of distinguishers examining the outcomes generated according to the predictors' predictions. In the distribution-specific and realizable setting where the learner is given the data distribution together with a predictor class P containing the target predictor, we show that the sample complexity of outcome indistinguishability is characterized by the metric entropy of P w.r.t. the dual Minkowski norm defined by D, and equivalently by the metric entropy of D w.r.t. the dual Minkowski norm defined by P. This equivalence makes an intriguing connection to the long-standing metric entropy duality conjecture in convex geometry. Our sample complexity characterization implies a variant of metric entropy duality, which we show is nearly tight. In the distribution-free setting, we focus on the case considered by Dwork et al. where P contains all possible predictors, hence the sample complexity only depends on D. In this setting, we show that the sample complexity of outcome indistinguishability is characterized by the fat-shattering dimension of D. We also show a strong sample complexity separation between realizable and agnostic outcome indistinguishability in both the distribution-free and the distribution-specific settings. This is in contrast to distribution-free (resp. distribution-specific) PAC learning where the sample complexity in both the realizable and the agnostic settings can be characterized by the VC dimension (resp. metric entropy).