<p>I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with <em>arbitrary dependencies</em> between the different input bits. I know of <span class="math-container">$p$</span>-biased analysis, but I'm facing the setting where there can be <em>correlations</em> between the different input bits <span class="math-container">$x_i$</span>.</p>

<p>Specifically, I have the following question.</p>

<p><strong>Background:</strong> The <strong>average sensitivity</strong> of a Boolean function <span class="math-container">$f : \{-1,1\}^n \rightarrow \{-1,1\}$</span> is <span class="math-container">$as(f) := \mathbb{E}_x[s(f,x)]$</span>, where <span class="math-container">$s(f,x)$</span> is the number of Hamming neighbors <span class="math-container">$x'$</span> of <span class="math-container">$x$</span> such that <span class="math-container">$f(x) \neq f(x')$</span>. Here, the expectation <span class="math-container">$\mathbb{E}_x$</span> is over the uniform distribution over <span class="math-container">$\{-1,1\}^n$</span>.
In this setting, low average sensitivity guarantees approximation by low-degree polynomials:
If <span class="math-container">$\hat{f}(S)$</span> is the Fourier coefficient associated to the set <span class="math-container">$S \subset \{X_1, \dots, X_n\}$</span>, then <span class="math-container">$as(f) = \sum_{S} |\hat{f}(S)|^2 |S|$</span> (e.g. shown in Section 3.3 of Ryan O'Donnell's tutorial <a href="https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf" rel="nofollow noreferrer">https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf</a>).
Therefore, by Markov's inequality and the Parseval theorem, a polynomial of degree <span class="math-container">$as(f)/\epsilon^2$</span> is sufficient to approximate <span class="math-container">$f$</span> up to <span class="math-container">$\ell_2$</span> error <span class="math-container">$\epsilon$</span>.</p>

<p><strong>My question</strong> is: Is there any known way to generalize this to the setting where the distribution of <span class="math-container">$x \in \{-1,1\}^n$</span> is <strong>not uniform</strong>?
That is, is there an average-sensitivity-like measure that bounds the degree of a polynomial approximating the function in <span class="math-container">$\ell_2$</span>, where all expectations over input strings <span class="math-container">$x$</span> are taken w.r.t. the given non-uniform distribution? (Complexity measures other than polynomial degree are also welcome.)</p>

<p>I can think of a couple of generalizations of average sensitivity that appear reasonable to me. To give a specific example, take the following averaged version of block sensitivity:
<span class="math-container">$$\max_{d} \sum_{i=1}^{|d|} Var[f|X_i : X_i \not\in d_i]$$</span>
where <span class="math-container">$d$</span> runs over all partitions of <span class="math-container">$\{X_1, ..., X_n\}$</span> into disjoint subsets.
This measure evaluates, for each subset <span class="math-container">$d_i$</span>, how sensitive <span class="math-container">$f$</span> is to that specific subset, on average across the input strings <span class="math-container">$x$</span> distributed according to the given nonuniform distribution. For the uniform distribution, it is equal to the ordinary average sensitivity <span class="math-container">$as(f)$</span>.
Can this, or a similar, sensitivity measure tell us something about the polynomial degree (or decision tree depth, ...) needed to approximate <span class="math-container">$f$</span> in <span class="math-container">$\ell_2$</span> (or some other metric)?</p>

<p>Any pointers, ideas, or thoughts would be extremely appreciated! Thanks for your help!</p>

<p><strong>Addition:</strong> Why is the `standard' definition <span class="math-container">$as(f) := \mathbb{E}_x[s(f,x)]$</span> not a sufficient answer? (Responding to question asked by Stella Biderman): First, I don't know how to prove in the non-uniform setting that low average sensitivity entails approximability with low-degree polynomials, as is known in the uniform setting.
Second, it seems to provide answers that do not match the polynomial degree necessary for approximation: Consider the distribution <span class="math-container">$P_0$</span> putting almost all (<span class="math-container">$1-\epsilon$</span>) of its mass on <span class="math-container">$1^n$</span>, and let <span class="math-container">$f$</span> be the PARITY function. Then <span class="math-container">$\mathbb{E}_{x\sim{P_0}}[s(f,x)] = n$</span>, even though <span class="math-container">$f$</span> is almost a constant function.
If low average sensitivity corresponds to low-degree approximability (as is the case for the unifrm distribution), then this is undesirable, as a constant is sufficient to approximate <span class="math-container">$f$</span> up to <span class="math-container">$\ell_2$</span> error <span class="math-container">$\epsilon$</span>, under the given distribution.
In contrast, the proposed sensitivity metric <span class="math-container">$\max_{d} \sum_{i=1}^{|d|} Var[f|X_i : X_i \not\in d_i]$</span> gives a value of about <span class="math-container">$\epsilon$</span>.</p>

CC BY-SA 4.0
2019-08-08T19:58:05.763Z
It seems to me that the obvious generalization of sensitivity is to take the expected value over $x\sim\mathcal{D}$ for some distribution $\mathcal{D}$. Your question implies that there are other notions of average sensitivity that appeal to you. What are they? In any event, for this generalization (as long as the domain is discrete) you can compute the answer by using the linearity of the expectation.
Stella Biderman
CC BY-SA 4.0
2019-09-14T15:01:19.963Z
Thanks for your reply! I added a section explaining why the standard definition, taking the expected value over $x \sim \mathcal{D}$, does not seem to be sufficient.
Michael Hahn
<cc.complexity-theory><co.combinatorics><boolean-functions><fourier-analysis><bounded-degree>
Sensitivity and Low-Degree Approximation under Non-Uniform Distribution
Michael Hahn
# Sensitivity and Low-Degree Approximation under Non-Uniform Distribution

(Asked by: username_0 on 2019-07-26)

I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with *arbitrary dependencies* between the different input bits. I know of $p$-biased analysis, but I'm facing the setting where there can be *correlations* between the different input bits $x\_i$.

Specifically, I have the following question.

**Background:** The **average sensitivity** of a Boolean function $f : \{-1,1\}^n \rightarrow \{-1,1\}$ is $as(f) := \mathbb{E}\_x[s(f,x)]$, where $s(f,x)$ is the number of Hamming neighbors $x'$ of $x$ such that $f(x) \neq f(x')$. Here, the expectation $\mathbb{E}\_x$ is over the uniform distribution over $\{-1,1\}^n$.
In this setting, low average sensitivity guarantees approximation by low-degree polynomials:
If $\hat{f}(S)$ is the Fourier coefficient associated to the set $S \subset \{X\_1, \dots, X\_n\}$, then $as(f) = \sum\_{S} |\hat{f}(S)|^2 |S|$ (e.g. shown in Section 3.3 of Ryan O'Donnell's tutorial <https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf>).
Therefore, by Markov's inequality and the Parseval theorem, a polynomial of degree $as(f)/\epsilon^2$ is sufficient to approximate $f$ up to $\ell\_2$ error $\epsilon$.

**My question** is: Is there any known way to generalize this to the setting where the distribution of $x \in \{-1,1\}^n$ is **not uniform**?
That is, is there an average-sensitivity-like measure that bounds the degree of a polynomial approximating the function in $\ell\_2$, where all expectations over input strings $x$ are taken w.r.t. the given non-uniform distribution? (Complexity measures other than polynomial degree are also welcome.)

I can think of a couple of generalizations of average sensitivity that appear reasonable to me. To give a specific example, take the following averaged version of block sensitivity:
$$\max\_{d} \sum\_{i=1}^{|d|} Var[f|X\_i : X\_i \not\in d\_i]$$
where $d$ runs over all partitions of $\{X\_1, ..., X\_n\}$ into disjoint subsets.
This measure evaluates, for each subset $d\_i$, how sensitive $f$ is to that specific subset, on average across the input strings $x$ distributed according to the given nonuniform distribution. For the uniform distribution, it is equal to the ordinary average sensitivity $as(f)$.
Can this, or a similar, sensitivity measure tell us something about the polynomial degree (or decision tree depth, ...) needed to approximate $f$ in $\ell\_2$ (or some other metric)?

Any pointers, ideas, or thoughts would be extremely appreciated! Thanks for your help!

**Addition:** Why is the `standard' definition $as(f) := \mathbb{E}\_x[s(f,x)]$ not a sufficient answer? (Responding to question asked by Stella Biderman): First, I don't know how to prove in the non-uniform setting that low average sensitivity entails approximability with low-degree polynomials, as is known in the uniform setting.
Second, it seems to provide answers that do not match the polynomial degree necessary for approximation: Consider the distribution $P\_0$ putting almost all ($1-\epsilon$) of its mass on $1^n$, and let $f$ be the PARITY function. Then $\mathbb{E}\_{x\sim{P\_0}}[s(f,x)] = n$, even though $f$ is almost a constant function.
If low average sensitivity corresponds to low-degree approximability (as is the case for the unifrm distribution), then this is undesirable, as a constant is sufficient to approximate $f$ up to $\ell\_2$ error $\epsilon$, under the given distribution.
In contrast, the proposed sensitivity metric $\max\_{d} \sum\_{i=1}^{|d|} Var[f|X\_i : X\_i \not\in d\_i]$ gives a value of about $\epsilon$.

**Tags:** cc.complexity-theory, co.combinatorics, boolean-functions, fourier-analysis, bounded-degree
> **Comments:**
> **username_1**: It seems to me that the obvious generalization of sensitivity is to take the expected value over $x\sim\mathcal{D}$ for some distribution $\mathcal{D}$. Your question implies that there are other notions of average sensitivity that appeal to you. What are they? In any event, for this generalization (as long as the domain is discrete) you can compute the answer by using the linearity of the expectation.  
> **username_0**: Thanks for your reply! I added a section explaining why the standard definition, taking the expected value over $x \sim \mathcal{D}$, does not seem to be sufficient.  

---

## 0 answers

