Complexity of neural network training and complexity proofs bypassing frontier issues
Time: 14:00 -- Location: LRI, 445
summary: We study the complexity of the neural network training decision
problem in two different contexts. First, in the general context, this
problem has been shown to be in extensions of the class ∃R. We have
been able to show that whenever the activation functions are Lipschitz
functions and the error function is the norm 2, the decision problem
can be solved in polynomial time with oracle in NP if we allow a
"grey" zone of small radius around the frontier of the problem. We
have also been able to use such frontier of difficult problem in the
case of 3-coloring, and built an algorithm which is constant time in
expectation. Second, if the activation function is ReLU, the error
function is an usual norm, and with only one neuron, we have been able
to show that the training decision problem is NP-complete.
In this talk, we will put a focus on the representation of certificates of
such problems, which, in both positive results around neural networks,
consists in finding a rational certificate of polynomial size.