PaperlayerView exact revision on arXiv

Source-linked AI summary

On the entropy of a noisy function

Alex Samorodnitsky

arXiv:1508.01464v4cs.ITmath.COmath.IT

TL;DR

The paper addresses the conjecture that characteristic functions of (n−1)-dimensional subcubes are the most informative Boolean functions under noise. It bounds noisy entropy using average conditional entropies and applies the bound to establish the conjecture for high noise levels.

  • Problem

    The paper studies the Courtade–Kumar conjecture that characteristic functions of (n−1)-dimensional subcubes are the most informative Boolean functions under coordinatewise noise.

    Source: §1 · pp. 1–2

  • Method

    The paper upper-bounds noisy-function entropy using average entropy of conditional expectations over random variable sets.

    Source: §1 · p. 2, §1.3 · p. 5

  • Results

    For high noise levels, the paper establishes the Courtade–Kumar conjecture using its subcube-stability application together with results and [14].

    Source: §1 · p. 2

  • Takeaways & Limitations

    At high noise, characteristic functions of (n−1)-dimensional subcubes are at least as stable as functions close to them, supporting the conjecture’s conclusion.

    Source: §1 · p. 2

    The averaging argument replaces φ(x, ǫ) with the larger linear bound (1 − 2ǫ)^2 · x, and the resulting bounds are incomparable.

    Source: §1.4.1 · p. 10

Abstract

from arXiv · show

Let $0 < \epsilon < 1/2$ be a noise parameter, and let $T_{\epsilon}$ be the noise operator acting on functions on the boolean cube $\{0,1\}^n$. Let $f$ be a nonnegative function on $\{0,1\}^n$. We upper bound the entropy of $T_{\epsilon} f$ by the average entropy of conditional expectations of $f$, given sets of roughly $(1-2\epsilon)^2 \cdot n$ variables. In information-theoretic terms, we prove the following strengthening of "Mrs. Gerber's lemma": Let $X$ be a random binary vector of length $n$, and let $Z$ be a noise vector, corresponding to a binary symmetric channel with crossover probability $\epsilon$. Then, setting $v = (1-2\epsilon)^2 \cdot n$, we have (up to lower-order terms): $$ H\Big(X \oplus Z\Big) \ge n \cdot H\left(\epsilon ~+~ (1-2\epsilon) \cdot H^{-1}\left(\frac{{\mathbb E}_{|B| = v} H\Big(\{X_i\}_{i\in B}\Big)}{v}\right)\right) $$ As an application, we show that for a boolean function $f$, which is close to a characteristic function $g$ of a subcube of dimension $n-1$, the entropy of $T_{\epsilon} f$ is at most that of $T_{\epsilon} g$. This, combined with a recent result of Ordentlich, Shayevitz, and Weinstein shows that the "Most informative boolean function" conjecture of Courtade and Kumar holds for high noise $\epsilon \ge 1/2 - \delta$, for some absolute constant $\delta > 0$. Namely, if $X$ is uniformly distributed in $\{0,1\}^n$ and $Y$ is obtained by flipping each coordinate of $X$ independently with probability $\epsilon$, then, provided $\epsilon \ge 1/2 - \delta$, for any boolean function $f$ holds $I\Big(f(X);Y\Big) \le 1 - H(\epsilon)$.

1 Introduction

The paper studies which Boolean functions are most informative under coordinatewise noise, conjectured by Courtade and Kumar to be characteristic functions of (n−1)-dimensional subcubes. It bounds noisy-function entropy through conditional expectations and uses the result to establish the conjecture at high noise.

1 Introduction

  • The motivating conjecture is due to Courtade and Kumar.Source: §1 · p. 1
  • The conjecture identifies characteristic functions of (n−1)-dimensional subcubes as the most informative Boolean functions in the stated setting.The paper frames the problem as finding which Boolean functions are stablest under noise, meaning their entropy decreases least.Source: §1 · p. 2
  • The main result upper-bounds the noisy entropy of a nonnegative function by average conditional-expectation entropy over sets of roughly (1 − 2ǫ)^2 · n variables.This addresses entropy under the noise operator beyond Boolean functions.Source: §1 · p. 2
  • For ǫ close to 1/2, characteristic functions of (n−1)-dimensional subcubes are at least as stable under noise as functions close to them.Source: §1 · p. 2
  • The paper concludes that the Courtade–Kumar conjecture holds for high noise levels, combining this application with results and [14].Source: §1 · p. 2

1.1 Entropy of nonnegative functions and the noise operator

This section introduces entropy for nonnegative functions and the noise operator, then connects these notions to the Boolean-function setting of the conjecture. It also notes that applying noise decreases entropy and frames quantifying that decrease as the goal.

1.1 Entropy of nonnegative functions and the noise operator

  • For a nonnegative function f, the section introduces an entropy functional, but the supplied passage does not state its formula.Source: §1.1 · p. 2
  • The noise operator Tǫf evaluates f in expectation at points y that are ǫ-correlated with the input x.The section specifies 0 ≤ ǫ ≤ 1/2.Source: §1.1 · p. 2
  • Because Tǫf is a convex combination of shifted copies of f, convexity of entropy implies that noise decreases entropy.The section’s goal is to quantify this decrease.Source: §1.1 · p. 2

1.1.1 Connection between notions

  • The section connects the function-based setup to the Boolean-function setting by presenting an equivalent form of Conjecture 1.1.Source: §1.1.1 · p. 3

1.2 Mrs. Gerber’s function and Mrs. Gerber’s lemma

The section introduces Mrs. Gerber’s function in connection with Mrs. Gerber’s lemma and describes properties used in the paper. The lemma bounds the entropy of a nonnegative function after noise.

1.2 Mrs. Gerber’s function and Mrs. Gerber’s lemma

  • The function is parameterized by x and ǫ, with t chosen so that the two-point function ft has entropy x.Source: §1.2 · pp. 3–4
  • The paper calls φ Mrs. Gerber’s function, and identifies it as concave in x for each 0 ≤ ǫ ≤ 1/2.The function is increasing in x and starts at zero.Source: §1.2 · p. 4
  • Mrs. Gerber’s lemma gives an upper bound on the entropy of a nonnegative function after application of the noise operator.Source: §1.2 · p. 4

1.3 Main results

The section bounds noisy entropy by average conditional entropy over random subsets of coordinates. It also derives boolean-function consequences, including a high-noise application to Conjecture 1.1.

Main entropy bound

  • For normalized nonnegative f, Theorem 1.7 samples each coordinate independently with probability (1−2ε)^2 and bounds noisy entropy using conditional expectations on the sampled set.This makes the subset size random, with expected size (1−2ε)^2 n.Source: §1.3 · p. 5

Corollaries

  • Applying φ(x, ε) ≤ (1−2ε)^2 x gives a more streamlined claim, while the somewhat stronger theorem is needed for applications..Source: §1.3 · pp. 5, 7

Boolean-function applications

  • The entropy bound is also specialized to boolean functions in Corollary 1.10, stated in the notation of Conjecture 1.1.Source: §1.3 · p. 6

Mrs. Gerber’s lemma

  • In Theorem 1.12’s notation of Theorem 1.7, setting t = (1−2ε)^2·n yields a claim stronger than Theorem 1.6 up to a negligible error term.Separately, the paper presents a somewhat different strengthening of Corollary 1.9, giving a stronger version of Mrs. Gerber’s lemma.Source: §1.3 · pp. 6–7

Boolean-function applications

  • At high noise, the near-subcube application and results and [14] establish Conjecture 1.1 for functions meeting Theorem 1.14’s condition.The stated condition includes a singleton Fourier coefficient with magnitude at least (1−δ) E f.Source: §1.3 · pp. 7–8

1.4 More on Theorems 1.7 and 1.12

The section presents Theorems 1.7 and 1.12 as strengthenings of Mrs. Gerber’s lemma, tracing the improvement to a bound on how noise decreases mutual information. It outlines the proof strategy and explains how linearization shapes the relationship between the bounds.

1.4 More on Theorems 1.7 and 1.12

  • Directional noise operators commute, and composing them over a set of coordinates gives the noise operator on that set.The full operator T_ε is T_ε[n] in this notation.Source: §1.4 · p. 8
  • The chain-rule argument starts by normalizing E f = 1 and uses concavity to upper-bound entropy terms across restrictions of the function.The proof of Mrs. Gerber’s lemma averages over coordinate permutations and applies concavity of φ in the averaging steps.Source: §1.4 · pp. 8–9

1.4.1 Our improvement

  • The proof bounds the noisy decrease in mutual information, then averages the improved chain-rule bound over coordinate permutations.A linear program and its symmetric version provide an upper bound on noisy mutual information, yielding the improvement used in Theorems 1.7 and 1.12.Source: §1.4.1 · p. 10
  • The bounds are incomparable because their averaging steps apply different linearizations of φ; Theorem 1.12 is the more evident improvement over (4).The argument may replace φ(x, ε) with the larger linear function (1 − 2ε)^2 · x, so it does not necessarily directly improve (4). For small x, the two functions nearly coincide, and the bounds are close to Corollary 1.9 when f has low entropy, as for boolean functions.Source: §1.4.1 · p. 10

1.4.2 Related work

  • Y. Polyanskiy noted that upper-bounding ITǫAf(A, m) given If(A, m) is a strong data processing inequalities (SDPI) question; [16] and [17] are cited for pertinent results, including a new proof of Proposition 4.1.Source: §1.4.2 · p. 11

2 A linear programming bound for noisy mutual information

This section bounds noisy mutual information by a linear program whose variables track discrete derivatives after noise and whose boundary data come from the original function. The bound follows by showing the derivatives generated by the noisy distributions form a feasible solution.

Discussion

  • The discrete derivative of mutual information is a conditional mutual information, and noise in its direction reduces it by at least a factor of λ.Here λ = (1 − 2ε)^2; the passage attributes the reduction to the strong data processing inequality.Source: Discussion · p. 11, §2 · p. 11

Linear program

  • The noisy mutual information is upper bounded by the value of a linear optimization problem with boundary data determined by the original function.The program's variables are noisy discrete derivatives, and the strong data processing inequality supplies local linear constraints.Source: Discussion · pp. 11–12, Linear program · p. 13
  • The noisy derivatives generated from f satisfy the program's constraints, yielding a feasible solution whose value is the noisy mutual information.The argument verifies feasibility using the commutation of noise and conditional expectation operators and the strong data processing inequality.Source: Linear program · pp. 13–14

3 The optimization problem and its symmetric version

The section replaces the original optimization problem with a symmetric version and constructs a feasible symmetric solution. It then shows that this solution upper bounds the original optimum and expresses its value in terms of symmetric boundary data.

3 The optimization problem and its symmetric version

  • The section's overall strategy is to upper bound noisy mutual information by comparing the original program with its symmetric counterpart.The symmetric solution's value provides the upper bound on noisy mutual information.Source: §3 · p. 14

3.1 The symmetric problem and solution

  • A symmetric boundary and a solution indexed by set sizes and their overlaps are defined, and the constructed solution is feasible.Feasibility is established in Proposition 3.1.Source: §3.1 · p. 15

3.2 Optimality of the symmetric solution

  • The optimal value of the original program is upper bounded by the value of the constructed symmetric solution to the symmetric program.The result follows from the section's comparison of the original and symmetric optimization problems.Source: §3.2 · pp. 16–17

3.2.1 Notation

  • The proof compares the original and symmetric problem values using smaller restricted problems and induction on k and r.The induction assumes the claim for k − 1 and for smaller values of r at k.Source: §3.2 · p. 17, §3.2.1 · pp. 20–21

3.3 The value of the symmetric optimization problem

  • The symmetric solution's value is linear in the symmetric boundary data y1, ..., yk.For unit-vector initial data, Lemma 3.9 gives the parameters x_r^t as λ^(r−(t−s)) · (1 − λ)^(t−s) when s ≤ t ≤ s + r, and zero otherwise.Source: §3.3 · p. 22

4 Proof of Theorem 1.7

The proof derives Theorem 1.7 through a sequence of lemmas and bounds noisy mutual information using the symmetric optimization problem. It uses random subsets sampled at rate λ and averages over subsets and coordinates.

4 Proof of Theorem 1.7

  • Proposition 4.1 bounds noisy mutual information by the symmetric optimization problem's value, after applying Theorems 2.1 and 3.2.The symmetric value is given by Corollary 3.11 with the corresponding changes of indices and notation.Source: §4.0.1 · p. 24

4.0.1 Notation

  • The proof samples a random subset T by including each coordinate independently with probability λ and combines the resulting claim with Lemma 4.3.The passage states that the combination completes the proof, assuming Lemmas 4.3 and 4.4.Source: §4.0.1 · p. 25
  • The argument averages over subsets and coordinates, using concavity of φ to upper bound the quantity being proved.The averaging includes k-subsets A and coordinates m outside A.Source: §4.0.1 · p. 27

5 Proof of Theorem 1.14

This section proves both claims of Theorem 1.14, establishing the first in the small-noise regime via smoothing and auxiliary bounds, then completing the second by combining earlier estimates. The proof of the second claim is only sketched for unbalanced functions.

Notation

  • The notation sets E f = 1/2 − β for 0 ≤ β ≤ δ, takes bf(1) = (1 − α)·E f for 0 ≤ α ≤ δ, and defines γ = α + β.The noise parameter satisfies 0 < ε < 1/2 and (1 − 2ε)^2 ≤ δ, with λ = (1 − 2ε)^2.Source: §5 · p. 28, Notation · p. 29

5.1 Proof of the first claim of the theorem

  • For sufficiently small δ, the first claim follows by applying Theorem 1.7 to a smoothed function and bounding three terms with auxiliary lemmas.The proof takes h = T_{ετ}f and applies Theorem 1.7 with noise ε1; the resulting subset T samples each coordinate independently with probability (1 − 2ε1)^2.Source: §5.1 · pp. 29–30

Proof of Lemma 5.2

  • Lemma 5.2 uses the Fourier effect of smoothing, which multiplies each coefficient by a degree-dependent factor and does not increase its magnitude.The proof then applies earlier bounds to conclude the lemma.Source: Proof of Lemma 5.2 · p. 32

Proof of Lemma 5.3

  • Lemma 5.3 reduces the relevant function to a two-point space and uses convexity of Mrs. Gerber’s function to derive its bound.The argument applies a convexity inequality between λ and (1 − α)^2 λ, then concludes for sufficiently small λ.Source: Proof of Lemma 5.3 · p. 33

5.1.1 Proof of Lemma 5.1

  • The proof of Lemma 5.1 bounds two contributions using Fourier-coefficient estimates, including an inequality for the total squared first-level coefficients of a Boolean function.These estimates are combined to finish Lemma 5.1 and the first claim; the passage states that the second claim uses a similar argument with necessary differences.Source: §5.1.1 · pp. 34, 37

5.2 Proof of the second claim of the theorem

  • For balanced f, the second claim follows by applying the first claim to 1 − f; for unbalanced f, the proof sketches a similar three-term argument.The first two bounds carry over because the squared nontrivial Fourier coefficients behave the same for h and 1 − h; the third term follows the Lemma 5.3 argument.Source: §5.2 · p. 38
  • The proof combines all bounds on the right-hand sides of (18) and (26), and states that λ, γ ≤ O(δ) implies a result for sufficiently small δ > 0.Source: §5.2 · p. 39

6 Remaining proofs

These remaining proofs establish the stated entropy bounds and high-noise conclusion using noisy-entropy inequalities, symmetry and concavity, and Fourier estimates.

6.1 Proof of Lemma 1.2

  • The proof of Lemma 1.2 uses that the noise operator preserves expectation, E Tεg = E g.The passage states that this establishes the lemma's claim.Source: §6.1 · p. 39

6.2 Proof of Corollary 1.10

  • The proof of Corollary 1.10 applies Corollary 1.9 to f and 1 − f, reducing the argument to an inequality for each T ⊆ [n].Both sides are then viewed as functions of the coordinates indexed by T.Source: §6.2 · p. 40

6.3 Proof of Theorem 1.12

  • Theorem 1.12 follows by applying the noisy-entropy chain rule, averaging over permutations, and using symmetry and concavity to bound subset terms.The proof then uses the random-subset analysis from Theorem 1.7 to reach the theorem's claim.Source: §6.3 · pp. 40–41

6.3.1 Proof of (6)

  • The proof of (6) applies Theorem 1.12 to the distribution of X scaled by 2^n, then substitutes earlier identities to obtain the claim.The scaled function has expectation 1.Source: §6.3.1 · p. 41

6.4 Proof of Theorem 1.15

  • For sufficiently small λ, the proof of Theorem 1.15 uses Fourier bounds to find a coefficient near one, then applies Theorem 1.14 to conclude.The argument assumes noise with (1 − 2ε)^2 ≤ δ; the proof also cites the known bound for functions whose expectation is near 0 or 1.Source: §6.4 · pp. 41–43

6.4.1 Proof of Lemma 6.1

  • Lemma 6.1 is proved by splitting a function into even and odd parts, bounding three summands using variance control and Chebyshev's inequality, and combining the estimates.The argument is described as a slight extension of one in [14].Source: §6.4.1 · pp. 43–45
Loading 1508.01464v4…