STEEPEST GRADIENT DESCENT

Steepest gradient descent is a variation of the gradient descent method where the step size is not fixed but instead chosen dynamically at each iteration. This approach ensures that the algorithm takes the most efficient step towards the minimum in each iteration.

Update Rule

The update rule for steepest gradient descent is given by:

where the step size ${\gamma }_k$ is chosen to minimize the function along the descent direction:

This means that at each iteration, we find the optimal step size ${\gamma }_k$ by minimizing the function along the direction of the negative gradient.

Geometric Interpretation

The two images illustrate the difference between fixed step size gradient descent and steepest gradient descent:

1. Fixed Step Size in Gradient Descent:

   • The step size is constant across all iterations, leading to potential inefficiencies in convergence.

2. Adaptive Step Size in Steepest Gradient Descent:

   • The step size is chosen optimally at each iteration, ensuring more efficient movement towards the minimum.

Convergence Properties

Theorem:
Let $\{x^k\}$ be a convergent sequence generated by the steepest descent algorithm applied to a function $f$. Then, in the worst case, the order of convergence of $\{x^k\}$ is 1.

This means that in the worst case, steepest gradient descent has a linear rate of convergence.

What Does This Mean?

• The order of convergence describes how fast the error decreases as the algorithm progresses.
• If the order of convergence is 1, it means the error decreases linearly in the worst case.
• This implies that steepest gradient descent is not always very fast—it may take many iterations to reach an accurate solution, depending on the function.

Modification: Step Size Reduction (Step Shredding)

A practical modification of steepest gradient descent involves step size reduction, also called step shredding. Here, the step size is adjusted dynamically based on a condition:

where $\epsilon \in (0,1)$ is a pre-selected method parameter, that controls the minimum required decrease in function value.

This condition ensures that each step results in sufficient function decrease.

If the condition is not satisfied, we reduce the step size ${\gamma }_k$ using a reduction factor $\delta \in (0,1)$:

The parameter $\delta$ determines how aggressively the step size is reduced when the descent condition is not met.

Why is this modification useful?

• If ${\gamma }_k$ is too large, we may overshoot the minimum, leading to oscillations or divergence.
• If ${\gamma }_k$ is too small, convergence becomes slow and inefficient.
• The step reduction rule ensures we adapt to the function landscape, preventing large, ineffective updates while still making steady progress.

Algorithm for Modified Steepest Descent

1. Initialize $x^0\in {\mathbb{R}}^n$, an arbitrary step size $\gamma$ (the same in all iterations), and parameters $\epsilon ,\delta \in (0,1)$.

2. For each iteration $k+1$:

   Set initial ${\gamma }_k=\gamma$.
   Compute the update:

   $$x^{k+1}=x^k-{\gamma }_k\mathrm{\nabla }f(x^k).$$

   Check if the inequality:

   $$f(x^{k+1})\le f(x^k)-\epsilon {\gamma }_k\parallel \mathrm{\nabla }f(x^k){\parallel }^2$$

   is satisfied.
   If satisfied: accept ${\gamma }_k$ and move to the next iteration.
   If not satisfied: reduce step size ${\gamma }_k=\delta {\gamma }_k$ and repeat.

This method ensures that the step size is sufficiently large for fast convergence while also ensuring descent in function value.

Practical Insights

• The modification using step shredding makes steepest gradient descent more robust.
• Requirement $(\ast \ast )$ is stricter than $(\ast )$, but both ensure function decrease.
• This version of gradient descent is widely used in practice due to its adaptive nature.

Steepest gradient descent dynamically adapts the step size, ensuring that the optimal step length is chosen at each iteration, leading to faster and more efficient convergence.

Simple Example of the Algorithm

Finding the Minimum of $f(x)=x^2$

Let’s minimize:

using Modified Steepest Descent.

Step 1: Initialize Parameters

• Choose an initial point: $x^0=5$
• Initial step size: $\gamma =1$
• Set $\epsilon =0.1$, $\delta =0.5$.

Step 2: Iterate

1. Compute Gradient:

   $$\mathrm{\nabla }f(x)=2x$$

   At $x^0=5$:

   $$\mathrm{\nabla }f(5)=10$$

2. Compute Update:

   $$x^1=x^0-\gamma \mathrm{\nabla }f(x^0)=5-1(10)=-5$$

3. Check Descent Condition:

   $$f(x^1)\le f(x^0)-\epsilon \gamma \parallel \mathrm{\nabla }f(x^0){\parallel }^2$$$$(-5{)}^2\le 5^2-0.1(1)({10}^2)$$$$25\le 25-10$$$$25\le 15$$$$25\nleqq 15$$

Since the condition fails, we reduce $\gamma$:

Then repeat the update with the smaller step size.

Step 3: New Update with Reduced $\gamma$

1. Compute New Update:

   $$x^1=5-0.5(10)=0$$

2. Check Descent Condition Again:

   $$f(0)\le 5^2-0.1(0.5)({10}^2)$$$$0\le 25-5$$$$0\le 20$$$$0\le 20$$

Since the condition holds, we accept $x^1=0$ and move to the next iteration.