A proposal of SobolSampler

[kstoneriv3]

Motivation

The use of quasi-random low-discrepancy sequences in place of random sampling is known to perform better [1]. Sobol sequence is one of such sequences and is reported to perform well in [1].

Description

I implemented SobolSampler for optuna using a package sobol_seq, which is 1) lightweight and 2) distributed under MIT license. My implementation can be checked at my repository.

Benchmark

I compared by my implementation of SobolSampler with existing samplers of Optuna using kurobako. From 100 benchmarks per each sampler and each dataset, SobolSampler was reported (statistically significantly) better than RandomSampler for all datasets.

TODOs (updated)

• Discuss how we should support the Sobol sequence generator in Optuna
• Create PR for SobolSampler (and maybe for Sobol sequence generator)
• Benchmark the CMA-ES combined with the Sobol sequences

References

[1] Random Search for Hyper-Parameter Optimization

[HideakiImamura]

Thanks for the interesting proposal! Implementing the SobolSampler and introducing it to Optuna is important to improve the sampling performance. I'm looking forward to it!

One concern is that the SobolSampler may only be used when the search space is static. Allowing the dynamic search space is one of the most important Optuna features. I think it's important to know how to deal with this issue.

[kstoneriv3]

Thank you for your interest! At the moment, SobolSampler samples from the same search space as the first trial or the one specified by the user (using sample_relative). If a parameter to sample is not included in the above space, it will just use independent sampling. So users need to make sure to specify search spaces which they want to efficiently cover.

Though I am not an expert of the Sobol sequence, I believe that Dynamic search space should be out of the scope for now because the Sobol sequence is designed to fill the unit hypercube uniformly (or with low discrepancy). Use of dynamic search space immediately means that the user is not sampling from a hypercube so the sampler might not be as efficient as one might expect even if we support dynamic search space with some ad-hoc methods. I have heard of researches on low-discrepancy sequences on the various space (e.g. a sphere surface) but they look too complicated.

[github-actions]

This issue has not seen any recent activity.

[kstoneriv3]

Another proposal; using a randomized Sobol sequence in the CMA-ES seems promising. Sobol sequence can be used to sample from a multivariate normal distribution. Any opinion/comment on this?

[nomuramasahir0]

Another proposal; using a randomized Sobol sequence in the CMA-ES seems promising. Sobol sequence can be used to sample from a multivariate normal distribution. Any opinion/comment on this?

This result seems to be promising.
One thing I'm curious about is that the population size in the paper is set to a relatively large value, 20 * dim (the recommended value of the population size of CMA-ES is 4 + floor(3 * log(dim))).
Based on the use case of Optuna where the evaluation budget is usually limited, we might want to investigate the behavior of the Sobol sampler with a small population size.

[kstoneriv3]

I agree that we need benchmark results to see if using sobol with CMA-ES works well in a realistic setting. At the moment, I am optimistic about it because the SobolSampler is performing better than RandomSampler where the budget is larger than 20 in the benchmark I presented above.

[github-actions]

This issue has not seen any recent activity.

[toshihikoyanase]

Thank you for your proposal. SobolSampler seems promising.

I implemented SobolSampler for optuna using a package sobol_seq, which is 1) lightweight and 2) distributed under MIT license. My implementation can be checked at my repository.

I found that your current implementation includes a sobol sequence generator copied from http://people.sc.fsu.edu/~jburkardt/py_src/sobol/sobol.html instead of using sobol_seq package.

IMO, the copied files increase the maintenance cost of the code in terms of both the bug fix and code license. How about providing the SobolSampler as an integration module? If it gets many users, we can re-create it as a built-in sampler. We employed a similar approach when we provide CmaEsSampler.

[github-actions]

This issue has not seen any recent activity.

[HideakiImamura]

@toshihikoyanase Thanks for the proposal. I agree with your opinion, that is, the SobolSampler should be implemented as an integration module. In addition, we can implement the SobolSampler in samplers if we implement the algorithms of the sobol_sq package in the future.

@kstoneriv3 Do you have any concerns? I would be very happy to have your contribution.

[kstoneriv3]

@HideakiImamura @toshihikoyanase Thank you for the comments and sorry for the late reply. I just missed the former comment.

I agree with providing the Sobol sampler as an integration module. Since it might take some time before I implement it, in case you need it soon, please feel free to implement it on your side. I am aiming to implement it by the end of this year.

[kstoneriv3]

I have a question on parallelized optimization. In parallel optimization settings, every Sobol sampler in each process must share the same random seed. What do you believe is the best way to share the random seed of the Sobol sampler? At the moment, I am thinking of using storage.set_study_user_attr(study_id, key, value).

[github-actions]

This issue has not seen any recent activity.

[tupui]

FYI, there will be soon QMC in scipy with Sobol'. scipy/scipy#10844
I would suggest you go with this instead of sobol_seq as the sequence misses the first point (zero). This is a bigger problem as it may sound as you can read in scipy's PR. Also, sobol_seq only support 100 dimensions as opposed to 21201. Appart from scipy, this implementation is expected to be pushed to pytorch (this PR is based on original work in pytorch). But the version in scipy would allow more flexibility as more QMC samplers are available (LHS, Halton).

[kstoneriv3]

That is great news! Using scipy implementation sounds like a more reasonable option. Thank you for letting me know!

[Balandat]

The scipy PR has been ready for a long time, not quite sure what the holdup is to get this merged in. It could be helpful if people who would like to use it were to comment on the issue to give it some sense of urgency...

[github-actions]

This issue has not seen any recent activity.

[rgommers]

The scipy.stats.qmc module is a thing now, PR is merged. It will be in the 1.7.0 release (which is still a while away, probably May) - but it'll be in the nightly wheels soon (https://anaconda.org/scipy-wheels-nightly/), probably tomorrow.

[tupui]

Let me know if you need help. I can take some time to propose a PR.

[kstoneriv3]

That is great news!! I will implement Sobol sampler for Optuna soon using scipy.stats.qmc soon!
(Edit, 23 Feb) I will start working on this in a week...

[github-actions]

This issue has not seen any recent activity.

[github-actions]

This issue was closed automatically because it had not seen any recent activity. If you want to discuss it, you can reopen it freely.

[imbalu007]

I implemented SobolSampler for optuna using a package sobol_seq, which is 1) lightweight and 2) distributed under MIT license. My implementation can be checked at my repository.

@kstoneriv3 , would it be possible to share your repo? I am getting a 'Page not found' for the link to your repository.. In particular I want to see how you benchmarked it using kurobako

[tupui]

@imbalu007 the path changed since now it's using the SciPy version, cf the open PR #2423 still waiting for reviews... Here is the correct path https://github.com/kstoneriv3/optuna/blob/feature/qmc-sampler/optuna/samplers/_qmc.py

[imbalu007]

@kstoneriv3, @tupui, is there a plan to support priors on search space parameters? Ex: {'hyperparam1': uniform(0,1), 'hyperparam2': normal(0,1)}

[kstoneriv3]

@imbalu007 I do not think it is possible in the current framework of optuna as it only supports the following 5 distributions. When you use QMCSampler you can only sample from these distributions.

• Categorical
• Uniform
• log-Uniform
• Integer (discretized uniform dist.)
• log-Integer (discretized log-uniform dist.)

[imbalu007]

@kstoneriv3 , is there any limitation to use SciPy's distributions (https://docs.scipy.org/doc/scipy/reference/stats.html#statistical-functions-scipy-stats) and then call ppf() to calculate inverse CDF with your sobol sample?

[tupui]

@imbalu007 you should ping members of the optuna team with your questions, or open a new issue since this one is closed and might not get traction.

For SciPy, you can use the inverse CDF or use scipy.stats.NumericalInverseHermite. SciPy 1.8 will come with more options from UNURAN.

[kstoneriv3]

@kstoneriv3 , is there any limitation to use SciPy's distributions (https://docs.scipy.org/doc/scipy/reference/stats.html#statistical-functions-scipy-stats) and then call ppf() to calculate inverse CDF with your sobol sample?

In theory, it is possible to do so. However, all of Optuna's samplers do not handle unbounded distributions such as normal distribution at the moment, and supporting such distribution in its existing API will require a significant amount of work. So I would assume that the normal prior of parameters is unlikely to be supported in the very near future.