Permutation test: when the null hypothesis is **non**-equivalence of two models/predictors Suppose I have two models $M_1$ and $M_2$ and I want to compare their performances in terms of measure (accuracy on classification instances, i.e. number of correct predictions to size of all instances).  I conjecture that the difference in their results is not significant. So


*

*Null H: $M_1$ and $M_2$ are different (in terms of accuracy measure).  

*Alternative H: $M_1$ and $M_2$ are not different (in terms of accuracy measure).  


First: 
Is this hypothesis testable? Is it is well-defined? 
I have seen the reverse scenario in different places. For example, the paired-permutation test in [1] is designed for a different hypothesis (where null is not-difference of the two predictors).
At the link they're comparing generalization accuracies (the response) for two models. The test statistic is the mean difference in generalization accuracy. Under the null that the models have equal mean accuracy (and the additional assumption that they have the same distribution under the null), the model labels that go with the pairs of accuracies are arbitrary -- you could interchange them (flipping the sign of the difference in accuracy) without altering the distribution of differences. 
If in the original algorithm in [1] I change the condition from 
$$
|\mu_{new}| \geq |\mu_{old}|
$$
to 
$$
|\mu_{old}| \leq |\mu_{new}|
$$
Second: 
Is it a valid algorithm for my defined hypothesis testing? 
Third: 
If not, any suggestion on how to test this hypothesis? 
[1]  http://axon.cs.byu.edu/Dan/478/assignments/permutation_test.php
 A: Hypotheses should usually be phrased as a statement about population quantities (though in some cases, possibly infinite-dimensional), and that statement should generally be a null statement (typically about lack of difference); in particular, it needs to be a statement under which a null distribution of a test statistic can be computed (or at least an edge-case null can).
In the case of a permutation test, you need that the permutations are equally likely; the null needs to make the labels (or whatever it is that's being 'swapped around') at least exchangeable. Yours does not.
Assuming I've correctly guessed at the meaning of some of the symbols, the two expressions of null hypotheses in the first few lines of your link are suitable null hypotheses (though I'd probably phrase them slightly differently, they're clear enough and should be fine).
You say:

The pair-permutation test in [1] is designed for a different hypothesis (where null is non-significance of the two predictors). 

This is how null hypotheses have to work; if you make "difference" the null (an "open" compound hypothesis), the difficulty is in finding the distribution of the test statistic under the null; the limiting case would actually be in the alternative. In the case of a permutation test, this means that the permutation could only be done under the alternative you give... so that, perforce, must be the null hypothesis. 
It might be that your needs might be better served by some form of equivalence test, but this may be tricky in a permutation test context.
[Note that you can, however, flip the direction of a one-sided test if you need to (between $\leq$ and $\geq$), as long as it definitely includes the equality (the edge-case under which you can compute the distribution of the null).]
