Learning Rate's Impact on Gradient Descent Convergence

1. The Learning Rate: A Visual Recap

Let's begin by revisiting the core idea with a more detailed visual. In the last lesson, we saw that the gradient descent update rule is:

The learning rate $\eta$ scales the gradient vector to determine the step size. The choice of $\eta$ has a dramatic impact on the optimization process.

Let's break down what this image shows:

• Learning rate too low (blue): The algorithm takes very small, cautious steps. As the bottom plot shows, the loss decreases reliably but very slowly. This can be computationally expensive.
• Good learning rate (green): The steps are large enough to make rapid progress but small enough not to overshoot the minimum. The loss decreases quickly and smoothly, leading to efficient convergence.
• High learning rate (red): The steps are too large. The algorithm overshoots the minimum, bouncing from one side of the valley to the other. While it might eventually converge, the path is inefficient, and the loss oscillates as seen in the bottom plot.
• Learning rate much too high (top right): The steps are so large that each update sends the parameter further away from the minimum. The loss function diverges, rapidly increasing instead of decreasing.

The following video provides a concise recap of these scenarios.

2. Towards a Formal Analysis: The Role of Curvature

The visual intuition is clear, but to analyse convergence properly, we need to answer why a certain learning rate is good or bad. The answer lies in the curvature of the loss function.

Think of the loss landscape. If you are in a very steep, narrow valley (high curvature), you need to take small, careful steps. If you're on a wide, gentle plain (low curvature), you can afford to take much larger steps.

In a one-dimensional problem, the curvature is simply the second derivative, $J^{\prime \prime }(w)$. In multiple dimensions, this is captured by the Hessian matrix, $\mathbf{H}$, which we studied in a previous lesson. The eigenvalues of the Hessian tell us about the curvature along different directions.

For a simple quadratic loss function, we can use this information to derive the optimal learning rate.

From the article, for a quadratic error function $E(W)$, the optimal learning rate that reaches the minimum in a single step is:

This elegant result formally connects the best step size to the function's curvature. The condition for convergence is $\eta <\frac{2}{E^{\prime \prime }(W)}$. This gives us a hard mathematical boundary for the learning rate.

3. Convergence Analysis in Multiple Dimensions

Most machine learning problems involve thousands or millions of parameters, so we need to extend this analysis to higher dimensions. As mentioned, the Hessian matrix ${\mathbf{H}}_f$ and its eigenvalues replace the simple second derivative.

To provide guarantees about convergence, we often rely on certain assumptions about the loss function $f$. Two of the most important are L-smoothness and m-strong convexity.

• L-smoothness means the function's curvature is bounded from above. Intuitively, the function can't curve "too sharply". Formally, a function is $L$-smooth if the largest eigenvalue of its Hessian is at most $L$. This property is what prevents gradient descent from wildly overshooting if the learning rate is chosen correctly.

• m-strong convexity means the function's curvature is bounded from below. Intuitively, the function is "at least as curved as a quadratic". Formally, a function is $m$-strongly convex if the smallest eigenvalue of its Hessian is at least $m$. This property ensures there is a unique global minimum and prevents the landscape from becoming too flat, which would slow down convergence.

The following text provides the formal theorems for convergence under these assumptions.

Let's summarise the crucial takeaways from this rigorous analysis:

1. For an $L$-smooth function, if we set the learning rate $\eta \le 1/L$, gradient descent is guaranteed to converge (specifically, the gradient norm will go to zero). The convergence rate is of the order $O(1/S)$, where $S$ is the number of steps.
2. For a function that is both $L$-smooth and $m$-strongly convex, setting $\eta =1/L$ gives a much faster exponential convergence rate. The error decreases by a factor of $(1-m/L)$ at each step.
3. The ratio $\kappa =L/m$ is called the condition number of the function. If $\kappa$ is large (meaning the function is very steep in some directions but very flat in others), convergence will be slow. This explains why scaling your input features is so important—it often improves the condition number of the loss function.

4. Practical Strategies for Setting the Learning Rate

The theoretical results are powerful, but computing the Hessian and its eigenvalues ($L={\lambda }_{max}$, $m={\lambda }_{min}$) is computationally infeasible for large models. So, how do we set the learning rate in practice?

A. Manual Tuning

The most common method is simply to try several values and see what works. As Andrew Ng mentioned in the video, you can try values on a logarithmic scale (e.g., 0.1, 0.01, 0.001, ...) and plot the training loss for each. You then pick the one that gives the fastest, most stable convergence.

B. Learning Rate Schedules

Instead of a fixed $\eta$, it's often beneficial to decrease it during training. You can start with a relatively high learning rate for fast initial progress and then reduce it to take smaller, more refined steps as you approach the minimum. This is known as a learning rate schedule or learning rate decay.

C. Adaptive Methods: Line Search

A more sophisticated approach is to find the optimal step size at each iteration. Instead of fixing $\eta$, we can treat it as a variable to be optimized at each step $t$. This is called a line search. The process is:

1. At point ${\theta }_t$, compute the descent direction $d_t=-\nabla J({\theta }_t)$.
2. Define a 1D function of the step size $\eta$: $g(\eta )=J({\theta }_t+\eta d_t)$.
3. Find the value of $\eta$ that minimizes this 1D function, ${\eta }_t=\arg {\min }_{\eta >0}g(\eta )$.
4. Update the parameters: ${\theta }_{t+1}={\theta }_t+{\eta }_t{d}_t$.

This turns the difficult high-dimensional optimization of $\theta$ into a sequence of simpler 1D optimizations for $\eta$.

While powerful, line search adds computational overhead at each step. In modern deep learning, more popular adaptive methods like Adam and RMSprop implicitly adjust the learning rate for each parameter, but they are built on the same foundational ideas we've covered today.

Conclusion

In this lesson, we deepened your understanding of gradient descent by moving from a purely visual feel for the learning rate to a rigorous analysis of its effect on convergence.

Here are the main takeaways:

• The choice of learning rate $\eta$ is critical: it can lead to slow convergence, efficient convergence, oscillation, or divergence.
• The ideal learning rate is related to the curvature of the loss function, which is measured by the second derivative (in 1D) or the eigenvalues of the Hessian matrix (in N-D).
• For functions that are L-smooth, a learning rate $\eta \le 1/L$ guarantees convergence.
• If a function is also m-strongly convex, convergence is exponentially fast, at a rate determined by the condition number $\kappa =L/m$.
• In practice, since computing $L$ and $m$ is often infeasible, we rely on strategies like manual tuning, learning rate schedules, and adaptive methods like line search.

You are now equipped not only to implement gradient descent but also to analyze and troubleshoot its convergence, a crucial skill for any machine learning practitioner.

Having established the core optimization machinery, we are ready to take a step back. In the next lesson, we will begin our second module, "Principles of Statistical Learning," by formally defining the components of a supervised learning problem: the hypothesis class, loss function, and risk. This will provide the general framework into which specific models and algorithms, like the ones we'll train with gradient descent, will fit.