Choosing best model produced from different algorithms. Metric produced by cross-validation on the train set or metric produced on the test set?

I know that choosing between models produced by one algorithm with different hyperparameters the metric for choosing the best one should be the cross-validation on train set.

But what about choosing between models that are produced by different algorithm? By which metric should I compare them, the metric produced by cross-validation on the train set or metric produced on the test set? Also why?

When you are comparing different algorithms, you strictly use the test set to compare performance. That is, you retrain all of your candidate models using your entire train set (using cross-validation or whatever) and make predictions on the test set, from which you can assess model performance. These scores are the only unbiased measures of predictive performance that you have.

The reason why we compare scores based on the completely unseen test set, and not the training set, is to avoid optimization bias during the hyperparameter tuning step. Basically, there is a very large probability that you selected a hyperparameter combination that is overfitting the training set during your cross-validation. A relatively famous paper explores this phenomenon in detail. The result is that the scores you found when optimizing your hyperparameters are optimistically biased.

Your main question seems to be what about different algorithms?, and the answer to that is it makes no difference.

While hard to argue with the "test set" answer logic it is also easy to find a counter-example. If your training set has 100K examples, and you used, say 5-fold CV, and then you also have a test set with only 200 examples... the test set is 100x smaller and likely to be much less reliable.

Normally you would use cross-validation, or a test set. And if your training data is large, I would generally recommend just using a test set, because you probably have enough data and because CV takes longer to train. When training data is scarce, cross-validation makes more sense: training time probably matters less, you want to train the final model on everything you have, and also you will value the N different opinions that N-fold CV gives you, because your sample size is small.

If you have used both cross-validation and a test set for multiple models (whether same algorithm or different algorithms), then you should expect them both to agree on your choice of best model. If model A does better than model B on cross-validation, but model B does better on the test data, then you should go looking for a problem.

If that does happen, I'd first be suspicious that the test data is not representative. E.g. to exaggerate, your training data covers the period 1950 to 1970, and your test data is for the year 2020. At the other extreme, I'd check that the test data is not actually in your training data (implying that model B does a better job of memorizing).