21–30 of 116 posts
Earlier quoted context omitted.
Unless it provides or simply works within formal verification?
Formal verification does not prove lack of bugs. In best case, can only catch one certain type of bugs. https://smartech.gatech.edu/handle/1853/62855
This is completely besides the matter, but reading "provably" in the abstract is a frank reminder of how terrible English spelling/pronounciation is. I can't imagine I'm the only well-read native English speaker who read this as "prov-ably" on first take. I don't know about most languages, but you just don't get nonsense like this in French, at least.
Earlier quoted context omitted.
Unless it provides or simply works within formal verification?
Formal verification does not prove lack of bugs. In best case, can only catch one certain type of bugs. https://smartech.gatech.edu/handle/1853/62855
I have a gut feeling that there is a faster way to compute logarithms going from least to most significant bit. How would I go about using ML to find it? [Edit] I think Feynman's algorithm might do it: "Consider the problem of finding the logarithm of a fractional number between 1 and 2. (The algorithm can be generalized without too much difficulty.) Feynman observed that any such number can be uniquely represented a…
1. How big is the search space?
2. What analysis approaches are likely to bear fruit for the search space? (theoretical analysis? optimization?)
3. If optimization is called for, what kind?
The big claim turns out to be a little overstated. The claim: > AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. reduces to: > AlphaTensor discovers algorithms that outperform the Strassen-square algorithm, which is a fast algorithm for large square matrices31,32. Although the discovered algorithm has the same theoretical comple…
That's the DeepMind modus operandi- and why they publish in Nature. It's in their best interest to claim as much covered ground as possible so they can keep working towards their end-goal. But most people who read Nature already know that results in that journal are overhyped. You just have to apply a specific prior/translator when you read their papers.
The big claim turns out to be a little overstated. The claim: > AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. reduces to: > AlphaTensor discovers algorithms that outperform the Strassen-square algorithm, which is a fast algorithm for large square matrices31,32. Although the discovered algorithm has the same theoretical comple…
They also identified algorithms which do fewer matrix multiplications than Strassen, improving the lower bound of matrix multiplies required (They highlight this in Fig 3).
In that light, I thought their claim was fair. They've discovered (different) algorithms which are both theoretically and practically better than Strassen's.
The big claim turns out to be a little overstated. The claim: > AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. reduces to: > AlphaTensor discovers algorithms that outperform the Strassen-square algorithm, which is a fast algorithm for large square matrices31,32. Although the discovered algorithm has the same theoretical comple…
First, you cut out the initial part of the sentence about improving on Strassen's two-level algorithm. Here is the complete sentence:
> Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago.
That is, note that the improvement cited in the latter part of the sentence is for the 4 x 4 matrix case.
But then your next quote is not in reference to 4 x 4 matrices. That is, for larger matrix sizes, the best algorithm AlphaTensor discovered had the same theoretical complexity as Strassen-square, but better performance.
EDIT: my next comments are confused and best ignored. See reply from pxx below.
For the 4 x 4 matrix case, the theoretical complexity of AlphaTensor's algorithm was O(N^2.778) compared with the Strassen algorithm's complexity of O(N^2.8074), which is an improvement.
The big claim turns out to be a little overstated. The claim: > AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. reduces to: > AlphaTensor discovers algorithms that outperform the Strassen-square algorithm, which is a fast algorithm for large square matrices31,32. Although the discovered algorithm has the same theoretical comple…
This is not a correct summary of the results of the paper. First, you cut out the initial part of the sentence about improving on Strassen's two-level algorithm. Here is the complete sentence: > Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. That is,…
The big claim turns out to be a little overstated. The claim: > AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. reduces to: > AlphaTensor discovers algorithms that outperform the Strassen-square algorithm, which is a fast algorithm for large square matrices31,32. Although the discovered algorithm has the same theoretical comple…
The big claim turns out to be a little overstated. The claim: > AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. reduces to: > AlphaTensor discovers algorithms that outperform the Strassen-square algorithm, which is a fast algorithm for large square matrices31,32. Although the discovered algorithm has the same theoretical comple…
This is not a correct summary of the results of the paper. First, you cut out the initial part of the sentence about improving on Strassen's two-level algorithm. Here is the complete sentence: > Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. That is,…
the complexity improvement in this paper is for arithmetic in Z_2 (modular arithmetic over single bits). in standard arithmetic, there is no asymptotic complexity improvement but the developed algorithms involve more efficiently fusible[0] operations, which is useful for the target hardware.
[0] ed: this used to read 'with fewer multiplications,' which is clearly wrong: fewer multiplications would lower complexity. Interestingly, the discovered algorithm seems to have a larger number of additions, but still runs faster.