Conditional Search Space

[zhenlan0426]

I am looking for ways to define Conditional Search Space. For example, a parameter that chooses architecture, and each architecture has its own parameters. The condition can be nested, so the most general case would be a tree-like search space.

Concetually, I can think of ways to define kernel for such space, so the GP should be feasible. But I am not sure how optimization would work in such space.

I find this issue in Ax. It seems that they flatten the search space. I dont think it would be a good idea since the optimizer will no longer know the sturcture of the search space if flattened. The opimizer will be evaluated at part of the space that is meaningless, e.g. parameter of different architecture than the choosen one. And the flattened space will be much bigger, hence harder to optimize.

Any reference to papers/code would be helpful. Cheers!

[Balandat]

There are a few ways to do potentially do this. I haven't really come across a great general solution for this in the context of BO. http://proceedings.mlr.press/v108/ma20a/ma20a.pdf propose tree-structured covariance functions and ways of optimizing those. @dme65 tried this approach in the past, but it's a bit iffy and didn't work all that well on the real-world problems we tried it out on. @saitcakmak has some success with custom kernels for less general problems where the "conditionality" is only a single layer deep.

[saitcakmak]

I can't share any code at this point but the high level idea I've been experimenting with is to construct custom kernels based on the known structure of the search space. I've had decent success with additive kernels, where the kernels for all "active" parameters are evaluated and summed together to obtain the final covariance matrix. I've only tried this with single layer deep search spaces, though you could easily extend the idea to deeper search spaces, with the caveat that you'd need more data to properly train the hyper parameters.

As an additional reference, here's a more recent paper that proposes tree-ensemble kernels: https://arxiv.org/pdf/2207.00879.pdf

[zhenlan0426]

Thank you for your explanation. It’s very helpful.

[zhenlan0426]

I can't share any code at this point but the high level idea I've been experimenting with is to construct custom kernels based on the known structure of the search space. I've had decent success with additive kernels, where the kernels for all "active" parameters are evaluated and summed together to obtain the final covariance matrix. I've only tried this with single layer deep search spaces, though you could easily extend the idea to deeper search spaces, with the caveat that you'd need more data to properly train the hyper parameters.

As an additional reference, here's a more recent paper that proposes tree-ensemble kernels: https://arxiv.org/pdf/2207.00879.pdf

I think tree-like domain poses two challenges 1) appropriate kernal defined on such domain for GP; 2) how to optimize the acqusition function in such domain.

Your answer is on 1), and you still need to define the kernal value between different "active" parameter. e.g., choice para is on NN vs Xgboost, what is the kernal value comparing a parameter in NN vs xgboost. I can see ways to define this. But it feels kind of judgmental.

On 2), I think for one layer deep domain, we could be more brute force, treat each branch of the tree separatly as outer loop. Not sure how to scale to deeper tree, e.g., Neural architecture search

[saitcakmak]

2. how to optimize the acqusition function in such domain.

That's definitely a big part of it. If you define your kernel to take in "flattened" inputs and process them internally (i.e., figure out what is active and only use those values), then you can optimize it in the flattened space. If some or all of your conditioning variables are discrete, then you will want to make sure to optimize things using a mixed discrete optimizer to make sure that you're evaluating the kernel correctly during optimization.

Here's a recent paper from our group that proposes a new optimizer for BO with mixed spaces. We also have a heuristic that alternates between continuous and discrete optimization that I plan to open source soonish.

[zhenlan0426]

Thanks. recent paper is on my list. I plan to read through the paper first and then go through the github code base afterwards. Cheers!