Evaluating randomized algorithms on randomized problem instances

Question

Suppose we want to compare the performances of two algorithms — call them A and B — on a problem X. In particular, suppose that we want to evaluate the algorithms on random instances of X drawn from some distribution D. For simplicity assume that Algorithm A is deterministic and that Algorithm B is randomized. Assume that in each run of Algorithm B a random variable Y is selected from a distribution Q.

The goal is to determine whether algorithm A or B performs better. Specifically, we would like to create a 95% confidence interval that separates their performance.

The obvious approach would be to repeatedly do the following: for i = 1,..,T, sample y from Y according to Q and x from X according to D. Then run both algorithm A and algorithm B (using Y = y) on problem instance x. We can then compute the mean and standard error of the performances over these T samples to determine the average performances of the algorithms.

Now, suppose that it is costly to sample y from Q and that it would take too long to run enough experiments to obtain statistical significance. We could obtain a significant reduction in running time if we test multiple problem instances for each y sample. For example, we could run B using Y = y1 for x1,…,x100, then Y = y2 for x101…x200, etc. In this case the samples for running B on X would not be iid, and we could not conclude the standard error from the sample. However, the samples would still be unbiased and we could potentially obtain a much larger sample size for these experiments than if we need to sample a new y each time.

It doesn’t seem clear to me at all what the appropriate experimental design should be in this case. If we want to sample a new value for Y for each problem instance, the experiments may take too long for us to obtain a meaningful sample size. If we repeat values of y for some number of problem instances then we can obtain a much larger sample size, but at the expense of knowing the variance.

Is there any way to estimate the variance of the second approach despite not having iid samples? And if so, is there a way to determine the optimal number of samples of X to test for each sample of Y?

Thank you.

Answer 1

This is very like classical problems in experimental design. In the classical version you'd assume that the variance of completion times for fixed $y$ was constant, say $\sigma^2$, and the variance for random $Y$ was $\sigma^2+\tau^2$.

If you do $M$ cases for each of $N$ values of $Y$, the variance of the mean is $\sigma^2/MN+\tau^2/N$. If it costs $B$ times as much to generate a $Y$ as to do a test, the cost is proportional to $N(M+B)$. As long as you have some idea about $\sigma^2/\tau^2$ and $B$, you can optimise. If $\sigma^2/\tau^2$ is small, you don't gain much by doing many cases per $Y$, but if it's large you do. Note that this is the variance; it could be that the mean time to generate a $Y$ is very large, but that the variance of that time is small.

The mean is still estimated by the average. You can estimate $\sigma^2$ by the average of the $N$ variances for fixed $y$. The variance of the $N$ means for fixed $Y$ is $\sigma^2/M+\tau^2$, so you can estimate $\tau^2$, and you can then estimate the variance of the mean.

This approach will still work if $\sigma^2$ varies importantly with $y$, but something more complicated might be better.