# How is local minima possible in gradient descent?

Gradient descent works on the equation of mean squared error, which is an equation of a parabola $$y=x^2$$.

We often say that weight adjustment in a neural network by gradient descent algorithm can hit a local minima and get stuck in there.

How is local minima on the equation of a parabola possible, where the slope is always parabolic?

## 2 Answers

$$g(x) = x^2$$ is indeed a parabola and thus has just one optimum.

However, the $$\text{MSE}(\boldsymbol{x}, \boldsymbol{y}) = \sum_i (y_i - f(x_i))^2$$, where $$\boldsymbol{x}$$ are the inputs, $$\boldsymbol{y}$$ the corresponding labels and the function $$f$$ is the model (e.g. a neural network), is not necessarily a parabola. In general, it is only a parabola if $$f$$ is a constant function and the sum is over one element.

For example, suppose that $$f(x_i) = c, \forall i$$, where $$c \in \mathbb{R}$$. Then $$\text{MSE}(\boldsymbol{x}, \boldsymbol{y}) = \sum_i (y_i - c)^2$$ will only change as a function of one variable, $$\boldsymbol{y}$$, as in the case of $$g(x) = x^2$$, where $$g$$ is a function of one variable, $$x$$. In that case, $$(y_i - c)^2$$ will just be a shifted version (either to the right or left depending on the sign of $$c$$) of $$y_i^2$$, so, for simplicity, let's ignore $$c$$. So, in the case $$f$$ is a constant function, then $$\text{MSE}(\boldsymbol{x}, \boldsymbol{y}) = \sum_i y_i^2$$, which is a sum of parabolas $$y_i^2$$, which is called a paraboloid. In this case, the paraboloid corresponding to $$\text{MSE}(\boldsymbol{x}, \boldsymbol{y}) = \sum_i y_i^2$$ will only have one optimum, just like a parabola. Furthermore, if the sum is just over one $$y_i$$, that is, $$\text{MSE}(\boldsymbol{x}, \boldsymbol{y}) = \sum_i y_i^2 = y^2$$ (where $$\boldsymbol{y} = y$$), then the MSE becomes a parabola.

In other cases, the MSE might not be a parabola or have just one optimum. For example, suppose that $$f(x) = x^2$$, $$y_i = 1$$ ($$\forall i$$), then $$h(x) = (1 - x^2)^2$$ looks as follows

which has two minima (and one maximum): at $$x=0$$ and $$x=1$$. We can find the two minima of this function $$h$$ using calculus: $$h'(x) = -4x(1 - x^2)$$, which becomes zero when $$x=0$$ and $$x=1$$.

In this case, we only considered one term of the sum. If we considered the sum of terms of the form of $$h$$, then we could even have more "complicated" functions.

To conclude, given that $$f$$ can be arbitrarily complex, then also $$\text{MSE}(\boldsymbol{x}, \boldsymbol{y})$$, which is a function of $$f$$, can also become arbitrarily complex and have multiple minima. Given that neural networks can implement arbitrarily complex functions, then $$\text{MSE}(\boldsymbol{x}, \boldsymbol{y})$$ can easily have multiple minima. Moreover, the function $$f$$ (e.g. the neural network) changes during the training phase, which might introduce more complexity, in terms of which functions the MSE can be and thus which (and how many) optima it can have.

• A big thanks to John Doucette who pointed out that my previous answer wasn't completely correct. – nbro Apr 30 '19 at 11:25
• I read in one of Andrew's courses, that local optima usually don't look like hills with multiple zero-derivative points; instead GD usually faces 'saddle points', and in general, they're easy to deal with. What's your view on that? – Karan Shah May 1 '19 at 11:32

My question is, how is local minima possible on the equation of a parabola, where the slope is always parabolic !

A parabola has one minimum, and no separate local minima. So it isn't possible.

However . . .

Gradient descent works on the equation of mean squared error, which is an equation of a parabola $$y=x^2$$

Just because the loss function is a parabola with respect to the direct input, does not mean that the loss function is a parabola with respect to the parameters that indirectly cause that error.

In fact it only remains true for linear functions. When considering linear regression $$\hat{y} = \sum_i w_i x_i + b$$, there is only one global minimum (with specific values of $$w_i$$ or specific vector $$\mathbf{w}$$), and your assertion is true.

Once you add nonlinear activations, as in neural networks, then the relationship between error function and parameters of the model becomes far more complex. For the last/output layer you can carefully choose a loss function so that this cancels out - you can keep your single global minimum for logistic regression and softmax regression. However, one or more hidden layers, and all bets are off.

In fact you can prove quite easily that a neural network with a hidden layer must have multiple stationary points (not necessarily local minima). The outline of the proof is to note that there must be multiple equivalent solutions, since in a fully-connected network you can re-arrange the nodes into any order, move the weights to match, and it will be a new solution with exactly the same behaviour, including the same loss on the dataset. So a neural network with one hidden layer with $$n$$ nodes must have $$n!$$ absolute minimums. There is no way for these to exist without other stationary points in-between them.

There is theory to suggest that most of the stationary points found in practice will not be local minima, but saddle points.