Debiasing Polynomial and Fourier Regression
Abstract
We study the problem of approximating an unknown function \(f : \mathbb R \rightarrow \mathbb R\) by a degree-\(d\) polynomial using as few function evaluations as possible, where error is measured with respect to a probability distribution \(\mu\). Existing randomized algorithms achieve near-optimal sample complexities to recover a (\(1+\varepsilon\))-optimal polynomial but produce biased estimates of the best polynomial approximation, which is undesirable.
Fields of Study & Subjects
Markov Chains and Monte Carlo Methods
Mathematical Approximation and Integration
Polynomial and algebraic computation
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 340–351
- Publication date
- 1 January 2026
- Language
- EN