0
$\begingroup$

What is the difference between gradient descent and gradient boosting? Are they interdependent on each other in any way ?

$\endgroup$
2
$\begingroup$

They're two different algorithms, but there is some connection between them:

Gradient descent is an algorithm for finding a set of parameters that optimizes a loss function. Given a loss function $f(x, \phi)$, where $x$ is an n-dimensional vector and $\phi$ is a set of parameters, gradient descent operates by computing the gradient of $f$ with respect to $\phi$. It then "descends" the gradient by nudging the parameters in the opposite direction of the gradient. This process is repeated for different points in the space of inputs (i.e. different $x$s) until a minimum of $f$ is found.

Gradient boosting is a technique for building an ensemble of weak models such that the predictions of the ensemble minimize a loss function. I think the Wikipedia article on gradient boosting explains the connection to gradient descent really well:

. . . boosting algorithms [are] iterative functional gradient descent algorithms. That is, algorithms that optimize a cost function over function space by iteratively choosing a function (weak hypothesis) that points in the negative gradient direction.

So the connection is this: Both algorithms descend the gradient of a differentiable loss function. Gradient descent "descends" the gradient by introducing changes to parameters, whereas gradient boosting descends the gradient by introducing new models.

$\endgroup$
0
$\begingroup$

In my view, they are superficially related at best. In gradient descent, you stipulate some $f(x;\theta)$, where $x$ are the features of your data, which minimises some loss function $L = \sum_{i=1}^{N}\ell (y_{i}, f(x_{i};\theta)$. In order to find the $\theta$ which minimise this loss function, we calculate the gradient $\nabla _{\theta}L$, and move against that direction in $\theta$ space.

In gradient boosting, as far as I can tell, there are two parts which you can think of in terms of gradient (and they're both different to gradient descent).

Firstly, in gradient boosting, you make the choice the not fit your function too heavily (in terms of gradient boosted tree algorithms, this usually means to train a shallow tree), so that you don't overfit, and then, in order to improve upon that classifier, you fit a new classifier whose aim it is to improve on the loss of the first. You can think of this as fitting your second classifier to the functional gradient rather than the function, and then updating your classifier like $f(x) = f_{1}(x) +\delta f(x)$.

Secondly, the above described process usually involves, for fixed $f_{1}$, trying, within each node of the tree (in this example, let's look at the $k^{th}$ node), to find the constant $w_{k}$ which minimises the loss of that node, $L_{k}$, given by

$$\sum_{i \in R_{k}}\ell (y_{i}, f_{1}(x_{i}) + w_{k})$$

Because you have to do this calculation this for every node, for every (or at least many) different possible partitionings of the space, minimising the above term wrt $w_{k}$ needs to be something one can do quickly, but usually one would need to solve this numerically. Consequently, it is conventional (certainly in xgboost), to Taylor expand (hence gradients) the above to second order in $w_{K}$, which means one can then solve the equation in closed form.

In summary:

In gradient descent, the reason for calculating gradients and updating $\theta$ accordingly, is in order to optimise training loss.

In gradient boosting, one intentionally fits a weak classifier/simple function to the data, and then in turn another simple function to the functional derivative of the loss function w.r.t to the classifier. In each case, one could choose to optimise training loss more if one wanted to, but one does not, in order to avoid over-fitting.

Also, there are some implementational details/tricks in xgboost which require gradient expansions of the loss function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.