Design a site like this with WordPress.com
Get started
Featured

Summer/Fall School, October 10 -14, 2022

I am co-organizing a summer/Fall school which will be held online, October 10-14, 2022. The topic is “Computational Learning Theory and Fourier Analysis”. The deadline to submit the application is July 3rd, 2022. Graduate students and postdocs are welcome to apply.

For more details about the summer school and where to submit the application please see this webpage.

Advertisement

Several results on the Hamming cube under one identity

Since the paper was published, later it became clear that the key identity

\begin{aligned} -\frac{d}{dt} P_{t} f(\varepsilon) =\mathbb{E}_{\xi}\sum_{j=1}^{n} \delta_{j}(t) D_{j}f(\varepsilon \xi(t)) \frac{1}{\sqrt{e^{2t}-1}}\end{aligned}

valid for all functions f :\{-1,1\}^{n} \to X, where X is an arbitrary normed space, implies several important results on the hamming cube. I will briefly list some of these results together with proofs, hints, and references about how they follow from the identity.

  1. Enflo’s problem: in an arbitrary Banach space X, and an arbitrary p>0, the inequality \mathbb{E} ||f(\varepsilon) - f(-\varepsilon) ||^{p} \leq C_{p} \mathbb{E} \sum_{j=1}^{n} ||D_{j} f||^{p} holds with some finite constant C_{p}>0 and all f: \{-1,1\}^{n} \to X, if and only if the inequality holds for linear functions f(\varepsilon) = \sum_{j=1}^{n}x_{j} \varepsilon_{j}.
    Reference: see the paper.
  2. Pisier’s inequality with dimension free constant: In an arbitrary Banach space X, and any 1\leq p<\infty, Pisier’s inequality
    \begin{aligned} \mathbb{E} \|f-\mathbb{E} f\|^{p} \leq C_{p} \mathbb{E} \|\sum_{j=1}^{n} \delta_{j} D_{j}f(\varepsilon)\|^{p}\end{aligned}
    holds with a finite constant C_{p} for all f : \{-1,1\}^{n} \to X and all n \geq 1 if and only if X has finite cotype.
    Reference: see the paper.
  3. Pisier’s inequality with log(n) constant: in an arbitrary Banach space X, the inequality holds
    \begin{aligned} (\mathbb{E} \|f-\mathbb{E} f\|^{p})^{1/p} \leq C_{p} \ln(n) (\mathbb{E} \|\sum_{j=1}^{n} \delta_{j} D_{j}f(\varepsilon)\|^{p})^{1/p}\end{aligned} holds for all f :\{-1,1\}^{n} \to X and all n\geq 1.
    Reference: see my comment to this post. (Thanks to A. Eskenazis for this remark)
    Remark: ln(n) is sharp, the example is due to Talagrand. For p=\infty the inequality holds without \ln(n) factor (see this post).
  4. L1 Poincaré inequality on the Hamming cube: for any f :\{-1,1\}^{n} \mapsto \mathbb{C} we have
    \begin{aligned} \mathbb{E} |f-\mathbb{E}f| \leq \frac{\pi}{2} \mathbb{E} |\nabla f| \end{aligned}
    Reference: here is the proof from the identity
    \begin{aligned}\mathbb{E} |f - \mathbb{E}f| \leq \int_{0}^{\infty} \mathbb{E}_{\varepsilon} \mathbb{E}_{\xi}|\sum_{j=1}^{n} \delta_{j}(t)D_{j} f(\varepsilon \xi(t)) | \frac{dt}{\sqrt{e^{2t}-1}} = \int_{0}^{\infty} \mathbb{E}_{\varepsilon} \mathbb{E}_{\xi}|\sum_{j=1}^{n} \delta_{j}(t)D_{j} f(\varepsilon) | \frac{dt}{\sqrt{e^{2t}-1}}\end{aligned}
    \begin{aligned} \stackrel{Cauchy-Schwarz}{\leq} \int_{0}^{\infty}\mathbb{E}_{\varepsilon} \|\nabla f\| \frac{dt}{\sqrt{e^{2t}-1}} = \frac{\pi}{2} \mathbb{E}_{\varepsilon} \|\nabla f\|\end{aligned}.
    Remark: one can also get L^{p} Poincaré inequality \|f-\mathbb{E}f\|_{p} \leq C_{p} \|\nabla f\|_{p} with constant C_{p} \approx p^{3/2} using the identity, however, this does not give the correct growth on C_{p}. The correct grow is of order \sqrt{p}, and this grow can be obtained using the identity in a much more subtle way.
  5. Talagrand’s conjecture: There exists a universal finite constant C>0 such that for a f:\{-1,1\}^{n} \mapsto \{0,1\} we have
    \begin{aligned} \mathbb{E} |f-\mathbb{E}f|^{2} \leq C \frac{\mathbb{E} \|\nabla f\| }{\sqrt{\ln \left(2+ \frac{e}{\sum_{j=1}^{n} (\mathbb{E} |D_{j} f|)^{2}} \right)}}\end{aligned}.
    Reference: see Ramon van Handel’s lecture.
    Hint: Notice a wonderful equality \mathbb{E} |f-\mathbb{E}f|^{2} = (1/2)\mathbb{E} |f-P_{t}f|+\mathbb{E}|P_{t/2}f-\mathbb{E}f|^{2} for all t\geq 0. Indeed, since f takes values 0 or 1 you can write |f-P_{t}f| =f(1-P_{t}f)+(1-f)P_{t}f and now take the expectation. Next estimate the first term \mathbb{E} |f-P_{t}f| by \sqrt{t} \mathbb{E}|\nabla f| just by integrating the identity from 0 to t, and assuming t<10. By martingale arguments and hypercontractivity the second term \mathbb{E}|P_{t/2}f-\mathbb{E}f|^{2} can be estimated as \mathbb{E}|f-\mathbb{E}f|^{2} (4\sum_{j=1}^{n}(\mathbb{E}|D_{j}f|)^{2})^{\frac{1-e^{-t}}{2(1+e^{-t})}}. Now choose t=\frac{C_{1}}{\log(2+\frac{C_{2}}{\sum_{j=1}^{n}(\mathbb{E}|D_{j}f|)^{2}})} for some positive constants C_{1}, C_{2}.
  6. Kahn-Kalai-Linial inequality (KKL inequality): For any boolean function f : \{-1,1\}^{n} \mapsto \{-1,1\} one has
    \begin{aligned} \mathbb{E}|f-\mathbb{E}f|^{2} \lesssim \frac{\sum_{j} \mathbb{E} |D_{j}f|}{-\log(\max_{j} \mathbb{E} |D_{j}f|))} \end{aligned}.
    Remark 1: In a literature the objects \mathbb{E} |D_{j} f| are called influences in variable j and are denoted as \mathrm{Inf}_{j}(f). KKL inequality has several important corollaries. One of them says that any boolean function with nonzero variance \mathbb{E} |f-\mathbb{E}f|^{2} >\delta>0 has an influential variable \max_{j}\mathbb{E} |D_{j}f| > C(\delta) \frac{\ln n}{n}. To verify the corollary, it is a calculus problem to show that if \delta \lesssim \frac{n t}{-\log t} for some t \in [0,1] then t \geq C(\delta) \frac{\ln(n)}{n}. In fact, this corollary is called KKL theorem, however, it is not hard to see that the theorem follows from the techniques of the original paper of KKL: one starts with the equality \sum_{j=1}^{n} \| D_{j} f\|_{2}^{2} = \sum_{S \neq 0} |S| |\hat{f}(S)|^{2}, and “amplifies” it by applying the equality to P_{t} f instead of f, after which the fourier coefficients change as \widehat{P_{t}f}(S) = e^{-t|S|}\hat{f}(S). Finally, one integrates the both sides of the equality with respect to the measure e^{-t}dt on [0,\infty), and applies the hypercontractivity to get the inequality

    \int_{0}^{\infty} \| P_{t}D_{j} f\|_{2}^{2}e^{-t}dt \leq C \frac{\|D_{j} f\|_{1}}{\ln(e/\|D_{j} f\|_{1})}

    Remark 2: another nice corollary of KKL theorem is that if you have a monotone function f: \{-1,1\}^{n} \mapsto \{-1,1\} such that \mathbb{E}f>-0.99, then one can find about O(n/\ln(n)) variables J such that if we assign them values 1 then the average of f with respect to the rest of the variables will become at least 0.99. In social choice this means that in a monotone election, a candidate can bribe around O(n/\ln(n)) votes to win the election. To obtain this corollary, first switch the most influential variable to 1, and repeat these steps O(n/\ln(n)) times. Notice that on each step k we get a new function f_{k+1}, and it follows from monotonicity that \mathbb{E}f_{k+1}=\mathbb{E}f_{k}+\max_{j}|D_{j}f_{k}|>\mathbb{E}f_{k}+O(\ln(n)/n).
    Reference: One can get corollary on the lower bound \ln(n)/n in KKL inequality from Talagrand’s conjecture, however, this looks like to be a long path. So here is the proof of the KKL inequality via the identity. Since f is boolean |D_{j}f|^{p}=|D_{j}f| for any p>0. Apply the identity to P_{t}f instead of f, integrate over [0,\infty) in dt, and take the L^{2} norm of both sides. We obtain
    \begin{aligned}\|f-\mathbb{E} f\|_{2} \lesssim \int_{0}^{\infty} \left(\sum_{j=1}^{n} \| D_{j} P_{t} f\|_{2}^{2} \right)^{1/2}\frac{dt}{\sqrt{e^{2t}-1}} \stackrel{hypercon.}{\leq} \int_{0}^{\infty} \left(\sum_{j=1}^{n} (\mathbb{E} | D_{j} f|)^{\frac{2}{1+e^{-2t}}} \right)^{1/2}\frac{dt}{\sqrt{e^{2t}-1}} \end{aligned}
    \begin{aligned} \leq \sqrt{\sum_{j} |D_{j} f|_{1}} \int_{0}^{\infty} (\max_{j} |D_{j}f|_{1})^{\frac{1-e^{-2t}}{2(1+e^{-2t})}} \frac{dt}{\sqrt{e^{2t}-1}} \leq \sqrt{\sum_{j} |D_{j} f|_{1}} \int_{0}^{1} \frac{(\max_{j} |D_{j} f|_{1})^{(1-y)/2}}{\sqrt{1-y}}dy\end{aligned}
    \begin{aligned} = \sqrt{\frac{\sum_{j} |D_{j} f|_{1}}{-\log \max_{j} |D_{j}f|_{1}}} \int_{0}^{-\log \max_{j} |D_{j}f|_{1}} \frac{e^{-s/2}}{\sqrt{s}}ds \leq \sqrt{\frac{\sum_{j}|D_{j}f|_{1}}{-\log \max_{j} |D_{j}f|_{1}}} \,\sqrt{2\pi} \end{aligned}.

    Remark: The advantage of this “more involved” proof I presented above is that it extends to Banach space valued functions having Rademacher type 2. See this paper. Such an extension cannot be obtained with original arguments because, otherwise, this would solve Enflo’s problem which was open for a long time.