# Viewing Deep Learning as an optimization problem, and general theorems on Duality.

In optimization problems of the type LP, we have methods like the simplex algorithm. The integer version of the problem is I believe NP-complete, but we know that a solution exists and we can find it in finite steps. However, no such guarantee exists in Deep Neural networks. It's not clear these networks even optimize the objective function. It's not clear if backpropagation finds the global minimum, or even if a finite number of minimum points exist, or it even converges.

But I do find Duality Theory appealing. However, (I think) that the duality theorems only apply to certain cases of optimization problems (linear and I believe convex?). Deep Neural Networks (I believe) have a few nice properties, they are continuous and differentiable everywhere, I'm not sure about the behavior of the 2nd derivative. I know it's a non-convex function. Is there a more general version of Duality that can apply to Deep Neural Networks?

• If you're using the ReLU activation function, then the neural network is not actually differentiable. (But, it seems that this is not a problem in practice.) Commented Aug 14, 2019 at 2:22
• By the way, when you're minimizing empirical risk with a large number of parameters, it's not even clear that you want to find the global minimum, which probably overfits to the training data. You'd rather have an optimization method that performs implicit regularization, like stochastic gradient descent. Commented Aug 14, 2019 at 4:43
• @ChrisCulter what is the explicit meaning of regularization? Can it be viewed as finding the weights of a neural network that minimize empirical risk and variation of the function simultaneously?
– lee
Commented Aug 14, 2019 at 6:26
• @SpentDeath I don't know how to formulate the true variance as a function of the weights. There are explicit regularizers of the weights which, when minimized, have the effect of reducing variance, but that isn't quite the same. Commented Aug 14, 2019 at 6:41
• @ChrisCulter Question: rather than regularizing implicitly by stopping the optimization algorithm early, is it not better to just add a sufficiently strong regularization term to the objective function so that we do want to truly solve the resulting optimization problem (in the sense of finding a local minimum)? In the early days of classical image deblurring, "stopping early" was used as a regularization technique, but later this was abandoned in favor of using regularization terms like wavelet regularization. I wonder if we are not in a similar situation with neural networks. Commented Aug 14, 2019 at 10:21