Gradient Descent and Optimisation

The Mathematical Principle of Gradient Descent

Gradient descent

The goal: to find the minimum of a differentiable function f:Rn→Rf: \mathbb{R}^n \to \mathbb{R}.

The iteration formula:

x⃗k+1=x⃗k−αk∇f(x⃗k)\vec{x}_{k+1} = \vec{x}_k - \alpha_k \nabla f(\vec{x}_k)

where:

  • x⃗k\vec{x}_k is the iterate of the kk-th step
  • αk>0\alpha_k > 0 is the learning rate (the step size)
  • ∇f(x⃗k)\nabla f(\vec{x}_k) is the gradient; the minus sign means the update is made in the direction opposite to the gradient

The core idea: the gradient direction is the direction in which the value of the function grows fastest, so the negative gradient direction is the direction in which it decreases fastest (the direction of steepest descent).

The Analysis of Convergence

Theorem1

Suppose ff is an LL-smooth convex function (the gradient is LL-Lipschitz continuous, that is, ∣∣∇f(x)−∇f(y)∣∣≤L∣∣x−y∣∣||\nabla f(x)-\nabla f(y)|| \leq L||x-y||). With a fixed learning rate α∈(0,1L)\alpha \in (0, \frac{1}{L}), gradient descent satisfies:

f(x⃗k)−f∗≤∣∣x⃗0−x⃗∗∣∣22αkf(\vec{x}_k) - f^* \leq \frac{||\vec{x}_0 - \vec{x}^*||^2}{2\alpha k}

that is, the rate of convergence is O(1k)O(\frac{1}{k}) (sublinear convergence).

If ff is also μ\mu-strongly convex (∇2f⪰μI\nabla^2 f \succeq \mu I), then the rate of convergence is linear:

∣∣x⃗k−x⃗∗∣∣2≤(1−μL)k∣∣x⃗0−x⃗∗∣∣2||\vec{x}_k - \vec{x}^*||^2 \leq \left(1 - \frac{\mu}{L}\right)^k ||\vec{x}_0 - \vec{x}^*||^2

where κ=Lμ\kappa = \frac{L}{\mu} is called the condition number; the larger the condition number, the slower the convergence.

Exact line search and inexact line search

Exact line search: at each step the optimal step size is chosen

αk=arg⁡min⁡α>0f(x⃗k−α∇f(x⃗k))\alpha_k = \arg\min_{\alpha > 0} f(\vec{x}_k - \alpha \nabla f(\vec{x}_k))

Inexact line search: one only requires a sufficient decrease in the value of the function; the Armijo condition is the common choice:

f(x⃗k−α∇f(x⃗k))≤f(x⃗k)−cα∣∣∇f(x⃗k)∣∣2f(\vec{x}_k - \alpha \nabla f(\vec{x}_k)) \leq f(\vec{x}_k) - c\alpha ||\nabla f(\vec{x}_k)||^2

where c∈(0,1)c \in (0,1) is a constant. Inexact line search involves much less computation and is the mainstream choice in practice.

The Variants of Gradient Descent

Stochastic Gradient Descent (SGD)

Stochastic gradient descent

When the objective function is the sum of the losses of a large number of samples f(x)=1N∑i=1Nfi(x)f(x) = \frac{1}{N}\sum_{i=1}^N f_i(x), each iteration uses the gradient of only one sample (or a small batch) to approximate the full gradient:

x⃗k+1=x⃗k−α∇fik(x⃗k)\vec{x}_{k+1} = \vec{x}_k - \alpha \nabla f_{i_k}(\vec{x}_k)

Advantages: fast to compute and suited to large data. Disadvantages: the gradient is noisy, so the convergence oscillates. Mini-batch SGD is a compromise, computing the gradient from a batch of samples at each step.

Momentum

Momentum

v⃗k+1=βv⃗k+∇f(x⃗k)\vec{v}_{k+1} = \beta \vec{v}_k + \nabla f(\vec{x}_k) x⃗k+1=x⃗k−αv⃗k+1\vec{x}_{k+1} = \vec{x}_k - \alpha \vec{v}_{k+1}

where β∈[0,1)\beta \in [0,1) is the momentum coefficient (usually 0.9). Momentum accumulates the history of the gradients, which accelerates the convergence and reduces oscillation, and it is particularly suited to ill-conditioned problems.

Adam (Adaptive Moment Estimation)

The Adam algorithm

mk=β1mk−1+(1−β1)∇f(xk)m_k = \beta_1 m_{k-1} + (1-\beta_1)\nabla f(x_k) vk=β2vk−1+(1−β2)(∇f(xk))2v_k = \beta_2 v_{k-1} + (1-\beta_2)(\nabla f(x_k))^2 m^k=mk1−β1k,v^k=vk1−β2k\hat{m}_k = \frac{m_k}{1-\beta_1^k}, \quad \hat{v}_k = \frac{v_k}{1-\beta_2^k} xk+1=xk−αv^k+εm^kx_{k+1} = x_k - \frac{\alpha}{\sqrt{\hat{v}_k} + \varepsilon}\hat{m}_k

The default parameters are β1=0.9,β2=0.999,ε=10−8\beta_1=0.9, \beta_2=0.999, \varepsilon=10^{-8}. Adam combines momentum with an adaptive learning rate, and it is one of the most commonly used optimisers in deep learning.

Worked Examples

Example 1: Gradient Descent on a Quadratic Function

Use gradient descent to find the minimum of f(x,y)=x2+2y2f(x,y) = x^2 + 2y^2, starting from (1,1)(1,1) with a learning rate α=0.1\alpha=0.1, and write down the first three iterations and analyse the convergence.

gradient descenta quadratic functionconvergence

Approach:

The core action of gradient descent is “move a fixed step along the negative gradient direction”, so first write down the gradient and then iterate; and to discuss the convergence, put the relation between the largest eigenvalue of the Hessian and the learning rate on the table.

Steps:

  1. ∇f=(2x,4y)\nabla f = (2x, 4y)
  2. The start: x0=(1,1)x_0=(1,1) and f(x0)=3f(x_0)=3
  3. Step 1: x1=(1,1)−0.1(2,4)=(0.8,0.6)x_1 = (1,1) - 0.1(2,4) = (0.8, 0.6) and f=0.64+0.72=1.36f=0.64+0.72=1.36
  4. Step 2: x2=(0.8,0.6)−0.1(1.6,2.4)=(0.64,0.36)x_2 = (0.8,0.6) - 0.1(1.6,2.4) = (0.64, 0.36) and f=0.4096+0.2592=0.6688f=0.4096+0.2592=0.6688
  5. Step 3: x3=(0.64,0.36)−0.1(1.28,1.44)=(0.512,0.216)x_3 = (0.64,0.36) - 0.1(1.28,1.44) = (0.512, 0.216) and f=0.2621+0.0933=0.3554f=0.2621+0.0933=0.3554
  6. Convergence: L=4L=4 (the largest eigenvalue) and α=0.1<1L=0.25\alpha=0.1 < \frac{1}{L}=0.25, so the condition for convergence is satisfied. The convergence factor in the xx direction is 1−2α=0.81-2\alpha=0.8 and in the yy direction 1−4α=0.61-4\alpha=0.6, so the yy direction converges faster.

Answer: over the first three steps the function value falls from 3 to 0.3554, converging step by step to the minimum point (0,0)(0,0).

For f(x,y)=x2+2y2f(x,y) = x^2 + 2y^2, starting from (1,1)(1,1), use an exact line search to find the optimal step size of the first step.

exact line searchsteepest descenta quadratic function

Approach:

Exact line search treats the objective function along the search direction as a function of one variable and finds the optimal step size, so the key is to fix the direction first and then differentiate with respect to the step size and set it to zero.

Steps:

  1. The search direction d=−∇f(1,1)=(−2,−4)d = -\nabla f(1,1) = (-2,-4)
  2. f((1,1)+α(−2,−4))=(1−2α)2+2(1−4α)2f((1,1) + \alpha(-2,-4)) = (1-2\alpha)^2 + 2(1-4\alpha)^2
  3. =1−4α+4α2+2(1−8α+16α2)=3−20α+36α2= 1-4\alpha+4\alpha^2 + 2(1-8\alpha+16\alpha^2) = 3-20\alpha+36\alpha^2
  4. Differentiating with respect to α\alpha: −20+72α=0-20+72\alpha=0, so α=2072=518≈0.278\alpha = \frac{20}{72} = \frac{5}{18} \approx 0.278
  5. The next point: (1−1018,1−2018)=(49,−19)(1-\frac{10}{18}, 1-\frac{20}{18}) = (\frac{4}{9}, -\frac{1}{9})

Answer: the optimal step size is α=518\alpha = \frac{5}{18}, and the next point is (49,−19)(\frac{4}{9}, -\frac{1}{9}).


Exercises

Exercise 1

Use gradient descent to find the minimum of f(x,y)=x2+4y2f(x,y) = x^2 + 4y^2, starting from (2,1)(2, 1) with a learning rate α=0.1\alpha=0.1, and write down the first three iterations.

gradient descentiterationa quadratic function

Approach:

The same procedure as in the examples: write the gradient, then iterate.

Steps:

  1. ∇f=(2x,8y)\nabla f = (2x, 8y)
  2. The start x0=(2,1)x_0=(2,1) and f(x0)=4+4=8f(x_0)=4+4=8
  3. Step 1: x1=(2,1)−0.1(4,8)=(1.6,0.2)x_1 = (2,1) - 0.1(4,8) = (1.6, 0.2) and f=2.56+0.16=2.72f=2.56+0.16=2.72
  4. Step 2: x2=(1.6,0.2)−0.1(3.2,1.6)=(1.28,0.04)x_2 = (1.6,0.2) - 0.1(3.2,1.6) = (1.28, 0.04) and f=1.6384+0.0064=1.6448f=1.6384+0.0064=1.6448
  5. Step 3: x3=(1.28,0.04)−0.1(2.56,0.32)=(1.024,0.008)x_3 = (1.28,0.04) - 0.1(2.56,0.32) = (1.024, 0.008) and f=1.048576+0.000256=1.048832f=1.048576+0.000256=1.048832

Answer: the three iterations are x1=(1.6,0.2)x_1=(1.6,0.2), x2=(1.28,0.04)x_2=(1.28,0.04) and x3=(1.024,0.008)x_3=(1.024,0.008), with the function value falling from 8 to 1.0488.

Exercise 2

Explain why the learning rate must satisfy α<1L\alpha < \frac{1}{L} for gradient descent to converge on an LL-smooth function.

the learning rateconvergencethe Hessiana proof

Approach:

Look at the iteration in one dimension, where the update is the scalar xk+1=xk−αf′(xk)x_{k+1} = x_k - \alpha f'(x_k), and examine when this linear iteration diverges.

Steps:

  1. In one dimension, xk+1=xk−αf′(xk)x_{k+1} = x_k - \alpha f'(x_k); near a minimum x∗x^* we have f′(x)≈f′′(x∗)(x−x∗)f'(x) \approx f''(x^*)(x-x^*), and f′′(x∗)≤Lf''(x^*) \leq L
  2. Hence xk+1−x∗≈(1−αf′′(x∗))(xk−x∗)x_{k+1} - x^* \approx (1 - \alpha f''(x^*))(x_k - x^*)
  3. The iteration converges if and only if ∣1−αf′′(x∗)∣<1|1 - \alpha f''(x^*)| < 1, that is, 0<α<2f′′(x∗)0 < \alpha < \frac{2}{f''(x^*)}
  4. Since f′′(x∗)≤Lf''(x^*) \leq L, the condition α<1L≤2f′′(x∗)\alpha < \frac{1}{L} \leq \frac{2}{f''(x^*)} guarantees convergence in every direction
  5. If α>2L\alpha > \frac{2}{L}, then in the direction where f′′f'' is close to LL we have ∣1−αf′′∣>1|1-\alpha f''| > 1, and the iteration diverges (it oscillates with growing amplitude).

Answer: the condition α<1L\alpha < \frac{1}{L} guarantees that the contraction factor ∣1−αf′′(x∗)∣|1-\alpha f''(x^*)| is less than 1 in every direction, so the iteration converges; a learning rate that is too large makes the iteration diverge.


Summary

Symbols Used in This Article

SymbolTypePronunciation/ExplanationMeaning in This Article
α\alphaLearning ratelearning rateThe step size of gradient descent
x⃗k\vec{x}_kIterateiteration pointThe iterate of the kk-th step
v⃗k\vec{v}_kMomentumvelocity / momentumThe accumulated gradient in the momentum method
β\betaMomentum coefficientmomentum coefficientThe decay coefficient of the momentum method
LLLipschitz constantLipschitz constantThe Lipschitz constant of the gradient
μ\muStrong convexity parameterstrong convexityThe parameter of a strongly convex function
κ\kappaCondition numbercondition numberL/μL/\mu
mk,vkm_k, v_kAdam momentsmomentsThe first and second moments of the Adam algorithm
ε\varepsilonSmall constantepsilonThe small constant in Adam that prevents division by zero

Found an issue with this content?

Tell us what could be improved.