67
$\begingroup$

The cost function of neural network is $J(W,b)$, and it is claimed to be non-convex. I don't quite understand why it's that way, since as I see that it's quite similar to the cost function of logistic regression, right?

If it is non-convex, so the 2nd order derivative $\frac{\partial J}{\partial W} < 0$, right?

UPDATE

Thanks to the answers below as well as @gung's comment, I got your point, if there's no hidden layers at all, it's convex, just like logistic regression. But if there's hidden layers, by permuting the nodes in the hidden layers as well as the weights in subsequent connections, we could have multiple solutions of the weights resulting to the same loss.

Now more questions,

1) There're multiple local minima, and some of them should be of the same value, since they're corresponding to some nodes and weights permutations, right?

2) If the nodes and weights won't be permuted at all, then it's convex, right? And the minima will be the global minima. If so, the answer to 1) is, all those local minima will be of the same value, correct?

$\endgroup$
6
  • 3
    $\begingroup$ It is non-convex in that there can be multiple local minima. $\endgroup$ Feb 11, 2015 at 7:00
  • 4
    $\begingroup$ Depends on the neural network. Neural networks with linear activation functions and square loss will yield convex optimization (if my memory serves me right also for radial basis function networks with fixed variances). However neural networks are mostly used with non-linear activation functions (i.e. sigmoid), hence the optimization becomes non-convex. $\endgroup$ Feb 11, 2015 at 10:57
  • $\begingroup$ @gung, I got your point, and now I have more questions, please see my update :-) $\endgroup$
    – avocado
    May 23, 2016 at 7:25
  • 7
    $\begingroup$ At this point (2 years later), it might be better to roll your question back to the previous version, accept one of the answers below, and ask a new, follow-up question that links to this for context. $\endgroup$ May 23, 2016 at 11:08
  • 1
    $\begingroup$ @gung, yes you're right, but now I'm just not quite sure about some aspects of the the answer I upvoted before. Well, as I've left some new comments on the answers below, I'd wait a while to see if it's necessary to ask a new one. $\endgroup$
    – avocado
    May 23, 2016 at 12:31

7 Answers 7

48
$\begingroup$

The cost function of a neural network is in general neither convex nor concave. This means that the matrix of all second partial derivatives (the Hessian) is neither positive semidefinite, nor negative semidefinite. Since the second derivative is a matrix, it's possible that it's neither one or the other.

To make this analogous to one-variable functions, one could say that the cost function is neither shaped like the graph of $x^2$ nor like the graph of $-x^2$. Another example of a non-convex, non-concave function is $\sin(x)$ on $\mathbb{R}$. One of the most striking differences is that $\pm x^2$ has only one extremum, whereas $\sin$ has infinitely many maxima and minima.

How does this relate to our neural network? A cost function $J(W,b)$ has also a number of local maxima and minima, as you can see in this picture, for example.

The fact that $J$ has multiple minima can also be interpreted in a nice way. In each layer, you use multiple nodes which are assigned different parameters to make the cost function small. Except for the values of the parameters, these nodes are the same. So you could exchange the parameters of the first node in one layer with those of the second node in the same layer, and accounting for this change in the subsequent layers. You'd end up with a different set of parameters, but the value of the cost function can't be distinguished by (basically you just moved a node, to another place, but kept all the inputs/outputs the same).

$\endgroup$
8
  • $\begingroup$ OK, I understand the permutation explanation you made, I think it makes sense, but now I wonder is this the authentic one to explain why neural net is non-convex? $\endgroup$
    – avocado
    May 23, 2016 at 9:13
  • 2
    $\begingroup$ What do you mean with 'authentic one'? $\endgroup$
    – Roland
    May 23, 2016 at 9:41
  • $\begingroup$ I mean, this is how it should be interpreted, not just an analogy. $\endgroup$
    – avocado
    May 23, 2016 at 12:27
  • 5
    $\begingroup$ @loganecolss You are correct that this is not the only reason why cost functions are non-convex, but one of the most obvious reasons. Depdending on the network and the training set, there might be other reasons why there are multiple minima. But the bottom line is: The permuation alone creates non-convexity, regardless of other effects. $\endgroup$
    – Roland
    Feb 4, 2017 at 15:57
  • 1
    $\begingroup$ Sorry, I can not understand the last paragraph. But also I missunderstand why I mentioned max(0,x) here. In any case - I think the correct way to show that there maybe multiple mode (multiple local minimum) is prove it in some way. p.s. If Hessian is indefinite it said nothing - the quasiconvex function can have indefinite Hessian but it's still unimodal. $\endgroup$ Jul 10, 2017 at 19:19
28
$\begingroup$

If you permute the neurons in the hidden layer and do the same permutation on the weights of the adjacent layers then the loss doesn't change. Hence if there is a non-zero global minimum as a function of weights, then it can't be unique since the permutation of weights gives another minimum. Hence the function is not convex.

$\endgroup$
5
  • $\begingroup$ interesting heuristic $\endgroup$
    – Seymour
    Mar 21, 2020 at 16:43
  • $\begingroup$ you're assuming there is a minima that is attained. What if there isn't (think $e^{-x}$)? $\endgroup$ May 29, 2020 at 15:56
  • $\begingroup$ This is not a proof by any means, but how I intuitively understand it. It is certainly possible to design pathological examples where the above argument doesn't work. Besides the condition you mentioned, another case when this doesn't work is when all the weights at the minima are equal. But we know this case is highly unlikely. We also know that a minima exists by examining the region close to where gradient descent terminates. $\endgroup$
    – Abhinav
    May 30, 2020 at 17:36
  • 1
    $\begingroup$ This is pretty rigorous. Your argument shows that if the columns of each weight matrix are not identical at convergence, then the objective function is nonconvex. $\endgroup$
    – John Jiang
    Jul 26, 2020 at 16:07
  • $\begingroup$ Only strictly convex functions have a unique global minimum. Thus, this argument only rules out that our function is strictly convex. Convex functions are allowed to have multiple local minima, which are all global optima. So one would need to show that on the line segment (in parameter space) between the two found minima, our function value increases again. For an alternative answer not suffering from this issue, look at @Reza's answer. $\endgroup$
    – saper0
    Jan 6 at 8:59
12
$\begingroup$

Whether the objective function is convex or not depends on the details of the network. In the case where multiple local minima exist, you ask whether they're all equivalent. In general, the answer is no, but the chance of finding a local minimum with good generalization performance appears to increase with network size.

This paper is of interest:

Choromanska et al. (2015). The Loss Surfaces of Multilayer Networks

http://arxiv.org/pdf/1412.0233v3.pdf

From the introduction:

  • For large-size networks, most local minima are equivalent and yield similar performance on a test set.

  • The probability of finding a "bad" (high value) local minimum is non-zero for small-size networks and decreases quickly with network size.

  • Struggling to find the global minimum on the training set (as opposed to one of the many good local ones) is not useful in practice and may lead to overfitting.

They also cite some papers describing how saddle points are a bigger issue than local minima when training large networks.

$\endgroup$
6
  • 1
    $\begingroup$ thank you for the reference $\endgroup$
    – Seymour
    Mar 21, 2020 at 16:44
  • $\begingroup$ Then why does backpropagation work and not get stuck in a local minimum? $\endgroup$ Feb 15, 2021 at 19:52
  • 2
    $\begingroup$ @AlwaysLearning Gradient-based optimization algorithms can indeed get stuck in local minima. The point is that this is ok if the local minimum you get stuck in is a good one which, in machine learning tasks, means the corresponding parameters give good generalization performance. $\endgroup$
    – user20160
    Feb 16, 2021 at 2:36
  • $\begingroup$ My question is: how come this local minimum is always good in terms of fitting the training data. (given a reasonable depth and size of the network) $\endgroup$ Feb 16, 2021 at 12:07
  • 1
    $\begingroup$ @AlwaysLearning It's not always good, but the probability that it will be can increase with network size. Please have a look at the paper I mentioned. $\endgroup$
    – user20160
    Feb 16, 2021 at 22:47
6
$\begingroup$

Some answers for your updates:

  1. Yes, there are in general multiple local minima. (If there was only one, it would be called the global minimum.) The local minima will not necessarily be of the same value. In general, there may be no local minima sharing the same value.

  2. No, it's not convex unless it's a one-layer network. In the general multiple-layer case, the parameters of the later layers (the weights and activation parameters) can be highly recursive functions of the parameters in previous layers. Generally, multiplication of decision variables introduced by some recursive structure tends to destroy convexity. Another great example of this is MA(q) models in times series analysis.

Side note: I don't really know what you mean by permuting nodes and weights. If the activation function varies across nodes, for instance, and you permute the nodes, you're essentially optimizing a different neural network. That is, while the minima of this permuted network may be the same minima, this is not the same network so you can't make a statement about the multiplicity of the same minima. For an analogy of this in the least-squares framework, you are for example swapping some rows of $y$ and $X$ and saying that since the minimum of $\|y - X\beta\|$ is the same as before that there are as many minimizers as there are permutations.

$\endgroup$
9
  • 1
    $\begingroup$ "one-layer network" would be just what "softmax" or logistic regression looks like, right? $\endgroup$
    – avocado
    May 23, 2016 at 8:25
  • $\begingroup$ By "permuting nodes and weights", I mean "swapping", and that's what I got from the above 2 old answers, and as I understood their answers, by "swapping" nodes and weights in hidden layers, we might end up having the same output in theory, and that's why we might have multiple minima. You mean this explanation is not correct? $\endgroup$
    – avocado
    May 23, 2016 at 8:28
  • $\begingroup$ You have the right idea, but its not quite the same. For networks, the loss may not necessarily be binomial loss, the activation functions may not necessarily be sigmoids, etc. $\endgroup$ May 23, 2016 at 8:33
  • $\begingroup$ Yes, I don't think it's correct. Even though it's true that you'll get the same performance whether you permute these terms or not, this doesn't define the convexity or non-convexity of any problem. The optimization problem is convex if, for a fixed loss function (not any permutation of the terms in the loss), the objective function is convex in the model parameters and the feasible region upon which you are optimizing is convex and closed. $\endgroup$ May 23, 2016 at 8:34
  • $\begingroup$ I see, so if it's "one-layer", it might not be "softmax". $\endgroup$
    – avocado
    May 23, 2016 at 8:34
4
$\begingroup$

You will have one global minimum if problem is convex or quasiconvex.

About convex "building blocks" during building neural networks (Computer Science version)

I think there are several of them which can be mentioned:

  1. max(0,x) - convex and increasing

  2. log-sum-exp - convex and increasing in each parameter

  3. y = Ax is affine and so convex in (A), maybe increasing maybe decreasing. y = Ax is affine and so convex in (x), maybe increasing maybe decreasing.

Unfortunately it is not convex in (A, x) because it looks like indefinite quadratic form.

  1. Usual math discrete convolution (by "usual" I mean defined with repeating signal) Y=h*X Looks that it is affine function of h or of variable X. So it's a convex in variable h or in variable X. About both variables - I don't think so because when h and X are scalars convolution will reduce to indefinite quadratic form.

  2. max(f,g) - if f and g are convex then max(f,g) is also convex.

If you substitute one function into another and create compositions then to still in the convex room for y=h(g(x),q(x)), but h should be convex and should increase (non-decrease) in each argument....

Why neural netwoks in non-convex:

  1. I think the convolution Y=h*X is not nessesary increasing in h. So if you not use any extra assumptions about kernel you will go out from convex optimization immediatly after you apply convolution. So there is no all fine with composition.

  2. Also convolution and matrix multiplication is not convex if consider couple parameters as mentioned above. So there is evean a problems with matrix multiplication: it is non-convex operation in parameters (A,x)

  3. y = Ax can be quasiconvex in (A,x) but also extra assumptions should be taken into account.

Please let me know if you disagree or have any extra consideration. The question is also very interesting to me.

p.s. max-pooling - which is downsamping with selecting max looks like some modification of elementwise max operations with affine precomposition (to pull need blocks) and it looks convex for me.

About other questions

  1. No, logistic regression is not convex or concave, but it is log-concave. This means that after apply logarithm you will have concave function in explanatory variables. So here max log-likelihood trick is great.

  2. If there are not only one global minimum. Nothing can be said about relation between local minimums. Or at least you can not use convex optimization and it's extensions for it, because this area of math is deeply based on global underestimator.

Maybe you have confusion about this. Because really people who create such schemas just do "something" and they receive "something". Unfortunately because we don't have perfect mechanism for tackle with non-convex optimization (in general).

But there are even more simple things beside Neural Networks - which can not be solved like non-linear least squares -- https://youtu.be/l1X4tOoIHYo?t=2992 (EE263, L8, 50:10)

$\endgroup$
2
  • $\begingroup$ Then why does backpropagation work and not get stuck in a local minimum? $\endgroup$ Feb 15, 2021 at 19:52
  • $\begingroup$ Theoretical analysis, for now, can quantify only know a number of steps required to obtain an e-stationary point. If you want to leave within a room of non-convex optimization with fast (polynomial) methods you should not think about global minimum or local minimum for now.... In ML courses people sometime can wave hands, but I have described what is a situation right now. $\endgroup$ Feb 16, 2021 at 16:31
3
$\begingroup$

The composition of multiple layers is what makes the cross-entropy or least-squares loss function of multi-layer neural networks non-convex with respect to the set of all weights and biases. The composition is via multiplications of functions of the weights/biases and that is the main culprit for non-convexity, not the non-linearity of activation functions nor the inherent over-parameterization (re the arguments around permutations).

To understand how multiplying parameters can result in non-convexity, consider the function $f(x,y)=xy$. It is convex in $x$ when $y$ is constant and convex in $y$ when $x$ is fixed, but it is not convex in $x$ and $y$ jointly. Here is a plot of this function showing its non-convexity in $x$ and $y$:

enter image description here

Another example is $f(x,y)=x^2y^2$, which is non-convex as it is zero on the axes and positive elsewhere, while $x^2$ and $y^2$ are strictly convex.

$\endgroup$
5
  • $\begingroup$ I'm not certain this is true. Removing the non linearity (activation functions) means that any arbitrary network will collapse to a single neuron (any linear combination of linear transformations is itself a linear transformation). So adding extra layers without adding nonlinearity should not cause any changes. $\endgroup$
    – bendl
    Apr 29, 2023 at 12:48
  • $\begingroup$ You can replace the composition of multiple linear transformations with one without changing the global solution. It has nothing to do with the fact that, if you use the composition instead, the objective function will be non-convex with respect to the parameters of all layers. This is to point out the source of non-convexity not to suggest removing nonlinearities between layers. $\endgroup$
    – Reza
    Apr 30, 2023 at 23:57
  • 1
    $\begingroup$ @Reze So for example, lets assume that we have the network $y = w_2 \cdot w_1 x$. It can be also represented with another network, $y = w\cdot x$ where $w = w_1 \cdot w_2$. Lets say the global optimum is for the second network, $w = 1$. For the first network every solution of the form $(w*, 1/w*)$ would also be valid, and as such the loss would be non-convex. Did I get it right? $\endgroup$
    – ado sar
    May 27, 2023 at 11:08
  • $\begingroup$ You are right, @adosar. $\endgroup$
    – Reza
    May 28, 2023 at 12:47
  • 1
    $\begingroup$ This is a great answer as it is a clear and mathematically sound way of showing the non-convexity of multi-layer networks. Permuting weights is a good argument for getting intuition as to why multiple minima should exist. However, convex functions are allowed to have multiple local minima (which are all global minima) as only for strictly convex functions the global minimum is unique. (Of course for a convex function, the different global minima have to be "connected" in a certain sense regarding the parameters and can't be scattered, but this case has not been ruled out in previous answers.) $\endgroup$
    – saper0
    Jan 6 at 8:46
0
$\begingroup$

By definition, a function $f(x)$ is convex over a convex set $S$ if for all $x, y \in S$ and $t \in [0, 1]$, $tf(x) + (1-t)f(y) \geq f(tx + (1-t)y)$. Think of this as a straight line connecting two points of $y = x^2$ always being above the curve itself.

In the general case, $f$ can be shown to be convex if its Hessian is positive definite. Therefore, most of the cost functions used for training neural networks are convex with respect to the net's final output and expected value. This includes MSE, CCE. There are cherry-picked non-convex loss functions that could be used as well, such as the Rosenbrock function, $f(x, y) = 100(x^2-y)^2 + (x-1)^2$. However, I have not seen non-convex functions be used in literature or in practice unless the author is trying to show the goodness of their new update scheme. That an some $L \leq 1$ regularisation schemes.

As for convexity with respect to the intermediary layer weights, unless the output of these intermediaries is non-convex, convexity is still found. Linear layers, convolutions, and activation functions like ReLU are convex, so the loss is also convex with respect to these layers. Generally you just check the convexity of activation functions.


The argument about how to permute the weights and get the same loss shows that the loss isn't convex isn't true, and when it is, it's not useful.

Consider again $f(x, y)=x^2$ as a loss function. This is convex. Say the net currently outputs $x=2$ yielding a loss of $4$. But, if the weights are changed so that the net now outputs $x = -2$, the loss is also $4$. This is a convex function that (assuming suitable net expressivity) has a way to get the same loss.

Technically the argument also hinged on the fact that the loss you currently have is a global one - but this is an odd assumption as there's no way of knowing you've attained a global loss unless the function is cherry-picked or convex. There is also no suitable permutation of nodes to use, so there's no proof that the argument can be carried out.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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