Shock and awe

I'm not really sure about awe, but I sensed a bit of shock in Monday's class. I guess the fact that this was the first class in three weeks, plus the late time, plus my jetlag, plus the fact that the proof I showed was quite complicated all took their toll.

Not being able to follow everything in class is actually not such a bad thing - it is often unavoidable when learning serious math. But to really gain something from a class were you didn't follow everything, or just barely did so, it is essential to go over the material again and make sure that you eventually understand it. There will be no written assignment this week - your assignment is to go over Monday's class and to really understand all the details and ideas. If you have questions, feel free to ask me.

To help you out a bit, let me try to have another short attempt at explaining the crux of the proof, which is the lemma saying that if $g=c+\sum a_ix_i$ and $\alpha=\sum a_i^2$ is 'small enough', then $||g-\sign(g)||_2^2\geq \alpha(1+o_\alpha(1))$. First, if $c$ is close to zero this is easy - but you should verify that you know why. If $c$ is closer to, say, $1$ than it is to zero, the point is that $g$ will almost always be positive (but it can also be negative sometimes, even if $\sum a_i^2$ is small - can you see why?). That's why the variance of $g$ will be very close to the variance of $|g|$, which is good because
(a) we know the variance of $g$ - it equals $\alpha$, and
(b) The term $||g-\sign(g)||_2^2$ can be bounded from below by the variance of $|g|$.

All that is left is therefore to bound the difference between the variance of $g$ and that of $|g|$, which we managed to show (modulo the claim that $c+\mathbb{E}[|g|]\leq 4$) is bounded by the expectation of the negative part of $g$. Again, this seems easy since we can use Chernoff to show that the probability that $g$ is negative is very small - the $x_i$'s with their smallish coefficients must win the battle against the big $c$ for this to happen. The problem is that we need a bound not on the probability that $g$ is negative but on the expectation of its negative part. We therefore use a formula that writes the expectation of a random variable in terms of the probabilities of it being large, namely $\mathbb{E}[X]=\int_{t=0}^\infty\Pr[X>t] dx$. That's how we use the Chernoff bound to estimate an expectation rather than a probability - this is actually a standard and important trick. Once we write down the integral, it's all over but the shouting.