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?


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.