# The Sample Complexity of Learning Lipschitz Operators with respect to Gaussian Measures

arXiv: https://arxiv.org/abs/2410.23440 · HTML: https://mlsanity.com/paper/2410.23440/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 57 references that are in the map.
- First posted on arXiv 30 Oct 2024.

## Builds on (most cited first, 20 of 20)

- [Fourier Neural Operator for Parametric Partial Differential Equations](https://mlsanity.com/paper/2010.08895/) (2020)
- [DeepONet: Learning nonlinear operators for identifying differential equations based on the universal approximation theorem of operators](https://mlsanity.com/paper/1910.03193/) (2019)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Model Reduction and Neural Networks for Parametric PDEs](https://mlsanity.com/paper/2005.03180/) (2020)
- [Operator Learning: Algorithms and Analysis](https://mlsanity.com/paper/2402.15715/) (2024)
- [A Mathematical Guide to Operator Learning](https://mlsanity.com/paper/2312.14688/) (2023)
- [Generic bounds on the approximation error for physics-informed (and) operator learning](https://mlsanity.com/paper/2205.11393/) (2022)
- [Deep Nonparametric Estimation of Operators between Infinite Dimensional Spaces](https://mlsanity.com/paper/2201.00217/) (2022)
- [Operator learning with PCA-Net: upper and lower complexity bounds](https://mlsanity.com/paper/2303.16317/) (2023)
- [Nonlocality and Nonlinearity Implies Universality in Operator Learning](https://mlsanity.com/paper/2304.13221/) (2023)
- [The Parametric Complexity of Operator Learning](https://mlsanity.com/paper/2306.15924/) (2023)
- [Elliptic PDE learning is provably data-efficient](https://mlsanity.com/paper/2302.12888/) (2023)
- [Data Complexity Estimates for Operator Learning](https://mlsanity.com/paper/2405.15992/) (2024)
- [Deep Operator Network Approximation Rates for Lipschitz Operators](https://mlsanity.com/paper/2307.09835/) (2023)
- [Neural and spectral operator surrogates: unified construction and expression rate bounds](https://mlsanity.com/paper/2207.04950/) (2022)
- [Optimal deep learning of holomorphic operators between Banach spaces](https://mlsanity.com/paper/2406.13928/) (2024)
- [Operator Learning of Lipschitz Operators: An Information-Theoretic Perspective](https://mlsanity.com/paper/2406.18794/) (2024)
- [A practical existence theorem for reduced order models based on convolutional autoencoders](https://mlsanity.com/paper/2402.00435/) (2024)
- [On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples](https://mlsanity.com/paper/2203.13908/) (2022)
- [Learning smooth functions in high dimensions: from sparse polynomials to deep neural networks](https://mlsanity.com/paper/2404.03761/) (2024)

## Built on by (most cited first, 11 of 11)

- [Towards Sharp Minimax Risk Bounds for Operator Learning](https://mlsanity.com/paper/2512.17805/) (2025)
- [A short tour of operator learning theory: Convergence rates, statistical limits, and open questions](https://mlsanity.com/paper/2603.00819/) (2026)
- [Multiple Neural Operators Achieve Near-Optimal Rates for Multi-Task Learning](https://mlsanity.com/paper/2605.22724/) (2026)
- [Generalization Bounds and Statistical Guarantees for Multi-Task and Multiple Operator Learning with MNO Networks](https://mlsanity.com/paper/2604.01961/) (2026)
- [Variation Spaces for Encoder--Decoder Neural Operators: Approximation and Generalization](https://mlsanity.com/paper/2606.01244/) (2026)
- [Optimal Multiscale Learning of Linear Operators](https://mlsanity.com/paper/2606.16913/) (2026)
- [Upper Generalization Bounds for Neural Oscillators](https://mlsanity.com/paper/2603.09742/) (2026)
- [Cellular Sheaf Neural Operators for Structure-Preserving Surrogate Modeling of Constrained PDEs](https://mlsanity.com/paper/2606.00937/) (2026)
- [From Spectral Methods to Sample Complexity Bounds for Fourier Neural Operators](https://mlsanity.com/paper/2607.00320/) (2026)
- [Into the danger zone: stable extrapolation in high-dimensional function and operator learning](https://mlsanity.com/paper/2609.36709/) (2026)
- [Transmission Factors for Lossy Compression of PDE Training Data: Measuring What Reaches a Trained Operator](https://mlsanity.com/paper/2610.06095/) (2026)

## Abstract (arXiv)

Operator learning, the approximation of mappings between infinite-dimensional function spaces using machine learning, has gained increasing research attention in recent years. Operator approximations can serve as efficient surrogate models for problems in computational science and engineering, complementing traditional methods. However, despite their empirical success, our understanding of the underlying mathematical theory is in large part still incomplete. In this paper, we study the approximation of Lipschitz operators with respect to Gaussian measures. We prove higher Gaussian Sobolev regularity of Lipschitz operators and establish lower and upper bounds on the Hermite polynomial approximation error. We then study general reconstruction strategies of Lipschitz operators from m arbitrary (potentially adaptive) linear samples. As a key finding, we tightly characterize the corresponding sample complexity, that is, the smallest achievable worst-case error among all possible choices of (adaptive) sampling and reconstruction strategies, in terms of m. As a consequence, we identify an inherent curse of sample complexity: No method to approximate Lipschitz operators based on m linear samples can achieve algebraic convergence rates in m. On the positive side, we prove that a sufficiently fast spectral decay of the covariance operator of the underlying Gaussian measure guarantees convergence rates which are arbitrarily close to any algebraic rate. Overall, by tightly characterizing the sample complexity, our work confirms the intrinsic difficulty of learning Lipschitz operators, regardless of the data or learning technique.