Multiple Random Oracles Are Better Than One
| dc.creator | Arpe, Jan | |
| dc.creator | Mossel, Elchanan | |
| dc.date | 2008-04-23 | |
| dc.date.accessioned | 2026-07-07T09:34:55Z | |
| dc.date.available | 2026-07-07T09:34:55Z | |
| dc.description | We study the problem of learning k-juntas given access to examples drawn from a number of different product distributions. Thus we wish to learn a function f : {-1,1}^n -> {-1,1} that depends on k (unknown) coordinates. While the best known algorithms for the general problem of learning a k-junta require running time of n^k * poly(n,2^k), we show that given access to k different product distributions with biases separated by γ>0, the functions may be learned in time poly(n,2^k,γ^{-k}). More generally, given access to t <= k different product distributions, the functions may be learned in time n^{k/t} * poly(n,2^k,γ^{-k}). Our techniques involve novel results in Fourier analysis relating Fourier expansions with respect to different biases and a generalization of Russo's formula. | |
| dc.description | 17 pages | |
| dc.identifier | https://arxiv.org/abs/0804.3817 | |
| dc.identifier | http://arxiv.org/abs/0804.3817 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/159665 | |
| dc.subject | Machine Learning | |
| dc.title | Multiple Random Oracles Are Better Than One | |
| dc.type | text |