Submitted by **IamTimNguyen** t3_105v7el
in **MachineLearning**

#
**binfin**
t1_j3f8n5x wrote

Reply to comment by **BossOfTheGame** in **[R] Greg Yang's work on a rigorous mathematical theory for neural networks** by **IamTimNguyen**

That the network gets some percentage accuracy on some testing set.

Editing for additional contextâ€¦ the poly time verifier is testing the network and verifying that it gets at least some % accuracy. This is similar to the poly time verifier for the traveling salesman problem, where you verify that a solution exists with some total travel distance. To find the shortest distance in a TSP instance, or the highest accuracy in a neural network you just need to do a binary search on your accuracy cutoff.

The complete poly-time solution for the NDTM is to test every bit combination of your parameters, each time checking that the model has some % accuracy. To find the highest % accuracy you just perform a binary search of possible accuracies (which of course grows logarithmically with the floating point precision of your accuracy). This whole process is poly time on an NDTM, and therefor the problem is contained in NP. You can further prove that finding optimal neural networks is NP complete by having the neural network be trained to solve 3-sat problems, where number of neural network parameters is a poly scale of the 3-sat N.

Because optimizing an NN (with respect to some testing set) is solvable in poly-time by an NDTM, and because you can reduce an NP-complete problem to optimizing a neural network, optimizing a neural network is NP-complete.

#
**BossOfTheGame**
t1_j3fhxe7 wrote

I'm convinced. Brilliantly explained. Constructing the problem with respect to a bound makes a ton of sense.

Now I suppose we just code it up and throw it at CPLEX.

Viewing a single comment thread. View all comments