HalvingGridSearchCV giving non-optimal results with min_resources='exhaust'

### Describe the bug

I am using `HalvingGridSearchCV` with 160 combinations and 1050 samples. When I use `min_resources` with `'exhaust'`, I get 6 iterations with the last iteration including 5 candidates and 640 samples. The process starts with 20 samples.

When I set `min_resources=30`, I also get 6 iterations with the last iteration having 5 candidates, but with 960 samples.

### Steps/Code to Reproduce

```python
halving_cv = HalvingGridSearchCV(
    knn_model, knn_grid,  #our model and the parameter combos we want to try
    scoring="roc_auc",  #could alternatively choose f1, accuracy or others
    n_jobs=-1,  #use all available cpus
    min_resources=30,  #"exhaust" sets this to 20, which is non-optimal. Possible bug in algorithm.
    factor=2,  #double samples and take top half of combos on each iteration
    cv=5, random_state=1234,
    refit=True,  #remembers the best combo and gives us back that model already trained and ready for testing
)

grid_result = halving_cv.fit(x_train, y_train)
```

### Expected Results

My understanding is that by using 'exhaust', the algorithm should figure out that 30 is a better value for min_resources. Instead it sets it to 20.

My ideal case would be for the last iteration to use all 1050 samples with the 5 candidates but I see no way to set parameters to make this happen.

My question is whether there is a bug in the min_resources=exhaust algorithm.

### Actual Results

With min_resources=30:
```
310	5	960	{'algorithm': 'auto', 'n_neighbors': 15, 'p': 1, 'weights': 'uniform'}	0.804883
311	5	960	{'algorithm': 'brute', 'n_neighbors': 5, 'p': 1, 'weights': 'uniform'}	0.793407
312	5	960	{'algorithm': 'ball_tree', 'n_neighbors': 5, 'p': 1, 'weights': 'uniform'}	0.789650
313	5	960	{'algorithm': 'auto', 'n_neighbors': 5, 'p': 1, 'weights': 'uniform'}	0.789410
314	5	960	{'algorithm': 'kd_tree', 'n_neighbors': 5, 'p': 1, 'weights': 'uniform'}	0.789410
```

### Versions

```shell
System:
    python: 3.10.12 (main, Jun 11 2023, 05:26:28) [GCC 11.4.0]
executable: /usr/bin/python3
   machine: Linux-5.15.109+-x86_64-with-glibc2.35

Python dependencies:
      sklearn: 1.2.2
          pip: 23.1.2
   setuptools: 67.7.2
        numpy: 1.23.5
        scipy: 1.11.2
       Cython: 3.0.2
       pandas: 1.5.3
   matplotlib: 3.7.1
       joblib: 1.3.2
threadpoolctl: 3.2.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 2
         prefix: libopenblas
       filepath: /usr/local/lib/python3.10/dist-packages/numpy.libs/libopenblas64_p-r0-742d56dc.3.20.so
        version: 0.3.20
threading_layer: pthreads
   architecture: Zen

       user_api: openmp
   internal_api: openmp
    num_threads: 2
         prefix: libgomp
       filepath: /usr/local/lib/python3.10/dist-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
        version: None

       user_api: blas
   internal_api: openblas
    num_threads: 2
         prefix: libopenblas
       filepath: /usr/local/lib/python3.10/dist-packages/scipy.libs/libopenblasp-r0-23e5df77.3.21.dev.so
        version: 0.3.21.dev
threading_layer: pthreads
   architecture: Zen

       user_api: blas
   internal_api: openblas
    num_threads: 2
         prefix: libopenblas
       filepath: /usr/local/lib/python3.10/dist-packages/cvxopt.libs/libopenblasp-r0-5c2b7639.3.23.so
        version: 0.3.23
threading_layer: pthreads
   architecture: Zen
```
```

COMMENT:
So the relevant parts of the code are:

```py
        self.min_resources_ = self.min_resources
        if self.min_resources_ in ("smallest", "exhaust"):
            if self.resource == "n_samples":
                n_splits = self._checked_cv_orig.get_n_splits(X, y, **split_params)
                # please see https://gph.is/1KjihQe for a justification
                magic_factor = 2
                self.min_resources_ = n_splits * magic_factor
                if is_classifier(self.estimator):
                    y = self._validate_data(X="no_validation", y=y)
                    check_classification_targets(y)
                    n_classes = np.unique(y).shape[0]
                    self.min_resources_ *= n_classes
            else:
                self.min_resources_ = 1
            # if 'exhaust', min_resources_ might be set to a higher value later
            # in _run_search
```

which sets `min_resources_` to 20, and then this happens:

```py
        # n_required_iterations is the number of iterations needed so that the
        # last iterations evaluates less than `factor` candidates.
        n_required_iterations = 1 + floor(log(len(candidate_params), self.factor))

        if self.min_resources == "exhaust":
            # To exhaust the resources, we want to start with the biggest
            # min_resources possible so that the last (required) iteration
            # uses as many resources as possible
            last_iteration = n_required_iterations - 1
            self.min_resources_ = max(
                self.min_resources_,
                self.max_resources_ // self.factor**last_iteration,
            )

        # n_possible_iterations is the number of iterations that we can
        # actually do starting from min_resources and without exceeding
        # max_resources. Depending on max_resources and the number of
        # candidates, this may be higher or smaller than
        # n_required_iterations.
        n_possible_iterations = 1 + floor(
            log(self.max_resources_ // self.min_resources_, self.factor)
        )
```

This sets `n_possible_iterations` to 6, but I think it should be 7. With 6, the maximum resources to be used would be `20 * 2**5 = 640`. But There could be another extra iteration.

Note that later we have:

```py
            n_resources = int(self.factor**power * self.min_resources_)
            # guard, probably not needed
            n_resources = min(n_resources, self.max_resources_)
```

But I think `n_possible_iterations` should be 7, and the `n_resources = min(n_resources, self.max_resources_)` would then use maximum resources.

So the fix in this case would be to change `n_possible_iterations` to:

```py
        n_possible_iterations = 1 + ceil(
            log(self.max_resources_ // self.min_resources_, self.factor)
        )
```

Is this correct @NicolasHug ?

Labels: Needs Decision