Computing convolutions using FFTs is efficient for large kernels (or filters). Most convolutions in popular ML models have small kernels, a regime where it is t

Computing convolutions using FFTs is efficient for large kernels (or filters). Most convolutions in popular ML models have small kernels, a regime where it is typically more efficient to reformulate the convolution as a matrix multiplication. I think your complexity argument is correct for N=pixels=kernel size. But typically, pixels>>kernel size. Disclosure: I work at Arm optimising open source ML frameworks. Opinions are my own.