Book contents
Contents
raw Math
RAW Book Optimization Gradient Methods

Introduction to Gradient Descent

Robert Eisele

Gradient descent is a first-order method for minimizing differentiable objective functions. From an initial point \(\mathbf{x}_0\), it repeatedly moves along the negative gradient, which is the direction of steepest local decrease.

The method is foundational in numerical optimization and machine learning, where high-dimensional parameter vectors are fitted by minimizing a loss.

Optimization Objective

For a differentiable objective \(f: \mathbb{R}^d \to \mathbb{R}\), the target is

\[ \mathbf{x}^* = \arg\min_{\mathbf{x} \in \mathbb{R}^d} f(\mathbf{x}). \]

With step size \(\lambda_k > 0\), the gradient-descent iterate is

\[ \mathbf{x}_{k+1}=\mathbf{x}_k-\lambda_k\nabla f(\mathbf{x}_k). \]

In one dimension this reduces to

\[ x_{k+1}=x_k-\lambda_k f'(x_k). \]

Why the Negative Gradient?

The first-order model around \(\mathbf{x}\) is

\[ f(\mathbf{x}+\Delta)\approx f(\mathbf{x})+\nabla f(\mathbf{x})^{\mathsf T}\Delta. \]

For a fixed step norm \(\|\Delta\|\), the linear term is minimized when \(\Delta\) is antiparallel to \(\nabla f(\mathbf{x})\). This yields the update direction \(-\nabla f(\mathbf{x})\).

A geometric view of this tangent-based descent is shown below.

Relation to Newton's Method

Gradient descent uses first-order information only. Newton's method adds second-order curvature via the Hessian, often improving local convergence at higher per-step cost.

In one dimension:

\[ x_{k+1}^{\text{GD}} = x_k - \lambda f'(x_k), \qquad x_{k+1}^{\text{Newton}} = x_k - \frac{f'(x_k)}{f''(x_k)}. \]

A detailed derivation is available in Introduction to Newton's Method.

Learning Rate and Stability

Step-size choice controls speed and stability:

For \(f\) with \(L\)-Lipschitz gradient, the descent lemma gives

\[ f(\mathbf{x}_{k+1}) \le f(\mathbf{x}_k)-\left(\lambda_k-\frac{L}{2}\lambda_k^2\right)\|\nabla f(\mathbf{x}_k)\|^2. \]

Hence every step is objective-decreasing for \(0<\lambda_k<2/L\), and a common robust choice is \(\lambda_k\le 1/L\).

A simple practical safeguard is backtracking: reduce \(\lambda\) (for example, by halving) whenever a trial step increases the objective.

One-Dimensional Convergence Example

For \(f(x)=x^2\), the iteration becomes

\[ x_{k+1}=x_k-2\lambda x_k=(1-2\lambda)x_k. \]

Therefore

\[ x_k=(1-2\lambda)^k x_0. \]

Convergence to \(0\) occurs iff \(|1-2\lambda|<1\), i.e. \(0<\lambda<1\). This explains the three typical regimes in the plots: slow, effective, and unstable.

Stopping Criteria

Common termination rules are:

Variants and Practical Extensions

Stochastic Gradient Descent

In empirical risk minimization, \(f(\theta)=\frac{1}{N}\sum_{i=1}^{N}\ell_i(\theta)\), full gradients can be expensive. SGD replaces the full gradient by a random sample estimate, reducing per-step cost but increasing variance.

Mini-batch SGD averages a subset and is usually the best compromise between throughput and noise reduction.

Machine Learning Context (Backpropagation)

In neural network training, backpropagation computes \(\nabla L(\boldsymbol{\theta})\) for parameters \(\boldsymbol{\theta}\), and the update is

\[ \boldsymbol{\theta}_{k+1} = \boldsymbol{\theta}_k - \alpha\,\nabla L(\boldsymbol{\theta}_k), \]

with learning rate \(\alpha\). This is exactly gradient descent applied in a high-dimensional parameter space.

Coordinate-wise Step Sizes

A diagonal preconditioning view uses per-coordinate step sizes \(\boldsymbol{\lambda}\):

\[ \mathbf{x}_{k+1}=\mathbf{x}_k-\boldsymbol{\lambda}\circ\nabla f(\mathbf{x}_k), \]

where \(\circ\) is the Hadamard product. Adaptive optimizers such as AdaGrad, RMSProp, and Adam can be interpreted as dynamic, data-driven versions of this idea.

JavaScript Example with Backtracking Guard

// Minimize f(x) = x^2 by gradient descent
function f(x) {
  return x * x;
}

function df(x) {
  return 2 * x;
}

let learningRate = 0.1;
const precision = 1e-10;
let iterations = 1000;

let x = 4.3;
let y = f(x);

while (iterations-- > 0) {
  const xNext = x - learningRate * df(x);
  const yNext = f(xNext);

  // If the step increased f, shrink the learning rate.
  if (yNext > y) {
    learningRate /= 2;
    continue;
  }

  if (Math.abs(xNext - x) <= precision) {
    break;
  }

  x = xNext;
  y = yNext;
}

console.log("Minimum x value:", x);
console.log("Minimum f(x) value:", f(x));

References

Related Stuff

raw / Numerical Analysis
22 Sep
·
Robert Eisele

Introduction to Newton's Method

Newton's method is developed from tangent-line and Taylor viewpoints to solve nonlinear equations iteratively. It derives the root update and related formulas for square roots, inverse square roots, and n-th roots, then extends the method to optimization in one and multiple dimensions via gradient and Hessian-based updates. It further covers Newton-type methods more broadly: convergence rates, damped Newton steps, variable-metric methods, quasi-Newton methods and BFGS, Gauss-Newton and Levenberg-Marquardt, and inexact Newton-Krylov methods, with a dedicated chapter developing Gauss-Newton in full depth.
raw / Optimization
02 Aug
·
Robert Eisele

Introduction to the Gauss-Newton Method

The Gauss-Newton method is developed as Newton's method applied to a sum-of-squared-residuals objective, building directly on the quadratic Taylor model, gradient, and Hessian introduced for Newton's method. It derives the gradient and Hessian of the least-squares objective, motivates dropping the residual-curvature term to obtain the Gauss-Newton system, and shows the equivalent, more intuitive derivation as linearizing the residuals and solving an ordinary linear-regression subproblem at each step. The single-residual case is shown to reduce exactly to Newton-Raphson root finding, followed by a fully worked numerical example fitting an exponential decay, the algorithm in pseudocode, the Levenberg-Marquardt damping scheme and its connection to gradient descent, and a discussion of when the method works well or fails.
raw / Machine Learning
03 Dec
·
Robert Eisele

Introduction to Regression

This develops linear regression from the ground up: the error term, the sum-of-squared-errors loss function, and the closed-form least-squares solution for the slope and intercept, worked through step by step by hand. It covers the correlation coefficient and coefficient of determination as goodness-of-fit measures, with a proof that R² is exactly the share of variance explained, then discusses regression toward the mean and partial correlation before generalizing to multiple linear regression via the normal equation and Gramian matrix. Anscombe's Quartet illustrates why summary statistics alone are not enough. The chapter continues with batch gradient descent as an iterative alternative for large feature counts, extends to polynomial regression through feature maps, introduces ridge regression for ill-conditioned problems, and closes with common pitfalls of least-squares fitting.
All Math