Naive question: is the exponential increase in performance talked about in this article unique to neural nets? Or are there other techniques for writing classifiers that yield the same performance increase, given advances in hardware?
Neural networks are function approximators. So if you 1) know an algorithm that is really computationally complex but not highly random and 2) have a lot of inputs and outputs of that algorithm, you can usually train a neural network to approximate a closed-form formula of the algorithm. It boils down to a bunch of matrix-multiplies and some standard non-linear functions in between.
is that anything close to like polynomial fitting? What with PTIME and NP-Completion?
Kind of - but instead of computational complexity in the "NP" sense, you have lots of data. It's often so hard to get good training data that the cost of just waiting out a big algorithm to finish can be cheaper. So you have to weigh that.
well sure, you said as much before. But I was also thinking, what if P~=NP, in the sense that any function can be approximated by a polynomial of sufficiently high degree.
No, you can of course write some simple stretchy model that fits fast. The thing with NNs is that you don't have to domuch work to get a good fast model, you use cpu cores for that instead.