<p>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?</p>

<p>In other words, $f$ has the form</p>

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

<p>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.</p>

<p>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)$.</p>

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

CC BY-SA 3.0
2017-01-23T20:54:08.973Z
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:
https://www.cs.purdue.edu/homes/egrigore/papers/GRV11-ALT.pdf
Adam Smith
CC BY-SA 3.0
2017-01-23T22:11:45.150Z
@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?
D.W.
CC BY-SA 3.0
2017-01-25T02:19:13.980Z
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
(https://arxiv.org/abs/1502.05375).

Don't know much beyond that (but the authors might).
Adam Smith
<circuit-complexity><boolean-functions><lg.learning><fourier-analysis>
Learning function with a few low-order Fourier coefficients, from uniformly random samples
D.W.
# Learning function with a few low-order Fourier coefficients, from uniformly random samples

(Asked by: username_0 on 2017-01-20)

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?

**Tags:** circuit-complexity, boolean-functions, lg.learning, fourier-analysis
> **Comments:**
> **username_1**: 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: https://www.cs.purdue.edu/homes/egrigore/papers/GRV11-ALT.pdf  
> **username_0**: @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?  
> **username_1**: 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 (https://arxiv.org/abs/1502.05375).  Don't know much beyond that (but the authors might).  

---

## 0 answers

