Statistical tests for benchmark comparison

Question

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.

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.}

Answer 4

Choosing is loosing.

We should be collecting raw benchmarks results at a grand scale, independent of how we evaluate them. And we should have a free, open, objective website hosting all that data, from different researchers and different vendors.

I'd love to help build out an open datawarehouse of benchmarks, using our benchmark toolkit on top of Continuous Integration (Jenkins? Travis?). Once that's build, determining the best algorithm becomes a query problem for academic researchers. It enables Data Science.

Ironically, we have the means to generate a gold mine of data in optaplanner:

• 22 use cases (including CVRP, VRPTW, NRP, ...)
• thousands of data sets
• dozens of algorithms to apply on those 22 use cases
• Statistical benchmarking (different random seeds), JVM warm up support, ...
• optaplanner-benchmark that spits out an xml file with all benchmark results, csv files with all the telemetry data and a pretty html report

But the main problem is a lack of CPU power (there's little business revenue in buying AWS instances for this) and lack of time to code automating the start/collection of those benchmarks.

Answer 5

A good thing for you to invoke in your case is the Central Limit Theorem. It states, roughly speaking, that you can assume a normal distribution (a special case of the Gaussian Function) provided your sample size is "large enough." Usually "large enough" is taken to mean $n\ge30$.

You can use a Two Sample $t$-test for this. You want to show that Algorithm $1$ ($A_1$) is faster than Algorithm $2$ ($A_2$) WLOG. So you get:

\begin{align}H_0&: \mu_{A_1} - \mu_{A_2} = 0\\H_1&: \mu_{A_1} - \mu_{A_2} > 0\end{align}

I'm assuming you want $95\%$ confidence, since you didn't specify in the question. You can change this if you want, but you should know going in what you want it to be and stick to it.

Your statistic takes the form of:

$$T_0 = \frac{\mu_{A_1} - \mu_{A_2}}{s_p\sqrt{\frac1{n_1}+\frac1{n_2}}}$$

where $s_p$ is the pooled variance (more on that in a moment), $n_1$ is the sample size for algorithm $1$ and $n_2$ is the sample size for algorithm $2$.

$s_p$ operates under the assumption that your population variances for the two algorithms are the same, and is a weighted average of the two sample variances.

$$s_p = \sqrt{\frac{(n_1-1)s_1^2 + (n_2-1)s_2^2}{n_1+n_2 - 2}}$$

There's a whole rabbit hole I would happily travel down about unequal variances and testing for variance equality, but I sense you just want to know if one algorithm is faster than the other, right now.

TL;DR: Take a sample large enough to invoke the Central Limit Theorem and use a Two Sample $t$-Test. You can download the statistical software RStudio (it's free!) and perform the $t$-Test within minutes of booting up and installing required packages. It will spit out a $p$-value, and if your $p$-value is less that $1-\text{confidence level} =1-0.95 = 0.05$ you've made your case, so to speak.

Answer 6

Actually, I asked myself the same question some time ago. But after some time I figured out that the question is just too imprecise.

"Faster" can mean a lot of things. It can mean that the average time is shorter, that you win in the majority of benchmark instances (which is not a good measure in general, especially because it is intransitive), that you find a "significant" (however you define that, e.g. 50% better) advantage in the majority of cases, that the worst case is better etc.

All of these measures (and many more) are sensible for their use cases.

I very much understand the desire to rank algorithms, and it is important in science to distinguish between the fruitful and less fruitful approaches. But first of all you need to come up with a justified definition of "faster" that applies to the circumstances in which the algorithm shall be used.