What fraction of the training set should I use? I tried to fit RandomForestClassifier with n_estimators=500 to the training dataset which has 600,000 instances and it's taking too long. I'm also planning to use RandomizedSearchCV. What fraction of the training data should I use for RandomizedSearchCV fitting to be finished in reasonable amount of time?
 A: No one can really answer that question without knowing the data. But since you have a lot of data, you should partition your data into 3 parts, use the first partition to find the best model parameters (tuning), use the second partition to train your model, and the third to test it. This should cut down the time by a third. If it's still too much consider taking a random subsample out of each partition.
A: Although I completely agree with user2974951, I might want to throw in some ideas to speed up the process without the need to code to much extra:
1) 500 trees is a whole lot. Start with smaller values like 50 and then increase it until you see that the classifier performance plateaus.
2) After taking care of the number of trees, this leaves the only important parameter to be the number of features used per tree in the forest (there are actually more as in spark for example, but those are not found in all implementations so i pass on them here). Since you are doing classification, start with sqrt(m) if m is the number of features. From there increase in little steps if you need higher performance or decrease if you are overfitting to much.
3) adding to user2974951's answer: i generally start with a 70%/30% split. The 70% you use for cross validation and in order to determine the hyperparameters talked above and 30% for evaluation. That reduces the number of training instances.
4) If the number of examples is very high given the number of features (see the one-in-ten rule ), you could also try to just do a train-validation split, which basically is a "1-fold-cross-validation" with  split-percentages which you specify. I had several occasions where all n folds of a cv returned nearly the same model performances. Take this hint with caution tho, since this is not always the case. 
