Grid search with predetermined parameter order

### Describe the workflow you want to enable

I often have a pipeline with expensive preprocessing, and I tune hyperparameters both for preprocessing and downstream classifier. A toy example with PCA and logistic regression:
```
pipeline = Pipeline([
    ("pca", PCA()),
    ("logreg", LogisticRegression()),
])
cv = GridSearchCV(
    pipeline,
    param_grid={"pca__n_components": [100, 200, 300], "logreg__C": [1, 10, 100]},
    n_jobs=-1
)
```
In this setting, preprocessing is recomputed as many times as there are grid elements. This is very wasteful, as for given preprocessing parameters, the params of the downstream classifier can be optimized. The order would then be:
```
1. pca__n_components=100, check logreg__C = 1, 10, 100
2. pca__n_components=200, check logreg__C = 1, 10, 100
3. pca__n_components=300, check logreg__C = 1, 10, 100
```
For logistic regression, this behavior is actually possible by using `LogisticRegressionCV`. However, e.g. for Random Forest, it is not (to the best of my knowledge). In fact, this can be always done for any pipeline with estimator at the end, since there can only be one classifier (or estimator in general).

This would probably only be relevant to grid search and halving search. For randomized search, a cache for preprocessing output would achieve similar results.

### Describe your proposed solution

Additional parameter or setting to grid search, optimizing parameter order.

Note that this is not equivalent to pipeline caching: https://scikit-learn.org/stable/auto_examples/compose/plot_compare_reduction.html#caching-transformers-within-a-pipeline. Caching only saves the fitting time, whereas here I propose caching the actual transformed output and reusing it for tuning classifier hyperparameters. https://github.com/scikit-learn/scikit-learn/issues/10068 mentions something about caching transform output, but I haven't found confirmation of this behavior anywhere.

### Describe alternatives you've considered, if relevant

This can easily implemented manually in a simple version, but it's less trivial to handle `n_jobs` fully properly. Assuming that we have 100 different parameter sets to check for preprocessing, and 5 sets for classifier, then using n_jobs=6 should always use 6 workers in parallel. But checking only the "current" preprocessing result, we could only use 5 workers. Handling this and starting next batch (i.e. checking estimator hyperparameters for next set of preprocessing parameters) is less trivial, and it would also require keeping 2 (or possibly more) preprocessing results in memory.

### Additional context

This is highly relevant to graph kernels, where preprocessing (computing the kernel) takes ~90% of time. In general, kernel methods would greatly benefit from this.

COMMENT:
There are already 2 things you can do:
- pass a list of dictionaries parameter combinations instead of passing a dictionary
- set `memory` for the `Pipeline` object, which would then cache estimators. As you mention, this doesn't cache the outputs, but it does cache the estimators and that saves the most computationally intensive part.

"Fixing" this would require a massive coupling between `GridSearchCV` and `Pipeline`.

As you mention, a custom implementation of a search cv and a pipeline where they're coupled together might be the best way to go in your usecase, but it doesn't seem like something generic enough that we'd include in scikit-learn for now.

Labels: New Feature, Needs Triage