Repository: optuna/optuna
Pull request: Guarantee `weights_below` to be finite in MOTPE
<!-- Thank you for creating a pull request! In general, we merge your pull request after it gets two or more approvals. To proceed to the review process by the maintainers, please make sure that the PR meets the following conditions: (1) it passes all CI checks, and (2) it is neither in the draft nor WIP state. If you wish to discuss the PR in the draft state or need any other help, please mention the Optuna development team in the PR. -->

## Motivation
<!-- Describe your motivation why you will submit this PR. This is useful for reviewers to understand the context of PR. -->

Resolve https://github.com/optuna/optuna/issues/5374

## Description of the changes
<!-- Describe the changes in this PR. -->

I added code to guarantee `weights_below` to be finite in MOTPE. Weights fall-back to uniform if it contains inf, nan, or a value large enough to be inf when summed.

Problem statement:
Returning `float("inf")` failed with MOTPE
### Expected behavior

No errors occur.

### Environment

- Optuna version:4.0.0.dev
- Python version:3.12.2
- OS:macOS-14.4.1-arm64-arm-64bit

### Error messages, stack traces, or logs

```shell
[I 2024-03-29 17:20:44,217] A new study created in memory with name: no-name-3289a723-a36c-4729-a37e-6b440b830668
[I 2024-03-29 17:20:44,218] Trial 0 finished with values: [-0.497867971784556, inf] and parameters: {'x': -0.497867971784556}. 
[I 2024-03-29 17:20:44,218] Trial 1 finished with values: [1.3219469606529486, 0.0] and parameters: {'x': 1.3219469606529486}. 
[I 2024-03-29 17:20:44,218] Trial 2 finished with values: [-2.9993137510959307, inf] and parameters: {'x': -2.9993137510959307}. 
[I 2024-03-29 17:20:44,218] Trial 3 finished with values: [-1.1860045642089614, inf] and parameters: {'x': -1.1860045642089614}. 
[I 2024-03-29 17:20:44,218] Trial 4 finished with values: [-2.119464655097322, inf] and parameters: {'x': -2.119464655097322}. 
[I 2024-03-29 17:20:44,218] Trial 5 finished with values: [-2.445968431387213, inf] and parameters: {'x': -2.445968431387213}. 
[I 2024-03-29 17:20:44,218] Trial 6 finished with values: [-1.8824387317339746, inf] and parameters: {'x': -1.8824387317339746}. 
[I 2024-03-29 17:20:44,218] Trial 7 finished with values: [-0.9266356377417135, inf] and parameters: {'x': -0.9266356377417135}. 
[I 2024-03-29 17:20:44,218] Trial 8 finished with values: [-0.6193951546159804, inf] and parameters: {'x': -0.6193951546159804}. 
[I 2024-03-29 17:20:44,218] Trial 9 finished with values: [0.23290040402014167, 0.0] and parameters: {'x': 0.23290040402014167}. 
/Users/gen740/home/PFN/optuna/optuna/_hypervolume/hssp.py:62: RuntimeWarning: invalid value encountered in subtract
  assert not np.any(reference_point - rank_i_loss_vals < 0)
/Users/gen740/home/PFN/optuna/optuna/_hypervolume/hssp.py:64: RuntimeWarning: invalid value encountered in subtract
  contribs = np.prod(reference_point - rank_i_loss_vals, axis=-1)
[I 2024-03-29 17:20:44,222] Trial 10 finished with values: [2.7299172994598835, 0.0] and parameters: {'x': 2.7299172994598835}. 
/Users/gen740/home/PFN/optuna/optuna/_hypervolume/utils.py:39: RuntimeWarning: invalid value encountered in subtract
  edge_length_y = reference_points_y_cummin[mask] - used_solution[:, 1]
[W 2024-03-29 17:20:44,223] Trial 11 failed with parameters: {} because of the following error: ValueError('probabilities contain NaN').
Traceback (most recent call last):
  File "/Users/gen740/home/PFN/optuna/optuna/study/_optimize.py", line 196, in _run_trial
    value_or_values = func(trial)
                      ^^^^^^^^^^^
  File "/Users/gen740/home/PFN/workspace/pr/5355/motpe_inf.py", line 5, in objective
    x = trial.suggest_float("x", -3, 3)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/trial/_trial.py", line 163, in suggest_float
    suggested_value = self._suggest(name, distribution)
                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/trial/_trial.py", line 629, in _suggest
    param_value = self.study.sampler.sample_independent(
                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/samplers/_tpe/sampler.py", line 447, in sample_independent
    return self._sample(study, trial, {param_name: param_distribution})[param_name]
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/samplers/_tpe/sampler.py", line 487, in _sample
    samples_below = mpe_below.sample(self._rng.rng, self._n_ei_candidates)
                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/samplers/_tpe/parzen_estimator.py", line 81, in sample
    sampled = self._mixture_distribution.sample(rng, size)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/samplers/_tpe/probability_distributions.py", line 41, in sample
    active_indices = rng.choice(len(self.weights), p=self.weights, size=batch_size)
                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "numpy/random/mtrand.pyx", line 971, in numpy.random.mtrand.RandomState.choice
ValueError: probabilities contain NaN
[W 2024-03-29 17:20:44,225] Trial 11 failed with value None.
Traceback (most recent call last):
  File "/Users/gen740/home/PFN/workspace/pr/5355/motpe_inf.py", line 11, in <module>
    study.optimize(objective, n_trials=20)
  File "/Users/gen740/home/PFN/optuna/optuna/study/study.py", line 451, in optimize
    _optimize(
  File "/Users/gen740/home/PFN/optuna/optuna/study/_optimize.py", line 62, in _optimize
    _optimize_sequential(
  File "/Users/gen740/home/PFN/optuna/optuna/study/_optimize.py", line 159, in _optimize_sequential
    frozen_trial = _run_trial(study, func, catch)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/study/_optimize.py", line 247, in _run_trial
    raise func_err
  File "/Users/gen740/home/PFN/optuna/optuna/study/_optimize.py", line 196, in _run_trial
    value_or_values = func(trial)
                      ^^^^^^^^^^^
  File "/Users/gen740/home/PFN/workspace/pr/5355/motpe_inf.py", line 5, in objective
    x = trial.suggest_float("x", -3, 3)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/trial/_trial.py", line 163, in suggest_float
    suggested_value = self._suggest(name, distribution)
                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/trial/_trial.py", line 629, in _suggest
    param_value = self.study.sampler.sample_independent(
                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/samplers/_tpe/sampler.py", line 447, in sample_independent
    return self._sample(study, trial, {param_name: param_distribution})[param_name]
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/samplers/_tpe/sampler.py", line 487, in _sample
    samples_below = mpe_below.sample(self._rng.rng, self._n_ei_candidates)
                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/samplers/_tpe/parzen_estimator.py", line 81, in sample
    sampled = self._mixture_distribution.sample(rng, size)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/gen740/home/PFN/optuna/optuna/samplers/_tpe/probability_distributions.py", line 41, in sample
    active_indices = rng.choice(len(self.weights), p=self.weights, size=batch_size)
                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "numpy/random/mtrand.pyx", line 971, in numpy.random.mtrand.RandomState.choice
ValueError: probabilities contain NaN
```


### Steps to reproduce

```python
import optuna


def objective(trial):
    x = trial.suggest_float("x", -3, 3)
    return x, float("inf") if x < 0 else 0


sampler = optuna.samplers.TPESampler(seed=1)
study = optuna.create_study(directions=["minimize"] * 2, sampler=sampler)
study.optimize(objective, n_trials=20)
```
Run this code.

### Additional context (optional)

_No response_

Hints from issue discussion:
This error happens because the WFG calculates `inf - inf`, leading to `nan`.

In principle, we just need to return `inf` by definition if either the reference point or some of non-dominated points include `inf` or `-inf`.

Commit message: Update sampler.py

Patch to review:
diff --git a/optuna/samplers/_tpe/sampler.py b/optuna/samplers/_tpe/sampler.py
index 30d6d82e273..0d01561a5a9 100644
--- a/optuna/samplers/_tpe/sampler.py
+++ b/optuna/samplers/_tpe/sampler.py
@@ -516,6 +516,8 @@ def _build_parzen_estimator(
             weights_below = _calculate_weights_below_for_multi_objective(
                 study, trials, self._constraints_func
             )[param_mask_below]
+            if not np.isfinite(weights_below).all():
+                weights_below = np.clip(1.0 - np.isfinite(weights_below), EPS, 1.0)
             mpe = self._parzen_estimator_cls(
                 observations, search_space, self._parzen_estimator_parameters, weights_below
             )
@@ -814,8 +816,8 @@ def _calculate_weights_below_for_multi_objective(
         contributions = np.asarray(
             [hv - WFG().compute(lvals[indices_mat[i]], reference_point) for i in range(n_below)]
         )
-        contributions += EPS
-        weights_below = np.clip(contributions / np.max(contributions), 0, 1)
+        contributions = np.clip(contributions, EPS, None)
+        weights_below = np.clip(contributions / np.max(contributions), EPS, 1.0)
 
     # For now, EPS weight is assigned to infeasible trials.
     weights_below_all = np.full(len(below_trials), EPS)


Code review comments:
diff_hunk: @@ -814,8 +816,8 @@ def _calculate_weights_below_for_multi_objective(
         contributions = np.asarray(
             [hv - WFG().compute(lvals[indices_mat[i]], reference_point) for i in range(n_below)]
         )
-        contributions += EPS
-        weights_below = np.clip(contributions / np.max(contributions), 0, 1)
+        contributions = np.clip(contributions, EPS, None)
+        weights_below = np.clip(contributions / np.max(contributions), EPS, 1.0)
path: optuna/samplers/_tpe/sampler.py
text: @user1:
If the debugging is the purpose, what about the following and removing the lines in `_build_parzen_estimator`?
```suggestion
        contributions[np.isnan(contributions)] = np.inf
        max_contribution = np.max(contributions)
        if not np.isfinite(max_contribution):
            weights_below = np.ones_like(contributions, dtype=float)
            weights_below[np.isfinite(contributions)] = EPS
        else:
            weights_below = np.clip(contributions / max_contribution, EPS, 1)
```

@author:
I thought `contributions = np.clip(contributions, EPS, None)` is slightly better than `contributions += EPS` just because `contributions` can be close to `sys.float_info.max`; in that case, adding eps results inf.
However, since that rarely happens, I reconsidered and agree that your suggestion is better.