🤖 machine learning

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

This paper establishes that learning Lipschitz operators from linear samples under Gaussian measures suffers from an inherent curse of sample complexity, proving that no method can achieve algebraic convergence rates unless the underlying covariance operator exhibits sufficiently fast spectral decay.

Original authors: Ben Adcock, Michael Griebel, Gregor Maier

Published 2026-09-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ben Adcock, Michael Griebel, Gregor Maier

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern science and engineering, computers are increasingly asked to solve problems that involve not just single numbers, but entire shapes, waves, and fields of data. Think of predicting how a fluid flows around a wing, or how heat spreads through a complex material. These are not simple calculations; they are mappings between infinite-dimensional spaces, where the input is a whole function and the output is another whole function. For years, researchers have turned to machine learning to act as a shortcut, training artificial intelligence to learn these complex mappings and serve as a fast, efficient substitute for traditional, slow simulations. This field, known as operator learning, has shown great promise in practice, with neural networks successfully mimicking physical laws in various applications. However, a fundamental question has lingered: just how much data does a computer actually need to learn these rules reliably, and are there hard limits to what it can achieve?

A new study by researchers at Simon Fraser University and the University of Bonn tackles this question by focusing on a specific, challenging class of rules: those that are "Lipschitz continuous." In plain terms, this means the rules are stable; a small change in the input leads to a proportionally small change in the output, preventing the system from exploding into chaos. These rules appear frequently in real-world physics, such as in problems involving obstacles, like a membrane stretched over a barrier, or in financial models. The researchers set out to determine the theoretical minimum amount of data required to learn such rules accurately when the inputs are drawn from a standard Gaussian distribution, a bell-curve-like probability that is the most common choice for modeling uncertainty in science.

The team approached the problem by treating the learning process as a mathematical reconstruction task. They asked: if you are allowed to take a certain number of measurements from an unknown rule, what is the best possible accuracy you can hope to achieve? They investigated whether using more data would allow the error to shrink at a steady, predictable pace, known as an algebraic rate. In many scientific contexts, doubling the data might halve the error, or improve it by a power of two. The researchers proved, however, that for Lipschitz operators, achieving true algebraic convergence is impossible. They demonstrated that no matter how clever the learning algorithm is, or how the data points are chosen, it is fundamentally impossible to achieve these steady, algebraic improvements in accuracy just by increasing the number of samples under typical conditions.

This finding reveals a deep "curse of sample complexity." The study shows that the error in learning these operators generally cannot decay at an algebraic rate. However, the researchers identified a crucial exception: if the underlying data distribution decays incredibly fast—specifically, if the variance of the data drops off at a double-exponential rate—then it becomes possible to approach algebraic convergence rates. In this highly specific scenario, the error can be made to shrink almost as fast as desired, though never quite reaching the ideal algebraic speed. This suggests that while learning these operators is inherently difficult, it is not hopeless, provided the data itself is exceptionally well-behaved.

The work also clarifies the role of adaptivity in learning. A common intuition in data science is that being able to choose your next measurement based on previous results should always help. The researchers proved that for this specific problem, adaptivity offers no advantage at all. The best possible accuracy achievable with a smart, adaptive strategy is exactly the same as what could be achieved with a fixed, non-adaptive set of measurements. This confirms that the difficulty lies in the nature of the rules being learned, not in the strategy used to gather data.

Ultimately, this paper draws a clear boundary around what is possible in operator learning. It confirms that for a broad and important class of physical and mathematical rules, the path to high accuracy is paved with a fundamental barrier: no amount of data, no matter how intelligently collected, will yield the rapid, steady improvements that machine learning practitioners often expect, unless the data possesses extremely rare spectral properties. The study does not say these problems cannot be solved, but it establishes that they require a different mindset, one that accepts that learning Lipschitz operators is a task of extreme difficulty where the usual shortcuts of data accumulation simply do not apply.

Technical Summary: The Sample Complexity of Learning Lipschitz Operators with respect to Gaussian Measures

Problem Statement
The paper addresses the theoretical limitations of learning (approximating) Lipschitz continuous operators mapping between infinite-dimensional separable Hilbert spaces, $X$ and $Y$ . Specifically, it investigates the sample complexity of this task: determining the smallest achievable worst-case $L^2_\mu$ approximation error when reconstructing an operator from $m$ arbitrary linear samples, where the input samples are drawn from a centered, nondegenerate Gaussian measure $\mu$ . While neural operators (e.g., DeepONet, FNO) have shown empirical success, the theoretical understanding of their convergence rates for non-holomorphic operators, particularly Lipschitz ones, remains incomplete. Previous work has established "curse of dimensionality" or "curse of parametric complexity" results for bounded Lipschitz operators, but this paper extends the analysis to potentially unbounded Lipschitz operators under general Gaussian measures.

Methodology
The authors employ tools from infinite-dimensional analysis, information-based complexity (IBC), and approximation theory. The methodology proceeds in three main stages:

Functional Analysis and Regularity: The authors define a weighted Gaussian Sobolev space, $W^{1,2}_{\mu,b}(X;Y)$ , utilizing a sequence of positive bounded weights $b$ . They prove that the space of Lipschitz operators, $\text{Lip}(X;Y)$ , is continuously embedded within this Sobolev space. This embedding allows the authors to characterize Lipschitz operators via their Wiener-Hermite Polynomial Chaos (PC) expansions. The coefficients of these expansions are shown to belong to a weighted $\ell^2$ space, where the weights depend on the PCA eigenvalues of the covariance operator of $\mu$ and the sequence $b$ .
Polynomial Approximation Analysis: Using the $\ell^2$ characterization, the paper analyzes the best $s$ -term approximation of these operators using Hermite polynomials. By ordering the expansion coefficients based on their associated weights, the authors derive tight upper and lower bounds for the approximation error as a function of the number of terms $s$ .
Information-Based Complexity (IBC) Framework: The study generalizes from polynomial approximation to arbitrary reconstruction strategies based on $m$ linear samples (potentially adaptive). The authors define the adaptive $m$ -width, $\Theta_m(K)$ , which quantifies the minimal worst-case error achievable by any reconstruction mapping $T$ given $m$ samples generated by an adaptive sampling operator $L$ . They utilize duality relations between Gelfand, Kolmogorov, and adaptive compressive widths to establish lower bounds for this quantity.

Key Contributions and Results

Embedding of Lipschitz Operators: The paper proves that Lipschitz operators are Gaussian Sobolev operators (Theorem 2.11). Specifically, $\text{Lip}(X;Y) \subset W^{1,2}_{\mu,b}(X;Y)$ , provided the weights $b$ satisfy specific summability conditions (e.g., $b \in \ell^2$ if $Y$ is infinite-dimensional). This result generalizes Rademacher's theorem to infinite-dimensional Gaussian settings.
Curse of Parametric Complexity: The authors establish that no $s$ -term Hermite polynomial expansion can achieve algebraic convergence rates uniformly for all Lipschitz operators as $s \to \infty$ , regardless of the spectral decay of the PCA eigenvalues (Theorem 3.5). While the error decay can be made arbitrarily close to any algebraic rate if the eigenvalues decay sufficiently fast (e.g., double exponentially), it cannot strictly achieve an algebraic rate $O(s^{-\alpha})$ for any $\alpha > 0$ uniformly across the class.
Characterization of Adaptive $m$ -Width: The central result (Theorem 4.4) provides a tight characterization of the adaptive $m$ -width for the unit balls of both Lipschitz and Sobolev operators. The minimal worst-case error is exactly equal to the $(m+1)$ -th largest weight in the ordered sequence of Hermite coefficients, denoted $u_{\pi(m+1)}$ .
- Optimality of Non-Adaptive Linear Sampling: The result implies that adaptive sampling strategies offer no advantage over non-adaptive linear sampling in terms of the worst-case error constant. The optimal strategy is simply the projection onto the first $m$ Hermite polynomials corresponding to the largest weights.
- Equivalence of Spaces: From an IBC perspective, the adaptive $m$ -widths of the unit ball of Lipschitz operators and the unit ball of the full Sobolev space coincide. Thus, restricting the class to Lipschitz operators does not improve the sample complexity compared to the broader Sobolev class.
Curse of Sample Complexity: Consequently, the paper identifies a "curse of sample complexity": No method based on $m$ linear samples (adaptive or not) can achieve algebraic convergence rates for approximating Lipschitz operators under general Gaussian measures (Theorem 4.4 and Section 4.4). This holds regardless of the decay rate of the PCA eigenvalues. However, if the eigenvalues decay sufficiently fast (e.g., double exponentially), convergence rates arbitrarily close to any algebraic rate can be achieved.

Significance and Claims
The paper claims to provide a rigorous theoretical foundation explaining the intrinsic difficulty of learning Lipschitz operators. By tightly characterizing the sample complexity, the work confirms that the lack of algebraic convergence is not a failure of specific algorithms (like neural networks) but an inherent property of the operator class and the Gaussian measure.

The authors emphasize that their results generalize previous findings on bounded Lipschitz operators (e.g., Kovachki et al., 2024a) to unbounded operators and arbitrary Gaussian measures. They highlight that while the "curse" is inherent, it can be mitigated asymptotically if the underlying Gaussian measure exhibits sufficiently rapid spectral decay. The paper concludes that the class of Lipschitz operators may be too large for efficient learning with algebraic rates, suggesting a need for future research into operator classes that better reflect practical applications (which are often non-holomorphic but possess specific structures not captured by general Lipschitz continuity).

The work does not propose new algorithms or experimental validations but rather sets theoretical boundaries for what is achievable, serving as a benchmark for future algorithmic development and a guide for selecting appropriate operator classes in computational science and engineering.

Technical Summary: The Sample Complexity of Learning Lipschitz Operators with respect to Gaussian Measures

More like this