Cost of Finding the Best Split in a Regression Tree

MediumClassical ML

Reported in interviews at The Voleon Group

Problem statement

You are growing a regression (CART) tree. At a node you have $m$ samples and $p$ features, and you want to find the single best split: the feature and threshold that minimize the resulting L2 (sum-of-squared-error) loss of the two children.

  1. What is the complexity of a brute-force evaluation of all candidate splits at this node?
  1. Can you do better than re-summing the loss from scratch for every candidate threshold? What complexity does the improved method achieve?
Show hint

Treat the search as nested loops and ask what each loop level contributes to the cost.

Relevant roles: ML Engineer, Applied Scientist, Data Scientist and Research Scientist.

Related free problems