26
$\begingroup$

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?

$\endgroup$
7
  • 2
    $\begingroup$ I found that the Wilcoxon Signed Rank test satisfies these conditions, but apparently this test evaluate if one algorithm is always faster (for all instances), which can be too strict. $\endgroup$
    – Borelian
    Sep 14, 2019 at 17:25
  • $\begingroup$ But isn't that what you want to show? That one algorithm is better than another. Of course you will get an answer about the statistical significance of the performance differences of the two algorithms. I would go for the Wilcoxon signed rank test. $\endgroup$
    – JakobS
    Sep 14, 2019 at 17:39
  • 1
    $\begingroup$ I think it depends on the definition of being faster. You can also use a Sign Test, which compare instance by instance if you are better or not (ignoring the amplitude of the difference). But you can be slightly slower in half of the instances, and much faster in the others, but you will fail for this test. On the other extreme, you can just compare mean times (as usual in many, many papers). That's my question, which test should be considered a good definition of "being best" in the algorithmic context? I'll add this to the question. Thanks! $\endgroup$
    – Borelian
    Sep 14, 2019 at 19:01
  • $\begingroup$ Would you look for to Design of Experiments or Experimental Methods? Might, this or this link be useful to you. $\endgroup$
    – A.Omidi
    Sep 14, 2019 at 19:38
  • $\begingroup$ Your dislike of performance profiles for comparing two algorithms is flawed. If one is slower in more than half of the instances it will be dominated on the far left of the graph. Please update your question. $\endgroup$ Sep 17, 2019 at 6:42

6 Answers 6

14
$\begingroup$

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.

$\endgroup$
2
  • 5
    $\begingroup$ Unfortunately performance profiles suffer from an analogous problem to nontransitive dice: numerical.rl.ac.uk/people/j_scott/publications/2016/… $\endgroup$
    – TLW
    Sep 15, 2019 at 17:20
  • 1
    $\begingroup$ Yes!, as I mentioned, I'm also a fan of performance profiles. But in this particular case, I need to compare the objective function of the solution of two different stochastic models over a large out-of-sample set of scenarios.. I formulated the question asking about running time because it is more general for the OR community. But beside running time, performance profiles don't make much sense.... $\endgroup$
    – Borelian
    Sep 15, 2019 at 21:04
9
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

Options for you: McNemarNP, $t$ test (with variants)P, WilcoxonNP, sign testNP, FriedmanNP


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.

$\endgroup$
6
$\begingroup$

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:

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.

$\endgroup$
2
  • $\begingroup$ Concerning the CPU and AWS. I am doing an internship. I am trying to solve an NP-hard problem (an extension of the RCPSP). I didn't try any cloud servies before (AWS, Google Cloud, etc.). The company is asking me if I need a computer with "sufficient" CPU. I am going to opt for a cloud service, since they will use this environment later to deploy the application anyway. What do you think? $\endgroup$
    – Antarctica
    May 5, 2020 at 7:35
  • 1
    $\begingroup$ That's a good idea. But invest development time in automation and orchestration of running those solvers on any of those clouds. $\endgroup$ May 5, 2020 at 13:32
6
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Noting that this method requires that we have a way to take independent random samples over the space of problems of interest, and an accepted understanding of how much weight (selection probability) each problem should have. $\endgroup$ Sep 23, 2019 at 0:36
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.