Transformation of probability distribution under optimization

Question

I have a parametric strictly convex optimization problem with parameter $\theta$. This defines a mapping $f: \theta\mapsto x^*$, where $x^*$ is the unique optimal solution of the optimization problem with input $\theta$. Suppose $\theta$ is a random variable following some distribution $D$. I want to study the distribution of $x^*$ (both analytic and efficient sampling is fine). I would be glad if someone can point me to some literature regarding specific instances of this kind of problem or some general theory.

Answer 1

If you can evaluate $x^* = g(x) = \min_x f_\theta(x) : \theta \rightarrow x^*$, and can sample from $D$, then you can sample from an induced probability measure on $x^*$ by doing the following. Specifying $N$ as the number of desired samples:

For $n \in \{1,...,N\}$:

1. Sample $\theta_n \sim D$
2. Evaluate $x_n^* = g(\theta_n) = \min_x f_{\theta_n}(x)$
3. Store sample and repeat

This property about being able to induce the randomness in $x^*$ based on the randomness in $\theta$ is known as a Pushforward Measure.

You have a measure space $(\Theta,\mathcal{A})$ with a measure on it defined by $D$, and another measurable space $(\mathcal{X},\mathcal{B})$ and a measurable function $g(\theta): \Theta \rightarrow \mathcal{X}$. In this setting the randomness on $\theta$ from the measure $D$ induces a distribution on a deterministic function of $\theta$. The way to evaluate this without sampling is to do a change of variables from $\theta = g^{-1}(x)$ in the density for D.

Doing that change of variables could be difficult because your function $g$ is the solution to an optimization problem and could be hard to invert, for example if $g(\theta)$ is convex but not monotonic.

However, if the optimization is time consuming, then sampling each $x_n^*$ in the preceding algorithm could be slow.

Which one is better depends on the definition of $g(\theta)$ and $D$, and would probably be problem specific.