Cross validation and hyperparameter tuning workflow After reading a lot of articles on cross validation, I am now confused. I know that cross validation is used to get an estimate of model performance and is used to select the best algorithm out of multiple ones. After selecting the best model (by checking the mean and standard deviation of CV scores) we train that model on the whole of the dataset (train and validation set) and use it for real world predictions.
Let's say out of the 3 algorithms I used in cross validation, I select the best one. What I don't get is in this process, when do we tune the hyperparameters? Do we use Nested Cross validation to tune the hyperparameters during the cross validation process or do we first select the best performing algorithm via cross validation and then tune the hyperparameter for only that algorithm?
PS: I am splitting my dataset into train, test and valid where I use train and test sets for building and testing my model (this includes all the preprocessing steps and nested cv) and use the valid set to test my final model.
Edit 1 Below are two ways to perform Nested cross validation. Which one is the correct way aka which method does not lead to data leakage/overfitting/bias?
Method 1: Perform Nested CV for multiple algorithms and their hyperparameters simultaneously:-
# create some regression data
X, y = make_regression(n_samples=1000, n_features=10)

# split into train and test sets
X_train, X_test, y_train, y_test = train_test_split(X, y, train_size=0.3)

# set up models and params
model1 = SVR()
model2 = RandomForestRegressor(random_state = 69)

param1 = [{'C':[0.01,0.05]}]
param2 = [{'n_estimators':[10,100]}]

# inner cv for HP tuning
inner_cv = KFold(n_splits = 3)
gridcvs = {}

# estimate performance of hyperparameter tuning and model algorithm pipeline
for params, model, name in zip((param1, param2), (model1, model2), ('SVR', 'DTR')):
    
    # perform hyperparameter tuning
    gcv = GridSearchCV(estimator = model, param_grid = params, cv = inner_cv, 
                       scoring = 'neg_mean_absolute_error',
                       refit = True)
    
    gridcvs[name] = gcv
    
# outer cv for checking model performance        
outer_cv = KFold(n_splits = 5)

# outer loop cv
for name, gs_model in sorted(gridcvs.items()):
      nested_score = cross_val_score(gs_model, X_train, y_train, cv = outer_cv, n_jobs = -1, scoring = 'neg_mean_absolute_error')
      print(name, nested_score.mean(), nested_score.std())
    

# select HP for the best model (model2) based on regular k-fold on whole training set    
final_cv = KFold(n_splits = 5)

gcv_final_HP = GridSearchCV(estimator = model2,
                            param_grid = param2,
                            cv = final_cv, scoring = 'neg_mean_absolute_error'
                            )
    
gcv_final_HP.fit(X_train, y_train)

# get the best model from the gcv_final_HP
best_model = gcv_final_HP.best_estimator_    

# fit the model to whole "training" dataset
best_model.fit(X_train, y_train)
pred = best_model.predict(X_test)
mae = mean_absolute_error(y_test, pred)
    
# fit the model to whole of dataset to be deployed into production
best_model.fit(X, y)

# and then save the model into a pickle file   

Explanation of method 1
You don't need to do gcv.fit(). We have X_train, y_train, X_test, and y_test. Forget about X_test and y_test.
1.) First X_train and y_train are passed to cross_val_score which splits X_train into X_train1 and X_test1. Same for y_train (y_train1 and y_test1).
2.) X_test1 and y_test1 will be held back and X_train1 and y_train1 will be passed onto gcv for fit.
3.) Here X_train1 is further split into X_train2 and X_test2 in the gridsearch using inner_cv. Same for y_train1 (y_train2 and y_test2).
4.) Now the gridsearch estimator will be trained using X_train2 and y_train2 and scored using X_test2 and y_test2.
5.) Steps 3.) and 4.) will be repeated for inner_cv (3 in this case).
6.) The best HP will then be passed onto gcv.best_estimator_ and fitted for X_train1 and y_train1.
7.) This gcv.best_estimator_ is then scored using test_x1 and test_y1
8.) Steps 1.) to 7.) will then be repeated for outer_cv (5 in this case).
9.) We then get the nested_score.mean() and nested_score.std() as our final results based on which we will select out model.
10.) Next we again run a gridsearchCV on X_train and y_train to get the best HP on whole dataset.
11.) Finally using the best HP obtained from 10.), we fit the model on X_train and y_train and evaluate using X_test and y_test. And then for the final model which will go into production, we fit the model onto X and y.
Method 2: Perform Nested CV for single algorithm and it's hyperparameters:-
from sklearn.datasets import load_iris
from matplotlib import pyplot as plt
from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV, cross_val_score, KFold, train_test_split
import numpy as np

# Load the dataset
iris = load_iris()
X_iris = iris.data
y_iris = iris.target

train_x, test_x, train_y ,test_y = train_test_split(X_iris, y_iris, test_size = 0.2, random_state = 69)

# Set up possible values of parameters to optimize over
p_grid = {"C": [1, 10], "gamma": [0.01, 0.1]}

# We will use a Support Vector Classifier with "rbf" kernel
svm = SVC(kernel="rbf")

# Choose cross-validation techniques for the inner and outer loops,
# independently of the dataset.
# E.g "GroupKFold", "LeaveOneOut", "LeaveOneGroupOut", etc.
inner_cv = KFold(n_splits=4, shuffle=True, random_state=69)
outer_cv = KFold(n_splits=4, shuffle=True, random_state=69)
    
# Nested CV with parameter optimization
clf = GridSearchCV(estimator=svm, param_grid=p_grid, cv=inner_cv)
clf.fit(train_x, train_y)
nested_score = cross_val_score(clf, X=X_iris, y=y_iris, cv=outer_cv)
        
nested_scores_mean = nested_score.mean()
nested_scores_std = nested_score.std()

 A: 
... I use train and test sets for building and testing my model (this
includes all the preprocessing steps and nested cv) and use the valid
set to test my final model.

Test set is typically used as final evaluation and validation set for tuning.  So, I'll be using the general convention below.

Do we use Nested Cross validation to tune the hyperparameters during
the cross validation process or do we first select the best performing
algorithm via cross validation and then tune the hyperparameter for
only that algorithm?

You shouldn't compare models without tuning them. One way to do is nested cross validation where we have two levels of validation sets, i.e. train_inner + validation_inner + validation_outer. Each algorithm's hyperparameters (HP) are tuned on validation_inner. Then, in the outer loop, each algorithm with its best HP set is trained on train_inner + validation_inner, which is train_outer, and tested on validation_outer. If this is CV, the sets of best HPs change in each outer loop evaluation, but in the end the two algorithms are compared. The winner algorithm will be tuned on train_outer and tuned validation_outer.
Finally, the best model with its best HP is trained on train_outer + validation_outer, which we can call train, and it's tested on a test set  for last performance report.
One other way would be linearizing everything to a model list, e.g.
models = [RF(n_est=10), RF(n_est=100), SVM(C=1), SVM(C=10)]

and selecting the best among them using a single validation level, without nesting. This may be desirable when compute time is a concern since nested CV takes more time and resources.
About your Method 1, you shouldn't tune your HP and test your success on the same set:
clf = GridSearchCV(model, ...)
clf.fit(X_train, y_train)
score = cross_val_score(clf, X_train, y_train, ...)

This is an optimistic view on the success of the tuned model since it's being measured on the test it was tuned.
About your Method 2, the nested_score should be calculated solely on the test set, not X_iris, which the full dataset. Because, it also contains the training set.
None of the implementations you shared conforms with the methods I explained above.
A paper that explains both methods I proposed and favours the second one (calls it as flat cv): https://arxiv.org/pdf/1809.09446.pdf
