Constraint Handling in MC Acquisition Functions

[polivucci]

Hi all,

First off, thanks to the developers for the fantastic work on BOTorch.

I would like to make sense of constraint handling for MC Acquisition Functions (AFs).
As far as I know, BOTorch implements 3 ways of handling constraints:

1. Through the feasibility-weighted objective ConstrainedMCObjective(). Here , the AF is evaluated on a objective which has been already weighted with a feasibility indicator $FI$ as: $\alpha(g(x)FI(x))$
2. Through the SampleReducingMCAcquisitionFunction() AF class. Here feasibility weighting is introduced after evaluating the AF: $\alpha(g(x))FI(x)$ This seems similar to the analytic Constrained Expected Improvement.
3. Via ConstrainedMaxPosteriorSampling. This is a constrained version of Thompson Sampling from the SCBO paper.

My understanding is that the applicability of the above goes as follows:

1. is applicable to all MC acquisition functions of the MCAcquisitionFunction() class , to which we can pass ConstrainedMCObjective() through the objective argument. This includes most MC AFs with the exception of Entropy Search acquisitions which define their own AF base class.
2. is ofc applicable to all MC acquisition functions of the SampleReducingMCAcquisitionFunction() class, which as of now only include the EI and logEI family.
3. is only specific to Thompson Sampling. However, I believe passing an instance of ConstrainedMCObjective() to MaxPosteriorSampling would also work out as it admits an objective argument.

Therefore it seems to me that ConstrainedMCObjective() is the only method common to almost all MC AFs.
Exception is Entropy Search AFs for which constraining is atm not yet supported (unless perhaps one can make it work via posterior transform?).

Is my understading correct?
It looks to me that approaches 1. and 2. are not equivalent, so I would like to ask if and how they differ in practice and if you recommend one over the other, based on your experience. Intuitively I would lean towards 2. wherever possible.
Likewise for TS, SCBO handling vs the constrained objective.

Many thanks for your help!

[sdaulton]

Hi @polivucci, That's right.

2. is the preferred approach since it applies constraints on a sample level to the sample-level utility (improvement) for each individual candidate in the batch. 2 is a smooth relaxation of that approach in Letham et al, 2019. This is also the approach used in multi-objective acquisition functions.

3. is a different approach, where as you mentioned, the feasibility indicator is applied to samples of $f$ rather than to the sample-level utility. This is not an equivalent approach and can lead to more harshly penalize points that are not likely to be feasible.

@SebastianAment has done a deep dive on this and may have more thoughts.

[SebastianAment]

Hi @polivucci,

I second @sdaulton's comment that 2. is the preferred approach. Adding a few more technical details:

• Option 1. is likely to give rise to numerical problems. First, the objective function needs to be shifted to be positive before applying the feasibility indicator: $(g(x) - \min_z g(z)) FI(x) + \min_z g(z)$. This is done automatically using get_infeasible_cost. The main issue arises since the weighted objective values can be close to zero in a large portion of the space, depending how difficult it is to satisfy the constraints, leading to numerically vanishing gradients that can leave the acquisition function optimizer stuck in clearly infeasible regions.
• Option 2. mitigates the vanishing gradient problem by transforming the improvement computations to a smoothed log space, and adding the log constraint indicator function (botorch.utils.sigmoid), rather than multiplying with a potentially numerically vanishing number, i.e. $\log \min(g(x) - g^*) + \log(FI(x))$.

We saw particularly significant performance improvements using the smoothed log-transformed computations of LogEI for constrained problems, see Figure 4 of Unexpected Improvements to Expected Improvement for Bayesian Optimization.

Let me know if you have additional questions about the approach.

[polivucci]

Hi @SebastianAment, @sdaulton,

Many thanks for your kind replies!

I have a couple follow-up questions:

• My understanding is that using 2. is advatageous both in principle (as mentioned by @sdaulton) and numerically (due to log treatment @SebastianAment). Is this a correct view?

• I insisted on ConstrainedMCObjective() as it is to the best of my knowledge the only way to constrain single-objective AFs outside the EI family. I think many people (including myself) would like to test several AFs on their problem while maintaining a consistent constraint treatment. Do you see approach 2. being extended to KG, ES and TS in the future?

• I noticed that one can pass a series of exact input constraints to optimize_acqf(). I admittedly did not yet dig deep into the details, apologies if my questions sounds too vague. At the moment the way I prescribe exact nonlinear constraints on the inputs is by using a GenericDeterministicModel() as an outcome constraint model. What is your recommended treatment of nonlinear input constraints?

Thank you

[sdaulton]

Is this a correct view?

yes

Do you see approach 2. being extended to KG, ES and TS in the future?

KG doesn't support constraints (no published work on it). Constrained ES methods are more custom then just feasibility weighting the objective (any do not rely on MC sampling in the same way as an improvement-based AF). TS can easily be constrained by simply drawing a sample of the objective and constraint and computing the exact feasibility weighted objective under the sample (no smooth relaxation needed).

What is your recommended treatment of nonlinear input constraints?

What you described would be my recommendation.

[polivucci]

Hi @sdaulton,

Thanks for your advice.

Regarding constrained KG:

• qKnowledgeGradient can run on ConstrainedMCObjective. Is there a reason for why doing so is not recommended in principle? Aside from potential AF vanishing gradients. For example, in the case of EI, Letham et al, 2019 say their formulation is superior to another when observation noise is present.
• what is your opinion on Ungredda and Branke, 2021 ?
  They propose a constrained KG acquisition with a MC formulation and show it outperforms the "penalised KG" from Chen et al., 2021.

[sdaulton]

qKnowledgeGradient can run on ConstrainedMCObjective. Is there a reason for why doing so is not recommended in principle?

That should work, but I believe has not been thoroughly evaluated. For one, it seems KG may no longer be non-negative when there are constraints since evaluating a point that is infeasible seems like it could lower the feasible posterior maximizer). Empirically, this could work well though.

what is your opinion on Ungredda and Branke, 2021

I hadn't seen this before, but it looks interesting.

[polivucci]

I hadn't seen this before, but it looks interesting.

I just noticed it has just come out in print.
Table 1 also looks quite interesting to me:)

[slishak-PX]

Sorry to resurrect this old discussion.

Am I right in thinking that ConstrainedMCObjective has one advantage over SampleReducingMCAcquisitionFunction, in that it allows best_f for EI acquisition functions to be set more precisely?

For example, in https://botorch.org/tutorials/closed_loop_botorch_only, we set best_f to the best feasible observation so far. However, what if there are no feasible observations? Or what if we have an equality constraint (which can never be exactly satisfied)?

With ConstrainedMCObjective, we can at least set best_f to the feasibility-weighted objective function which is being maximised. With SampleReducingMCAcquisitionFunction, we can keep randomly sampling until we find a feasible value, or we can guess a feasible best_f value, or we can just choose an infeasible best_f.

[slishak-PX]

@sdaulton not sure if you've seen this, but I'd appreciate your input on this!

[SebastianAment]

Hi @slishak-PX,

Am I right in thinking that ConstrainedMCObjective has one advantage over SampleReducingMCAcquisitionFunction, in that it allows best_f for EI acquisition functions to be set more precisely?

In short: there is no difference in flexibility in setting best_f, and BoTorch uses the same value for both by default, see the following for details.

BoTorch uses compute_best_feasible_objective to set the best_f value, e.g. in the input constructors, the acquisition factories, and in the forward pass of any noisy EI variant.

If there are no feasible observations, compute_best_feasible_objective estimates a lower bound on the unconstrained objective function via _estimate_objective_lower_bound, which calls get_infeasible_cost, the same quantity that is used to specify the value of infeasible observations for ConstrainedMCObjectives, see e.g. here in the input constructor of qUCB.

As a result, the best_f value will be identical for both set-ups if there are no feasible observations. Generally, there's no difference in flexibility in assigning best_f values, and you could implement your own version of compute_best_feasible_objective if you wanted more flexibility.

Since there are significant performance advantages of SampleReducingAcquisitionFunctions over ConstrainedMCObjectives for constrained problems, we strongly recommend the former.

For example, in https://botorch.org/tutorials/closed_loop_botorch_only, we set best_f to the best feasible observation so far.

We should update this to use compute_best_feasible_objective for clarity, the current setup in the tutorial returns zero when there are no feasible observations which is a lower bound to "negative Hartmann", so this is in principle the same idea to inferring a lower bound based on the surrogate.

Or what if we have an equality constraint (which can never be exactly satisfied)?

BoTorch doesn't support equality constraints for outcomes. Generally this doesn't seem to be applicable to real-world experiments, where measurement noise affects the outcomes, and it will give rise to the same problem for both SampleReducingAcquisitionFunctions and ConstrainedMCObjectives since they would both assign best_f based on the infeasible value (lower bound to the objective) computed by get_infeasible_cost. If there's a non-zero tolerance, one could use an upper and lower bound constraint that are apart by the tolerance value, so that feasibility is achievable. Exact constraints are more common on the inputs of the function, and can be incorporated by passing the constraints to optimize_acqf.

With SampleReducingMCAcquisitionFunction, we can keep randomly sampling until we find a feasible value, or we can guess a feasible best_f value, or we can just choose an infeasible best_f.

You don't need to do random sampling, and can use SampleReducingMCAcquisitionFunction whenever you can use ConstrainedMCObjectives.

Let me know if you have additional thoughts or questions on this.

[slishak-PX]

Thank you, this is really helpful. I was unaware of much of the functionality you highlighted - it would be great if some of it was documented/used in some of the tutorials rather than buried in the API documentation!

I take your point on equality constraints not being applicable on real-world noisy observations, but not all applications of BO involve significant noise: if your black box function is deterministic yet expensive and nondifferentiable then you can imagine settings where you might want to set equality constraints on your outputs. As you say, as soon as you apply a tolerance, you of course just end up with a pair of inequality constraints.

[SebastianAment]

it would be great if some of it was documented/used in some of the tutorials rather than buried in the API documentation!

Yes we'll work on this, thanks for the feedback.

want to set equality constraints on your outputs

You can of course also achieve this with two inequality constraints with the same bound using the current functionality. If you are using any member of the LogEI family of acquisition functions (e.g. qLogNoisyExpectedImprovement or qLogNoisyExpectedHypervolumeImprovement), this could still work because the optimizer would get gradient information from the constraint component, even if most of the search space is infeasible.

This would make the policy aggressively search for feasibility, first and foremost. If you are ok with even a small deviation from the exact equality constraint, it would probably give you faster improvements in the objective function.

If you do end up trying this out, I'd be curious to hear about your experience!