Gradient Descent

The gradient descent algorithm (gradient descent, GD, or steepest descent) updates the weights $\boldsymbol\beta$ at each iteration using the gradient (more precisely, the negative gradient) of the objective function $S(\boldsymbol\beta)$:

$$\boldsymbol\beta_{t+1} = \boldsymbol\beta_{t} - \gamma \nab... ..._{t} - \gamma \sum_{i=1}^{n} \nabla \ell_i(\boldsymbol\beta_t)$$ (4.37)

or, by defining the update step:

$$\boldsymbol\delta_t = - \gamma \sum_{i=1}^{n} \nabla \ell_i(\boldsymbol\beta_t)$$ (4.38)

where $\gamma$ is a suitably chosen optimization factor (called the learning rate in machine learning). Under suitable assumptions, if the starting point is sufficiently close to the solution and the value of $\gamma$ is sufficiently small, the achievable convergence rate is practically linear.

Since the parameter $\gamma$ is chosen manually, the approach is empirical and problem-dependent, if not dependent on the user's experience. Comparing equation (4.37) with equation (4.36), we observe that Newton's method is effectively a special case of gradient descent, in which the scalar parameter $\gamma$ is replaced by a positive-definite matrix $\boldsymbol\Gamma_t$, obtained as the inverse of the Hessian at the current point:

$$\boldsymbol\beta_{t+1} = \boldsymbol\beta_{t} - \boldsymbol\Gamma_t \nabla S(\boldsymbol\beta_t)$$ (4.39)

Second-order gradient descent therefore corresponds to Newton's algorithm, which—under suitable assumptions—guarantees quadratic convergence, in contrast to the linear convergence of classical gradient descent.