Reproduce “Butterfly-Net: Optimal Function Representation Based on Convolutional Neural Networks” on OpenResearch

About this paper

Yingzhou Li, Xiuyuan Cheng, Jianfeng Lu

Butterfly-Net introduces a convolutional neural network architecture inspired by the Butterfly algorithm, demonstrating near-optimal O(K log N) parameter and O(N log N) computational complexity for approximating Fourier transforms and general functions by reducing effective dimensionality. This framework provides theoretical guarantees for exponential error decay and leverages a principled initialization strategy for superior training and generalization.

Key insights

• The 'complementary low-rank property' of the Fourier kernel, exploited by the Butterfly algorithm, can be effectively translated into a deep learning architecture with structured sparsity and hierarchical connections.
• A principled, mathematically-informed initialization strategy (Butterfly initialization) can dramatically improve neural network training efficiency, convergence, and final accuracy compared to random initialization.
• Deep neural networks can achieve effective dimension reduction for function approximation by extracting a small number of relevant frequency-domain features (K) from high-dimensional inputs (N), leading to complexity dependent on K rather than N.

Summary by alphaXiv.