7
$\begingroup$

Let $f:\{-1,+1\}^n \to \{-1,+1\}$ be a boolean function where all of the energy of the Fourier transform of $f$ is concentrated in a small number of low-order coefficients, say $k$ coefficients each having degree at most $d$. Can we efficiently learn $f$ given samples of the value of $f$ on uniformly random inputs?

In other words, $f$ has the form

$$f(x) = \sum_{i=1}^k \alpha_i g_i(x),$$

where each $g_i$ is a low-order square-free monomial: $g_i(x) = \prod_{j \in S_i} x_j$ for some set $S_i$ of size at most $d$, where $\sum \alpha_i^2 = 1$. Also assume that each $\alpha_i$ is either zero or bounded away from zero. Crucially, I'm interested in the case where $k$ is small.

Is there a way to learn $f$ given the value of $f$ on many random inputs? We are given $(x_1,y_1),\dots,(x_m,y_m)$ where each $x_i$ is drawn uniformly at random from $\{-1,+1\}^n$ and $y_i = f(x_i)$. I'd like to approximately learn $f$ from these values. One approach is to enumerate all ${n\choose 0} + \cdots + {n \choose d} = \Theta(n^d)$ possibilities for $g$, and estimate the Fourier coefficient for each by computing the average of $g(x_i) \cdot y_i$ over all samples. However, this requires enumerating $\Theta(n^d)$ choices of $g$, even if $k$ is much smaller than $\Theta(n^d)$.

Is there a method faster than estimating all $\Theta(n^d)$ low-order Fourier coefficients, when $k$ is small?

$\endgroup$
  • $\begingroup$ This seems to be a generalization of the problem of learning sparse parities with noise (since any noisy parity functions will have only one significant Fourier coefficient, correct?). There is work on that problem, for example here: cs.purdue.edu/homes/egrigore/papers/GRV11-ALT.pdf $\endgroup$ – Adam Smith Jan 23 '17 at 20:54
  • $\begingroup$ @AdamSmith, good stuff! Thanks for the reference. I guess there's two ways to view my problem: (a) learning a combination of multiple sparse parities, with no noise, or (b) learning a single sparse parity, with noise (since we can view $f$ as correlated to $g_1$, and consider $\sum_{i=2}^k \alpha_i g_i(x)$ as the "noise"; then the noise rate is determined by $\alpha_1$). The latter viewpoint plus the paper you cite immediately yields an algorithm for my problem that's better than $\Theta(n^d)$. Can we do anything with the former viewpoint? $\endgroup$ – D.W. Jan 23 '17 at 22:11
  • $\begingroup$ Not sure. There are a couple of possibly relevant recent papers: G. Valiant, Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem; and Arnab Bhattacharyya, Ameet Gadekar, Ninad Rajgopal, On learning k-parities with and without noise (arxiv.org/abs/1502.05375). Don't know much beyond that (but the authors might). $\endgroup$ – Adam Smith Jan 25 '17 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.