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.
Introduction
In the analysis of Boolean functions, understanding the relationship between a function's structural complexity and its sensitivity to input changes is a fundamental pursuit. The Fourier Entropy-Influence (FEI) Conjecture, proposed by Friedgut and Kalai in 1996, stands as a central open problem in this field. It posits that the "spread" of a function's Fourier spectrum (entropy) is bounded by its total sensitivity (influence). Proving this conjecture would have profound implications for learning theory, circuit complexity, and social choice theory.
While the conjecture has been verified for specific classes such as symmetric functions and decision trees, it has remained elusive for Linear Threshold Functions (LTFs). LTFs, which output a sign based on a weighted sum of inputs, serve as the mathematical foundation for the perceptron and single-neuron models. This research provides a significant breakthrough by proving that the FEI conjecture holds for "typical" or random LTFs.
The FEI Conjecture and LTFs
To understand the contribution, we define the two primary metrics for a Boolean function $f: \{+1, -1\}^n \to \{+1, -1\}$:
- Total Influence (Inf): This measures the average sensitivity of the function. It is the sum of the probabilities that flipping the $i$-th input bit changes the output value.
- Fourier Entropy (H): By treating the squared Fourier coefficients of the function as a probability distribution, we can calculate the Shannon entropy. This measures how "dispersed" the function is across different frequency components.
The FEI conjecture states that there exists a universal constant $C$ such that $H(f) \leq C \cdot \text{Inf}(f)$.
Linear Threshold Functions are defined by a weight vector $w \in \mathbb{R}^n$ and a threshold $\theta \in \mathbb{R}$, such that $f(x) = \text{sgn}(\sum_{i=1}^n w_i x_i - \theta)$. Despite their apparent simplicity, the general case for LTFs remains unproven. This paper shifts the focus to the average-case analysis: does the conjecture hold when the weights $w_i$ are chosen randomly?
Methodology: The "Sandwich" Strategy
The authors utilize a "sandwich" strategy to bridge the gap between entropy and influence. Previous research by Chakraborty et al. (2016) established a critical upper bound: for any LTF, the Fourier entropy $H(f)$ is at most $O(\sqrt{n})$.
To satisfy the FEI conjecture, the authors needed to demonstrate that for a random LTF, the total influence is at least $\Omega(\sqrt{n})$. If $\text{Inf}(f) \geq c\sqrt{n}$ and $H(f) \leq C\sqrt{n}$, then the ratio $H(f)/\text{Inf}(f)$ is bounded by a constant, satisfying the conjecture.
Modeling Randomness
The study considers two natural probability distributions for the weights $w_i$:
- Uniform Distribution: $w_i \sim \mathcal{U}(-1, 1)$
- Normal Distribution: $w_i \sim N(0, 1)$
Probabilistic Tools
The core of the proof relies on the Berry-Esseen Theorem, specifically a modern, optimal version provided by Shevtsova (2012). This theorem allows the authors to bound the probability that a weighted sum of random variables falls within a specific narrow range near the threshold. By precisely calculating the "typical" influence of each variable, they show that the total influence is sufficiently high.
Furthermore, the authors employ a homogenization technique. This mathematical reduction allows results derived for functions passing through the origin (where the threshold $\theta = 0$) to be generalized to non-homogeneous functions with arbitrary thresholds.
Key Results
The research successfully demonstrates that the FEI conjecture holds with high probability for random LTFs.
- High Probability Confirmation: For weights drawn from both Normal and Uniform distributions, the total influence is $\Omega(\sqrt{n})$ with high probability, matching the known entropy upper bound.
- Exponential Confidence: In the case of the Normal distribution, the probability that a randomly generated LTF violates the conjecture is exponentially small ($e^{-\Omega(n)}$).
- The Role of Regularity: The findings suggest that the conjecture holds for any LTF that is "regular"—meaning no single weight $w_i$ is so large that it dominates the entire sum. Randomness is a natural mechanism that ensures this regularity, preventing the "skewed" cases that make the general conjecture difficult to prove.
Conclusion and Future Work
This work provides strong evidence in favor of the FEI conjecture by showing it is true for the "average" case of one of the most important classes of Boolean functions. However, the "white whale" of the general case remains: proving the conjecture for LTFs with highly skewed or adversarial weights where influence might be significantly lower than $\sqrt{n}$.
Additionally, the authors note that these techniques do not immediately extend to Polynomial Threshold Functions (PTFs). PTFs involve products of variables (e.g., $x_i x_j$) and lack the same concentration properties as linear sums, representing a significantly harder challenge for future research in Fourier analysis.
Summary updated