Standard simplices and pluralities are not the most noise stable

Steven Heilman, Elchanan Mossel, Joe Neeman

TL;DR

This paper challenges the long-held conjectures that standard simplex partitions in Gaussian space and plurality functions in discrete spaces are always optimal for noise stability. The authors demonstrate that these "standard" partitions are, in fact, suboptimal for partitions into three or more parts, especially when the parts have unequal measures. This finding suggests a fundamental difference between optimizing for two-part versus multi-part noise stability and opens the door to exploring new, potentially more complex, optimal partitions.

What Problem Does This Paper Address?

Noise stability is a crucial concept in various fields, including theoretical computer science, statistics, and machine learning. It measures how much a function's output changes when its input is slightly perturbed (e.g., by adding noise). A key question in this area is identifying "optimal" partitions of a space that maximize this noise stability.

For partitions into two parts, it's well-established that half-spaces in Gaussian space and majority functions in discrete spaces are optimal. This led to two natural conjectures:

  1. The Standard Simplex Conjecture: Standard simplex partitions are optimal for Gaussian noise stability for partitions into k parts.
  2. The Plurality is Stablest Conjecture: Plurality functions are optimal for discrete noise stability for partitions into k parts.

These conjectures were supported by analogies with isoperimetric problems and initial results. However, the authors of this paper investigate whether these conjectures hold for partitions into k ≥ 3 parts, particularly when the measures of these parts are not equal. They aim to determine if the "standard" partitions remain optimal in these more general scenarios.

Methods

The paper introduces a novel analytical technique involving the Ornstein-Uhlenbeck operator. The core of their method lies in:

  • First Variation Argument: They analyze the "first variation" of noise stability for simplicial cones. This is a standard technique in optimization that examines how a quantity changes when a set is infinitesimally perturbed.
  • Holomorphicity of the Ornstein-Uhlenbeck Operator: A key technical contribution is showing that when the Ornstein-Uhlenbeck operator is applied to the indicator function of a simplicial cone and restricted to certain lines, it becomes a holomorphic function. This property is crucial for their argument.
  • Normal Variation: They use a normal variation argument, which involves moving mass between sets in a volume-preserving way, to demonstrate that noise stability can be improved by perturbing the standard simplex partition.

This approach allows them to prove that for certain non-equal measure partitions, the standard simplex is not optimal, and for discrete spaces, plurality is not the most stable.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Standard Simplex and Plurality are Not Universally Optimal: The most striking insight is that the long-standing conjectures about standard simplex and plurality partitions being optimal for noise stability are false for partitions into three or more parts, especially when the parts have unequal measures.
  • Difference Between Two-Part and Multi-Part Stability: This work highlights a significant divergence between the optimization problems for two-part noise stability (where standard partitions are optimal) and multi-part noise stability. The geometric intuition that worked for two parts doesn't directly extend.
  • Importance of Measure Distribution: The paper emphasizes that the distribution of measures among the partition parts is critical. When measures are unequal, the "standard" partitions fail to be optimal.
  • New Analytical Tools: The development of techniques to analyze the holomorphicity of the Ornstein-Uhlenbeck operator on specific geometric objects (simplicial cones) is a significant methodological contribution.

Key Results

  • Theorem 2.6: The paper proves that for a shifted flat partition with equal volumes (a specific type of standard simplex partition), it is not the most noise stable partition in Gaussian space for k ≥ 3 parts when the noise parameter p is non-zero. The same holds for p < 0.
  • Corollary 2.9: It is shown that plurality functions are not the most stable low-influence functions in discrete spaces for k ≥ 3 parts, even when the election is slightly biased.
  • Bilinear Noise Stability (Proposition 2.10): In a special case of bilinear noise stability with unequal measures (1/3, 1/2, 0), the optimal partitions are not standard simplex partitions, but rather parallel half-spaces.

Limitations and Future Work

  • Focus on Specific Partitions: The paper primarily focuses on disproving the optimality of standard simplex and plurality partitions. It does not explicitly identify the actual optimal partitions for the cases where the standard ones fail.
  • General Measures: While the results hold for unequal measures, the paper doesn't explore the full spectrum of possible measure distributions for all k.
  • Future Work: The authors pose the natural question of identifying the (conjectured) partitions that do achieve the optimum noise stability in these more general settings. They also note that existing proofs for two-part noise stability fail for more than two sets, suggesting a need for entirely new proof techniques for the multi-part case.

Summary updated

BibTeX
@inproceedings{heilman2015standard,
  author = {Steven Heilman and Elchanan Mossel and Joe Neeman},
  title = {{Standard simplices and pluralities are not the most noise stable}},
  booktitle = {ITCS},
  year = {2015},
  doi = {10.1145/2688073.2688076},
}
Figure