Why should we expect there to be any mathematical foundation to this stuff? It's quite possible to imagine an alternate universe where GAs and neural nets don't work. Because they have different datasets that don't fit the structure of NNs well. Or problems that happen to not be solvable by the search strategies of GAs.
In fact we have many such problems in our own universe. I can give many examples of things NNs and GAs don't work well on right now. Those are just ignored by the research.
> Why should we expect there to be any mathematical foundation to this stuff?
i would be surprised that "this stuff" would be exception to the unreasonable effectiveness of mathematics. mathematics underpins virtually every observed phenomenon, including theoretical physics, computer science, economics. in fact, the mathematical structure of any physical theory often points the way to further advances in that theory and even to empirical predictions.
to not expect that "this stuff" should not have any mathematical foundation is a fantastically naive view.
No, there is no mathematical foundation for most of that stuff. No mathematician can prove that gravity exists. You can describe the laws of physics with mathematical expressions. Just as you can describe machine learning algorithms with mathematical expressions. But you can't prove the laws of physics are true with math. And I don't expect anyone to ever prove that Machine Learning should work.
why does the existence of such problems disprove the existence of a mathematical foundation? A well-founded mathematical foundation would prove/predict/explain why such problems don't "fit" with the "structure of NNs" with precise lower/upper bounds. Anything that works, and especially everything that doesn't work, must have an explanation. God doesn't play dice.
Maybe there's a reason. But I don't think you will ever be able to "prove" it. In any kind of formal way that would be satisfying to mathematicians.
Solomonoff induction is the best attempt to try to formalize machine learning. And in theory any machine learning algorithm that works, works because it approximates Solomonoff induction somehow. But proving anything approximates Solomonoff induction is absurdly difficult or impossible. Because it's incomputable and involves the search space of all possible computer programs.
In fact we have many such problems in our own universe. I can give many examples of things NNs and GAs don't work well on right now. Those are just ignored by the research.