Local minima and number of tries in metaMDS

[jarioksa]

Peter Minchin turned my attention to the danger of falling to a local minimum in metaMDS iterations. We stop with convergence as soon as we find two minimum stress solutions. Sometimes this stops too soon, and ends up in a local minimum. Compare these two runs with dune data:

set.seed(1); metaMDS(dune)
set.seed(3); metaMDS(dune)

The first (and several other starts) will first find the local minimum of run 0 (stress 0.1192678) and stop, but the second example will find a better minimum of stress 0.1183186. I think most of these cases can be avoided if we require a minimum number of tries before checking for convergence.

I have implemented this in branch https://github.com/vegandevs/vegan/tree/metaMDS-try. I wanted to maintain backward compatibility and therefore I kept the old trymax argument and added a new argument try that gives the minimum number of tries before signalling convergence. The first version keeps the old limit trymax = 20 and set minimum to try = 6. I think both of these limits are too low and should be increased, but I don't know how much. They come from a time when computers were slower and we used isoMDS which also is much slower than current monoMDS.

[jarioksa]

I ended up setting both try=20 and trymax=20, and internally metaMDS will set trymax = max(try, trymax). This keeps more or less the old interface and defaults, except that default is now to always run 20 random starts and select the best of these. The change is in d126db3.

I tested this with settings try=20, trymax=1000: this would use the current (new) number of try, but continue till convergence. In most cases this ended up in the same and probably global optimum. This means that 20 runs is usually sufficient to get out of the local optimum. Not always, though. This can be only solved by using higher try and depends on the data set. However, I leave this decision to users. I tested this with vegan data sets dune, mite (also with k=3) and BCI and with labdsv data set bryceveg. FWIW, from 10000 random starts in monoMDS I estimated that probability of finding the local optimum with dune was 0.37, and the probability for the local optimum of Run 0 was 0.39. So it is more probable to land on local than in global optimum with the old heuristics, but global optimum was always found with the new strategy.