Journal of Machine Learning Research 83 (2018)

Submitted 10/27 2017; Published

arXiv:1802.09301v1 [cs.LG] 26 Feb 2018

Dimension-free Information Concentration
via Exp-Concavity
Ya-Ping Hsieh

ya-ping.hsieh@epfl.ch

Volkan Cevher

volkan.cevher@epfl.ch

Laboratory for Information and Inference Systems (LIONS)
École Polytechnique Fédérale de Lausanne (EPFL)
EPFL-STI-IEL-LIONS, Station 11
CH-1015 Lausanne, Switzerland

Editor:

Abstract
Information concentration of probability measures have important implications in learning
theory. Recently, it is discovered that the information content of a log-concave distribution
concentrates around their differential entropy, albeit with an unpleasant dependence on
the ambient dimension. In this work, we prove that if the potentials of the log-concave
distribution are exp-concave, which is a central notion for fast rates in online and statistical
learning, then the concentration of information can be further improved to depend only
on the exp-concavity parameter, and hence, it can be dimension independent. Central to
our proof is a novel yet simple application of the variance Brascamp-Lieb inequality. In
the context of learning theory, our concentration-of-information result immediately implies
high-probability results to many of the previous bounds that only hold in expectation.
Keywords: Dimension-Free Concentration, Log-Concave Measures, Exp-Concavity, Variance Brascamp-Lieb Inequality, Differential Entropy

1. Introduction
We study the information concentration of probability measures: Given a probability
density f and a random variable X ∼ f , we ask how concentrated is the random variable
− log f (X) around its mean E[− log f (X)], which is simply the differential entropy of f .
We focus on the class of log-concave probability measures, whose densities are of the
form f (x) ∝ e−V (x) for some convex function V (·). Information concentration for logconcave measures has found many applications in learning theory, ranging from aggregation
(Dalalyan et al., 2016) and Bayesian decision theory (Pereyra, 2017), to, unsurprisingly,
information theory (Raginsky et al., 2013). It also has immediate implications to online
learning and PAC-Bayesian analysis (cf., Section 4 for further discussion on this topic)
Bobkov et al. (2011) discovered the information concentration phenomenon for logconcave measures. Their result was later sharpened by Fradelizi et al. (2016), which establishes the current state-of-the-art. However, via the concentration bound in (Fradelizi et al.,
2016), one can immediately notice a poor dependence on the dimension (see Theorem 1).
This unpleasant dependence is, however, not due to any deficit of the analysis: Even
in the Gaussian case, the information concentration is known to be dimension-dependent
1

Hsieh and Cevher

(Cover and Pombra, 1989), and the bound in (Fradelizi et al., 2016) matches the tightest
known result. We can verify that the exponential distributions, another candidate for
dimension-free concentration, share the same poor dimensional scaling.
Given these observations, one might pessimistically conjecture that no meaningful subclass of log-concave measures satisfies the information concentration in a dimension-free
fashion. Hence, our main result comes as a surprise that, not only does there exist a
large subclass of log-concave measures with dimension-free information concentration, but
in addition, this subclass is extremely well-known to the machine learning community:
Our main result (informal statement): Let f (x) ∝ e−V (x) where V is ηexp-concave. Then, the information concentration of f (x) solely depends on the
exp-concavity parameter η, and not the ambient dimension.
Many loss functions in machine learning are known to be exp-concave; a non-exhaustive
list includes the squared loss, entropic loss, log-linear loss, SVMs with squared hinge loss, and
log loss; see (Cesa-Bianchi et al., 2006) for more. Moreover, distributions of the type e−V (x) ,
where V is exp-concave, appear frequently in many areas of learning theory. Consequently,
our main result is tightly connected to learning with exp-concave losses; see Section 4.
Our main insight is that exp-concave functions are Lipschitz in a local norm, and logconcave measures satisfy the “Poincaré inequality in this local norm”, namely the BrascampLieb inequality. We elaborate more on the intuition in Section 5.1. In retrospect, the proof
of our main result is, once the right tools are identified, completely natural and elementary.
In fact, our result basically implies that the exp-concavity arises naturally in the dimensionfree information concentration.
The rest of the paper is organized as follows. We first set up notations and review
basics of differential entropy and log-concave distributions in Section 2. In Section 3, which
contains precise statements of the main result, we present various dimension-free inequalities
for information concentration. We provide a counterexample to a conjecture, which is a
natural strengthening of our results. We discuss implications of information concentration
in Section 4 with motivating examples. Finally, Section 5 presents the technical proofs.

2. Preliminaries
2.1 Notations
R
R
R
2
For a function f , we write Eµ f := f dµ and Varµ (f ) := f 2 dµ −
f dµ . We write
X ∼ µ for a random variable X associated with the probability measure µ.
In this paper, the norm k · k is always the Euclidean norm, and we use h·, ·i for the
Euclidean inner product. We use ∇V , ∇2 V , and ∂V to denote the gradient, Hessian, and
subgraident of V , respectively. The notation C k denotes the class of k-times differentiable
functions with continuous k-th derivatives.
2

Dimension-free Information Concentration via Exp-Concavity

2.2 Differential Entropy and Log-Concave Distributions
Let µ be a probability measure having density f with respect to the Lebesgue measure and
let X ∼ µ. The differential entropy (Cover and Thomas, 2012) of X is defined as
h(µ) = h(X) := Eµ [− log f (X)].

(1)

The random variable h̃(µ) = h̃(X) := − log f (X) is called the information content of µ.
We study the concentration of information content around the differential entropy:


P |h̃(X) − h(X)| > t ≤ α(t)

where α : R+ → R+ vanishes rapidly as t increases.
Throughout this paper, we consider log-concave probability measures, namely probability
measures having density of the form
e−V (x)
dµV (x) = R −V dx,
e

(2)

R
where V is a convex function such that e−V < ∞. The function V is called the potential
of the measure µV . For log-concave measures, the concentration of information content is
equivalent to the concentration of the potential, i.e., P (|V − EµV V | > t).

3. Dimension Free Concentration of Information for Exp-Concave
Potentials
This section presents our main results.
We first review the state-of-the-art bound in Section 3.1. In Section 3.2, we demonstrate
dimension-free information concentration when the underlying potential V is assumed to be
exp-concave. All our results are of sub-exponential type; it is hence natural to ask if the subGaussian counterparts are also true. We show that this is impossible even in dimension 1, by
giving a counterexample in Section 3.3. Finally, we highlight some immediate consequences
of our main results in Section 3.4. All proofs are deferred to Section 5.
3.1 Previous Art
The state-of-the-art concentration bound for V is given by Fradelizi et al. (2016):
Theorem 1 (Information Concentration for Log-Concave Vectors) Let dµV (x) :=
be a d-dimensional log-concave probability measure. Then, we have

eR−V (x)
dx
e−V

1. Var(V (X)) ≤ d.
2. There exist universal constants c1 and c2 such that

 2 
t
.
P (|V − EV | > t) ≤ c1 exp −c2 min t,
d
3

(3)

Hsieh and Cevher

This is the main result of (Fradelizi et al., 2016) combined with the well-known relation
t − log(1 + t) ≃ min(t, t2 )
for every t ≥ 0.
2
The bound (3) matches the tightest known results for V = k·k2 (i.e., the Gaussian case;
see Cover and Pombra, 1989). However, notice that (3) has a poor dependence on the
2
dimension d, as well as having the exponent being the worst case of t and td .
3.2 Our Results
We first recall the definition of exp-concave functions (Hazan, 2016):
Definition 2 A function V is said to be η-exp-concave if e−ηV is concave. Equivalently, V
is η-exp-concave if the matrix inequality ∇2 V (x)  η∇V (x)∇V (x)⊤ holds for all x. Notice
that an exp-concave function is necessarily convex.
We next present three concentration inequalities for V in Theorem 3-6. Theorem 3
serves as the prototype for all the concentration inequalities to come, however with restrictive conditions that severely limit its applicability. To overcome such dilemma, in Theorem
5 and 6 we introduce practically motivated assumptions, and show how the restrictive conditions of Theorem 3 can be removed without effecting the concentration.
3.2.1 Information Concentration: the Strictly Convex Case
The first main result of this paper is that, for dµV with V being η-exp-concave and strictly
convex, the concentration of information content depends solely on η.
Theorem 3 Assume that V ∈ C 2 is η-exp-concave and ∇2 V ≻ 0. Let dµV (x) =
be the log-concave distribution associated with V . Then

eR−V (x)
dx
e−V

1. VarµV (V ) ≤ η1 .



√
2. P |V − EV | ≥ t ≤ 6 exp − max( η, η)t .

Notice that when η1 ≃ d, the bounds in Theorem 1 and 3 yield comparable results.
In this sense, η1 can be viewed as the “effective dimension” regarding the concentration of
information content.
3.2.2 Information Concentration: the General Convex Case
In many of the applications in learning theory (cf., Section 4), the potential V is not
guaranteed to be globally strictly convex. However, we have the following observation:
Lemma 4 Assume that V ∈ C 2 is η-exp-concave. Let S + (x) be the subspace spanned by
the eiganvectors corresponding to non-zero eigenvalues of ∇2 V (x). Then ∇V (x) ∈ S + (x)
for all x.
4

Dimension-free Information Concentration via Exp-Concavity

Simply put, ∇2 V may not be strictly convex in all directions, but it is always strictly convex
in the direction of ∇V . Our second result shows that in this case, one can drop the global
strict convexity of V while retaining exactly the same dimension-free concentration.
Theorem 5 Assume that V ∈ C 2 is η-exp-concave, but not necessarily strictly convex. Let
−V (x)
dµV (x) = eR e−V dx be the log-concave distribution associated with V . Then
1. VarµV (V ) ≤ η1 .



√
2. P |V − EV | ≥ t ≤ 6 exp − max( η, η)t .

3.2.3 Information Concentration in the Presence of Nonsmooth Potential
The following case appears frequently in machine learning applications: The potential V
can be decomposed as V = V1 + V2 , where V1 is a “nice” convex function (meaning satisfying
either the assumptions in Theorem 3 or Theorem 5), while V2 is a nonsmooth convex
function. Since V is neither differentiable nor strictly convex, results above do not apply.
Our third result is to show that, in this scenario, the term V1 in fact enjoys dimension-free
concentration as if the nonsmooth term V2 is absent.
Theorem 6 Let V = V1 + V2 , where V1 satisfies the assumptions in either Theorem 3 or
Theorem 5, and V2 is a general convex function. Then we have


√
(4)
P |V1 − EV1 | ≥ t ≤ 6 exp (− max( η, η)t) ,

where the probability is with respect to the total measure dµV , and η is the exp-concavity
parameter of V1 .

3.3 A Counterexample to Sub-Gaussian Concentration of Information Content
So far, we have established dimension-free concentration of sub-exponential type under
various conditions. An ansatz is whether under the same assumptions, one has dimensionfree sub-Gaussian concentration; i.e., a deviation inequality of the form
2

P (|V − EV | ≥ t) ≤ c1 e−c(η)t

(5)

for a universal constant c1 and some constant c(η) depending only on η.
In this subsection, we provide a counterexample to this conjecture, showing that this is
impossible even in dimension 1.
Consider the one-dimensional case where V (x) = − log x and the support is Ω := (0, 1).
Notice that V is trivially 1-exp-concave. If (5) holds for V , then we would have
Z ∞ 

2
λ(V −EV )2
P eλ(V −EV ) > x dx
=
Ee
0
Z ∞
2
2
c1 e−c(η)t teλt dt
≤ 2λ
0

<∞

5

Hsieh and Cevher

if λ < c(η). However, a straightforward computation shows that
λ

2

Eeλ(V −EV ) =

e 64
2

Z

1

0

2

x1.25 eλ(log x) dx = ∞

(6)

for every λ > 0. We hence cannot have any sub-Gaussian concentration for V .
It is easy to generalize this example to any dimension.
3.4 Immediate Consequences
An immediate consequence of information concentration is that many important densities
in information theory also concentrate.
Corollary 7 (Concentration of Information Densities) Let f (x, y) : Rd × Rd → R
be a joint log-concave density of the random variable
pair (X, Y ). Denote the marginal
R
distribution of the first argument by f (x) := Rd f (x, y)dy and similarly for f (y), and
denote the conditional distribution by f (y|x) := ff(x,y)
(x) . Then there exist universal constants
c1 , c2 such that the following holds:
 2 

.
1. P (|− log f (Y |X) − E[− log f (Y |X)]| > t) ≤ 2c1 exp − c22 min t, td
2. P



 2 
i


h
(X,Y )
f (X,Y )
c2
.
− log f f(X)f
min
t, td
>
t
≤
3c
exp
−
−
E
−
log
1
3
(Y )
f (X)f (Y )

If, in addition, that − log f (x, y), − log f (x), and − log f (y) are η-exp-concave and − log f (·, ·)
√
is strictly convex. Then the exponents in the above bounds can be improved to max( η, η)t.
Notice that
i [− log f (Y |X)] is the conditional (differential) entropy, and
h h(Y |X) := E
f (X,Y )
:=
I(X; Y )
E − log f (X)f (Y ) is the mutual information. The (random) quantities − log f (Y |X)

(X,Y )
and − log f f(X)f
(Y ) play prominent roles in recent advances of non-asymptotic information
theory; see Polyanskiy (2010) and the references therein.

Proof A celebrated result of Prékopa (1971) states that the marginals of log-concave measures are also log-concave. The corollary then follows by the well-known decomposition
h(Y |X) = h(X, Y ) − h(X) and I(X; Y ) = h(X) + h(Y ) − h(X, Y ).

4. Motivating Examples
Unsurprisingly, information concentration has many applications in learning theory; we
present three examples in this section. To avoid lengthy but straightforward calculations,
we shall omit the details and refer the readers to proper literature.
P
Below, we consider loss functions of the form Ln (x) := n1 ni=1 ℓi (x), where ℓi ’s are
exp-concave. By Lemma 12 in Appendix A, the total loss Ln is also exp-concave. Denote
the exp-concave parameter of Ln by η.
We remark that, in general, η can depend on the dimension d or the sample size n. A
comparison of the favorable regimes for different η’s is presented in Table 1.
6

Dimension-free Information Concentration via Exp-Concavity

Ours, η = Ω(1)

t = Θ(1)
√
t = Θ( d)

Fradelizi et al. (2016)

exp − d1

t = Θ(d)

exp (−d)

exp (−d)

exp (−1)
 √ 
exp − d

exp (−1)

Ours,
 η =Ω
exp − √1
d

1
d



exp (−1)
 √ 
exp − d

Table 1: The deviation P (|V − EV | > t) dictated by different concentration inequalities.
4.1 High-Probability Regret Bounds for Exponential Weight Algorithms
Exp-concave losses have received substantial attention in online learning as they exhibit
logarithmic regret (Hazan et al., 2007). One class of algorithms attaining logarithmic regret
is based on the Exponential Weight, which makes prediction according to
xt+1 = Eπt X,

(7)

πt (x) ∝ e−nLn (x) .

(8)

where
A common belief is that the algorithm (7) is inefficient to implement, and practitioners
would more opt into first-order methods such as the (see Hazan et al., 2007) Online Newton
Step (which is also somewhat inefficient: every iteration requires inverting a matrix and
a projection). However, recent years have witnessed a surge of interest in the sampling
schemes, mainly due to its connection to the ultra-simple Stochastic Gradient Descent
(Welling and Teh, 2011). Theoretical (Bubeck et al., 2015; Durmus and Moulines, 2016;
Dalalyan, 2017; Dalalyan and Karagulyan, 2017; Cheng and Bartlett, 2018) and empirical
(Welling and Teh, 2011; Ahn et al., 2012; Rezende et al., 2014; Blei et al., 2017) studies of
sampling schemes have now become one of the most active areas in machine learning.
In view of these recent developments, it is natural to consider, instead of
Pthe expected
prediction (7), taking samples Xt,1 , Xt,2 , ..., Xt,N ∼ πt and predict X̄t := N1 N
i=1 Xt,i . The
following corollary of our main result establishes the desirable concentration property of X̄t .
Re
. Assume that V
Corollary 8 Let {Xi }N
i=1 be i.i.d. samples from the distribution
e−V
satisfies either the assumptions of Theorem 3 or Theorem 5. Then
!
N
√
1 X
V (Xi ) − EV > t ≤ 2e−N ( ηt−log 3) .
(9)
P
N
−V

i=1

Proof For simplicity, assume η = 1; the general case is similar.
By the classic Chernoff bounding technique, we can compute
!
N

 PN
1 X
V (Xi ) − EV > t = P e i=1 (V (Xi )−EV ) > eN t
P
N
i=1
N

≤ e−N t Ee(V (X)−EV )
≤ e−N t · 3N

= e−N (t−log 3) ,

7

Hsieh and Cevher

where the second inequality follows from (22) with η = 1.
Plugging (9) into the expected regret bounds for the Exponential Weight algorithm (e.g.,
Hazan et al., 2007), we immediately obtain high-probability regret bounds.
Similar arguments hold for random walk-based approaches in online learning (Narayanan and Rakhlin,
2010).
4.2 Posterior Concentration of Bayesian and Pac-Bayesian Analysis
The (pseudo-)posterior distribution plays a fundamental role in the PAC-Bayesian theory:
π̂(x) ∝ exp (−nVn (x)) ,

(10)

where Vn (x) = Ln (x) − n1 log π0 (x). Here, x represents the parameter vector and π0 is the
prior distribution. It is well-known that (10) is optimal in PAC-Bayesian bounds for the
expected (over the posterior distribution on the parameter set) population risk (Catoni,
2007). Moreover, when the loss functions ℓi ’s are the negative log-likelihood of the data,
the optimal PAC-Bayesian posterior (10) coincides with the Bayesian posterior; see (Zhang,
2006) or the more recent (Germain et al., 2016).
We now consider the high-probability bound in the following sense: Instead of taking the
expectation over π̂ as previously done, we draw a random sample X ∼ π̂, and ask what is the
population risk for X. Besides its apparent theoretical interest, such characterization is also
important in practice, as there exist many sampling schemes for log-concave distributions
π̂ (Lovász and Vempala, 2007; Bubeck et al., 2015; Durmus and Moulines, 2016; Dalalyan,
2017), while computing the mean is in general costly (the mean is typically obtained through
a large amount of sampling anyway).
A straightforward application of Theorem 6 shows that, if the prior π0 is log-concave,
then Ln (X) concentrates around Eπ̂ Ln (X); notice that many popular priors (uniform, Gaussian, Laplace, etc.) are log-concave. On the other hand, concentration of the empirical risk
Ln around the population risk is a classical theme in statistical learning. To conclude,
Theorem 6 implies high-probability results for the PAC-Bayesian bounds. In view of
the equivalence established in (Germain et al., 2016), we also obtain concentration for the
Bayesian posterior in the case of negative log-likelihood loss.
4.3 Bayesian Highest Posterior Density Region
Let π̂ be the posterior distribution as in (10). In Bayesian decision theory, the optimal
confidence region associated with a level α is given by the Highest Posterior Density (HPD)
region (Robert, 2007), which is defined as
Cα⋆ := {x ∈ Rd | Vn (x) ≤ γα }

(11)

R
where γα is chosen so that C ⋆ π̂(x)dx = 1 − α.
α
Using concentration of the information content for log-concave distributions, Pereyra
(2017) showed that Cα⋆ is contained in the set
C̃α := {x ∈ Rd | Vn (x) ≤ Vn (x⋆ ) + dtα + d},
8

(12)

Dimension-free Information Concentration via Exp-Concavity

q

:= arg maxx Vn (x) is the MAP parameter, and tα = c1 log(1/α)
for some constant
where
d
c1 . A straightforward application of our results shows that, when the data term Ln in Vn is
η-exp-concave, then we can improve (12). For simplicity, let us focus on the uniform prior
(π0 = constant). Adapting the analysis in Pereyra (2017), we can show that Cα⋆ is contained
in the set
(13)
C̃αη := {x ∈ Rd | Vn (x) ≤ Vn (x⋆ ) + tηα + d},
q
where tηα = c2 log(1/α) · nη . Comparing (12) and (13), we see that (ignoring logarithmic

terms) we get improvements whenever η = Ω nd . This is typically the case in highdimensional statistics (Bühlmann and Van De Geer, 2011) or compressive sensing (Ji et al.,
2008; Foucart and Rauhut, 2013) where n ≪ d.
Similar results can be established for the Gaussian and Laplace prior, where one can
invoke results in (Cover and Pombra, 1989) and (Talagrand, 1995) to deduce the concentration of the prior term. We omit the details.
x⋆

5. Proofs of the Main Results
We prove the main results in this section. Our analysis crucially relies on the variance
Brascamp-Lieb inequality, recalled and elaborated in Section 5.1. Section 5.2-4 are devoted
to the proofs of Theorem 3-6, respectively.
5.1 Proof Ideas
For a probability measure µ, we say that µ satisfies the Poincaré inequality with constant
λ1 if
Z
λ1 Varµ (f ) ≤ k∇f k2 dµ
(14)
for all locally Lipschitz f . It is well-known that if (14) is satisfied for µ, then all the Lipschitz
functions concentrate exponentially (Ledoux, 2004, 2005):
∀ 1 − Lipschitz f,

P (|f − Ef | > t) ≤ c1 e−

√

λ1 t

(15)

for some universal constant c1 .
At first glance, our theorems seem to have little to do with the Poincaré inequality, since
1. It is not known whether a log-concave distribution satisfies the Poincaré inequality
with a dimension-independent constant (this is the content of the Kannan-LovászSimonovits conjecture; see Kannan et al., 1995; Alonso-Gutiérrez and Bastero, 2015).
2. Typically, the potential V is not Lipschitz (consider the Gaussian distribution where
2
depends
V (x) = kxk
2 ). Moreover, even if V is Lipschitz, the Lipschitz constant often
√
on the dimension (consider the exponential distribution where k∇V k = Θ( d)).
The important observation in this paper is that the appropriate norm in (14) for information concentration is not the Euclidean norm (or any ℓp -norm), but instead the (dual of
the) local norm defined by the potential V itself, namely kykx := ∇2 V (x)y, y .
9

Hsieh and Cevher

Lemma 11 in Appendix A expresses the fact that η-exp-concave functions are Lipschitz
with respect to this local norm, and the Brascamp-Lieb inequality below provides a suitable
strengthening of the Poincaré inequality:
Theorem 9 (Brascamp-Lieb Inequality) Let dµV (x) =
ability measure with V ∈
L2 (µV ), we have

C2

and

∇2 V

VarµV (f ) ≤

eR−V (x)
dx
e−V

be a log-concave prob-

≻ 0. Then for all locally Lipschitz function f ∈
Z

∇2 V −1 ∇f, ∇f dµV .

(16)

We shall see that the Brascamp-Lieb inequality provides precisely the desired control of
the Lipschitzness of V in terms of the aforementioned dual local norm. Once this is observed,
the rest of the proof is a routine in deducing from Poincaré inequality the sub-exponential
concentration of Lipschitz functions.
We remark that our approach is, in retrospect, completely natural and elementary.
However, to the best of our knowledge, our work is the first to combine the Brascamp-Lieb
inequality (16) with the local norm of the form kykx := ∇2 V (x)y, y .
5.2 Proof of Theorem 3
The first assertion is a simple application of the Brascamp-Lieb inequality (16) and Lemma
11.


We now prove the concentration inequality. We first show that P |V − EV | ≥ t ≤


√ 
)
6 exp − ηt . Applying (16) to f = exp λ(V −EV
, we get
2
Z
λ2
f 2 ∇2 V −1 ∇V, ∇V dµV
VarµV (f ) ≤
4
Z
λ2
≤
f 2 dµV
4η

(17)

by Lemma 11. Let M (λ) := E exp (λ(V − EV )). Then the inequality (17) reads
 2
λ
λ2
M (λ) − M
≤
M (λ),
2
4η
and hence

 2
λ
M
M (λ) ≤
.
λ2
2
1 − 4η
1

(18)

(19)

Apply (19) recursively to obtain
M (λ) ≤

ΠK−1
k=1

1
1−

λ2
4k+1 η

!2k

M



λ
2K

2K

Since M (λ) = 1 + o(λ), we have
  K
 2K 
2
λ
λ
→1
= 1+o
M
K
K
2
2
10

.

(20)

Dimension-free Information Concentration via Exp-Concavity

as K → ∞. Hence (20) implies
M (λ) ≤ Π∞
k=1
which in turn gives

1
1−

λ2
4k+1 η

!2k

,

√
M ( η) ≤ 3.

The proof can now be completed by the classic Chernoff bounding technique:
 √
√ 
P (V − EV ≥ t) = P e η(V −EV ) ≥ e ηt
√
√
≤ e− ηt M ( η)
≤ 3e−

√

ηt

.

(21)

(22)

(23)

Now, the inequality (23) implies that for any 1-exp-concave V , we have
P (V − EV ≥ t) ≤ 3e−t .
If V is η-exp-concave, ηV is 1-exp-concave, and hence we conclude that


t
≤ 3e−t ;
P V − EV ≥
η
that is to say,
P (V − EV ≥ t) ≤ 3e−ηt .

(24)

The bound for P (V − EV ≤ −t) is similar.
The proof is completed by taking the best case of (23) and (24), and applying the union
bound.
5.3 Proof of Lemma 4 and Theorem 5
We first prove Lemma 4.
For any point x, let {ai }ki=1 be an orthonormal basis for S + (x), assumed to have dimension k. We extend {ai }ki=1 to an orthonormal basis for Rd as {ai }di=1 , and we decompose
P
∇V (x) = di=1 ci ai for some real numbers ci ’s.
For the purpose of contradiction, assume that ∇V (x) ∈
/ S + (x). Then cj 6= 0 for some
j ∈ {k + 1, k + 2, ..., d}. But then
∇2 V (x)aj , aj = 0
while
⊤
2
a⊤
j ∇V (x)∇V (x) aj = cj > 0,

contradicting the exp-concavity of V . This finishes the proof of Lemma 4.
We now turn to Theorem 5.
Let ǫ > 0 be arbitrarily small, and consider the quantity
D
E
−1
∇2 V + ǫI
∇V, ∇V .
11

(25)

Hsieh and Cevher

Lemma 4 implies that (25) is equal to
D
E
−1
∇2 V + ǫIS +
∇V, ∇V ,

(26)

where IS + is the identity map on the subspace S + . Since V is strictly convex restricted to
S + , and since ∇V ∈ S + , Lemma 11 then implies
D
E 1
−1
∇2 V + ǫI
∇V, ∇V ≤
(27)
η

for all ǫ > 0.


2
λ(V −EV )
. Since Ṽ is strictly convex, we may
Consider Ṽ = V + ǫk·k
,
and
let
f
=
exp
2
2
invoke the Brascamp-Lieb inequality (16) to conclude
Z
D
E
λ2
VarµṼ (f ) ≤
f 2 ∇2 Ṽ −1 ∇V, ∇V dµṼ
4
Z
λ2
f 2 dµṼ
(28)
≤
4η
where the second inequality follows from (27). Letting ǫ → 0 in (28) then gives
Z
λ2
VarµV (f ) ≤
f 2 dµV .
4η

(29)

The rest of the proof is similar to that of Theorem 3; we omit the details.
5.4 Proof of Theorem 6
We will need the following strengthened Brascamp-Lieb inequality, which might be of independent interest. Once the following theorem is established, one can follow a similar proof
as in Section 5.2. We omit the details, and focus on the proof of the following theorem in
the rest of this subsection.
Theorem 10 (Nonsmooth Brascamp-Lieb Inequality) Let dµṼ (x) =

eR−Ṽ (x)
dx
e−Ṽ

be a

log-concave measure with Ṽ = V + U , where V ∈ C 2 , ∇2 V ≻ 0, and U is convex but possibly
non-differentiable. Then for all locally Lipschitz function f ∈ L2 (µṼ ), we have
Z
∇2 V −1 ∇f, ∇f dµṼ .
(30)
VarµṼ (f ) ≤
Proof [Proof of Theorem 10] Define the cost functions
D
E
cṼ (x, y) := Ṽ (y) − Ṽ (x) − ∂ Ṽ (x), y − x

(31)

cV (x, y) := V (y) − V (x) − h∇V (x), y − xi .

(32)

and

By Proposition 1.1 of Cordero-Erausquin (2017) (see also p.482 for the non-differentiable
case), we know that the measure dµṼ satisfies the transportation cost inequality:
WcṼ (µṼ , ν) ≤ D(νkµṼ )
12

Dimension-free Information Concentration via Exp-Concavity

for any probability measure ν. Here, WcṼ (µṼ , ν) := inf X,Y EcṼ (X, Y ) where the infimum is
over all joint distributions with marginals X ∼ µṼ and Y ∼ ν, and D(νkµṼ ) is the relative
entropy between ν and µṼ . Since U is convex, we have cṼ (x, y) ≥ cV (x, y) for all x, y, and
hence µṼ satisfies the weaker transportation cost inequality
WcV (µṼ , ν) ≤ D(νkµṼ ).

(33)

The theorem can then be deduced from a standard linearization procedure that is wellknown since the classic (Otto and Villani, 2000). The rest of the proof below is a suitable
adaptation of the version in (Cordero-Erausquin, 2017).
Since continuous functions with compact support are dense in L2 (µṼ ), we will prove
Theorem 10 for any continuous function with compact support. Notice that such functions
are necessarily Lipschitz and hence differentiable µṼ -almost everywhere. Since modifying f
in a set of µṼ -measure 0 does not effect (30), we may henceforth assume that f ∈ C 1 and
has compact support.
Since V ∈ C 2 , ∇2 V (y) is uniformly continuous on any compact set, and hence we have
cV (y + h, y) =

1
∇2 V (y)h, h + khk2 · o(1)
2

(34)

uniformly in y on any compact set when h → 0. Assume for the moment thatR cV (x, y) ≥
δ
2
1
2 kx−yk for some δ > 0. Given any function g ∈ C with compact support and gdµṼ = 0,
introduce the infimal convolution associated with the cost cV :
Qc (g)(y) := inf {g(x) + cV (x, y)},
x

(35)

whence Qc (g)(y) − g(x) ≤ cV (x, y). By the definition of WcV , for any joint probability
measure π having marginals µṼ and ν, we must have
Z
Z
Z
(36)
WcV (µṼ , ν) = inf cV (x, y)dπ(x, y) ≥ Qc (g)dν − gdµṼ .
π

Consider the infimum convolution of ǫg:
Qc (ǫg)(y) = inf {ǫg(x) + cV (x, y)} = inf {ǫg(y + h) + cV (y + h, y)}.
x

h

(37)

Let hǫ = hǫ (y) denote a point where the infimum is achieved. Since g is globally Lipschitz,
say with constant L,
ǫg(y + hǫ ) + cV (y + hǫ , y) ≥ ǫg(y) − ǫLkhǫ k + δkhǫ k2 .

(38)

On the other hand, by setting h = 0 in (37), we see that ǫg(y + hǫ ) + cV (y + hǫ , y) ≤ ǫg(y).
Combining this with (38) gives
L
khǫ k ≤ ǫ.
(39)
δ
Notice that (39) does not depend on y, and hence khǫ k = O(ǫ) uniformly in y.
As g is compactly supported, we have sup |g| = M < ∞. Let Ω be the support of
c
g, and let Bǫ := {x | ∃y ∈ Ω, kx − yk2 ≤ 2ǫM
δ }. We claim that Qc (ǫg) ≥ 0 on Bǫ .
13

Hsieh and Cevher

Indeed, for any y ∈ Bǫc , suppose that the infimum of x in (37) is attained in Ω. Then
δ
2ǫM
2
2
Qc (ǫg) ≥ 2δ · 2ǫM
δ − ǫM = 0, since cV (x, y) ≥ 2 kx − yk and inf x∈Ω ky − xk ≥ δ . On
the other hand, if the infimum of x in (37) is attained outside Ω, then ǫg = 0 and cV ≥ 0
implies that Qc (ǫg) ≥ 0.
R
For the sake of linearization, set dν = (1 + ǫf ) dµṼ for some f ∈ C 1 with f dµṼ = 0.
We now compute
Z
Z
WcV (µṼ , (1 + ǫf )dµṼ ) ≥ Qc (ǫg) (1 + ǫf ) dµṼ
since
gdµṼ = 0,
Z
Qc (ǫg) (1 + ǫf ) dµṼ
since Qc (ǫg) ≥ 0 on Bǫc .
(40)
≥
Bǫ

As the set Bǫ is itself compact, we have, uniformly in y,

Qc (ǫg)(y) = ǫg(y + hǫ ) + c(y + hǫ , y)
1
= ǫg(y) + ǫ h∇g(y), hǫ i +
∇2 V (y)hǫ , hǫ + o(ǫ2 )
(41)
2
where the last line follows by (39). Noticing that (41) is convex in hǫ , we can find its
minimum (up to o(ǫ2 )) and write
ǫ2
∇2 V −1 (y)∇g(y), ∇g(y) + o(ǫ2 ).
(42)
2
R
RMultiplying (42) by 1 + ǫf and integrate on Bǫ w.r.t. dµṼ , we get, using (40) and f dµṼ =
gdµṼ = 0,
Z
Z

1
1
f
gdµ
−
≥
∇2 V −1 ∇g, ∇g dµṼ + o(1).
(43)
µ
,
(1
+
ǫf
)
dµ
W
c
Ṽ
Ṽ
ǫ2 V Ṽ
2
Bǫ
Bǫ
Qc (ǫg)(y) ≥ ǫg(y) −

By definition, Bǫ contains the support of g, and hence the integrals in (43) are in fact over
the whole space. We hence conclude
Z
Z

1
1
∇2 V −1 ∇g, ∇g dµṼ .
(44)
lim inf 2 WcV µṼ , (1 + ǫf ) dµṼ ≥ f gdµṼ −
ǫ→0 ǫ
2
Replacing g by λg in (44) and optimizing over λ, we get
2
R

f gdµṼ
1
R
≤ lim inf 2 WcV µṼ , (1 + ǫf ) dµṼ .
−1
ǫ→0 ǫ
2 h∇V ∇g, ∇gi dµṼ
R
2
Moreover, using log(1 + x) = x − x2 + o(x2 ) and f dµṼ = 0, we can compute


Z

ǫ2 f 2
2
+ o(ǫ ) dµṼ
D (1 + ǫf ) dµṼ kµṼ = (1 + ǫf ) ǫf −
2
Z
ǫ2
=
f 2 dµṼ + o(ǫ2 ).
2

(45)

(46)

In the case of cV (x, y) ≥ 2δ kx − yk2 , Theorem 10 then follows by using g = f in (45)
2

and combing (33) and (46). For general case, replace V by V + δk·k
2 and take δ → 0 in (44)
and (46) to deduce the same inequalities.

14

Dimension-free Information Concentration via Exp-Concavity

6. Conclusion
We have shown that for log-concave distributions with exp-concave potentials, the information concentration is dictated by its exp-concavity parameter η. Information theoretically
speaking, η (or rather η1 ) can be viewed as some sort of effective dimension, in the sense that
1
η and d play very similar roles in both the variance and concentration controls, the former
for log-concave measures with exp-concave potential and the latter for general log-concave
measures. Such a understanding enables us to derive high-probability results for many of
the machine learning algorithms, including the Bayesian, PAC-Bayesian, and Exponential
Weight type approaches.

Acknowledgments
This project has received funding from the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant agreement no
725594 - time-data).

Appendix A. Properties of Exp-Concave Functions
We present two useful properties of exp-concave functions in this appendix. While these
properties are well-known to the experts, we provide the proofs for completeness.
Lemma 11 Assume that V is η-exp-concave and ∇2 V ≻ 0. Then we have
∇2 V −1 (x)∇V (x), ∇V (x) ≤

1
η

(47)

for all x.
Proof Since V is η-exp-concave, we have
1 2
∇ V  ∇V ∇V ⊤ .
η
Let v =

∇V
k∇V k

(48)

and R := I − vv ⊤ . For any δ > 0, we have
1 2
1
∇ V + δI  ∇2 V + δR
η
η
 ∇V ∇V ⊤ + δR

= k∇V k2 − δ vv ⊤ + δI
≻0

(49)

if δ < k∇V k2 . Using the fact that B  A ≻ 0 implies A−1  B −1 ≻ 0, we get


1 2
∇ V + δI
η

−1



15

−1
1
I + tvv ⊤
δ

(50)

Hsieh and Cevher

where t :=

k∇V k2
δ

− 1. The Sherman–Morrison formula implies


−1

I + tvv ⊤

=I−

t
vv ⊤ ,
1+t

(51)

and hence,
*

1 2
∇ V + δI
η

−1

+

∇V, ∇V


t
2
k∇V k
k∇V k −
1+t


t
1+t
2
2
k∇V k
k∇V k −
=
k∇V k2
1+t
= 1.

1
≤
δ



2

(52)

On the other hand, since ∇2 V ≻ 0, we have
*
+ *
+
−1
−1
1 2
1 2
lim
∇V, ∇V =
∇V, ∇V
∇ V + δI
∇ V
δ→0
η
η
= η ∇2 V −1 ∇V, ∇V .

The proof is hence completed by letting δ → 0 in (52).

Lemma 12 Let Vi ’s be ηi -exp-concave functions for i = 1, 2, ..., k. Then
P
concave with η1 = ki=1 η1i .

Pk

i=1 Vi

is η-exp-

Proof Let X be any random variable. Using the exp-concavity and Hölder’s inequality,
we get
η 

η
η
η
e−η(V1 +V2 )(EX) ≥ Ee−η1 V1 (X) 1 · Ee−η2 V2 (X) 2
= ke−V1 kηη1 · ke−V2 kηη2

≥ ke−(V1 +V2 ) kηη



−η V1 (X)+V2 (X)

= Ee

.

1
Here, ke−V1 kη1 := Ee−η1 V1 η1 and similarly for ke−V2 kη2 .
The general case follows from induction.

References
Sungjin Ahn, Anoop Korattikara, and Max Welling. Bayesian posterior sampling via
stochastic gradient fisher scoring. In Proceedings of the 29th International Coference
on International Conference on Machine Learning, pages 1771–1778, 2012.
16

Dimension-free Information Concentration via Exp-Concavity

David Alonso-Gutiérrez and Jesús Bastero. Approaching the Kannan-Lovász-Simonovits
and variance conjectures, volume 2131. Springer, 2015.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for
statisticians. Journal of the American Statistical Association, (just-accepted), 2017.
Sergey Bobkov, Mokshay Madiman, et al. Concentration of the information in data with
log-concave distributions. The Annals of Probability, 39(4):1528–1543, 2011.
Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from a log-concave distribution with projected langevin monte carlo. arXiv preprint arXiv:1507.02564, 2015.
Peter Bühlmann and Sara Van De Geer. Statistics for high-dimensional data: methods,
theory and applications. Springer Science & Business Media, 2011.
Olivier Catoni. PAC-Bayesian Supervised Classification: the Thermodynamics of Statistical
Learning. Institute of Mathematical Statistics, 2007.
Nicolo Cesa-Bianchi, Gabor Lugosi, and Learning Prediction. Games, 2006.
Xiang Cheng and Peter Bartlett. Convergence of langevin mcmc in kl-divergence. Proceedings of Machine Learning Research, 83, 2018.
Dario Cordero-Erausquin. Transport inequalities for log-concave measures, quantitative
forms and applications. Canadian Journal of Mathematics, 69:481–501, 2017.
Thomas M Cover and Sandeep Pombra. Gaussian feedback capacity. IEEE Transactions
on Information Theory, 35(1):37–43, 1989.
Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons,
2012.
Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and logconcave densities. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79(3):651–676, 2017.
Arnak S Dalalyan and Avetik G Karagulyan. User-friendly guarantees for the langevin
monte carlo with inaccurate gradient. arXiv preprint arXiv:1710.00095, 2017.
Arnak S Dalalyan, Edwin Grappin, and Quentin Paris. On the exponentially weighted
aggregate with the laplace prior. arXiv preprint arXiv:1611.08483, 2016.
Alain Durmus and Eric Moulines. High-dimensional bayesian inference via the unadjusted
langevin algorithm. 2016.
Simon Foucart and Holger Rauhut. A mathematical introduction to compressive sensing,
volume 1. Birkhäuser Basel, 2013.
Matthieu Fradelizi, Mokshay Madiman, and Liyao Wang. Optimal concentration of information content for log-concave densities. In High Dimensional Probability VII, pages
45–60. Springer, 2016.
17

Hsieh and Cevher

Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien. Pac-bayesian
theory meets bayesian inference. In Advances in Neural Information Processing Systems,
pages 1884–1892, 2016.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends R in
Optimization, 2(3-4):157–325, 2016.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online
convex optimization. Machine Learning, 69(2):169–192, 2007.
Shihao Ji, Ya Xue, and Lawrence Carin. Bayesian compressive sensing. IEEE Transactions
on Signal Processing, 56(6):2346–2356, 2008.
Ravi Kannan, László Lovász, and Miklós Simonovits. Isoperimetric problems for convex
bodies and a localization lemma. Discrete & Computational Geometry, 13(1):541–559,
1995.
Michel Ledoux. Spectral gap, logarithmic sobolev constant, and geometric bounds. Surveys
in differential geometry, 9:219–240, 2004.
Michel Ledoux. The concentration of measure phenomenon. American Mathematical Soc.,
2005.
László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling
algorithms. Random Structures & Algorithms, 30(3):307–358, 2007.
Hariharan Narayanan and Alexander Rakhlin. Random walk approach to regret minimization. In Advances in Neural Information Processing Systems, pages 1777–1785, 2010.
Felix Otto and Cédric Villani. Generalization of an inequality by talagrand and links with
the logarithmic sobolev inequality. Journal of Functional Analysis, 173(2):361–400, 2000.
Marcelo Pereyra. Maximum-a-posteriori estimation with bayesian confidence regions. SIAM
Journal on Imaging Sciences, 10(1):285–302, 2017.
Yury Polyanskiy. Channel coding: non-asymptotic fundamental limits. Princeton University,
2010.
András Prékopa. Logarithmic concave measures with applications. Acta Sci. Math, 32:
301–316, 1971.
Maxim Raginsky, Igal Sason, et al. Concentration of measure inequalities in information
theory, communications, and coding. Foundations and Trends R in Communications and
Information Theory, 10(1-2):1–246, 2013.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation
and approximate inference in deep generative models. arXiv preprint arXiv:1401.4082,
2014.
Christian Robert. The Bayesian choice: from decision-theoretic foundations to computational implementation. Springer Science & Business Media, 2007.
18

Dimension-free Information Concentration via Exp-Concavity

Michel Talagrand. Concentration of measure and isoperimetric inequalities in product
spaces. Publications Mathematiques de l’IHES, 81(1):73–205, 1995.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics.
In Proceedings of the 28th International Conference on Machine Learning (ICML-11),
pages 681–688, 2011.
Tong Zhang. Information-theoretic upper and lower bounds for statistical estimation. IEEE
Transactions on Information Theory, 52(4):1307–1321, 2006.

19

