Select features first or optimize hyperparameters first? I want to train a binary classification model using some tree ensemble (either xgboost or random forests). My dataset has some 50 features, and I believe some of them are redundant (there's correlation between some features, among other things).
I am wondering what order should I perform the following two tasks


*

*Optimize hyperparameters for the tree ensemble (e.g. number of trees, tree depth etc.) via $k$-fold cross validation

*Recursive Feature Elimination: Fix hyperparameters and train a model. Remove features one at a time (after each model is trained) based on feature weights (lower weights => less importance). That is, train a model on $p$ features, remove feature $j$ with the lowest weight so now we have $p-1$ features, and repeat this until either i) the desired number of features are left or ii) the accuracy hits a lower threshold
What I am concerned about is if I remove features first and then optimize hyperparameters second, I may be loosing out on some complex feature + hyperparameter interactions. However if I do the converse, tune hyperparameters with all features, then remove features, I may end up with a dataset for which the hyperparameters we found are no longer optimal.
Is there a correct way / order to do this?
 A: 
Is there a correct way / order to do [two kind of hyperparameter optimization]?

Yes: unless you know for sure that the different hyperparameters do not interact, they should to be optimized together.
Here, they do interact => optimize together
You can also optimize sequentially, but that should then become an iterative procedure: 


*

*optimize one type of hyperparameter  

*optimize the other

*repeat until the two optimization steps do not yield changes any more.


And of course, that optimum may be only a local optimum.

Also, please read up on randomForest. A large part of your optimization is done already by rF, and some features (most prominently no. of trees) of rF behave differently wrt. optimization from what you may be thinking. 
A: For tree based model, it can automatically handle redundant features, i.e. less useful features will not be selected as a split point. So you do not need to manually handle feature selection problems.
In many implementations of random forest or tree based boosting, the algorithm will automatically select a subset of features to build each tree. Therefore, from computational complexity perspective, thousands features are fine (In your case you only have 50 features.) 
