Statistical test to compare method performance over multiple problems I am comparing several methods of ordering training patterns for on-line neural network training. Let's call those methods I-VII.
Then, I have a sample of 20 data sets within a given "data set type" - for instance, with patterns distributed uniformly, let's call that "Uniform Set Type". In other words, I will have 20 randomly generated instances of this type of data set.
Now, for each ordering method I-VII I let it run 50 times on each instance of a data set type. This would give 20 instances x 50 repetitions = 1000 runs total per each method I-VII, forming the whole body of knowledge about performance over "Uniform Set Type" of the methods under test.
The measure of performance I use is MSE. In addition, I also compute another measure for each data set instance like this:


*

*See what was the single lowest MSE achieved on this data set instance by any method I-VII, during any of the 50 repetitions

*Divide the MSEs by the lowest MSE. This gives me values starting at 1.0, corresponding to the lowest error. Let's call this new measure "Relative error".


With this data, I see two ways to compare the methods:


*

*Calculate mean and SD of MSE over all data set instances, all
repetitions for each method (sample size 20 x 50 = 1000), then use a
statistical test to compute p-values concerning whether the mean MSE
between any two methods is different

*Calculate mean and SD of MSE for each data set instance (20 means and SDs, each based on a sample size of 50, since 50 repetitions are
performed per data set instance), and then use a statistical test
that would tell whether there is a significant difference between
methods based on comparison of respective results over each data set
instance.


The problem with approach (1) is that if a method achieved a big bad error on one of the data set instances, this will significantly affect the single mean used for the test, assuming I use pure MSE and not the "Relative error". This is because the MSEs over data set instances might lie anywhere between 0.0001 and 2.0. I can give an example how this would be a problem if asked; omitting it now for brevity.
To solve this problem, I could use the "Relative error". Or I could simply take approach (2) - this time, it seems, there would be no such problem with either pure MSE or "Relative error" - since I am comparing the results instance by instance, which intuitively feels like the better approach to me.
My questions, ranked most important to least, are these:


*

*Which approach, (1) or (2) is better suited to compare the methods?

*Which statistical tests should I use for approaches (1) and (2)?

*Is there any other approach you would recommend in this scenario?

*Any opinion regarding whether MSE or "Relative error" might be the more valuable measure under any of the approaches?

 A: On behalf of the initiative by @PawelP, I a writing a summary of the paper by Demšar, which covers $N \times M$ comparisons and is applicable to the original question.

Firstly, let me explain what $N \times M$ comparisons actually are. Imagine having $N$ subjects (e.g. datasets), which one wants to asses using $M$ methods (e.g. machine learning algorithms). This is usually done by assessing every subject with every method, yielding a data table with $N$ rows and $M$ columns.
Each individual column therefore represents some performance measurement (e.g. error rate, precision, recall etc.) across all subjects. In analogy, each individual row represents a subject, assessed by multiple methods.
Since each subject is assessed under the same conditions, this means that the data table is actually a vector of dependent variables. Therefore, usage of statistical tests for dependent variables is the way to go.

Now that we understand what kind of data we are dealing with, we can continue with analysing our data using various statistical tests.
In the aforementioned paper, the authors have compared various parametric and non-parametric tests, such as paired t-test, ANOVA, Wilcoxon signed-rank test, Sign test, and Friedman's test.
The $N \times M$ test set-up consists of two phases:


*

*Testing across all subjects and all methods using either ANOVA or Friedman's test.

*Whether the previous test yields significant results, one can continue to pairwise comparisons between all pairs of methods, yielding a $M(M-1)/2$ comparisons. The pairwise comparisons can be done by either paired t-test, Wilcoxon signed-rank test or the Sign test.


One can notice that multiple comparisons in step #2 are prone to the familywise error rate (FWER). Therefore a Type I correction method needs to be used. The authors of the aforementioned papers have also tested various methods, such as: Dunnet, Holm, Bonferroni, Hochberg, and Hommel.

To sum up, the authors' conclusions were the following:


*

*Use non-parametric tests. Namely Friedman test for overall comparison and Wilcoxon signed-rank test for pairwise comparisons (or Sign test if Wilcoxon signed-rank test is not applicable).



Overall, the non-parametric tests, namely the Wilcoxon and Friedman
  test are suitable for our problems. They are appropriate since they
  assume some, but limited commensurability. They are safer than
  parametric tests since they do not assume normal distributions or
  homogeneity of variance. As such, they can be applied to
  classification accuracies, error ratios or any other measure for
  evaluation of classifiers, including even model sizes and computation
  times. Empirical results suggest that they are also stronger than the
  other tests studied. The latter is particularly true when comparing a
  pair of classifiers.



*

*Use Holm-Bonferroni FWER method



The corresponding non-parametric post-hoc tests give similar results,
  so it is upon the researcher to decide whether the slightly more
  powerful Hommel test is worth the complexity of its calculation as
  compared to the much simpler Holm test.


For further reading, if one needs more statistical power, he/she may look into the follow-up paper by Garcia & Herrera, which explains more powerful methods for rejecting hypotheses based on $p$-values obtained by pairwise tests.

TL;DR
First test all subjects across all methods using the Friedman test. Then proceed with pairwise tests using Wilcoxon signed-rank test along with the Holm-Bonferroni FWER method.
