I don’t know a lot about the study of matrix multiplication complexity, but I think that one of the following two possibilities is likely to be true:
There is some ω∈R and an algorithm for matrix multiplication of complexity O(nω+ϵ) for any ϵ>0 s.t. no algorithm of complexity O(nω−ϵ) exists (AFAIK, the prevailing conjecture is ω=2). This algorithm is simple enough for human mathematicians to find it, understand it and analyze its computational complexity. Moreover, there is a mathematical proof of its optimality that is simple enough for human mathematicians to find and understand.
There is a progression of algorithms for lower and lower exponents that increases in description complexity without bound as the exponent approaches ω from above, and the problem of computing a program with given exponent is computationally intractable or even uncomputable. This fact has a mathematical proof that is simple enough for human mathematicians to find and understand.
Moreover, if we only care about having a polynomial time algorithm with some exponent then the solution is simple (and doesn’t require any astronomical coefficients like Levin search; incidentally, the O(n3) algorithm is also good enough for most real world applications). In either case, the computational complexity of matrix multiplication is understandable in the sense I expect intelligence to be understandable.
So, it is possible that there is a relatively simple and effective algorithm for intelligence (although I still expect a lot of “messy” tweaking to get a good algorithm for any specific hardware architecture; indeed, computational complexity is only defined up to a polynomial if you don’t specify a model of computation), or it is possible that there is a progression of increasingly complex and powerful algorithms that are very expensive to find. In the latter case, long AGI timelines become much more probable since biological evolution invested an enormous amount of resources in the search which we cannot easily match. In either case, there should be a theory that (i) defines what intelligence is (ii) predicts how intelligence depends on parameters such as description complexity and computational complexity.
A good algorithm can be easy to find, but not simple in the other senses of the word. Machine learning can output an algorithm that seems to perform well, but has a long description and is hard to prove stuff about. The same is true for human intelligence. So we might not be able to find an algorithm that’s as strong as human intelligence but easier to prove stuff about.
Machine learning uses data samples about an unknown phenomenon to extrapolate and predict the phenomenon in new instances. Such algorithms can have provable guarantees regarding the quality of the generalization: this is exactly what computational learning theory is about. Deep learning is currently poorly understood, but this seems more like a result of how young the field is, rather than some inherent mysteriousness of neural networks. And even so, there is already someprogress. People have been making buildings and cannons before Newtonian mechanics, engines before thermodynamics and ways of using chemical reactions before quantum mechanics or modern atomic theory. The fact you can do something using trial and error doesn’t mean trial and error is the only way to do it.
Deep learning is currently poorly understood, but this seems more like a result of how young the field is, rather than some inherent mysteriousness of neural networks.
I think “inherent mysteriousness” is also possible. Some complex things are intractable to prove stuff about.
I don’t know a lot about the study of matrix multiplication complexity, but I think that one of the following two possibilities is likely to be true:
There is some ω∈R and an algorithm for matrix multiplication of complexity O(nω+ϵ) for any ϵ>0 s.t. no algorithm of complexity O(nω−ϵ) exists (AFAIK, the prevailing conjecture is ω=2). This algorithm is simple enough for human mathematicians to find it, understand it and analyze its computational complexity. Moreover, there is a mathematical proof of its optimality that is simple enough for human mathematicians to find and understand.
There is a progression of algorithms for lower and lower exponents that increases in description complexity without bound as the exponent approaches ω from above, and the problem of computing a program with given exponent is computationally intractable or even uncomputable. This fact has a mathematical proof that is simple enough for human mathematicians to find and understand.
Moreover, if we only care about having a polynomial time algorithm with some exponent then the solution is simple (and doesn’t require any astronomical coefficients like Levin search; incidentally, the O(n3) algorithm is also good enough for most real world applications). In either case, the computational complexity of matrix multiplication is understandable in the sense I expect intelligence to be understandable.
So, it is possible that there is a relatively simple and effective algorithm for intelligence (although I still expect a lot of “messy” tweaking to get a good algorithm for any specific hardware architecture; indeed, computational complexity is only defined up to a polynomial if you don’t specify a model of computation), or it is possible that there is a progression of increasingly complex and powerful algorithms that are very expensive to find. In the latter case, long AGI timelines become much more probable since biological evolution invested an enormous amount of resources in the search which we cannot easily match. In either case, there should be a theory that (i) defines what intelligence is (ii) predicts how intelligence depends on parameters such as description complexity and computational complexity.
A good algorithm can be easy to find, but not simple in the other senses of the word. Machine learning can output an algorithm that seems to perform well, but has a long description and is hard to prove stuff about. The same is true for human intelligence. So we might not be able to find an algorithm that’s as strong as human intelligence but easier to prove stuff about.
Machine learning uses data samples about an unknown phenomenon to extrapolate and predict the phenomenon in new instances. Such algorithms can have provable guarantees regarding the quality of the generalization: this is exactly what computational learning theory is about. Deep learning is currently poorly understood, but this seems more like a result of how young the field is, rather than some inherent mysteriousness of neural networks. And even so, there is already some progress. People have been making buildings and cannons before Newtonian mechanics, engines before thermodynamics and ways of using chemical reactions before quantum mechanics or modern atomic theory. The fact you can do something using trial and error doesn’t mean trial and error is the only way to do it.
I think “inherent mysteriousness” is also possible. Some complex things are intractable to prove stuff about.