Has the journal Science endorsed the Garden of Forking Pathes Analyses?

Question

The idea of adaptive data analysis is that you alter your plan for analyzing the data as you learn more about it. In the case of exploratory data analysis (EDA), this is generally a good idea (you are often looking for unforeseen patterns in the data), but for a confirmatory study, this is widely accepted as a very flawed method of analysis (unless all the steps are clearly defined and properly planned out in advanced).

That being said, adaptive data analysis is typically how many researchers actually conduct their analyses, much to the dismay of statisticians. As such, if one could do this in a statistical valid manner, it would revolutionize statistical practice.

The following Science article claims to have found a method for doing such (I apologize for the paywall, but if you are at a university, you likely have access): Dwork et al, 2015, The reusable holdout: Preserving validity in adaptive data analysis.

Personally, I've always been skeptical of statistics articles published in Science, and this one is no different. In fact, after reading through the article twice, including the supplementary material, I cannot understand (at all) why the authors claim that their method prevents over-fitting.

My understanding is that they have a holdout dataset, which they will reuse. They seem to claim by "fuzzing" the output of the confirmatory analysis on the holdout dataset, over-fitting will be prevented (it is worth noting that the fuzzing seems to be just adding noise if the calculated statistic on the training data is sufficiently far from the calculated statistic on the holdout data). As far as I can tell, there is no real reason this should prevent over-fitting.

Am I mistaken on what the authors are proposing? Is there some subtle effect that I'm overlooking? Or has Science endorsed the worst statistical practice to date?

Answer 1

There is a blog posting by the authors that describes this at a high level.

To quote from early in that posting:

In order to reduce the number of variables and simplify our task, we first select some promising looking variables, for example, those that have a positive correlation with the response variable (systolic blood pressure). We then fit a linear regression model on the selected variables. To measure the goodness of our model fit, we crank out a standard F-test from our favorite statistics textbook and report the resulting p-value.

Freedman showed that the reported p-value is highly misleading - even if the data were completely random with no correlation whatsoever between the response variable and the data points, we’d likely observe a significant p-value! The bias stems from the fact that we selected a subset of the variables adaptively based on the data, but we never account for this fact. There is a huge number of possible subsets of variables that we selected from. The mere fact that we chose one test over the other by peeking at the data creates a selection bias that invalidates the assumptions underlying the F-test.

Freedman’s paradox bears an important lesson. Significance levels of standard procedures do not capture the vast number of analyses one can choose to carry out or to omit. For this reason, adaptivity is one of the primary explanations of why research findings are frequently false as was argued by Gelman and Loken who aptly refer to adaptivity as “garden of the forking paths”.

I can't see how their technique addresses this issue at all. So in answer to your question I believe that they don't address the Garden of Forking Paths, and in that sense their technique will lull people into a false sense of security. Not much different from saying "I used cross-validation" lulls many -- who used non-nested CV -- into a false sense of security.

It seems to me that the bulk of the blog posting points to their technique as a better answer to how to keep participants in a Kaggle-style competition from climbing the test set gradient. Which is useful, but doesn't directly address the Forking Paths. It feels like it has the flavor of the Wolfram and Google's New Science where massive amounts of data will take over. That narrative has a mixed record, and I'm always skeptical of automated magic.

Answer 2

The claim that adding noise helps prevent overfitting really does hold water here, since what they are really doing is limiting how the holdout is reused. Their method actually does two things: it limits the number of questions that can be asked of the holdout, and how much of each of the answers reveals about the holdout data.

It might help to understand what the benchmarks are: one on hand, you can just insist that the holdout be used only once. That has clear drawbacks. On the other hand, if you want to be able to use the holdout $k$ times, you could chop it into $k$ disjoint pieces, and use each piece once. The problem with that method is that it loses a lot of power (if you had $n$ data points in your holdout sample to begin with, you are now getting the statistical power of only $n/k$ samples).

The Dwork et al paper gives a method which, even with adversarially posed questions, gives you an effective sample size of about $n/\sqrt{k}$ for each of the $k$ questions you ask. Furthermore, they can do better if the questions are "not too nasty" (in a sense that is a bit hard to pin down, so let's ignore that for now).

The heart of their method is a relationship between algorithmic stability and overfitting, which dates back to the late 1970's (Devroye and Wagner 1978). Roughly, it says

"Let $A$ be an algorithm that takes a data set $X$ as input and outputs the description of a predicate $q=A(X)$. If $A$ is "stable" and $X$ is drawn i.i.d from a population $P$, then the empirical frequency of $q$ in $x$ is about the same as the frequency of $q$ in the population $P$."

Dwork et al. suggest using a notion of stability that controls how the distribution of answers changes as the data set changes (called differential privacy). It has the useful property that if $A(\cdot)$ is differentially private, then so is $f(A(\cdot))$, for any function $f$. In other words, for the stability analysis to go through, the predicate $q$ doesn't have to be the output of $A$ --- any predicate that is derived from $A$'s output will also enjoy the same type of guarantee.

There are now quite a few papers analyzing how different noise addition procedures control overfitting. A relatively readable one is that of Russo and Zou (https://arxiv.org/abs/1511.05219). Some more recent follow-up papers on the initial work of Dwork et al. might also be helpful to look at. (Disclaimer: I have two papers on the topic, the more recent one explaining a connection to adaptive hypothesis testing: https://arxiv.org/abs/1604.03924.)

Hope that all helps.

Answer 3

I'm sure I'm over-simplifying this differential privacy technique here, but the idea makes sense in a high level.

When you get an algorithm to spit out good result (wow, the accuracy on my test set has really improved), you don't want to jump to conclusion right away. You want to accept it only when the improvement is significantly larger than the previous algorithm. That's the reason for adding noise.

EDIT : This blog has good explanation and R codes to demo the effectiveness of the noise adder, http://www.win-vector.com/blog/2015/10/a-simpler-explanation-of-differential-privacy/

Answer 4

I object to your second sentence. The idea that one's complete plan of data analysis should be determined in advance is unjustified, even in a setting where you are trying to confirm a preexisting scientific hypothesis. On the contrary, any decent data analysis will require some attention to the actual data that has been acquired. The researchers who believe otherwise are generally researchers who believe that significance testing is the beginning and the end of data analysis, with little to no role for descriptive statistics, plots, estimation, prediction, model selection, etc. In that setting, the requirement to fix one's analytic plans in advance makes more sense because the conventional ways in which p-values are calculated require that the sample size and the tests to be conducted are decided in advance of seeing any data. This requirement hamstrings the analyst, and hence is one of many good reasons not to use significance tests.

You might object that letting the analyst choose what to do after seeing the data allows overfitting. It does, but a good analyst will show all the analyses they conducted, say explicitly what information in the data was used to make analytic decisions, and use methods such as cross-validation appropriately. For example, it is generally fine to recode variables based on the obtained distribution of values, but choosing for some analysis the 3 predictors out of 100 that have the closest observed association to the dependent variable means the the estimates of association are going to be positively biased, by the principle of regression to the mean. If you want to do variable selection in a predictive context, you need to select variables inside your cross-validation folds, or using only the training data.