5
$\begingroup$

I am trying to understand the proof of Lemma 4.1.2 in Michel Talagrand's publication from 1995 on concentration inequalities (see below for the precise question statement):


enter image description here


A bit of context: Talagrand fixes a point $x\in X$ (he uses the notation $X=\Omega$) and a subset $A\subset X$, where $X=X_1\times X_2\times\dots X_n$ is the product space of arbitrary non-empty sets $X_1,\dots, X_n$. The $\alpha_i$ and $t$ are all supposed to be positive real numbers. He defines $A_t^c$ as follows:


enter image description here


My question. I understand why (4.1.4) implies (4.1.5). However, Talagrand says that "the converse follows from the Hahn-Banach theorem". How does it follow from the Hahn-Banach theorem?


Note: The problem can be slightly reformulated by saying that we want to prove that for $t>0$ and all $M\subset\{0,1\}^n$, we have that whenever $$\text{for all }\alpha\in]0,\infty[^n, \text{ there exists a } m\in M \text{ such that } \langle \alpha, m \rangle \le t\lVert \alpha\rVert_2,$$ then

$$\min_{m \in \text{Convex hull of } M} \lVert m \rVert_2 \le t.$$

In fact, if somebody can show this, then I will be able to prove the conjecture formulated by me yesterday.

$\endgroup$

1 Answer 1

7
$\begingroup$

To solve the problem you mention at the end you can argue in this way: $$ \min_{m \in \mathrm{conv} (M)} \|m\|_{2}=\min_{m \in \mathrm{conv} (M)} \max_{\|\alpha\|_{2}\leq 1} \langle \alpha, m\rangle = \max_{\|\alpha\|_{2}\leq 1} \min_{m \in \mathrm{Conv}(M)}\langle \alpha, m\rangle \leq \max_{\|\alpha\|_{2}\leq 1, \alpha \in [0, \infty)^{n}} \min_{m \in M}\langle \alpha, m\rangle \leq t $$

The only nontrivial observation was used is min-max theorem, which says that if $X, Y$ are convex compact sets, $f(x,y)$ continuous, convex in $x$ and concave in $y$ then $\min_{x \in X} \max_{y \in Y} f(x,y) = \max_{y\in Y} \min_{x\in X} f(x,y)$. Choose $f(x,y)=\langle x, y\rangle$

$\endgroup$
2
  • $\begingroup$ Amazing! Can't this be used to also directly prove my conjecture here as the last inequality seems like an equality to me if you consider the Bauer maximum principle ? (The right-hand side is just the minimum of norms over the convex hull of $M$.) $\endgroup$ Jun 26, 2020 at 15:30
  • 1
    $\begingroup$ Turns out the answer is "yes, it can!". Please have a look at my answer here which is a very small extension of your answer. $\endgroup$ Jun 26, 2020 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.