Answers.Body: <blockquote>
  <p>How are multiple local minima on the equation of a parabola possible, if a parabola has only one minimum?</p>
  </blockquote>
  <p>A parabola has one minimum, and no separate local minima. So it isn't possible.</p>
  <p>However...</p>
  <blockquote>
  <p>Gradient descent works on the equation of mean squared error, which is an equation of a parabola <span class="math-container">$y=x^2$</span></p>
  </blockquote>
  <p>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.</p>
  <p>In fact it only remains true for linear functions. When considering linear regression <span class="math-container">$\hat{y} = \sum_i w_i x_i + b$</span>, there is only one global minimum (with specific values of <span class="math-container">$w_i$</span> or specific vector <span class="math-container">$\mathbf{w}$</span>), and your assertion is true.</p>
  <p>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.</p>
  <p>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 <span class="math-container">$n$</span> nodes must have <span class="math-container">$n!$</span> absolute minimums. There is no way for these to exist without other stationary points in-between them.</p>
  <p>There is theory to suggest that most of the stationary points found in practice will not be local minima, but saddle points.</p>
  <p>As an example, <a href="http://liacs.leidenuniv.nl/assets/PDF/TechRep/tr94-19.pdf" rel="nofollow noreferrer">this is an analysis of saddle points in a simple XOR approximator</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-23T19:44:56.560Z
Answers.LastActivityDate: 2021-11-16T13:35:09.910Z
Answers.LastEditDate: 2021-11-16T13:35:09.910Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>Another view on this topic: think about the derivative of the MSE with respect to the inputs. You will need to apply the chain rule:</p>
  <p><span class="math-container">$$\frac{dMSE}{dx_i}=\sum_i2(y_i-f(x_i))\cdot(-1)\cdot\frac{df(x_i)}{dx_i}$$</span></p>
  <p>which only resembles the derivative of the parabola when, as mentioned in <a href="https://ai.stackexchange.com/a/11982/45714">nbro's answer</a>, <span class="math-container">$f(x_i)=c, \forall\ i$</span> or, more generally, when they <span class="math-container">$f(x)$</span> is linear (<a href="https://ai.stackexchange.com/a/11981/45714">Neil's answer</a>).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-18T14:22:22.453Z
Answers.LastActivityDate: 2021-11-18T14:22:22.453Z
Answers.UserDisplayName: Jzbach
Answers.Body: <p><span class="math-container">$g(x) = x^2$</span> is indeed a parabola and thus has just one optimum.</p>
  <p>However, the <span class="math-container">$\text{MSE}(\boldsymbol{x}, \boldsymbol{y}) = \sum_i (y_i - f(x_i))^2$</span>, where <span class="math-container">$\boldsymbol{x}$</span> are the inputs, <span class="math-container">$\boldsymbol{y}$</span> the corresponding labels and the function <span class="math-container">$f$</span> is the model (e.g. a neural network), is <em>not necessarily</em> a parabola. In general, it is only a parabola if <span class="math-container">$f$</span> is a constant function and the sum is over one element.</p>
  <p>For example, suppose that <span class="math-container">$f(x_i) = c, \forall i$</span>, where <span class="math-container">$c \in \mathbb{R}$</span>. Then <span class="math-container">$\text{MSE}(\boldsymbol{x}, \boldsymbol{y}) = \sum_i (y_i - c)^2$</span> will only change as a function of one variable, <span class="math-container">$\boldsymbol{y}$</span>, as in the case of <span class="math-container">$g(x) = x^2$</span>, where <span class="math-container">$g$</span> is a function of one variable, <span class="math-container">$x$</span>. In that case, <span class="math-container">$(y_i - c)^2$</span> will just be a shifted version (either to the right or left depending on the sign of <span class="math-container">$c$</span>) of <span class="math-container">$y_i^2$</span>, so, for simplicity, let's ignore <span class="math-container">$c$</span>. So, in the case <span class="math-container">$f$</span> is a constant function, then <span class="math-container">$\text{MSE}(\boldsymbol{x}, \boldsymbol{y}) = \sum_i y_i^2$</span>, which is a sum of parabolas <span class="math-container">$y_i^2$</span>, which is called a <em>paraboloid</em>. In this case, the paraboloid corresponding to <span class="math-container">$\text{MSE}(\boldsymbol{x}, \boldsymbol{y}) = \sum_i y_i^2$</span> will only have one optimum, just like a parabola. Furthermore, if the sum is just over one <span class="math-container">$y_i$</span>, that is, <span class="math-container">$\text{MSE}(\boldsymbol{x}, \boldsymbol{y}) = \sum_i y_i^2 = y^2$</span> (where <span class="math-container">$\boldsymbol{y} = y$</span>), then the MSE becomes a parabola.</p>
  <p>In other cases, the MSE might not be a parabola or have just one optimum. For example, suppose that <span class="math-container">$f(x) = x^2$</span>, <span class="math-container">$y_i = 1$</span> (<span class="math-container">$\forall i$</span>), then <span class="math-container">$h(x) = (1 - x^2)^2$</span>  looks as follows</p>
  <p><a href="https://i.sstatic.net/Uy0PZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Uy0PZ.png" alt="enter image description here" /></a></p>
  <p>which has two minima at <span class="math-container">$x=-1$</span> and <span class="math-container">$x=1$</span> and one maximum at <span class="math-container">$x=0$</span>. We can find the two minima of this function <span class="math-container">$h$</span> using calculus: <span class="math-container">$h'(x) = -4x(1 - x^2)$</span>, which becomes zero when <span class="math-container">$x=-1$</span> and <span class="math-container">$x=1$</span>.</p>
  <p>In this case, we only considered one term of the sum. If we considered the sum of terms of the form of <span class="math-container">$h$</span>, then we could even have more &quot;complicated&quot; functions.</p>
  <p>To conclude, given that <span class="math-container">$f$</span> can be arbitrarily complex, then also <span class="math-container">$\text{MSE}(\boldsymbol{x}, \boldsymbol{y})$</span>, which is a function of <span class="math-container">$f$</span>, can also become arbitrarily complex and have multiple minima. Given that neural networks can implement arbitrarily complex functions, then <span class="math-container">$\text{MSE}(\boldsymbol{x}, \boldsymbol{y})$</span> can easily have multiple minima. Moreover, the function <span class="math-container">$f$</span> (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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-01T11:32:12.410Z
Answers.Text: 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?
Answers.UserDisplayName: Karan Shah
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-23T19:49:21.737Z
Answers.LastActivityDate: 2023-01-20T15:28:44.257Z
Answers.LastEditDate: 2023-01-20T15:28:44.257Z
Answers.UserDisplayName: nbro
Body: <p>We often train neural networks by optimizing the mean squared error (MSE), which is an equation of a parabola <span class="math-container">$y=x^2$</span>, with gradient descent.</p>
  <p>We also say that weight adjustment in a neural network by the gradient descent algorithm can hit a local minimum and get stuck in there.</p>
  <p>How are multiple local minima on the equation of a parabola possible, if a parabola has only one minimum?</p>
  
Tags: <neural-networks><deep-learning><optimization><gradient-descent><mean-squared-error>
Title: How is it possible that the MSE used to train neural networks with gradient descent has multiple local minima?
UserDisplayName: souparno majumder
ThreadText: # How is it possible that the MSE used to train neural networks with gradient descent has multiple local minima?
  
  (Asked by: username_0 on 2019-04-23)
  
  We often train neural networks by optimizing the mean squared error (MSE), which is an equation of a parabola $y=x^2$, with gradient descent.
  
  We also say that weight adjustment in a neural network by the gradient descent algorithm can hit a local minimum and get stuck in there.
  
  How are multiple local minima on the equation of a parabola possible, if a parabola has only one minimum?
  
  **Tags:** neural-networks, deep-learning, optimization, gradient-descent, mean-squared-error
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_3 on 2019-04-23. Score: 9 | Accepted answer
  
  $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
  
  [![enter image description here](https://i.sstatic.net/Uy0PZ.png)](https://i.sstatic.net/Uy0PZ.png)
  
  which has two minima at $x=-1$ and $x=1$ and one maximum at $x=0$. We can find the two minima of this function $h$ using calculus: $h'(x) = -4x(1 - x^2)$, which becomes zero when $x=-1$ 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.
  
  > **Comments:**
  > **username_4**: 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?  
  
  ---
  
  ### Answer by username_1 on 2019-04-23. Score: 3
  
  > How are multiple local minima on the equation of a parabola possible, if a parabola has only one minimum?
  
  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.
  
  As an example, [this is an analysis of saddle points in a simple XOR approximator](http://liacs.leidenuniv.nl/assets/PDF/TechRep/tr94-19.pdf).
  
  
  ---
  
  ### Answer by username_2 on 2021-11-18. Score: 0
  
  Another view on this topic: think about the derivative of the MSE with respect to the inputs. You will need to apply the chain rule:
  
  $$\frac{dMSE}{dx\_i}=\sum\_i2(y\_i-f(x\_i))\cdot(-1)\cdot\frac{df(x\_i)}{dx\_i}$$
  
  which only resembles the derivative of the parabola when, as mentioned in [username_3's answer](https://ai.stackexchange.com/a/11982/45714), $f(x\_i)=c, \forall\ i$ or, more generally, when they $f(x)$ is linear ([username_1's answer](https://ai.stackexchange.com/a/11981/45714)).
  
  
  ---
  
  