Also, I'll mention that you're being too pessimistic about what theory can accomplish. The learning problem is much more constrained than P = NP.
The use, for example, of a training set of N examples, drawn iid, and evaluation on samples drawn from the same distribution imposes a lot of structure. I don't know if you're familiar with VC theory, but it's an example of the kind of "surprising" guarantees that can be derived in this setting. Other general examples are weak learning, the bias/variance tradeoff, and (in SVMs) the notion of large margin classifiers.
An applicable "theory" of design is what separates engineering from just mucking around.
The way I understand experimental physics, its purpose is either (a) to make observations on which new theories can be built or (b) to experimentally verify, or falsify, existing theories.
I don't think it's quite like throwing stuff at a wall and looking to see what sticks.
Sounds more like alchemy than experimental physics to me.