Near-Linear Sample Complexity for $L_p$ Polynomial Regression
Near-Linear Sample Complexity for $L_p$ Polynomial Regression
复制标题
$L_p$ 多项式回归的近线性样本复杂度
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Samson Zhou
中科院分区：
文献类型：
--
作者：
R. A. Meyer;Cameron Musco;Christopher Musco;David P. Woodruff;Samson Zhou
我们研究$ L_P $多项式回归。给定查询访问功能$ f：[ - 1,1]
iTharrow mathbb {r} $，目标是找到一个$ d $ d $ polyenmial $ hat {q} $，这样，对于给定参数$ varepsilon> 0 $，$$，$$ | hat {q} -f | _ple（1+varepsilon） $$这里$ | cdot | _p $是$ l_p $ norm，$ | g | _p =（int _ { - 1}^1 | g（t）|^p dt）^{1/p} $。我们表明，以$ [-1,1] $从Chebyshev量度随机提取的点上查询$ f $是在所有$ L_P $ NORMS中的多项式回归的近乎最佳策略。特别是，要查找$ hat q $，就可以采样$ o（d，frac {ext {polylog}，d} {ext {poly}，varepsilon}）$ points $ points $ points $ points $ [ - 1,1] $，概率与此度量成正比。虽然以$ l_2 $和$ l_infty $的方式对多项式回归的最佳样本复杂性进行了充分的理解，但我们的结果是第一个以$ d $和错误$ $ $ $（1+varepsilon）$（1+varepsilon）$的$ p $ $ p $实现样本复杂性。我们的结果需要两个主要的技术贡献。第一个涉及$ PLEQ 2 $，我们为此提供了无限线性运算符的多项式回归的$ L_P $ LEWIS权重函数的明确界限。使用正交多项式文献中的工具，我们表明此功能受Chebyshev密度的界定。我们的第二个主要贡献是利用多项式结构，将$ p> 2 $的情况减少到$ pleq 2 $案例。通过这样做，我们获得的样本复杂性比一般$ p $ -norm线性回归问题所能获得的更高的样本复杂性，为此，需要$欧米茄（d^{p/2}）$样本。
We study $L_p$ polynomial regression. Given query access to a function $f:[-1,1]
ightarrow mathbb{R}$, the goal is to find a degree $d$ polynomial $hat{q}$ such that, for a given parameter $varepsilon>0$, $$ |hat{q}-f|_ple (1+varepsilon) cdot min_{q: ext{deg}(q)le d}|q-f|_p. $$ Here $|cdot|_p$ is the $L_p$ norm, $|g|_p = (int_{-1}^1 |g(t)|^p dt)^{1/p}$. We show that querying $f$ at points randomly drawn from the Chebyshev measure on $[-1,1]$ is a near-optimal strategy for polynomial regression in all $L_p$ norms. In particular, to find $hat q$, it suffices to sample $O(d, frac{ ext{polylog},d}{ ext{poly},varepsilon})$ points from $[-1,1]$ with probabilities proportional to this measure. While the optimal sample complexity for polynomial regression was well understood for $L_2$ and $L_infty$, our result is the first that achieves sample complexity linear in $d$ and error $(1+varepsilon)$ for other values of $p$ without any assumptions. Our result requires two main technical contributions. The first concerns $pleq 2$, for which we provide explicit bounds on the $L_p$ Lewis weight function of the infinite linear operator underlying polynomial regression. Using tools from the orthogonal polynomial literature, we show that this function is bounded by the Chebyshev density. Our second key contribution is to take advantage of the structure of polynomials to reduce the $p>2$ case to the $pleq 2$ case. By doing so, we obtain a better sample complexity than what is possible for general $p$-norm linear regression problems, for which $Omega(d^{p/2})$ samples are required.