Limits on Matrix Multiplication
rjlipton.wordpress.com
rjlipton.wordpress.com
Do you have one off the top of your head you could link the code too? Doesn't have to be your implementation specifically. I just want to read the code for a parallel implementation.
I would however be impressed if it were constructively proven to be 2
Did we already exhaust economics of scale on this one?
If one has to multiply very large matrices then the goal is usually not so much to optimise matrix multiplication in general but to optimise the multiplication of the subset of matrices one is interested in. In these situations one cares about eg density and symmetry and choice of basis. There is a lot of information in a large random matrix and there is typically less information in an interesting large matrix. Therefore the goal is to skip the work required by all the entropy one does not have
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)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.
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 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.
The key here is that the methods have impracticably huge constant factors, such that for anything beyond Strassen would necessitate matrices larger than we could conceivably use to be more effective.
This comment also seems to suggest that legions of scientists and engineers aren't trying to optimize matrix multiplication. They are. Here are a few directions to pay attention to:
1. Specialized matrix multiplications for specific sizes and with reduced precision.
For example, Intel's libxsmm, methods for multiplying with reduced precision on [CGT]PU.
2. Structured matrix multiplication
Circulant and FFT-like matrices can be multiplied in linearithmic time. If you can set your problem up to use these instead (see Choromanski's Orthogonal Random Features [2016] or Smola's Deep-Fried Convnets [2015]/Fastfood [2014]), you can dramatically improve the speed and memory efficiency of your application.
3. Hardware-specific optimizations.
Optimizing algorithms by cache efficiency, using FMA (fused multiply-addition) and SIMD instructions, and prefetching all play a big part in improving these multiplications. I'm commenting specifically on CPUs, but similar issues and methods exist on all hardware backends.
In summary, many people are working very hard on improving matrix multiplication. Lower asymptotic complexity algorithms are not the answer for this due to the absurd constant factors they require.
Put some nicely formatted text such as Google ad results and clearly mention it as an ad. WHY the fuck do ad companies have to do insanely annoying borderline unethical things? Why is this industry so rotten to the core?
In this time and age, every computer literate person install adblocking in every system or asks someone to help to do it and almost nevers sees these ads. What is left is people who are more likely to fall for scams.