0
$\begingroup$

Let $\varepsilon \in (0,1)$ and $\xi \in \mathbb{R}^n$ with $\xi \sim \mathcal{N}(0,I_n)$ be a random vector from a multivariate normal distribution with zero mean and identity covariance matrix. In a paper I'm reading on chance-constrained optimization, the authors claim that the feasible region of the probabilistic constraint $$\{x \in \mathbb{R}^n : \text{Prob}(\xi^{\text{T}} x \leq 1) \geq 1 - \varepsilon\}$$ is a Euclidean ball centered at the origin of radius

\begin{align} \label{eqn:radius} r &= (1 + o(1))\sqrt{2\log\left(\frac{1}{\varepsilon}\right)} \tag{1}. \end{align}

as $\varepsilon \to 0$. I would like to derive the above result.

We can rewrite the probabilistic constraint as $$\left\lbrace x \in \mathbb{R}^n : \text{Prob}\left(\xi^{\text{T}} \frac{x}{\left\lVert x\right\rVert} \leq \frac{1}{\left\lVert x\right\rVert}\right) \geq 1 - \varepsilon \right\rbrace$$ to see that the feasible region of this constraint will be a sphere of certain radius (this follows from the fact that we can pick any unit vector $\frac{x}{\left\lVert x\right\rVert}$ because of the spherical symmetry of the distribution of $\xi$), but I don't know how to proceed further to derive \eqref{eqn:radius}.

$\endgroup$
  • $\begingroup$ Is it really 2 log (1/$\epsilon$) or log (2 / $\epsilon$)? If it is the latter, then you can use gaussian tail bounds to show it. $\endgroup$ – E-A Mar 30 '18 at 23:15
  • $\begingroup$ The source says $2\log\left(\frac{1}{\varepsilon}\right)$, but I'm primarily interested in the approach to deriving such a bound. $\endgroup$ – madnessweasley Mar 30 '18 at 23:20
2
$\begingroup$

Since the distribution is spherically symmetrical, just look at one of the axes; in which case, you are essentially trying to find the $r$ that satisfies $P(|\xi r| > 1) < \epsilon$, which is equivalent to $P(|\xi| > \frac{1}{r}) < \epsilon$.

Now, a popular bound in probability called Chernoff bound for gaussian variables (with variance 1) tells you that $P(|\xi| > t) < 2e^{-\frac{t^2}{2}}$. As such, if $2e^{-\frac{1}{2r^2}} < \epsilon$, you are in the feasible region.

Solving it by algebra, you get $r < \sqrt{\frac{2}{\log{\frac{2}{\epsilon}}}}$ (You should check to verify), and this has I think the "right" scaling with epsilon; in the bound you gave in the question, picking epsilon close to 1 seems to shrink your feasible region, whereas it should be expanding (since if epsilon could be 1, any x would be feasible).

I could be wrong though, but since you asked how such bounds are derived, this is one way to approach this problem.

$\endgroup$
  • $\begingroup$ Thanks - I think you are correct that the scaling of the result stated in the question seems to be off. I checked again with the original source, and that is what they have - maybe they forgot an inverse along the way. I think I've managed to derive a closed-form solution to the problem based on your hint - I've posted my solution for reference. $\endgroup$ – madnessweasley Mar 31 '18 at 1:49
  • $\begingroup$ I've also noted in the question that the authors propose the bound for $r$ for the case when $\varepsilon \to 0$. $\endgroup$ – madnessweasley Mar 31 '18 at 1:55
  • $\begingroup$ Yeah, your answer looks right. Generally, people would do it using the Chernoff bound I think, since it is more "closed form" than using the error function, and tells you the behavior more clearly in my opinion, but that is just a preference issue. $\endgroup$ – E-A Mar 31 '18 at 14:56
0
$\begingroup$

Based on user E-A's hint, I've derived a related description of the feasible region.

Consider the following equivalent form of the chance constraint: $$\left\lbrace x \in \mathbb{R}^n : \text{Prob}\left(\xi^{\text{T}} \frac{x}{\left\lVert x\right\rVert} \leq \frac{1}{\left\lVert x\right\rVert}\right) \geq 1 - \varepsilon \right\rbrace.$$ Since the distribution of $\xi$ is spherically symmetric, we can choose $\frac{x}{\left\lVert x \right\rVert}$ to be the unit vector along the first coordinate direction, which then yields the following condition for the (maximal) radius $r$: $$\text{Prob}\left(\xi_1 \leq \frac{1}{r}\right) = 1 - \varepsilon \implies \text{Prob}\left(\xi_1 \geq \frac{1}{r}\right) = \varepsilon.$$ Since $\xi_1 \sim \mathcal{N}(0,1)$, we can simplify this to $$1 - \Phi\left( \frac{1}{r} \right) = \frac{1}{2}\left[1 - \text{erf}\left(\frac{1}{\sqrt{2}r}\right) \right] = \varepsilon \implies r = \frac{1}{\sqrt{2}\text{erf}^{-1}(1-2\varepsilon)}.$$ For $\varepsilon \ll 1$, we can use the approximation $\text{erf}^{-1}(1-2\varepsilon) \sim \sqrt{-\log\left[1-(1-2\varepsilon)^2\right]} = \sqrt{-\log\left[4\varepsilon - 4\varepsilon^2\right]}$ to get $$r \sim \frac{1}{\sqrt{-2 \log\left[4\varepsilon - 4\varepsilon^2\right]}},$$ which also agrees with the scaling argument put forth by user E-A.

$\endgroup$

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.