# On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 147 references that are in the map.
- First posted on arXiv 25 Mar 2022.

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

- [Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem](https://mlsanity.com/paper/2101.08286/) (2021)
- [Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark](https://mlsanity.com/paper/2002.01290/) (2020)
- [Deep Neural Networks Are Effective At Learning High-Dimensional Hilbert-Valued Functions From Limited Data](https://mlsanity.com/paper/2012.06081/) (2020)
- [A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods](https://mlsanity.com/paper/1803.00151/) (2018)
- [Automatic selection of basis-adaptive sparse polynomial chaos expansions for engineering applications](https://mlsanity.com/paper/2009.04800/) (2020)
- [Sparse Polynomial Chaos Expansions via Compressed Sensing and D-optimal Design](https://mlsanity.com/paper/1712.10131/) (2017)
- [Compressive sensing adaptation for polynomial chaos expansions](https://mlsanity.com/paper/1801.01961/) (2018)
- [A class of null space conditions for sparse recovery via nonconvex, non-separable minimizations](https://mlsanity.com/paper/1710.07348/) (2017)
- [Enhancing Sparsity of Hermite Polynomial Expansions by Iterative Rotations](https://mlsanity.com/paper/1506.04344/) (2015)
- [WARPd: A linearly convergent first-order method for inverse problems with approximate sharpness conditions](https://mlsanity.com/paper/2110.12437/) (2021)

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

- [Operator Learning: Algorithms and Analysis](https://mlsanity.com/paper/2402.15715/) (2024)
- [Operator Learning of Lipschitz Operators: An Information-Theoretic Perspective](https://mlsanity.com/paper/2406.18794/) (2024)
- [The Sample Complexity of Learning Lipschitz Operators with respect to Gaussian Measures](https://mlsanity.com/paper/2410.23440/) (2024)
- [Learning smooth functions in high dimensions: from sparse polynomials to deep neural networks](https://mlsanity.com/paper/2404.03761/) (2024)
- [A unified framework for learning with nonlinear model classes from arbitrary linear samples](https://mlsanity.com/paper/2311.14886/) (2023)
- [One model to solve them all: 2BSDE families via neural operators](https://mlsanity.com/paper/2511.01125/) (2025)
- [Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods](https://mlsanity.com/paper/2301.02268/) (2023)
- [Infinite dimensional generative sensing](https://mlsanity.com/paper/2603.03196/) (2026)

## Abstract (arXiv)

Sparse polynomial approximation has become indispensable for approximating smooth, high- or infinite-dimensional functions from limited samples. This is a key task in computational science and engineering, e.g., surrogate modelling in uncertainty quantification where the function is the solution map of a parametric or stochastic differential equation (DE). Yet, sparse polynomial approximation lacks a complete theory. On the one hand, there is a well-developed theory of best s-term polynomial approximation, which asserts exponential or algebraic rates of convergence for holomorphic functions. On the other, there are increasingly mature methods such as (weighted) ℓ1-minimization for computing such approximations. While the sample complexity of these methods has been analyzed with compressed sensing, whether they achieve best s-term approximation rates is not fully understood. Furthermore, these methods are not algorithms per se, as they involve exact minimizers of nonlinear optimization problems. This paper closes these gaps. Specifically, we consider the following question: are there robust, efficient algorithms for computing approximations to finite- or infinite-dimensional, holomorphic and Hilbert-valued functions from limited samples that achieve best s-term rates? We answer this affirmatively by introducing algorithms and theoretical guarantees that assert exponential or algebraic rates of convergence, along with robustness to sampling, algorithmic, and physical discretization errors. We tackle both scalar- and Hilbert-valued functions, this being key to parametric or stochastic DEs. Our results involve significant developments of existing techniques, including a novel restarted primal-dual iteration for solving weighted ℓ1-minimization problems in Hilbert spaces. Our theory is supplemented by numerical experiments demonstrating the efficacy of these algorithms.