Где именно возникает градиент в алгоритме градиентного бустинга, если базовый алгоритм — обычное дерево решений?

Градиент вычисляется у функции потерь по текущим предсказаниям ансамбля, а не по порогам дерева. Новое дерево приближает направление уменьшения ошибки.

На шаге m для каждого объекта вычисляют псевдоостаток r_i = -∂L(y_i, F(x_i))/∂F(x_i). Затем обучают дерево предсказывать эти значения и добавляют его к ансамблю с коэффициентом learning rate.

Для половины квадратичной ошибки псевдоостаток равен y_i − F(x_i). Для других loss он отличается от обычного остатка. Дерево не обязано быть дифференцируемым по своим разбиениям: оно приближает значения градиента на обучающих объектах. Некоторые реализации дополнительно используют вторые производные.

Источник: scikit-learn.org.