Is training a tree faster with squared-error loss as compared to other losses? I am reading through various introductions to decision trees and boosting algorithms. It strikes me that people always like to resort to squared-error loss whenever a tree needs to be trained. For example, gradient boosting allows any loss function to be minimized but operationally it only trains trees with squared-error loss (when fitting trees to gradients).
So I am wondering whether training a tree is simpler with a squared-error loss as compared to other loss functions? I have been trying to find an answer in various books but have found no explicit answer. My guess is that under the squared-error loss, there is some shortcut for finding the split point (Basically, you only need to make the means of the two split leaves as far apart as possible).
With a general loss function (e.g., binomial), there seems to be no similar trick to find the optimal split.
Can someone confirm this or point me to a different reason?
 A: My (limited) understanding is that you can make finding the best-variance split into an $O\left( N \right)$ operation.
Note: You are asking about variance, which applies to continuous variables, and not something like gini score (aka not gini coefficient) which is used for categorical ones.
Setup:
Lets say you have a the following case:
library(pracma)
library(ggplot2)
set.seed(1)
x <- linspace(x1=0,x2=1,n=101)
y <- rep.int(x = 1, times = 101)
y[50:101] <- 2
y <- y + rnorm(n = 101, mean = 0, sd = 0.1)
df <- data.frame(x=x, y=y)
ggplot(df, aes(x=x,y=y)) + geom_point() +geom_path()

aka

The eyeball says "split at x=0.5".  It is a toy, not 1000 dimensions, or 1M rows.
The classic way:
To compute the group variance we need to first compute the mean by $N$ additions, lets assume we have a decent memory structure so we don't have to increment rows, then we need a divide at the end.  We then subtract the mean from each element and square it for an additional $2N$ times and at the end divide again.  This gives $3N+2$ operations to get the total variance.  If we perform $N$ operations for $N$ times it is an $O\left( N^2 \right)$ total operations.
An alternative form:
The windowed mean, also known as rolling subgroup mean, can be made to look like EWMA.
$$ \mu_{N} = \frac{1}{N} \sum_{i=1}^{N}{x_i} $$
$$ \mu_{N} =  \frac{1}{N} \sum_{i=1}^{N-1}{x_i} + \frac{1}{N} x_{N}$$
$$ \mu_{N} = \frac{N-1}{N} \frac{1}{N-1}\sum_{i=1}^{N-1}{x_i} + \frac{1}{N} x_{N}$$
$$ \mu_{N} = \frac{N-1}{N} \mu_{N-1} + \frac{1}{N} x_{N}$$
$$ \mu_{N} = \left(1-\alpha \right) \cdot \mu_{N-1} + \alpha \cdot x_{N}$$
Similarly with the variance.  Feel free to work out how the running variance is computed using a running mean.
This means we can compute the change in variance of the split by having a pair of rolling windows, one at the start and one at the end, so for about $8N$ which is $ O\left(N \right)$.
Applying it:
Here is a graphical example of it:
N <- nrow(df)
var_all <- var(y)

store1 <- numeric(length = N);store2 <- numeric(length = N);store3 <- numeric(length = N)

mu1  <- y[1]
var1 <- 0.5*var(y[1:2])

for(i in 2:N){
  
  #first mean
  mu1  <- ((i-1)/i)*mu1 + (1/i)*y[i]
  var1 <- ((i-1)/i)*var1 + (1/i)*(y[i]-mu1)^2
  
  store1[i] <- var1
  store2[i] <- var(y[i:N])
  
}

store2[1] <- var_all
store1[N] <- var_all
store2[N] <- store1[1]

df2 <- data.frame(x=x,y=y, 
                  v1=store1, v2=store2)

ggplot(df2, aes(x=x)) + 
  geom_path(aes(y=v1), color="Red")+
  geom_path(aes(y=v2), color="Blue") +
  geom_path(aes(y=v1+v2), color="darkgreen", size=1)+
  ylab("Variance") +
  xlab("Split location")

Which yields this:

You can see the very clear minimum variance in the middle.
A challenge for you, replace the "var" part of "store2[i] <- var(y[i:N])" with the rolling mean and variance, and get the same plot. Hint: it will require its own for loop, and be careful about start/end conditions.
