29
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Those without Science access might want to consult this recent Science news article about how one can access paywalled papers. $\endgroup$ – amoeba says Reinstate Monica Jul 11 '16 at 14:39
  • 1
    $\begingroup$ Is this possibly a preprint: arxiv.org/pdf/1411.2664.pdf ? $\endgroup$ – Tim Jul 11 '16 at 14:40
  • 1
    $\begingroup$ @Tim: the Science article cites the preprint you posted. Also, the Laplacian Noise Addition section seems very similar, but not identical, to the methods in the published article. $\endgroup$ – Cliff AB Jul 11 '16 at 14:54
  • 1
    $\begingroup$ @CliffAB so they possibly used differential privacy to make them different ;) $\endgroup$ – Tim Jul 11 '16 at 14:57
  • 4
    $\begingroup$ This topic is actually a tutorial at ICML last month. "Rigorous Data Dredging: Theory and Tools for Adaptive Data Analysis" by some fellow at google. icml.cc/2016/?page_id=97 $\endgroup$ – horaceT Jul 11 '16 at 22:37
7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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/

$\endgroup$
  • $\begingroup$ But that's not an improvement over saying "I will only accept estimated effects $> \tau$"...which will not prevent over fitting (although it will slightly dampen it). Interestingly, in their own plots, you can see evidence of over fitting (systematically lower reported error on holdout data than on fresh data). $\endgroup$ – Cliff AB Jul 12 '16 at 0:05
  • 1
    $\begingroup$ @CliffAB I have the same nagging feeling why this works better than just a simple threshold. But they have proofs! $\endgroup$ – horaceT Jul 12 '16 at 0:13
  • $\begingroup$ ...except that their own example is inconsistent with their claim of preventing over fitting, and is consistent with what I would expect the results to be from "I will only accept estimated effects $> \tau$". $\endgroup$ – Cliff AB Jul 12 '16 at 0:43
  • $\begingroup$ @CliffAB Can you elaborate? where? That'a an intriguing possibility.... $\endgroup$ – horaceT Jul 12 '16 at 2:06
  • $\begingroup$ Using the slides from your earlier link (icml.cc/2016/?page_id=97), on slides 72 and 73, even when using the "Thresholdout" method, the holdout accuracy is greater than the fresh data at every single simulation, although it does do better than "standard holdout" (which is really "standard abuse of the validation dataset", not an actual valid statistical procedure). FYI, the plot appears on the slides to be the same one in the Science paper (just in case you don't have access). $\endgroup$ – Cliff AB Jul 12 '16 at 3:11
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I believe a lot of what you are suggesting fits into the realm of exploratory data analysis (EDA), for which I did endorse adaptive data analysis methods. I also think EDA is underrated and should be given more credit. But all this is orthogonal to the question at hand, which is "Have these authors really allowed us to repeatedly reuse the validation data for model selection in a statistical valid method?" Your last sentence suggests that you, like myself, are somewhat skeptical of such findings. $\endgroup$ – Cliff AB Jul 12 '16 at 2:49
  • $\begingroup$ I don't think e.g. estimation is inherently exploratory, no. If you have a scientific hypothesis that says that the maximum length of a crocodile must be 12 feet and you try to estimate the maximum length of a crocodile to check this, you're doing a confirmatory analysis. $\endgroup$ – Kodiologist Jul 12 '16 at 4:24
  • 2
    $\begingroup$ +1, despite three existing downvotes. I do agree with the main point of this answer (your 2nd sentence), even though I am fully aware that it is quite controversial. In general I think the difference between the exploratory and the confirmatory analysis is overrated; real-life analysis is often somewhere in between. That said, I don't think you answered (or even attempted to answer) OP's question which was about Dwork et al. paper. $\endgroup$ – amoeba says Reinstate Monica Sep 18 '16 at 22:39
  • $\begingroup$ @amoeba "I don't think you answered (or even attempted to answer) OP's question which was about Dwork et al. paper" — True, although this still seemed worth posting as an answer because it casts doubt on what seems to be a premise of the question. $\endgroup$ – Kodiologist Sep 18 '16 at 23:04
  • 2
    $\begingroup$ +1 to @amoeba's comment. This would have been a great comment to the question, but it's not an answer. $\endgroup$ – S. Kolassa - Reinstate Monica Sep 20 '16 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.