1
$\begingroup$

Let $f_j:\mathbb{R}^n\to\mathbb{R}$ be a set of 1-Lipschitz functions for $1\leq j\leq M$. From Gaussian isoperimetry or a log-Sobolev inequality, it can be shown that $$ \mathbf{Pr}(|f_j(X)-\mathbf{E}f_j(X)|\geq t) \leq C\exp(-ct^2) $$ where the probability distribution over $X$ is the standard Gaussian.

I wonder if there exist conditions which guarantee any extra concentration for the variable $$ \min_{1\leq j\leq M} |f_j(X) - \mathbf{E} f_j(X)|. $$ For example, if $n=M$ and $f_j(X)$ is simply the $j$-th coordinate, then one gains a factor of $M$ in the exponent.

This makes me wonder if a sufficient condition is to ask that $\langle f_j,f_k\rangle = 0$ when $j\not= k$. The intuition is that the level sets of the medians of $f_j$ are orthogonal to each other, so their intersections have higher codimension, and in particular the volume of their union is roughly additive. Is this correct?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.