Remarkable New Stochastic Methods in ABF: Ronen Eldan and Renan Gross Found a New Proof for KKL and Settled a Conjecture by Talagrand

 

The main conjecture from Talagrand’s paper on boundaries and influences was settled by Ronen Eldan and Renan Gross. Their paper introduces a new powerful method to the field of analysis of Boolean functions (ABF).

This post is devoted to a new breakthrough paper by Ronen Eldan and Renan Gross, Concentration on the Boolean hypercube via pathwise stochastic analysis.

The paper introduces remarkable new techniques based on stochastic calculus, (that bypass the use of hypercontractivity), that allow to settles several open problems on analysis of Boolean functions. (And on the way, to give a very different proof for KKL.)

Renan Gross recently wrote an excellent high-level explanation of the paper in his  blog: New paper on arXiv: Concentration on the Boolean hypercube via pathwise stochastic analysis. It is accompanied by a brief introduction to Boolean analysis, featuring the required Boolean material:

 

Before we move on, a trivia question:

Trivia question: Who invented the term hypercontractivity?

(For a hint, see at the end of the post.)

Back to the paper by Ronen Eldan and Renan Gross. Perhaps the best way to explain what was achieved in this paper is to put one after the other the abstracts of the first version followed by the abstract of the second paper.

 

Ronen and Renan’s paper. Version 1, 26 Sept 2019.

The title for version 1 was: Stability of Talagrand’s influence inequality

And here is the abstract: 

We strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function

(1)~~~~~\mathrm{var}\left(f\right)\leq C\sum_{i=1}^{n}\frac{\mathrm{Inf}_{i}\left(f\right)}{1+\log\left(1/\mathrm{Inf}_{i}\left(f\right)\right)}

where  \mathrm{Inf}_{i}\left(f\right) denote the influence of the i-th coordinate. We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial (KKL) inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary. Our proofs rely on new techniques, based on stochastic calculus, and bypass the use of hypercontractivity common to previous proofs.

Let me say a few words about it. KKL theorem asserts that the maximal influence of a balanced Boolean function is at least \Omega (\log n/n) var (f). The famous tribe example of Ben-Or and Linial shows that this is tight.  The KKL paper gave some statements about other norms of the influence vector and Talagrand’s inequality stated above (from the paper “On Russo’s 0-1 law”) gives a sharp description of the influence vectors. Ronen and Renan found a new method that gave new proofs for KKL’s theorem and the stronger Talagrand’s inequality. This new methods led to new stability result.

Now, lets move to version 2.

Ronen and Renan’s paper: Version 2: 12 Nov 2019,

Ronen Eldan and Renan Gross, Concentration on the Boolean hypercube via pathwise stochastic analysis.

Abstract: We develop a new technique for proving concentration inequalities which relate between the variance and influences of Boolean functions. Using this technique, we

1. Settle a conjecture of Talagrand [Tal97] proving that

(2)~~~~~\int_{\left\{ -1,1\right\} ^{n}}\sqrt{h_{f}\left(x\right)}d\mu\geq C\cdot\mathrm{var}\left(f\right)\cdot\left(\log\left(\frac{1}{\sum\mathrm{Inf}_{i}^{2}\left(f\right)}\right)\right)^{1/2},

where h_f(x) is the number of edges at x  along which f changes its value, and Inf_i(f) is the influence of the i-th coordinate.

2. Strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function f

\mathrm{var}\left(f\right)\leq C\sum_{i=1}^{n}\frac{\mathrm{Inf}_{i}\left(f\right)}{1+\log\left(1/\mathrm{Inf}_{i}\left(f\right)\right)}

We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary.

3. Improve a quantitative relation between influences and noise stability given by Keller and Kindler.

Our proofs rely on techniques based on stochastic calculus, and bypass the use of hypercontractivity common to previous proofs.

Let me explain in a few words the main inequality that verified a conjecture by Talagrand. For other advances look at the paper itself.

The famous Margulis-Talagrand inequality asserts that

(3)~~~~~\int_{\left\{ -1,1\right\} ^{n}}\sqrt{h_{f}\left(x\right)}d\mu\geq C\cdot\mathrm{var}(f).

Let me say a little more. Talagrand’s proved in  his paper on Influence and boundary asserts that the right hand is a constant only if II(f) – the sum of squares of the influences is a constant. He conjectured that we can actually add the square root of \log II(f) to the RHS.

A few remarks:

  1.  For more background see my old post “Nati’s influence“.
  2. Let me mention that Talagrand’s influence inequality (Equation (1) above) is sharp up to a multiplicative constant. This is shown in a 2015 paper: On the Converse of Talagrand’s Influence Inequality by Saleet Klein, Amit Levi, Muli Safra, Clara Shikhelman, and Yinon Spinka.
  3.  Finding the best constant in KKL’s theorem is a well known challenge. So is the question of understanding balanced Boolean functions on n variables where the maximum influence is C \log n/n. Ehud Friedgit in his paper: Influences in Product Spaces, KKL and BKKKL Revisited, have made important conjectures for such Boolean functions.
  4.  I expect that the new method will have many applications. Ronen Eldan in a paper Second-order bounds on correlations between increasing families, found applicaions to correlation inequalities which I will discuss at some other time.
  5.  See the last part of this post for a description of Talagrand’s various relevant papers.
  6. Renan Gross is building the BooleanZoo in a similar spirit to the famous complexityZoo.
  7. I was in the process of writing a post about progress on ABS, mentioning twelve or so papers, apologizing for not mentioning others, promising to write in details about some of the papers, and making further apologetic remarks. But as this large post does not advance let me start with some of the promises.

talabb

Hint to the trivia question:

The very same person also coined the terms: Berry’s phase, TKN^2 integers, almost Matthieu, HVZ, Birman-Schwinger, infrared bounds, diamagnetic inequality, Verblunsky coefficient, Maryland model, ultracontractivity, …

This entry was posted in Analysis, Combinatorics, Probability and tagged , , . Bookmark the permalink.

5 Responses to Remarkable New Stochastic Methods in ABF: Ronen Eldan and Renan Gross Found a New Proof for KKL and Settled a Conjecture by Talagrand

  1. Nick Read says:

    Must be Barry Simon!

  2. Ronen Eldan says:

    Thanks, Gil! Two quick comments:
    1. In the special case that the function is roughly balanced, it turns out that the “pathwise” approach is not essential for the proof of Talagrand’s conjecture (hence, there is a version of the proof that doesn’t use stochastic calculus). Two ways to do this were found (independently) by Ramon Van Handel and Dor Minzer. But at this point it does seem that for the stability results, and also to get a sharp dependence on the expectation of the function, the only way to go is to use the pathwise approach.
    2. A beautiful proof by Franck Barthe and Bernard Maurey (based on ideas by Capitaine-Hsu-Ledoux) uses yet another argument based on stochastic calculus to prove a one-dimensional inequality which implies Bobkov’s strengthening of inequality (3), see http://www.numdam.org/article/AIHPB_2000__36_4_419_0.pdf .

    • Gil Kalai says:

      Thanks, Ronen! It is certainly nice to have various approaches. I remember that I was very impressed by Bobkov’s stronger form of Talagrand (3), but I am not sure I was aware of the Barthe Maurey’s paper.

    • Gil Kalai says:

      Meanwhile Noam showed me the proof-by-hypercontractivity for Talagrand’s conjecture which is also very pretty (and not-too-complicated). Let me make three comments:
      1) Both Talagrand and me were interested in the late 90s if there is a Fourier proof for the Margulis-Talagrand inequality. (And Michel shot down some suggestions I had.)
      2) Having two major competing methods is often great for an area. Let me mention, simplex algorithm and interior point methods for linear programming as an example.
      3) It would be great to find purely combinatorial proofs to KKL’s theorem. (I spent a lot of time thinking about it over the years.)
      4) There is an old different avenue to KKL via log-Sobolev inequalities by Dvir Falik and Alex Samorodnitsky, and a new paper with yet another avaenue also with log-Sobolev inequality by Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra https://eccc.weizmann.ac.il/report/2020/009/ .

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s