8
$\begingroup$

Are there any neural network training procedure that involves solving a convex problem?

Note that I am referring more to MLPs, instead of (multi-class) logistic regression which is a neural network with no hidden layers.

I know that for MLPs, if there are no activation function in between (e.g. an identity activation function), then the entire model is simply $\hat y = W_n \cdots W_1 x$, $x$ is your example, $\hat y$ is your output, and obviously leads to a convex problem (linear regression) $\min_w \|\hat y - y\|$.

$\hat y = \text{softmax}(W_n \cdots W_1 x)$ is also convex, I believe (a composition of convex functions).

  • What about the case when there are nonlinearity in between (or at the output)? Does adding ANY standard choices of nonlinearity automatically lead to a non-convex problem?

  • In the same vein, are there any convex models except for (multi-class) logistic regression and MLPs with no hidden layers?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Any neural net with at least one hidden layer with any more than just one neuron, leads to an optimization problem that is not convex, this is true because if you have any (local) optimum for that architecture, you can get another one by switching the weights of those two neurons. Of course this is not granted to work if the two neurons have different inputs or different activation functions, but still, obtaining a convex optimization problem seems very unlikely anyway.

Beware that if you use identity activation (linear neurons) you still don't get a convex problem, because the same argument as above applies, you still get a problem with many redundant solutions. Linear problems can be convex only if there is no over-parametrization, that means using GLMs, not MLPs.

$\endgroup$
3
  • 1
    $\begingroup$ I believe that you are wrong. MLPs with linear activations are convex, but not strictly convex, just like linear regression with correlated regressors. They can be effectively optimized. $\endgroup$ Dec 9, 2020 at 13:42
  • $\begingroup$ @CagdasOzgenc What is the meaning of "linear regression correlated regressor" $\endgroup$
    – Fraïssé
    Dec 9, 2020 at 22:12
  • $\begingroup$ @CagdasOzgenc Hinton, Bengio, and LeCun have a very long talk that focuses on this question for a few slides. See, e.g. Slide 53, which points out that even with a single neuron in each layer multiplied by a constant weight, attempting to learn the identity function is not convex. Indeed, their are an infinite number of solutions lying along a hyperbola in w1,w2 space. Perhaps you mean that they are "not strictly convex in the neighborhood of the minimum"? $\endgroup$ Jun 26, 2023 at 21:50

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.