Small crown probabilities (and infinite dimensional margin assumption) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T17:05:14Z http://mathoverflow.net/feeds/question/29961 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29961/small-crown-probabilities-and-infinite-dimensional-margin-assumption Small crown probabilities (and infinite dimensional margin assumption) robin girard 2010-06-29T19:45:08Z 2011-06-30T23:08:06Z <p><strong>My question is:</strong> How do I find <strong>sharp</strong> upper bounds on $P(|q|\leq \epsilon)$ uniformly over a set of gaussian polynomes $q$ of degree two.</p> <p><strong>Notations and definitions</strong> (to make the question rigorous)</p> <ul> <li><p>Let me define $\mathcal{X}_{2}^*$ as the set of real random variables $q$ that can be written $$q=c+\sum_{i\geq 1}\beta_i (\xi_i^2-1)+\alpha_i\xi_i$$ with $c\in \mathbb{R}$, $\beta=(\beta_i)_i\in l_2(\mathbb{N})$, $\alpha=(\alpha_i)_i\in l^2(\mathbb{N})$ and $(\xi_i)_{i\in \mathbb{N}}$ a sequence of iid gaussian random variables with mean $0$ and variance $1$. This set is also known as gaussian polynomial of degree two (see for example the book of Bogachev 1998).</p></li> <li><p>Let $q\in \mathcal{X}_2^*$ given by $q=c+\sum_{i\geq 0}\alpha_i\xi_i+\sum_{i}\beta_i(\xi_i^2-1)$, I use the notation $$n_2(q)=\max_i |\beta_i|, \;\; \sigma(q)=\left (\sum_{i\geq 0}2\beta_i^2+\alpha_i^2\right )^{1/2}$$.</p></li> <li><p>I propose to use the following <strong>sets of polynomes</strong>: $$\Gamma_{2}(c)= ( q\in \mathcal{X}_{2}^*\;:\sigma(q)\geq c),\; \Gamma_{\infty}(c)=(q\in \mathcal{X}_{2}^*\;:n_2(q)\geq c)$$ and $$\Gamma_{1}(c)=(q\in \mathcal{X}_{2}^*\;:|\mathbb{E}(q)|\geq c).$$</p></li> </ul> <hr> <p><strong>Motivation for this problem</strong> </p> <p>It is worth noticing that this problem appears when one wants to check the so called <strong>Noise condition</strong> in an infinite dimensional gaussian classification problem.... Anyway, I called it small crown, even if it is not always a crown ... should be easy for expert of "small ball probabilities" ? </p> <hr> <p><strong>What I have so far</strong></p> <ol> <li>There exists $C(c_0)>0$ such that $\forall \epsilon>0\; \sup_{q\in \Gamma_1(c_0)} P(|q|\leq \epsilon)\leq C(c_0)\epsilon^{2/7}$</li> <li>There exists $C'(c_0)>0$ such that $\forall \epsilon>0$ $\sup_{q\in \Gamma_2(c_0)} P(|q|\leq \epsilon)\leq C'(c_0)\epsilon^{1/3}$.</li> <li>Let $q\in \mathcal{X}_{2}^*$, for all $\epsilon> 0$, $P(|q|\leq \epsilon) \leq \sqrt{\frac{1}{\pi}\frac{\epsilon}{n_2(q)}}$.</li> </ol> <p><strong>Comments</strong> Point 3 is easy but point 1 and 2 are less easy. I can provide a link to the proof if desired. If $n_2(q)=\max_{i}|\beta_i|>c_0$, bound of point $3$ is optimal in the sense that if $\beta=(1,0,\dots)$, $c=1$ and $\alpha=0$ we get $P(|q|\leq \epsilon)=P(|\xi^2|\leq \epsilon)\sim C\epsilon^{1/2}$ (for a constant $C$ that can be calculated explicitly). I have problem for case 1 and 2 .... </p> <p><strong>My analysis and conjecture:</strong> When $\|\beta\|2 \rightarrow 0$ ($l^2$ norm) the behaviour of $P(|q|\leq \epsilon)$ tends to be the same behaviour that $P(|\|\alpha\|_{l^2} \mathcal{N}(0,1)-c|\leq \epsilon)\sim C'(c_0)\epsilon$. Also, it is possible to conjecture that point $1$ and $2$ of the Theorem can be improved (in order to obtain exponent $1/2$ instead of $2/7$ and $1/3$). The difficult cases to study are those with $\|\beta\|_{\infty}\rightarrow 0$ but $\|\beta\|2$ doesn't tends to zero (there, in the proof of points 1 and 2 I use a gaussian approximation of q). Notice that when you restrict yourself to $\beta=0$ the answer to point 2 is that the best exponent is 1! hence a gap between linear and quadratic form...</p> <p>Some of the ideas I have tryed (without success :( )</p> <ol> <li><p>Using an explicit formulae of the density (if the density of $q$ is uniformly in $L^p$ for a good $p$ then we are done.. ) using characteristic funtions.</p></li> <li><p>Using optimal Young inequality (we have an infinite number of convolutions to build q)</p></li> </ol> http://mathoverflow.net/questions/29961/small-crown-probabilities-and-infinite-dimensional-margin-assumption/69082#69082 Answer by Victor for Small crown probabilities (and infinite dimensional margin assumption) Victor 2011-06-29T01:58:13Z 2011-06-30T21:04:48Z <p>Here is a solution for problem 2, with power $1/2$, using your idea 1. First some computations. Let A, B real numbers, let z ~ N(0,1), and X=$B(z^2-1) + Az$. The Fourier transform of the distribution of X (i.e.: the characteristic function of X with some $\pi$) is</p> <p>$\; \; \; \;\; \; \; \;E(exp(-2\pi i\xi X) = \frac{e^{2\pi i \xi B - \frac{2\pi^2 A^2 \xi^2}{1+4\pi i B \xi}}}{\sqrt{1+4\pi i\xi B}}$ </p> <p>where the square root is the one with positive real part. Then</p> <p>$\; \; \; \;\; \; \; |E(exp(-2\pi i\xi X)|^2 = \frac{e^{- \frac{4\pi^2 A^2 \xi^2}{1+16\pi^2 B^2 \xi^2} }} {1+16\pi^2 \xi^2 B^2}$ </p> <p>We also have for any pair of real numbers $a, b\ge 0$</p> <p>$\; \; \; \;\; \; \; \ln(\frac{1+8b + 4a}{1+16b}) &lt; \ln(1+\frac{4a}{1+16b})\le \frac{4a}{1+16b}$</p> <p>In particular, </p> <p>$\; \; \; \;\; \; \; -\frac{4a}{1+16b} - \ln(1+16b)&lt;-\ln(1+4(2b + a))$</p> <p>thus, with $a=\pi^2\xi^2 A^2$ and $b=\pi^2\xi^2 B^2$</p> <p>$\; \; \; \;\; \; \; |E(exp(-2\pi i\xi X)|^2 \le \frac{1} {1+4\pi^2 \xi^2 (2B^2+A^2)}.$ </p> <p>It follows that the Fourier transform of a Gaussian polynomial of degree two $q$ satisfies, with notation as in your definition:</p> <p>$\; \; \; \;\; \; \; |E(exp(-2\pi i\xi q)|^2 \le \prod_{j}{\frac{1} {1+4\pi^2 \xi^2 (2\beta_j^2+\alpha_j^2)}}\le\frac{1}{1+4\pi^2\xi^2\sigma(q)^2}.$ </p> <p>Then, the density of $q$ is bounded in $L^2$ , uniformly in $\Gamma_2(c_0)$, and so there exists a constant $C'$ such that for all $\epsilon>0$</p> <p>$\; \; \; \;\; \; \;\sup_{q\in \Gamma_2(c_0)} P(|q|\leq \epsilon)\leq C'\epsilon^{1/2}.$</p> http://mathoverflow.net/questions/29961/small-crown-probabilities-and-infinite-dimensional-margin-assumption/69223#69223 Answer by Victor for Small crown probabilities (and infinite dimensional margin assumption) Victor 2011-06-30T23:01:43Z 2011-06-30T23:08:06Z <p>Here is a contribution to problem 1, with power arbitrary close to $1/2$. First, we may as well assume $c_0 = 1$, and $0&lt;\epsilon&lt;.5$, since the general case reduces to this case. Then, for a quadratic gaussian polynomial $q = 1 + q_0$ with $E(q_0)=0$, </p> <p>$\;\;\;\;\;\;P(|q| \le\epsilon) \le P( |q_0|\ge(1-\epsilon))\le \frac{E(|q_0|^p)}{(1-\epsilon)^p}\le$ $C_1(p)\sigma(q_0)^{p}\le C_2\epsilon^\lambda$</p> <p>provided $\;\;\sigma(q_0)^{p}\le\epsilon^\lambda$. But, from the solution to 2, </p> <p>$\;\;\;\;\;\;P(|q| \le\epsilon) \le C_3(\frac{\epsilon}{\sigma(q_0)})^{1/2}\le C_3 \epsilon^{\frac{1}{2}-\frac{\lambda}{p}}$</p> <p>provided $\;\;\sigma(q_0)^{p}>\epsilon^\lambda$. Taking $\lambda=\frac{1}{2+\frac{2}{p}}$ both cases are bound by the same power of $\epsilon$, and we get</p> <p>$\;\;\;\;\;\;P(|q| \le\epsilon) \le C_4 \epsilon^{\frac{1}{2+(2/p)}}$</p> <p>whether $\sigma(q_0)$ is large or small.</p>