Mfcttrf

Suppose that you have two algorithms for solving an optimization model, and you want to benchmark their performance over a large set of instances (with only one performance metric, for example, the running time). I want to show that one algorithm is "faster" than the other by using some statistical test.

My question: Which test is the correct one to use?

More precisely: Most of the paper in OR just compare mean times, which is clearly too weak. On the other extreme, you can use a Sign Test, but it doesn't consider the magnitude of the difference, only if you are faster or not on the different instances. Others (including me) use Performance Profiles, but this graph ignores the one-to-one comparison over each instance (you can be slower in more than half of the instances, and still have a performance curve dominating the other).

My knowledge of statistics is low (for being a mathematician), but if I'm not wrong, you need:

• a nonparametric test (because I cannot assume normality or any other distribution)


• paired (because the time of each algorithm in the same instance are not independent)


• one-sided (because I want to show that one algorithm is better than the other)

Also, does it make a difference if the instances are randomly independently generated or not?

I think there are many different factors to consider. There's a very good paper by Coffin and Saltzman (Statistical Analysis of Computational Tests of Algorithms
and Heuristics, INFORMS JOC 12(1): 24-44, 2000) that discusses this issue in detail.

Options for you: McNemar^NP, $t$ test (with variants)^P, Wilcoxon^NP, sign test^NP, Friedman^NP

Dietterich (1998)

Five statistical tests are compared primarily on the type I error produced. Emphasis mine.

Two widely used statistical tests are shown to have high probability of type I error in certain situations and should never be used: a test for the difference of two proportions and a paired-differences $t$ test based on taking several random train-test splits. A third test, a paired differences $t$ test based on $10$-fold cross-validation, exhibits somewhat elevated probability of type I error.

In your case, this shouldn't matter as a $t$ test assumes normality to a certain extent.

The cross-validated $t$ test is the most powerful. The $5×2$ cv test is shown to be slightly more powerful than McNemar’s test. The choice of the best test is determined by the computational cost of running the learning algorithm. For algorithms that can be executed only once, McNemar’s test is the only test with acceptable type I error. For algorithms that can be executed $10$ times, the $5×2$ cv test is recommended, because it
is slightly more powerful and because it directly measures variation due to the choice of training set.

Note that McNemar's test is non-parametric, similar to goodness-of-fit that uses a $chi^2$-distribution.

Demšar (2006)

This paper is more interesting as it considers some alternative, non-parametric approaches, such as the Wilcoxon signed-rank test.

When the assumptions of the paired $t$-test are met, the Wilcoxon signed-ranks test is less powerful than the paired $t$-test. On the other hand, when the assumptions are violated, the Wilcoxon test can be even more powerful than the $t$-test.

Another non-parametric test is the Friedman test. It is similar to ANOVA, and still uses ranking as part of the expression for the test statistic.

A simpler method is to use the sign test, and the larger the number of data the closer the equivalence of this test to the $z$-test. However, the cost of the simplicity is highlighted below.

This test does not assume any commensurability of scores or differences nor does it assume normal distributions and is thus applicable to any data (as long as the observations, i.e. the data sets, are independent). On the other hand, it is much weaker than the Wilcoxon signed-ranks test.

In conclusion...

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.

_References

_{[1] Dietterich, T. G. (1998). Approximate Statistical Tests for Comparing Supervised
Classification Learning Algorithms. Neural Computation. 10:1895-1923.}

_{[2] Demšar, J. (2006). Statistical Comparisons of Classifiers over Multiple Data Sets. Journal of Machine Learning Research. 7:1-30.}

I know that you explicitly ask for a statistical test, but maybe this is because you don't know about alternatives that are rather established in the community. When comparing algorithms, my number one is performance profiles.

They were introduced in this article: Elizabeth D. Dolan and Jorge J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, 91(2):201–213, 2002.