Challenges in Bayesian Adaptive Data Analysis

Sam Elder

Published 2016-04-08Version 1

Traditional statistical analysis requires that the analysis process and data are independent. By contrast, the new field of adaptive data analysis hopes to understand and provide algorithms and accuracy guarantees for research as it is commonly performed in practice, as an iterative process of proposing hypotheses and interacting with the data set. Previous work has established a model with a rather strong lower bound on sample complexity in terms of the number of queries, $n\sim\sqrt q$, arguing that adaptive data analysis is much harder than static data analysis, where $n\sim\log q$ is possible. Instead, we argue that those strong lower bounds point to a shortcoming in the model, an informational asymmetry with no basis in applications. In its place, we propose a new Bayesian version of the problem without this unnecessary asymmetry. The previous lower bounds are no longer valid, which offers the possibility for stronger results. However, we show that a large family of methods, including all previously proposed algorithms, cannot achieve the static dependence of $n\sim\log q$ even in this regime, establishing polylogarithmic lower bounds with a new family of lower bounds. These preliminary results suggest that adaptive data analysis is harder than static data analysis even without this information asymmetry, but still leave wide open the possibility that new algorithms can be developed to work with fewer samples than the previous best known algorithms.