Gradient descent

Gradient descent is “a first-order iterative algorithm for minimizing a differentiable multivariate function” — the canonical gradient-based optimizer, and the deliberate counterpoint to this wiki’s gradient-free metaheuristics (the gap the synthesis open questions named). Source: Wikipedia.

How it works

Step opposite the gradient: xₙ₊₁ = xₙ − η∇f(xₙ) — “repeated steps in the opposite direction of the gradient.” The learning rate η is the knob: “too small … slow convergence … too large … overshoot and divergence” (tuned by line search / backtracking). Requires a differentiable objective and converges only to a local minimum.

Provenance and convergence rates

The method is old: “generally attributed to Augustin-Louis Cauchy, who first suggested it in 1847” wikipedia-gradient-descent, with a similar idea from Hadamard (1907) and convergence first studied by Haskell Curry (1944). On convex, Lipschitz-smooth functions plain gradient descent achieves O(1/k) error; Nesterov acceleration sharpens this to O(1/k²), which is optimal for first-order methods wikipedia-gradient-descent. The catch is conditioning — iteration count runs “proportional to the spectral condition number κ(A),” and ill-conditioning carves “a characteristic zig–zag path.” Two classic fixes: the Barzilai–Borwein step (set from successive iterate/gradient differences) and the heavy-ball / momentum method, which on quadratics matches conjugate-gradient rates. These rate guarantees are exactly the kind of structural certainty the black-box metaheuristics trade away.

Why it matters here — the other half of optimization

It inverts every assumption of the founding corpus: it uses derivatives (metaheuristics are black-box), it’s exploitation-only (no population, no exploration), and it gives no global guarantee off-convexity. The no-free-lunch-theorem cuts both ways: where gradients exist and the landscape is benign, gradient descent crushes any metaheuristic on speed; where it’s black-box/non-differentiable/multimodal, the metaheuristics earn their keep. The workhorse of ML training (see stochastic-gradient-descent).

Related

stochastic-gradient-descent · convex-optimization · metaheuristic-optimization · exploration-vs-exploitation · no-free-lunch-theorem · bayesian-optimization · wikipedia-gradient-descent