## Guest post by Miklos Racz: The fundamental limits of dimension estimation in random geometric graphs

This post is a continuation of the previous one, where we explored how to detect geometry in a random geometric graph. We now consider the other side of the coin: when is it impossible to detect geometry and what are techniques for proving this? We begin by discussing the model introduced in the previous post and then turn to a more general setup, proving a robustness result on the threshold dimension for detection. The proof of the latter result also gives us the opportunity to learn about the fascinating world of entropic central limit theorems.

Barrier to detecting geometry: when Wishart becomes GOE

Recall from the previous post that is a random geometric graph where the underlying metric space is the -dimensional unit sphere , and where the latent labels of the nodes are i.i.d. uniform random vectors in . Our goal now is to show the impossibility result of Bubeck, Ding, Eldan, and Racz: if , then it is impossible to distinguish between and the Erdos-Renyi random graph . More precisely, we have that

(1)

when and , where denotes total variation distance.

There are essentially three main ways to bound the total variation of two distributions from above: (i) if the distributions have nice formulas associated with them, then exact computation is possible; (ii) through coupling the distributions; or (iii) by using inequalities between probability metrics to switch the problem to bounding a different notion of distance between the distributions. Here, while the distribution of does not have a nice formula associated with it, the main idea is to view this random geometric graph as a function of an Wishart matrix with degrees of freedom—i.e., a matrix of inner products of -dimensional Gaussian vectors—denoted by . It turns out that one can view as (essentially) the same function of an GOE random matrix—i.e., a symmetric matrix with i.i.d. Gaussian entries on and above the diagonal—denoted by . The upside of this is that both of these random matrix ensembles have explicit densities that allow for explicit computation. We explain this connection here in the special case of for simplicity; see Bubeck et al. for the case of general .

Recall that if is a standard normal random variable in , then is uniformly distributed on the sphere . Consequently we can view as a function of an appropriate Wishart matrix, as follows. Let be an matrix where the entries are i.i.d. standard normal random variables, and let be the corresponding Wishart matrix. Note that and so . Thus the matrix defined as

has the same law as the adjacency matrix of . Denote the map that takes to by , i.e., .

In a similar way we can view as a function of an matrix drawn from the Gaussian Orthogonal Ensemble (GOE). Let be a symmetric random matrix where the diagonal entries are i.i.d. normal random variables with mean zero and variance 2, and the entries above the diagonal are i.i.d. standard normal random variables, with the entries on and above the diagonal all independent. Then has the same law as the adjacency matrix of . Note that only depends on the sign of the off-diagonal elements of , so in the definition of we can replace with , where is the identity matrix.

We can thus conclude that

The densities of these two random matrix ensembles are explicit and well known (although we do not state them here), which allow for explicit calculations. The outcome of these calculations is the following result, proven independently and simultaneously by Bubeck et al. and Jiang and Li.

Define the random matrix ensembles and as above. If , then

We conclude that it is impossible to detect underlying geometry whenever .

The universality of the threshold dimension

How robust is the result presented above? We have seen that the detection threshold is intimately connected to the threshold of when a Wishart matrix becomes GOE. Understanding the robustness of this result on random matrices is interesting in its own right, and this is what we will pursue in the remainder of this post, which is based on a recent paper by Bubeck and Ganguly.

Let be an random matrix with i.i.d. entries from a distribution that has mean zero and variance . The matrix is known as the Wishart matrix with degrees of freedom. As we have seen above, this arises naturally in geometry, where is known as the Gram matrix of inner products of points in . The Wishart matrix also appears naturally in statistics as the sample covariance matrix, where is the number of samples and is the number of parameters. (Note that in statistics the number of samples is usually denoted by , and the number of parameters is usually denoted by ; here our notation is taken with the geometric perspective in mind.)

We consider the Wishart matrix with the diagonal removed, and scaled appropriately:

In many applications—such as to random graphs as above—the diagonal of the matrix is not relevant, so removing it does not lose information. Our goal is to understand how large does the dimension have to be so that is approximately like , which is defined as the Wigner matrix with zeros on the diagonal and i.i.d. standard Gaussians above the diagonal. In other words, is drawn from the Gaussian Orthogonal Ensemble (GOE) with the diagonal replaced with zeros.

A simple application of the multivariate central limit theorem gives that if is fixed and , then converges to in distribution. The main result of Bubeck and Ganguly establishes that this holds as long as under rather general conditions on the distribution .

Theorem [Bubeck and Ganguly]

If the distribution is log-concave, i.e., if it has density for some convex function , and if , then

(2)

On the other hand, if has a finite fourth moment and , then

(3)

This result extends Theorem 1 from the previous post and Theorem 1 from above, and establishes as the universal critical dimension (up to logarithmic factors) for sufficiently smooth measures : is approximately Gaussian if and only if is much larger than . For random graphs, as seen above, this is the dimension barrier to extracting geometric information from a network: if the dimension is much greater than the cube of the number of vertices, then all geometry is lost. In the setting of statistics this means that the Gaussian approximation of a Wishart matrix is valid as long as the sample size is much greater than the cube of the number of parameters. Note that for some statistics of a Wishart matrix the Gaussian approximation is valid for much smaller sample sizes (e.g., the largest eigenvalue behaves as in the limit even when the number of parameters is on the same order as the sample size (Johnstone, 2001)).

To distinguish the random matrix ensembles, we have seen in the previous post that signed triangles work up until the threshold dimension in the case when is standard normal. It turns out that the same statistic works in this more general setting; when the entries of the matrices are centered, this statistic can be written as . We leave the details as an exercise for the reader.

We note that for (2) to hold it is necessary to have some smoothness assumption on the distribution . For instance, if is purely atomic, then so is the distribution of , and thus its total variation distance to is . The log-concave assumption gives this necessary smoothness, and it is an interesting open problem to understand how far this can be relaxed.

We will see the proof (and in particular the connection to entropic CLT!) in the next post.

## Guest post by Miklos Racz: Estimating the dimension of a random geometric graph on a high-dimensional sphere

Following the previous post in which we studied community detection, in this post we study the fundamental limits of inferring geometric structure in networks. Many networks coming from physical considerations naturally have an underlying geometry, such as the network of major roads in a country. In other networks this stems from a latent feature space of the nodes. For instance, in social networks a person might be represented by a feature vector of their interests, and two people are connected if their interests are close enough; this latent metric space is referred to as the social space. We are particularly interested in the high-dimensional regime, which brings about a host of new questions, such as estimating the dimension.

A simple random geometric graph model and basic questions

We study perhaps the simplest model of a random geometric graph, where the underlying metric space is the -dimensional unit sphere , and where the latent labels of the nodes are i.i.d. uniform random vectors in . More precisely, the random geometric graph is defined as follows. Let be independent random vectors, uniformly distributed on . In , distinct nodes and are connected by an edge if and only if , where the threshold value is such that For example, when we have .

The most natural random graph model without any structure is the standard Erdos-Renyi random graph , where any two of the vertices are independently connected with probability .

We can thus formalize the question of detecting underlying geometry as a simple hypothesis testing question. The null hypothesis is that the graph is drawn from the Erdos-Renyi model, while the alternative is that it is drawn from . In brief:

(1)

To understand this question, the basic quantity we need to study is the total variation distance between the two distributions on graphs, and , denoted by ; recall that the total variation distance between two probability measures and is defined as . We are interested in particular in the case when the dimension is large, growing with .

It is intuitively clear that if the geometry is too high-dimensional, then it is impossible to detect it, while a low-dimensional geometry will have a strong effect on the generated graph and will be detectable. How fast can the dimension grow with while still being able to detect it? Most of this post will focus on this question.

If we can detect geometry, then it is natural to ask for more information. Perhaps the ultimate goal would be to find an embedding of the vertices into an appropriate dimensional sphere that is a true representation, in the sense that the geometric graph formed from the embedded points is indeed the original graph. More modestly, can the dimension be estimated? We touch on this question at the end of the post.

The dimension threshold for detecting underlying geometry

The high-dimensional setting of the random geometric graph was first studied by Devroye, Gyorgy, Lugosi, and Udina, who showed that geometry is indeed lost in high dimensions: if is fixed and , then . More precisely, they show that this convergence happens when , but this is not tight. The dimension threshold for dense graphs was recently found by Bubeck, Ding, Eldan, and Racz, and it turns out that it is , in the following sense.

Theorem [Bubeck, Ding, Eldan, and Racz 2014]

Let be fixed. Then

Moreover, in the latter case there exists a computationally efficient test to detect underlying geometry (with running time ).

(2)

(3)

Most of this post is devoted to understanding (3), that is, how the two models can be distinguished; the impossibility result of (2) will be discussed in a future post. At the end we will also consider this same question for sparse graphs (where ), where determining the dimension threshold is an intriguing open problem.

The triangle test

A natural test to uncover geometric structure is to count the number of triangles in . Indeed, in a purely random scenario, vertex being connected to both and says nothing about whether and are connected. On the other hand, in a geometric setting this implies that and are close to each other due to the triangle inequality, thus increasing the probability of a connection between them. This, in turn, implies that the expected number of triangles is larger in the geometric setting, given the same edge density. Let us now compute what this statistic gives us.

Given that is connected to both and , and are more likely to be connected under than under .

For a graph , let denote its adjacency matrix. Then

is the indicator variable that three vertices , , and form a triangle, and so the number of triangles in is

By linearity of expectation, for both models the expected number of triangles is times the probability of a triangle between three specific vertices. For the Erd\H{o}s-R\’enyi random graph the edges are independent, so the probability of a triangle is , and thus we have

For it turns out that for any fixed we have

(4)

for some constant , which gives that

Showing (4) is somewhat involved, but in essence it follows from the concentration of measure phenomenon on the sphere, namely that most of the mass on the high-dimensional sphere is located in a band of around the equator. We sketch here the main intuition for , which is illustrated in the figure below.

Let , , and be independent uniformly distributed points in . Then

where the last equality follows by independence. So what remains is to show that this latter conditional probability is approximately . To compute this conditional probability what we really need to know is the typical angle is between and . By rotational invariance we may assume that , and hence , the first coordinate of . One way to generate is to sample a -dimensional standard Gaussian and then normalize it by its length. Since the norm of a -dimensional standard Gaussian is very well concentrated around , it follows that is on the order of . Conditioned on , this typical angle gives the boost in the conditional probability that we see.

If and are two independent uniform points on , then their inner product is on the order of due to the concentration of measure phenomenon on the sphere.

Thus we see that the boost in the number of triangles in the geometric setting is in expectation:

To be able to tell apart the two graph distributions based on the number of triangles, the boost in expectation needs to be much greater than the standard deviation. A simple calculation shows that

and also

Thus we see that if , which is equivalent to .

Signed triangles are more powerful

While triangles detect geometry up until , are there even more powerful statistics that detect geometry for larger dimensions? One can check that longer cycles also only work when , as do several other natural statistics. Yet the underlying geometry can be detected even when .

The simple idea that leads to this improvement is to consider signed triangles. We have already noticed that triangles are more likely in the geometric setting than in the purely random setting. This also means that induced wedges (i.e., when there are exactly two edges among the three possible ones) are less likely in the geometric setting. Similarly, induced single edges are more likely, and induced independent sets on three vertices are less likely in the geometric setting. The following figure summarizes these observations.

The signed triangles statistic incorporates these observations by giving the different patterns positive or negative weights. More precisely, we define

The key insight motivating this definition is that the variance of signed triangles is much smaller than the variance of triangles, due to the cancellations introduced by the centering of the adjacency matrix: the term vanishes, leaving only the term. It is a simple exercise to show that

and

On the other hand it can be shown that

(5)

so the gap between the expectations remains. Furthermore, it can also be shown that the variance also decreases for and we have

Putting everything together we get that if , which is equivalent to . This concludes the proof of (3) from Theorem 1.

Estimating the dimension

Until now we discussed detecting geometry. However, the insights gained above allow us to also touch upon the more subtle problem of estimating the underlying dimension .

Dimension estimation can also be done by counting the “number” of signed triangles as above. However, here it is necessary to have a bound on the difference of the expected number of signed triangles between consecutive dimensions; the lower bound on in~(5) is not enough. Still, we believe that the lower bound should give the true value of the expected value for an appropriate constant , and hence we expect to have that

(6)

Thus, using the variance bound from above, we get that dimension estimation should be possible using signed triangles whenever , which is equivalent to . Showing (6) for general seems involved; Bubeck et al. showed that it holds for , which can be considered as a proof of concept.

Theorem [Bubeck, Ding, Eldan, and Racz 2014]

There exists a universal constant such that for all integers and , one has

This result is tight, as demonstrated by a result of Eldan, which implies that and are indistinguishable when .

The mysterious sparse regime

We conclude this post by discussing an intriguing conjecture for sparse graphs. It is again natural to consider the number of triangles as a way to distinguish between and . Bubeck et al. show that this statistic works whenever , and conjecture that this is tight.

Conjecture [Bubeck, Ding, Eldan, and Racz 2014]

Let be fixed and assume . Then

The main reason for this conjecture is that, when , and seem to be locally equivalent; in particular, they both have the same Poisson number of triangles asymptotically. Thus the only way to distinguish between them would be to find an emergent global property which is significantly different under the two models, but this seems unlikely to exist. Proving or disproving this conjecture remains a challenging open problem. The best known bound is from (2) (which holds uniformly over ), which is very far from !

## Guest post by Miklos Racz: A primer on exact recovery in the general stochastic block model

Foreword: this will be a series of blog posts written by our Theory Group postdoc Miklos Racz. It is essentially the transcript of a mini-course that Miki gave at the University of Washington and at the XX Brazilian School of Probability, and that I gave at the University of Nice. These notes are also posted on arxiv. I now leave the floor to Miki:

Community detection is a fundamental problem in many sciences, such as sociology (e.g., finding tight-knit groups in social networks), biology (e.g., detecting protein complexes), and beyond. Given its importance, there have been a plethora of algorithms developed in the past few decades to detect communities. In the past few years there have also been many works studying the fundamental limits of these recovery algorithms.

This post describes the recent results of Abbe and Sandon which characterize the fundamental limits of exact recovery in the most canonical and popular probabilistic generative model, the stochastic block model (SBM).

The stochastic block model and exact recovery

The general stochastic block model is a distribution on graphs with latent community structure, and it has three parameters:

, the number of vertices;

a probability distribution that describes the relative sizes of the communities;

and , a symmetric matrix that describes the probabilities with which two given vertices are connected, depending on which communities they belong to.

The number of communities, , is implicit in this notation; in these notes we assume that is a fixed constant.

A random graph from is defined as follows:

• The vertex set of the graph is .
• Every vertex is independently assigned a (hidden) label from the probability distribution on . That is, for every .
• Given the labels of the vertices, each (unordered) pair of vertices is connected independently with probability .

Example [Symmetric communities]

A simple example to keep in mind is that of symmetric communities, with more edges within communities than between communities.

This is modeled by the SBM with for all and if and otherwise, with .

We write for a graph generated according to the SBM without the hidden vertex labels revealed.

The goal of a statistical inference algorithm is to recover as many labels as possible using only the underlying graph as an observation.

There are various notions of success that are worth studying. In this post we focus on exact recovery: we aim to recover the labels of all vertices exactly with high probability (whp).

More precisely, in evaluating the success of an algorithm, the agreement of a partition with the true partition is maximized over all relabellings of the communities, since we are not interested in the specific original labelling per se, but rather the partition (community structure) it induces.

For exact recovery, all vertices in all but one community should be non-isolated (in the symmetric case this means that the graph should be connected), requiring the edge probabilities to be .

It is thus natural to scale the edge probability matrix accordingly, i.e., to consider , where .

We also assume that the communities have linear size, i.e., that is independent of , and for all .

From exact recovery to testing multivariate Poisson distributions

As a thought experiment, imagine that not only is the graph given, but also all vertex labels are revealed, except for that of a given vertex . Is it possible to determine the label of ?

Understanding this question is key for understanding exact recovery, since if the error probability of this is too high, then exact recovery will not be possible. On the other hand, it turns out that in this regime it is possible to recover all but labels using an initial partial recovery algorithm. The setup of the thought experiment then becomes relevant, and if we can determine the label of given the labels of all the other nodes with low error probability, then we can correct all errors made in the initial partial recovery algorithm, leading to exact recovery. We will come back to the connection between the thought experiment and exact recovery; for now we focus on understanding this thought experiment.

Given the labels of all vertices except , the information we have about is the number of nodes in each community it is connected to. In other words, we know the degree profile of , where, for a given labelling of the graph’s vertices, the -th component is the number of edges between and the vertices in community .

The distribution of the degree profile depends on the community that belongs to. Recall that the community sizes are given by a multinomial distribution with parameters and , and hence the relative size of community concentrates on . Thus if , the degree profile can be approximated by independent binomials, with approximately distributed as

where denotes the binomial distribution with trials and success probability . In this regime, the binomial distribution is well-approximated by a Poisson distribution of the same mean. Thus the degree profile of a vertex in community is approximately Poisson distributed with mean

where is the -th unit vector. Defining , this can be abbreviated as , where denotes the -th column of the matrix .

We call the quantity the community profile of community ; this is the quantity that determines the distribution of the degree profile of vertices from a given community.

Our thought experiment has thus been reduced to a Bayesian hypothesis testing problem between multivariate Poisson distributions.

The prior on the label of is given by , and we get to observe the degree profile , which comes from one of multivariate Poisson distributions, which have mean times the community profiles , .

Testing multivariate Poisson distributions

We now turn to understanding the testing problem described above; the setup is as follows.

We consider a Bayesian hypothesis testing problem with hypotheses.

The random variable takes values in with prior given by , i.e., .

We do not observe , but instead we observe a draw from a multivariate Poisson distribution whose mean depends on the realization of :

given , the mean is .

In short:

In more detail:

where

and

Our goal is to infer the value of from a realization of .

The error probability is minimized by the maximum a posteriori (MAP) rule, which, upon observing , selects

as an estimate for the value of , with ties broken arbitrarily.

Let denote the error of the MAP estimator.

One can think of the MAP estimator as a tournament of pairwise comparisons of the hypotheses:

if

then the MAP estimate is not .

The probability that one makes an error during such a comparison is exactly

(1)

For finite , the error of the MAP estimator is on the same order as the largest pairwise comparison error, i.e., .

In particular, we have that

(2)

Thus we desire to understand the magnitude of the error probability in (1) in the particular case when the conditional distribution of given is a multivariate Poisson distribution with mean vector on the order of . The following result determines this error up to first order in the exponent.

Lemma [Abbe and Sandon 2015]

For any with and , we have

(3)

where

(4)

Due to connections with other, well-known measures of divergence (which we do not discuss here), Abbe and Sandon termed the Chernoff-Hellinger divergence.

We do not go over the proof of this statement—which we leave to the reader as a challenging exercise—but we provide some intuition in the univariate case.

Observe that

decays rapidly away from

so we can obtain a good estimate of the sum

by simply estimating the term

Now observe that must satisfy

after some algebra this is equivalent to

Let denote the maximizer in the expression of in~\eqref{eq:D_+}.

By differentiating in , we obtain that satisfies

and so

Thus we see that

from which, after some algebra, we get that

The proof of (3) in the multivariate case follows along the same lines: the single term corresponding to

gives the lower bound. For the upper bound of (3) one has to show that the other terms do not contribute much more.

Characterizing exact recoverability using CH-divergence

Our conclusion is thus that the error exponent in testing multivariate Poisson distributions is given by the explicit quantity in (4).

The discussion above then implies that plays an important role in the threshold for exact recovery.

In particular, it intuitively follows from the above Lemma that a necessary condition for exact recovery should be that

Suppose on the contrary that

for some and .

This implies that the error probability in the testing problem is for some for all vertices in communities and . Since the number of vertices in these communities is linear in , and most of the hypothesis testing problems are approximately independent, one expects there to be no error in the testing problems with probability at most

.

It turns out that this indeed gives the recoverability threshold.

Theorem [Abbe and Sandon 2015]

Let denote the number of communities,

let with denote the community prior,

let ,

and let be a symmetric matrix with no two rows equal.

Exact recovery is solvable in if and only if

(5)

This theorem thus provides an operational meaning to the CH-divergence for the community recovery problem.

Example [Symmetric communities]

Consider again symmetric communities, that is,

for all ,

if ,

and otherwise, with .

Then exact recovery is solvable in if and only if

(6)

We note that in this case is the same as the Hellinger divergence.

Above we have heuristically described why the condition (5) is necessary.

To see why it is sufficient, first note that if (5) holds, then the Lemma tells us that in the hypothesis testing problem between Poisson distributions the error of the MAP estimate is .

Thus if the setting of the thought experiment applies to every vertex, then by looking at the degree profiles of the vertices we can correctly reclassify all vertices, and the probability that we make an error is by a union bound.

However, the setting of the thought experiment does not quite apply. Nonetheless, in this logarithmic degree regime it is possible to partially reconstruct the labels of the vertices, with only vertices being misclassified. The details of this partial reconstruction procedure would require a separate post—in brief, it determines whether two vertices are in the same community or not by looking at how their size neighborhoods interact.

One can then apply two rounds of the degree-profiling step to each vertex, and it can be shown that all vertices are then correctly labelled whp.

## Kernel-based methods for convex bandits, part 3

(This post absolutely requires to have read Part 1 and Part 2.) A key assumption at the end of Part 1 was that, after rescaling space so that the current exponential weights distribution is isotropic, one has

(1)

for some . Effectively this means that the estimated cumulative loss outside of the ball is infinite (recall that is proportional to ). Thus to enforce (1) (at time ) we will actually set the loss estimate to on . The price one pays for this is that the loss estimator is now unbiased only on , which in turn means that we control the cumulative regret with respect to points in only. We believe that in the so-called stochastic setting where the loss sequence is i.i.d. one should be able to prove that the minimizer of the expected loss function remains in at all round (for ) which would imply with the calculations from Part 1 and Part 2 a cumulative regret of order (note: we were not able to prove this and I think it is a great and accessible open problem). However this will certainly not be true in the general as one could imagine an adversary that makes us zoom in on a small portion of space using the first rounds and then move out the optimum very far from this region for the remaining rounds. To solve this issue we introduce a restart condition: essentially if the algorithm believes that the optimum might be outside the region then it restarts (i.e. it plays as if the next round was the first one in a game with time horizon ). We will modify the algorithm so we can ensure that when a restart occurs the algorithm actually had negative regret, and thus in the final regret bound we can ignore everything that happened before the last restart. The definition of the focus region given in (1) will not quite work, and in fact we will construct a region which verifies

Furthermore we will need to take which in turn forces us to take (indeed recall that in Part 1 we showed that the magnitude of the estimated loss is essentially where instead of comes from the above display, and furthermore in Part 2 we explained that with the Gaussian core one needs to take to be times smaller than the predicted value from Part 1) and hence the final regret bound (indeed recall that we got a bound of where the first comes from the fact that we need to take a learning rate times smaller than the optimal learning rate to ensure approximate log-concavity of the exponential weights, and the comes from the relative entropy distance to the optimum at the beginning).

We will use extensively the following result:

Lemma: Let be an isotropic log-concave measure. Then for any such that one has .

Restart condition

The simplest idea to restart goes as follows. Let us consider some (with defined as in (1)). Why is it there? Well there must be some time in the past where we estimated the cumulative regret of to be at least . In particular if this now has a small estimated regret, say smaller than then we can reasonably believe that something weird is going on, for instance the adversary could be trying to move the optimum outside of the current region of focus . Thus our restart condition looks like this: restart if

A key observation (which is the real reason to introduce the above restart condition) is that by convexity of the losses, by the concentration property of Part 2, and by taking the constant to be large enough, we know that the optimum (over all of ) of the “true” cumulative loss is still in at the time when we restart.

Hoping for negative regret

If we catch the adversary’s presumptive attempt to move the optimum out of quickly enough we can hope to get negative regret. Indeed we initially zoomed in on region for a good reason, and thus if we compare ourselves to the point which triggers the restart we have accumulated a lot of negative regret during this zooming procedure (since was performing badly during this time). Mathematically this shows up in the following term which appears in the regret bound calculation, where is the time at which enters the boundary of the focus region,

(2)

Roughly (essentially thanks to the Lemma above) we should expect this quantity to be as small as for , and thus this term divided by (which is then ) could easily compensate the variance term which is . This sounds great, but unfortunately the difference of entropy in (2) does not appear in our current regret bound (because of the telescopic sum of entropies). However it is easy to see that if at time step we had increased the learning rate from to then we would have the term multiplied by in the final regret bound and thus we would only need to have to ensure negative regret (note that compensating the entropy at the beginning is more difficult than compensating the variance term because of our choice of ). Let us make this slightly more formal.

Turning up the learning rate

Let us assume that we update the exponential weights distribution with a time-dependent learning rate as follows: . One can see with the same calculations than in Part 1 that:

In particular if we increase the learning rate at some times by then we have

Using that the normalizing constants are all larger than (this can be proved using the fact that covariance of the exponential weights is at least some ) and assuming that (i.e. ) one gets roughly, with ,

where the second inequality uses that (see Part 2).

We see that by taking we can guarantee negative regret with respect to any whose first time at which it belonged to the boundary of the focus region is also a time at which we increased the learning rate (i.e., one of the times ). Thus we see that we should take if we want to have a regret of order . Recall also that we can afford to update the learning rate only times. Thus the next idea is to update the focus region only when it is necessary. We will see that we can take (and thus , ) while guaranteeing that the focus region satisfies

As we explained at the beginning of this post this will conclude the proof of the regret bound.

Updating the focus region more carefully

We update the focus region only at times such that, once space is rescaled so that is isotropic,

and in this case we set

Somewhat clearly we won’t make more than updates (since after that many updates the focus region is really tiny) so the only thing to verify is that one always has (whether we update or not)

This follows from:

Lemma: Let be a convex body and be the centered unit ball. Suppose that . Then .

Proof: Let us prove the contrapositive and assume that there is a point with . Denote , and consider the sets .

Note that those sets are disjoint. Indeed, the intervals are disjoint, which implies that the projections of the ellipsoids onto the span of are disjoint. So, we have

which concludes the proof.

That’s it folks!

This concludes the informal proof! In the real proof we unfortunately need to deal with the various places where we said “events of probability do not matter”. There is also the discrepancy between approximately log-concave and exactly log-concave measure. Finally doing the concentration argument properly (with the induction) is one more place that add some unwanted (but relatively minor) technical complications.

Another important part which I completely omitted in these lecture notes is the computational complexity of the resulting algorithm. Using known results on sampling from approximately log-concave measures it is fairly easy to sample in time . Checking whether the focus region has to be updated can also be done in poly time. The only real difficulty is checking the restart condition which asks to minimize an approximately convex function on the boundary of a convex set! The trick here is that one can replace ellipses by boxes, and thus we are left with minimizing an approximately convex function on convex sets (which are dimensional). All of this can be found in the paper of course!

## Kernel-based methods for convex bandits, part 2

The goal of this second lecture is to explain how to do the variance calculation we talked about at the end of Part 1 for the case where the exponential weights distribution is non-Gaussian. We will lose here a factor in the regret bound compared to the optimistic calculations from Part 1, and thus by the end of this lecture we could still hope to prove a regret bound of order .

Gaussian core

First let us revisit the introduction of the core. Recall that we are considering a kernel such that is the distribution of for some random variable to be defined. To control the regret we want to have the following inequality for any convex function :

which means that the distribution of the random variable should satisfy

(1)

The core is defined so that (1) is in fact an equality. As we discussed in the previous post the core is a deep mathematical construction, but unfortunately we could not find a way to generalize the Part 1’s variance calculation when the core is non-Gaussian. In what follows we describe a slightly different construction which will allow us to satisfy (1) with being Gaussian. A key observation is that if is convexly dominated by , i.e. for any convex one has , then (1) is satisfied by taking to be the core of :

Thus it suffices to show that for any that we care about one can find a Gaussian “inside” of (in the sense that is convexly dominated by ). Then instead of taking the core of to define the kernel one can take the core of (which we will also refer to as the Gaussian core of ).

Next we show that we can essentially restrict our attention to the case where is log-concave, and then we show how to find a Gaussian inside a log-concave measure.

Approximate log-concavity

Recall that in Part 1 we replaced the variance calculation by simply showing that the loss estimates are bounded. Thus we see by induction and using Hoeffding-Azuma that with probability at least one has

Using an union bound over an -net together with Lipschitzness of (which we didn’t prove but it follows the same lines than boundedness) one has in fact that with high probability (say ) there is a convex function (recall that is a convex function) such that

In particular provided that the above display shows that (whose density is proportional to ) is -approximately log-concave (recall that is said to be -approximately log-concave if there is a log-concave function such that ). To simplify the discussion in these lectures we will in fact assume that is exactly log-concave.

We note that the above concentration argument makes us lose a factor in the regret. Indeed in Part 1 we used to (informally) obtain the regret (or with even more optimistic calculations). We see that now we are forced to take a learning rate which is smaller than this, which in turn multiplies the regret bound by a factor .

Finding a Gaussian inside a log-concave

Let be an isotropic log-concave measure. We will show that a centered Gaussian with covariance is (approximately) convexly dominated by . We note in passing that by going back to the calculations at the end of Part 1 it is easy to see that this factor in the covariance will in turn force us to take to be smaller than what we hoped at the end of Part 1, leading to yet again an extra in the regret bound.

In fact we will show that any centered measure supported on a ball of radius is (exactly) convexly dominated by . This implies the (approximate) Gaussian convex domination we mentioned above since most of the mass of is in such a ball (it is easy to deal with the remaining mass but we won’t worry about it here).

Let us fix some convex function . We want to show that . Since both measures are centered we may add any linear function to without affecting this inequality, so we may legitimately assume that and for all . By scaling we might also assume that the maximum on the centered ball of radius is and thus it is enough to show . By convexity is above the linear function where is the maximizer of on the centered ball of radius . Note also that and thus it is enough to show (recall that ):

where , which is implied by

It only remains to use the fact that an isotropic real log-concave random variable verifies , and thus the above display holds true with .

## Kernel-based methods for bandit convex optimization, part 1

A month ago Ronen Eldan, Yin Tat Lee and myself posted our latest work on bandit convex optimization. I’m quite happy with the result (first polynomial time method with poly(dimension)-regret) but I’m even more excited by the techniques we developed. Next week I will give three 60 minutes lectures at MSR to explain those techniques. I thought the notes for these lectures could be useful to people who are going through the main paper as the informal style of blog posts/lectures allow to gloss over some of the annoying details we had to deal with in the real proof. Each lecture covers essentially one major idea of the paper. Here we go for the notes of the first lecture!

Bandit convex optimization
Let a convex body in . For , the player selects (at random) and simultaneously an adversary selects a convex function . The player observes/suffers the loss . The player’s performance is measured by the regret:

The goal of these notes is to give a “simple” informal proof of a -regret (with high probability).

The full information engine
Most previous works on bandit convex optimization were using Online Gradient Descent as a full information primitive (in the full information setting one observes the complete loss function ). Here we will use continuous exponential weights. Let us recall what this means and the basic regret bound one can obtain. For sake of notation we use the same symbol for a probability measure and for its density with respect to the Lebesgue measure (when it has one). We denote for the usual inner product (i.e. ) and .

Theorem: Let be arbitrary functions from to . Let be some measure on and define by induction

where is a normalization constant and is some fixed learning rate. Then

Note that the quantity should be interpreted as the expected regret of playing at random from compared to playing the fixed distribution . Just as a teaser for the experts reading this, a key point of the argument in the third lecture will be to use the term in the regret bound (usually we simply drop this term as it is negative).

Proof: Observe that

Using the basic inequalities and for any , as well as the fact that one obtains

Rearranging the two above displays we proved

which concludes the proof.

Kernels
The usual bandit argument is to use the bandit feedback to build some unbiased estimator of (i.e. such that ) and then use the full information primitive with the estimated losses instead of the real ones. The previous theorem indicates that the only difficulty is then to control the variance of these estimators, i.e. . This is where the shape assumption on the losses has to be used: the observation of the loss at has to be somehow propagated to nearby points so as to have a low variance estimator. The bottleneck of bandit convex optimization is exactly that it is highly unclear how to leverage the convexity assumption to propagate information to nearby points. Our first idea is that one should not estimate directly, but rather it is enough to estimate a coarse approximation to , where the level of coarseness depends on our level of uncertainty about where lies the optimum of the current cumulative loss. In particular “far” (where distances are measured with respect to the variance of our current exponential weights) from our current believed optimum (which is basically the center of mass of our current exponential weights) a very rough estimation of is probably enough. We found that the best way to realize this idea is via kernels as we now explain.

Let be a kernel (which will depend on the current exponential weights distribution ), which we think of as a linear operator over probability measures through the formula . The adjoint acts on functions: (indeed ). The key point of is that there is a canonical unbiased estimator of it based on the observation of with sampled from some distribution , namely . That’s great, and we will see soon how to control the variance of this estimator, but first let us talk about a more pressing issue: with these estimators one would control the regret as if the adversary was playing the losses , but what we want is to control the regret with respect to real losses . In other words we control terms of the form but what we really care about is something like for some potentially different from (indeed we can play from some which can be different from the exponential weights distribution). A natural guess is to take , in which case we would be satisfied by an inequality of the form .

Generalized Bernoulli convolutions
(What follows is an almost exact copy of Section 1.2.2. in the main paper.) As we just explained above for a given measure we want to find a kernel such that for all convex functions and all points . We note that for any one has

(1)

Leveraging the fact that is convex we see that a natural kernel to consider is such that is the distribution of for some random variable to be defined. Indeed in this case one has

Thus this kernel satisfies the right hand side of (1) if is defined to be equal to , that is satisfies the following distributional identity, where ,

(2)

If (2) holds true we say that is the core of . It is easy to see that the core always exists and is unique by taking where are i.i.d. copies of . Interestingly such random variables have a long history for the special case of a random sign where they are called Bernoulli convolutions (they were introduced by Erdos in a 1939 paper). Our notion of core can thus be viewed as a generalized Bernoulli convolution. We refer the reader to the following very nice a survey on Bernoulli convolutions by Peres, Schlag and Solomyak, and we simply mention that the main objective in this literature is to understand for which values of is the random variable “smooth” (say for instance absolutely continuous with respect to the Lebesgue measure).

Summarizing the discussion so far, we see that by playing at round from , where is the kernel described above and is the continuous exponential weights strategy on the estimated losses one has for any ,

The term in the left hand side is almost exactly the expected regret by taking to be uniform on a small ball around the minimizer of , and in this case the term is of order .

Variance control in the Gaussian case
All that remains to be done is to control the variance term where . More precisely if this quantity is then we obtain a regret of . This variance control will turn out to be more challenging than one might expect and our goal for the rest of this first lecture is to derive some intuition from the case where is a standard Gaussian. In the next lecture we will see how to somehow reduce the general case to the Gaussian case. In the calculations below we will also assume that is compactly supported on the Euclidean ball of radius . Of course this is at odds with the Gaussian assumption, but again this issue will be dealt with in the next lecture. The more tricky part will be to ensure that the exponential weights distribution is indeed truncated outside of a ball of such radius (observe that is assumed to be isotropic, so with respect to the distances in the original space this ball might represent a tiny ball in ). This truncation (and dealing with the issues that result from it) will be the topic of the third lecture (this is where the negative entropic term in the regret bound of exponential weights will turn out to be useful!).
First observe that to bound the variance term it is in fact sufficient to show that is bounded for all in the support of and all in the support of . In fact it is fine if we have this control with probability at least with respect to the draw of from (recall that eventually is the played point, so events with small probability on can intuitively be ignored). Next we need to understand what is when is a standard Gaussian. Observe that, with denoting the core of , one always has . Furthermore it is a straightforward calculation that the core of standard Gaussian is a centered Gaussian with covariance . Thus we obtain:

Finally note that with high probability one has . Ignoring logarithmic factors, and provided that somehow one could take (which is the ball that contains most of the mass of a standard Gaussian so it seems reasonable), we see that for we have a constant variance, which in turn lead to a regret of order . In fact by being more careful in bounding the variance one could hope that is enough (basically in the display above one could do a moment generating function calculation instead of Cauchy-Schwarz to replace the term by ) which in turn would give a regret. This latter result is what we conjecture to be optimal, but we are quite far from being able to prove this!

In the next lecture we will do a little bit of geometry of log-concave measures to show how to reduce the general case to the Gaussian case. In the third and final lecture we will deal with the truncation of the exponential weights distribution (this will force us to significantly modify the algorithm).

## COLT 2016 videos

This is a one-sentence post for the set {blog followers}\{Twitter/Facebook followers} to advertise the COLT 2016 videos which have just been posted!

## Notes on least-squares, part II

As promised at the end of Part I, I will give some intuition for the Bach and Moulines analysis of constant step size SGD for least-squares. Let us recall the setting. Let be a pair of random variables with where . Let be the convex quadratic function defined by

Observe that, with the notation and one has

We assume that (in particular this implies ) and . For instance these assumptions are respectively satisfied with almost surely, and independent of . Recall that constant step-size SGD on is defined by the following iteration (where is a sequence of i.i.d. copies of ), for ,

Our goal is to show that for one has (for a sequence we denote by its average )

Decomposition into a noise-free SGD and a pure noise SGD

With the notation , , and (with the convention ) one can write an iteration of SGD as

Interestingly, since , we have with ,

In other words the convergence analysis decomposes into two terms: which corresponds to a noise-free SGD (it is as if we were running SGD with ) and which corresponds to a pure noise SGD (it is as if we were running SGD with ).

Noise-free SGD

The analysis of the noise-free SGD is the usual drill: let and recall that (recall that in the noise-free case one has ), thus

which directly yields and thus for one gets which finally yields (by convexity of )

Thus from now on we can restrict our attention to the pure noise case, and the goal is to show that in this case one has .

The pure noise case is the difficult part in the proof (this was to be expected, indeed in the SGD analysis 101 one usually cancels the effect of the noise by taking a very small step size). For this case Bach and Moulines (following the footsteps of Polyak and Juditsky [1992]) suggest to first study a “full gradient” method, that is to replace the term by in the SGD iteration. More precisely the “full gradient” analysis would amount to study the sequence defined by (recall that we are in the pure noise case and thus ) and

We expect that will manage to stay pretty close to the optimum since we are doing full gradient steps, and thus it should only suffer the inherent variance of the problem (recall that the statistical lower bound for this problem is ). It is actually easy to prove that this intuition is correct, first note that

(1)

and thus for (which implies )

which implies (the cross terms vanish since is centered, and also recall that )

(2)

Difference between full gradient and SGD

Let us now see how different is the sequence from our real target :

(3)

In words we see that the difference between the two sequences satisfy exactly the same recursion as SGD, except that the noise term is replaced by . This is pretty good news since we expect to be of order : indeed is a full gradient method starting from , so it should stay close to up to the noise term ; again this intuition is easy to make precise since with (X) one sees easily that . In other words while corresponds to SGD with noise (the covariance of this noise is bounded by ), we see that corresponds to SGD with noise (now the covariance of this noise is bounded by ). Thus we see that the new noise term is a factor smaller. In particular we expect to have

(this come from the usual decomposition of the “average regret” for SGD as distance to optimum over –which is here– plus times the average of the norm squared of the noise –which is .)

Not quite there but close

So far we have obtained for the pure noise case:

We fall short of what we were hoping to prove (which is ) because is not close enough to . Morally the above shows that can be viewed as a order approximation to , with a remainder term of order . What about continuing this expansion of as a polynomial in ? Let us see what the next term should look like. First we hope that this term will also satisfy (2) and thus it should correspond to a full gradient method. On the other hand the noise term in this full gradient method should absorb the noise term in (3) so that we can hope that the noise term in the new (3) will be smaller. This leads to:

(4)

and thus (1) rewrites as

In fact there is no reason to stop there, and for any one can define

Denoting for a positive number such that the covariance matrix of (which is the noise term in the “full gradient with noise” corresponding to both and ) is bounded by , one gets with the same arguments as above

and

In particular to conclude it suffices to show that is geometrically decreasing. In fact an easy induction shows that one can take (we already did the base case ).

That’s it for today. In part III I will discuss how to use random projections to speed up computations for least squares in both the large sample regime and in the high-dimensional regime .

## Bandit theory, part II

These are the lecture notes for the second part of my minicourse on bandit theory (see here for Part 1).

The linear bandit problem, Auer [2002]

We will mostly study the following far-reaching extension of the -armed bandit problem.

Known parameters: compact action set , adversary’s action set , number of rounds .

Protocol: For each round , the adversary chooses a loss vector and simultaneously the player chooses based on past observations and receives a loss/observation .

Other models: In the i.i.d. model we assume that there is some underlying such that . In the Bayesian model we assume that we have a prior distribution over the sequence (in this case the expectation in is also over ). Alternatively we could assume a prior over .

Example: Part 1 was about and . Another simple example is path planning: say you have a graph with edges, and at each step one has to pick a path from some source node to a target node. The action set can be represented as a subset of the hypercube . The adversary chooses delays on the edges, and the delay of the chosen path is the sum of the delays on the edges that the path visits (this is indeed a linear loss).

Assumption: unless specified otherwise we assume .

Other feedback model: in the case where one can assume that the loss is observed at every coordinate where . This is the so-called semi-bandit feedback.

Thompson Sampling for linear bandit after RVR14

Assume . Recall from Part 1 that TS satisfies

where and .

Writing , , and we want to show that

Using the eigenvalue formula for the trace and the Frobenius norm one can see that . Moreover the rank of is at most since where (the row of is and for it is ).

Let us make some observations.

1. TS satisfies . To appreciate the improvement recall that without the linear structure one would get a regret of order and that can be exponential in the dimension (think of the path planning example).
2. Provided that one can efficiently sample from the posterior on (or on ), TS just requires at each step one linear optimization over .
3. TS regret bound is optimal in the following sense. W.l.og. one can assume and thus TS satisfies for any action set. Furthermore one can show that there exists an action set and a prior such that for any strategy one has , see Dani, Hayes and Kakade [2008], Rusmevichientong and Tsitsiklis [2010], and Audibert, Bubeck and Lugosi [2011, 2014].

Recall from Part 1 that exponential weights satisfies for any such that and ,

DHK08 proposed the following (beautiful) unbiased estimator for the linear case:

Again, amazingly, the variance is automatically controlled:

Up to the issue that can take negative values this suggests the “optimal” regret bound.

1. The non-negativity issue of is a manifestation of the need for an added exploration. DHK08 used a suboptimal exploration which led to an additional in the regret. This was later improved in Bubeck, Cesa-Bianchi, and Kakade [2012] with an exploration based on the John’s ellipsoid (smallest ellipsoid containing ). You can check this video for some more details on this.
2. Sampling the exp. weights is usually computationally difficult, see Cesa-Bianchi and Lugosi [2009] for some exceptions.
3. Abernethy, Hazan and Rakhlin [2008] proposed an alternative (beautiful) strategy based on mirror descent. The key idea is to use a -self-concordant barrier for as a mirror map and to sample points uniformly in Dikin ellipses. This method’s regret is suboptimal by a factor and the computational efficiency depends on the barrier being used.
4. Bubeck and Eldan [2014]‘s entropic barrier allows for a much more information-efficient sampling than AHR08. This gives another strategy with optimal regret which is efficient when is convex (and one can do linear optimization on ). You can check this video for some more on the entropic barier.

Adversarial combinatorial bandit after Audibert, Bubeck and Lugosi [2011, 2014]

Combinatorial setting: , , .

1. Full information case goes back to the end of the 90’s (Warmuth and co-authors), semi-bandit and bandit were introduced in Audibert, Bubeck and Lugosi [2011] (following several papers that studied specific sets ).
2. This is a natural setting to study FPL-type (Follow the Perturbed Leader) strategies, see e.g. Kalai and Vempala [2004] and more recently Devroye, Lugosi and Neu [2013].
3. ABL11: Exponential weights is provably suboptimal in this setting! This is in sharp contrast with the case where .
4. Optimal regret in the semi-bandit case is and it can be achieved with mirror descent and the natural unbiased estimator for the semi-bandit situation.
5. For the bandit case the bound for exponential weights from the previous slides gives (you should read this as “range of the loss times square root dimension times time times logsize of the set). However the lower bound from ABL14 is , which is conjectured to be tight.

Preliminaries for the i.i.d. case: a primer on least squares

Assume where is an i.i.d. sequence of centered and sub-Gaussian real-valued random variables. The (regularized) least squares estimator for based on is, with and :

Observe that we can also write where so that

A basic martingale argument (see e.g., Abbasi-Yadkori, Pal and Szepesvari [2011]) shows that w.p. , ,

Note that (w.l.o.g. we assumed ).

i.i.d. linear bandit after DHK08, RT10, AYPS11

Let , and . We showed that w.p. one has for all .

The appropriate generalization of UCB is to select: (this optimization is NP-hard in general, more on that next slide). Then one has on the high-probability event:

To control the sum of squares we observe that:

so that (assuming )

Putting things together we see that the regret is .

What’s the point of i.i.d. linear bandit?

So far we did not get any real benefit from the i.i.d. assumption (the regret guarantee we obtained is the same as for the adversarial model). To me the key benefit is in the simplicity of the i.i.d. algorithm which makes it easy to incorporate further assumptions.

1. Sparsity of : instead of regularization with -norm to define one could regularize with -norm, see e.g., Johnson, Sivakumar and Banerjee [2016] (see also Carpentier and Munos [2012] and Abbasi-Yadkori, Pal and Szepesvari [2012].
2. Computational constraint: instead of optimizing over to define one could optimize over an -ball containing (this would cost an extra in the regret bound).
3. Generalized linear model: for some known increasing , see Filippi, Cappe, Garivier and Szepesvari [2011].
4. -regime: if is finite (note that a polytope is effectively finite for us) one can get regret:

Some non-linear bandit problems

1. Lipschitz bandit: Kleinberg, Slivkins and Upfal [2008, 2016], Bubeck, Munos, Stoltz and Szepesvari [2008, 2011], Magureanu, Combes and Proutiere [2014]
2. Gaussian process bandit: Srinivas, Krause, Kakade and Seeger [2010]
3. Convex bandit: see the videos by myself and Ronen Eldan here and our arxiv paper.

Contextual bandit

We now make the game-changing assumption that at the beginning of each round a {\em context} is revealed to the player. The ideal notion of regret is now:

Sometimes it makes sense to restrict the mapping from contexts to actions, so that the infimum is taken over some {\em policy set} .

As far as I can tell the contextual bandit problem is an infinite playground and there is no canonical solution (or at least not yet!). Thankfully all we have learned so far can give useful guidance in this challenging problem.

Linear model after embedding

A natural assumption in several application domains is to suppose linearity in the loss after a correct embedding. Say we know mappings such that for some unknown (or in the adversarial case that ).

This is nothing but a linear bandit problem where the action set is changing over time. All the strategies we described are robust to this modification and thus in this case one can get a regret of (and for the stochastic case one can get efficiently ).

A much more challenging case is when the correct embedding is only known to belong to some class . Without further assumptions on we are basically back to the general model. Also note that a natural impulse is to run “bandits on top of bandits”, that is first select some and then select based on the assumption that is correct. We won’t get into this here, but let us investigate a related idea.

Exp4, Auer, Cesa-Bianchi, Freund and Schapire [2001]

One can play exponential weights on the set of policies with the following unbiased estimator (obvious notation: , , and )

Easy exercise: (indeed the relative entropy term is smaller than while the variance term is exactly ).

The only issue of this strategy is that the computationally complexity is linear in the policy space, which might be huge. A year and half ago a major paper by Agarwal, Hsu, Kale, Langford, Li and Schapire was posted, with a strategy obtaining the same regret as Exp4 (in the i.i.d. model) but which is also computationally efficient with an oracle for the offline problem (i.e., ). Unfortunately the algorithm is not simple enough yet to be included in these slides.

The statistician perspective, after Goldenshluger and Zeevi [2009, 2011], Perchet and Rigollet [2011]

Let , , i.i.d. from some absolutely continuous w.r.t. Lebesgue. The reward for playing arm under context is drawn from some distribution on with mean function which is assumed to be -Holder smooth. Let be the “gap” function.

A key parameter is the proportion of contexts with a small gap. The margin assumption is that for some , one has

One can achieve a regret of order , which is optimal at least in the dependency on . It can be achieved by running Successive Elimination on an adaptively refined partition of the space, see Perchet and Rigollet [2011] for the details.

The online multi-class classification perspective after Kakade, Shalev-Shwartz, and Tewari [2008]

Here the loss is assumed to be of the following very simple form: . In other words using the context one has to predict the best action (which can be interpreted as a class) .

KSST08 introduces the banditron, a bandit version of the multi-class perceptron for this problem. While with full information the online multi-class perceptron can be shown to satisfy a “regret” bound on of order , the banditron attains only a regret of order . See also Chapter 4 in Bubeck and Cesa-Bianchi [2012] for more on this.

1. The optimal regret for the linear bandit problem is . In the Bayesian context Thompson Sampling achieves this bound. In the i.i.d. case one can use an algorithm based on the optimism in face of uncertainty together with concentration properties of the least squares estimator.
2. The i.i.d. algorithm can easily be modified to be computationally efficient, or to deal with sparsity in the unknown vector .
3. Extensions/variants: semi-bandit model, non-linear bandit (Lipschitz, Gaussian process, convex).
4. Contextual bandit is still a very active subfield of bandit theory.
5. Many important things were omitted. Example: knapsack bandit, see Badanidiyuru, Kleinberg and Slivkins [2013].

Some open problems we discussed

2. Guha and Munagala [2014] conjecture: for product priors, TS is a 2-approximation to the optimal Bayesian strategy for the objective of minimizing the number of pulls on suboptimal arms.
3. Find a “simple” strategy achieving the Bubeck and Slivkins [2012] best of both worlds result (see Seldin and Slivkins [2014] for some partial progress on this question).
4. For the combinatorial bandit problem, find a strategy with regret at most (current best is ).
5. Is there a computationally efficient strategy for i.i.d. linear bandit with optimal gap-free regret and with gap-based regret?
6. Is there a natural framework to think about “bandits on top of bandits” (while keeping -regret)?
Posted in Optimization, Probability theory | 4 Comments

## Bandit theory, part I

This week I’m giving two 90 minutes lectures on bandit theory at MLSS Cadiz. Despite my 2012 survey with Nicolo I thought it would be a good idea to post my lectures notes here. Indeed while much of the material is similar, the style of a mini-course is quite different from the style of a survey. Also, bandit theory has surprisingly progressed since 2012 and many things can now be explained better. Finally in the survey we completely omitted the Bayesian model as we thought that we didn’t have much to add on this topic compared to existing sources (such as the 2011 book by Gittins, Glazebrook, Weber). For a mini-course this concern is irrelevant so I quickly discuss the famous Gittins index and its proof of optimality.

i.i.d. multi-armed bandit, Robbins [1952]

Known parameters: number of arms and (possibly) number of rounds .

Unknown parameters: probability distributions on with mean (notation: ).

Protocol: For each round , the player chooses based on past observations and receives a reward/observation (independently from the past).

Performance measure: The cumulative regret is the difference between the player’s accumulated reward and the maximum the player could have obtained had she known all the parameters,

This problem models the fundamental tension between exploration and exploitation (one wants to pick arms that performed well in the past, yet one needs to make sure that no good option has been missed). Almost every week new applications are found that fit this simple framework and I’m sure you already have some in mind (the most popular one being ad placement on the internet).

i.i.d. multi-armed bandit: fundamental limitations

How small can we expect to be? Consider the -armed case where and where is unknown. Recall from Probability 101 (or perhaps 102) that with expected observations from the second arm there is a probability at least to make the wrong guess on the value of . Now let be the expected number of pulls of arm up to time when . One has

We refer to Bubeck, Perchet and Rigollet [2013] for the details. The important message is that for fixed the lower bound is , while for the worse (which is of order ) it is . In the -armed case this worst-case lower bound becomes (see Auer, Cesa-Bianchi, Freund and Schapire [1995]). The -lower bound is slightly “harder” to generalize to the -armed case (as far as I know there is no known finite-time lower bound of this type), but thankfully it was already all done 30 years ago. First some notation: let and the number of pulls of arm up to time . Note that one has . For let

Theorem [Lai and Robbins [1985]]

Consider a strategy s.t. , we have if . Then for any Bernoulli distributions,

Note that so up to a variance-like term the Lai and Robbins lower bound is . This lower bound holds more generally than just for Bernoulli distributions, see for example Burnetas and Katehakis [1996].

i.i.d. multi-armed bandit: fundamental strategy

Hoeffding’s inequality teaches us that with probability at least , ,

The UCB (Upper Confidence Bound) strategy (Lai and Robbins [1985], Agarwal [1995], Auer, Cesa-Bianchi and Fischer [2002]) is:

The regret analysis is straightforward: on a probability event one has

so that and in fact

i.i.d. multi-armed bandit: going further

• The numerical constant in the UCB regret bound can be replaced by (which is the best one can hope for), and more importantly by slightly modifying the derivation of the UCB one can obtain the Lai and Robbins variance-like term (that is replacing by ): see Cappe, Garivier, Maillard, Munos and Stoltz [2013].
•  In many applications one is merely interested in finding the best arm (instead of maximizing cumulative reward): this is the best arm identification problem. For the fundamental strategies see Even-Dar, Mannor and Mansour [2006] for the fixed-confidence setting (see also Jamieson and Nowak [2014] for a recent short survey) and Audibert, Bubeck and Munos [2010] for the fixed budget setting. Key takeaway: one needs of order rounds to find the best arm.
• The UCB analysis extends to sub-Gaussian reward distributions. For heavy-tailed distributions, say with moment for some , one can get a regret that scales with (instead of ) by using a robust mean estimator, see Bubeck, Cesa-Bianchi and Lugosi [2012].

Adversarial multi-armed bandit, Auer, Cesa-Bianchi, Freund and Schapire [1995, 2001]

For , the player chooses based on previous observations, and simultaneously an adversary chooses a loss vector . The player’s loss/observation is . The regret and pseudo-regret are defined as:

Obviously and there is equality in the oblivious case ( adversary’s choices are independent of the player’s choices). The case where is an i.i.d. sequence corresponds to the i.i.d. model we just studied. In particular we already know that is a lower bound on the attainable pseudo-regret.

The exponential weights strategy for the full information case where is observed at the end of round is defined by: play at random from where

In five lines one can show with and a well-chosen learning rate (recall that ):

For the bandit case we replace by in the exponential weights strategy, where

The resulting strategy is called Exp3. The key property of is that it is an unbiased estimator of :

Furthermore with the analysis described above one gets

It only remains to control the variance term, and quite amazingly this is straightforward:

Thus with one gets .

• With the modified loss estimate one can prove high probability bounds on , and by integrating the deviations one can show .
• The extraneous logarithmic factor in the pseudo-regret upper can be removed, see Audibert and Bubeck [2009]. Conjecture: one cannot remove the log factor for the expected regret, that is for any strategy there exists an adaptive adversary such that .
• can be replaced by various measure of “variance” in the loss sequence, see e.g., Hazan and Kale [2009].
• There exist strategies which guarantee simultaneously in the adversarial model and in the i.i.d. model, see Bubeck and Slivkins [2012].
• Many interesting variants: graph feedback structure of Mannor and Shamir [2011] (there is a graph on the set of arms, and when an arm is played one observes the loss for all its neighbors), regret with respect to best sequence of actions with at most switches, switching cost (interestingly in this case the best regret is , see Dekel, Ding, Koren and Peres [2013]), and much more!

Bayesian multi-armed bandit, Thompson [1933]

Here we assume a set of “models” and prior distribution over . The Bayesian regret is defined as

where simply denotes the regret for the i.i.d. model when the underlying reward distributions are . In principle the strategy minimizing the Bayesian regret can be computed by dynamic programming on the potentially huge state space . The celebrated Gittins index theorem gives sufficient condition to dramatically reduce the computational complexity of implementing the optimal Bayesian strategy under a strong product assumption on . Notation: denotes the posterior distribution on at time .

Theorem [Gittins [1979]]

Consider the product and -discounted case: , , , and furthermore one is interested in maximizing . The optimal Bayesian strategy is to pick at time the arm maximizing the Gittins index:

where the expectation is over drawn from with , and the supremum is taken over all stopping times .

Note that the stopping time in the Gittins index definition gives the optimal strategy for a 2-armed game, where one arm’s reward distribution is while the other arm reward’s distribution is with as a prior for .

Proof: The following exquisite proof was discovered by Weber [1992]. Let

be the Gittins index of arm at time , which we interpret as the maximum charge one is willing to pay to play arm given the current information. The prevailing charge is defined as (i.e. whenever the prevailing charge is too high we just drop it to the fair level). We now make three simple observations which together conclude the proof:

• The discounted sum of prevailing charge for played arms is an upper bound (in expectation) on the discounted sum of rewards. Indeed the times at which the prevailing charge are updated are stopping times, and so between two such times the expected sum of discounted reward is smaller than the discounted sum of the fair charge at time which is equal to the prevailing charge at any time in .
• Since the prevailing charge is nonincreasing, the discounted sum of prevailing charge is maximized if we always pick the arm with maximum prevailing charge. Also note that the sequence of prevailing charge does not depend on the algorithm.
• Gittins index does exactly 2. (since we stop playing an arm only at times at which the prevailing charge is updated) and in this case 1. is an equality. Q.E.D.

For much more (implementation for exponential families, interpretation as a multitoken Markov game, …) see Dumitriu, Tetali and Winkler [2003], Gittins, Glazebrook, Weber [2011], Kaufmann [2014].

Bayesian multi-armed bandit, Thompson Sampling (TS)

In machine learning we want (i) strategies that can deal with complicated priors, and (ii) guarantees for misspecified priors. This is why we have to go beyond the Gittins index theory.

In his 1933 paper Thompson proposed the following strategy: sample and play .

Theoretical guarantees for this highly practical strategy have long remained elusive. Recently Agrawal and Goyal [2012] and Kaufmann, Korda and Munos [2012] proved that TS with Bernoulli reward distributions and uniform prior on the parameters achieves (note that this is the frequentist regret!). We also note that Liu and Li [2015] takes some steps in analyzing the effect of misspecification for TS.

Let me also mention a beautiful conjecture of Guha and Munagala [2014]: for product priors, TS is a 2-approximation to the optimal Bayesian strategy for the objective of minimizing the number of pulls on suboptimal arms.

Bayesian multi-armed bandit, Russo and Van Roy [2014] information ratio analysis

Assume a prior in the adversarial model, that is a prior over , and let denote the posterior distribution (given ). We introduce

The key observation is that (recall that )

Indeed, equipped with Pinsker’s inequality and basic information theory concepts one has (we denote for the mutual information conditionally on everything up to time , also denotes the law of conditionally on everything up to time ):

Thus which gives the claim thanks to a telescopic sum. We will use this key observation as follows (we give a sequence of implications leading to a regret bound so that all that is left to do is to check that the first statement in this sequence is true for TS):

Thus writing and we have

For TS the following shows that one can take :

Thus TS always satisfies . Side note: by the minimax theorem this implies the existence of a strategy for the oblivious adversarial model with regret (of course we already proved that such a strategy exist, in fact we even constructed one via exponential weights, but the point is that the proof here does not require any “miracle” –yes exponential weights are kind of a miracle, especially when you consider how the variance of the unbiased estimator gets automatically controlled).

Summary of basic results

• In the i.i.d. model UCB attains a regret of and by Lai and Robbins’ lower bound this is optimal (up to a multiplicative variance-like term).
• In the adversarial model Exp3 attains a regret of and this is optimal up to the logarithmic term.
• In the Bayesian model, Gittins index gives an optimal strategy for the case of product priors. For general priors Thompson Sampling is a more flexible strategy. Its Bayesian regret is controlled by the entropy of the optimal decision. Moreover TS with an uninformative prior has frequentist guarantees comparable to UCB.
Posted in Optimization, Probability theory | 6 Comments