How sensitive are probability distributions to noise?

Question

I'm trying to prove a result but I'm stuck at the very end of it: I'm having troubles understanding how noise propagates when considering a probability distribution. In other words, if I inject some noise in a vector, how does it change its probability distribution? Let's give some notation:

Let $\sigma: \mathbb{R}^d \rightarrow (0,1)^d$ be the softmax operator which maps $x$ to the manifold of the probability distributions on $d$ variables defined in the following way: $$\sigma(x)_i = \frac{e^{x_i}}{\sum_j e^{x_j}}$$ I have a vector $x \in \mathbb{R}^d$ with norm one. I also have random noise vector $\eta \in \mathbb{R}^d$ with norm $1/k$ taken uniformely at random from the sphere $S^{d-1}$ of radius 1/k, where k is a large natural number.

I need to compute an upper bound of the following expected value, which is the norm of the difference between the vector without noise and the one with injected noise $\eta$:

$$ \mathbb{E}[||\sigma(x) - \sigma(x+\eta)||]$$

I gave a bounty to this question because I really need to understand this problem (I will have to solve several problems of this kind).

Thank you very much!

Answer 1

$$\mathbb{E}(|\sigma(x+\eta)-\sigma(x)|)=\mathbb{E}(|J_\sigma\eta|)+O(|\eta|^2)$$where $J_\sigma$ is the Jacobi matrix $$ (J_\sigma)_{i,j}=\frac{e^{x_i}}{\sum_k e^{x_k}}\delta_{i,j} - \frac{e^{x_i+x_j}}{(\sum_k e^{x_k})^2}$$ and $$\mathbb{E}(|J_\sigma\eta|)^2\leq \mathbb{E}(|J_\sigma\eta|^2)=\mathbb{E}(\langle \eta J_\sigma^2\eta\rangle)=\frac{|\eta|^2}{d}\text{Tr}(J_\sigma^2)$$with $$\text{Tr}(J_\sigma^2 )=\sum_i \frac{e^{2x_i}}{(\sum_k e^{x_k})^2}+\sum_{i,j} \frac{e^{2x_i}e^{2x_j}}{(\sum_k e^{x_k})^4} -2\sum_{i}\frac{e^{3x_i}}{(\sum_k e^{x_k})^3} \\ = \sum_i (\sigma(x)_i)^2+\big(\sum_i (\sigma(x)_i)^2\big)^2-2\sum_i (\sigma(x)_i)^3$$

Conclusion : $$\mathbb{E}(|\sigma(x+\eta)-\sigma(x)|)\leq \frac{\eta}{\sqrt{d}}\sqrt{\sum_i (\sigma(x)_i)^2+\big(\sum_i (\sigma(x)_i)^2\big)^2-2\sum_i (\sigma(x)_i)^3 }+O(|\eta|^2)$$