From Spectral Methods to Sample Complexity Bounds for Fourier Neural Operators

Problem Statement
Fourier Neural Operators (FNOs) have demonstrated empirical success in learning solution operators for partial differential equations (PDEs), specifically mapping initial states to future states in dissipative evolution equations. However, a rigorous theoretical understanding of the structural conditions under which FNOs can efficiently approximate and learn these operators remains incomplete. While general operator learning faces "curse of dimensionality" barriers—where learning $k$-times Fréchet differentiable or Lipschitz operators requires exponentially many samples in the worst case—this paper seeks to identify specific structural properties of dissipative PDEs that allow FNOs to achieve polynomial sample complexity.

Methodology
The authors establish a connection between classical spectral approximation theory and modern operator learning. Their approach proceeds in four logical steps:

1. Spectral Discretization: They introduce classes of semi-implicit Fourier spectral schemes that discretize dissipative evolution equations in space and time. These schemes treat linear dissipation terms implicitly and nonlinear reaction/transport terms explicitly, often with stabilization.
2. Operator Class Definition: They define specific classes of solution operators ($S_{poly}$ for polynomial nonlinearities and $S_{smooth}$ for general smooth nonlinearities) characterized by their ability to be approximated by iterating stable and accurate spectral steps. These classes are defined by parameters governing dissipation strength, nonlinearity smoothness, and input space regularity.
3. FNO Construction: They construct FNOs that emulate single steps of these spectral methods. By composing these single-step FNOs, they create architectures capable of approximating the full time-$T$ solution map. The construction leverages the fact that FNOs can efficiently represent linear operators diagonalizable in the Fourier basis and approximate nonlinearities via pointwise neural networks.
4. Learning Guarantees: They combine the constructive approximation bounds with metric-entropy estimates to derive learning guarantees for empirical risk minimization (ERM) over the defined FNO classes.

Key Contributions

• Spectral-Method-Based Operator Classes: The paper introduces a broad class of time-$T$ solution operators defined through stable semi-implicit Fourier spectral approximations. This class captures the numerical structure shared by many dissipative equations while remaining general enough to include standard nonlinear PDEs.
• Uniform Approximation Bounds: For equations with polynomial nonlinearities, the authors prove that every operator in the defined class can be uniformly approximated by an FNO. The required network size (depth, width, and weight magnitude) is quantified in terms of the desired accuracy and the parameters defining the operator class (Theorem 3.4).
• Polynomial Sample Complexity: By combining approximation bounds with metric-entropy estimates, the paper establishes that FNOs trained via ERM can learn operators in these classes with polynomial sample complexity. For polynomial nonlinearities, the learning rates depend primarily on the Sobolev smoothness of the input space and the dimension of the physical domain (Theorem 3.6).
• Extension to General Smooth Nonlinearities: The framework is extended to equations with non-polynomial smooth nonlinearities (Theorem 4.3, 4.4). In this setting, polynomial sample complexity is preserved, though the rates additionally depend on the smoothness of the nonlinearity and the strength of dissipation.
• Concrete Applications: The theory is applied to verify that the time-$T$ solution maps of the Navier–Stokes, Allen–Cahn, and Cahn–Hilliard equations fit within the abstract framework, providing concrete learning guarantees for these specific PDEs. Additionally, the theory is applied to the Cahn–Hilliard equation with a logarithmic potential, a case involving singularities that requires careful handling.

Results

• Approximation: The paper provides quantitative bounds showing that FNOs can approximate the solution operators of dissipative PDEs to any accuracy $\epsilon$ with network sizes that scale polynomially in $\epsilon^{-1}$ (for polynomial nonlinearities) or with slightly more complex dependencies for general smooth nonlinearities.
• Learning Rates: For polynomial nonlinearities, the generalization error decays at a rate of $O(M^{-1/(6 + 2d/a)})$, where $M$ is the number of samples, $d$ is the physical dimension, and $a$ is the Sobolev smoothness of the input space. This contrasts with negative results for generic operators, which require exponential sample complexity.
• Specific PDEs:
  • Navier–Stokes: Learning rates depend on $a=2$ and $d=2$, yielding a rate of $M^{-1/8}$.
  • Allen–Cahn: With $a=4$ and $d=2$, the rate is $M^{-1/7}$.
  • Cahn–Hilliard: Similarly yields $M^{-1/7}$ for $a=4, d=2$.
  • Logarithmic Cahn–Hilliard: The rate depends on the smoothness of the nonlinearity $\alpha$, yielding $M^{-1/(7 + 24/(5\alpha))}$.

Significance
The paper claims that "stable spectral approximability" is a broad structural condition that enables FNOs to learn nonlinear evolution operators efficiently. By formalizing the premise that FNOs can efficiently learn operators whenever those operators admit stable and accurate spectral discretizations, the work bridges the gap between classical numerical analysis and modern deep learning theory. The results explain when and why FNOs succeed in learning PDE solution operators, moving beyond specific empirical successes to provide uniform guarantees over families of equations rather than single fixed PDEs. The authors note that these guarantees are particularly relevant for data-driven surrogate forecasting models used in data assimilation, suggesting that future work could extend these bounds to higher-order Sobolev norms to better couple with data assimilation accuracy guarantees.