3
$\begingroup$

I have a problem with one variable (rounds) that affects the time it takes a program to solve it. For a given number of rounds I generate multiple independent instances and measure the time it takes to solve them.

I then repeat this (with the same instances) with an modified (optimized) version of the solving algorithm. I want to see if the modification leads to faster solving times or not.

I am sure there is proper statistic test for this kind of experiment, however I was unable to find it. Could you point me in the right direction?

Also, to visualize the difference I used two violin plots. The first one shows the distribution of running times for instances of given size side by side (left/yellow is original, right/green is optimized). The second shows the distribution of pairwise differences in time.

enter image description here enter image description here

$\endgroup$
2
  • $\begingroup$ your problem description is confusing. You do not solve a variable. If I said "solve x" it has no meaning. If you had an expression that contained the variable "x" you could "solve for x". I don't know what you are doing that takes the work. The reason that adds confusion is because I can't tell if you are underfitting. For methods (like Newton's) the closer you are to the destination, the faster you go. If you have a consistent initial condition then you can track error vs. iteration by making one "deep run" then repeating and computing the sum of squares of error. $\endgroup$ Mar 26, 2016 at 13:24
  • $\begingroup$ @EngrStudent Sorry I should call rounds a parameter. The bigger it is, the more difficult the instances become and the time get higher. I want to compare the effect of the optimization across all values of the rounds parameter, using multiple instances for each to average out "noise". I'm not sure what you mean by underfitting, can you explain it a more please? Thanks. $\endgroup$
    – lacop
    Mar 28, 2016 at 9:34

1 Answer 1

1
$\begingroup$

I don't know a frequentist test for your problem (a one-sided Wilcoxon signed-rank test or sign test won't work because the differences are not identically distributed). But perhaps your problem could be solved easily using a Bayesian approach. For example:

Let $d_i = 1(x_i < y_i)$, which is 1 if the runtime of the modified optimization, $x_i$, was smaller than the runtime of the unmodified optimization, $y_i$, and 0 otherwise.

Let's say $\pi$ is the (unknown) probability that $x < y$. If our prior beliefs over $\pi$ are uniform, $p(\pi) = 1$, then

\begin{align} p(\pi \mid \mathcal{D}) &\propto p(\mathcal{D} \mid \pi) p(\pi) =\prod_i \pi^{d_i} (1 - \pi)^{1 - d_i} \propto \text{Beta}\left(\pi; 1 + \sum_i d_i, 1 + N - \sum_i d_i \right), \end{align} where $\mathcal{D} = \{d_1, ..., d_N\}$. I.e., our posterior beliefs over $\pi$ are beta distributed. From this we can easily derive the probability that the modified optimization tends to be faster, $P(\pi > .5 \mid \mathcal{D})$.

If instead of using a uniform prior we want to make the reasonable assumption that $\pi$ is more likely to be around .5 then one of the extreme values, we could use a beta prior with parameters $\alpha = \beta$, $\alpha > 1$ and get

$$p(\pi \mid \mathcal{D}) = \text{Beta}\left(\pi; \alpha + \sum_i d_i, \beta + N - \sum_i d_i \right).$$

In Python code:

import numpy as np
import scipy as sp

# prior
alpha = beta = 2

# data
x = np.asarray([1, 4, 5, 7, 10, 11])
y = np.asarray([3, 4, 6, 8,  9, 12])

# statistic
d = np.asarray(x < y, int)
N = d.size
T = np.sum(d)

# posterior probability that x < y
p = 1. - sp.stats.beta.cdf(.5, alpha + T, beta + N - T)
$\endgroup$
1
  • $\begingroup$ Interesting, thank you. I will try this out on some datasets I've collected. $\endgroup$
    – lacop
    Mar 28, 2016 at 9:36

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.