Implement a gradient boosting regressor over depth-1 regression stumps, without sklearn. Where bagging (#19) is "a majority vote of independent learners", this is sequential: each learner fills in the residual the previous one left behind. The most common boosting bug is getting the ordering — or the moment you update the residual — wrong.

Base learner: the regression stump

A depth-1 tree. Its best split is found by minimizing weighted SSE (sum of squared errors).

• Candidate thresholds: sort each feature's values, drop duplicates, take the midpoint of adjacent pairs
• Left = X[:, f] <= t, right = the rest
• Weighted SSE = $\sum_{i \in L}(y_i - \bar y_L)^2 + \sum_{i \in R}(y_i - \bar y_R)^2$
• On a tie: lower feature index → lower threshold
• Each side predicts the mean of its training rows
• If no split is possible (every feature has a single value), use the overall mean as the prediction for both sides
• Round the threshold to 6 decimal places

Boosting

model = GradientBoostingRegressor(n_estimators=10, lr=0.1)
model.fit(X, y)
pred = model.predict(X)      # a list of n floats

• base = mean(y) — computed once and never changed afterwards (the model's constant term).
• Start with the residual residual = y - base.
• Run rounds $m = 1..$n_estimators. Each round:
  1. Fit one regression stump to the current residual and store it.
  2. Update the residual: residual <- residual - lr * (the prediction of the stump you just fit).
• predict(X) = base + lr * (sum of every stump's prediction).

⚠️ Each round's stump is fit on the residual as it stands at that moment — not on the original y. And the residual update subtracts only the stump you just fit this round; it does not recompute the accumulated prediction. (The two are equivalent in the end, but confusing the update order makes the next round's stump see the wrong residual.)

If X and y are empty, set base = 0.0 and finish training with no stumps (no exception). predict in that state returns 0.0 for every input row.

Level structure

Each level must preserve the behavior of the previous ones.

Build the base learner first.

fit_reg_stump(X, y) -> (dict, float)

It returns a (stump, gain) tuple. stump is one of these two shapes.

{"feature": int, "threshold": float, "left": float, "right": float}
{"feature": None, "threshold": None, "left": m, "right": m}   # no split, m = overall mean

gain is the SSE the split removed: parent_sse - (left_sse + right_sse). When no split was possible, gain is 0.0.

• The split and tie rules match the shared spec (minimize weighted SSE; ties go to the lower feature index, then the lower threshold).
• Round the threshold to 6 decimal places.
• Each side predicts the mean of its rows.

predict_reg_stump(stump, X) -> list

• For each row, left when X[:, feature] <= threshold, otherwise right.
• When feature is None, return the left value for every row.