Math and computer science are full of inequalities, but there is one that shows up more often in my work than any other. Of course, I’m talking about
This is The Inequality. I’ve been told on many occasions that the entire field of machine learning reduces to The Inequality combined with the Chernoff bound (which is proved using The Inequality).
Why does it show up so often in machine learning? Mostly because in analyzing an algorithm you want to bound the probability that some bad event happens. Bad events are usually phrased similarly to
And applying The Inequality we can bound this from above by
The point is that usually is the size of your dataset, which you get to choose, and by picking larger you make the probability of the bad event vanish exponentially quickly in . (Here is unrelated to how I am about to use as weights).
Of course, The Inequality has much deeper implications than bounds for the efficiency and correctness of machine learning algorithms. To convince you of the depth of this simple statement, let’s see its use in an elegant proof of the arithmetic geometric inequality.
Theorem: (The arithmetic-mean geometric-mean inequality, general version): For all non-negative real numbers and all positive such that , the following inequality holds:
Note that when all the this is the standard AM-GM inequality.
Proof. This proof is due to George Polya (in Hungarian, Pólya György).
We start by modifying The Inequality by a shift of variables , so that the inequality now reads . We can apply this to each giving , and in fact,
Now we have something quite curious: if we call the sum , the above shows that . Moreover, again because that shows that the right hand side of the inequality we’re trying to prove is also bounded by . So we know that both sides of our desired inequality (and in particular, the max) is bounded from above by . This seems like a conundrum until we introduce the following beautiful idea: normalize by the thing you think should be the larger of the two sides of the inequality.
Define new variables and notice that just by unraveling the definition. Call this sum . Now we know that
Now we unpack the pieces, and multiply through by , the result is exactly the AM-GM inequality.
Even deeper, there is only one case when The Inequality is tight, i.e. when , and that is . This allows us to use the proof above to come to a full characterization of the case of equality in the proof above. Indeed, the crucial step was that , which is only true when , i.e. when . Spending a few seconds thinking about this gives the characterization of equality if and only if .
So this is excellent: the arithmetic-geometric inequality is a deep theorem with applications all over mathematics and statistics. Adding another layer of indirection for impressiveness, one can use the AM-GM inequality to prove the Cauchy-Schwarz inequality rather directly. Sadly, the Wikipedia page for the Cauchy-Schwarz inequality hardly does it justice as far as the massive number of applications. For example, many novel techniques in geometry and number theory are proved directly from C-S. More, in fact, than I can hope to learn.
Of course, no article about The Inequality could be complete without a proof of The Inequality.
Theorem: For all , .
Proof. The proof starts by proving a simpler theorem, named after Bernoulli, that for every and every . This is relatively straightforward by induction. The base case is trivial, and
And because , we get Bernoulli’s inequality.
Now for any we can set , and get for every . Note that Bernoulli’s inequality is preserved for larger and larger because . So taking limits of both sides as we get the definition of on the right hand side of the inequality. We can prove a symmetrical inequality for when , and this proves the theorem.
What other insights can we glean about The Inequality? For one, it’s a truncated version of the Taylor series approximation
Indeed, the Taylor remainder theorem tells us that the first two terms approximate around zero with error depending on some constant times . In other words, is a lower bound on around zero. It is perhaps miraculous that this extends to a lower bound everywhere, until you realize that exponentials grow extremely quickly and lines do not.
One might wonder whether we can improve our approximation with higher order approximations. Indeed we can, but we have to be a bit careful. In particular, is only true for nonnegative (because the remainder theorem now applies to , but if we restrict to odd terms we win: is true for all .
What is really surprising about The Inequality is that, at least in the applications I work with, we rarely see higher order approximations used. For most applications, The difference between an error term which is quadratic and one which is cubic or quartic is often not worth the extra work in analyzing the result. You get the same theorem: that something vanishes exponentially quickly.