Stochastic Optimization Techniques

169 Views Asked by At

I am looking to collect stochastic optimization techniques that would say under what conditions \begin{align} E[ f(X_2)] \le E[ f(X_1)]. \end{align} for some random variables $X_1$ and $X_2$. Here is an example of one such result that I am aware of

If $X_1$ stochastically dominates $X_2$ and $f(x)$ is non-decreasing then \begin{align} E[ f(X_2)] \le E[ f(X_1)]. \end{align} Where $X_1$ stochasticly dominates $X_2$ if $F_{X_1}(x) \le F_{X_2}(x)$ for all $x$.

The above is an example of first order stochastic dominance. There are other similar notions called second and third order stochastic dominance.

This is tool can be very powerful in some stochastic optimization scenarios. However, it has its limitations. That is why I would like to collect of few other results that say under what conditions expectation with respect to distribution $X_1$ is larger (or smaller) than expectation with respect to $X_2$.

If anyone is aware of any other result with similar flavor or any good reference, please let me know. Thank you.

1

There are 1 best solutions below

1
On

Suppose $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is a convex function. Let $\vec{X}_1$ and $\vec{X}_2$ be random vectors with the same mean, so that $E[\vec{X}_1]=E[\vec{X}_2]=\vec{m}$ for some vector $\vec{m} \in \mathbb{R}^n$. Further suppose $\vec{X}_2$ has the same distribution as $\vec{m} + \theta(\vec{X}_1-\vec{m})$ for some constant $\theta \in [0,1]$. So $\vec{X}_2$ has a distribution that is scaled to make it more tightly concentrated about the mean. Then:

$$E[f(\vec{X}_2)] \leq E[f(\vec{X}_1)] $$

This can be viewed as a generalization of Jensen's inequality (the case $\theta=0$ is exactly Jensen's inequality and gives $f(\vec{m}) \leq E[f(\vec{X}_1)]$).

Proof: \begin{align} E[f(\vec{X}_2)] &= E[f(\vec{m} + \theta(\vec{X}_1-\vec{m}))]\\ &=E[f((1-\theta)\vec{m} + \theta \vec{X}_1)] \\ &\leq E[(1-\theta) f(\vec{m}) + \theta f(\vec{X}_1)] \quad \mbox{[since $f$ is convex]}\\ &= (1-\theta)f(E[\vec{X}_1]) + \theta E[f(\vec{X}_1)]\\ &\leq (1-\theta)E[f(\vec{X}_1)] + \theta E[f(\vec{X}_1)] \quad \mbox{[by Jensen's inequality]}\\ &= E[f(\vec{X}_1)] \end{align} $\Box$