Scikit-optimize: Sobol' and Halton sequences should start with 0

[tupui]

QMC sequences should starts with 0. Both Halton and Sobol' don't start with 0. This is also reflected the the sampling examples.

For Sobol' I've seen that you don't return the plain Sobol' sequence (which is accessible as a hidden method). IMO this is confusing and not really explained in the doc. Still, when asking for the first point of the sequence _sobol(..., 1) it should return [0, ...].

An even more concerning point is that by default you skip an arbitrary number of points in the sequence. This is wrong. Sobol' sequence follows a power of 2 logic. If you forget even 1 point (like the first point 0), the sequence is unbalanced and the convergence rate is deteriorated. And if you decide to skip 128 points for instance, then you can only sample 128 points afterwards the sequence is again unbalanced.

We are currently in the process of merging low discrepancy sequences (and LHS) into scipy (https://github.com/scipy/scipy/pull/10844) and had this discussion with experts on the matter. You could either fix the zero and the skipping here or rely on this new scipy.stats.qmc submodule when it's merged.

Also, I don't get why Sobol' is not the default option (with scrambling) for gp_minimize.

PS. In the doc there is a misspell, it should be Sobol' and not Sobol.

[tupui]

What do you think @holgern?

[betatim]

Thanks for adding to/editing your original post to explain more about what the problem is with not starting at zero.

I think once the scipy changes have been merged and released for a while we could switch to using them. I wouldn't be in a hurry to switch to scipy based sequences because we have the feature already and it would require all users to upgrade to the latest version of scipy.

When you say "it is wrong" do you mean wrong in the sense of 2 + 2 coming out as five. Or is it sub-optimal as in slower convergence. The first would be bad, the second would be not-nice.

Do you want to make a PR to address the points you are concerned about?

A quick PR for the typos would be great as well.

[betatim]

The defaults for gp_minimize were set long before quasi random sequences were added. Instead of going through the steps of deprecating old defaults and switching over to a new value we treat the defaults more like scikit-learn does: they are not-wrong values but users should tweak and tune them for the problem they are tackling.

[tupui]

Do you want to make a PR to address the points you are concerned about?

A quick PR for the typos would be great as well.

Sure I can make a PR. Will be glad to help 😃.

[tupui]

When you say "it is wrong" do you mean wrong in the sense of 2 + 2 coming out as five. Or is it sub-optimal as in slower convergence. The first would be bad, the second would be not-nice.

I did not answer this sorry. It is sub-optimal and will result in worst convergence rate. See this paper from @ArtOwen for reference: https://arxiv.org/abs/2008.08051

[ArtOwen]

I would say that it is `wrong' in the sense of false advertising. Sobol' sequences are constructed to give you a sequence of digital nets. If you skip the initial point, then what you deliver is not a digital net any more. So the users are misled.

Both Sobol' and Halton sequences really need to be scrambled in order to remove artifacts. In the Halton case, those artifacts are similar to the problems with a badly chosen congruential random number generator. It can be an awful striping that is easily broken up by scrambling.

For scrambled Halton it makes a lot less difference whether you start at the 0'th or 1'st point. Halton does not promise a digital net. If the goal is to be consistent, then it makes sense to start both of them at the 0'th because it matters a lot for Sobol'.

-Art

I've been immersed in QMC for a long time, so skipping the first point or using n=100 is to me like scratching a chalk board or putting wood screws in with your hammer.

On 9/28/20 12:04 AM, Pamphile ROY wrote:

When you say "it is wrong" do you mean wrong in the sense of 2 + 2 coming out as five. Or is it sub-optimal as in slower convergence. The first would be bad, the second would be not-nice.

I did not answer this sorry. It is sub-optimal and will result in worst convergence rate. See this paper from @ArtOwenhttps://github.com/ArtOwen for reference: https://arxiv.org/abs/2008.08051

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHubhttps://github.com/scikit-optimize/scikit-optimize/issues/953#issuecomment-699819824, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AD4ZGF6XKUBSSGBVDMV2O7DSIAYPVANCNFSM4RRSLIMA.