Gradient descent objective and update rule

Summary

Gradient descent is a first-order iterative optimization method used to minimize a differentiable multivariable objective function. The core idea is to repeatedly move from the current parameter vector in the opposite direction of the gradient, because the negative gradient points in the direction of steepest local decrease. With a sufficiently small learning rate (step size) η, the update produces a non-increasing sequence of objective values, ideally converging to a local minimum. The step size may vary by iteration (ηn), and convergence can be guaranteed under additional assumptions on the objective (e.g., convexity and Lipschitz continuity of the gradient) and appropriate step-size choices (e.g., line search, Wolfe conditions, or Barzilai–Borwein-type rules). The standard update rule is: x_{n+1} = x_n − η_n ∇f(x_n). More generally, one can use a descent direction pn and update x_{n+1} = x_n − η_n pn, as long as pn has a positive alignment with the negative gradient (so the method still moves “downhill”). Choosing η too small slows progress, while choosing it too large can cause overshooting and divergence; therefore, practical methods often use line search or backtracking line search. When the objective is convex, all local minima are global minima, so gradient descent can converge to the global solution.

Key Points

• 1

  Gradient descent minimizes f by iteratively updating parameters in the negative gradient direction using a step size η.

• 2

  The basic update rule is x_{n+1} = x_n − η_n ∇f(x_n), with convergence depending on assumptions about f and the choice of η_n.

• 3

  More general updates x_{n+1} = x_n − η_n p_n work when p_n is sufficiently aligned with the negative gradient, and step-size selection is crucial to avoid divergence.