Global optimizer idea: using low-discrepancy quasi-random sampler

[aldanor]

I was playing around the optimizer a bit and noticed one thing: looking at how it picks new points to test, it's now done completely at random:

https://github.com/davisking/dlib/blob/e558318c9a23c4897191c8089e34570dbe3d84ad/dlib/global_optimization/global_function_search.cpp#L801

However, in higher dimensions, it's fairly well known that the uniform distribution is inferior to low-discrepancy sequences for optimization/search purposes since the latter provide more "uniform"/equidistant coverage; the simplest example would the Sobol sequence (more generally, see here).

This is a perfect application since the bounding region is basically an n-dimensional box (in the space where log-scale dimensions are log-transformed first), so you can just generate a Sobol sequence taking values within (0; 1) in all dimensions and then shift/scale/transform it to get to the original space.

I'm not very familiar with dlib, but could probably try contributing if noone else would and if anyone would find it useful.

// Not sure how many people are interested in it, but having a fast n-d Sobol sequence generator might be a nice addition to the library that aims to be versatile :)

[davisking]

Yeah, that's definitely something worth adding to dlib. You should submit a PR for it :)

[aldanor]

Great! I’ll give it a shot. Any quick hints on where this sort of stuff should go in the library or any other useful dev tips so as to save me from having to read the entire codebase first? :)

[davisking]

Sweet. You can add a new file in the same folder as the other global optimization code. I don't know if there are any tools in dlib that are especially relevant for implementing the function you are talking about, so there isn't much to be aware of I think. Other than generally following the coding guidelines (http://dlib.net/howto_contribute.html) that is.

[vhartman]

Hey! I just stumbled upon this issue/feature request. I saw that there is a sobol-sequence generator (and quite a few quasi random generators) in the boost library (https://www.boost.org/doc/libs/develop/doc/html/boost_random/reference.html#boost_random.reference.concepts.quasi_random_number_generator - added just after the request here).

I assume it does not really make sense to add the generators themselves here, but rather provide wrappers that can be used directly in the optimizer, right? I am not entirely sure how the rand-things are used throughout the codebase, so I would try to not change anything there, but do you think the QRNGs might be useful in other places than here?

If not, I would likely just add a flag to the make_random_vector function to decide which method to use for the generation of the random vector.

[davisking]

Please don't add a dependency on boost. But if you want to add such a sequence generator to dlib, but without adding a boost dependency, that would be cool.

[vhartman]

Oh, I see.

I'll check if there actually is a performance gain by adding it (by testing it with the boost implementation) and will report back here. (However I assume that I am not able to implement a better version than the one that is present in boost).

[vhartman]

Brief update: I had an initial go at it, and it seems like the implementation is not worth it, at least not in the naive way, of simply replacing the random generator.

I am not entirely sure where the problem is located, but it seems to perform worse than the random sampling, which is counter intuitive for me, and might indicate an error somewhere. I will clean up the code I used for testing a bit, and share it here - the testfunctions could be of interest, if performance of the optimizer should be looked at close in the future.

[davisking]

Do you use a different random sequence each time the random search happens? If it's the same sequence it will definitely be worse (a lot worse) than the current code.

[vhartman]

Tried both, using a new sequence each time actually worked better than generating samples from the same one.