[jondea]

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.