Generalization in Adaptive Data Analysis via Max-Information

In this work we formalize and address the general problem of data reuse in adaptive data analysis. We show how the differential-privacy based approach given in (Dwork et al., 2014) is applicable much more broadly to adaptive data analysis. We then show that a simple approach based on description length can also be used to give guarantees of statistical validity in adaptive settings. Finally, we demonstrate that these incomparable approaches can be unified via the notion of approximate max-information that we introduce.

 

Joint work with C. Dwork, M. Hardt, T. Pitassi, O. Reingold and A. Roth