1
$\begingroup$

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. :)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jan 8, 2016 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
    Commented Jan 8, 2016 at 22:00

Your Answer

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

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