Debiasing Polynomial and Fourier Regression

Abstract

We study the problem of approximating an unknown function $f:\mathbb{R}\to \mathbb{R}$ by a degree-$d$ polynomial using as few function evaluations as possible, where error is measured with respect to a probability distribution $\hat{I}¼$. Existing randomized algorithms achieve near-optimal sample complexities to recover a $(1+\epsilon )$-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(\hat{I}{»}_1),\dots ,f(\hat{I}{»}_{d+1})$ where $\hat{I}{»}_1,\dots ,\hat{I}{»}_{d+1}$ are the eigenvalues of a suitably designed random complex matrix tailored to the distribution $\hat{I}¼$. 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.