Towards Sharp Minimax Risk Bounds for Operator Learning

Ben Adcock, Gregor Maier, Rahul ParhiarXiv 2025 · DOI · arXiv

In the burgeoning field of machine learning for scientific computing, "operator learning" has become a superstar. Whether it's predicting fluid dynamics or mapping boundary conditions to PDE solutions, we are increasingly asking models to learn maps between infinite-dimensional function spaces. But how many samples do we actually need to do this reliably?

A new paper by Ben Adcock, Gregor Maier, and Rahul Parhi, titled "Towards Sharp Minimax Risk Bounds for Operator Learning," provides a sobering mathematical answer: operator learning is subject to a brutal "curse of sample complexity."

TL;DR

The authors establish the first comprehensive minimax theory for learning Lipschitz operators between Hilbert spaces. They prove that for generic operators, the error cannot decay at any algebraic rate relative to the number of samples—meaning that even with "smooth" operators, you might need an astronomical amount of data to achieve high precision.

What Problem Does This Paper Address?

In classical non-parametric regression (like fitting a curve to points in 2D), we know exactly how fast the error drops as we add more data. Usually, the error looks something like $m^{-s/(2s+d)}$, where $m$ is the number of samples, $s$ is smoothness, and $d$ is the dimension.

In operator learning, the "dimension" $d$ is effectively infinite because the inputs and outputs are functions, not vectors. This paper asks: What is the fundamental limit of how well any algorithm can learn an operator from $m$ noisy samples?

The authors focus on the class of uniformly bounded Lipschitz operators—a natural and widely used model for physical systems—and investigate how the geometry of the input data (specifically the eigenvalues of its covariance) dictates the learning rate.

Methods

The researchers approached this as a minimax estimation problem, seeking to find the "best of the worst-case" error.

  1. Lower Bounds: To prove the problem is hard, they used Fano’s inequality. They constructed a set of "bump" functions in the infinite-dimensional space that are far apart from each other but hard for any estimator to distinguish given noisy data.
  2. Upper Bounds: To prove the bounds are "sharp" (or nearly so), they constructed a histogram-based estimator adapted for infinite-dimensional Hilbert spaces.
  3. Noise Models: They accounted for two types of noise: Hilbert-valued Gaussian noise (where the noise itself is a "nice" function) and Gaussian white noise (which is much more "rugged" and technically challenging to handle).

Datasets

As a theoretical work, this paper does not use empirical datasets. Instead, it defines the problem over separable Hilbert spaces (like $L^2$) and assumes the input data is distributed according to a measure $\mu$ with a specific eigenvalue decay $\lambda_i$ in its covariance operator.

Key Insights and Ideas

  • The Curse of Sample Complexity: The most striking takeaway is that for generic Lipschitz operators, the minimax risk cannot decay at an algebraic rate ($m^{-q}$). No matter how much data you throw at the problem, the error will eventually decrease slower than any power of $1/m$.
  • Eigenvalues are the Throttle: The speed of learning is entirely governed by how fast the eigenvalues of the input data's covariance decay.
  • If eigenvalues decay algebraically (slowly), the error decays incredibly slowly (logarithmically).
  • If eigenvalues decay exponentially (fast), the error decays "super-logarithmically" but still sub-algebraically.
  • Smoothness is Not a Silver Bullet: In finite dimensions, more smoothness (higher Hölder regularity) usually leads to much faster learning rates. Surprisingly, the authors show that for operators, higher regularity does not improve the minimax rate over the basic Lipschitz case (up to constants). The infinite-dimensional nature of the problem simply "swallows" the benefits of smoothness.

Key Results

The paper provides a tight characterization of the log-minimax risk ($L_m$). For the case where eigenvalues decay exponentially ($\lambda_i = \exp(-\tau i^\omega)$), they show:

$$L_m \approx \left( \log(m/\sigma^2) \right)^{\frac{\omega}{\omega+1}}$$

This result is "sharp," meaning the upper and lower bounds match. It quantifies exactly how the "effective dimension" of the input data (represented by $\omega$) makes the problem harder or easier.

Essentially, unless your data is extremely "low-dimensional" (meaning the eigenvalues decay very, very fast), you are trapped in a regime where doubling your data provides diminishing returns.

Limitations and Future Work

  • Non-Sharpness in Algebraic Regimes: While the bounds for exponential decay are tight, the authors acknowledge that their lower bounds for algebraically decaying eigenvalues are likely not yet sharp. They suspect an artifact in the proof related to how the dimension $d$ is handled.
  • Constants: The theory focuses on the rate of decay. Finding the exact constants (the "speed limit" in absolute terms) remains an open challenge.
  • Other Operator Classes: The authors suggest extending this framework to other classes, such as holomorphic operators (which are even smoother than Hölder) or Besov classes, where the fundamental limits are still unknown.

For practitioners, this paper serves as a theoretical warning: when building neural operators, the "infinite-dimensional" nature of the task is a formidable opponent that even the cleverest architectures cannot entirely circumvent.

Summary updated

Abstract

We develop a minimax theory for operator learning, where the goal is to estimate an unknown operator between separable Hilbert spaces from finitely many noisy input-output samples. For uniformly bounded Lipschitz operators, we prove information-theoretic lower bounds together with matching or near-matching upper bounds, covering both fixed and random designs under Hilbert-valued Gaussian noise and Gaussian white noise errors. The rates are controlled by the spectrum of the covariance operator of the measure that defines the error metric. Our setup is very general and allows for measures with unbounded support. A key implication is a curse of sample complexity, which shows that the minimax risk for generic Lipschitz operators cannot decay at any algebraic rate in the sample size. We obtain sharp characterizations when the covariance spectrum decays exponentially and provide general upper and lower bounds in slower-decay regimes. Finally, we show that assuming higher regularity, i.e., Hölder smoothness, does not improve minimax rates over the Lipschitz case, up to potential constants. Thus, we show that learning operators of any finite regularity necessarily suffers a curse of sample complexity.
BibTeX
@misc{adcock2025towards,
  author = {Ben Adcock and Gregor Maier and Rahul Parhi},
  title = {{Towards Sharp Minimax Risk Bounds for Operator Learning}},
  year = {2025},
  eprint = {2512.17805},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.17805},
}
Figure