6
$\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$
1
  • 2
    $\begingroup$ Theorem 3 of this paper of Adamczak provides a sufficient condition, albeit slightly stronger than subgaussianity. $\endgroup$
    – Clement C.
    Feb 6, 2021 at 5:01

1 Answer 1

6
$\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$
2
  • $\begingroup$ Did you end up figuring out the answer to the last question? $\endgroup$
    – Clement C.
    Feb 5, 2021 at 5:28
  • 1
    $\begingroup$ @ClementC. No... Please ping me again if no answer is forthcoming -- might need to roll up my sleeves on this one... (Or maybe assign it to students ;) $\endgroup$ Feb 5, 2021 at 12:51

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.