On Lower Bounds for Statistical Learning Theory

Abstract

In recent years, tools from information theory have played an increasingly prevalent role in statistical machine learning. In addition to developing efficient, computationally feasible algorithms for analyzing complex datasets, it is of theoretical importance to determine whether such algorithms are “optimal” in the sense that no other algorithm can lead to smaller statistical error. This paper provides a survey of various techniques used to derive information-theoretic lower bounds for estimation and learning. We focus on the settings of parameter and function estimation, community recovery, and online learning for multi-armed bandits. A common theme is that lower bounds are established by relating the statistical learning problem to a channel decoding problem, for which lower bounds may be derived involving information-theoretic quantities such as the mutual information, total variation distance, and Kullback–Leibler divergence. We close by discussing the use of information-theoretic quantities to measure independence in machine learning applications ranging from causality to medical imaging, and mention techniques for estimating these quantities efficiently in a data-driven manner.

1. Introduction

Statistical learning theory refers to the rigorous mathematical analysis of machine learning algorithms [1,2]. On one hand, it is desirable to derive error bounds for the performance of particular machine learning algorithms under appropriate assumptions on the probabilistic models used to generate the data. On the other hand, it is important to understand the fundamental limitations of any algorithmic procedure, which may be influenced by quantities such as the sample size, signal-to-noise ratio, or smoothness of an ambient function space. Whereas statistical techniques based on concentration inequalities and empirical process theory may often be employed to derive rates of convergence of specific estimators to the underlying parameters of a data-generating distribution, the somewhat trickier problem of quantifying the best possible performance of any learning procedure requires tools from information theory.

A general approach is to relate the machine learning task at hand to an appropriate channel decoding problem, where the output corresponds to the observed data and the input corresponds to a cleverly constructed subset of the parameter space. For estimation problems, the key observation is that, if the underlying parameters may be estimated closely (i.e., on the level of discretization of the subset of parameter space), decoding may be performed accurately with high probability. The hardness of the decoding problem may in turn be quantified using techniques in information theory [3], leading to a lower bound on the estimation error. This strategy has been applied successfully to a diverse array of statistical estimation problems, including parametric and nonparametric regression, structure estimation for graphical models, covariance matrix estimation, and dimension reduction methods such as principal component analysis [4,5,6,7,8,9]. Section 2 discusses the method and several illustrative examples in greater detail.

Although some classes of machine learning problems may not be analyzed directly using these methods, alternative approaches involving related information-theoretic concepts may be employed. In Section 3 and Section 4, we consider the problems of community recovery and online learning, which are both active areas of research in machine learning. Our discussion of weak recovery in the community estimation setting is similar to the framework described in Section 2, but since the loss function used to quantify the estimation error incurred by the algorithm is more complicated, a more careful analysis must be conducted to derive sharp lower bounds. The theory characterizing the regimes in which exact recovery is possible are of a somewhat different flavor, but the emergence of sharp thresholds may again be related to Shannon coding theory. Section 4, concerning online learning for multi-armed bandits, provides a still different setting, where the goal is to bound a quantity known as regret. Although this is a radically different goal from bounding estimation error, the techniques used to obtain lower bounds for multi-armed bandits nonetheless include components of reductions to channel decoding problems: The key is to relate the performance of a learning algorithm to a problem of distinguishing between pairs of parameter assignments corresponding to underlying reward distributions that are close in parameter space.

We include proof sketches for the stated theorems in the main text of the paper, with references to resources where the reader can find more detailed proofs and additional background material. Although the discussion of each problem setting is necessarily brief, given the broad scope of this paper, we hope that our survey will convey the high-level ideas involved in applying information-theoretic tools to derive lower bounds for some statistical machine learning problems in a clear, concise manner. We have intentionally selected a diverse variety of problem settings in order to help the reader compare and contrast different approaches for obtaining lower bounds and identify the common threads underlying all the strategies.

2. Statistical Estimation

We begin by discussing an approach based on minimax theory for statistical estimation problems [10]. Our goal is a lower bound on the following quantity, known as the minimax risk:

$$\underset{\widehat{\theta }}{inf}\underset{P\in \mathcal{P}}{sup}{\mathbb{E}}_{X\sim P}\left[\ell (\widehat{\theta }\left(X\right),\theta \left(P\right))\right],$$

(1)

where ℓ is a symmetric loss function. Here, $\mathcal{P}$ denotes a class of data-generating distributions and $\theta :\mathcal{P}\to \mathsf{\Omega }$ is a functional that maps each distribution in $\mathcal{P}$ to a parameter in the metric space $\mathsf{\Omega }$. The expectation in expression (1) is taken with respect to data from a particular distribution $P\in \mathcal{P}$, and the infimum is then taken over all possible estimators $\widehat{\theta }=\widehat{\theta }\left(X\right)$ computed from the data. In other words, quantity (1) captures the worst-case risk of the best possible estimator. Whereas statistical analysis of a specific estimator can provide an upper bound on the minimax risk, tools from information theory may be used to derive a lower bound on the same quantity. Throughout this section, we will restrict our attention to the setting where $\ell =\mathsf{\Phi }\circ \rho$, for a metric $\rho$ and monotonically increasing function $\mathsf{\Phi }:[0,\infty )\to [0,\infty )$. For instance, Example 2 below will discuss the setting where $\rho$ is the $L_2$-distance in a function space and $\mathsf{\Phi }\left(t\right)=t^2$, so ℓ is the squared $L_2$-distance.

The basic idea is to transform an estimation problem into a decoding problem, in which we wish to infer the correct message from a discrete set of messages, corresponding to a collection of parameters. The estimation problem must be at least as hard as the decoding problem, since, if the parameters in the discrete set are appropriately separated, accurate parameter estimation implies accurate decoding. In Section 2.1, we present a general technique based on Fano’s inequality, which expresses the probability of error for the decoding in terms of the mutual information between the input (parameters in the discrete subset) and output (observed data). Section 2.2 and Section 2.3 then provide methods for bounding the mutual information and discuss applications to concrete statistical estimation settings. We will follow the convention of Cover and Thomas [3] and take all logarithms with respect to base 2 in our definitions of entropy and mutual information; analogous results hold when logarithms are taken with respect to base e.

2.1. Fano’s Method

We begin by describing the general approach for deriving lower bounds. The key idea consists of relating the estimation problem to a decoding problem, and then using Fano’s inequality to lower-bound the probability of error for the decoding problem. Recall the definition of the mutual information:

$$I(Y;X)=H\left(Y\right)-H\left(Y\right|X).$$

(2)

The main result relates the minimax risk to the mutual information between observations and the data-generating distribution.

Theorem 1.

Suppose $\{P_1,\dots ,P_M\}\subseteq \mathcal{P}$ satisfy $\rho (\theta \left(P_i\right),\theta \left(P_j\right))\ge 2\delta$, for all $i\ne j$. Then

$$\underset{\widehat{\theta }}{inf}\underset{P\in \mathcal{P}}{sup}{\mathbb{E}}_{X\sim P}\left[\ell (\widehat{\theta }\left(X\right),\theta \left(P\right))\right]\ge \mathsf{\Phi }\left(\delta \right)\left(1-\frac{I(Y;X)-1}{{log}_{2}M}\right),$$

where Y is distributed uniformly on $\{1,\dots ,M\}$ and the conditional distribution of X given Y is defined by $X\mid \{Y=j\}\sim P_j$.

Proof (sketch).

We begin by writing

$$\underset{P\in \mathcal{P}}{sup}{\mathbb{E}}_{X\sim P}\left[\ell (\widehat{\theta }\left(X\right),\theta \left(P\right))\right]\ge \frac{1}{M}\sum _{i=1}^M{\mathbb{E}}_{X\sim P_i}\left[\ell (\widehat{\theta }\left(X\right),\theta \left(P_i\right))\right].$$

(3)

If we define the decision rule

$$\psi \left(X\right)=arg\underset{1\le j\le M}{min}\ell ({\theta }_j,\widehat{\theta }\left(X\right)),$$

where we break ties arbitrarily, we may verify that

$${\mathbb{E}}_{X\sim P_i}\left[\ell (\widehat{\theta }\left(X\right),\theta \left(P_i\right))\right]\stackrel{\left(a\right)}{\ge }\mathsf{\Phi }\left(\delta \right){\mathbb{P}}_i\left(\ell (\widehat{\theta }\left(X\right),\theta \left(P_i\right))\ge \mathsf{\Phi }\left(\delta \right)\right)\stackrel{\left(b\right)}{\ge }\mathsf{\Phi }\left(\delta \right){\mathbb{P}}_i\left(\psi \left(X\right)\ne i\right),$$

for each $1\le i\le M$. Inequality $\left(a\right)$ is a direct application of Markov’s inequality, and inequality $\left(b\right)$ follows from the fact that if $\ell (\widehat{\theta },{\theta }_i)<\mathsf{\Phi }\left(\delta \right)$, or equivalently, $\rho (\widehat{\theta },{\theta }_i)<\delta$, then

$$\rho (\widehat{\theta },{\theta }_j)\ge \rho ({\theta }_i,{\theta }_j)-\rho ({\theta }_i,\widehat{\theta })>2\delta -\delta >\rho (\widehat{\theta },{\theta }_i),\forall j\ne i,$$

implying that $\psi \left(X\right)=i$.

Now, recall the statement of Fano’s inequality:

Lemma 1

(Fano’s inequality [3]) For any estimator $\widehat{Y}$ of Y such that $Y\to X\to \widehat{Y}$ forms a Markov chain, it holds that

$$\mathbb{P}(\widehat{Y}\ne Y)\ge \frac{H\left(Y\right|X)-1}{{log}_2\left|\mathcal{Y}\right|},$$

where $\mathcal{Y}$ is the range of Y.

Applying Lemma 1 with $\widehat{Y}=\psi \left(X\right)$ and writing out the error probability explicitly, we obtain

$$\frac{1}{M}\sum _{i=1}^M{\mathbb{P}}_i(\psi \left(X\right)\ne i)\ge \frac{H\left(Y\right|X)-1}{{log}_{2}M}=\frac{{log}_{2}M-I(Y;X)-1}{{log}_{2}M},$$

(4)

where the equality follows from relation (2) and the fact that Y has a uniform distribution. Combining inequalities (3) and (4) establishes the desired result. ☐

In the following subsections, we describe two methods for upper-bounding the mutual information term $I(Y;X)$ appearing in Theorem 1, yielding a lower bound on the minimax risk.

2.2. Local Packings

The first method applies the convexity of the Kullback-Leibler (KL) divergence to obtain an upper bound on $I(Y;X)$ in terms of pairwise KL divergences. We have the following lemma:

Lemma 2.

Let X and Y be defined as in Theorem 1. Then,

$$I(Y;X)\le \frac{1}{M^2}\sum _{1\le i,j\le M}{D}_{KL}(P_i\parallel P_j).$$

Proof. 

We can check that

$$I(Y;X)=\frac{1}{M}\sum _{i=1}^M{D}_{KL}(P_i\parallel \overline{P}),$$

where $\overline{P}=\frac{1}{M}{\sum }_{j=1}^M{P}_j$ is a mixture distribution. By the convexity of the KL divergence, we then have

$$I(Y;X)\le \frac{1}{M}\sum _{i=1}^M\frac{1}{M}\sum _{j=1}^M{D}_{KL}(P_i\parallel P_j),$$

which is the desired expression. ☐

This bounding technique is known as a “local packing”, since the trick is to design an appropriate set $\{P_1,\dots ,P_M\}$ such that the parameters $\theta \left(P_i\right)$ are $2\delta$-separated, while the pairwise KL divergences between the data-generating distributions are relatively small.

Example 1

(High-dimensional linear regression). Suppose we have observation pairs ${\left\{(x_i,y_i)\right\}}_{i=1}^n$ from a linear model:

$$y_i=x_i^T{\beta }^{*}+w_i,$$

where $x_i\in {\mathbb{R}}^p$ and $w_i\sim N(0,{\sigma }^2)$ is i.i.d. noise, and ${\beta }^{*}\in {\mathbb{R}}^p$ is the unknown parameter vector. We assume that $p>n$, but ${\beta }^{*}$ is known to have at most s nonzero values, where $s\le n$. More precisely, if ${\mathbb{B}}_q\left(r\right)$ denotes the ball of radius r in the ${\ell }_q$ norm, we are interested in characterizing the minimax risk over the parameter space

$${\mathbb{B}}_0\left(s\right)\cap {\mathbb{B}}_2\left(1\right)=\left\{\beta \in {\mathbb{R}}^p{:\parallel \beta \parallel }_0\le s,{\parallel \beta \parallel }_2\le 1\right\}.$$

For any fixed parameter $\delta >0$, it is possible to construct a subset of parameters $\{{\beta }_1,\dots ,{\beta }_M\}$ lying in the parameter space such that $\delta \le \parallel {\beta }_j-{\beta }_k{\parallel }_2\le 2\delta \sqrt{2}$ for all $1\le j<k\le M$ and $logM\ge \frac{s}{2}log\left(\frac{p-s}{s/2}\right)$, essentially by rescaling a packing of the subset of ${\{-1,0,1\}}^p$ of s-sparse vectors such that the Hamming distance between any two elements is at least $\frac{s}{2}$ [4,11]. Furthermore, we may compute the pairwise KL divergences in terms of the squared ${\ell }_2$-norm between parameter vectors, so

$$D_{KL}(P_j\parallel P_k)=\frac{1}{2{\sigma }^2}{\parallel X({\beta }_j-{\beta }_k)\parallel }_2^2\le \frac{4n{\delta }^2{\gamma }_{2s}^2}{{\sigma }^2},$$

where ${\gamma }_{2s}={sup}_{\beta \in {\mathbb{B}}_0\left(2s\right)}\frac{{\parallel X\beta \parallel }_2}{\sqrt{n}{\parallel \beta \parallel }_2}$. Note that $P_j$ and $P_k$ refer to the conditional distributions of the $y_i$’s given the $x_i$’s for this example, so we are assuming the design matrix is fixed. Applying Theorem 1 and Lemma 2 with ρ equal to the ${\ell }_2$-distance and Φ equal to the identity, we therefore have

$$\underset{\widehat{\beta }}{inf}\underset{\beta \in {\mathbb{B}}_0\left(s\right)\cap {\mathbb{B}}_2\left(1\right)}{sup}\mathbb{E}\left[\parallel \widehat{\beta }{-\beta \parallel }_2\right]\ge \frac{\delta }{2}\left(1-\frac{\frac{n{\delta }^2{\gamma }_{2s}^2}{{\sigma }^2}-1}{\frac{s}{2}log\left(\frac{p-s}{s/2}\right)}\right).$$

Taking ${\delta }^2\asymp \frac{\sigma slog\left(\frac{p-s}{s/2}\right)}{{\gamma }_{2s}^{2}n}$ and assuming that the problem dimensions satisfy $n\ge Cslogp$, we then obtain a lower bound of the form

$$\underset{\widehat{\beta }}{inf}\underset{\beta \in {\mathbb{B}}_0\left(s\right)\cap {\mathbb{B}}_2\left(1\right)}{sup}\mathbb{E}\left[\parallel \widehat{\beta }{-\beta \parallel }_2\right]\ge \frac{\delta }{4}\ge \frac{c}{{\gamma }_{2s}^2}\sqrt{\frac{s}{n}log\left(\frac{p-s}{s}\right)}.$$

In the case of the ${\ell }_2$-loss, the Lasso estimator achieves the risk expression in the lower bound (up to constant factors), implying that it is a rate-optimal estimator [4]. Similar bounds on the minimax risk may be derived when the norms appearing in the loss function and/or parameter space are replaced by a general ${\ell }_q$-norm [4,12].

2.3. Metric Entropy

The second method for bounding $I(Y;X)$, due to Yang and Barron [13], is based on the metric entropy of the parameter space. Recall the notion of the $ϵ$-covering number of a set in a metric space, which is the minimum number of $ϵ$-balls required to cover the set. The logarithm of the covering number is also known as the metric entropy. In particular, we are interested in the quantity $log{N}_{KL}(ϵ;\mathcal{P})$, defined by

$$N_{KL}(ϵ;\mathcal{P})=min\left\{N:\exists \{Q_1,\dots ,Q_N\}\subseteq \mathcal{P}\mathrm{s}.\mathrm{t}.\underset{1\le i\le N}{min}\sqrt{D_{KL}(P,Q_i)}\le ϵ,\forall P\in \mathcal{P}\right\},$$

which denotes the $ϵ$-covering number of $\mathcal{P}$, where distances are measured with respect to the square root KL divergence. We have the following bound:

Lemma 3.

Let X and Y be defined as in Theorem 1. Then,

$$I(Y;X)\le \underset{ϵ>0}{inf}\left\{{ϵ}^2+log{N}_{KL}(ϵ;\mathcal{P})\right\}.$$

Proof (sketch).

Suppose $\{Q_1,\dots ,Q_N\}$ is an $ϵ$-cover of $\mathcal{P}$ with respect to the square root KL divergence. Letting $\overline{P}=\frac{1}{M}{\sum }_{i=1}^M{P}_i$ and $\overline{Q}=\frac{1}{N}{\sum }_{j=1}^N{Q}_j$, we can check that

$$I(Y;X)=\frac{1}{M}\sum _{i=1}^M{D}_{KL}(P_i\parallel \overline{P})\le \frac{1}{M}\sum _{i=1}^M{D}_{KL}(P_i\parallel \overline{Q}),$$

where the inequality holds because $\overline{P}$ minimizes the average KL divergence with respect to the second argument. Furthermore, we know that there exists some $Q_n$ such that $D_{KL}(P_i\parallel Q_n)\le {ϵ}^2$, implying that

$$\begin{array}{cc}\hfill D_{KL}(P_i\parallel \overline{Q})& =\int log\frac{d{P}_i\left(X\right)}{d\overline{Q}\left(X\right)}d{P}_i\left(X\right)\le \int log\frac{d{P}_i\left(X\right)}{\frac{1}{N}d{Q}_n\left(X\right)}d{P}_i\left(X\right)=D_{KL}(P_i\parallel Q_n)+logN\hfill \\ & \le {ϵ}^2+log{N}_{KL}(ϵ;\mathcal{P}).\hfill \end{array}$$

Since the above inequality holds for all $ϵ>0$, we may take an infimum over $ϵ$ to obtain the stated bound.  ☐

As an example of the above technique, we consider the problem of nonparametric regression. Note that the following example shows that the general machinery developed above, though described in terms of parameter estimation, may be applied to nonparametric settings involving function estimation, as well.

Example 2.

(Nonparametric regression) Suppose we observe i.i.d. pairs ${\left\{(x_i,y_i)\right\}}_{i=1}^n$, where

$$y_i=f^{*}\left(x_i\right)+w_i,$$

$x_i\sim Uniform[0,1]$, $w_i\sim N(0,1)$, and $x_i$ is independent of $w_i$. We also assume that $f^{*}$ belongs to the function class ${\mathcal{F}}_s$, for a positive integer s, defined as the set of all continuous functions f on $[0,1]$ satisfying the following properties:

(i)

f is differentiable $s-1$ times on $(0,1),$

(ii)

${sup}_{0\le x\le 1}\left|f^{\left(k\right)}\left(x\right)\right|\le 1$, for all $k=0,1,\dots ,s-1$, where $f^{\left(0\right)}\left(x\right):=f\left(x\right),$

(iii)

$f^{(s-1)}$ is 1-Lipschitz on $(0,1)$.

We derive lower bounds on the minimax risk of estimating $f^{*}$ when ℓ is the squared $L_2$-distance, defined by

$$\ell (f,g)={\int }_0^1{\left(f\left(x\right)-g\left(x\right)\right)}^{2}dx.$$

Hence, we will take $\mathsf{\Phi }\left(t\right)=t^2$ and ρ equal to the $L_2$-distance. Let $\mathcal{P}$ denote the set of joint distributions of $(x,y)$ generated by the class ${\mathcal{F}}_s$. By standard results on the metric entropy of function classes [14,15], we have the bound

$$c{\left(\frac{1}{ϵ}\right)}^{1/s}\le log{N}_2(ϵ;{\mathcal{F}}_s)\le C{\left(\frac{1}{ϵ}\right)}^{1/s},$$

where $log{N}_2(ϵ;{\mathcal{F}}_s)$ denotes the metric entropy of ${\mathcal{F}}_s$ with respect to the $L_2$-distance. Furthermore, for any $\delta >0$, there exists a δ-packing $\{f_1,\dots ,f_M\}$ of ${\mathcal{F}}_s$ in the $L_2$-metric such that $logM=c^{\prime }{\left(\frac{1}{\delta }\right)}^{1/s}$. For two functions $f,g\in {\mathcal{F}}_s$, we may compute the KL divergence between the corresponding distributions $P_f,P_g\in \mathcal{P}$:

$$D_{KL}(P_f\parallel P_g)=\frac{n}{2}·{\parallel f-g\parallel }_2^2.$$

Hence, it follows that

$$log{N}_{KL}(ϵ;\mathcal{P})\le log{N}_2\left(ϵ\sqrt{\frac{2}{n}};{\mathcal{F}}_s\right)\le C{\left(\frac{1}{ϵ}\sqrt{\frac{n}{2}}\right)}^{1/s}.$$

Minimizing the bound obtained from Lemma 3 with respect to ϵ, we obtain ${ϵ}^{*}=C^{\prime }{n}^{\frac{1}{4s+2}}$, and plugging back into Theorem 1, we obtain the lower bound

$${\delta }^2\left(1-\frac{C^{″}{n}^{1/(4s+2)}}{{(1/\delta )}^{1/s}}\right).$$

Taking $\delta \asymp {\left(\frac{1}{n}\right)}^{s/(4s+2)}$ then yields the bound

$$\underset{\widehat{f}}{inf}\underset{f^{*}\in {\mathcal{F}}_s}{sup}{\mathbb{E}}_{f^{*}}\left[\parallel \widehat{f}-f^{*}{\parallel }_2^2\right]\ge c^{\prime }{\left(\frac{1}{n}\right)}^{s/(2s+1)}.$$

A matching upper bound may be derived using local weighted polynomial regression [16], so the minimax risk is $\mathsf{\Theta }\left(n^{-s/(2s+1)}\right)$.

3. Community Recovery

Another area of machine learning that has recently received a substantial amount of attention concerns recovering communities based on node connectivity in a network. A popular probabilistic model is known as the stochastic block model (SBM). In the simplest form of the model, parametrized by $(n,K,p,q)$, the graph has nodes $\{1,\dots ,n\}$ partitioned into K communities. Let the community label of node i be denoted by $\sigma \left(i\right)$. The edge set E of the random graph G is then constructed in the following manner: each edge $(i,j)$ is generated independently from all others, with probability

$$P\left((i,j)\in E\right)=\left\{\begin{array}{cc}p,\hfill & \mathrm{if}\sigma \left(i\right)=\sigma \left(j\right),\hfill \\ q,\hfill & \mathrm{if}\sigma \left(i\right)\ne \sigma \left(j\right).\hfill \end{array}\right.$$

The goal is to partition the n nodes into the underlying communities based on observing the graph G.

In order to measure the performance of an algorithm, we consider the loss function

$$r(\widehat{\sigma },\sigma )=\frac{1}{n}\underset{\tau \in S_K}{min}{d}_H(\widehat{\sigma },\tau \circ \sigma ).$$

Here, the estimator $\widehat{\sigma }:\{1,\dots ,n\}\to \{1,\dots ,K\}$ corresponds to a partitioning of the nodes into K communities, and $d_H$ denotes the Hamming distance between assignments. Furthermore, we take the minimum over all permutations $S_K$ of the community labels. Hence, $r(\widehat{\sigma },\sigma )$ is the proportion of incorrectly labeled nodes (for the optimal labeling of partitions). We will focus our discussion on the setting where K is fixed, but p and q may vary with n; generalizations exist in the literature where K is allowed to grow with n, as well. We are interested in the behavior of various algorithms as $n\to \infty$.

In the following two subsections, we discuss the popular notions of weak recovery and exact recovery. The algorithm $\widehat{\sigma }$ achieves weak recovery if $\mathbb{E}\left[r(\widehat{\sigma },\sigma )\right]\to 0$ (i.e., the expected fraction of misclassified nodes tends to 0 as $n\to \infty$), and achieves exact recovery if $r(\widehat{\sigma },\sigma )=0$. For a more complete description of current work on stochastic block models, see the extensive survey paper by Abbe [17].

3.1. Weak Recovery

Analogous to the setting discussed in Section 2, we may derive bounds on the minimax risk

$$\underset{\widehat{\sigma }}{inf}\underset{\sigma \in \Sigma (n,K)}{sup}\mathbb{E}\left[r(\widehat{\sigma },\sigma )\right],$$

where $\Sigma (n,K)$ is an appropriate class of underlying community labelings. We state and prove a result for approximately equal-sized communities in the limit as $n\to \infty$, so $\Sigma (n,K)$ is the set of all labelings $\sigma$ such that $\left|\{i:\sigma \left(i\right)=k\}\right|=(1+o\left(1\right))\frac{n}{K}$, for all $1\le k\le K$.

The main result is the following [18]:

Theorem 2.

Suppose $p=\frac{a}{n}$ and $q=\frac{b}{n}$, and suppose $\frac{nI}{K}\to \infty$, where

$$I=-2log\left(\sqrt{\frac{a}{n}}\sqrt{\frac{b}{n}}+\sqrt{1-\frac{a}{n}}\sqrt{1-\frac{b}{n}}\right).$$

(5)

A lower bound on the minimax risk of community estimation is given by

$$\underset{\widehat{\sigma }}{inf}\underset{\sigma \in \Sigma (n,K)}{sup}\mathbb{E}\left[r(\widehat{\sigma },\sigma )\right]\ge exp\left(-(1+o\left(1\right))\frac{nI}{K}\right).$$

Proof (sketch).

The core of the approach bears similarity to the method for obtaining lower bounds for estimation, in the sense that we construct a subset ${\Sigma }^L$ of the parameter space corresponding to “messages”, which we wish to recover via an appropriate decoding strategy. In the case when $K=2$ (and n is even), the subset ${\Sigma }^L$ consists of all partitions of the nodes into equal-sized communities and communities of size $\left(\frac{n}{2}+1,\frac{n}{2}-1\right)$. We focus on the case $K=2$ in the present proof sketch to avoid technical complications.

The proof is somewhat more involved than the strategies outlined in Section 2, however, since the unknown quantity to be estimated is a set of discrete labelings and the loss function is defined with respect to an optimal permutation. The first step is to lower-bound the minimax risk by the average risk over the class ${\Sigma }^L$. Furthermore, a more technical argument shows that we may just examine the average local risk defined with respect to a single node in the graph:

$$\begin{array}{cc}\hfill \underset{\widehat{\sigma }}{inf}\underset{\sigma \in \Sigma (n,K)}{sup}\mathbb{E}\left[r(\widehat{\sigma },\sigma )\right]& \ge \underset{\widehat{\sigma }}{inf}\underset{\sigma \in {\Sigma }^L}{sup}{\mathbb{E}}_{\sigma }\left[r(\widehat{\sigma },\sigma )\right]\hfill \\ & \ge \underset{\widehat{\sigma }}{inf}\frac{1}{|{\Sigma }^L|}\sum _{\sigma \in {\Sigma }^L}\mathbb{E}\left[r(\widehat{\sigma },\sigma )\right]\hfill \\ & =\underset{\widehat{\sigma }}{inf}\frac{1}{|{\Sigma }^L|}\sum _{\sigma \in {\Sigma }^L}\mathbb{E}\left[r_1(\widehat{\sigma },\sigma )\right],\hfill \end{array}$$

where $r_1$ is the local loss function defined with respect to node 1, which is the fraction of optimal permutations of community assignments that incorrectly classify node 1. The next step is to lower-bound the local risk (uniformly over all choices of $\sigma \in {\Sigma }^L$) using the minimum risk of a binary hypothesis testing problem, where the two hypotheses correspond to the possible assignments of node 1 as a member of the first or second community. In particular, we have the following inequality, which holds for each $\sigma$:

$$\mathbb{E}\left[r_1(\widehat{\sigma },\sigma )\right]\ge c\mathbb{P}\left(\sum _{i=1}^{n/2}{X}_i\ge \sum _{j=1}^{n/2}{Y}_j\right),$$

where $X_i\stackrel{i.i.d.}{\sim }Bernoulli\left(\frac{b}{n}\right)$ and $Y_j\stackrel{i.i.d.}{\sim }Bernoulli\left(\frac{a}{n}\right)$ are independent random variables. Standard techniques involving large deviation inequalities allow us to lower-bound the latter probability, thus yielding the overall lower bound appearing in the theorem.  ☐

As demonstrated by Zhang and Zhou [18], the lower bound on the risk appearing in Theorem 2 may be achieved using a form of penalized likelihood estimation. A computationally feasible procedure was subsequently provided in Gao et al. [19].

Remark 1.

The quantity I appearing in Equation (5) is the Renyi divergence of order $\frac{1}{2}$ between a Bernoulli$\left(\frac{a}{n}\right)$ and Bernoulli$\left(\frac{b}{n}\right)$ distribution. In fact, these results generalize to the case of non-binary edge weights, and the Renyi divergence of order $\frac{1}{2}$ also appears in the minimax rates for estimation in weighted stochastic block models [20]. Furthermore, if the communities are not all of equal size, alternative divergence functions appear in the error exponent [21,22]. Finally, note that the regime where $p=\frac{a}{n}$ and $q=\frac{b}{n}$, with $a,b=\mathsf{\Theta }\left(1\right)$, corresponds to the threshold at which giant components emerge in the network [23]. Theorem 2 allows a and b to scale arbitrarily with n, provided $\frac{nI}{K}\to \infty$, which will not hold if $a,b\ll n$.

3.2. Exact Recovery

Information-theoretic arguments may also be used to establish lower bounds for exact recovery in stochastic block models, which corresponds to correct classification of every single node (up to permutation the of community labels). We present a result, due to Abbe et al. [24], that provides lower bounds for exact recovery in the case of two equal-sized communities.

We have the following result:

Theorem 3.

Let $p=\frac{alogn}{n}$ and $b=\frac{qlogn}{n}$, where $a>b\ge 0$. If ${\left(\sqrt{a}-\sqrt{b}\right)}^2<2$, then for sufficiently large n, the maximum likelihood estimator fails in recovering the communities with probability bounded away from 0:

$$lim\underset{n\to \infty }{inf}\mathbb{P}\left(r({\widehat{\sigma }}_{MLE},\sigma )\ne 0\right)>0.$$

Proof (sketch).

We denote the two communities by A and B. Let F be the event that the maximum likelihood estimator fails in performing exact recovery, and let

$$\begin{array}{cc}\hfill F_A& =\left\{\exists i\in A:i\mathrm{is}\mathrm{connected}\mathrm{to}\mathrm{more}\mathrm{nodes}\mathrm{in}B\mathrm{than}\mathrm{in}A\right\},\hfill \\ \hfill F_B& =\left\{\exists j\in B:j\mathrm{is}\mathrm{connected}\mathrm{to}\mathrm{more}\mathrm{nodes}\mathrm{in}A\mathrm{than}\mathrm{in}B\right\}.\hfill \end{array}$$

By symmetry, we have $\mathbb{P}\left(F_A\right)=\mathbb{P}\left(F_B\right)$. Furthermore, note that

$$F_A\cap F_B\subseteq F,$$

since if both $F_A$ and $F_B$ were to occur simultaneously, swapping the labels of the nodes i and j would lead to a higher value of the likelihood than in the case of correct labeling. In particular, this implies that

$$\mathbb{P}\left(F\right)\ge \mathbb{P}(F_A\cap F_B)\ge \mathbb{P}\left(F_A\right)+\mathbb{P}\left(F_B\right)-1=2\mathbb{P}\left(F_A\right)-1.$$

(6)

Let $H\subseteq A$ denote a fixed subset with $\left|H\right|=⌊\frac{n}{{log}^3\left(n\right)}⌋$, and define the event

$$F_H=\left\{\exists j\in H\mathrm{s}.\mathrm{t}.E(j,A\setminus H)+\frac{logn}{loglogn}\le E(j,B)\right\},$$

where $E(j,C)$ denotes the number of edges between j and the nodes in C. Note that, if event $F_H$ occurs and all nodes in H are connected to at most $\frac{logn}{loglogn}$ other nodes in H, then event $F_A$ must occur. Furthermore, one can show that, with high probability, every node in H is connected to at most $\frac{logn}{loglogn}$ other nodes in H. Hence,

$$\mathbb{P}\left(F_A\right)\ge \mathbb{P}\left(F_H\right)+o\left(1\right).$$

(7)

It remains to derive a lower bound on $\mathbb{P}\left(F_H\right)$. For $j\in H$, let

$$F_H^{\left(j\right)}=\left\{E(j,A\setminus H)+\frac{logn}{loglogn}\le E(j,B)\right\},$$

and note that the $F_H^{\left(j\right)}$’s are independent. Hence,

$$\mathbb{P}\left(F_H\right)=\mathbb{P}\left(\bigcup _{j\in H}{F}_H^{\left(j\right)}\right)=1-\prod _{j\in H}\left(1-\mathbb{P}\left(F_H^{\left(j\right)}\right)\right).$$

Straightforward techniques for bounding sums of independent Bernoulli random variables show that $\mathbb{P}\left(F_H^{\left(j\right)}\right)>\frac{log\left(4\right){log}^3\left(n\right)}{n}$ for each j, from which we can conclude that

$$\mathbb{P}\left(F_H\right)\ge 1-{\left(1-\frac{log\left(4\right){log}^3\left(n\right)}{n}\right)}^{⌊\frac{n}{{log}^3\left(n\right)}⌋}=1-\frac{1}{4}+o\left(1\right).$$

(8)

Combining inequalities (6)–(8) then yields the desired result. ☐

Note that for any other estimator $\widehat{\sigma }$, we have

$$\mathbb{P}\left(r({\widehat{\sigma }}_{MLE},\sigma )=0\right)\ge \mathbb{P}\left(r(\widehat{\sigma },\sigma )=0\right).$$

Hence, Theorem 3 also implies that

$$lim\underset{n\to \infty }{inf}\mathbb{P}\left(r(\widehat{\sigma },\sigma )\ne 0\right)\ge \mathbb{P}\left(r({\widehat{\sigma }}_{MLE},\sigma )\ne 0\right)\ge 0.$$

In fact, a converse of Theorem 3 holds, as well:

Theorem 4.

Under the same conditions as in Theorem 3, suppose instead that ${\left(\sqrt{a}-\sqrt{b}\right)}^2>2$. Then, the maximum likelihood estimator succeeds in recovering the communities with probability tending to 1:

$$\underset{n\to \infty }{lim}\mathbb{P}\left(r({\widehat{\sigma }}_{MLE},\sigma )=0\right)=1.$$

Since the focus of this paper is to establish lower bounds, we refer the reader to Abbe [24] for the proof of Theorem 4, which proceeds by direct calculation. An extension of Theorems 3 and 4 for weighted stochastic block models may be found in Jog and Loh [25].

Remark 2.

The threshold behavior described in Theorems 3 and 4 is perhaps not surprising in light of known threshold behavior in Shannon coding theory, and the connections between each of the statistical learning tasks and the problem of decoding on a discrete alphabet after passage through a noisy channel. Indeed, the community recovery problem has been cast in information-theoretic terminology as decoding in a “graphical channel" [26]. On the other hand, the coding scheme is fixed according to the stochastic block model, whereas Shannon theory allows one to design an optimal encoding scheme to achieve channel capacity. See also the paper by Chen et al. [27], and the derivation of similar types of sharp threshold behavior in submatrix localization problems [28,29]. Finally, we note that the scaling $p=\frac{alogn}{n}$ and $q=\frac{blogn}{n}$, when $a,b=\mathsf{\Theta }\left(1\right)$, corresponds to the threshold for the graph to have isolated vertices with probability tending to 1 [23]. Indeed, it would be impossible to perform exact recovery with high probability in the presence of isolated vertices: flipping the community assignments of two isolated vertices belonging to the two different communities would not change the value of the likelihood.

4. Online Learning

We now shift our focus to sequential allocation problems. The setup we consider involves a series of actions taken by a player, using limited feedback about the environment based on his/her past actions. We study the setting of a multi-armed bandit, where each potential action of the player is associated with a reward distribution, but the player only observes the reward corresponding to his/her action on successive rounds. In the following two subsections, we will consider the cases of stochastic and adversarial bandits and obtain bounds on a quantity known as regret. More details on the setting and results may be found in Bubeck and Cesa-Bianchi [30] or Cesa-Bianchi and Lugosi [31].

4.1. Stochastic Bandits

We first analyze the setting of stochastic multi-armed bandits. On each round, the player may choose one of k different arms. Associated to arm j is a reward distribution $P_{{\theta }_j}$, where ${\theta }_j\in \mathsf{\Theta }$ belongs to some parameter space. Furthermore, we assume that the reward distributions ${\left\{P_{{\theta }_j}\right\}}_{j=1}^k$ remain fixed across all rounds. We use the notation $\mu \left(\theta \right)$ to denote the mean of the distribution $P_{\theta }$, and let ${\mu }^{*}={max}_{1\le j\le k}\mu \left({\theta }_j\right)$ denote the maximum expected reward.

Denote the sequence of actions chosen by the player as $(I_1,\dots ,I_n)$, where $I_t\in \{1,\dots ,k\}$ is the arm played at time t, and let $X_{I_t,t}\sim P_{{\theta }_{I_t}}$ denote the observed reward, which is an i.i.d. drawn from the distribution $P_{{\theta }_{I_t}}$. Note that $I_t$ may be a function of the previously observed reward sequence $(X_{I_1,1},\dots ,X_{I_{t-1},t})$ and may also involve additional randomization. We are interested in bounding a quantity known as the pseudo-regret, defined as

$${\overline{R}}_n=n{\mu }^{*}-\mathbb{E}\left[\sum _{t=1}^n{X}_{I_t,t}\right],$$

where we may also write ${\overline{R}}_n({\theta }_1,\dots ,{\theta }_k)$ to make the dependence on the reward distributions explicit. If the player employs a random strategy, the expectation is computed with respect to randomness in the sequence of actions $(I_1,\dots ,I_n)$, as well as randomness generated by draws from the reward distributions. In other words, the pseudo-regret measures the difference between the expected reward incurred by the player’s strategy and the expected reward incurred by playing the arm with maximum expected reward on every round.

Lai and Robbins [32] prove the following result. We omit some technical regularity conditions on the parameter space, such as denseness of the parameter space and continuity with respect to the KL divergence, in order to avoid cluttering the presentation.

Theorem 5.

Suppose that, for all pairs ${\theta }_1,{\theta }_2\in \mathsf{\Theta }$ such that $\mu \left({\theta }_1\right)>\mu \left({\theta }_2\right)$, we have $0<D_{KL}(P_{{\theta }_2}\parallel P_{{\theta }_1})<\infty$. Suppose a strategy satisfies ${\overline{R}}_n({\theta }_1,\dots ,{\theta }_k)=o\left(n^{\alpha }\right)$, for all ${\theta }_1,\dots ,{\theta }_k\in \mathsf{\Theta }$ and all $\alpha >0$. Then, for any $({\theta }_1,\dots ,{\theta }_k)\in \mathsf{\Theta }$, we have

$$lim\underset{n\to \infty }{inf}\frac{{\overline{R}}_n({\theta }_1,\dots ,{\theta }_k)}{logn}\ge \sum _{j:{\mu }_j<{\mu }^{*}}\frac{{\mu }^{*}-{\mu }_j}{D_{KL}(P_{{\theta }_j}\parallel P_{{\theta }^{*}})},$$

where ${\theta }^{*}\in arg{min}_{\theta \in \mathsf{\Theta }}\mu \left(\theta \right)$ and ${\mu }_j=\mu \left({\theta }_j\right)$.

Proof (sketch).

We may write

$${\overline{R}}_n=\sum _{j=1}^k\mathbb{E}\left[T_j\left(n\right)\right]{∆}_j,$$

where ${∆}_j={\mu }^{*}-{\mu }_j$ and $T_j\left(n\right)={\sum }_{t=1}^{n}1\{I_t=j\}$. The main step is to show that the inequality

$$\mathbb{E}\left[T_j\left(n\right)\right]\ge \frac{logn}{D_{KL}(P_{{\theta }_j}\parallel P_{{\theta }^{*}})},\forall j:{\mu }_j<{\mu }^{*}$$

(9)

holds for any strategy. Inequality (9) provides a lower bound on the expected number of pulls to any suboptimal arm (note that, as $P_{{\theta }_j}$ becomes further from $P_{{\theta }^{*}}$, the two arms are easier to distinguish, so the expected number of pulls to the suboptimal arm can be smaller). We focus on proving inequality (9) for $j=2$; the other cases are similar.

Consider two parameter vectors $\theta =({\theta }_1,{\theta }_2,\dots ,{\theta }_k)$ and ${\theta }^{\prime }=({\theta }_1,{\theta }_2^{\prime },\dots ,{\theta }_k)$, which differ only in the second coordinate. We further choose the parameters such that

$$\begin{array}{c}{\mu }_1>{\mu }_2\ge {\mu }_3\ge \dots \ge {\mu }_k,\hfill \\ {\mu }_2^{\prime }\ge {\mu }_1>{\mu }_3\ge \dots \ge {\mu }_k,\hfill \end{array}$$

so the second arm is suboptimal in the first setting but optimal in the second. We will choose ${\theta }_2^{\prime }$ close to ${\theta }_1$, so

$$D_{KL}(P_{{\theta }_2}\parallel P_{{\theta }_2^{\prime }})\approx D_{KL}(P_{{\theta }_2}\parallel P_{{\theta }_1})=D_{KL}(P_{{\theta }_2}\parallel P_{{\theta }^{*}}).$$

(The regularity conditions on the parameter space and reward distributions ensure that such a choice is possible.) The idea is that, since $P_{\theta }$ and $P_{{\theta }^{\prime }}$ are close, any strategy should pick roughly the same sequence of arms in both scenarios, but a strategy that performs well on $\theta$ will behave relatively poorly on ${\theta }^{\prime }$ (and vice versa), since the ordering of arms according to optimality is different in the two settings. In particular, we will derive the following bound, relating the probabilities of pulling the second arm in each of the parameter settings:

$${\mathbb{P}}_{\theta }(T_2\left(n\right)<a_n)\le c_n^{\prime }{\mathbb{P}}_{{\theta }^{\prime }}(T_2\left(n\right)<a_n)+b_n,$$

(10)

where $a_n=\frac{(1-3\alpha )logn}{D_{KL}(P_{{\theta }_2}\parallel P_{{\theta }_2^{\prime }})}$, and we take $\alpha <\frac{1}{3}$. We can show that $b_n=o\left(1\right)$ since $P_{\theta }$ and $P_{{\theta }^{\prime }}$ are close, and that the right-hand probability is also $o\left(1\right)$, since arm 2 is optimal under ${\theta }^{\prime }$.

For a fixed strategy, let ${\left\{X_{j,s}\right\}}_{\stackrel{1\le j\le k}{1\le s\le n}}$ denote the rewards corresponding to various arm pulls. For $A\subseteq \{T_2\left(n\right)=n_2\}$, we have

$$\begin{array}{cc}\hfill {\mathbb{P}}_{{\theta }^{\prime }}\left(A\right)& ={\int }_{A}d{\mathbb{P}}_{{\theta }^{\prime }}\left(x\right)={\int }_A\frac{d{\mathbb{P}}_{{\theta }^{\prime }}\left(x\right)}{d{\mathbb{P}}_{\theta }\left(x\right)}·d{\mathbb{P}}_{\theta }\left(x\right)\hfill \\ & ={\int }_A\prod _{s=1}^{n_2}\frac{d{P}_{{\theta }_2^{\prime }}\left(x_{2,s}\right)}{d{P}_{{\theta }_2}\left(x_{2,s}\right)}d{\mathbb{P}}_{\theta }\left(x\right)\hfill \\ & ={\int }_A{e}^{-L_2\left(x\right)}d{\mathbb{P}}_{\theta }\left(x\right),\hfill \end{array}$$

where we define $L_2\left(x\right)={\sum }_{s=1}^{T_2\left(n\right)}log\frac{d{P}_{{\theta }_2}\left(x_{2,s}\right)}{d{P}_{{\theta }_2^{\prime }}\left(x_{2,s}\right)}$. In particular, if $A\subseteq \{T_2\left(n\right)=n_2,L_2\left(X\right)\le c_n\}$, we have

$${\mathbb{P}}_{{\theta }^{\prime }}\left(A\right)\ge e^{-c_n}{\mathbb{P}}_{\theta }\left(A\right),$$

where we will take $c_n=(1-2\alpha )logn$. We may therefore write

$$\begin{array}{cc}\hfill {\mathbb{P}}_{\theta }(T_2\left(n\right)<a_n)& ={\mathbb{P}}_{\theta }(T_2\left(n\right)<a_n,L_2\left(X\right)\le c_n)+{\mathbb{P}}_{\theta }(T_2\left(n\right)<a_n,L_2\left(X\right)>c_n)\hfill \\ & \le e^{c_n}{\mathbb{P}}_{{\theta }^{\prime }}(T_2\left(n\right)<a_n,L_2\left(X\right)\le c_n)+{\mathbb{P}}_{\theta }(T_2\left(n\right)<a_n,L_2\left(X\right)>c_n)\hfill \\ & \le e^{c_n}{\mathbb{P}}_{{\theta }^{\prime }}(T_2\left(n\right)<a_n)+{\mathbb{P}}_{\theta }(T_2\left(n\right)<a_n,L_2\left(X\right)>c_n),\hfill \end{array}$$

which is inequality (10) with $c_n^{\prime }=e^{c_n}$ and $b_n={\mathbb{P}}_{\theta }(T_2\left(n\right)<a_n,L_2\left(X\right)>c_n)$. Note that if $T_2\left(n\right)<a_n$, we have $L_2\left(X\right)<{\sum }_{s=1}^{a_n}log\frac{d{P}_{{\theta }_2}\left(X_{2,s}\right)}{d{P}_{{\theta }_2^{\prime }}\left(X_{2,s}\right)}$, so

$$b_n\le {\mathbb{P}}_{\theta }\left(\sum _{s=1}^{a_n}log\frac{d{P}_{{\theta }_2}\left(X_{2,s}\right)}{d{P}_{{\theta }_2^{\prime }}\left(X_{2,s}\right)}>c_n\right)=o\left(1\right),$$

where the last equality follows from the fact that the rewards ${\left\{X_{2,s}\right\}}_{s=1}^{a_n}$ are i.i.d. and

$$\frac{1}{a_n}\sum _{s=1}^{a_n}log\frac{d{P}_{{\theta }_2}\left(X_{2,s}\right)}{d{P}_{{\theta }_2^{\prime }}\left(X_{2,s}\right)}\stackrel{a.s.}{⟶}{\mathbb{E}}_{\theta }\left[log\frac{d{P}_{{\theta }_2}\left(X_{2,s}\right)}{d{P}_{{\theta }_2^{\prime }}\left(X_{2,s}\right)}\right]=D_{KL}(P_{{\theta }_2}\parallel P_{{\theta }_2^{\prime }}).$$

Finally, we bound ${\mathbb{P}}_{{\theta }^{\prime }}(T_2\left(n\right)<a_n)$ using Markov’s inequality:

$${\mathbb{P}}_{{\theta }^{\prime }}(T_2\left(n\right)<a_n)={\mathbb{P}}_{{\theta }^{\prime }}(n-T_2\left(n\right)\ge n-a_n)\le \frac{{\mathbb{E}}_{{\theta }^{\prime }}[n-T_2\left(n\right)]}{n-a_n}=o\left(n^{\alpha -1}\right),$$

where the last equality follows from the fact that $a_n=o\left(n\right)$ and the assumption on ${\overline{R}}_n\left({\theta }^{\prime }\right)$. Altogether, we conclude that the right-hand side of inequality (10) is $o\left(1\right)$.

By another application of Markov’s inequality, we conclude that

$${\mathbb{E}}_{\theta }\left[T_2\left(n\right)\right]·\frac{D_{KL}(P_{{\theta }_2}\parallel P_{{\theta }_2^{\prime }})}{logn}\ge {\mathbb{P}}_{\theta }\left(T_2\left(n\right)\ge \frac{logn}{D_{KL}(P_{{\theta }_2}\parallel P_{{\theta }_2^{\prime }})}\right)>{\mathbb{P}}_{\theta }(T_2\left(n\right)>a_n)\to 1.$$

Hence,

$$\frac{{\mathbb{E}}_{\theta }\left[T_2\left(n\right)\right]}{logn}\ge \frac{1}{D_{KL}(P_{{\theta }_2}\parallel P_{{\theta }_2^{\prime }})}\approx \frac{1}{D_{KL}(P_{{\theta }_2}\parallel P_{{\theta }^{*}})},$$

as wanted. ☐

Note that the assumption ${\overline{R}}_n({\theta }_1,\dots ,{\theta }_k)=o\left(n^{\alpha }\right)$ implies that a sufficiently good player strategy exists for all choices of reward parameters. In particular, such a condition may be verified when the reward distributions are Bernoulli (e.g., $P_{\theta }\sim \mathrm{Bernoulli}\left(\theta \right)$). Then, we have

$$D_{KL}(P_{{\theta }_1}\parallel P_{{\theta }_2})={\theta }_{1}log\frac{{\theta }_1}{{\theta }_2}+(1-{\theta }_1)log\frac{1-{\theta }_1}{1-{\theta }_2},$$

and combined with Theorem 5, we obtain the lower bound

$$lim\underset{n\to \infty }{inf}\frac{{\overline{R}}_n({\theta }_1,\dots ,{\theta }_k)}{logn}\ge {\mu }^{*}(1-{\mu }^{*})\sum _{j:{\mu }_j<{\mu }^{*}}\frac{1}{{\mu }^{*}-{\mu }_j}.$$

A player strategy known as the Upper Confidence Bound (UCB) strategy may be shown to achieve this lower bound, up to constant factors [32,33].

Finally, we mention a non-asymptotic lower bound on the pseudo-regret that comes from the probably approximately correct (PAC) literature on bandits [34,35,36]:

Theorem 6.

In the case of Bernoulli reward distributions, there exist positive constants ${\left\{c_i\right\}}_{i=1}^5$ such that for all $k\ge 2$ and $n\ge 1$, the pseudo-regret of any strategy satisfies

$$\underset{{\theta }_1,\dots ,{\theta }_k\in [0,1]}{sup}{\overline{R}}_n({\theta }_1,\dots ,{\theta }_k)\ge min\left\{c_{1}n,c_{2}k+c_{3}n,c_{4}k(logn-logk+c_5)\right\}.$$

(11)

Proof (sketch).

For a detailed proof of Theorem 6, we refer the reader to Mannor and Tsitsiklis [36]. The main idea is to construct a collection of k vectors $\{{\theta }^1,\dots ,{\theta }^k\}\subseteq {[0,1]}^k$ corresponding to the parameters of the reward distributions on arms. For each $2\le i\le k$, we define the vector ${\theta }^i=({\theta }_1^i,\dots ,{\theta }_k^i)$ such that

$${\theta }_1^i=\frac{1}{2}+\frac{ϵ}{2},{\theta }_i^i=\frac{1}{2}+ϵ,{\theta }_j^i=\frac{1}{2},\mathrm{for}j\notin \{1,i\},$$

and we define the vector ${\theta }^1$ such that

$${\theta }_1^1=\frac{1}{2}+\frac{ϵ}{2},{\theta }_j^1=\frac{1}{2},\mathrm{for}j>1.$$

In other words, the reward distribution of arm 1 is the same for all k parameter settings, but in the case of vector ${\theta }^i$, the reward distribution for arm i is slightly better than the reward distributions of the other arms. We then compute a weighted sum of the regret incurred in each parameter setting, where ${\theta }^1$ is given weight $\frac{1}{2}$ and all other ${\theta }^i$’s are given weight $\frac{1}{2(n-1)}$. We may show that this weighted regret is lower-bounded by the quantity appearing in inequality (11), implying the existence of at least one parameter setting that satisfies the desired bound. Computing the lower bound for the weighted regret is similar to the procedure adopted in the proof of Theorem 5, in that we compute a lower bound on the expected number of arm pulls of each suboptimal arm in each parameter setting in terms of $ϵ$. ☐

Theorem 6 is a type of minimax result, stating that, for any player strategy, a distribution of Bernoulli rewards exists for which the problem incurs $\mathsf{\Omega }(logn)$ regret. The same UCB strategies of Auer et al. [33] may be used to obtain $\mathcal{O}(logn)$ upper bounds on the minimax regret even for the worst-case reward distribution, showing that the bound stated in Theorem 6 is tight.

4.2. Adversarial Bandits

In the adversarial setting, we allow the reward distributions to vary arbitrarily over time. Thus, we assume that the reward distributions are chosen by an “adversary”, where the class of permissible adversarial strategies is denoted by $\mathcal{P}$. For a player strategy S and an adversarial strategy $P\in \mathcal{P}$, we define the pseudo-regret analogously to the stochastic case:

$${\overline{R}}_n(S,P)=\underset{1\le j\le k}{max}{\mathbb{E}}_P\left[\sum _{t=1}^n{X}_{j,t}\right]-{\mathbb{E}}_{S,P}\left[\sum _{t=1}^n{X}_{I_t,t}\right],$$

where the first expectation is taken with respect to possible randomization in the adversarial strategy, and the second expectation is taken with respect to randomization in the strategies of both the player and adversary.

The following result provides a lower bound for the minimax pseudo-regret, where the supremum is taken over ${\mathcal{P}}_{Ber}$, the set of all Bernoulli reward distributions over the k time steps, and the infimum is taken over all player strategies [30,37]:

Theorem 7.

The minimax pseudo-regret satisfies the bound

$$\underset{S\in \mathcal{S}}{inf}\underset{P\in {\mathcal{P}}_{Ber}}{sup}{\overline{R}}_n(S,P)\ge \frac{1}{18}·min\{\sqrt{nk},n\},$$

where the infimum is taken over all (possibly randomized) player strategies.

Proof (sketch).

Note that it suffices to prove the bound when the infimum is taken over deterministic player strategies, since the pseudo-regret for a randomized strategy will be a convex combination of the pseudo-regret of deterministic strategies. Fix a deterministic player strategy, and consider the reward distributions ${\mathbb{P}}_1,\dots ,{\mathbb{P}}_k\in {\mathcal{P}}_{Ber}$, where ${\mathbb{P}}_j$ corresponds to the distribution where the reward of each arm $i\ne j$ is i.i.d. Bernoulli$\left(\frac{1}{2}\right)$, and the reward of arm j is i.i.d. Bernoulli$\left(\frac{1}{2}+ϵ\right)$. Note that this construction bears some similarity to the proof outline for Theorem 6 provided above, in that the reward distribution ${\mathbb{P}}_j$ slightly favors arm j. We will also compute a lower bound for the weighted regret, this time allocating uniform weights to each parameter setting, in order to conclude the existence of at least one assignment of reward distributions satisfying the desired lower bounds. Let ${\mathbb{E}}_j$ denote the expectation with respect to the reward distribution ${\mathbb{P}}_j$.

We may compute

$$\frac{1}{k}\sum _{j=1}^k{\overline{R}}_n(S,{\mathbb{P}}_j)=\frac{1}{k}\sum _{j=1}^k{\mathbb{E}}_j\left[\sum _{i\ne j}ϵT_i\left(n\right)\right]=\frac{ϵ}{k}\sum _{j=1}^k{\mathbb{E}}_j\left[n-T_j\left(n\right)\right]=ϵ\left(n-\frac{1}{k}\sum _{j=1}^k{\mathbb{E}}_j\left[T_j\left(n\right)\right]\right),$$

(12)

where $T_i\left(n\right)$ denotes the number of pulls of arm i.

Let $\mathbb{P}$ denote the reward distribution where all arms have a Bernoulli$\left(\frac{1}{2}\right)$ distribution. We may obtain the following bound:

$${\mathbb{E}}_j\left[T_j\left(n\right)\right]\stackrel{\left(a\right)}{\le }{\mathbb{E}}_{\mathbb{P}}\left[T_j\left(n\right)\right]+n\sqrt{\frac{1}{2}{D}_{KL}(\mathbb{P}\parallel {\mathbb{P}}_j)}\stackrel{\left(b\right)}{=}{\mathbb{E}}_{\mathbb{P}}\left[T_j\left(n\right)\right]+\frac{n}{2}\sqrt{log\left(\frac{1}{1-4{ϵ}^2}\right)\mathbb{E}\left[T_j\left(n\right)\right]},$$

(13)

where inequality $\left(a\right)$ may be derived by first relating the difference in expectations for bounded random variables to total variation distance and then applying Pinsker’s inequality, and equality $\left(b\right)$ follows from a direct computation. Combining inequalities (12) and (13), we then obtain

$$\begin{array}{cc}\hfill \frac{1}{k}\sum _{j=1}^k{\overline{R}}_n(S,{\mathbb{P}}_j)& \ge ϵ\left(n-\frac{n}{k}-\frac{n}{2k}\sqrt{log\left(\frac{1}{1-4{ϵ}^2}\right)}\sum _{j=1}^k\sqrt{\mathbb{E}\left[T_j\left(n\right)\right]}\right)\hfill \\ & =ϵn\left(1-\frac{1}{k}-\frac{1}{2}\sqrt{log\left(\frac{1}{1-4{ϵ}^2}\right)}\frac{1}{k}\sum _{j=1}^k\sqrt{\mathbb{E}\left[T_j\left(n\right)\right]}\right)\hfill \\ & \ge ϵn\left(1-\frac{1}{k}-\frac{1}{2}\sqrt{log\left(\frac{1}{1-4{ϵ}^2}\right)}\sqrt{\frac{n}{k}}\right),\hfill \end{array}$$

using the concavity of the square root function. Choosing $ϵ=\frac{1}{4n}min\{\sqrt{kn},n\}$ then yields the inequality

$$\underset{P\in {\mathcal{P}}_{Ber}}{sup}{\overline{R}}_n(S,P)\ge \frac{1}{k}\sum _{j=1}^k{\overline{R}}_n(S,{\mathbb{P}}_j)\ge \frac{1}{18}min\{\sqrt{kn},n\},$$

and taking an infimum over all player strategies produces the desired result. ☐

Note that the lower bound provided in Theorem 7 clearly also holds when the supremum is taken over any class of adversarial strategies containing ${\mathcal{P}}_{Ber}$. In particular, one topic of study is that of oblivious adversaries, which are allowed to perform any strategy that is non-adaptive to the actions of the player (i.e., it is chosen before the start of the first round). The Exp3 algorithm provides an upper bound on the minimax pseudo-regret for oblivious adversaries that matches the lower bound in Theorem 7 up to a factor of $\sqrt{logk}$ [37]. The study of non-oblivious adversaries refers to the setting where the adversary’s actions may be chosen in response to the player’s sequential choices, as well, and is also an active area of research [31,38].

5. Discussion

In this article, we have presented several distinct approaches for deriving lower bounds in various statistical learning problems. In each of the settings described—statistical estimation, community recovery, and online learning—we have shown how to simplify the problem to one involving channel decoding, and leverage information-theoretic bounds on the hardness of the decoding problem to bound the hardness of the corresponding statistical problem. It is worth reflecting on the similarities between the techniques employed in each of the approaches. Although the specific interpretation involving channel decoding looks quite different in each of the settings, the trick is to find an appropriate discretization of parameter space so that pairs of parameters are relatively far apart, but the corresponding data-generating distributions are close. In the context of statistical estimation, this means that we construct a packing of parameter space. In the community recovery setting, we consider pairs of community partitions that differ only in the assignment of a single node. In the multi-armed bandit setting, we consider pairs of arm parameters that flip the assignment of the optimal arm, while perturbing the parameter values as little as possible.

On a more applied note, information-theoretic tools have made an appearance in various machine learning algorithms involving maximizing independence between observed quantities. Some examples include decision tree learning via information gain [39]; independent component analysis by mutual information minimization [40]; causal inference algorithms maximizing independence [41]; minimal-redundancy-maximal-relevance (mRMR) methods for feature selection [42]; and image registration via mutual information maximization in medical imaging [43]. As a result, quantities such as mutual information have become increasingly mainstream in data science applications. Note, however, that such applications of information theory to machine learning have no connection to the channel decoding techniques or hardness results discussed in this article. In terms of statistical theory, these applications have created a renewed interest in deriving efficient estimators of entropy and other related information measures based on finite samples [44,45,46,47], but a detailed discussion of such methods is somewhat orthogonal to the main topic of this survey.