BIU theory seminar 07-Dec-22. Omri Weinstein (Columbia & HUJI): Approximate Matrix Multiplication via Spherical Convolutions

[Arnold Filtser]

Hello all,
Next Wednesday at 12:00 we will meet for our theory seminar.
Location: Building 403, room 217.

Please tell your colleagues and students about the seminar. You can join this mailing list, and a google calendar via the seminar page below.

See you there,
Arnold
https://theory.cs.biu.ac.il/

Speaker: Omri Weinstein 

Title: Approximate Matrix Multiplication via Spherical Convolutions

Abstract: We introduce a new bilinear operation, which we call Polyform, for fast approximate matrix multiplication, through sums of carefully weighted sparse polynomial multiplications. This algorithmic framework leads to several (parametrized)  improvements over known worst-case speed-vs-accuracy tradeoffs for approximate matrix multiplication. It also yields a cheap practical alternative to matrix multiplication in deep neural networks (DNNs), which is the main bottleneck in large-scale training and inference. 

Our algorithm has deep connections to additive combinatorics, sparse fourier transforms, and spherical harmonics. In particular, optimizing the polynomial's coefficients leads to a (non-convex) low-rank SDP problem generalizing Spherical codes. Meanwhile, our experiments demonstrate that, when using SGD to learn these coefficients in DNNs,  Polyform provides a substantial speedup on state-of-art DL models. This suggests replacing matrix multiplication with (variants of) polynomial multiplication in large-scale deep neural networks.

[Arnold Filtser]

The seminar starts in one hour!