11
$\begingroup$

While minimizing a Lipschitz continuous strongly convex functions, the rate of convergence of the gradient descent method depends on the condition number of the hessian of the function, where a high condition number leads to slow convergence. Can someone give an intuitive explanation explaining why the condition number of the hessian and the rate of convergence are related?

$\endgroup$

3 Answers 3

20
$\begingroup$

The classic zig-zag picture is misleading since it suggests that the slow convergence is due to overshooting. But for ill-conditioned problems, convergence is still slow even on a purely quadratic function with perfect "ridge-line" line search, where you step to the exact ridge-line of the mountain so that there is no overshooting at all.

The correct intuition is that, since the gradient points in the steepest direction, gradient descent cannot effectively explore a direction in parameter space until it has already eliminated all other directions in parameter space that are steeper. So even in the best case scenario of perfect line search, it will take one iteration to eliminate the steepest direction, then the next iteration to eliminate the second steepest direction, then the next iteration to eliminate the third steepest direction, and so forth.

Imagine climbing up a mountain using the method of steepest ascent. You will not walk straight towards the peak. Rather, you will climb up the steepest face of the mountain until you reach a ridge, then follow the ridge to the top, making a dog-leg path.

climbing mt si (image credit to Mountains to Sound Greenway Trust)

Were it possible to climb an N -dimensional mountain, the path of steepest ascent would first climb to the top of the (N − 1)-dimensional ridge perpendicular to the steepest direction, then to the top of the (N − 2)-dimensional ridge perpendicular to the first two steepest directions, and so on. The more the eigenvalues of the Hessian are separated, the more the path will resemble the set of $N$ edges on a box, traversing from one corner of the box to the opposite corner. This is illustrated below for ill-conditioned functions $\mathcal{J}(q)$ in increasing numbers of dimensions.

When climbing to a ridge, only minor progress will be made in the direction of future, less steep, ridges. This minor progress is what the classic convergence bounds for gradient descent rely on. The rate of this minor progress will be proportional to the ratio of steepnesses: the greater the difference in steepness, the less progress will be made on the future ridge during the process of climbing the current ridge. The eigenvalues of the Hessian characterize these different steepnesses. The condition number of the Hessian, being the ratio of the largest eigenvalue to the smallest, is the ratio of the steepest ridge's steepness to the shallowest ridge's steepness, which is why it enters into the convergence bounds.

2D

2d dog-leg path

3D

3d dog-leg path

3d hypercube path 2

ND

Nd dog-leg path

This is discussed in greater detail in Section 3.1 of my Ph.D. thesis here: https://repositories.lib.utexas.edu/bitstream/handle/2152/75559/ALGER-DISSERTATION-2019.pdf?sequence=1

$\endgroup$
1
  • 2
    $\begingroup$ amazing intuition, I find difficult to interpret SGD artifacts on high dimensions and this brings some knowledge to the table, thanks! $\endgroup$
    – fr_andres
    Commented Apr 11, 2019 at 23:15
3
$\begingroup$

The steepest descent method "zigzags" as it approaches a minimum. See this figure from Wikipedia. This phenomenon becomes much worse for a badly conditioned problem.

The reason that the method zigzags is that the level curves of the objective function are not perfectly circular. If they were circular, then the steepest descent direction would point straight to the minimum of the function and the method could converge to the minimum in a single iteration (assuming that the step length was selected properly.)

With elliptical level curves, the steepest descent direction doesn't point straight to the minimum. Even with an "exact line search" that minimizes along that steepest descent direction, the method ends up zigzagging.

For a very badly conditioned problem, the steepest descent direction can be nearly orthogonal to the direction that would take you to the minimum, so that the method must zigzag many times to get close to the minimum.

$\endgroup$
2
1
$\begingroup$

To give a more visual answer, would suggest you download and play with this fantastic package (I am not the author): https://github.com/lilipads/gradient_descent_viz

In particular, try out gradient descent (both the continuous and stepwise versions). Here is a visualization I generated using this package (also see the full resolution version):

Gradient descent on a simple convex loss surface

Let the function we are trying to minimize (which generates this convex paraboliod surface) be $f(x)$. Recall that if the surface is an upward-facing paraboloid, it is given by the vector-valued function $f: \mathbb{R}^n \rightarrow \mathbb{R}$, where $f(x) = \frac{x^TAx}{2} - x^Tb$. Things to keep in mind:

  • $A \in \mathbb{R}^{n \times n}$ is a particular kind of matrix called Symmetric Positive Definite. An SPD matrix is analogous to a positive scalar ($\alpha > 0$) when the number of dimensions is $n \gt 1$. The important property is that $x^TAx > 0, \forall x\neq 0$, which is what makes the parabolid open upwards rather than downwards. The values in $A$ determine how curved the paraboloid is.
  • $b$ is some vector which we assume to be non-zero. Varying b changes what the minima of this surface is.
  • The vector which gives the direction of the (negative) gradient at any point $x \in \mathbb{R}^n$ is: $ - \nabla f(x) = b - Ax$.
  • In our current discussion, $x \in \mathbb{R}^2$.

Notice that in the screencap below, we are currently at $x = (\chi_0, \chi_1) = (-1.68, 0.97)$. Even though $f(x)$ is convex, the gradient (black arrow) does not point towards the minima (red region). You can conjecture that, given a certain $A$ and $b$, there are many values of $x$ which cause this to happen, particularly when $\chi_0$ and $\chi_1$ have relatively large magnitude.

Start of gradient descent

Now, when we update the ball to the second location in the video, we are at $x = (-0.56, 0.04)$. Notice that $\chi_1$ here is much smaller than before (0.97 to 0.04). As a result, when we compute the gradient at our second location, is mostly along the $\chi_0$ (notice the stubby little blue arrow pointing east).

Whether or not the gradient vector points in the direction of the minima is immaterial of where the minima is located; it is simply the tangent to the loss surface at some point $x$.

One case where the gradient vector definitely points to the minima is when $A$ is the identity matrix and $b=0$, then the gradient vector is $-x$, which will point exactly at the minima (which will be the origin).

Second step of gradient descent

Now, the previous surface was nicely convex: the width and height of the parabola were roughly equal, and we could converge quickly.

Let's consider an ill-conditioned problem, i.e. due to some skewed values in $A$, the paraboloid $f(x)$ is highly stretched along one axis ($\chi_0$ as per the image below). In this case, the value $f(x)$ will fluctuate rapidly with small changes in $\chi_1$, i.e. the component of the gradient vector $- \nabla f(x)$ corresponding to $\chi_1$ is large. This means the gradient vector will mostly point along $\chi_1$, which may or may not be in the direction of the minima.

On the other hand, assume even that in this stretched parabola, we start due south of the minima. In that case, the gradient will generally point towards of the minima, so gradient descent will converge quickly. The issue occurs when you start somewhere on the far left or the far right. In particular, if your random initialization starts you at some point far from the minima in $\chi_0$ (the stretched axis) then you start getting the zig-zag pattern.

To avoid this, we often precondition the problem, so that the contour plots looks like circles. In that case, no matter where you start, convergence takes roughly the same amount of (short) time.

Skewed parabolic region

(image credit: https://mc.ai/my-machine-learning-diary-day-65/)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .