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'm a bit confused by the previous replies, I might of course be missing something.
Using neural networks leads indeed to an identifiability problem, i.e., multiple parametrizations lead to the same model, and therefore, to the same loss.
That being said, a $L2$ regularization changes the loss of these identical models to favorize those with lower $L2$ parameter norm.
If $H$ is the hessian of your empirical risk, then the hessian of your $L2$ penalized empirical risk is $H'=H+\lambda I$, where $I$ is a diagonal matrix and $\lambda$ is your penalization coeficient.
From there you can compute $\lambda'$, the value such that $H'$ is positive definite for all parameters, which is the absolute of the smallest eigenvalue of $H$ for the parameters minimizing that eigenvalue.
Now we have $H'=H+\lambda'I > 0$, from what I understand this is a necessary and sufficient condition for contrained risk to be convex.
Of course a notable problem is the fact that neural networks have models with identical $L2$ norm and identical empirical risk at the same time, and this for any given set of parameters, this is due to the neurons in a same layer being interchangeable.
This means that your convex empirical risk will necessarily have identical parameters at all interchangeable positions, has this is the only way a convex function can tolerate interchangeability, which makes the hidden layers all have effective width $1$.
I am not $100\%$ sure, but I'd wager using a $L2$ penalty with monotone parameterwise weight could do the trick in maintaining the width, as it would impose an order.
For example, for the p-vector of parameters $\theta$, instead of using $\lambda||\theta||^2_2$, you could use $\theta^Tdiag(\lambda, \lambda^2, ..., \lambda^p)\theta$.
