The problem with ML in my opinion is not that we're missing some sort of fundamental theory, but that there simply is none. ML is essentially fancy pattern matching roughly resembling the human visual system, which is why it happens to be good at tasks related to perception. It's not some master algorithm, it's not going to produce sci-fi AI, and it probably isn't even suited to solve most problems in the realm of in…
Deep Learning is just a branch (or even a sub-branch inside NN) of many ML techniques. Not all of them suffer the same problems or are based in the same theoretical background.