5
$\begingroup$

Similar to how Strassen matrix multiplication is an asymptotically faster matrix-multiplication algorithm, there exists a similar idea for convolution by (short) filters called Winograd convolution [1,2] that lowers the number of multiplications required below that of the naive, direct-form convolution. To do this, Winograd convolution uses the Chinese Remainder Theorem over polynomials to convert real-valued data and filters to a real-valued transform space, pointwise multiplies, then transforms back the output. The FFT convolution does something similar but uses Fourier space and complex numbers.

It is worth noting at this point that like the FFT, Winograd convolution is linear and "correct" (if a convolution using these algorithms were symbolically performed, the exactly correct result, and not a mere approximation, would be obtained).

And yet, a properly implemented FFT is numerically stable, while Winograd convolution acquires hideous roundoff errors.

I've attempted to determine empirically using Numpy where, if anywhere, I could perform the steps for Winograd convolution (6, 3) (See [2]: indicates 6 outputs, 3 filter taps) in reduced precision while still maintaining high output precision. I used random, normally-distributed inputs and filter taps, and the $A, B, G$ matrices suggested by the authors on Github for NNPACK [3]. The answer was, nowhere:

  • If IEEE 754-2008 float (23+1 bit mantissa) is used throughout, the output appears to have around 12 bits precision.
  • If double (52+1 bit mantissa) is used throughout, the output appears to have about 25 bits precision.
  • If I cheap out and use float anywhere in the double-precision evaluation, I get 12 bits precision.

So my question is, Why does Winograd convolution halve the precision of the computation?

Because of Winograd's (and FFT's) linearity and correctness, I don't know how to isolate what causes the numerical instability in Winograd. Whatever the input and filters, both algorithms nominally give 0 error, and the perturbation in the outputs is linear in the perturbations at the inputs and filters; Yet Winograd halves precision and FFT does not. I would love it if any answer could address how numerical analysts go about proving error bounds due to roundoff in such linear, "correct" algorithms. This would expose the flaws in my thinking that leave me so baffled.

[1] Arithmetic Complexity of Computation, Schmuel Winograd

[2] Fast Algorithms for Convolutional Neural Networks, Andrew Lavin & Scott Gray

[3] https://github.com/Maratyszcza/NNPACK/issues/8

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.