8
$\begingroup$

Here is the simplest statement of my question:

Let $Y$ be a centered real random variable and define $$\|Y\|_* = \sup \left\{ \mathbb{E}[X \cdot Y] ~:~ \forall t \in \mathbb{R} ~~ \mathbb{E}[e^{tX}] \le e^{t^2/2}\right\},$$ where the supremum is over real random variables $X$ that may depend on $Y$.

Is there a closed-form expression for $\|Y\|_*$? (Or a good closed-form approximation.)


Here is a more detailed statement of my question:

Define a norm on the space of random variables by $$\|X\| := \inf \left\{ \max\{|\mu|,|\sigma|\} : \mu,\sigma \in \mathbb{R},~~\forall t \in \mathbb{R} ~~~ \mathbb{E}\left[e^{tX}\right] \leq e^{t\mu+t^2\sigma^2/2} \right\}.$$

If $\|X\|$ is finite, then $X$ is said to be subgaussian. The norm is scaled to have the property $\|\mathcal{N}(\mu,\sigma^2)\|= \max\{|\mu|,|\sigma|\}$. By Hoeffding's lemma, we have $$\|X\| \leq \|X\|_\infty := \inf\{\tau:\mathbb{P}[|X|\leq\tau]=1\},$$ i.e., bounded random variables are also subgaussian.

I'm interested in the dual norm, defined by $$\|Y\|_* := \sup \left\{ \mathbb{E}[X \cdot Y] : X \text{ is a random variable satisfying } \|X\| \leq 1 \right\}.$$ Of course, $X$ and $Y$ are not independent in the above supremum.

Is there a simple expression for the dual norm $\|\cdot\|_*$? I would like to be able to calculate $\|\cdot\|_*$ and the definition above is not useful. Even a good approximation to the dual norm would be helpful.



Below are various things I know or think about this question, which may be helpful for answering it.

My intuition is that $\|\cdot\|\approx\|\cdot\|_\infty$, as, in my experience, most properties of bounded random variables extend to subgaussian random variables. Since the $1$-norm is the dual of the $\infty$-norm, my intuition is that $\|\cdot\|_*\approx\|\cdot\|_1$.

This intuition can be made a bit more formal by looking at $p$-norms, as follows. It is easy to show that $$\|X\|_p := \mathbb{E}[|X|^p]^{1/p} \leq (\sqrt{p}+2) \cdot \|X\|$$ for all $p \in [1,\infty)$ and all subgaussian $X$. Thus, by Hölder's inequality, for all $p \in (1,\infty)$ and all random variables $X$ and $Y$, $$\mathbb{E}[X \cdot Y] \leq \|X\|_p \cdot \|Y\|_{1+\frac{1}{p-1}} \leq O(\sqrt{p}) \cdot \|X\| \cdot \|Y\|_{1+\frac{1}{p-1}}.$$ Hence $\|Y\|_* \leq O\left(\frac{1}{\sqrt{\varepsilon}}\right) \cdot \|Y\|_{1+\varepsilon}$ for all $\varepsilon > 0$. Since $\|X\| \leq \|X\|_\infty$, we also have $\|Y\|_* \geq \|Y\|_1$.

Here is an example that "breaks" this intuition. However, it only slightly breaks it, which is why I think the intuition is still correct. Let $X$ be a standard Gaussian and $Y=\mathsf{sign}(X) \cdot e^{X^2/2}/(1+X^2)$. Then $\|X\|=1$, but $\|X\|_\infty = \infty$. And $\|Y\|_1 = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^\infty \frac{1}{1+x^2} \mathrm{d}x = \sqrt{\frac{\pi}{2}}$, while $\|Y\|_* \geq \mathbb{E}[XY] = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^\infty \frac{|x|}{1+x^2} \mathrm{d}x = \infty$. However, note that $\mathbb{E}[|Y|\log|Y|]=\infty$, so one only needs something "slightly larger" than the $1$-norm for this example. My intuition is that, in general, $\|\cdot\|_*$ is only slightly larger than $\|\cdot\|_1$.

My guess is that the answer is something asymptotically like $\|Y\|_* \overset{?}{=} \mathbb{E}\left[|Y|\sqrt{\log(1+|Y|)} \right]$. Has anyone seen a norm like this before? (I can show that, if $\mathbb{E}\left[|Y|\sqrt{\log(1+|Y|)} \right]=\infty$, then $\|Y\|_*=\infty$.)

I can prove the following upper bound on the dual norm. This is the strongest bound I have been able to prove so far. $$\|Y\|_* \leq \sqrt{2} \mathbb{E}[|Y|] + 4\sqrt{\mathbb{E}[|Y|] \cdot \left(\mathbb{E}[|Y|\log|Y|] - \mathbb{E}[|Y|]\log\mathbb{E}[|Y|]\right)}.$$ Note that by Jensen's inequality and the convexity of $x \mapsto x \log x$, we have $\mathbb{E}[|Y|\log|Y|] \geq \mathbb{E}[|Y|]\log\mathbb{E}[|Y|]$. So the right hand side of the above bound is well-defined and non-negative. Multiplying $Y$ by a constant also multiplies the expression by that constant. So this expression is almost a norm, although I don't know if it satisfies the triangle inequality.

Furthermore, if $\mu=\mathbb{E}[Y]$, then $\|Y\|_* = |\mu| + \|Y-\mu\|_*$. This centering can also be combined with the above bound.

$\endgroup$
  • $\begingroup$ Nice question! Note that if $Y$ is symmetric then $\|Y\|_*=0$. Maybe you meant using $\mathbb E|X\cdot Y|$ instead? $\endgroup$ – Adrien Hardy Sep 21 '17 at 21:09
  • $\begingroup$ It is tempting to use that the Legendre transform of $f(x)=e^{tx}$ with $t>0$ is $f^*(y)=\frac yt(\log\frac yt -1)$ for $y>0$ in order to get an upper bound on $\|Y\|_*$, but the signs make thinks ugly. I imagine this was the starting point for your guess, doesn't it? $\endgroup$ – Adrien Hardy Sep 21 '17 at 21:12
  • $\begingroup$ I would expect that, in order to achieve the sup in the dual norm definition, $X$ and $Y$ would always have the same sign so that $\mathbb{E}[XY]=\mathbb{E}[|XY|]$. I don't have a good justification for my guess; I was actually thinking about KL divergence. But it definitely breaks due to the sign issue. $\endgroup$ – Thomas Sep 21 '17 at 22:41
  • $\begingroup$ For non-negative $Y$, we have $\mathbb{E}[XY] \leq \mathbb{E}[Y \log Y] - \mathbb{E}[Y] \log \mathbb{E}[Y] + \mathbb{E}[Y] \log \mathbb{E}[e^{X}]$. This feels like a relevant bound, but I don't know what to do with it. $\endgroup$ – Thomas Sep 21 '17 at 22:51
  • $\begingroup$ If we change tack a little, and use the equivalent (up to constants) definition of the subGaussian norm as $\|X\| := \inf\{ t > 0: \mathbb{E}[ e^{X^2/t^2} - 1] \le 1\},$ then one can invoke (i.e. look up :P) the theory of Orlicz spaces to give characterisations. I don't really know much functional analysis, but this seems to provide $\endgroup$ – stochasticboy321 Oct 29 '19 at 2:36
1
$\begingroup$

I do not have an answer, but have derived a dual formulation that produces an upper bound. For fixed $y$, you are interested in: \begin{align} \max &\int_\mathbb{R} xy f(x) dx \\ \text{s.t.} &\int_\mathbb{R} \exp(tx) f(x) dx \leq \exp(t^2 / 2) \quad\forall t\\ &\int_\mathbb{R} f(x) dx = 1\\ &f(x) \geq 0 \end{align} This is a linear optimization problem with optimization variables $f(x)$. Its dual is: \begin{align} \min &\int_\mathbb{R} \exp(t^2 / 2) g(t) dt + \mu \\ \text{s.t.} &\int_\mathbb{R} \exp(tx) g(t) dt + \mu \geq xy \quad\forall x \\ &g(t) \geq 0, \mu \geq 0 \end{align} The first constraint in the dual can be written as $$\min_{x,\nu} \left\{ \int_\mathbb{R} \exp(t \nu(t)) g(t) dt - xy : \nu(t)=x \right\} \geq -\mu$$ Let's dualize the left part of this constraint via the Lagrangian: $$L(x,\nu,\lambda) = \int_\mathbb{R} \exp(t\nu(t)) g(t) dt - xy + \int_\mathbb{R} \lambda(t) (x - \nu(t)) dt$$ You need $\int_\mathbb{R} \lambda(t) dt = y$ as otherwise the value is $-\infty$ (by letting $x \to \pm \infty$) and the constraint is violated, so the terms with $x$ vanish. The derivative of $L$ with respect to $\nu(t)$ is $\exp(t \nu(t)) t g(t) - \lambda(t)$. Therefore, $\lambda(t) \geq 0$ for $t>0$ and $\lambda(t) \leq 0$ for $t<0$ (as otherwise the value is $-\infty$), and settings the derivative to $0$ yields:

\begin{align} \min &\int_\mathbb{R} \exp(t^2 / 2) g(t) dt + \mu \\ \text{s.t.} &\int_\mathbb{R} \frac{\lambda(t)}{t} \left( 1 - \log\left( \frac{\lambda(t)}{tg(t)} \right) \right)dt \geq -\mu \\ & \int_\mathbb{R} \lambda(t) dt = y \\ & t \lambda(t) \geq 0 \quad \forall t \\ &g(t) \geq 0, \mu \geq 0, \lambda(t) \in \mathbb{R}. \end{align} You can substitute out $\mu$: \begin{align} \min &\int_\mathbb{R} \exp(t^2 / 2) g(t) dt + \max\left\{0, \int_\mathbb{R} \frac{\lambda(t)}{t} \left( \log\left( \frac{\lambda(t)}{tg(t)} \right) - 1 \right) dt \right\} \\ \text{s.t.} & \int_\mathbb{R} \lambda(t) dt = y \\ & t \lambda(t) \geq 0 \quad \forall t \\ &g(t) \geq 0, \lambda(t) \in \mathbb{R}. \end{align} Any feasible pair $(g(t), \lambda(t))$ yields an upper bound to the dual norm.

$\endgroup$
  • $\begingroup$ I don't quite understand why, but I never got to award the bounty (the option was never available). $\endgroup$ – Clement C. Nov 8 '19 at 1:36
  • $\begingroup$ @ClementC. thanks for mentioning! I had already assumed you did not award it because I did not answer the question. $\endgroup$ – LinAlg Nov 8 '19 at 2:12
  • $\begingroup$ Oh, well -- the points have been taken from my account, so the very least would be to give them to someone instead of just having them disappeared; and your answer provides a non-trivial step... but I didn't get any occasion to award anything. $\endgroup$ – Clement C. Nov 8 '19 at 3:16

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.