Let $\mathbf{a}_1,\ldots,\mathbf{a}_n \in \mathbb R^d$ and $b_1,\ldots,b_n \in \mathbb R$ be fixed. For $\mathbf{x} \sim \mathcal U([0,1]^d)$ and $j \in \{1,\ldots,n\}$, consider the real variable defined by the softmax / "logistic" transformation

$$y_j(\mathbf{x}) = \frac{\exp(\mathbf{a}_j^T \mathbf{x} + b_j)}{\sum_{k=1}^n\exp(\mathbf{a_k}^T\mathbf{x} + b_k)}. $$

I'm interesting in an efficient way to compute the expected value of $y_j$.

Poorman's solution:

  • Draw $\mathbf{x}_1,\ldots,\mathbf{x}_N \sim \mathcal U([0,1]^d)$
  • Compute the empirical mean $\hat{\mu}_N(y_j) := \frac{1}{N}\sum_i^N y_j(\mathbf{x}_i)$.

For sure, $\hat{\mu}_N(y_j) \overset{N \rightarrow \infty}{\longrightarrow} \mathbb E_{\mathbf{x} \sim \mathcal U([0,1]^d)} [y_j(\mathbf{x})]$ by law of large numbers.


  • How to make the above "poorman's solution" faster (i.e high accuracy with small $N$) ?

  • How can "importance sampling" be used to accomplish this ?

Details will be very much appreciated.

  • $\begingroup$ Why are you assuming $x_i$ are uniform? Wouldn't it make more sense to assume they are sampled from your data distribution? $\endgroup$ – Alex R. Dec 5 '17 at 19:14
  • 1
    $\begingroup$ It's not just an artificial assumption, it's part of the problem data... $\endgroup$ – dohmatob Dec 5 '17 at 19:49
  • $\begingroup$ not importance sampling, but for small $d$, quasi-Monte Carlo would give you a better convergence rate w.r.t $N$ $\endgroup$ – πr8 Feb 12 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.