Discovering novel algorithms with AlphaTensor

[Jeff Hammond]

Hmm. Are we obsolete?

https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor

Jeff

Sent from my iPhone

[Jed Brown]

The supplement is far more interesting than the paper. It includes this (citing Grey Ballard et al [10]) on stability and the attached figure comparing with Strassen. I recall Jianyu's Strassen-BLIS paper showing greater than 10% speedups for square matrices with Strassen on CPUs. This shows Strassen being only 7-9% faster than baseline and the optimized results being a few percent faster than Strassen on TPUs. Maybe that's architecture or maybe it's implementation. It looks like they aren't exploring non-square matrices, while the Strassen-BLIS paper does.

Numerical stability. [10] identified two principal quantities that govern the numerical error bounds of matrix
multiplication algorithms: a prefactor Q, and a stability factor E. Lower values correspond to tighter bounds.
For the Strassen2 algorithm Q = 24 and E = 144, while for the discovered factorizations Q ∈ [23, 39] and
E ∈ [136, 1046]. In particular, AlphaTensor discovered an algorithm with Q = 23 and E = 136 without using a
reward function that would optimize for numerical stability. Finally, the growth factor [11] of the factorizations
is in the range from 220.14 to 547.26.