Elliptic PDE learning is provably data-efficient

Nicolas Boullé, Diana Halikias, Alex Townsend

Abstract

Recent empirical successes in learning solution operators for Partial Differential Equations (PDEs) have challenged the conventional wisdom that deep learning requires massive datasets. While models like Fourier Neural Operators (FNO) and DeepONets demonstrate high accuracy with surprisingly few samples, a theoretical explanation for this efficiency has remained elusive. This paper provides the first rigorous proof that learning the solution operators of elliptic PDEs is inherently data-efficient. By leveraging the hierarchical low-rank structure of Green’s functions and randomized numerical linear algebra, we show that an $\epsilon$-approximation of a 3D elliptic PDE operator can be achieved with a poly-logarithmic number of training samples—specifically $O(\log^5(1/\epsilon))$.

Introduction

In the burgeoning field of "PDE learning," neural networks are trained to map input functions (like forcing terms or boundary conditions) to output solutions. Despite the "curse of dimensionality" typically associated with high-dimensional operator learning, empirical results have shown that these models generalize remarkably well even when trained on small datasets. Prior theoretical frameworks suggested that the sample complexity should scale polynomially with the desired error (e.g., $O(\epsilon^{-6})$ for 3D problems), a prediction that fails to account for the observed performance of modern architectures.

This work bridges the gap between theory and practice by demonstrating that the underlying physics of elliptic PDEs imposes structural constraints that act as a natural regularizer. We prove that the solution operators for a broad class of elliptic PDEs can be learned with exponential efficiency.

The Structure of Elliptic Operators

The core of our analysis centers on the Green’s function $G(x, y)$, which serves as the kernel for the solution operator of a PDE. For elliptic PDEs, such as the steady-state heat equation or the Poisson equation, the Green’s function possesses a critical property: off-diagonal decay.

While $G(x, y)$ may be singular or highly complex near the diagonal (where $x \approx y$), it becomes increasingly smooth and low-rank as the distance between $x$ and $y$ increases. This physical property implies that the operator can be represented using a hierarchical multi-scale structure. By partitioning the domain into a tree-like hierarchy, the operator can be decomposed into a collection of low-rank blocks, significantly reducing the effective dimensionality of the learning problem.

The Peeling Algorithm: Learning via Randomized Sketches

To translate this structural insight into a complexity bound, we adapt the "Peeling Algorithm" from randomized numerical linear algebra to the infinite-dimensional setting of operators. The algorithm works by "peeling" away layers of the hierarchical operator level-by-level:

  1. Randomized Sketching: The operator is probed with a small number of random input functions (forcing terms sampled from Gaussian Processes).
  2. Hierarchical Reconstruction: Using the outputs of these sketches, the algorithm employs randomized Singular Value Decomposition (SVD) to reconstruct the low-rank blocks of the Green’s function.
  3. Adaptive Precision: To prevent error accumulation across the hierarchy, the algorithm employs higher precision at coarser levels, ensuring that the final approximation remains within the $\epsilon$ tolerance.

This approach allows for the reconstruction of the entire operator using only a few random input-output pairs, leading to the $O(\log^5(1/\epsilon))$ sample complexity.

Empirical Validation and Insights

The theoretical findings are supported by numerical experiments on 2D Poisson equations and 3D uniformly elliptic PDEs with variable coefficients.

  • Architecture Performance: Comparisons between Fourier Neural Operators (FNO), DeepONets, and GreenLearning reveal that while all architectures benefit from the underlying physics, those that can better exploit hierarchical or local structures (like DeepONet and GreenLearning) show the predicted exponential decay in error relative to training set size, significantly outperforming FNO on small datasets.
  • Physics as a Regularizer: The study confirms that the "search space" for the learning algorithm is effectively constrained by the decay properties of the Green's function. This explains why even general-purpose neural networks can find accurate solutions without needing millions of examples.
  • Reliability: The randomized nature of the learning process is shown to be robust, with a failure probability that is negligible for any practical application.

Conclusion and Future Directions

This work provides a mathematical foundation for the observed data efficiency in PDE learning, moving the field beyond empirical observation toward provable guarantees. However, several challenges remain:

  • Hyperbolic PDEs: Unlike elliptic systems, hyperbolic PDEs (such as wave equations) do not generally exhibit the same off-diagonal decay in their Green’s functions, making them significantly harder to learn with the same efficiency.
  • Noise Robustness: The current proof assumes high-quality, noise-free data. Extending these guarantees to noisy, real-world experimental data is a vital next step.
  • Informed Architecture Design: These results suggest that future neural network architectures could be explicitly designed to mirror the hierarchical, low-rank structure of physical operators to further maximize data efficiency.

Summary updated

Abstract

Partial differential equations (PDE) learning is an emerging field that combines physics and machine learning to recover unknown physical systems from experimental data. While deep learning models traditionally require copious amounts of training data, recent PDE learning techniques achieve spectacular results with limited data availability. Still, these results are empirical. Our work provides theoretical guarantees on the number of input–output training pairs required in PDE learning. Specifically, we exploit randomized numerical linear algebra and PDE theory to derive a provably data-efficient algorithm that recovers solution operators of three-dimensional uniformly elliptic PDEs from input–output data and achieves an exponential convergence rate of the error with respect to the size of the training dataset with an exceptionally high probability of success.
BibTeX
@inproceedings{boulle2023elliptic,
  author = {Nicolas Boullé and Diana Halikias and Alex Townsend},
  title = {{Elliptic PDE learning is provably data-efficient}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2023},
  url = {https://openreview.net/forum?id=VlqOXhcT3V},
}
Figure