# Testing contrasts in statistics: Is this provably a hard problem, or not?

Scheffé's method for identifying statistically significant contrasts is widely known. A contrast among the means $\mu_i$, $i=1,\ldots,r$ of $r$ populations is a linear combination $\sum_{i=1}^r c_i \mu_i$ in which $\sum_{i=1}^r c_i=0$, and a scalar multiple of a contrast is essentially the same contrast, so one could say the set of contrasts is a projective space. Scheffé's method tests a null hypothesis that says all contrasts among these $r$ populations is $0$, and given a significance level $\alpha$, rejects the null hypothesis with probability $\alpha$ given that the null hypothesis is true. And if the null hypothesis is rejected, Scheffé points out that his test tells us which contrasts differ significantly from $0$ (I'm not sure the Wikipedia article I linked to points that out).

I would like to know if one can do something similar in a different sort of situation. Consider a simple linear regression model $Y_i = \alpha + \beta x_i + \varepsilon_i$, where $\varepsilon_i\sim\operatorname{i.i.d.}N(0,\sigma^2)$, $i=1,\ldots,n$.

The null hypothesis I want to consider concerns a different sort of contrast. It says there is no subset $A\subseteq\lbrace 1,\ldots,n\rbrace$ such that $E(Y_i) = \alpha_1 + \beta x_i$ for $i\in A$ and $E(Y_i) = \alpha_2 + \beta x_i$ for $i\not\in A$, where $\alpha_1\ne\alpha_2$. If the subset $A$ is specified in advance, then an ordinary two-sample $t$-test does it, but we want something that considers all subsets and holds down the probability of rejecting a true null hypothesis.

One could figure this out if efficiency were not a concern: find a test that goes through all $2^{n-1}-1$ possibilities. Even then it's problematic; two contrasts would not be independent. I asked an expert on outlier detection about this and he just said it's a combinatorial nightmare. Then I asked if one could prove that there's no efficient way to do it, perhaps by reducing an NP-hard problem to it. He just said he stays away from NP-hard problems.

So: Can one prove either that this problem is "hard" or that it's not?

-
Maybe about a year ago at a statistics seminar at the University of Minnesota, the speaker mentioned that a certain problem was NP-hard. For reasons not related to that comment, I thought his topic might bear upon someething I'd wondered about. The more routine but rather laborious exercises in applied statistics courses at a master's degree level include multiple linear regression problems in which one must do "subsetting", i.e. deciding which predictors to discard for lack of evidence that they matter. The problem was how to adjust the sizes of confidence....... – Michael Hardy Jun 5 '13 at 1:04
....intervals to take into account the uncertainties in subsetting. I never heard that question addressed in a course. So I asked the speaker at that seminar about that. His answer was startling: that is a harder problem than the ones he had spoken on. – Michael Hardy Jun 5 '13 at 1:07
+1. Very nice problem. – Joel David Hamkins Jun 5 '13 at 2:03
+1. Do you want some kind of requirement on the power of the test? The facetious test of randomly rejecting a certain fraction irrespective of the data is definitely polynomial time and trivially satisfies the control of false rejections. I don't think my question is just a nit-pick either, because it seems plausible to me that the hardness of the problem could be directly related to what other desiderata you add. – R Hahn Jun 5 '13 at 2:43
I say 'facetious' because when people mention 'random reject' tests it is often to attack hypothesis testing generically. The problem you describe is practically relevant; in clinical trials one will often find that a drug doesn't work on average, but appears to work on, say, white males with brown eyes. If you allow such subgrouping, you must account for multiple-testing issues you induce. Like your, my experience is that people working on this problem acknowledge that it is a 'combinatorial nightmare' but I have yet to see a formal articulation of computational hurdles involved. – R Hahn Jun 5 '13 at 14:47