0
$\begingroup$

Let's say I have an algorithm that can be tuned by a parameter $h>0$ and is expected to converge as $h\to 0$.

I want to study the computational complexity of this algorithm, i.e., how the required runtime increases with increasing accuracy. For this purpose, I run the algorithm for different values of $h$ (say, $h_1>h_2>\dots>h_n>\dots >h_N$) and summarize the accuracy (computed in comparison to a different, established method, with high accuracy) and runtime of these runs in a plot.

The plot shows runtime on the horizontal axis and accuracy on the vertical axis. However, sometimes, the runtimes are non-monotonic as I increase $n$. Should I reorder the runs so as to have a plot where the accuracy is a function of the work?

For example, the plots may look like this if I just connect run $n$ to run $n+1$:

enter image description here

Note that run $n=2$ took more time than run $n=3$ but also ended up being more accurate.

The reordered plot would look as below. Note that the data points have not changed, they are just connected in a different order.

enter image description here

Another example would be that run $n=2$ takes longer but is still less accurate than $n=3$. The unshuffled and shuffled plots then would look like this: enter image description here

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ A line chart is the wrong choice of graphic. The line strongly suggests that it is sensible to read off a value on the y-axis for any value on the x-axis, eg, at a rough estimate the first graphic gives y = 6.1 for x = 2.3. But your question indicates that the values along the x-axis are discrete, ie 1,2,3,4,.... Use a scatterplot. $\endgroup$ – High Performance Mark Mar 7 '18 at 8:44
  • $\begingroup$ The line chart also strongly suggests an inverse relationship between the variables on the two axes, and you are tying yourself in knots trying to maintain that (misleading) illusion with your suggested modifications to the chart. $\endgroup$ – High Performance Mark Mar 7 '18 at 8:46
  • $\begingroup$ Apart from the obvious improvement you need on those plots, why dont you just make a stem plot. Do not connect the points, its not a continuous function. This solves all your problems. $\endgroup$ – Ander Biguri Mar 7 '18 at 9:21
  • $\begingroup$ @Ander yeah, yeah, shame on me.... I also should have made the y axis logarithmic. Most importantly I should have marked the actual values by crosses or something. I see your (and @HighPerformanceMark) point about not connecting the points, but everybody in my field does this (again, after marking the data points). The reason is that the parameter is not actually an integer but a real $h>0$ (as in finite element methods) and so there IS some sense in intepolating. I will update the question $\endgroup$ – Bananach Mar 7 '18 at 12:22
  • $\begingroup$ @Ander by last one you mean the reordered one? $\endgroup$ – Bananach Mar 7 '18 at 12:26
2
$\begingroup$

It sounds like you actually have three pieces of information here -- h, error, and runtime. Plotting accuracy vs runtime isn't that useful if there is no correspondence with h (and so the user of your algorithm can't know how to pick h to get the desired accuracy/runtime).

I'd do scatter plots with color of the glyph to indicate h. In this way your first example would make it clear, even with only glyphs, that something weird is going on here. Reordering the runs hides the fact that some sort of strange cancelation/unexpected behavior CAN happen, so expecting monotonic (convergence, runtime increase) is not to be expected.

| cite | improve this answer | |
$\endgroup$

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.