0
$\begingroup$

This question was asked here, but I have reason to believe that it's a serious research question appropriate for this forum (also, the answers given at the link aren't satisfactory).

​If $X\in\mathbb{R}^n$ is a random vector with independent $\sigma$-subgaussian components and $f:\mathbb{R}^n\to\mathbb{R}$ is $L$-Lipschitz (w.r.t. $\ell_2$), can the subgaussian moment of $f(X)$ be bounded in terms of $\sigma$ and $L$, independently of $n$?

I am told that the answer is no, so the first "real" question is to produce a counterexample. A second question is: What (hopefully mild) additional assumptions need to be made to make the answer positive?

$\endgroup$
0
$\begingroup$

A counterexample to the first part is obtained by considering the uniform distribution on $\{0,1\}^n$, for $n$ even, defining $A\subset\{0,1\}^n$ by $A=\{x:\sum_{i=1}^n x_i\le n/2\}$, and defining $f(x)=\inf_{y\in A}||x-y||$. Then $f$ is a Lipschitz function of iid subgaussian random variables yet fails to satisfy subgaussian concentration. The detailed argument is worked out in Ledoux and Talagrand (1991, p. 17), and also appears as Exercise 6.4 in the Boucheron-Massart-Lugosi concentration-of-measure book.

An additional assumption to make the claim hold is to assume that $f$ is separately convex (Exercise 6.5 in the Boucheron-Massart-Lugosi book), but annoyingly, the support of the distribution is assumed to be compact. Question: does the subgaussian concentration claim hold for separately convex Lipschitz functions of independent subgaussian random variables without assuming compact support?

$\endgroup$

Your Answer

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

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