{"id":932,"date":"2022-08-02T14:55:51","date_gmt":"2022-08-02T14:55:51","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=932"},"modified":"2024-12-02T17:43:43","modified_gmt":"2024-12-02T17:43:43","slug":"big-ideas-in-applied-math-concentration-inequalities","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2022\/08\/02\/big-ideas-in-applied-math-concentration-inequalities\/","title":{"rendered":"Big Ideas in Applied Math: Concentration Inequalities"},"content":{"rendered":"\n

<\/p>\n\n\n\n

This post is about randomized algorithms<\/a> for problems in computational science and a powerful set of tools, known as concentration inequalities<\/a>, which can be used to analyze why they work. I’ve discussed why randomization can help in solving computational problems in a previous post<\/a>; this post continues this discussion by presenting an example of a computational problem where, somewhat surprisingly, a randomized algorithm proves effective. We shall then use concentration inequalities to analyze why this method works.<\/p>\n\n\n\n

Triangle Counting<\/h2>\n\n\n\n

Let’s begin our discussion of concentration inequalities by means of an extended example. Consider the following question: How many triangles are there in the Facebook network? That is, how many trios of people are there who are all mutual friends? While seemingly silly at first sight, this is actually a natural and meaningful question about the structure of the Facebook social network and is related to similar questions such as “How likely are two friends of a person to also be friends with each other?” <\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

If there are \"n\" people on the Facebook graph, then the natural algorithm of iterating over all \"{n \choose 3} \approx n^3/6\" triplets and checking whether they form a triangle is far too computationally costly for the billions of Facebook accounts. Somehow, we want to do much faster than this, and to achieve this speed we would be willing to settle for an estimate<\/em> of the triangle count up to some error.<\/p>\n\n\n\n

There are many approaches to this problem, but let’s describe a particularly surprising algorithm. Let \"A\" be an \"n\times n\" matrix where the \"ij\"th entry of \"A\" is \"1\" if users \"i\" and \"j\" are friends and \"0\" otherwise1<\/a><\/sup>All of the diagonal entries of \"A\" are set to zero.<\/span>; this matrix is called the adjacency matrix<\/a><\/strong> of the Facebook graph. A fact from graph theory is that the \"ij\"th entry of the cube<\/em> \"A^3\" of the matrix \"A\" counts the number of paths from user \"i\" to user \"j\" of length three.2<\/a><\/sup>By a path of length three, we mean a sequence of users \"i,k,\ell,j\" where \"i\" and \"k\", \"k\" and \"\ell\", and \"\ell\" and \"j\" are all friends.<\/span> In particular, the \"ii\"th entry of \"A^3\" denotes the number of paths from \"i\" to itself of length \"3\", which is twice<\/em> the number of triangles incident on \"i\". (The paths \"i\to j \to k \to i\" and \"i\to k \to j\to i\" are both counted as paths of length 3 for a triangle consisting of \"i\", \"j\", and \"k\".) Therefore, the trace<\/a> of \"A^3\", equal to the sum of its diagonal entries, is six<\/em> times the number of triangles: The \"ii\"th entry of \"A^3\" is twice<\/em> the number of triangles incident on \"i\" and each triangle \"(i,j,k)\" is counted thrice<\/em> in the \"ii\"th, \"jj\"th, and \"kk\"th entries of \"A^3\". In summary, we have<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Therefore, the triangle counting problem is equivalent to computing the trace of \"A^3\". Unfortunately, the problem of computing \"A^3\" is, in general, very computationally costly. Therefore, we seek ways of estimating the trace of a matrix without forming it.<\/p>\n\n\n\n

Randomized Trace Estimation<\/a><\/h2>\n\n\n\n

Motivated by the triangle counting problem from the previous section, we consider the problem of estimating the trace of a matrix \"M\". We assume that we only have access to the matrix \"M\" through matrix\u2013vector products<\/a>; that is, we can efficiently compute \"Mx\" for a vector \"x\". For instance, in the previous example, the Facebook graph has many fewer friend relations (edges) \"m\" than the maximum possible amount of \"{n\choose 2} \approx n^2/2\". Therefore, the matrix \"A\" is sparse<\/a>; in particular, matrix\u2013vector multiplications with \"A\" can be computed in around \"m\" operations. To compute matrix\u2013vector products \"Mx\" with \"M = A^3\", we simply compute matrix\u2013vector products with \"A\" three times, \"x \mapsto Ax \mapsto A(Ax) \mapsto A(A(Ax)) = A^3x\".<\/p>\n\n\n\n

Here’s a very nifty idea to estimate the trace of \"M\" using only matrix\u2013vector products, originally due to Didier A. Girard<\/a> and Michael F. Hutchinson<\/a>. Choose \"x\" to be a random<\/em> vector whose entries are independent<\/a> \"\pm 1\"-values, where each value \"+1\" and \"-1\" occurs with equal \"1/2\" probability. Then if one forms the expression \"x^\top M x = \sum_{i,j=1}^n M_{ij} x_i x_j\". Since the entries of \"x_i\" and \"x_j\" are independent, the expectation<\/a> of \"x_ix_j\" is \"0\" for \"i\ne j\" and \"1\" for \"i = j\". Consequently, by linearity of expectation<\/a>, the expected value of \"x^\top M x\" is<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

The average value of \"x^\top M x\" is equal to the trace of \"M\"! In the language of statistics, we might say that \"x^\top M x\" is an unbiased estimator<\/strong><\/a> for \"\operatorname{tr}(M)\". Thus, the efficiently computable quantity \"x^\top M x\" can serve as a (crude) estimate for \"\operatorname{tr}(M)\".<\/p>\n\n\n\n

While the expectation of \"x^\top Mx\" equals \"\operatorname{tr}(M)\", any random realization of \"x^\top M x\" can deviate from \"\operatorname{tr}(M)\" by a non-neligible amount. Thus, to reduce the variability of the estimator \"x^\top M x\", it is appropriate to take an average of multiple copies of this random estimate. Specifically, we draw \"k\" random vectors with independent random \"\pm 1\" entries \"x_1,\ldots,x_k\" and compute the averaged trace estimator<\/p>\n\n\n

(1) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

The \"k\"-sample trace estimator \"T_k\" remains an unbiased estimator for \"\operatorname{tr}(M)\", \"\mathbb{E}\, T_k = \operatorname{tr}(M)\", but with reduced variability. Quantitatively, the variance<\/a> of \"T_k\" is \"k\" times smaller than the single-sample estimator \"x^\top M x\":<\/p>\n\n\n

(2) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

The Girard\u2013Hutchinson trace estimator gives a natural way of estimating the trace of the matrix \"M\", a task which might otherwise be hard without randomness.3<\/a><\/sup>To illustrate what randomness is buying us here, it might be instructive to think about how one might try to estimate the trace of \"M\" via matrix\u2013vector products without the help of randomness.<\/span> For the trace estimator to be a useful tool, an important question remains: How many samples \"k\" are needed to compute \"\operatorname{tr}(M)\" to a given accuracy? Concentration inequalities answer questions of this nature.<\/p>\n\n\n\n

Concentration Inequalities<\/h2>\n\n\n\n

A concentration inequality<\/strong> provides a bound on the probability a random quantity is significantly larger or smaller than its typical value. Concentration inequalities are useful because they allow us to prove statements like “With at least 99% probability, the randomized trace estimator with 100 samples produces an approximation of the trace which is accurate up to error no larger than \"0.001\".” In other words, concentration inequalities can provide quantitative estimates of the likely size of the error when a randomized algorithm is executed.<\/p>\n\n\n\n

In this section, we shall introduce a handful of useful concentration inequalities, which we will apply to the randomized trace estimator in the next section. We’ll then discuss how these and other concentration inequalities can be derived<\/em> in the following section. <\/p>\n\n\n\n

Markov’s Inequality<\/h3>\n\n\n\n

Markov’s inequality is the most fundamental concentration inequality. When used directly, it is a blunt instrument, requiring little insight to use and producing a crude but sometimes useful estimate. However, as we shall see later, all of the sophisticated concentration inequalities that will follow in this post can be derived from a careful use of Markov’s inequality.<\/p>\n\n\n\n

The wide utility of Markov’s inequality is a consequence of the minimal assumptions needed for its use. Let \"X\" be any<\/em> nonnegative random variable. Markov’s inequality states that the probability that \"X\" exceeds a level \"t > 0\" is bounded by the expected value of \"X\" over \"t\". In equations, we have<\/p>\n\n\n

(3) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

We stress the fact that we make no assumptions on how the random quantity \"X\" is generated other than that \"X\" is nonnegative.<\/p>\n\n\n\n

As a short example of Markov’s inequality, suppose we have a randomized algorithm which takes one second on average to run. Markov’s inequality then shows that the probability the algorithm takes more than 100 seconds to run is at most \"1/100 = 1\%\". This small example shows both the power and the limitation of Markov’s inequality. On the negative side, our analysis suggests that we might have to wait as much as 100 times the average runtime for the algorithm to complete running with 99% probability; this large huge multiple of 100 seems quite pessimistic. On the other hand, we needed no information whatsoever about how the algorithm works to do this analysis. In general, Markov’s inequality cannot be improved without more assumptions on the random variable \"X\".4<\/a><\/sup>For instance, imagine an algorithm which 99% of the time completes instantly and 1% of the time takes 100 seconds. This algorithm does have an average runtime of 1 second, but the conclusion of Markov’s inequality that the runtime of the algorithm can be as much as 100 times the average runtime with 1% probability is true.<\/span>\n\n\n\n

Chebyshev’s Inequality and Averages<\/h3>\n\n\n\n

The variance<\/a> of a random variable describes the expected size of a random variable’s deviation from its expected value. As such, we would expect that the variance should provide a bound on the probability a random variable is far from its expectation. This intuition indeed is correct and is manifested by Chebyshev’s inequality<\/a>. Let \"X\" be a random variable (with finite expected value) and \"t > 0\". Chebyshev’s inequality states that the probability that \"X\" deviates from its expected value by more than \"t\" is at most \"\operatorname{Var}(X)/t^2\":<\/p>\n\n\n

(4) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Chebyshev’s inequality is frequently applied to sums or averages of independent random quantities. Suppose \"X_1,\ldots,X_n\" are independent and identically distributed<\/a> random variables with mean \"\mu\" and variance \"\sigma^2\" and let \"\overline{X}\" denote the average<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Since the random variables \"X_1,\ldots,X_n\" are independent,5<\/a><\/sup>In fact, this calculation works if \"X_1,\ldots,X_n\" are only pairwise independent<\/a> or even pairwise uncorrelated<\/a>. For algorithmic applications, this means that \"X_1,\ldots,X_n\" don’t have to be fully independent of each other; we just need any pair of them to be uncorrelated. This allows many randomized algorithms to be “derandomized<\/a>“, reducing the amount of “true” randomness needed to execute an algorithm.<\/span> the properties of variance<\/a> entail that<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

where we use the fact that \"\operatorname{Var}(X_1) = \cdots = \operatorname{Var}(X_n) = \sigma^2\". Therefore, by Chebyshev’s inequality,<\/p>\n\n\n

(5) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Suppose we want to estimate the mean \"\mu\" by \"\overline{X}\" up to error \"\epsilon\" and are willing to tolerate a failure probability of \"\delta\". Then setting the right-hand side of (5) to \"\delta\", Chebyshev’s inequality suggests that we need at most<\/p>\n\n\n

(6) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

samples to achieve this goal.<\/p>\n\n\n\n

Exponential Concentration: Hoeffding and Bernstein<\/h3>\n\n\n\n

How happy should we be with the result (6) of applying Chebyshev’s inequality the average \"\overline{X}\"? The central limit theorem<\/a> suggests that \"\overline{X}\" should be approximately normally distributed with mean \"\mu\" and variance \"\sigma^2/n\". Normal random variables have an exponentially<\/em> small probability of being more than a few standard deviations above their mean, so it is natural to expect this should be true of \"\overline{X}\" as well. Specifically, we expect a bound roughly like<\/p>\n\n\n

(7) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Unfortunately, we don’t have a general result quite this nice without additional assumptions, but there are a diverse array of exponential concentration inequalities available which are quite useful in analyzing sums (or averages) of independent random variables that appear in applications.<\/p>\n\n\n\n

Hoeffding’s inequality<\/a> is one such bound. Let \"X_1,\ldots,X_n\" be independent (but not necessarily identically distributed) random variables and consider the average \"\overline{X} = (X_1 + \cdots + X_n)/n\". Hoeffding’s inequality makes the assumption that the summands are bounded<\/em>, say within an interval \"[a,b]\".6<\/a><\/sup>There are also more general versions of Hoeffding’s inequality where the bound on each random variable is different.<\/span> Hoeffding’s inequality then states that<\/p>\n\n\n

(8) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Hoeffding’s inequality is quite similar to the ideal concentration result (7) except with the variance \"\sigma^2 = n\operatorname{Var}(\overline{X})\" replaced by the potentially much larger quantity7<\/a><\/sup>Note that \"\sigma^2\" is always smaller than or equal to \"(b-a)^2/4\".<\/span> \"(b-a)^2/4\".<\/p>\n\n\n\n

Bernstein’s inequality<\/a> fixes this deficit in Hoeffding’s inequality at a small cost. Now, instead of assuming \"X_1,\ldots,X_n\" are bounded within the interval \"[a,b]\", we make the alternate boundedness assumption \"|X_i - \mathbb{E}\, X_i| \le B\" for every \"1\le i\le n\". We continue to denote \"\sigma^2 = n\operatorname{Var}(\overline{X})\" so that if \"X_1,\ldots,X_n\" are identically distributed, \"\sigma^2\" denotes the variance of each of \"X_1,\ldots,X_n\". Bernstein’s inequality states that<\/p>\n\n\n

(9) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

For small values of \"t\", Bernstein’s inequality yields exactly the kind of concentration that we would hope for from our central limit theorem heuristic (7). However, for large values of \"t\", we have<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

which is exponentially small in \"t\" rather than \"t^2\". We conclude that Bernstein’s inequality provides sharper bounds then Hoeffding’s inequality for smaller values of \"t\" but weaker bounds for larger values of \"t\".<\/p>\n\n\n\n

Chebyshev vs. Hoeffding vs. Bernstein<\/h3>\n\n\n\n

Let’s return to the situation where we seek to estimate the mean \"\mu\" of independent and identically distributed random variables \"X_1,\ldots,X_n\" each with variance \"\sigma^2\" by using the averaged value \"\overline{X} = (X_1 + \cdots + X_n)/n\". Our goal is to bound how many samples \"n\" we need to estimate \"\mu\" up to error \"\epsilon\", \"| \overline{X} - \mu | \le \epsilon\", except with failure probability at most \"\delta\". Using Chebyshev’s inequality, we showed that (see (7))<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Now, let’s try using Hoeffding’s inequality. Suppose that \"X_1,\ldots,X_n\" are bounded in the interval \"[a,b]\". Then Hoeffding’s inequality (8) shows that<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Bernstein’s inequality states that if \"X_1,\ldots,X_n\" lie in the interval \"[\mu-B,\mu+B]\" for every \"1\le i \le n\", then<\/p>\n\n\n

(10) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Hoeffding’s and Bernstein’s inequality show that we need \"n\" roughly proportional to \"\tfrac{\log(1/\delta)}{\epsilon^2}\" samples are needed rather than proportional to \"\tfrac{1/\delta}{\epsilon^2}\". The fact that we need proportional to \"1/\epsilon^2\" samples to achieve error \"\epsilon\" is a consequence of the central limit theorem and is something we would not be able to improve with any concentration inequality. What exponential concentration inequalities allow us to do is to improve the dependence on the failure probability from proportional to \"1/\delta\" to \"\log(1/\delta)\", which is a huge<\/em> improvement.<\/p>\n\n\n\n

Hoeffding’s and Bernstein’s inequalities both have a small drawback. For Hoeffding’s inequality, the constant of proportionality is \"(b-a)^2/4\" rather than the true variance \"\sigma^2\" of the summands. Bernstein’s inequality gives us the “correct” constant of proportionality \"\sigma^2\" but adds a second term proportional to \"\tfrac{\log(1/\delta)}{\epsilon}\"; for small values of \"\epsilon\", this term is dominated by the term proportional to \"\tfrac{\log(1/\delta)}{\epsilon^2}\" but the second term can be relevant for larger values of \"\epsilon\".<\/p>\n\n\n\n

There are a panoply of additional concentration inequalities than the few we’ve mentioned. We give a selected overview in the following optional section.<\/p>\n\n\n

<\/span>Other Concentration Inequalities<\/div>
There are a handful more exponential concentration inequalities for sums of independent random variables such as Chernoff’s inequality<\/a> (very useful for somes of bounded, positive random variables) and Bennett’s inequality<\/a>. There are also generalizations of Hoeffding’s<\/a>, Chernoff’s, and Bernstein’s inequalities for unbounded random variables with subgaussian<\/a> and subexponential<\/a> tail decay; these results are documented in Chapter 2 of Roman Vershynin’s<\/a> excellent book High-Dimensional Probability<\/em><\/a>.<\/p>\n

One can also generalize concentration inequalities to so-called martingale<\/a> sequences, which can be very useful for analyzing adaptive algorithms. These inequalities can often have the advantage of bounding the probability that a martingale sequence ever<\/em> deviates by some amount from its applications; these results are called maximal inequalities. Maximal analogs of Markov’s and Chebyshev’s inequalities are given by Ville’s inequality<\/a> and Doob’s inequality<\/a>. Exponential concentration inequalities include the Hoeffding\u2013Azuma inequality<\/a> and Freedman’s inequality<\/a>.<\/p>\n

Finally, we note that there are many<\/em> concentration inequalities for functions of independent random variables other than sums, usually under the assumption that the function is Lipschitz continuous<\/a>. There are exponential concentration inequalities for functions with “bounded differences”<\/a>, functions of Gaussian random variables, and convex functions of bounded random variables. References for these results include Chapters 3 and 4 of the lecture notes Probability in High Dimension<\/em><\/a> by Ramon van Handel<\/a> and the comprehensive monograph Concentration Inequalities<\/em><\/a> by St\u00e9phane Boucheron<\/a>, G\u00e1bor Lugosi<\/a>, and Pascal Massart<\/a>.<\/div><\/div>\n\n\n

Analysis of Randomized Trace Estimation<\/h2>\n\n\n\n

Let us apply some of the concentration inequalities we introduced in last section to analyze the randomized trace estimator. Our goal is not to provide the best possible analysis of the trace estimator,8<\/a><\/sup>More precise estimation for trace estimation applied to positive semidefinite matrices was developed by Gratton and Titley-Peloquin<\/a>; see Theorem 4.5 of the following survey<\/a>.<\/span> but to demonstrate how the general concentration inequalities we’ve developed can be useful “out of the box” in analyzing algorithms.<\/p>\n\n\n\n

In order to apply Chebyshev’s and Berstein’s inequalities, we shall need to compute or bound the variance of the single-sample trace estimtor \"x^\top Mx\", where \"x\" is a random vector of independent \"\pm 1\"-values. This is a straightforward task using properties of the variance<\/a>:<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Here, \"\operatorname{Cov}\" is the covariance<\/a> and \"\|\cdot\|_{\rm F}\" is the matrix Frobenius norm<\/a>. Chebyshev’s inequality (5), then gives<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Let’s now try applying an exponential concentration inequality. We shall use Bernstein’s inequality, for which we need to bound \"|x^\top M x - \operatorname{tr}(M)|\". By the Courant\u2013Fischer minimax principle<\/a>, we know that \"x^\top M x\" is between \"\lambda_{\rm min}(M) \cdot \|x\|^2\" and \"\lambda_{\rm max} (M)\cdot\|x\|^2\" where \"\lambda_{\rm min}(M)\" and \"\lambda_{\rm max}(M)\" are the smallest and largest eigenvalues<\/a> of \"M\" and \"\|x\|\" is the Euclidean norm<\/a> of the vector \"x\". Since all the entries of \"x\" have absolute value \"1\", we have \"\|x\| = \sqrt{n}\" so \"x^\top M x\" is between \"n\lambda_{\rm min}(M)\" and \"n\lambda_{\rm max}(M)\". Since the trace equals the sum of the eigenvalues<\/a> of \"M\", \"\operatorname{tr}(M)\" is also between \"n\lambda_{\rm min}(M)\" and \"n\lambda_{\rm max}(M)\". Therefore,<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

where \"\|\cdot\|\" denotes the matrix spectral norm<\/a>. Therefore, by Bernstein’s inequality (9), we have<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

In particular, (10) shows that<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

samples suffice to estimate \"\operatorname{tr}(M)\" to error \"\epsilon\" with failure probability at most \"\delta\". Concentration inequalities easily furnish estimates for the number of samples needed for the randomized trace estimator.<\/p>\n\n\n\n

We have now accomplished our main goal of using concentration inequalities to analyze the randomized trace estimator, which in turn can be used to solve the triangle counting problem. We leave some additional comments on trace estimation and triangle counting in the following bonus section.<\/p>\n\n\n

<\/span>More on Trace Estimation and Triangle Counting<\/div>
To really complete the analysis of the trace estimator in an application (e.g., triangle counting), we would need to obtain bounds on \"\|M\|_{\rm F}\" and \"\|M\|\". Since we often don’t know good bounds for \"\|M\|_{\rm F}\" and \"\|M \|\", one should really use the trace estimator together with an a posteriori <\/em><\/a>error estimates for the trace estimator, which provide a confidence interval<\/a> for the trace rather than a point estimate<\/a>; see sections 4.5 and 4.6 in this survey<\/a> for details.<\/p>\n

One can improve on the Girard\u2013Hutchinson trace estimator by using a variance reduction technique. One such variance reduction technique was recently proposed under the name Hutch++<\/a>, extending ideas by Arjun Singh Gambhir, Andreas Stathopoulos, and Kostas Orginos<\/a> and Lin Lin<\/a>. In effect, these techniques improve the number of samples \"k\" needed to estimate the trace of a positive semidefinite<\/em><\/a> matrix \"A\" to relative error<\/a> \"\epsilon\" to proportional to \"1/\epsilon\" down from \"1/\epsilon^2\".<\/p>\n

Several algorithms have been proposed for triangle counting, many of them randomized. This survey<\/a> gives a comparison of different methods for the triangle counting problem, and also describes more motivation and applications for the problem.<\/div><\/div>\n\n\n

Deriving Concentration Inequalities<\/h2>\n\n\n\n

Having introduced concentration inequalities and applied them to the randomized trace estimator, we now turn to the question of how to derive<\/em> concentration inequalities. Learning how to derive concentration inequalities is more than a matter of mathematical completeness since one can often obtain better results by “hand-crafting” a concentration inequality for a particular application rather than applying a known concentration inequality. (Though standard concentration inequalities like Hoeffding’s and Bernstein’s often give perfectly adequate answers with much less work.)<\/p>\n\n\n\n

Markov’s Inequality<\/h3>\n\n\n\n

At the most fundamental level, concentration inequalities require us to bound a probability<\/em> by an expectation<\/em>. In achieving this goal, we shall make a simple observation: The probability that \"X\" is larger than or equal to \"t\" is the expectation of a random variable \"\mathbf{1}_{[t,\infty)}(X)\".9<\/a><\/sup>More generally, the probability of an event can be written as an expectation of the indicator<\/a> random variable of that event.<\/span> Here, \"\mathbf{1}_{[t,\infty)}(\cdot)\" is an indicator<\/a> function which outputs one if its input is larger than or equal to \"t\" and zero otherwise.<\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

As promised, the probability \"X\" is larger than \"t\" is the expectation of \"\mathbf{1}_{[t,\infty)}(X)\":<\/p>\n\n\n

(11) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

We can now obtain bounds on the probability that \"X\ge t\" by bounding its corresponding indicator function. In particular, we have the inequality <\/p>\n\n\n

(12) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n

\n
\"\"<\/figure><\/div>\n\n\n

Since \"X\" is nonnegative, combining equations (11) and (12) gives Markov’s inequality:<\/p>\n\n\n

  <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

Chebyshev’s Inequality<\/h3>\n\n\n\n

Before we get to Chebyshev’s inequality proper, let’s think about how we can push Markov’s inequality further. Suppose we find a bound on the indicator function \"\mathbf{1}_{[t,\infty)}(\cdot)\" of the form<\/p>\n\n\n

(13) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

A bound of this form immediately to bounds on \"\mathbb{P} \{X \ge t\}\" by (11). To obtain sharp and useful bounds on \"\mathbb{P}\{X\ge t\}\" we seek bounding functions \"f(\cdot)\" in (13) with three properties:<\/p>\n\n\n\n

    \n
  1. For \"x\in[0, t)\", \"f(x)\" should be close to zero,<\/li>\n\n\n\n
  2. For \"x\in [t,\infty)\", \"f(x)\" should be close to one, and<\/li>\n\n\n\n
  3. We need \"\mathbb{E} \, f(X)\" to be easily computable or boundable.<\/li>\n<\/ol>\n\n\n\n

    These three objectives are in tension with each other. To meet criterion 3, we must restrict our attention to pedestrian functions \"f(\cdot)\" such as powers \"f(x) = (x/t)^\theta\" or exponentials \"f(x) = \exp(\theta (x-t))\" for which we have hopes of computing or bounding \"\mathbb{E} \, f(X)\" for random variables \"X\" we encounter in practical applications. But these candidate functions \"f(\cdot)\" have the undesirable property that making the function smaller on \"[0, t)\" (by increasing \"\theta\") to meet point 1 makes the function larger on \"(t,\infty)\", detracting from our ability to achieve point 2. We shall eventually come up with a best-possible resolution to this dilemma by formulating this as an optimization problem to determine the best choice of the parameter \"\theta > 0\" to obtain the best possible candidate function of the given form.<\/p>\n\n\n\n

    Before we get ahead of ourselves, let us use a specific choice for \"f(\cdot)\" different than we used to prove Markov’s inequality. We readily verify that \"f(x) = (x/t)^2\" satisfies the bound (13), and thus by (12),<\/p>\n\n\n

    (14) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n

    \n
    \"\"<\/figure><\/div>\n\n\n

    This inequality holds for any nonnegative random variable \"X\". In particular, now consider a random variable \"X\" which we do not assume to be nonnegative. Then \"X\"‘s deviation from its expectation, \"|X-\mathbb{E} X|\", is a nonnegative random variable. Thus applying (14) gives<\/p>\n\n\n

      <\/span>   <\/span>\"\begin{equation*}\mathbb{P} \{ |X - \mathbb{E} X| \ge t \} \le \frac{\mathbb{E} | X - \mathbb{E} X|^2}{t^2} = \frac{\operatorname{Var}(X)}{t^2}.<\/p><\/p>\n\n\n

    We have derived Chebyshev’s inequality! Alternatively, one can derive Chebyshev’s inequality by noting that \"|X-\mathbb{E} X| \ge t\" if, and only if, \"|X-\mathbb{E} X|^2 \ge t^2\". Therefore, by Markov’s inequality,<\/p>\n\n\n

      <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    The Laplace Transform Method<\/h3>\n\n\n\n

    We shall now realize the plan outlined earlier where we shall choose an optimal bounding function \"f(\cdot)\" from the family of exponential functions \"f(x) = \exp(\theta(x-t))\", where \"\theta > 0\" is a parameter which we shall optimize over. This method shall allow us to derive exponential concentration inequalities like Hoeffding’s and Bernstein’s. Note that the exponential function \"f(x) = \exp(\theta(x-t))\" bounds the indicator function \"\mathbf{1}_{[t,\infty)}(\cdot)\" for all<\/em> real numbers \"x\", so we shall no longer require the random variable \"X\" to be nonnegative. Therefore, by (11), <\/p>\n\n\n

    (15) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    The functions<\/p>\n\n\n

      <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    are known as the moment generating function<\/a><\/strong> and cumulant generating function<\/a><\/strong> of the random variable \"X\".10<\/a><\/sup>These functions are so-named because they are the (exponential) generating functions<\/a> of the (polynomial) moments<\/a> \"\mathbb{E} X^k\", \"k=0,1,2,\ldots\", and the cumulants<\/a> of \"X\".<\/span> With these notations, (15) can be written<\/p>\n\n\n

    (16) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    The moment generating function coincides with the Laplace transform<\/a> \"\mathbb{E} \exp(-\theta X) = m_X(-\theta)\" up to the sign of the parameter \"\theta\", so one name for this approach to deriving concentration inequalities is the Laplace transform method. (This method is also known as the Cram\u00e9r\u2013Chernoff method<\/a>.)<\/p>\n\n\n\n

    The cumulant generating function has an important property for deriving concentration inequalities for sums or averages of independent random variables: If \"X_1,\ldots,X_n\" are independent random variables, than the cumulant generating function is additive<\/em>:11<\/a><\/sup>For proof, we compute \"m_{\sum_j X_j}(\theta) = \mathbb{E} \prod_j \exp(\theta X_j) = \prod_j \mathbb{E} \exp(\theta X_j)\". Taking logarithms proves the additivity.<\/span>\n\n\n

    (17) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    Proving Hoeffding’s Inequality<\/h3>\n\n\n\n

    For us to use the Laplace transform method, we need to either compute or bound the cumulant generating function. Since we are interested in general concentration inequalities which hold under minimal assumptions such as boundedness, we opt for the latter. Suppose \"a\le X \le b\" and consider the cumulant generating function of \"Y:=X-\mathbb{E}X\". Then one can show the cumulant generating function bound12<\/a><\/sup>The bound (18) is somewhat tricky to establish, but we can establish the same result with a larger constant than \"1/8\". We have \"|Y| \le b-a =: c\". Since the function \"\theta \mapsto \exp(\theta Y)\" is convex<\/a>, we have the bound \"\exp(\theta Y) \le \exp(-\theta c) + (Y+c)\tfrac{\mathrm{e}^{\theta c} -\mathrm{e}^{-\theta c}}{2c}\". Taking expectations, we have \"m_Y(\theta) \le \cosh(\theta c)\". One can show by comparing Taylor series that \"\cosh(\theta c) \le \exp(\theta^2 c^2/2)\". Therefore, we have \"\xi_Y(\theta) \le \theta^2c^2/2 = \theta^2(b-a)^2/2\".<\/span>\n\n\n

    (18) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    Using the additivity of the cumulant generating function (17), we obtain the bound<\/p>\n\n\n

      <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    Plugging this into the probability bound (16), we obtain the concentration bound<\/p>\n\n\n

    (19) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    We want to obtain the smallest possible upper bound on this probability, so it behooves us to pick the value of \"\theta > 0\" which makes the right-hand side of this inequality as small as possible. To do this, we differentiate the contents of the exponential and set to zero, obtaining<\/p>\n\n\n

      <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    Plugging this value for \"\theta\" into the bound (19) gives A bound for \"\overline{X}\" being larger<\/em> than \"\mathbb{E}\overline{X} + t\":<\/p>\n\n\n

    (20) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    To get the bound on \"\overline{X}\" being smaller<\/em> than \"\mathbb{E}\overline{X} - t\", we can apply a small trick. If we apply (20) to the summands \"-X_1,-X_2,\ldots,-X_n\" instead of \"X_1,\ldots,X_n\", we obtain the bounds<\/p>\n\n\n

    (21) <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    We can now combine the upper tail bound<\/em> (19) with the lower tail bound<\/em> (21) to obtain a “symmetric” bound on the probability that \"|\overline{X} - \mathbb{E}\overline{X}| \ge t\". The means of doing often this goes by the fancy name union bound<\/a><\/em>, but the idea is very simple:<\/p>\n\n\n

      <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    Thus, applying this union bound idea with the upper and lower tail bounds (20) and (21), we obtain Hoeffding’s inequality, exactly as it appeared above as (8):<\/p>\n\n\n

      <\/span>   <\/span>\"\begin{align*}<\/p><\/p>\n\n\n

    Voil\u00e0! Hoeffding’s inequality has been proven! Bernstein’s inequality is proven essentially the same way except that, instead of (17), we have the cumulant generating function bound<\/p>\n\n\n

      <\/span>   <\/span>\"\begin{equation*}<\/p><\/p>\n\n\n

    for a random variable \"Y\" with mean zero and satisfying the bound \"|Y| \le B\".<\/p>\n\n\n\n

    Upshot:<\/strong> Randomness can be a very effective tool for solving computational problems, even those which seemingly no connection to probability like triangle counting. Concentration inequalities are a powerful tool for assessing how many samples are needed for an algorithm based on random sampling to work. Some of the most useful concentration inequalities are exponential concentration inequalities like Hoeffding and Bernstein, which show that an average of bounded random quantities are close to their average except with exponentially small probability. <\/p>\n","protected":false},"excerpt":{"rendered":"

    This post is about randomized algorithms for problems in computational science and a powerful set of tools, known as concentration inequalities, which can be used to analyze why they work. I’ve discussed why randomization can help in solving computational problems in a previous post; this post continues this discussion by presenting an example of aRead more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,14],"tags":[],"class_list":["post-932","post","type-post","status-publish","format-standard","hentry","category-big-ideas-in-applied-math","category-trace-estimation"],"_links":{"self":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/932","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/comments?post=932"}],"version-history":[{"count":99,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/932\/revisions"}],"predecessor-version":[{"id":1967,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/932\/revisions\/1967"}],"wp:attachment":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/media?parent=932"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/categories?post=932"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/tags?post=932"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}