It's not like we don't know anything about NP complete problems, neither. Critical phase transition in transition of alpha on random kSAT and other stuff, the realization that this is neither necessary or sufficient for NP completeness just a really common complementary phenomenon, etc etc
If you use 40M+ optimization variables and a really really bad optimization technique (gradients), which is however fast, as is the case in DL, the amount of nice practical things (e.g. limits) you might be able to say could be very low.
Yes, we all were stunned when somebody pulled some awesome trick and found a better upper/lower bound on something, yet sometimes it's better to be realistic - maybe once we transfer to quantum computers, we can test more limits practically when utilizing parallel power of QP.
Re:Failures of Deep Learning
by rectangletangle on Friday March 24, 2017 @05:38PM
(#13952438)
A lot of useful analogies for N-dimensional space can be abstracted from the simple transition from 2 to 3 dimensions.
"To deal with a 14-dimensional space, visualize a 3-D space and say 'fourteen' to yourself very loudly." -- Geoff Hinton
A math student and an engineering student went together to a presentation called "14-dimensional space topology". As the presentation progressed, engineering student became more and more frustrated as she could only grasp a few simple initial examples but the deeper the presentation went, the worse was the understanding. Yet the math student was absolutely enthusiastic, often asking the presenter various complicated questions and looking he enjoyed himself a lot. With a massive headache in the end, the engineering student turned to math student and asked: "How could you understand the presentation? I was able to understand 2D, 3D but once we increased number of dimensions I got lost and never understood anything about 14D!" The math student looked at her with a confident careless look and said: "It was simple. I imagined everything in N dimensions, and then just reduced it to 14".
I agree that it has turned into an NP problem in a lot of cases now but the concepts behind the problem of N-dimensional optimization are pretty well understood.