Repository: scikit-learn/scikit-learn
Pull request: FIX  `param_distribution` param of `HalvingRandomSearchCV` accepts list of dicts 
#### What does this implement/fix? Explain your changes.
Closes #26885
Fixed that the `param_distribution` param of `HalvingRandomSearchCV` accepts lists of dicts and updated documentation.



I also tried to implement a test, using` test_random_search_cv_results` as a template, as you suggested @glemaitre , but I encountered several problems, that I could not resolve. 

The template implementation calls two functions (`check_cv_results_array_types` and `check_cv_results_keys`), that check and compare the occurrence of params. But those might not always be present (like 'param_degree'  is only a key in `cv_results` for the poly kernel, not for rbf). (HalvingSerach' cv_results will also have two additional keys, compared to the other searches, these tests are used for: "iter", "n_resources")

I cannot see a way to use the assert tests in the end of the template test, because  HalvingGridSearchCV will mask part of the candidates, as part of the process. So, checking for this is not going to work, I assume.

I have determined the value for `n_proportion = 6` by looking at `cv_results[key].shape,` which is for sure the wrong way around.

I have commented the test out and hope for your advice. At the moment the test fails because of KeyError (`param_degree`) in one of the util functions.

I could write a much simpler test, that captures the insertion of `param_distribution` as a list of dicts.


Problem statement:
HalvingRandomSearchCV does not support param_distribution as a list
### Describe the bug

Before scikit-learn version 1.3.0 (e.g. 1.2.0) HalvingRandomSearchCV could be used with a `list[dict]` as the input for param_distribution (similar to RandomizedSearchCV). 
The type hint in the documentation states that only `dict` is possible but the description talks about the option to pass also a `list`. As for version 1.3.0 the parameters are validated so `list[dict]` no longer works.

### Steps/Code to Reproduce

```python
from sklearn.experimental import enable_halving_search_cv # noqa
from sklearn.model_selection import HalvingRandomSearchCV, RandomizedSearchCV

from sklearn.tree import DecisionTreeClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.pipeline import Pipeline
from sklearn.datasets import load_iris

X, y = load_iris(return_X_y=True)

pipe = Pipeline([("clf", None)])
params = [
    {'clf': (DecisionTreeClassifier(),), 'clf__criterion': ['entropy', 'gini']},
    {'clf': (LogisticRegression(),), 'clf__C': [0.01, 0.1, 1, 10, 100], 'clf__max_iter': [10_000]}
]

search = HalvingRandomSearchCV(
    pipe, param_distributions=params, scoring="accuracy")

search.fit(X, y)
```

### Expected Results

No error is thrown

### Actual Results

```py
---------------------------------------------------------------------------
InvalidParameterError                     Traceback (most recent call last)
Cell In[22], line 20
     12 params = [
     13     {'clf': (DecisionTreeClassifier(),), 'clf__criterion': ['entropy', 'gini']},
     14     {'clf': (LogisticRegression(),), 'clf__C': [0.01, 0.1, 1, 10, 100], 'clf__max_iter': [10_000]}
     15 ]
     17 search = HalvingRandomSearchCV(
     18     pipe, param_distributions=params, scoring="accuracy")
---> 20 search.fit(X, y)

File ~\AppData\Local\miniconda3\envs\automl\lib\site-packages\sklearn\base.py:1144, in _fit_context.<locals>.decorator.<locals>.wrapper(estimator, *args, **kwargs)
   1139 partial_fit_and_fitted = (
   1140     fit_method.__name__ == "partial_fit" and _is_fitted(estimator)
   1141 )
   1143 if not global_skip_validation and not partial_fit_and_fitted:
-> 1144     estimator._validate_params()
   1146 with config_context(
   1147     skip_parameter_validation=(
   1148         prefer_skip_nested_validation or global_skip_validation
   1149     )
   1150 ):
   1151     return fit_method(estimator, *args, **kwargs)

File ~\AppData\Local\miniconda3\envs\automl\lib\site-packages\sklearn\base.py:637, in BaseEstimator._validate_params(self)
    629 def _validate_params(self):
    630     """Validate types and values of constructor parameters
    631 
    632     The expected type and values must be defined in the `_parameter_constraints`
   (...)
    635     accepted constraints.
    636     """
--> 637     validate_parameter_constraints(
    638         self._parameter_constraints,
    639         self.get_params(deep=False),
    640         caller_name=self.__class__.__name__,
    641     )

File ~\AppData\Local\miniconda3\envs\automl\lib\site-packages\sklearn\utils\_param_validation.py:95, in validate_parameter_constraints(parameter_constraints, params, caller_name)
     89 else:
     90     constraints_str = (
     91         f"{', '.join([str(c) for c in constraints[:-1]])} or"
     92         f" {constraints[-1]}"
     93     )
---> 95 raise InvalidParameterError(
     96     f"The {param_name!r} parameter of {caller_name} must be"
     97     f" {constraints_str}. Got {param_val!r} instead."
     98 )

InvalidParameterError: The 'param_distributions' parameter of HalvingRandomSearchCV must be an instance of 'dict'. Got [{'clf': (DecisionTreeClassifier(),), 'clf__criterion': ['entropy', 'gini']}, {'clf': (LogisticRegression(),), 'clf__C': [0.01, 0.1, 1, 10, 100], 'clf__max_iter': [10000]}] instead.
```

### Versions

```shell
1.3.0
```

Hints from issue discussion:
cc @jeremiedbb @glemaitre 
I can take care of it, thanks @adrinjalali.
So we need to enable it and have some unit tests (since we did not break anything it seems to not be tested :)). @StefanieSenger Go ahead, happy to review the PR.
The param description in the docstring should also be updated. It should be like the one of ``RandomizedSearchCV``
@glemaitre Could you give me a hint of what to test for? 
I assume that we could repeat the test of the `RandomizedSearch`:

https://github.com/scikit-learn/scikit-learn/blob/ca51d77cc28edd57fd22ac2b4a5edf47ce79e3ff/sklearn/model_selection/tests/test_search.py#L991-L1051

Here, we can get the smaller dataset possible and just be sure that we get the expected output regarding the field of `cv_results`.
@glemaitre Thank you for the hint. And I know now what the purpose of testing this is.

As I went through the function I got aware of a miss-match: We instantiate the SVC model with a polynomial kernel and then assert for a linear kernel. I believe this is not on purpose, is it?

See:

```
    params = [
        {"kernel": ["rbf"], "C": expon(scale=10), "gamma": expon(scale=0.1)},
        {"kernel": ["poly"], "degree": [2, 3]},
```

and:

```
    assert all(
        (
            cv_results["param_C"].mask[i]
            and cv_results["param_gamma"].mask[i]
            and not cv_results["param_degree"].mask[i]
        )
        for i in range(n_candidates)
        if cv_results["param_kernel"][i] == "linear"
    )

```

The same for `test_grid_search_cv_results ` above.

Apart from replicating this function for the HalvingGridSearchCV, with not masking any of these params like this:

```
    assert all(
        (
           not  cv_results["param_C"].mask[i] 
            and not cv_results["param_gamma"].mask[i]
            and not cv_results["param_degree"].mask[i]
        )
        for i in range(n_candidates)
        if cv_results["param_kernel"][i] == "poly"
    )

```
I understood that I should make an even smaller dataset, maybe by reducing the number of features to 2?
The dataset can be as small as it can be to make things fast, but I don't think we're very consistent in that, as long as things are fast.

As for the tests, you're right I believe. The first one checking for `linear` is practically returning an empty list, which needs to be fixed.

Commit message: bug fix and cleanup in test_grid_search_cv_results and test_random_search_cv_results

Patch to review:
diff --git a/doc/whats_new/v1.3.rst b/doc/whats_new/v1.3.rst
index 8d39ca2fed143..6ba517f4e24a9 100644
--- a/doc/whats_new/v1.3.rst
+++ b/doc/whats_new/v1.3.rst
@@ -23,6 +23,10 @@ Changelog
   :attr:`sklearn.neighbors.KDTree.valid_metrics` as public class attributes.
   :pr:`26754` by :user:`Julien Jerphanion <jjerphan>`.
 
+- |Fix| :class:`sklearn.model_selection.HalvingRandomSearchCV` no longer raises
+  when the input to the `param_distributions` parameter is a list of dicts.
+  :pr:`26893` by :user:`Stefanie Senger <StefanieSenger>`.
+
 .. _changes_1_3:
 
 Version 1.3.0
diff --git a/sklearn/model_selection/_search_successive_halving.py b/sklearn/model_selection/_search_successive_halving.py
index 38fe1e0e7a15c..708092d09a2a5 100644
--- a/sklearn/model_selection/_search_successive_halving.py
+++ b/sklearn/model_selection/_search_successive_halving.py
@@ -750,11 +750,13 @@ class HalvingRandomSearchCV(BaseSuccessiveHalving):
         Either estimator needs to provide a ``score`` function,
         or ``scoring`` must be passed.
 
-    param_distributions : dict
-        Dictionary with parameters names (string) as keys and distributions
+    param_distributions : dict or list of dicts
+        Dictionary with parameters names (`str`) as keys and distributions
         or lists of parameters to try. Distributions must provide a ``rvs``
         method for sampling (such as those from scipy.stats.distributions).
         If a list is given, it is sampled uniformly.
+        If a list of dicts is given, first a dict is sampled uniformly, and
+        then a parameter is sampled using that dict as above.
 
     n_candidates : "exhaust" or int, default="exhaust"
         The number of candidate parameters to sample, at the first
@@ -1024,7 +1026,7 @@ class HalvingRandomSearchCV(BaseSuccessiveHalving):
 
     _parameter_constraints: dict = {
         **BaseSuccessiveHalving._parameter_constraints,
-        "param_distributions": [dict],
+        "param_distributions": [dict, list],
         "n_candidates": [
             Interval(Integral, 0, None, closed="neither"),
             StrOptions({"exhaust"}),
diff --git a/sklearn/model_selection/tests/test_search.py b/sklearn/model_selection/tests/test_search.py
index 6ea52049f3ced..9c828a3ea0075 100644
--- a/sklearn/model_selection/tests/test_search.py
+++ b/sklearn/model_selection/tests/test_search.py
@@ -900,18 +900,16 @@ def check_cv_results_array_types(search, param_keys, score_keys):
         assert cv_results["rank_test_%s" % key].dtype == np.int32
 
 
-def check_cv_results_keys(cv_results, param_keys, score_keys, n_cand):
+def check_cv_results_keys(cv_results, param_keys, score_keys, n_cand, extra_keys=()):
     # Test the search.cv_results_ contains all the required results
-    assert_array_equal(
-        sorted(cv_results.keys()), sorted(param_keys + score_keys + ("params",))
-    )
+    all_keys = param_keys + score_keys + extra_keys
+    assert_array_equal(sorted(cv_results.keys()), sorted(all_keys + ("params",)))
     assert all(cv_results[key].shape == (n_cand,) for key in param_keys + score_keys)
 
 
 def test_grid_search_cv_results():
     X, y = make_classification(n_samples=50, n_features=4, random_state=42)
 
-    n_splits = 3
     n_grid_points = 6
     params = [
         dict(
@@ -949,9 +947,7 @@ def test_grid_search_cv_results():
     )
     n_candidates = n_grid_points
 
-    search = GridSearchCV(
-        SVC(), cv=n_splits, param_grid=params, return_train_score=True
-    )
+    search = GridSearchCV(SVC(), cv=3, param_grid=params, return_train_score=True)
     search.fit(X, y)
     cv_results = search.cv_results_
     # Check if score and timing are reasonable
@@ -967,17 +963,20 @@ def test_grid_search_cv_results():
     check_cv_results_keys(cv_results, param_keys, score_keys, n_candidates)
     # Check masking
     cv_results = search.cv_results_
-    n_candidates = len(search.cv_results_["params"])
-    assert all(
+
+    poly_results = [
         (
             cv_results["param_C"].mask[i]
             and cv_results["param_gamma"].mask[i]
             and not cv_results["param_degree"].mask[i]
         )
         for i in range(n_candidates)
-        if cv_results["param_kernel"][i] == "linear"
-    )
-    assert all(
+        if cv_results["param_kernel"][i] == "poly"
+    ]
+    assert all(poly_results)
+    assert len(poly_results)
+
+    rbf_results = [
         (
             not cv_results["param_C"].mask[i]
             and not cv_results["param_gamma"].mask[i]
@@ -985,13 +984,14 @@ def test_grid_search_cv_results():
         )
         for i in range(n_candidates)
         if cv_results["param_kernel"][i] == "rbf"
-    )
+    ]
+    assert all(rbf_results)
+    assert len(rbf_results)
 
 
 def test_random_search_cv_results():
     X, y = make_classification(n_samples=50, n_features=4, random_state=42)
 
-    n_splits = 3
     n_search_iter = 30
 
     params = [
@@ -1016,12 +1016,12 @@ def test_random_search_cv_results():
         "mean_score_time",
         "std_score_time",
     )
-    n_cand = n_search_iter
+    n_candidates = n_search_iter
 
     search = RandomizedSearchCV(
         SVC(),
         n_iter=n_search_iter,
-        cv=n_splits,
+        cv=3,
         param_distributions=params,
         return_train_score=True,
     )
@@ -1029,8 +1029,7 @@ def test_random_search_cv_results():
     cv_results = search.cv_results_
     # Check results structure
     check_cv_results_array_types(search, param_keys, score_keys)
-    check_cv_results_keys(cv_results, param_keys, score_keys, n_cand)
-    n_candidates = len(search.cv_results_["params"])
+    check_cv_results_keys(cv_results, param_keys, score_keys, n_candidates)
     assert all(
         (
             cv_results["param_C"].mask[i]
@@ -1038,7 +1037,7 @@ def test_random_search_cv_results():
             and not cv_results["param_degree"].mask[i]
         )
         for i in range(n_candidates)
-        if cv_results["param_kernel"][i] == "linear"
+        if cv_results["param_kernel"][i] == "poly"
     )
     assert all(
         (
diff --git a/sklearn/model_selection/tests/test_successive_halving.py b/sklearn/model_selection/tests/test_successive_halving.py
index d4cc09ee01044..da5de99070246 100644
--- a/sklearn/model_selection/tests/test_successive_halving.py
+++ b/sklearn/model_selection/tests/test_successive_halving.py
@@ -2,7 +2,7 @@
 
 import numpy as np
 import pytest
-from scipy.stats import norm, randint
+from scipy.stats import expon, norm, randint
 
 from sklearn.datasets import make_classification
 from sklearn.dummy import DummyClassifier
@@ -23,7 +23,11 @@
     _SubsampleMetaSplitter,
     _top_k,
 )
-from sklearn.svm import LinearSVC
+from sklearn.model_selection.tests.test_search import (
+    check_cv_results_array_types,
+    check_cv_results_keys,
+)
+from sklearn.svm import SVC, LinearSVC
 
 
 class FastClassifier(DummyClassifier):
@@ -777,3 +781,65 @@ def test_select_best_index(SearchCV):
     # we expect the index of 'i'
     best_index = SearchCV._select_best_index(None, None, results)
     assert best_index == 8
+
+
+def test_halving_random_search_cv_results():
+    X, y = make_classification(n_samples=150, n_features=4, random_state=42)
+
+    params = [
+        {"kernel": ["rbf"], "C": expon(scale=10), "gamma": expon(scale=0.1)},
+        {"kernel": ["poly"], "degree": [2, 3]},
+    ]
+    param_keys = (
+        "param_C",
+        "param_degree",
+        "param_gamma",
+        "param_kernel",
+    )
+    score_keys = (
+        "mean_test_score",
+        "mean_train_score",
+        "rank_test_score",
+        "split0_test_score",
+        "split1_test_score",
+        "split2_test_score",
+        "split0_train_score",
+        "split1_train_score",
+        "split2_train_score",
+        "std_test_score",
+        "std_train_score",
+        "mean_fit_time",
+        "std_fit_time",
+        "mean_score_time",
+        "std_score_time",
+    )
+    extra_keys = ("n_resources", "iter")
+
+    search = HalvingRandomSearchCV(
+        SVC(), cv=3, param_distributions=params, return_train_score=True, random_state=0
+    )
+    search.fit(X, y)
+    n_candidates = sum(search.n_candidates_)
+    cv_results = search.cv_results_
+    # Check results structure
+    check_cv_results_keys(cv_results, param_keys, score_keys, n_candidates, extra_keys)
+    check_cv_results_array_types(search, param_keys, score_keys)
+
+    assert all(
+        (
+            cv_results["param_C"].mask[i]
+            and cv_results["param_gamma"].mask[i]
+            and not cv_results["param_degree"].mask[i]
+        )
+        for i in range(n_candidates)
+        if cv_results["param_kernel"][i] == "poly"
+    )
+    assert all(
+        (
+            not cv_results["param_C"].mask[i]
+            and not cv_results["param_gamma"].mask[i]
+            and cv_results["param_degree"].mask[i]
+        )
+        for i in range(n_candidates)
+        if cv_results["param_kernel"][i] == "rbf"
+    )


Code review comments:
diff_hunk: @@ -967,31 +963,35 @@ def test_grid_search_cv_results():
     check_cv_results_keys(cv_results, param_keys, score_keys, n_candidates)
     # Check masking
     cv_results = search.cv_results_
-    n_candidates = len(search.cv_results_["params"])
-    assert all(
+
+    poly_results = [
         (
             cv_results["param_C"].mask[i]
             and cv_results["param_gamma"].mask[i]
             and not cv_results["param_degree"].mask[i]
         )
         for i in range(n_candidates)
-        if cv_results["param_kernel"][i] == "linear"
-    )
-    assert all(
+        if cv_results["param_kernel"][i] == "poly"
+    ]
+    assert all(poly_results)
+    assert len(poly_results)
path: sklearn/model_selection/tests/test_search.py
text: @user1:
in this case we know exactly how many candidates there were for each kernel (4 and 2), so we could check the exact length.

@author:
Yes! I've added that.