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.
If you’re interested in learning more about the theory of inequalities, I wholeheartedly recommend The Cauchy-Schwarz Master Class. This book is wonderfully written, and chock full of fun exercises. I know because I do exercises from books like this one on planes and trains. It’s my kind of sudoku 🙂
> by picking larger m you make the probability of the bad event vanish exponentially quickly in m
Some assumptions on the $p_i$ are missing here. In particular, those you use below in a different context (that they sum up to 1) can not hold. You need that $\sum p_i \in \Omega(m)$ or your conclusion is false. So I guess you have i.i.d. random variables with constant probability of “bad things” to happen?
LikeLike
Dear Jeremy,
Thank you for this post! It was really astonishing to learn that this seemingly simple inequality has so many applications.
I think there is a typo in the proof of general version of AM-GM inequality: B should be $B = \sum_{i} p_i b_i$ instead of $B = \sum_{i} b_i$, right?
Best regards,
Tadashi
LikeLike
Yes, fixed!
LikeLike
OK, this is an example of what I hate about Mathematics.
What is “c”. 1+x v.s. c**x? If c is between 0 and 1 or either? 1+20 is not <= 1**20.
Just assume everyone has at least a Masters in math, or understands your abstruse nomenclature.
While I understand and can follow the implications, I get lost tracing back because nowhere do you even have a link referencing what "c" is.
LikeLike
It’s an “e”, as in the Euler constant, not a “c”. Did you just read it wrong or are you implying writing the Euler constant as “e” is abstruse or obscure notation? Because the number e is high school stuff(if you have calculus in high school anyway).
LikeLike
to prove that 1+x <= e^x, consider h(x) = 1+x – e^x, now h(0) = 0 but there are not more solutions of h(x)=0 since by Rolle's Theorem, si x1 is another solution then there is c in (0,c) such that h'(c) = 0, but h'(c) = 1-e^c=0 c=0 not in the open interval (0,c) or (c,0). Then h(x) != 0 for x != 0, so one of h(x)>=0 for all x or h(x) 0 so that h(x)>=0 for all x, and h(x)=0 only when x=0.
LikeLike
Agh, this would have been so useful for the homework I just had to hand in on the 23rd. I think this is the way to solve it.
LikeLike