标题： 去偏多项式和傅里叶回归 显示英文标题

标题： Debiasing Polynomial and Fourier Regression

摘要： 我们研究了通过使用尽可能少的函数评估来用次数为$d$的多项式近似未知函数$f:\mathbb{R}\to\mathbb{R}$的问题，其中误差是相对于概率分布$\mu$进行测量的。现有的随机算法能够以接近最优的样本复杂度恢复一个$ (1+\varepsilon) $-最优多项式，但会产生对最佳多项式逼近的有偏估计，这是不希望的。我们提出了一种简单的去偏方法，该方法基于多项式回归与随机矩阵理论之间的联系。我们的方法涉及评估$f(\lambda_1),\ldots,f(\lambda_{d+1})$，其中$\lambda_1,\ldots,\lambda_{d+1}$是一个针对分布$\mu$专门设计的随机复数矩阵的特征值。我们的估计器是无偏的，具有接近最优的样本复杂度，并且在实验中表现优于独立同分布的杠杆分数采样。此外，我们的技术使我们能够以接近最优的样本复杂度对使用截断傅里叶级数近似周期性函数的现有方法进行去偏。 显示英文摘要

摘要： 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 $\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. We propose a simple debiasing method based on a connection between polynomial regression and random matrix theory. Our method involves evaluating $f(\lambda_1),\ldots,f(\lambda_{d+1})$ where $\lambda_1,\ldots,\lambda_{d+1}$ are the eigenvalues of a suitably designed random complex matrix tailored to the distribution $\mu$. 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.