I want to compare performance of two stochastic optimization algorithms: A1 and A2. Performance is defined as the output of a run. The lower the output is, the better is the solution the algorithm found. There are 15 problem instances I'm supposed to solve. However, I cannot run algorithms just once per instance, since they are non deterministic and don't always return the same result.

I think I could compare them as follows:

Run A1 and A2 for N times per instance. Conduct parametric or non parametric independent samples test, depending on normality and variances of the distributions, to test the following hypotheses:

H0: mean(performance of A1) = mean(performance of A2)

H1: mean(performance of A1) =/= mean(performance of A2)

After repeating this procedure for each instance, I would report for which I have found significant difference between A1 and A2 and end there.

However, I'm concerned with whether this approach is suitable. In the literature, statistical tests are rarely used. My questions are as follows:

  1. Could I consider the outputs for A1 and A2 to be independent samples? I cannot come up with any criterion for pairing, so I guess the samples are independent, no matter that the algorithms are run on same instances.
  2. If this is not a good approach, which statistical test should I use? I'm rather new to statistics, so any help will be very appreciated. :)

Thanks in advance. :)


I cautiously answer "yes." Without any knowledge of your algorithms, I would advise you to conduct a non-parametric test in order to not rely on erroneous assumptions. I will further caution you that your inferences will be limited to what you are testing. If you are testing that the means are different, then that is what you are able to potentially conclude from the test. If you can show in an airtight way that one mean being less than the other implies that one algorithm performs more efficiently than the other, then you can make the jump to algorithm efficiency. However, if you're relying on logical jumps and leaps to get to algorithmic efficiency, then it is inadvisable to conclude anything about the efficiency. Only make conclusions based on what you can justify from your tests, given that any assumptions you make when testing are satisfied.

  • $\begingroup$ Thank you for your answer and suggestion for non-parametric tests. What approach would you suggest to compare efficiency in a correct manner? I could formulate Ho as Outputs of A1 follow the same distribution as the outputs of A2 and Ha as Outputs of A2 tend to have greater values than A2. Would Mann-Whitney U test be appropriate? $\endgroup$ – Milos Jan 8 '16 at 21:44
  • $\begingroup$ The Mann-Whitney U test does test whether two distributions are equivalent, but I believe it focuses on ranking observations and looking at the differences in medians. I would personally use a Kolmogorov-Smirnov test as I believe this to be a better quantifier of the true difference between two distributions. $\endgroup$ – Matt Brems Jan 8 '16 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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