Upper bound for distance between the expectations from two distributions

Question

Suppose there are two distributions $P$ and $Q$ on a common measurable space, and $f$ is a smooth and convex function, e.g., a quadratic function. I wonder if there are nice upper bounds for the following distance \begin{equation} |\mathbb{E}_{\xi\sim P}[f(\xi)] - \mathbb{E}_{\xi\sim Q}[f(\xi)]|. \end{equation} I feel like the total variation distance $\operatorname{TV}(P,Q)$ might be related, since $|\mathbb{E}_{\xi\sim P}[f(\xi)] - \mathbb{E}_{\xi\sim Q}[f(\xi)]| \le \int_x |f(x)|\cdot|p(x)-q(x)| \, dx$. However, if $f$ does not have an upper bound, this will not give a nice upper bound.

Answer 1

As stated, there are no general bounds possible. Taking $f(x) = x$ with the domain $\mathbb{R}$ and letting $P$ be distributed as a Cauchy random variable results in the quantity of interest to you being infinite. As it stands, there's nothing guaranteeing the expectations are finite nor that the difference is finite. About the only thing that can be said is

$$|\text{E}_P[f] - \text{E}_Q[f] | \leq |\text{E}_P[f]| + |\text{E}_Q[f]| $$

The convexity of $f$ allows an application of Jensen's inequality to say that $E[f(x)] \geq f(E[x])$ but that hits a dead-end with the difference of expectations.

If you're willing to drop the assumption of convexity of $f$ and instead require that $||f|| \leq 1$ for some appropriate norm, you may be able to make use of the maximum mean discrepancy which is typically found applied in functional analysis and kernel learning but has a conveniently familiar form if using $||f||_2 \leq 1$:

$$MMD(P, Q) = \sup_{||f||_2 \leq 1} E_P[f]-E_Q[f]$$

Some basic calculus of variations shows that the maximizer is given by

$$f(x) = \frac{p(x) - q(x)}{||p-q||_2}$$

And the supremum by

$$ MMD(P, Q) = ||p-q||_2 $$

Finally, we can put this all together with the definition of the supremum to show that

$$ E_P[f] - E_Q[f] \leq \sup_{||g||_2 \leq 1} E_P[g] - E_Q[g] = ||p-q||_2 $$

Note that the lack of absolute value signs on the left hand side is not an issue because of the symmetry of MMD in P and Q. Swapping them gives the inequality

$$-(E_P[f]-E_Q[f]) \leq ||p-q||_2$$

$$ \implies -||p-q||_2 \leq E_P[f]-E_Q[f] \leq ||p-q||_2 \implies$$

$$|E_P[f]-E_Q[f]| \leq ||p-q||_2$$

This is an upper bound that does not depend on anything about $f$ except for the fact that it lies within the unit ball* in the $L^2$ norm. The gist of the proof is the same if using another norm but it may be easier to apply to your uses since they will give different bounds, the differences in the proof only come in calculating the supremum.

* since your function of interest is homogeneous of order 1, scalar multiples of $f$ give a scalar multiple of the difference in expectations, so if $||f||\leq \alpha$ is known you can use $|E_P[f]-E_Q[f]| \leq \alpha ||p-q||$ and you may apply this argument to any $f$ with a bounded norm.

Answer 2

When looking at expressions of form $\sup_{f} \mathbb{E}_{x \sim P} f(x) - \mathbb{E}_{x \sim Q} f(x)$, we usually restrict our attention to $f \in \mathcal{F}$ which are somehow bounded. In particular, if we have a norm $\|\cdot\|_N$ on the space of functions under consideration, than basically by the definition of the dual norm we get $$\sup_{f : \|f\|_N \leq 1} \mathbb{E}_{x \sim P} f(x) - \mathbb{E}_{x \sim Q} f(x) \leq \|P - Q\|_{N^*},$$ where $\|\cdot\|_{N^*}$ is the dual norm, but crucially this dual norm can often be explicitly described. This includes the case of $f$ bounded in $\| \cdot \|_\infty$ norm discussed in OP, which leads to the upper bound on $\mathbb{E}_{x \sim P} f(x) - \mathbb{E}_{x \sim Q} f(x)$ by the TV distance between $P$ and $Q$.

Moreover, if we start with the family of $f$ bounded in $\| \cdot\|_2$ with respect to some base measure, this leads to the upper bound by $\|P - Q\|_2$ mentioned in the Camerons answer. Finally, if the constraint on the test functions is having bounded Lipschitz constant (this is not quite a norm, but it does not matter, the core of the argument is essentially the same), we arrive at the upper bound of the difference between expectations by Wasserstein distance between the two distributions, as mentioned in the usuls comment (see Kantorovich-Rubinstein duality).

Can we improve upon these bounds with the additional information that we care only about the convex test function (but still bounded with respect to $\|\cdot\|_N$)?

For two distributions $P_1$ and $Q_1$, I will write $P_1 \preceq Q_1$ if there exist a coupling $(x, t, y)$ s.t. $y \sim P_1$, $x \sim Q_1$ and $\mathbb{E}[x | t] = y$.

Note that if we have any two distributions satisfying $P_1 \preceq Q_1$, we can deduce that for any convex function $f$, we have $\mathbb{E}_{x \sim P_1} f(x) \leq \mathbb{E}_{x \sim Q_1} f(x)$. Indeed, $$\mathbb{E}_{x \sim Q_1} f(x) = \mathbb{E}[\mathbb{E}[ f(x) | t ]] \geq \mathbb{E}[ f (\mathbb{E}[x | t]) ] = \mathbb{E}_{y \sim P_1} [f(y)].$$

Hence, for any two distributions $P, Q$, if we are able to decompose them as mixtures $P= \alpha P_1 + (1 - \alpha) P_2$ and $Q = \alpha Q_1 + (1-\alpha) Q_2$, s.t. $P_2 \preceq Q_2$, then we will have $$\sup_{\|f\|_N \leq 1, f \text{ is convex}} \mathbb{E}_{x \sim P} f(x) - \mathbb{E}_{x \sim Q} f(x) \leq \alpha \|P_1 - Q_1\|_{N^*}.$$

To get the other inequality $\mathbb{E}_{x \sim Q} f(x) - \mathbb{E}_{x \sim P} f(x) \leq T$ we need in turn to find a decomposition in the opposite direction: i.e. find $P = \alpha' P'_1 + (1-\alpha') P'_2$, and $Q = \alpha' Q'_2 + (1 - \alpha') Q'_2$ s.t. $Q'_2 \preceq P'_2$.

I imagine that usually the strong duality should hold here: for any pair of distributions $P, Q$, the $$\sup_{\|f\|_N \leq 1, f \text{ is convex}} |\mathbb{E}_{x \sim P} f(x) - \mathbb{E}_{x \sim Q} f(x)|$$ should be equal to the infinium over upper bounds that can be obtained via this method.

Unfortunately, it seems that in most cases those upper bounds are less than workable --- finding a useful decomposition of $P$ and $Q$ into mixtures satisfying the desired property is probably something that we very rarely will be able to accomplish in practice, and especially if we need bounds in both directions.