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.
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.