It took me a while, but by reading a lot of AI research papers, I finally realized that Computer Science is primarily an experimental subject. You can see that we are running a lot of experiments in these papers. I don't think we understand what is going on inside the Deep Learning networks, for example. Sure, there are quite a few studies, but overall I think this is accurate, we simply does not know what is happening inside. The main difficulty is high dimensionality. We simply do not have mathematical frameworks to analyze structures in the 100s of dimensions. With the advent of special relativity in 1900s, we developed some understanding of 4-dimensional objects, and a bit higher dimensions in the String Theory. But 100s or 1000s dimensions, - we simply have no mathematical tools for that. The real CS theory is sorely lacking. For some reason, theoretical computer science seem to contribute quite little to the practical deep learning world, while primarily concerning itself with the complexity theory and computability questions. Fun stuff, but... Somebody needs to do this. Calling all theoretical physicists looking for hard but immediately useful problems to solve!
> The main difficulty is high dimensionality. We simply do not have mathematical frameworks to analyze structures in the 100s of dimensions.
The main difficulty in deep learning is the non-convexity of the optimization problem. We can handle simpler problems in high dimensions just fine. The oracle complexity bounds for projected gradient descent in convex optimization even hold for infinite-dimensional problems - see work of Nesterov.
Most of the hard questions about deep learning remain hard even for neural networks with low-dimensional inputs, outputs, and hidden layers. Also, some of the more fruitful approaches in deep learning theory involve taking the limit as the width of one network layer goes to infinity.
> For some reason, theoretical computer science seem to contribute quite little to the practical deep learning world, while primarily concerning itself with the complexity theory and computability questions. Fun stuff, but... Somebody needs to do this.
Lots of theoretical researchers are trying to figure out why deep learning works. Check out the work of Jason Lee, Simon Du, Sebastien Bubeck, etc. Most of these researchers have a CS background.
I am not sure we are disagreeing on much here. Yes, non-covexity is major problem for optimization. And yes, very simple problems could be analyzed in high dimensions. But many problems are not simple, including understanding general structure of the information/data flow through the network as well as non-convex optimization itself. The work on infinite width networks is very interesting and is getting novel insights. Many theoretical CS researchers are working on understanding of deep neural networks. I should have rephrased the sentence from "Somebody needs to do this" to "It would be nice if we could make a major progress in this direction".
