On Measure Concentration of Random Maximum A-Posteriori
Perturbations
Francesco Orabona∗
Toyota Technological Institute at Chicago, 6045 S. Kenwood Ave, Chicago, IL 60637
Tamir Hazan∗
Dept. of Computer Science, University of Haifa, 31905 Haifa, Israel

orabona@ttic.edu
tamir@cs.haifa.ac.il

Anand D. Sarwate∗
asarwate@ece.rutgers.edu
Rutgers University, Dept. of Electrical and Computer Engineering, 94 Brett Road, Piscataway, NJ 08854
Tommi S. Jaakkola
MIT CSAIL, Stata Center, Bldg 32-G470, 77 Mass Ave. Cambridge, MA 02139

Abstract
The maximum a-posteriori (MAP) perturbation framework has emerged as a usefulapproach for inference and learning in highdimensional complex models. By maximizing a randomly perturbed potential function,
MAP perturbations generate unbiased samples from the Gibbs distribution. Unfortunately, the computational cost of generating
so many high-dimensional random variables
can be prohibitive. More efficient algorithms
use sequential sampling strategies based on
the expected value of low dimensional MAP
perturbations. This paper develops new measure concentration inequalities that boundthe number of samples needed to estimate
such expected values. Applying the general
result to MAP perturbations can yield a more
efficient algorithm to approximate samplingfrom the Gibbs distribution. The measureconcentration result is of general interest andmay be applicable to other areas involving
Monte Carlo estimation of expectations.

1. Introduction
Modern machine learning tasks in computer vision,
natural language processing, and computational biology involve inference in high-dimensional com∗

FO, TH and ADS contributed equally to this paper.
Proceedings of the 31 st International Conference on Machine Learning, Copyright 2014 by the author(s).

tommi@csail.mit.edu

plex models. Examples include scene understanding(Felzenszwalb & Zabih, 2011), parsing (Koo et al.,2010), and protein design (Sontag et al., 2008). In
these settings inference involves finding likely structures that fit the data: objects in images, parsers
in sentences, or molecular configurations in proteins.
Each structure corresponds to an assignment of values to random variables and the likelihood of an assignment is based on defining potential functions that
account for interactions over these variables. Given
the observed data, these likelihoods yield a posterior
probability distribution on assignments known as theGibbs distribution. Contemporary posterior probabilities that are used in machine learning incorporate local
potential functions on the variables of the model thatare derived from the data (high signal) as well as higher
order potential functions that account for interactions
between the model variables and derived from domainspecific knowledge (high coupling). The resulting posterior probability landscape is often “ragged,” and insuch landscapes Markov chain Monte Carlo (MCMC)
approaches to sampling from the Gibbs distribution
may become prohibitively expensive. By contrast,
when no data terms (local potential functions) exist,
MCMC approaches can be quite successful (e.g., Jerrum et al. (2004); Huber (2003)).
An alternative to sampling from the Gibbs distribution is to look for the maximum a posteriori probability (MAP) structure. Substantial effort has gone
into developing algorithms for recovering MAP assignments by exploiting domain-specific structural restrictions such as super-modularity (Kolmogorov, 2006) orby linear programming relaxations such as cutting-Measure concentration of random MAP perturbations

planes (Sontag et al., 2008; Werner, 2008). However, in many contemporary applications, the complex potential functions on a large number of variables yield several likely structures. We want to findthese “highly probable” assignments as well, and unfortunately MAP inference returns only a single assignment.

2. Problem statement

Recent work leverages the current efficiency of MAP
solvers to build samplers for the Gibbs distribution,
thereby avoiding the computational burden of MCMC
methods. These works calculate the MAP structure of a randomly perturbed potential function. Suchan approach effectively ignores the raggedness of thelandscape that hinders MCMC. Papandreou & Yuille(2011) and Tarlow et al. (2012) have shown that randomly perturbing the potential of each structure withan independent random variable that follows the Gumbel distribution and finding the MAP assignment of
the perturbed potential function provides an unbiased
sample from the Gibbs distribution. Unfortunately the
total number of structures, and consequently the total number of random perturbations, is exponential in
the structure’s dimension. Alternatively, Hazan et al.
(2013b) use expectation bounds on the partition function (Hazan & Jaakkola, 2012) to build a sampler for
Gibbs distribution using MAP solvers on low dimensional perturbations; the complexity is linear in thedimension of the structures.

Statistical inference problems involve reasoning about
the states of discrete variables whose configurations(assignments of values) specify the discrete structuresof interest. Suppose that our model has n variables
x = (x1 , x2 , . . . , xn ) where each xi taking values in a
discrete set Xi . Let X = X1 × X2 × · · · × Xn so thatx ∈ X . Let Dom(θ) ⊆ X be a subset of possible configurations and θ : X → R be a potential function thatgives a score to an assignment or structure x, whereθ(x) = −∞ for x ∈/ Dom(θ). The potential function
induces a probability distribution on configurations x
via the Gibbs distribution:∆ 1(1)
p(x) = exp(θ(x)),
Z
X∆
Z=
exp(θ(x)).
(2)

The low dimensional samplers require calculating expectations of the value of the MAP solution after perturbing the posterior distribution. In this paper westudy the distribution of this perturbed MAP solution. In particular, we prove new measure concentration inequalities that show the expected perturbed
MAP value can be estimated with high probability using only a few random samples. This is an important
ingredient to construct an alternative to MCMC in thedata-knowledge domain that relies on MAP solvers.
The key technical challenge comes from the fact thatthe perturbations are Gumbel random variables, whichhave support on the entire real line. Thus, standard
approaches for bounded random variables, such as McDiarmid’s inequality, do not apply. Instead, we derivea new Poincaré inequality for the Gumbel distribution,
as well as a modified logarithmic Sobolev inequality
using the approach suggested by Bobkov & Ledoux(1997); Ledoux (2001). These results, which are ofindependent interest, guarantee that the deviation between the sample mean of random MAP perturbations
and the expectation has an exponential decay.

Notation: Boldface will denote tuples or vectors
and calligraphic script sets.
For a tuple x =(x1 , x2 , . . . , xn ), let xj:k = (xj , xj+1 , . . . , xk ).
2.1. The MAP perturbation frameworkx∈X

The normalization constant Z is called the partition
function. Sampling from (1) is often difficult because
the sum in (2) involves an exponentially large numberof terms (equal to the number of discrete structures).
In many cases, computing the partition function is in
the complexity class #P (e.g., Valiant (1979)).
Finding the most likely assignment of values to variables is easier. As the Gibbs distribution is typicallyconstructed given observed data, we call this the maximum a-posteriori (MAP) prediction. Maximizing (1):x̂MAP = argmax θ(x).

(3)

x∈X

There are many good optimization algorithms for solving (3) in cases of practical interest. Although MAP
prediction is still NP-hard in general, it is often simpler
than sampling from the Gibbs distribution.
Due to modeling inaccuracies, there are often several
meaningful structures x whose scores θ(x) are close toθ(x̂MAP ), and we would like to recover those as well. As
an alternative to MCMC methods for sampling fromthe Gibbs distribution in (1), we can draw samples
by perturbing the potential function and solving theresulting MAP problem. The MAP perturbation approach adds a random function γ : X → R to thepotential function in (1) and solves the resulting MAP
problem:x̂R−MAP = argmax {θ(x) + γ(x)} .
x∈X

(4)

Measure concentration of random MAP perturbations

The random function γ(·) associates a random variable to each x ∈ X . The simplest approach to designing a perturbation function is to associate an independent and identically distributed (i.i.d.) randomvariable γ(x) for each x ∈ X . We can find the distribution of the randomized MAP predictor in (4) when{γ(x) : x ∈ X } are i.i.d.; in particular, suppose eachγ(x) is a Gumbel random variable with zero mean,variance π 2 /6, and cumulative distribution function

Algorithm 1 Sampling with low-dimensional random MAP perturbations from the Gibbs distribution(Hazan et al., 2013b)
Iterate over j = 1, ..., n, while keeping fixed x1:(j−1)G(y) = exp(− exp(−(y + c))),

3. Sample an element in Xj ∪ {r} according to pj (·).
If r is sampled then reject and restart with j = 1.
Otherwise, fix the sampled element xj and continue the iterations(5)

where c ≈ 0.5772 is the Euler-Mascheroni constant.
The following result characterizes the distribution of
the randomized predictor x̂R−MAP in (4).
Theorem 1. (Gumbel & Lieblein, 1954) Let Γ ={γ(x) : x ∈ X } be a collection of i.i.d. Gumbel randomvariables whose distribution is given by (5). Then
exp(θ(x̂)), (6)PΓ x̂ = argmax {θ(x) + γ(x)} =
Z
x∈X


EΓ max {θ(x) + γ(x)} = log Z,x∈XVarΓ max {θ(x) + γ(x)} = π 2 /6.
x∈X

The max-stability of the Gumbel distribution provides
a straightforward approach to generate unbiased samples from the Gibbs distribution – simply generate theperturbations in Γ and solve the problem in (4). These
solution may also be used to approximate the partition function in (2), as random samples concentratearound their expectation according to their variance.
F (Γ) = [maxx∈X {θ(x) + γ(x)}] then

1. For each xj ∈ Xj , set pj (xj ) =Vj is given by (8)P
2. Set pj (r) = 1 − xj ∈Xj p(xj )exp(EΓ [Vj+1 ])exp(EΓ [Vj ]) , where

Output: x = (x1 , ..., xn )then use these upper bounds in an iterative algorithm
that samples from the Gibbs distribution using low dimensional random MAP perturbations. This gives a
method which has complexity linear in n.
In the following, instead of the |X | independent random variables in (4), we define the random function
γ(x) in (4) as the sum of independent random variables for each coordinate xi of x:γ(x) =nX

γi (xi ).

i=1

Pn
This function involves generating
i=1 |Xi | randomvariables for each i and xi ∈ Xi . LetΓ=n[{γi (xi ) : xi ∈ Xi }i=1

hi Var F (Γ).
PΓ F (Γ) − E[F (Γ)] ≥  ≤2(7)

However, because Γ contains |X | i.i.d. random variables, this approach to inference has complexity whichis exponential in n.
2.2. Sampling from the Gibbs distribution
using low dimensional perturbations
Sampling from the Gibbs distribution is inherently tiedto estimating the partition function in (2). If we could
compute Z exactly, then wePcould sample x1 withprobability proportional tox2 ,...,xn exp(θ(x)), andfor each subsequent dimensioni,sample xi with probP
ability proportional to xi+1 ,...,xn exp(θ(x)), yieldinga Gibbs sampler. However, this involves computing
the partition function (2), which is hard. Instead,
Hazan et al. (2013b) use the representation in (6) toderive a family of self-reducible upper bounds on Z andP
be a collection of i |Xi | i.i.d. Gumbel random variables with distribution (5). The sampling algorithm in
Algorithm 1 uses these random perturbations to draw
unbiased samples from the Gibbs distribution. For a
fixed x1:(j−1) = (x1 , . . . , xj−1 ), define

Vj = max

xj:n 

θ(x) +

n
X
i=j



γi (xi ) .


(8)The sampler proceeds sequentially – for each j it constructs a distribution pj (·) on Xj ∪ {r}, where r indicates a “restart” and attempts to draw an assignment
for xj . If it draws r then it starts over again fromj = 1, and if it draws an element in Xj it fixes xj tothat element and proceeds to j + 1.
Implementing Algorithm 1 requires estimating the expectations EΓ [Vj ] in (8). In this paper we show how toMeasure concentration of random MAP perturbations

estimate EΓ [Vj ] and bound the error with high probability by taking the sample mean of M i.i.d. copies
of Vj . Specifically, we show that the estimation error
decays exponentially with M by proving measure concentration via a modified logarithmic Sobolev inequality for the product of Gumbel random variables. To
do so we derive a more general result – a Poincaré inequality for log-concave distributions that may not be
log-strongly concave, i.e., for which the second derivative of the exponent is not bounded away from zero.
2.3. Measure concentration
We can think of the maximum value of the perturbed
MAP problem as a function of the associated perturbation variables Γ = {γi (xi ) : i ∈ [n], xi ∈ Xi }. There∆
are m = |X1 | + |X2 | + · · · + |Xn | i.i.d. random variables in Γ. For practical purposes, e.g., to estimate
the quality of the sampling algorithm in Algorithm 1,
it is important to evaluate the deviation of its sampled mean from its expectation. For notational simplicity we would only describe the deviation of the
maximum value of the perturbed MAP from its expectation, namely
F (Γ) = V1 − E [V1 ] .

(9)RSince the expectation is a linear function, E [F ] =F (Γ)dµ(Γ) = 0 for any measure µ on Γ. The Chebyshev’s inequality in (7) shows that the deviation of
F (Γ) is dominated by its variance. Although the variance of a Gumbel random variable is π 2 /6, the variance of low dimensional MAP perturbations does nothave an analytic form. However, we P
may bound it asnfollows: Var[F (Γ)] ≤ (maxx {θ(x) + i=1 γi (xi )})2 ≤2
2
maxx {θ(x) } + nπ /6. However, this bound on thevariance is loose and does not reveal the concentrationof measure phenomena of MAP perturbations.
To account for the offsets θ(x) seamlessly, it is natural
to consider measure concentration results that rely on
the variation F (Γ). For example, the random function
F (Γ) is a Lipschitz functions, and thus it is concentrated around its mean whenever the random variablesin Γ are sampled i.i.d from a (sub-)Gaussian distribution (Pisier, 1986; Ledoux & Talagrand, 1991). Unfortunately, such results do not hold for the Gumbel
distribution, for which the density function decays on
the positive reals R+ more slowly than the Gaussian
distribution (see Fig. 1). An alternative is to apply
measure concentration for Lipschitz random functionsof the Laplace distribution (cf. Ledoux (2001)), since
the Laplace distribution and the Gumbel distribution
decay similarly on the positive real numbers. However, representing F (Γ) over Gumbel random variables

Figure 1. Comparing the decay of Gaussian, Gumbel and
Laplace random variables. The decay of the Gaussian random variable is significantly faster and its moments Λ(λ)
always exist. The moments of the Gumbel and Laplacerandom variables do not always exist (e.g., Λ(1)).

Γ using the logarithm of an exponential random variables Γ̂ results in a compound function over exponential random variables F (− log Γ̂) that is no longer Lipschitz.
Although many measure concentration results (such as
McDiarmid’s inequality) use bounds on the variationof F (Γ), MAP perturbations are unbounded, so we derive our result using a different approach. We boundthe deviation of F (Γ) via its moment generating function∆

Λ(λ) = E [exp(λF )] .

(10)

To wit, for every λ > 0,
P (F (γ) ≥ r) ≤ Λ(λ)/ exp(−λr).
More specifically, we construct a differential bound on
the λ−scaled cumulant generating function:∆

H(λ) =

1log Λ(λ).
λ

(11)
0

(0)
First note that that by L’Hôpital’s rule H(0) = ΛΛ(0)=RnF dµ = 0, so we may represent H(λ) by integrating
Rλits derivative: H(λ) = 0 H 0 (λ̂)dλ̂. Thus to boundthe moment generating function it suffices to boundH 0 (λ) ≤ α(λ) for some function α(λ). A direct computation of H 0 (λ) translates this bound toλΛ0 (λ) − Λ(λ) log Λ(λ) ≤ λ2 Λ(λ)α(λ).

(12)

The left side of (12) turns out to be the so-called
functional entropy (Ledoux, 2001) of the function h =exp(λF ) with respect to a measure µ:
Z

Z
Z
∆
Entµ (h) = h log hdµ −hdµ log hdµ.

Measure concentration of random MAP perturbations

Unlike McDiarmid’s inequality, this approach provides
measure concentration for unbounded functions suchthose arising from MAP perturbations.
Log-Sobolev inequalities upper-bound the entropy
2Entµ (h) in terms of an integral involving k∇F k . They
are appealing to derive measure concentration results
in product spaces, i.e., for functions of subsets of variables Γ, because it is sufficient to prove a log-Sobolev
inequality on a single variable function f . Given sucha scalar result, the additivity property of the entropy(e.g., (Boucheron et al., 2004)) extends the inequality to functions F of many variables. In this work wederive a log-Sobolev inequality for the Gumbel distribution, by bounding the variance of a function by its
derivative:
2
Z
Z
Z
∆
f dµ ≤ C |f 0 |2 dµ.
Varµ (f ) = f 2 dµ −(13)This is called a Poincaré inequality, proven originallyfor the Gaussian case. We prove such an inequality for
the Gumbel distribution, which then implies the logSobolev inequality and hence measure concentration.
We then apply the result to the MAP perturbation
framework.
2.4. Related work
We are interested in efficient sampling from the Gibbs
distribution in (1) when n is large and the model iscomplex due to the amount of data and the domainspecific modeling. MCMC approaches to sampling(cf.
Koller & Friedman (2009)) may be computationally intractable in such ragged probability landscapes. MAP
perturbations use efficient MAP solvers as black box,
but the statistical properties of the solutions, beyond
Theorem 1, are still being studied. Papandreou &Yuille (2011) consider probability models that are defined by the maximal argument of randomly perturbed
potential function, while Tarlow et al. (2012) considers sampling techniques for such models. Keshet et al.
(2011) and Hazan et al. (2013a) study the generalization bounds for such models. Rather than focus on
the statistics of the solution (the argmaxx ) we study
statistical properties of the MAP value (the maxx ) of
the estimate in (4). Other strategies for sampling fromthe Gibbs distribution using MAP solvers include randomized hashing of Ermon et al. (2013).
Hazan & Jaakkola (2012) used the random MAP perturbation framework to derive upper bounds on thepartition function in (2), and Hazan et al. (2013b)
derived the unbiased sampler in Algorithm 1. Bothof these approaches involve computing an expectation

over the distribution of the MAP perturbation – thiscan be estimated by sample averages. This paper derives new measure concentration results that boundthe error of this estimate in terms of the number ofsamples, making Algorithm 1 practical.
Measure concentration has appeared in many machine learning analyses, most commonly to bound therate of convergence for risk minimization, either via
empirical risk minimization (ERM) (e.g., Bartlett &Mendelson (2003)) or in PAC-Bayesian approaches(e.g., McAllester (2003)). In these applications thefunction for which we want to show concentration
is “well-behaved” in the sense that the underlying
random variables are bounded or the function satisfies some bounded-difference or self-bounded conditions conditions, so measure concentration follows
from inequalities such as Bernstein (1946), AzumaHoeffding (Azuma, 1967; Hoeffding, 1963; McDiarmid,1989), or Bousquet (2003). However, in our setting, the Gumbel random variables are not bounded,
and random perturbations may result in unboundedchanges of the perturbed MAP value.
There are several results on measure concentration for
Lipschitz functions of Gaussian random variables (c.f.
the result of Maurey (1979) in Pisier (1986)). In thiswork we use logarithmic Sobolev inequalities (Ledoux,
2001) and prove a new measure concentration result
for Gumbel random variables. To do this we generalize a classic result of Brascamp & Lieb (1976) on
Poincaré inequalities to non-strongly log-concave distributions, and also recover the concentration resultof Bobkov & Ledoux (1997) for functions of Laplacerandom variables.

3. Concentration of measure
In this section we prove the main technical results ofthis paper – a new Poincaré inequality for log concave
distributions and the corresponding measure concentration result. We will then specialize our result to the
Gumbel distribution and apply it to the MAP perturbation framework. Because of the tensorization property of the functional entropy, it is sufficient for ourcase to prove an inequality like (13) for functions fof a single random variable with measure µ. Proofs
are deferred to the supplement due to space considerations.
3.1. A Poincaré inequality for log-concave
distributions
Our Theorem 2 in this section generalizes a celebrated
result of Brascamp & Lieb (1976, Theorem 4.1) to a

Measure concentration of random MAP perturbations

wider family of log-concave distributions and strictly
improves their result. For an appropriately scaled convex function Q on R, the function q(y) = exp(−Q(y))
defines a density on R corresponding to a log concave
measure µ. Unfortunately, their result is restricted to
distributions for which Q(y) is strongly convex. The
Gumbel distribution with CDF (5) has density
g(y) = exp (− (y + c + exp(−(y + c)))) ,(14)

and the second derivative of y+c+exp(−(y+c)) cannot
be lower bounded by any constant greater than 0, so
it is not log-strongly convex.
Theorem 2. Let µ be a log-concave measure with density q(y) = exp(−Q(y)), where Q : R → R is a convex
function satisfying the following conditions:• Q has a unique minimum in a point y = a,
• Q is twice continuously differentiable in each pointof his domain, except possibly in y = a,
• Q0 (y) 6= 0 for any y 6= a,2• limy→a± Q0 (y) 6= 0 or limy→a± Q00 (y) 6= 0.
Let f : R → R be a continuous function, differentiable
almost everywhere, such that
lim

y→±∞

f (y)q(y) = 0.
00

Proof. The proof is based on the one in Brascamp &Lieb (1976), but it uses a different strategy in the final
critical steps. We first observe that for any K ∈ R,
Z
Varµ (f ) ≤ (f (y) − K)2 dµ,(16)R

so we will focus on bounding the right-hand side of(16) for the particular choice of K = h(a).
∆where in the second inequality we used 2αβ ≤ αζ +β 2 ζ, for any α, ζ ∈ R and ζ > 0, with α = |f˜0 (y)|,00
β = |f˜(x)|, and ζ = Q 0 (y) + η|Q0 (y)|. Reasoning in|Q (y)|

the same way for the interval [a, +∞), reordering theterms, and using (16), we have the result.

(15)

Q (y)
0
6 0
Then for any 0 ≤ η < 1 such that |Q
0 (y)| +η|Q (y)| =for all y ∈ R \ {a}, we haveZ
(f 0 (y))21q(y)dy.
Varµ (f ) ≤00
1 − η R Q (y) + η(Q0 (y))2∆

We now consider the integral between −∞ and a(analogous reasoning holds for the one between a and+∞). We claim that limy→a− U (y) = 0. There are
two possible cases: Q0 (a) 6= 0 and Q0 (a) = 0. In
the first case the claim is obvious, in the second casef˜(y)2
2f 0 (y)f˜(y)we have limy→a− Q= 0, and0 (y) = limy→a−Q00 (y)anagously for the limit from the left. Using (15) too,
we haveZ af˜(y)2 q(y)dy
−∞
!
Z a+
2f˜0 (y)f˜(y) f˜(y)2 Q00 (y)−q(y)dy= lim−Q0 (y)(Q0 (y))2
→0
−∞
!
Z a+
2|f˜0 (y)||f˜(y)| f˜(y)2 Q00 (y)q(y)dy≤ lim−−|Q0 (y)|(Q0 (y))2
→0
−∞
!
Z a+
f˜0 (y)22
˜≤ lim−+ η f (y) q(y)dy,
Q00 (y) + η(Q0 (y))2
→0
−∞

˜

2

q(y)
Let f˜(y) = f (y) − f (a) and U (y) = f (y)Q0 (y) . Notethat dµ = q(y)dy. We have that 00
2f˜0 (y)f˜(y)q(y)Q (y)˜(y)2 q(y)U 0 (y) =−f+
1.
Q0 (y)(Q0 (y))2

Rearranging terms and integrating, we see thatZf˜(y)2 q(y)dy!
Z
2f˜0 (y)f˜(y) f˜(y)2 Q00 (y)=−q(y)dy − U (y).
Q0 (y)(Q0 (y))2

The main difference between Theorem 2 and the resultof Brascamp & Lieb (1976, Theorem 4.1) is that thelatter requires the function Q to be strongly convex.
Our result holds for non-strongly concave functions including the Laplace and Gumbel distributions. If wetake η = 0 in Theorem 2 we recover the original resultof Brascamp & Lieb (1976, Theorem 4.1). For the case
η = 1/2, Theorem 2 yields the Poincaré inequality for
the Laplace distribution given in Ledoux (2001). Like
the Gumbel distribution, the Laplace distribution is
not strongly log-concave and previously required analternative technique to prove measure concentration(Ledoux, 2001). The following gives a Poincaré inequality for the Gumbel distribution.
Corollary 1. Let µ be the measure corresponding to
the Gumbel distribution and q(y) = g(y) in (14). For
any function f that satisfies the conditions in Theorem 2, we haveZ
Varµ (f ) ≤ 4 (f 0 (y))2 dµ.
(17)R

Proof. For the Gumbel distribution we have Q(y) =y + c + exp(−(y + c)) in Theorem 2, so
Q00 (y) + η(Q0 (y))2 = e−(y+c) + η(1 − e−(y+c) )2 .

Measure concentration of random MAP perturbations

We want an lower bound for all y. Minimizing,e−(y+c) = 2η(1 − e−(y+c) )e−(y+c)
111or e−(y+c) = 1 − 2η
, so the lower bound is 1 − 2η
+ 4η
4η−1
1
1
or 4η for η > 2 . For η ≤ 2 ,

η + (1 − 2η)e−(y+c) + e−2(y+c) ≥ η.
on4η1
, η(1−η)= 4 at η = 12 . Applying
So min (4η−1)(1−η)

11Hence, choosing ρ = 10
, we obtain, for any |λ| ≤ 10b

Entµm (exp(λF )) ≤ 5a2 λ2 Eµm [exp(λF )].

(18)

Recall the moment generating function in (10) andλ−scaled cumulant generating function in (11), andnote that H(0) = E[F ]. We now use Herbst’s argument (Ledoux, 2001). Using (18) we have
H 0 (λ) =Theorem 2 we obtain (17).

Entµm (exp(λF ))≤ 5a2 .
λ2 Λ(λ)(19)

Integrating (19) we get
3.2. Measure concentration for the Gumbel
distribution
MAP perturbations such as those in (8) are a function of many random variables. We now derive a result based on the Corollary 1 to bound the moment
generating function for random variables defined as afunction of m random variables. This gives a measureconcentration inequality for the product measure µmof µ on Rm , where µ corresponds to a scalar Gumbel
random variable.
Theorem 3. Let µ denote the Gumbel measure on R
and let F : Rm → R be a function such that µm -almost
2
everywhere we have k∇F k ≤ a2 and k∇F k∞ ≤ b.
Furthermore, suppose that for y = (y1 , . . . , ym ),lim F (y1 , . . . , ym )yi →±∞mYg(yi ) = 0,

i=1where g(·) is given by (14). Then, for any r ≥ 0 and1
any |λ| ≤ 10b, we haveE[exp(λ(F − E[F ]))] ≤ exp(5a2 λ2 ).
Proof. For each i = 1, 2 . . . , m, we can think of F as ascalar function fi of its i-th argument for i = 1, . . . , m.
Using Theorem 5.14 of Ledoux (2001) and Corollary 1,
for any |λ|b ≤ ρ ≤ 1,

H(λ) ≤ H(0) + 5a2 λ = E[F ] + 5a2 λ,Now, from the definition of H(λ), this implies
log E[exp(λF )] ≤ λE[F ] + 5a2 λ2 .
With this lemma we can now upper bound the error
in estimating the average E[F ] of a function F of mi.i.d. Gumbel random variables by generating M independent samples of F and taking the sample mean.
Corollary 2. Consider the same assumptions of Theorem 3. Let η1 , η2 , . . . , ηM be M i.i.d. random variables with the same distribution as F . Then with probability at least 1 − δ,
!
r
M
20a2
1 X
20b
1
1
ηj − E[F ] ≤ max
log ,
log
.
M j=1
M
δ
M
δ
Proof. From the independence assumption, using theMarkov inequality, we have that


M
X
P
ηj ≤ M E[F ] + M rj=1

≤ exp(−M E[F ] − M r)

M
Y

E[exp(ληj )].

j=1

Entµi (exp(λfi ))
2

Z
√
1+ρ
exp(2 5ρ) |∂i F |2 dµi .
≤ 2λ2
1−ρ
We now use Proposition 5.13 in Ledoux (2001) to tensorize the entropy by summing over i = 1 to m:
Entµm (exp(λfi ))

2
Z X
m
√
1+ρ
≤ 2λ2
exp(2 5ρ)|∂i F |2 exp(λF )dµm
1−ρ
i=1

2
Z
√
1+ρ
≤ 2λ2
exp(2 5ρ)a2 exp(λf )dµm .
1−ρ1Applying Theorem 3, we have, for any |λ| ≤ 10b
,


M
X
1
P
ηj ≤ E[F ] + r ≤ exp(M (5a2 λ2 − λr)).
M j=1
1
Optimizing over λ subject to |λ| ≤ 10b
we obtainM
exp(M (5a λ − λr)) ≤ exp − min
20
2 2



r r2
,
b a2


.

Equating the left side of the last inequality to δ andsolving for r, we have the stated bound.

Measure concentration of random MAP perturbations

3.3. Application to MAP perturbations

110

1 samples
5 samples
10 samples

100

90

80

total deviation

To apply these results to the MAP perturbation problem we must calculate the parameters in the boundgiven by the Corollary 2. Let F (Γ) be the random
MAP perturbation as defined in (9). This is a func∆ Pntion of m = i=1 |Xi | i.i.d. Gumbel random variables.
The (sub)gradient of this function is structured andpoints toward the γi (xi ) corresponding to the maximizing P
assignment in x̂R−MAP defined in (4), whennγ(x) = i=1 γi (xi ). That is,∂F (Γ)
1 if xi ∈ x̂R−MAP=.
0 otherwise∂γi (xi )

70

60

50

40

30

20

10

0

0.5

1

1.5

2

2.5

3

3.5

4

coupling strengths

Figure 2. Error of the sample mean versus couplingstrength. With only 10 samples one can estimate the expectation well.

2

We have k∇F k = n and k∇F k∞ = 1 almost everywhere, so a2 = n and b = 1. Suppose we sample M
i.i.d. copies Γ1 , Γ2 , . . . , ΓM copies of Γ andPMestimate
1
the deviation from the expectation by M
i=1 F (Γi ).
We can apply Corollary 2 to both F and −F to get thefollowing double-sided bound with probability 1 − δ:
!
r
M
1 X
20
2
20n
2
F (Γi ) ≤ max
log ,
log
.
M i=1
M
δ
M
δ
Thus this result gives an P
estimate of the MAP pern
turbation E [maxx {θ(x) + i=1 γi (xi )}] that holds inhigh probability.
This result can also be applied to estimate the qualityof Algorithm 1, which samples from the Gibbs distribution using MAP solvers. To do so, let F equal∆ Pn
Vj from (8). This is a function of mj =i=j |Xi |i.i.d. Gumbel random variables whose gradient sat2
isfies k∇Vj k = n − j + 1 and k∇Vj k∞ = 1 almost
everywhere, so a2 = n − j + 1 and b = 1. Suppose
U = Vj − E [Vj ] is a random variable that measuresthe deviation of Vj from its expectation, and assume
we sample Mj i.i.d. random variable U1 , U2 , . . . , UMj .
We then estimate this deviation by the sample meanPMj
1
i=1 Ui . Applying Corollary 2 to both Vj and −Vj
Mj
to get the following bound with probability 1 − δ:
Mj
1 X
Ui
Mj i=1

≤ max

2
20
log ,
Mj
δ

s

20(n − j + 1)
2
log
Mj
δ

!
.

(20)

For each j in Algorithm 1, we must estimate |Xj | expectations EΓ [Vj+1 ], for a total at most m expectation
estimates. For any  > 0 we can choose {Mj : j =1, . . . , n} so that the right side of (20) is at most  foreach j with probability 1 − nδ. Let p̂j (xj ) be the ratio

estimated in the first step of Algorithm 1, and δ 0 = nδ.
Then with probability 1 − δ 0 , for all j = 1, 2, . . . , n,exp(E[Vj+1 ]−)exp(E[Vj+1 ]+)exp(E[Vj ]+) ≤ p̂j (xj ) ≤ exp(E[Vj ]−) , orexp(−2) ≤p̂j (xj )≤ exp(2).
pj (xj )4. Experiments
We evaluated our approach on a 100 × 100 spin glassmodel with n = 104 variables, for whichXX
θ(x1 , ..., xn ) =θi (xi ) +θi,j (xi , xj ) .
i∈V(i,j)∈E

where xi ∈ {−1, 1}. Each spin has a local field parameter θi (xi ) = θi xi and interacts in a grid shaped graphical structure with couplings θi,j (xi , xj ) = θi,j xi xj .
Whenever the coupling parameters are positive themodel is called attractive since adjacent variables
give higher values to positively correlated configurations. We
Pnused low dimensional random perturbations
γ(x) = i=1 γi (xi ).
The local field parameters θi were drawn uniformly at
random from [−1, 1] to reflect high signal. The parameters θi,j were drawn uniformly from [0, c], wherec ∈ [0, 4] to reflect weak, medium and strong coupling potentials. As these spin glass models are attractive, we are able to use the graph-cuts algorithm(Kolmogorov (2006)) to compute the MAP perturbations efficiently. Throughout our experiments we evaluated the expected value of F (Γ) with 100 different
samples of Γ. We note that we have two random variables γi (xi ) for each of the spins in the 100×100 model,thus Γ consists of m = 2 ∗ 104 random variables.
FigurePM 2 shows the error in the sample mean
1
k=1 F (Γk ) versus the coupling strength for threeMMeasure concentration of random MAP perturbations

histogram (frequency) of deviation

histogram (frequency) of deviation

20

15

10

5

0

0

50

100

150

200

total deviation

250

300

Local field = 1, coupling strength = 225

1 samples
5 samples
10 samples

350

20

15

10

5

0

Local field = 1, coupling strength = 325

1 samples
5 samples
10 samples

histogram (frequency) of deviation

Local field = 1, coupling strength = 1

25

0

50

100

150

200

250

300

total deviation

1 samples
5 samples
10 samples

20

15

10

5

0

0

50

100

150

200

250

300

350

total deviation

Figure 3. Histogram of MAP values for the 100 × 100 spin glass model.

different sample sizes M = 1, 5, 10. The error reduces
rapidly as M increases; only 10 samples are needed toestimate the expected value of a random MAP perturbation with 104 variables. To test our measure concentration result, that ensures exponential decay, wemeasure the deviation of the sample mean from its
expectation by using M = 1, 5, 10 samples. Figure
3 shows the histogram of the sample mean, i.e., thenumber of times that the sample mean has error morethan r from the true mean. One can see that the decay is indeed exponential for every M , and that forlarger M the decay is much faster. These show thatby understanding the measure concentration properties of MAP perturbations, we can efficiently estimate
the mean with high probability, even in very high dimensional spin-glass models.

5. Conclusion
Sampling from the Gibbs distribution is important because it helps find near-maxima in the “ragged” posterior probability landscapes typically encountered in
the high dimensional complex models. MCMC approaches are inefficient in such settings due to domainspecific modeling (coupling) and the influence of data
(signal). However, sampling based on MAP perturbations ignores the ragged landscape. In this paper wecharacterized the statistics of MAP perturbations.
The low-dimensional MAP perturbation technique requires estimating the expected value of the quantities Vj under the perturbations. We derived highprobability estimates of these expectations that allow estimation with arbitrary precision. This followedfrom more general results on measure concentration forfunctions of Gumbel random variables and a Poincaréinequality for non-strongly log-concave distributions.
These results may be of use in other applications.
Our results can be extended in several ways. The
connection between MAP perturbations and PAC-

Bayesian generalization bounds suggests that we may
be able to show PAC-Bayesian bounds for unbounded
loss functions. Such loss functions may exclude certain configurations and are already used implicitly invision applications such as interactive segmentation.
More generally, Poincaré inequalities relate the variance of a function and its derivatives. Our result may
suggest new stochastic gradient methods that control
variance via controlling gradients. This connection between variance and gradients may be useful in the analysis of other learning algorithms and applications.

References
Azuma, K. Weighted sums of certain dependent randomvariables. Tôhoku Mathematical Journal, 19(3):357–367,
1967.
Bartlett, P. L. and Mendelson, S. Rademacher and Gaussian complexities: Risk bounds and structural results.
JMLR, 3:463–482, 2003.
Bernstein, S. The Theory of Probabilities. Gastehizdat
Publishing House, Moscow, 1946.
Bobkov, S. and Ledoux, M. Poincaré’s inequalities and Talagrand’s concentration phenomenon for the exponential
measure. Probability Theory and Related Fields, 107(3):383–400, March 1997.
Boucheron, S., Lugosi, G., and Bousquet, O. Concentration inequalities. In Advanced Lectures on Machine
Learning, pp. 208–240. Springer, 2004.
Bousquet, O. Concentration inequalities for sub-additive
functions using the entropy method. In Stochastic inequalities and applications, pp. 213–247. Springer, 2003.
Brascamp, H. J. and Lieb, E. H. On extensions of theBrunn-Minkowski and Prékopa-Leindler theorems, including inequalities for log concave functions, and with
an application to the diffusion equation. J. Func. Analysis, 22(4):366 – 389, August 1976.
Ermon, S., Gomes, C. P., Sabharwal, A., and Selman, B.
Embed and project: Discrete sampling with universal
hashing. In Advances in Neural Information Processing
Systems, pp. 2085–2093, 2013.

Measure concentration of random MAP perturbations
Felzenszwalb, P.F. and Zabih, R. Dynamic programmingand graph algorithms in computer vision. IEEE Trans.
PAMI, 33(4):721–740, 2011.

Papandreou, G. and Yuille, A. Perturb-and-MAP random
fields: Using discrete optimization to learn and sample
from energy models. In ICCV, 2011.

Gumbel, E. J. and Lieblein, J. Statistical theory of extreme
values and some practical applications: a series of lectures. Number 33 in National Bureau of Standards Applied Mathematics Series. US Govt. Print. Office, Washington, DC, 1954.

Pisier, G. Probabilistic methods in the geometry of Banach
spaces. In Probabilty and Analysis, Varenna (Italy) 1985,
volume 1206 of Lecture Notes in Mathematics. Springer,
Berlin, 1986.

Hazan, T. and Jaakkola, T. On the partition function andrandom maximum a-posteriori perturbations. In ICML,
2012.
Hazan, T., Maji, S., J., Keshet, and Jaakkola, T. Learning
efficient random maximum a-posteriori predictors with
non-decomposable loss functions. Advances in Neural
Information Processing Systems, 2013a.
Hazan, T., Maji, S., and Jaakkola, T. On samplingfrom the gibbs distribution with random maximum aposteriori perturbations. Advances in Neural Information Processing Systems, 2013b.
Hoeffding, W. Probability inequalities for sums of bounded
random variables. JASA, 58(301):13–30, March 1963.
Huber, M. A bounding chain for swendsen-wang. Random
Structures & Algorithms, 22(1):43–59, 2003.
Jerrum, M., Sinclair, A., and Vigoda, E. A polynomialtime approximation algorithm for the permanent of amatrix with nonnegative entries. JACM, 51(4):671–697,
2004.
Keshet, J., McAllester, D., and Hazan, T. PAC-Bayesian
approach for minimization of phoneme error rate. In
ICASSP, 2011.
Koller, D. and Friedman, N. Probabilistic graphical models.
MIT press, 2009.
Kolmogorov, V. Convergent tree-reweighted message passing for energy minimization. PAMI, 28(10), 2006.
Koo, T., Rush, A.M., Collins, M., Jaakkola, T., andSontag, D. Dual decomposition for parsing with nonprojective head automata. In EMNLP, 2010.
Ledoux, M. The Concentration of Measure Phenomenon,
volume 89 of Mathematical Surveys and Monographs.
American Mathematical Society, 2001.
Ledoux, M. and Talagrand, M. Probability in BanachSpaces: isoperimetry and processes, volume 23. Springer,
1991.
Maurey, B. Construction de suites symétriques. Comptes
Rendus de l’Académie des Sciences, Paris, Série A-B,
288:A679–681, 1979.
McAllester, D. Simplified PAC-Bayesian margin bounds.
Learning Theory and Kernel Machines, pp. 203–215,
2003.
McDiarmid, C. On the method of bounded differences. In
Surveys in Combinatorics, number 141 in London Mathematical Society Lecture Note Series, pp. 148–188. Cambridge University Press, Cambridge, 1989.

Sontag, D., Meltzer, T., Globerson, A., Jaakkola, T., andWeiss, Y. Tightening LP relaxations for MAP using
message passing. In UAI, 2008.
Tarlow, D., Adams, R.P., and Zemel, R.S. Randomized
optimum models for structured prediction. In AISTATS,
pp. 21–23, 2012.
Valiant, L.G. The complexity of computing the permanent.
Theoretical computer science, 8(2):189–201, 1979.
Werner, T. High-arity interactions, polyhedral relaxations,and cutting plane algorithm for soft constraint optimisation (MAP-MRF). In CVPR, 2008.