.png){kind=icon}
返回
Polynomial regression under arbitrary product distributions
.png){kind=icon}
OA
AI
DOI：10.1007/s10994-010-5179-6.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In recent work, Kalai, Klivans, Mansour, and Servedio (2005) studied a variant of the Low-Degree (Fourier) Algorithm for learning under the uniform probability distribution on {0, 1}(n). They showed that the L-1 polynomial regression algorithm yields agnostic (tolerant to arbitrary noise) learning algorithms with respect to the class of threshold functions-under certain restricted instance distributions, including uniform on {0, 1}(n) and Gaussian on R-n. In this work we show how all learning results based on the Low-Degree Algorithm can be generalized to give almost identical agnostic guarantees under arbitrary product distributions on instance spaces X-1 x ... x X-n. We also extend these results to learning under mixtures of product distributions. The main technical innovation is the use of (Hoeffding) orthogonal decomposition and the extension of the noise sensitivity method to arbitrary product spaces. In particular, we give a very simple proof that threshold functions over arbitrary product spaces have d-noise sensitivity O(root delta), resolving an open problem suggested by Peres (2004).
Keyword:
Agnostic learning
Polynomial regression
Linear threshold functions
Noise sensitivity
期刊
IF:
2.9
论文数:
2.7K
被引数:
3.4W
.png){kind=icon}
查看更多内容