On The Most Discriminative Boolean Functions for Correlated Sources

Technical Summary: On The Most Discriminative Boolean Functions for Correlated Sources

Problem Statement
Motivated by a conjecture of Amari and Kobayashi regarding the maximization of Fisher information for correlated sources, this paper investigates the problem of identifying pairs of Boolean functions $(f, g)$ that maximize the Kullback-Leibler (KL) divergence between output distributions derived from two correlated binary sources $(X^n, Y^n)$. Specifically, the sources follow either a $\rho_0$-correlated distribution or a $\rho_1$-correlated distribution. The goal is to determine which functions $f, g: \{0,1\}^n \to \{\pm 1\}$ maximize the divergence $D(P_{f(X^n)g(Y^n), \rho_0} \| P_{f(X^n)g(Y^n), \rho_1})$.

This problem generalizes two known settings:

1. Mutual Information Maximization: When $\rho_1 = 0$ (independent sources), the problem reduces to maximizing mutual information, where the optimality of dictator functions was established by Pichler, Piantanida, and Matz.
2. Fisher Information Maximization: The problem studied by Amari and Kobayashi, which seeks to maximize Fisher information, can be viewed as a local version of the KL divergence problem where $\rho_0$ and $\rho_1$ are infinitesimally close. Amari and Kobayashi conjectured that parity functions are optimal for all $\rho$.

Methodology
The authors employ Fourier analysis on the Boolean cube as the primary analytical tool. Key elements of the methodology include:

• Fourier Expansion: Representing Boolean functions in terms of parity functions $\chi_S$, where the Fourier coefficients $\hat{f}(S)$ characterize the function's behavior.
• Noise Stability and Operators: Utilizing the noise operator $T_\rho$ and the concept of noise stability to relate the correlation of inputs to the correlation of outputs.
• Level-$k$ Functions: Focusing on functions whose Fourier coefficients are supported only on sets of size $k$ (level-$k$ functions). Note that level-1 functions are dictator functions, while level-$k$ functions for $k \ge 2$ include but are not limited to parity functions.
• Convexity and Inequalities: Proving bounds using the joint convexity of the KL divergence, the Cauchy-Schwarz inequality, and specific lemmas regarding the convexity of divergence with respect to weight vectors.
• Data Processing Inequality: Applying the data processing inequality to establish local optimality results.

Key Contributions and Results

1. KL Divergence Maximization:

   • Unbiased Functions: For unbiased Boolean functions ($\hat{f}(\emptyset) = \hat{g}(\emptyset) = 0$), the authors prove that the KL divergence is maximized when $f$ and $g$ are identical level-$k$ functions for some $k$. The optimal $k$ depends on the parameters $\rho_0$ and $\rho_1$.
   • Biased Identical Functions: For the case where $f = g$ (not necessarily unbiased) and the correlation is non-negative ($\rho \in [0, 1)$), the divergence is also maximized by level-$k$ functions.
   • Local Optimality: The paper proves that if one function in the pair is a level-$k$ function, the divergence cannot be increased by choosing a different second function; the optimal pair consists of two identical level-$k$ functions.
   • Limitations: The authors note that for the general case of biased, distinct functions ($f \neq g$), or for specific parameter regimes (e.g., $\rho_0 < \rho_1$ or opposite signs), the optimality of level-$k$ functions is not proven. Numerical examples suggest that for certain parameters, functions other than level-$k$ (such as majority functions) may be optimal.

2. Fisher Information Maximization:

   • Leveraging the relationship that Fisher information is the second derivative of KL divergence, the authors derive partial resolutions to the Amari-Kobayashi conjecture.
   • They prove that for unbiased functions and for identical functions in the non-negative correlation regime, Fisher information is maximized by level-$k$ functions. Since parity functions are a subset of level-$k$ functions, this provides a partial resolution to the conjecture that parity functions are optimal. However, the optimal solution is a broader class (level-$k$) than just parity functions.

3. Bayesian Distributed Hypothesis Testing:

   • The paper formulates a Bayesian one-bit distributed hypothesis testing problem where a receiver must distinguish between $\rho_0$ and $\rho_1$ correlations based on one-bit outputs from $f(X^n)$ and $g(Y^n)$.
   • It is proven that the Bayes error probability is minimized (and correct probability maximized) by level-$k$ functions among all pairs of Boolean functions. The optimal decision rule depends on the sign of the difference in expectations under the two hypotheses.

4. One-Function Version:

   • The paper discusses the one-function version of the divergence maximization problem, analogous to the Courtade-Kumar conjecture.
   • Unlike the two-function setting, the authors provide counterexamples where level-$k$ functions are not optimal for the one-function case (e.g., for $n=3$ with specific $\rho$ values, majority functions or level-2 functions outperform level-$k$ functions depending on parameters). This suggests the one-function and two-function settings exhibit different behaviors.

Significance and Claims
The paper claims to provide a partial resolution to the Amari-Kobayashi conjecture by demonstrating that level-$k$ functions (a class containing parity functions) are optimal for maximizing Fisher information and KL divergence under specific conditions (unbiasedness or identical functions in non-negative correlation).

The authors emphasize that while level-$k$ functions are optimal in the two-function setting for the conditions they prove, the general solution for the two-function problem remains open, particularly for biased, distinct functions. Furthermore, they highlight a distinct behavior in the one-function setting, where level-$k$ functions are not universally optimal, contrasting with the known optimality of dictator functions in the mutual information (Courtade-Kumar) setting. The work bridges distributed statistical inference and the Fourier analysis of Boolean functions, offering new insights into the structure of optimal compressions for correlated sources.