Debiasing Polynomial and Fourier Regression

We study the problem of approximating an unknown function f:R by a degree-d polynomial using as few function evaluations as possible, where error is measured with respect to a probability distribution $μ$. Existing randomized algorithms achieve near-optimal sample complexities to recover a (1+ε)-optimal polynomial but produce biased estimates of the best polynomial approximation, which is undesirable. We propose a simple debiasing method based on a connection between polynomial regression and random matrix theory. Our method involves evaluating f(λ₁),…,f(λd+1) where λ₁,…,λd+1 are the eigenvalues of a suitably designed random complex matrix tailored to the distribution $μ$. Our estimator is unbiased, has near-optimal sample complexity, and experimentally outperforms iid leverage score sampling. Additionally, our techniques enable us to debias existing methods for approximating a periodic function with a truncated Fourier series with near-optimal sample complexity.