Near-Optimal Learning of Gaussian Sobolev Operators

• URL: http://arxiv.org/abs/2607.11921v1
• Date: Wed, 08 Jul 2026 23:14:42 GMT
• Title: Near-Optimal Learning of Gaussian Sobolev Operators
• Abstract summary: We present a fully data-driven algorithm, termed Hermite-PCA approximation, for learning Gaussian Sobolev operators with near-optimal sample complexity.<n>It employs principal component analysis and weighted least-squares methods and is therefore computationally efficient.<n>We provide a full error analysis of this algorithm, taking into account all sources of error, along with numerical experiments that verify our theoretical results.
• Score: 3.6777052815434534
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A key question in operator learning is how to design surrogate operators with provable approximation guarantees in reasonable computational time. Whereas smooth operators can be approximated efficiently, i.e., with at least algebraic convergence in the amount of training data, learning finitely regular operators is known to be less efficient. The reason is an intrinsic curse of sample complexity, which allows only subalgebraic sample complexity rates. This fact makes it all the more important to develop algorithms which provably achieve these rates. In this work, we present a fully data-driven algorithm, termed Hermite-PCA approximation, for learning Gaussian Sobolev operators with near-optimal sample complexity. It employs principal component analysis and weighted least-squares methods and is therefore computationally efficient. Moreover, it is spectral, in the sense that it achieves faster (and near-optimal) convergence the higher the Sobolev regularity. We provide a full error analysis of this algorithm, taking into account all sources of error, along with numerical experiments that verify our theoretical results and empirically confirm the efficacy of Hermite-PCA approximation for learning Sobolev operators.

Related papers

• Convergence Rates for Learning Pseudo-Differential Operators [1.1559118525005183]
  We formulate learning over elliptic pseudo-differential operators as a structured infinite-dimensional regression problem with multiscale sparsity.<n>We show that the learned operator induces an efficient and stable Galerkin solver whose numerical error matches its statistical accuracy.<n>Our results contribute to bringing together operator learning, data-driven solvers, and wavelet methods in scientific computing.
  arXiv  Detail & Related papers  (2026-01-08T01:21:08Z)
• Cauchy Random Features for Operator Learning in Sobolev Space [9.616322090804436]
  We propose a random feature operator learning method with theoretical guarantees and error bounds.<n>Compared to kernel-based method and neural network methods, the proposed method can obtain similar or better test errors.
  arXiv  Detail & Related papers  (2025-03-01T02:14:25Z)
• The Sample Complexity of Learning Lipschitz Operators with respect to Gaussian Measures [1.037768322019687]
  We study the approximation of Lipschitz operators with respect to Gaussian measures.<n>We study general reconstruction strategies of Lipschitz operators from $m$ arbitrary (potentially adaptive) linear samples.
  arXiv  Detail & Related papers  (2024-10-30T20:32:30Z)
• Operator Learning of Lipschitz Operators: An Information-Theoretic Perspective [2.375038919274297]
  This work addresses the complexity of neural operator approximations for the general class of Lipschitz continuous operators. Our main contribution establishes lower bounds on the metric entropy of Lipschitz operators in two approximation settings. It is shown that, regardless of the activation function used, neural operator architectures attaining an approximation accuracy $epsilon$ must have a size that is exponentially large in $epsilon-1$.
  arXiv  Detail & Related papers  (2024-06-26T23:36:46Z)
• Data Complexity Estimates for Operator Learning [4.056627267544063]
  We develop theory to study the data complexity of operator learning. We show that on a narrower class of operators, efficiently approximated by FNO in terms of the number of tunable parameters, efficient operator learning is attainable in data complexity as well.
  arXiv  Detail & Related papers  (2024-05-25T00:16:21Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  We study representation learning in partially observable Markov Decision Processes (POMDPs) We first present an algorithm for decodable POMDPs that combines maximum likelihood estimation (MLE) and optimism in the face of uncertainty (OFU) We then show how to adapt this algorithm to also work in the broader class of $gamma$-observable POMDPs.
  arXiv  Detail & Related papers  (2023-06-21T16:04:03Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Lassoed Tree Boosting [53.56229983630983]
  We prove that a gradient boosted tree algorithm with early stopping faster than $n-1/4$ L2 convergence in the large nonparametric space of cadlag functions of bounded sectional variation. Our convergence proofs are based on a novel, general theorem on early stopping with empirical loss minimizers of nested Donsker classes.
  arXiv  Detail & Related papers  (2022-05-22T00:34:41Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  We study efficient algorithms for reinforcement learning in decision processes whose complexity is independent of the number of states. We give an efficient algorithm that is capable of improving the accuracy of such weak learning methods.
  arXiv  Detail & Related papers  (2021-08-22T16:00:45Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.