High dimensional MOO over discrete input spaces

[1bing2]

Hi,everyone：
I am new here and i have a problem recently. I need to limit a high-dimensional design candidate X. the shape of this x is 1 * n. if I need to limit every dimension of this x (the first dimension can only take 1, 2, 3, and the second dimension can only take 4, 5, 6,...), I use the qExpectedHypervolumeImprovement as acquisition function and optimize_acqf to optimize. How to solve such a problem to have a proper constrain ? thank you!

[saitcakmak]

Hi @1bing2. I'd highly recommend using Ax to do this. A tutorial for multi-objective optimization in Ax is here. It will use qExpectedHypervolumeImprovement under the hood and do all the conversion to support your discrete / categorical variables. How to specify the type of your parameters (when using Service API) is explained here.

For a pure BoTorch solution, you'd have to use either optimize_acqf_discrete, to which you have to provide a set of possible solutions -- which it will enumerate, so this may not scale well -- or optimize_acqf_discrete_local_search which will do a greedy nearest neighbor search -- may scale better to large dimensions since it doesn't do full enumeration.

[1bing2]

Thank you a lot! I have handle this problem. But I ran anew one.
Problem: For a Pareto frontier problem that needs to find the minimum
Can i use this is_non_dominated ? But I see the tutorial is to solve a problem of finding the maximum value.

[Balandat]

So as the docstring says here, is_non_dominated assumes maximization of all objectives. If you use minimization you can just flip the signs of the associated outcomes, apply is_non_dominated, and then flip the signs of the returned frontier.

[1bing2]

Thank you a lot.Your reply have impressed me.
For an another problem I want to know the class called qExpectedHypervolumeImprovement.
It has a MCSampler ,how can l understand this MCsampler?
or Can you explain the usage of this or give some information about it?

[Balandat]

Answered here: #1238

[1bing2]

Answered here: #1238

Thank you a lot ! Your answer has helped me a lot! However,I run a new problem recently. The tutorials have a function called optimize_acqf, it can generate a set of candidates via multi-start optimization. I don't understand the multi-start optimization.Can you explain the usage of this or give some information about it?

[Balandat]

Optimizing the acquisition function is generally a very hard numerical optimization problem. It's generally non-convex, and the optimization surface has lots of flat regions and local optima and so we can't hope to find the global optimum via gradient descent type methods from a single initial condition.

"Multi-start" optimization just means that we run a bunch of local optimizations from a number of randomized initial conditions to increase the chance to find the global optimum. See e.g. this paper for some more discussion.

[1bing2]

Thank you very much！But the raw_samples which means The number of samples for initialization.The samples means what? Posterior or just some points draw from the design space

[saitcakmak]

The initial conditions for multi start optimization are selected via a heuristic that samples 'raw_samples' (using Sobol sequences) points from the design space, evaluates the acquisition function at these points, then selects the initial conditions from these 'raw_samples' with probability proportional to a soft -max transform of the corresponding acquisition values.

[1bing2]

Thank you very much for your reply. So the optimization function starts from raw_ Samples -- extract the points from the design space, these points are with probability proportional to a soft -max transform of the corresponding acquisition values.Then start the optimization many times to find the same candidate points or find the points make the acquisition values max. By the way,Is the re parameterization trick of the acquisition function qehvi the same as that of the acquisition function?

[1bing2]

Forgive me for interrupting again，I have an another qusetion come from the paper Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization In this paper it has a part called Sequential Greedy and Joint Batch Optimization But I don't make it clearly,how the Joint Batch Optimization mean? Can you explain it or give me some information about it?

[Balandat]

By the way,Is the re parameterization trick of the acquisition function qehvi the same as that of the acquisition function?

Of which acquisition function? The reparameterization trick is about how to parameterize samples from the model posterior, which is somewhat orthogonal to the acquisition function used. When using a Gaussian Process model (the default in BoTorch) this is indeed the same.

But I don't make it clearly,how the Joint Batch Optimization mean?

Joint optimization means considering the parameters of q new candidates jointly in a single, big optimization problem. Sequential greedy means we optimize for a single candidate, and then condition on that choice. You can find more info and links to other references in Sec 5.2 of https://proceedings.neurips.cc/paper/2020/hash/f5b1b89d98b7286673128a5fb112cb9a-Abstract.html

[1bing2]

Of which acquisition function? The reparameterization trick is about how to parameterize samples from the model posterior, which is somewhat orthogonal to the acquisition function used. When using a Gaussian Process model (the default in BoTorch) this is indeed the same.

Forgive me for interrupting again, I mean the reparameterization trick of the acquisition function qehvi is the same as that of the acquisition function Ei ?
So in the Gaussian Process Model,reparameterization trick and acquisition function are the same?

[saitcakmak]

The reparameterization trick is a way to generate differentiable samples from the Gaussian process posterior, by factoring the posterior distribution into a product of the Cholesky factor of the covariance matrix and the standard multivariate normal distribution (plus a mean term). It is a trick that is independent of the acquisition function. If your acquisition function can be MC estimated as a differentiable function of the posterior samples, then you can use the reparameterization trick to make the acquisition function differentiable. All MCAcquisitionFunctions in BoTorch use this trick. I'd recommend reading the paper for more detail and checking out the reference linked above: https://arxiv.org/abs/1712.00424