title: Why is training a random forest regressor with MAE criterion so slow compared to MSE?
body: <p>When training on even small applications (&lt;50K rows &lt;50 columns) using the mean absolute error criterion for sklearn's RandomForestRegress is nearly 10x slower than using mean squared error. To illustrate even on a small data set:</p>
  
  <pre><code>import time
  from sklearn.ensemble import RandomForestRegressor
  from sklearn.datasets import load_boston
  
  X, y = load_boston(return_X_y=True)
  
  def fit_rf_criteria(criterion, X=X, y=y):
      reg = RandomForestRegressor(n_estimators=100,
                                  criterion=criterion,
                                  n_jobs=-1,
                                  random_state=1)
      start = time.time()
      reg.fit(X, y)
      end = time.time()
      print(end - start)
  
  fit_rf_criteria('mse')  # 0.13266682624816895
  fit_rf_criteria('mae')  # 1.26043701171875
  </code></pre>
  
  <p>Why does using the 'mae' criterion take so long for training a RandomForestRegressor? I want to optimize MAE for larger applications, but find the speed of the RandomForestRegressor tuned to this criterion prohibitively slow.</p>