1
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Do you know of a sampling method that is faster then MC? I was hoping that there would be some way of exploiting the fact that we are dealing with this optimization setup to save some computations. For example if we use gradient descent then for $\theta_{n+1}$ we could choose $\theta_{min} \in \lbrace \theta_1, ... , \theta_n \rbrace $ closest to $\theta_{n+1}$ and initialize the descent by starting at $x^*_{min}$. Intuitively it makes sense to me that the later into sampling we get the cheaper the descent becomes. Do you know of some literature that contains some theory on this? $\endgroup$ Mar 6 '18 at 11:09
  • 1
    $\begingroup$ If you had some relationship between $g(\theta_n)$ and $g(\theta_m)$ ,call it $h(g(\theta_n),\theta_m)\rightarrow \mathcal{X}$,such that if you sampled $\theta_m$ after sampling $\theta_n$, you didn't have to resolve the optimization problem but could just solve $h(g(\theta_n),\theta_m) = g(\theta_m)$ then you could do that. Otherwise I don't know much about it, but there may be some general theory someone else could comment on. $\endgroup$ Mar 7 '18 at 6:22
  • $\begingroup$ I'm assuming that you can't solve the general problem by evaluating the pushforward measure in closed form from $D$ and the optimization problem; if there was a mathematically tractable way to do that you could try it. You don't even need to necessarily have a full form of the density. You could get it unnormalized and approximate it using rejection sampling or something, and that might be faster than recomputing the optimization problem from the sampled $\theta$. $\endgroup$ Mar 7 '18 at 6:24
  • $\begingroup$ The approach using $h$ seems promising. I will look into that. Thanks for the help! Yes, I am assuming that the optimization problem cannot be solved analytically but is still computationally tractable. $\endgroup$ Mar 7 '18 at 9:38

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.