91–100 of 175 posts
Earlier quoted context omitted.
Essentially leveraging Convolution theorem. Same philosophy pops up in many places, e.g. DFT calculations
Yep, it's very common to use this. we used it for grid based pairwise interactions since it turns N^2 op into N log N.
Basically leverages convolution theorem[0]: expensive convolutions in direct space becomes simple multiplications in reciprocal space, and vice versa. Whereever you have a convolution operation on your data, transform them to the conjugate domain to turn it into multiplication. In other words, work in the domain that is natural to your data. [0] https://en.wikipedia.org/wiki/Convolution_theorem
Maybe for self-attention and for their use cases n is much larger, I didn't read the article. But you still have to deal with complex numbers.
Google introduced this idea in 2022 with "FNet: Mixing Tokens with Fourier Transforms" [0]. Later they found out that, performance of their TPU(s) for matrix multiplication was faster than FFT in the most scenarios. [0]: https://arxiv.org/abs/2105.03824
Referenced in this paper: "Overall, while approaches such as FNet, Performer, and sparse transformers demonstrate that either fixed or approximate token mixing can reduce computational overhead, our adaptive spectral filtering strategy uniquely merges the efficiency of the FFT with a learnable, input-dependent spectral filter. This provides a compelling combination of scalability and adaptability, which is crucial fo…
Pretty lame.
Google introduced this idea in 2022 with "FNet: Mixing Tokens with Fourier Transforms" [0]. Later they found out that, performance of their TPU(s) for matrix multiplication was faster than FFT in the most scenarios. [0]: https://arxiv.org/abs/2105.03824
>The TPU is so inefficient at FTs that the researchers did not use the FFT algorithm on sequences > on an Nvidia Quadro P6000 GPU, the FT was responsible for up to 30% of the inference time on the FNet architecture [0]
This company [0] claimed in 2021 they could squash inference time by 40% if google would use their light chips on TPU. Perhaps more if FFTNet does more heavy lifting.
[0]: https://scribe.rip/optalysys/attention-fourier-transforms-a-...
This guy's has had a lot bangers lately.
Overall, i like this guys papers but they strike me as someone who is very smart but hasnt looked through the literature carefully. Many of the techniques he is proposing were already done about 5-6 years ago. However, I imagine that because the field is flooded with new humans, they are not aware of this research or think it will lead to a fruitful end (which many other researchers have already thought of this and i…
This reminds me of some HN comments about rocketry ideas and in the thread one of the comments was “Everything in rocket science has been theorized/tried by some Russian scientist 40-50 years ago” and it still gives me a chuckle.
Earlier quoted context omitted.
Overall, i like this guys papers but they strike me as someone who is very smart but hasnt looked through the literature carefully. Many of the techniques he is proposing were already done about 5-6 years ago. However, I imagine that because the field is flooded with new humans, they are not aware of this research or think it will lead to a fruitful end (which many other researchers have already thought of this and i…
> Overall, it seems we are starting to recycle ideas because there isnt enough lit review and or mentoring from senior deep learning / ML folks who can quickly look at a paper and tell the author where the work has been already investigated. Arguably, the literature synthesis and knowledge discovery problem has been overwhelming in many fields for a long time; but I wonder if, in ML lately, an accelerated (if not fra…
Google introduced this idea in 2022 with "FNet: Mixing Tokens with Fourier Transforms" [0]. Later they found out that, performance of their TPU(s) for matrix multiplication was faster than FFT in the most scenarios. [0]: https://arxiv.org/abs/2105.03824
I would guess that the FFT scales better as you increase the number of tokens in the context window. Interesting Google's models outperform their competitors on context size.
Basically leverages convolution theorem[0]: expensive convolutions in direct space becomes simple multiplications in reciprocal space, and vice versa. Whereever you have a convolution operation on your data, transform them to the conjugate domain to turn it into multiplication. In other words, work in the domain that is natural to your data. [0] https://en.wikipedia.org/wiki/Convolution_theorem
Yeah, but the savings are theoretical. You turn a O(n^2) operation into O(nlog n). Sounds great until you realize that n is three on average. To boot, you have to use complex numbers for calculations which are also less numerically stable. So, to the best of my knowledge, FFT is not a win for ordinary convolution. Maybe for self-attention and for their use cases n is much larger, I didn't read the article. But you st…
Earlier quoted context omitted.
Yeah, but the savings are theoretical. You turn a O(n^2) operation into O(nlog n). Sounds great until you realize that n is three on average. To boot, you have to use complex numbers for calculations which are also less numerically stable. So, to the best of my knowledge, FFT is not a win for ordinary convolution. Maybe for self-attention and for their use cases n is much larger, I didn't read the article. But you st…
3^2 / (3*log(3)) = >6x performance improvement and, if three is a linear average, I'd expect the average improvement to be even higher. I know real world computation doesn't answer to the simple scaling equations and there may well be a constant factor >6 that eats the gains, but I don't think the two Big Os and a n=3 are sufficient to make your case.
> I know real world computation doesn't answer to the simple scaling equations ... but
No, no "but". This defeats the entire claim, and you can't just "but" it back.
Also, you appear to have used base-10 log for Log(3). It's almost certain that base-2 is more appropriate, leading to a factor of 1.8x, not 6x. But of course Log_1000(n) and Log_2(n) have the same Big-O, which is why the base is left off, so you really just cannot say anything specific at all. O(n^2) might be faster than O(n*log(n)) up to n = Graham's number.