Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles

摘要

We study fire 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 oil k (unknown) coordinates. While the best-known algorithms for the general problem of learning a k-junta require running times of n(k) poly(n, 2(k)), we show that, given access to k different product distributions with biases separated by gamma > 0, the functions may be learned in time poly(n, 2(k), gamma(-k)). More generally. given access to t <= k dilferent product distributions, the functions may be learned in time n(k/t) poly(n, 2(k), gamma(-k)). Our techniques involve results in Fourier aualysis, relating Fourier expansions with respect to different biases, and a generalization of Russo's formula.