5
$\begingroup$

A good way to visualize gradient ascent/descent is to assume you are in a quadratic bowl or on a mountain. If I visualize this, then the direction of steepest ascent/descent is the one that points straight towards the bottom of the bowl or top of the mountain.

With this understanding I have two questions:

  1. If you want to climb the hill or go down a bowl, why take a zig-zag path instead of taking a straight path to the top/bottom?

  2. Why doesn't the steepest path have a unit in the z direction? I understand that gradient is orthogonal to the level sets of the function. That is it lies in the x-y plane orthogonal to the contour. But why doesn't it have a unit in the z direction? With a unit in the z direction, it can point towards the minima/maxima and still be orthogonal to contour lines.

I have a related question: Gradient is NOT the direction that points to the minimum or maximum

$\endgroup$
  • $\begingroup$ The reason one takes a zigzag path (see: switchbacks) up a mountain is for a number of reasons, including the fact that the steepest possible assent is often very physically demanding for hikers (and potentially too steep for cars / trucks to safely ascend). Such paths also mitigate erosion problems IIRC. But the zigzag path is certainly not the "fastest" way up. To answer your second question, the "z" component is pre-determined by which direction one chooses to walk at any given point. It would be redundant information. $\endgroup$ – Kaj Hansen May 5 '17 at 23:27
  • $\begingroup$ The gradient of a function on two variables is a vector "in the input space", i.e. a vector with two components. What would it even mean for such a vector to have a "$z$-direction"? $\endgroup$ – Omnomnomnom May 5 '17 at 23:30
  • $\begingroup$ To expand on my earlier comment, it isn't too hard for most physically fit hikers to walk, say, 5 miles at a 5% grade. But it can be nigh-impossible for hikers to walk, say, 1 mile at a 30% grade. $\endgroup$ – Kaj Hansen May 5 '17 at 23:33
  • $\begingroup$ A gradient of $[1, 2]$ means that the slope is $1$ in the $x$ direction and $2$ in the $y$ direction. This completely defines the slope at that point. Why would you need a $z$ component? $\endgroup$ – Kaynex May 5 '17 at 23:50
  • 3
    $\begingroup$ It’s a zig-zag path for two reasons. The first, which is being covered in your related question, is that the gradient at a point doesn’t necessarily point toward a minimum (not even a local one). It points in the direction in which the slope is steepest at that point. The second reason is that gradient descent/ascent takes finite-length steps, ignoring all the changes of direction of the gradient in between stopping points. If instead you continuously adjusted the direction of motion, you’d end up with a smooth, albeit not necessarily straight, path. $\endgroup$ – amd May 6 '17 at 0:18
2
$\begingroup$

Suppose we have a $n \times n$ symmetric, positive definite matrix $\rm Q$. We define the following (convex) quadratic cost function

$$f (\mathrm x) := \frac 12 \mathrm x^\top \mathrm Q \,\mathrm x$$

whose gradient is $\nabla f (\mathrm x) = \mathrm Q \mathrm x$. Using gradient descent with step size $\mu > 0$,

$$\begin{array}{rl} \mathrm x_{k+1} &= \mathrm x_k - \mu \nabla f (\mathrm x_k)\\ &= \mathrm x_k - \mu \mathrm Q \mathrm x_k\\ &= \left( \mathrm I_n - \mu \mathrm Q \right) \mathrm x_k\end{array}$$

Let $\rm Q = V \Lambda V^\top$ be a spectral decomposition of $\rm Q$. Let $\eta_k := \mathrm V^\top \mathrm x_k$. After a bit of work, we obtain

$$\eta_{k+1} = \left( \mathrm I_n - \mu \Lambda \right) \eta_k$$

Note that if

$$0 < \mu \leq \frac{1}{\lambda_{\max} (\mathrm Q)}$$

then all the entries on the main diagonal of $\mathrm I_n - \mu \Lambda$ are in $[0,1)$ and, thus, no zig-zag behavior does occur. However, if

$$\frac{1}{\lambda_{\max} (\mathrm Q)} < \mu \leq \frac{2}{\lambda_{\max} (\mathrm Q)}$$

then at least one of the entries on the main diagonal of $\mathrm I_n - \mu \Lambda$ will be in $[-1,0)$ and, thus, zig-zagging will occur. In short, zig-zagging arises when the step size $\mu$ is not chosen properly.

$\endgroup$
0
$\begingroup$

Here's the plot of the gradient of a certain bowl. Notice that while the arrows point "uphill", they don't necessarily point directly away from the minimum at $(0,0)$.

The straight path to the bottom will not, in general, follow the direction of steepest descent.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.