Why can't we just add a penalty to make the Neural Network objective convex? When we use Neural Networks to solve various tasks, we define an objective that the Network parameters $\theta=(\theta_i)_{1\le i\le N}\in\Theta^N$ have to minimize. So, for neural networks $f(\cdot|\theta) $ parameterized by an array $(\theta_i)_i $, the objective can be written as follows
$$(\hat \theta):=\arg\min_{\theta\in\Theta^N} \mathcal L[f(\cdot|\theta )]\tag1$$
Where $\mathcal L$ is a loss function that we would like as small as possible.
A well known fact about neural networks is that, in essentially all non-trivial cases, the objective $(1)$ is highly non-convex and thus hard to optimize. It is true that SGD and its variants do a very good job, but we basically have no guarantees (as far as I know) not to get trapped in a bad local minima, or to get in a saddle point region which will make the training very slow.
A (probably naive) "solution" to these issues that occured to me is to "convexify" the objective, by adding a large enough strictly convex regularization term. In other words, solving the following objective :
$$\hat \theta:=\arg\min_{\theta\in\Theta^N} \mathcal L[f(\cdot|\theta) ] + \lambda\mathcal P[\theta ]\tag2 $$
Where $\lambda$ is a real hyperparameter and $\mathcal P$ is a strictly convex penalty (typically, $\mathcal P:\theta\mapsto\|\theta\|_2^2$).
Now, if the set $\Theta$ is compact (bounded, really) and $\mathcal L$ is twice-differentiable w.r.t. $\theta$, it is not hard to show that, for $\lambda$ large enough, the problem $(2)$ becomes strictly convex, which is appealing for a number of reasons :

*

*Convex optimization is much easier than non-convex optimization, therefore the optimization algorithms in this case could achieve much better performance.

*We are guaranteed that there exists a unique global minimizer of $(2)$ and to converge to it, so we are guaranteed to find the network with the "best possible performance".

*Aside from convexity, the penalty term $\lambda\mathcal P$ acts as a regularizer : it penalizes too complex solutions and makes the network less likely to overfit, which is a very desirable property.

Due to these observations, I was expecting that method (which I would call strongly regularized networks) to have been well studied in the literature, but I surprisingly haven't been able to find anything so far. I am aware that this method is perhaps a bit naive, here are a some points against it I can think of :

*

*Although $\Theta$ and thus the Hessian of $\mathcal L$ are bounded, in practice the minimum $\lambda$ which ensures strong convexity of $(2)$ would have to be way too large for the solutions to be exploitable. This makes sense although I still think that one could find practical applications in which $\lambda$ wouldn't have to be that large.

*A strongly convex penalty such as $\theta \mapsto \|\theta\|_2^2$ is not that desirable because it does not encourage sparsity, which seems to be one of the main things people are looking for when dealing with deep nets.

*This is, in some sense, already equivalent to existing and well-studied regularization methods (here are I am particularly thinking about the equivalence between Tikhonov and Ivanov regularization). If that is the case, I would like some references highlighting this, since I haven't been able to.

So, my question is : Has the setting $\mathbf{(2)} $ been well studied in the literature ? If not, why ? If so, can you please provide some references ?
Thank you.

Update : Following @Sycorax's great answer below, I still have some concerns :

*

*I understand the non-identifiability argument given below, and it seemingly implies that if $\mathcal P$ is a square loss penalty, $(2)$ will still not be convex. I would however like to know what is wrong with the following argument :

Denote by $\nabla^2\mathcal L$ the Hessian matrix of $\mathcal L$. $\nabla^2\mathcal L$ is well defined and is bounded on $\Theta^N$ (again, not a big assumption, if you take common loss functions and activations it is known that the second derivative exists and is continuous). If $\mathcal P$ is the least square loss then the Hessian matrix of $\lambda \mathcal P$ is $2\lambda\mathbf I_N$. Therefore, the Hessian matrix of the objective $(2)$ is $\nabla^2\mathcal L + 2\lambda\mathbf I_N$. Now, the definition of convexity tells us that $(2)$ is a striclty convex problem if and only if the Hessian is positive definite in the domain, i.e. if
$$\theta^T(\nabla^2 \mathcal  L+2\lambda\mathbf I_N)\theta >0,\quad\forall\theta\in\Theta^N-\{0\} $$
Now because the domain $\Theta^N$ is bounded, the eigenvalues of $\nabla^2 \mathcal  L$ are bounded on the domain as well, so taking $\lambda$ such that $2\lambda + \psi^*>0$ where $\psi^*:=\inf_{\theta\in\Theta^N}\mathrm{eig}(\nabla^2 \mathcal  L)$ guarantees that the above inequality is always satisfied, and thus strict convexity of the problem. However, this directly contradicts the non-identifiability argument given in the answer below. What is wrong with this argument ?

*

*Even if the least square penalty doesn't solve the problem of convexity, my question still stands. Indeed, the non-identifiability issue could be easily fixed by letting $\epsilon = (\epsilon_i)_{1\le i\le N}$ be fixed (small) hyperparameters, and defining
$$\mathcal P : \theta \mapsto \sum_{i=1}^N (\theta_i-\epsilon_i)^2$$
This way, by having a big enough $\lambda$, the convexity would be guaranteed by a similar argument as above, and if the $\epsilon_i$ are distinct then the non-identifiability issue disappears as well (in a way, it's like slightly disturbing a matrix to ensure it is invertible). Has this been studied ? Is this a ridiculous idea ?


I thought about it a bit more, and here is another simple explanation of why, for the least square loss $\mathcal P = \|\cdot\|_2^2$, using that method to learn your typical fully connected feedforward ReLU network is a terrible idea and you're not just likely but guaranteed to have a useless model after training (which also resolves the "paradox" of how a convex function can achieve multiple minima, as I asked in my question too) :
If $\lambda$ is taken large enough so that the program $(2)$ is convex, then it is straightforward to show that there exists a unique global minimum on the domain $\Theta^N$, let's call it $\theta^*$. So in this setting, we know that $\theta^*$ is unique, SGD should be able to pretty quickly converge to it and furthermore because $\lambda$ is probably pretty large the solution will not overfit the data. Great, isn't it ? No, not really.
The thing is, even if the minimizer is unique, any multilayer network is non-identifiable. That is, for any given set of weights $\theta$, there exist permutations of these weights $\tilde \theta$ that computes the exact same function (in fact, there are many such permutations, see here, here, or just the answer above). That property still holds for the minizer $\theta^*$, but we just said $\theta^*$ is unique ! So that implies that for any $\tilde \theta^*$ that is an appropriate permutation of $\theta^*$, we have
$$\tilde \theta^*_i=\theta^*_i,\quad \forall\, 1\le i\le N$$
It is thus easy to conclude from these observations that, at the minimum, for a non-identifiable loss such as least squares, all the weights are in fact equal, i.e. $\theta^* \in\mathrm{span}\{(1,1,\ldots,1)^T\}$. The neural network learned this way is thus essentially a non-linear function of only one parameter, which will be totally useless for the kind of problems that do require neural networks in the first place.

Now, as mentioned in my updated question, it doesn't necessarily mean that such an approach is doomed to fail : one could circumvent the non-identifiability issue by adding some acceptable constraints to the network such as adding some dropout (also known as skip connections). The penalty $\mathcal P$ could be chosen non-identifiable as well, although it would in some sense add some extra bias to the model that is not necessarily needed.
I mainly asked out of curiosity, so I'm not planning to implement any of these ideas anytime soon, but if someone does I'd love to see the results !
