This is no longer there case, given deep learning, though. Right? Effectively, the training process can be seen as a giant matrix multiplication in one step.
Even a 2000x2000 matrix is relatively small as far as non O(N^3) matrix multiplication algorithms go. The faster asymptotic algorithms have larger fixed costs and do not map as nicely to current CPU/GPU architectures. Additionally, the people capable of writing high performance matrix multiplication mostly haven't spent time on the non-N^3 algorithms. I believe every common implementation (MKL, cuBLAS, Eigen, and various other BLAS's) all use the N^3 algorithm with optimizations more focused on computer architecture (cache and register blocking, limiting instruction dependencies, SIMD) than on algorithmic cleverness.
The only attempt that I know of to use a non-N^3 algorithm for practical matrix multiplication is this 2016 paper[0] called Strassens' reloaded. Figure 5 shows that their implementation of Strassen's outperforms MKL on a single core on about a (2K, 2K, 2K) matrix multiplication problem (look at upper right part of figure). However, you're rarely multiplying on a single core. Figure 6 shows that for a 10 core system, Strassen's becomes marginally faster with square matrices of size 4K, and only becomes significantly faster at size 8K. Although these results are super cool in my opinion, they're mostly not applicable to deep learning in it's current incarnation. Finally, Strassen's algorithm is one of the simplest non-N^3 matmul algorithms (known since 1969, complexity O(n^2.8)) and I believe it has much lower fixed costs than something more recent that has complexity more like O(n^2.37).
[0] Strassen's Reloaded paper: https://www.cs.utexas.edu/~jianyu/papers/sc16.pdf
And I also hadn't looked closely enough to see if amount of training data influenced matrix size. Makes sense that it would only influence a single dimension.
The output feature count is completely independent of the data size, and input feature count is only dependent on the dimensionality of the data (not the number of points), and that's only in the first layer of the network. Even with datasets with huge number of examples, the net usually only trains on a small "minibatch" of examples at a time, typically somewhere between 16 and 1024. This minibatch size is the algorithmic N_EXAMPLES. Given these numbers, the typical neural net matrix multiplication is probably something like (32, 256) x (256, 128). This is not nearly large enough for non-N^3 tmatmul algorithms o accelerate things.
It’s also worth noting that eg a convolution can be written with matrix multiplication (or rather some tensor products and contraction but there would be much redundancy from the fact that distant points cannot influence each other and the same thing is done to each point in the convolution. This is much less general than matrix multiplication
However, researchers at OpenAI demonstrated that the use of subnormal floating point values and their discontinuity [0] provides sufficient nonlinearity to learn nonlinear associations.
[0] https://blog.openai.com/nonlinear-computation-in-linear-netw...
Why are we working with these numbers so imprecisely, and with such discontinuity? When I've done math work in school, I always worked with the primitives without approximating.. 2^.5 was handled as such unless asked for an approximate answer.
I also ran across this in AutoCAD. Because they force arbitrary precision, one cannot define a sqrt length. 1.414 doesn't reach all the way on a r-triangle with 1,1 .
Edit: also, it isn't the activation function that makes it deep, is it? Rather, it is the literal depth of the network. Right?
for weight,bias in layers:
a = sigmoid(np.dot(weight, a) + bias)It can't be seen that way.
Deep learning becomes deep when you alter linear matrix multiplications with non-continuous functions. After that you can't reduce the problem into one step. You also lose associativity so you can't even do matrix chain multiplication optimization.
That said, in circuits, it is far less likely to ever multiply that large of a matrix. Even if I were correct that many steps of large training can be cast as a matrix multiply.