Ax: Constraints on discrete parameters do not work - seem to operate on double-values

[winf-hsos]

I created an experiment with 3 discrete parameters P1, P2, and P3, all in the range from 1 to 10. I also put a constraint on the experiment:

P1 + P2 + P3 <= 10

When I run the experiment, I frequently get suggestions that do not satisfy the constraint. I tried the same setting the parameters to continuous, here there are no violations of the constraint. My guess is that the constraints are evaluated at the level of the original continuous values, which are rounded afterwards. So a continuous parameter set of P1 = 3.51, P2 = 3.51 and P3 = 2.51 would satisfy the constraint, but when the values are rounded we get P1 = 4, P2 = 4, and P3 3, which sums up to 11 and the constraint is violated.

How can I address this issue. I only want to get valid suggestions for discrete parameters with constraints.

Thx
Nicolas

[lena-kashtelyan]

Hi, @winf-hsos! Quick question: are your parameters of form RangeParameter(parameter_type=ParameterType.INT, ...) and constraints are SumConstraint-s? Or how are you initializing the parameters and constraints in your experiment? Your hunch is likely correct, but knowing exactly what your code looks like will help us debug faster.

Also, while we're working on debugging, the quick workaround would be to manually check the suggested parameterizations for whether they violate the constraint and just manually call ax_client.get_next_trial() again if they do.

[winf-hsos]

Hi, @lena-kashtelyan! Thanks for the reply. Short answer to your question. Yes, I create the experiment including the parameters like this:

ax = AxClient(verbose_logging=True)
current_trial_index = 0

# Setup experiment
params = [
        {
            "name": "p1",
            "type": "range",
            "bounds": [0, 20],
            "value_type": "int",

        },
        {
            "name": "p2",
            "type": "range",
            "bounds": [0, 20],
            "value_type": "int",

        },
        {
            "name": "p3",
            "type": "range",
            "bounds": [0, 20],
            "value_type": "int",           
        }
]

constraints = ["p1 + p2 + p3 <= 20"]

ax.create_experiment(
        name="Model",
        parameters=params,
        objective_name="MyResponse",
        minimize=True,
        parameter_constraints=constraints
    )

Where the objective function MyResponse is the response from a simulation model run in an external simulation tool called Simio. The tool asks for new suggestions, and I generate them with:

parameters, current_trial_index = ax.get_next_trial()

When the simulation ran and it created the response, I complete the trial like this:

ax.complete_trial(trial_index=current_trial_index, raw_data=responses)

I attached a JSON dump of a model (model_debug.zip) I ran which has proposed a set of values for the parameters that violate the constraint. This happens in trial 23. In all subsequent trials, BO suggests this very same point over and over again (until trial 100 where I stop the process). I think there is a correlation between constraint violating points and creating the same trials over and over again, which is addressed in issue #228. It's not ALWAYS the case, but very often that BO won't stop suggesting the same point forever (or very many times). But this is just an impression I got from observing, not a systematic evaluation behind it.

By the way, I think BO does notice the point is out of bounds:

[INFO 12-15 00:02:52] ModelBridge: Leaving out out-of-design observations for arms: 22_0

But why then does it even suggest it? And how could I obtain that information, other than from the log output? If could check somehow whether a point violates the constraint, I could then decide not to run the simulation (or evaluate the objective function) with that point. But I am not sure if that would solve the issue of BO suggesting the point over and over again.

Below you see a screenshot of the suggestions in the experiment view of the simulation tool. The red marked scenarios starting in scenario 23 have parameters (controls) that violate the constraint:

Thanks very much, your help is greatly appreciated!
Nicolas

[2timesjay]

@winf-hsos I can provide more background.

Our underlying algorithm transforms int ranges to floats, to more flexibly apply our underlying Gaussian Process algorithms implemented in BoTorch, then rounds the results back to ints. When the floating-point candidates are generated they obey the constraints you've given, but our rounding ignores constraints.

This rounding also causes the repeated selection of points in this region because of some details of our point selection algorithm* (see note).

We're working on making rounding smarter and aim to have a fix soon but this there can always be constraints that are difficult or impossible to satisfy (yours should be simple enough to not be a problem).

The best solution, if possible for you, is to use float ranges. If not, the point chosen is still quite good. You could try to manually add trials for nearby points or enforce a slightly stricter constraint which will be within your original constraint when violated.

*We choose points by a combination of expected objective score and uncertainty about that objective score, called "Expected Improvement". After rounding the uncertainty is not reduced very much at original floating-point candidate location, so it can continue to be the best-scoring candidate again and again. With floating-point ranges this sort of degenerate behavior doesn't happen.

[winf-hsos]

The best solution, if possible for you, is to use float ranges. If not, the point chosen is still quite good. You could try to manually add trials for nearby points or enforce a slightly stricter constraint which will be within your original constraint when violated.

Just to be sure: I can define a parameter as int and then define ranges as being float, and that might solve my issue? Like this?

params = [
        {
            "name": "p1",
            "type": "range",
            "bounds": [0.0, 20.0],
            "value_type": "int",
        }
]

Or do you mean the best solution would be to get rid of int parameters altogether? Because that wouldn't solve my problem, or at best move the problem to a later stage when I have to decide what a float value for a machine capacity (which is discrete by nature) means and how I run the simulation with it.

This rounding also causes the repeated selection of points in this region because of some details of our point selection algorithm* (see note).

*We choose points by a combination of expected objective score and uncertainty about that objective score, called "Expected Improvement". After rounding the uncertainty is not reduced very much at original floating-point candidate location, so it can continue to be the best-scoring candidate again and again. With floating-point ranges this sort of degenerate behavior doesn't happen.

I understand the concept of exploration and exploitation. I didn't really understand why the uncertainty is not reduced using the rounded numbers. Can you please explain that in more detail?

I also thought about introducing a penalty (very large response) for parameters constellations that violate the constraints. Do you think that would be a good addition to avoid theses combinations better?

[2timesjay]

Unfortunately changing the bounds to floats alone won't help anything (and might throw an error) you would need to change the value_type to float. Since this fits poorly with your model it's not a great solution (but if you model with float parameters then do the rounding yourself in a way that conforms to your constraints you might end up with a decent solution).

---

Details on the repeated point problem:

The underlying Gaussian Process generates point (6.5, 6.6, 6.7). Let's suppose it has estimated objective 36 and estimated uncertainty 10. This is then rounded to (7, 7, 7). If objective error is 0 then uncertainty is reduced to 0 at point (7, 7, 7), and the objective estimate set to 38 there. However, at point (6.5, 6.6, 6.7) the objective estimate and estimated uncertainty will be updated only slightly, proportionate to their distance from the point they were rounded to.

Even if the uncertainty estimate is reduced substantially (6.5, 6.6, 6.7) or points very close to it may continue to have the highest expected improvement, and their uncertainty (and consequently expected improvement score) will never be reduced to 0.

This is a weakness of our algorithm when discrete parameters are present, but on the other hand the point that gets chosen repeatedly should be quite close to the truly optimal point in general.

---

Solution:

We have just finished implementing a solution internally that will randomize rounding when discrete parameter ranges are constrained, and attempt to find a rounding that obeys those constraints (by rounding up to 1000 times).

When this rounding is very difficult and the constraint can't be followed you'll see behavior similar to what you currently see. However your constraint is fairly simple and you should see valid roundings.

The repeated point problem can still happen, but random rounding is likely to eventually reduce uncertainty more at the chosen floating point than the current deterministic rounding.

[lena-kashtelyan]

The smart rounding fix is now part of the latest stable version, 0.1.8!

[winf-hsos]

Thank you so much for adding this so quick. Just tried it, it works great for me.

One question to be sure: Although there are no more suggestions that violate the constraints (so far), the problem with identical trials doesn't go away (as expected, considering the explanation by @2timesjay above). So when I get identical trials, is it best to complete the trial and giving BO the same answer over and over again to step by step reduce the uncertainty in the area of this point of integers? Or should I not complete these repeated trials and ask for the next point. My hunch is it would be better to complete these trials, right?

Also, in the newly generated warning I would suggest to (small) improvements:

[WARNING 12-27 21:12:32] ax.modelbridge.transforms.int_to_float: Unable to round {'PropertyCapaServer1': 5, 'PropertyCapaServer2': 8, 'PropertyCapaServer3': 7, 'PropertyCapaServer4': 10, 'PropertyCapaServer5': 9}to meet constraints of SearchSpace(parameters=[RangeParameter(name='PropertyCapaServer1', parameter_type=INT, range=[1, 10]), RangeParameter(name='PropertyCapaServer2', parameter_type=INT, range=[1, 10]), RangeParameter(name='PropertyCapaServer3', parameter_type=INT, range=[1, 10]), RangeParameter(name='PropertyCapaServer4', parameter_type=INT, range=[1, 10]), RangeParameter(name='PropertyCapaServer5', parameter_type=INT, range=[1, 10])], parameter_constraints=[ParameterConstraint(1.0*PropertyCapaServer1 + 1.0*PropertyCapaServer2 + 1.0*PropertyCapaServer3 + 1.0*PropertyCapaServer4 + 1.0*PropertyCapaServer5 <= 25.0)])

1. I think it is a bit misleading to say that you couldn't round the integer values to meet the constraints. It would be better to actually print the float values that could not be rounded. I am curious if I could somehow obtain these anyway?

2. Add a space between printing the parameters and to meet constraints

Thanks again so much!
Nicolas

[eytan]

Hi Nicolas,

Re: repeating points: Is your function deterministic? If it is stochastic then evaluating the point multiple times could be useful, but if not you are better off just terminating since picking the same point over and over suggests that the algorithm has converged to a global max. Feeding it the same (input, output) pairs over and over could cause numerical issues and is not likely to fix anything.

Thanks for the feedback re: warnings.

Sent from my iPhone

On Dec 27, 2019, at 3:24 PM, Nicolas [e-mail] wrote:


Thank you so much for adding this so quick. Just tried it, it works great for me.

One question to be sure: Although there are no more suggestions that violate the constraints (so far), the problem with identical trials doesn't go away (as expected, considering the explanation by @2timesjay above). So when I get identical trials, is it best to complete the trial and giving BO the same answer over and over again to step by step reduce the uncertainty in the area of this point of integers? Or should I not complete these repeated trials and ask for the next point. My hunch is it would be better to complete these trials, right?

Also, in the newly generated warning I would suggest to (small) improvements:

[WARNING 12-27 21:12:32] ax.modelbridge.transforms.int_to_float: Unable to round {'PropertyCapaServer1': 5, 'PropertyCapaServer2': 8, 'PropertyCapaServer3': 7, 'PropertyCapaServer4': 10, 'PropertyCapaServer5': 9}to meet constraints of SearchSpace(parameters=[RangeParameter(name='PropertyCapaServer1', parameter_type=INT, range=[1, 10]), RangeParameter(name='PropertyCapaServer2', parameter_type=INT, range=[1, 10]), RangeParameter(name='PropertyCapaServer3', parameter_type=INT, range=[1, 10]), RangeParameter(name='PropertyCapaServer4', parameter_type=INT, range=[1, 10]), RangeParameter(name='PropertyCapaServer5', parameter_type=INT, range=[1, 10])], parameter_constraints=[ParameterConstraint(1.0PropertyCapaServer1 + 1.0PropertyCapaServer2 + 1.0PropertyCapaServer3 + 1.0PropertyCapaServer4 + 1.0*PropertyCapaServer5 <= 25.0)])

I think it is a bit misleading to say that you couldn't round the integer values to meet the constraints. It would be better to actually print the float values that could not be rounded. I am curious if I could somehow obtain these anyway?

Add a space between printing the parameters and to meet constraints

Thanks again so much!
Nicolas

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub, or unsubscribe.

[winf-hsos]

Hi @eytan, yes for now it is deterministic, although we plan to apply it to stochastic simulations in the near future. My current optimization problem has 5 integer parameters (machine capacities) in the range of 1 to 20. If I understand correctly, the problem here is that BO is optimizing using floats under the hood, and then rounding them (which was improved with the last fix). So I see the same point(s) over and over again, but under the hood it could actually be trying to reduce uncertainty in a particular area. This "reducing uncertainty" works only so well with integers, if I correctly understand @2timesjay explanations. So maybe it takes a lot of iterations until a new point is tried? But how can I know how many?

For this particular problem, I know the optimum from applying brute force to it. In some optimization runs, I get the same point many times, but it is definitely not a global optimum. If I let it run long enough it will eventually find the optimum (or a very close solution), but not without many times the same point(s) over and over again.

Thx
Nicolas

[winf-hsos]

UPDATE: I tested a bit more. The smart rounding does not seem to apply when I have a mixed scenario with 2 integers and 1 float parameter. With that constellation, I constantly get constraint violations. It seems to be even worse in that case now.

[winf-hsos]

UPDATE 2:: I have now removed the float parameter from the constraint, but the problem remains: Many constellations with the two integers that are violating the constraint. This worked perfectly in a scenario where I had only integer parameters.

[2timesjay]

@winf-hsos Thanks for the error message suggestion. I'll double check the rounding, though you mixed int/float case should be covered as well as the int case (and will fail in the same sorts of circumstances as solely-int constraints will fail).

Right now we have no good way to estimate the reduction in uncertainty, or the number of iterations to fully exhaust the acquisition function at a local optima, when int parameters are involved.

We would really appreciate any additional details about your problem that could help with reproduction, especially the gap between Ax's best point after a reasonable number of simulations and your true verified global optimum. If it's very large then maybe ax is just modeling the problem poorly (for instance if the best point found with float parameters is worse than the true optimum with int parameters, then poor modeling and/or a need for more iterations are both likely)

[winf-hsos]

@2timesjay So far from our initial experiments it appears Ax finds very good points (or the best) within < 50 trials (simulations) for our specific example. For a first result that's pretty amazing in my opinion. That said, we have not yet performed _systematic_ analysis of the applicability to our discrete and stochastic simulation models we find in practice. Until now we are still in a proof of concept phase with a limited and synthetic model. To improve upon that and do a systematic evaluation is one of our research goals we'll pursue in the next weeks and months to come. I will update you on our results when we have them, and also let you know about any questions, bugs or improvements we might come up with ;)

Thanks very much for your help already up until here. We are looking forward to working with and contributing to the development of Ax in 2020!

Nicolas