Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions

Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam, Nitin Saurabh

This paper, published in March 2019, explores a fundamental question in the analysis of Boolean functions: the relationship between a function's "complexity" (Fourier entropy) and its "sensitivity" (influence). Specifically, the authors provide a significant step toward solving a 25-year-old mystery by proving the Fourier Entropy-Influence (FEI) Conjecture for a broad class of "random" Linear Threshold Functions.

TL;DR

The authors prove that the Fourier Entropy-Influence (FEI) Conjecture holds with high probability for "random" Linear Threshold Functions (LTFs). By showing that random LTFs typically have high total influence, they bridge the gap between known entropy bounds and the requirements of this long-standing conjecture.

What Problem Does This Paper Address?

In Theoretical Computer Science, we often represent logic as Boolean functions ($f: \{+1, -1\}^n \to \{+1, -1\}$). Two ways to measure these functions are:

  1. Influence (Inf): How much does changing one input bit, on average, change the output? It’s a measure of sensitivity.
  2. Fourier Entropy (H): If we decompose the function into its frequency components (Fourier analysis), how "spread out" is the information?

The FEI Conjecture (proposed by Friedgut and Kalai in 1996) posits that for any Boolean function, the Fourier entropy is always bounded by its total influence (multiplied by some constant $C$). This is a "holy grail" conjecture because proving it would automatically solve several other major problems in learning theory and circuit complexity.

While the conjecture has been proven for some classes (like symmetric functions), it remains unproven for Linear Threshold Functions (LTFs)—functions that output a sign based on a weighted sum of inputs (essentially the mathematical model of a single neuron). This paper asks: even if we can't prove it for all LTFs yet, does it at least hold for a "typical" or "random" one?

Methods

The authors employ a "sandwich" strategy. Previous research (specifically by Chakraborty et al., 2016) already established that for any LTF, the Fourier entropy is at most $O(\sqrt{n})$. To satisfy the FEI conjecture ($H(f) \leq C \cdot \text{Inf}(f)$), the authors simply needed to prove that for a random LTF, the total influence is at least $\Omega(\sqrt{n})$.

To do this, they:

  • Modeled Randomness: They drew weights ($w_i$) from two natural distributions: the Uniform distribution $[-1, 1]$ and the Normal distribution $N(0, 1)$.
  • Applied the Berry-Esseen Theorem: They used a modern, optimal version of this theorem (by Shevtsova, 2012) to bound the probability that a weighted sum of random variables falls within a specific range. This allowed them to calculate the "typical" influence of a variable.
  • Homogenization: They provided a mathematical reduction to show that results for functions passing through the origin (homogeneous) could be translated to functions with an arbitrary threshold (non-homogeneous).

Datasets

As a theoretical mathematics paper, it does not use empirical datasets. Instead, it uses probabilistic models:

  • Uniform Distribution: $w_i \sim \mathcal{U}(-1, 1)$
  • Normal Distribution: $w_i \sim N(0, 1)$

Key Insights and Ideas

  • The "Typical" LTF is Sensitive: The core insight is that while one can construct "weird" LTFs where influence is low (e.g., where one weight is massive and dictates everything), a randomly chosen LTF tends to have its influence spread out, resulting in a total influence of $\Omega(\sqrt{n})$.
  • Leveraging Optimal Probability Bounds: The proof relies heavily on the "optimality" of recent versions of the Berry-Esseen theorem. Older versions of the theorem weren't precise enough to provide the tight lower bounds on influence required for the proof.
  • $\tau$-Regularity: The authors identify that the conjecture holds for any LTF that is "regular"—meaning no single weight is too dominant. Randomness is just one way to ensure this regularity.

Key Results

  • Affirmative Answer for Random LTFs: The FEI conjecture holds with high probability for LTFs where weights are chosen from Normal or Uniform distributions.
  • Exponential Confidence: For the Normal distribution, the probability that the conjecture fails to hold for a function of $n$ variables is exponentially small ($e^{-\Omega(n)}$).
  • Lower Bound on Influence: The paper establishes that for these random distributions, $\text{Inf}(f) = \Omega(\sqrt{n})$ with high probability, matching the known entropy upper bound.

Limitations and Future Work

  • The General Case: The "white whale" remains: proving the conjecture for all LTFs, including those with highly skewed or adversarial weights.
  • Polynomial Threshold Functions (PTFs): The authors note that their techniques don't easily generalize to PTFs (where the sum involves products of variables, like $x_i x_j$). PTFs are much harder to analyze because they lack the same concentration properties as linear sums.
  • Skewness Bounds: They suggest that a future path might involve bounding Fourier entropy based on a measure of the "skewness" of the weights $w_i$.

Reference: Chakraborty, S., Karmalkar, S., Kundu, S., Lokam, S. V., & Saurabh, N. (2019). Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions. arXiv:1903.11635v1 [cs.CC].

Summary updated

Abstract

The Fourier-Entropy Influence (FEI) Conjecture states that for any Boolean function $f:\{+1,-1\}^n \to \{+1,-1\}$, the Fourier entropy of $f$ is at most its influence up to a universal constant factor. While the FEI conjecture has been proved for many classes of Boolean functions, it is still not known whether it holds for the class of Linear Threshold Functions. A natural question is: Does the FEI conjecture hold for a `random' linear threshold function? In this paper, we answer this question in the affirmative. We consider two natural distributions on the weights defining a linear threshold function, namely uniform distribution on $[-1,1]$ and Normal distribution.
BibTeX
@inproceedings{chakraborty2018fourier,
  author = {Sourav Chakraborty and Sushrut Karmalkar and Srijita Kundu and Satyanarayana V. Lokam and Nitin Saurabh},
  title = {{Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions}},
  booktitle = {LATIN},
  year = {2018},
  url = {https://openreview.net/forum?id=lt5iHUeoapb},
}

Loading related content...

Figure