Dimension-free Information Concentration via Exp-Concavity

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.


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 (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 "Poincaré inequality in this local norm", namely the Brascamp-Lieb 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.

Notations
For a function f , we write E µ f := f dµ and Var µ (f ) := f 2 dµ − f dµ 2 . We write X ∼ µ for a random variable X associated with the probability measure µ.
In this paper, the norm · is always the Euclidean norm, and we use ·, · 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.

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 (1) The random variableh(µ) =h(X) := − log f (X) is called the information content of µ.
We study the concentration of information content around the differential entropy: 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 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).

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 sub-Gaussian 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.

Previous Art
The state-of-the-art concentration bound for V is given by Fradelizi et al. (2016): e −V dx be a d-dimensional log-concave probability measure. Then, we have 1. Var(V (X)) ≤ d.
2. There exist universal constants c 1 and c 2 such that This is the main result of (Fradelizi et al., 2016) combined with the well-known relation for every t ≥ 0. The bound (3) matches the tightest known results for V = · 2 2 (i.e., the Gaussian case; see Cover and Pombra, 1989). However, notice that (3) has a poor dependence on the dimension d, as well as having the exponent being the worst case of t and t 2 d .

Our Results
We first recall the definition of exp-concave functions (Hazan, 2016): 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.

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 η.
e −V dx be the log-concave distribution associated with V . Then 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.

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.
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

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 = V 1 + V 2 , where V 1 is a "nice" convex function (meaning satisfying either the assumptions in Theorem 3 or Theorem 5), while V 2 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 V 1 in fact enjoys dimension-free concentration as if the nonsmooth term V 2 is absent.
where V 1 satisfies the assumptions in either Theorem 3 or Theorem 5, and V 2 is a general convex function. Then we have where the probability is with respect to the total measure dµ V , and η is the exp-concavity parameter of V 1 .

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 for a universal constant c 1 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 However, a straightforward computation shows that for every λ > 0. We hence cannot have any sub-Gaussian concentration for V . It is easy to generalize this example to any dimension.

Immediate Consequences
An immediate consequence of information concentration is that many important densities in information theory also concentrate.
Then there exist universal constants c 1 , c 2 such that the following holds: is strictly convex. Then the exponents in the above bounds can be improved to max( √ η, η)t.
is the conditional (differential) entropy, and 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 Prékopa (1971) states that the marginals of log-concave measures are also log-concave. The corollary then follows by the well-known decomposition

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.
Below, we consider loss functions of the form L n (x) := 1 n n i=1 ℓ i (x), where ℓ i 's are exp-concave. By Lemma 12 in Appendix A, the total loss L n is also exp-concave. Denote the exp-concave parameter of L n 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. Fradelizi et al. (2016) Ours, η = Ω(1) Ours, η = Ω 1 Table 1: The deviation P (|V − EV | > t) dictated by different concentration inequalities.

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 where π t (x) ∝ e −nLn(x) .
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 In view of these recent developments, it is natural to consider, instead of the expected prediction (7), taking samples X t,1 , X t,2 , ..., X t,N ∼ π t and predictX t := 1 N N i=1 X t,i . The following corollary of our main result establishes the desirable concentration property ofX t .
Assume that V satisfies either the assumptions of Theorem 3 or Theorem 5. Then Proof For simplicity, assume η = 1; the general case is similar. By the classic Chernoff bounding technique, we can compute 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).

Posterior Concentration of Bayesian and Pac-Bayesian Analysis
The (pseudo-)posterior distribution plays a fundamental role in the PAC-Bayesian theory: where V n (x) = L n (x) − 1 n 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 distributionŝ π (Lová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 L n (X) concentrates around EπL n (X); notice that many popular priors (uniform, Gaussian, Laplace, etc.) are log-concave. On the other hand, concentration of the empirical risk L n 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.

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 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 where x ⋆ := arg max x V n (x) is the MAP parameter, and t α = c 1 log(1/α) d for some constant c 1 . A straightforward application of our results shows that, when the data term L n in V n 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 setC where t η α = c 2 log(1/α) · n η . Comparing (12) and (13), we see that (ignoring logarithmic terms) we get improvements whenever η = Ω n d . This is typically the case in highdimensional statistics (Bü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.

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.

Proof Ideas
For a probability measure µ, we say that µ satisfies the Poincaré inequality with constant λ 1 if for all locally Lipschitz f . It is well-known that if (14) is satisfied for µ, then all the Lipschitz functions concentrate exponentially (Ledoux, 2004(Ledoux, , 2005: for some universal constant c 1 . At first glance, our theorems seem to have little to do with the Poincaré inequality, since 1. It is not known whether a log-concave distribution satisfies the Poincaré inequality with a dimension-independent constant (this is the content of the Kannan-Lovász-Simonovits conjecture; see Kannan et al., 1995;Alonso-Gutiérrez and Bastero, 2015).
2. Typically, the potential V is not Lipschitz (consider the Gaussian distribution where V (x) = x 2 2 ). Moreover, even if V is Lipschitz, the Lipschitz constant often depends on the dimension (consider the exponential distribution where ∇V = Θ( √ 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 y x := ∇ 2 V (x)y, y .
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 Poincaré inequality: e −V dx be a log-concave probability measure with V ∈ C 2 and ∇ 2 V ≻ 0. Then for all locally Lipschitz function f ∈ L 2 (µ V ), we have 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 Poincaré 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 y x := ∇ 2 V (x)y, y .

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 ) 2 , we get by Lemma 11. Let M (λ) := E exp (λ(V − EV )). Then the inequality (17) reads and hence Apply (19) recursively to obtain Since M (λ) = 1 + o(λ), we have which in turn gives The proof can now be completed by the classic Chernoff bounding technique: Now, the inequality (23) implies that for any 1-exp-concave V , we have If V is η-exp-concave, ηV is 1-exp-concave, and hence we conclude that that is to say, 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.

Proof of Lemma 4 and Theorem 5
We first prove Lemma 4.
For any point x, let {a i } k i=1 be an orthonormal basis for S + (x), assumed to have dimension k. We extend {a i } k i=1 to an orthonormal basis for R d as {a i } d i=1 , and we decompose ∇V (x) = d i=1 c i a i for some real numbers c i 's. For the purpose of contradiction, assume that ∇V (x) / ∈ S + (x). Then c j = 0 for some j ∈ {k + 1, k + 2, ..., d}. But then We now turn to Theorem 5. Let ǫ > 0 be arbitrarily small, and consider the quantity Lemma 4 implies that (25) is equal to where I S + is the identity map on the subspace S + . Since V is strictly convex restricted to S + , and since ∇V ∈ S + , Lemma 11 then implies for all ǫ > 0.
SinceṼ is strictly convex, we may invoke the Brascamp-Lieb inequality (16) to conclude where the second inequality follows from (27). Letting ǫ → 0 in (28) then gives The rest of the proof is similar to that of Theorem 3; we omit the details.

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µṼ (x) = e −Ṽ (x) e −Ṽ dx be a log-concave measure withṼ = V + U , where V ∈ C 2 , ∇ 2 V ≻ 0, and U is convex but possibly non-differentiable. Then for all locally Lipschitz function f ∈ L 2 (µṼ ), we have Proof [Proof of Theorem 10] Define the cost functions and By Proposition 1.1 of Cordero-Erausquin (2017) (see also p.482 for the non-differentiable case), we know that the measure dµṼ satisfies the transportation cost inequality: for any probability measure ν. Here, W cṼ (µṼ , ν) := inf X,Y EcṼ (X, Y ) where the infimum is over all joint distributions with marginals X ∼ µṼ and Y ∼ ν, and D(ν µṼ ) is the relative entropy between ν and µṼ . Since U is convex, we have cṼ (x, y) ≥ c V (x, y) for all x, y, and hence µṼ satisfies the weaker transportation cost inequality 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 L 2 (µṼ ), we will prove Theorem 10 for any continuous function with compact support. Notice that such functions are necessarily Lipschitz and hence differentiable µṼ -almost everywhere. Since modifying f in a set of µṼ -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 uniformly in y on any compact set when h → 0. Assume for the moment that c V (x, y) ≥ δ 2 x−y 2 for some δ > 0. Given any function g ∈ C 1 with compact support and gdµṼ = 0, introduce the infimal convolution associated with the cost c V : whence Q c (g)(y) − g(x) ≤ c V (x, y). By the definition of W c V , for any joint probability measure π having marginals µṼ and ν, we must have Consider the infimum convolution of ǫg: Let h ǫ = h ǫ (y) denote a point where the infimum is achieved. Since g is globally Lipschitz, say with constant L, On the other hand, by setting h = 0 in (37), we see that ǫg(y + h ǫ ) + c V (y + h ǫ , y) ≤ ǫg(y).
Combining this with (38) gives Notice that (39) does not depend on y, and hence h ǫ = O(ǫ) uniformly in y.

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.
where t := ∇V 2 δ − 1. The Sherman-Morrison formula implies and hence, On the other hand, since ∇ 2 V ≻ 0, we have The proof is hence completed by letting δ → 0 in (52).