Gradient Descent and Optimisation
Definition
A definition is a precise description of what a concept, a term, or an object means. Understanding definitions is the foundation of learning any field, and every concept has its own exact meaning.
The goal: to find the minimum of a differentiable function .
The iteration formula:
where:
- is the iterate of the -th step
- is the learning rate (the step size)
- 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).
Theorem
A theorem is a proposition that has been rigorously proved, and it is the foundation of mathematical reasoning. A theorem usually states its conditions and its conclusion, and is an important part of any mathematical system.
Suppose is an -smooth convex function (the gradient is -Lipschitz continuous, that is, ). With a fixed learning rate , gradient descent satisfies:
that is, the rate of convergence is (sublinear convergence).
If is also -strongly convex (), then the rate of convergence is linear:
where is called the condition number; the larger the condition number, the slower the convergence.
The Choice of the Learning Rate
- A learning rate that is too small: the convergence is slow and many iterations are needed.
- A learning rate that is too large: it may oscillate or even diverge (the value of the function rises instead of falling).
- The optimal fixed learning rate: ( is the Lipschitz constant of the gradient).
- In practice one often uses a decaying learning rate: or .
Definition
A definition is a precise description of what a concept, a term, or an object means. Understanding definitions is the foundation of learning any field, and every concept has its own exact meaning.
Exact line search: at each step the optimal step size is chosen
Inexact line search: one only requires a sufficient decrease in the value of the function; the Armijo condition is the common choice:
where is a constant. Inexact line search involves much less computation and is the mainstream choice in practice.
Stochastic Gradient Descent (SGD)
Mathematical formula
A formula is a symbolic expression of quantitative relations and structural patterns, and an essential tool for solving mathematical problems. Key formulas should be mastered and applied flexibly.
When the objective function is the sum of the losses of a large number of samples , each iteration uses the gradient of only one sample (or a small batch) to approximate the full gradient:
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
Mathematical formula
A formula is a symbolic expression of quantitative relations and structural patterns, and an essential tool for solving mathematical problems. Key formulas should be mastered and applied flexibly.
where 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)
Mathematical formula
A formula is a symbolic expression of quantitative relations and structural patterns, and an essential tool for solving mathematical problems. Key formulas should be mastered and applied flexibly.
The default parameters are . Adam combines momentum with an adaptive learning rate, and it is one of the most commonly used optimisers in deep learning.
Example 1: Gradient Descent on a Quadratic Function
Use gradient descent to find the minimum of , starting from with a learning rate , and write down the first three iterations and analyse the convergence.
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:
- The start: and
- Step 1: and
- Step 2: and
- Step 3: and
- Convergence: (the largest eigenvalue) and , so the condition for convergence is satisfied. The convergence factor in the direction is and in the direction , so the 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 .
Example 2: Exact Line Search
For , starting from , use an exact line search to find the optimal step size of the first step.
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:
- The search direction
- Differentiating with respect to : , so
- The next point:
Answer: the optimal step size is , and the next point is .
Exercise 1
Use gradient descent to find the minimum of , starting from with a learning rate , and write down the first three iterations.
Approach:
The same procedure as in the examples: write the gradient, then iterate.
Steps:
- The start and
- Step 1: and
- Step 2: and
- Step 3: and
Answer: the three iterations are , and , with the function value falling from 8 to 1.0488.
Exercise 2
Explain why the learning rate must satisfy for gradient descent to converge on an -smooth function.
Approach:
Look at the iteration in one dimension, where the update is the scalar , and examine when this linear iteration diverges.
Steps:
- In one dimension, ; near a minimum we have , and
- Hence
- The iteration converges if and only if , that is,
- Since , the condition guarantees convergence in every direction
- If , then in the direction where is close to we have , and the iteration diverges (it oscillates with growing amplitude).
Answer: the condition guarantees that the contraction factor is less than 1 in every direction, so the iteration converges; a learning rate that is too large makes the iteration diverge.
Symbols Used in This Article
| Symbol | Type | Pronunciation/Explanation | Meaning in This Article |
|---|---|---|---|
| Learning rate | learning rate | The step size of gradient descent | |
| Iterate | iteration point | The iterate of the -th step | |
| Momentum | velocity / momentum | The accumulated gradient in the momentum method | |
| Momentum coefficient | momentum coefficient | The decay coefficient of the momentum method | |
| Lipschitz constant | Lipschitz constant | The Lipschitz constant of the gradient | |
| Strong convexity parameter | strong convexity | The parameter of a strongly convex function | |
| Condition number | condition number | ||
| Adam moments | moments | The first and second moments of the Adam algorithm | |
| Small constant | epsilon | The small constant in Adam that prevents division by zero |
