Concentration inequalities and performance guarantees for hypocoercive MCMC samplers
Jeremiah Birrell Luc Rey-Bellet
math.PR









Performance Guarantees for Hypocoercive MCMC Samplers       












T1Research supported in part by the National Science Foundation (DMS-1515712) and the Air Force Office of Scientific Research (AFOSR) (FA-9550-18-1-0214).

T2Luc Rey-Bellet thanks Gabriel Stoltz and Stefano Olla for useful discussions and suggestions.

University of Massachusetts Amherst 

Department of Mathematics and Statistics,

University of Massachusetts Amherst

710 N Pleasant St
Amherst, MA, 01002, USA 

birrell@math.umass.edu, luc@math.umass.edu 





Birrell and Rey-Bellet





































  In this paper we provide performance guarantees for hypocoercive non-reversible MCMC samplers X_t with invariant measure       μ^* and our results apply in particular to the Langevin equation, Hamiltonian Monte-Carlo, and the bouncy particle and  zig-zag samplers. Specifically, we establish a concentration inequality of Bernstein type for ergodic averages 1/T∫_0^T f(X_t)  dt. As a consequence we provide performance guarantees:  (a) explicit non-asymptotic confidence intervals  for ∫ f dμ^* when using a finite time ergodic average with given initial condition μ and (b) uncertainty quantification bounds, expressed in terms of relative entropy rate, on the bias of ∫ f dμ^* when using  an alternative or approximate processes X_t. (Results in (b) generalize recent results from <cit.> for coercive dynamics.) The concentration inequality is proved by combining the approach via Feynmann-Kac semigroups first noted by <cit.> with the hypocoercive estimates of <cit.> developed for the Langevin equation and recently generalized to partially deterministic Markov processes by  <cit.>.   















[class=MSC]

60J25
47D07
39B72






concentration inequality
uncertainty quantification
hypocoercivity
Langevin equation
Bouncy particle sampler
Zig-zag sampler
Hybrid Hamiltonian Monte-Carlo










§ INTRODUCTION AND STATEMENT OF THE RESULTS



 Consider the problem of computing the  expected value 

    ν^*[f]≡∫ f(q)  dν^*(q)   with    d ν^* =  Z^-1 e^- β V(q) dq

for some given function f: 𝒬→ℝ with 𝒬⊂ℝ^d. If the normalization constant Z is unknown or prohibitive to compute, it can be advantageous to construct a ergodic stochastic process Q_t with stationary distribution ν^* (in this paper only  continuous-time processes are considered) and use the fact that, by the strong law of large numbers and for suitable f, one has

    lim_T →∞1/T∫_0^T f(Q_t)   dt  = ν^*[f] .
 
Such a process Q_t is usually called a Monte-Carlo Markov chain (MCMC) and 
we can then use the finite time average 1/T∫_0^T f(Q_t)dt as an estimator for ν^*[f]. 
There are of course multiple choices of stochastic processes with invariant 
measure ν^* and in order to decide which process  to use  we need to evaluate its performance. 


While traditional Monte-Carlo algorithms are often built to be reversible, in recent years  non-reversible algorithms have attracted a lot of attention because of their potential to sample the space in a more efficient manner, in particular in the context of Bayesian statistics and molecular dynamics   (see for example <cit.> and many more references therein).
In this paper we consider a variety of non-reversible MCMC samplers such as the Langevin equation, and various modifications thereof, as well as partially deterministic Markov processes such as the zig-zag sampler (<cit.>),  the bouncy particle sampler (<cit.>), and the hybrid Hamiltonian Monte-Carlo (<cit.>).  
Each of these samplers are  constructed by extending the phase space from 𝒬 to 𝒳 =  𝒬×𝒫 and then constructing a non-reversible MCMC in the extended phase space with an invariant measure μ^*=ν^* ×ρ^*. 
The extra dimension  𝒫 can be thought as  momentum space and the dynamics considered here combine a conservative Hamiltonian-type dynamics with a dissipative sampling mechanism for the measure ρ^* in the momentum variable p ∈𝒫. For example ρ^* may be a Gaussian distribution, although other choices are possible; we do assume ρ^* has mean zero.

All the algorithms we consider here have been proved to be hypocoercive. 
The concept of hypocoercivity was formalized by Villani  to describe dynamics 
which do not satisfy  a Poincaré inequality (otherwise they would be called coercive) but yet converge exponentially fast to equilibrium in L^2(μ^*).  In a series of work <cit.> it was proved that the Langevin equation is hypocoercive (see also <cit.> for some earlier and related convergence results). 
   A few years ago <cit.> found a new, short and very elegant, proof of hypocoercivity, and their techniques have been used for various modifications of the Langevin equation <cit.> 
   (some of them without hypoellitpicity) 
   and recently in <cit.>  for a class of partially deterministic Markov  processes, among them:
   
   
  * The bouncy particle sampler, which was introduced  in <cit.> and whose ergodic properties were studied in <cit.> and <cit.>. 
   
  * The zig-zag sampler, introduced in <cit.> and further studied 
   in <cit.>, which generalize to higher dimension the so-called telgraph process studied earlier in <cit.> and <cit.>. 
   
  * The hybrid Hamiltonian Monte Carlo introduced by <cit.> and whose ergodic properties are studied in <cit.>, see also  <cit.> and  <cit.>. 
   
   
 To explain this result,    decompose the generator A of the dynamics on the Hilbert space L^2(μ^*) into symmetric and antisymmetric parts,  
A= S+T with S^†=S, T^†=-T, denote by Π the projection of L^2(μ^*) onto L^2(ν^*) given Π(f)(q) = ∫ f(q,p) d ρ^*(p), and consider the operator 

    B= (I +  (T Π)^* (T Π))^-1 (- T Π)^*

and the family of modified scalar products ⟨  f,  g⟩_ϵ = ⟨  f, (I + ϵ G) g⟩, where G=B+B^†; here, and in the following, ⟨·,·⟩ will denote the L^2(μ^*)-scalar product. Under suitable conditions (more details are in Section <ref>)
this scalar product is equivalent to the L^2(μ^*)-scalar product and it is shown in <cit.> that, for sufficiently small values of ϵ>0, the dynamics satisfy a Poincaré inequality for the modified scalar product
    
    ⟨ - A f , f ⟩_ϵ≥Λ(ϵ)   Var_μ^*(f)  ,

where Λ(ϵ)>0 can be explicitly bounded in terms of  the Poincaré constant of the measure ν^*, the spectral gap of the sampling dynamics for ρ^*, and properties of the potential V (see Section <ref>).  





In this paper we leverage this approach to hypocoercivity to prove concentration inequalities (of Bernstein type) for finite time ergodic averages of a function (observable) f:𝒳→ℝ:

    F_T=1/T∫_0^T f(X_t)dt .

For reversible processes, or more generally for processes whose reversible part satisfies a Poncaré inequality, that is for coercive processes,  concentration inequalities were obtained  first in <cit.>   and then both simplified and greatly generalized in <cit.>; our approach relies heavily on the ideas developed in these works. 


Concentration inequalities are very useful for providing performance guarantees (e.g. confidence intervals) valid for all time T (and which do not rely on the central limit theorem).  In practice, algorithm performance is typically evaluated in terms of the asymptotic variance 

    σ^2(f) ≡lim_T →∞ T ( 1/T∫_0^T f(X_t)   dt);
 we take here the alternative point of view of using  concentration inequalities, thereby obtaining non-asymptotic performance guarantees.  In a related manner, it has been advocated in <cit.> that, to evaluate the performance of a MCMC algorithm,  one consider the large deviation rate for the empirical measure itself, an approach used in <cit.> to analyze  non-reversible perturbations of the overdamped Langevin equation. 

We prove the following non-asymptotic performance guarantee in Section <ref> (see Corollary <ref>). Here, and in the following, (X_t,P^μ) will denote a 𝒳-valued Markov process with initial distribution X_0 ∼μ (i.e. (X_0)_*P^μ=μ), E^μ will be the expectation with respect to P^μ, and  · will denote the L^2(μ^*)-norm.

(Non-asymptotic confidence intervals)
Suppose that the Markov process (X_t,P^μ) satisfies the hypocoercive estimate (<ref>). Then for any bounded observable f, any time T>0, and tolerance level 0< 1-δ < 1  
we have 

    P^μ( | 1/T∫_0^Tf(X_t)dt-μ^*[f]| ≤ r )≥ 1-δ ,

where    

    r =√(2 v 1/Tlog(2N/δ)) + b
    1/Tlog(2N/δ) ,

with 

    v= (1+ϵ) (1 - ϵ^2/4)/1-ϵ2 _μ^*[f]/Λ(ϵ) ,    b =  (1+ϵ)^2/1-ϵf_∞/Λ(ϵ) ,  N = dμ/dμ^*/√(1-ϵ) .

Λ(ϵ) is defined in Lambda_m_def and ϵ must satisfy eq:Lambda_pos.



We also prove a robustness result for the dynamics, with respect to model-form uncertainty. For such uncertainty quantification (UQ) bounds, we think of (X_t,P^μ), called the baseline model, as an imperfect representation of a “true" (or at least, more precise) alternative model. This alternative model may not be fully known, or it might be intractable (analytically or numerically), and so one may want to investigate how sensitive the results for the baseline model are to (not necessarily small) model perturbations. The next theorem provides such performance guarantees, generalizing the results in <cit.>, and is based on the general approach to uncertainty quantification developed in <cit.>.  In this context, the goal is to control the bias 

    E^μ[ 1/T∫_0^Tf(X_t)  dt ] - μ^*[f] ,

where  (X_t,P^μ) with X_0 ∼μ 
is the alternative model and E^μ is the expectation with respect to P^μ.   We denote by P^μ_T and P_T^μ  the path-space  distributions of the base and alternative models on the time window [0,T] and  prove the following result in Section <ref> (see Theorem <ref>). 







(Uncertainty quantification bounds)  
Suppose that the baseline Markov process X_t satisfies the hypocoercive estimate (<ref>) and (X_t,P^μ) is a stochastic process such that the path space relative entropy satisfies

    R ( P_T^μ||P_T^μ^*) <∞ .
	
Then we have    

    | E^μ[ 1/T∫_0^Tf(X_t)   dt   ] - μ^*[f] |
    ≤   √( 2 v η_T)+  bη_T  ,
  
where v and b are given in (<ref>),  and 

    η_T =1/T(log((1-ϵ)^-1/2)+  R(P^μ_T||P^μ^*_T) ) .


















































The remainder of this paper is organized as follows.  In Section <ref>
we review several examples of hypocoercive systems to which our results apply.  There, we also give an overview of the hypocoercivity method of <cit.>.  This method is a crucial tool in the proofs of our new results, namely the concentration inequalities and UQ bounds outlined above; proofs of these are given in Section <ref>.










§ HYPOCOERCIVE MCMC SAMPLERS
  
 
In this section we introduce several examples of popular hypocoercive samplers for which the modified Poincaré
inequality (<ref>)  has been proven by following the strategy of <cit.>. 
In particular we consider several examples of partially deterministic MCMC samplers studied in the recent paper <cit.>. 
 We will refer the  reader to the original papers for technical details  and content ourselves with a brief, and at times somewhat informal, overview:

Consider a probability measure d ν^*(q)=Z^-1 e^-β V(q)dq on 
ℝ^d to be sampled, and for which a Poincaré inequality holds, i.e., there exists a constant C_ν^*>0 such that for all for g ∈ L^2(ν^*)  

    ∇_q g ^2_L^2(ν^*)≥ C_ν^*_ν^*[g] .

See e.g. <cit.> for conditions on V which imply   a Poincaré inequality. 

Define the product measure μ^*= ν^*×ρ^* 
on the extended phase space ℝ^d × E   and  the projection Π f  = ∫ f dρ^*.  
We consider a Markov processes X_t=(Q_t,P_t) on  ℝ^d× E 
with invariant measure μ^* and assume standard smoothness and growth conditions on V to ensure that X_t  induces a strongly continuous semi-group 𝒫_t on L^2(μ^*) with generator A, and with the time-reversed process having generator  given by the adjoint A^† of A on L^2(μ^*).  We decompose A into symmetric and  antisymmetric parts: 

    A = S+T,     with    S= A + A^†/2 and      T= A - A^†/2 .


The following  four examples  fit within this framework and that will be used to illustrate the utility of our results; see <cit.>  for a proof of hypocoercivity of a more general class of models which covers all examples considered here,  
as well as <cit.> for further examples (some of them being non-equilibrium as well). 



  * (Langevin and modified Langevin equations) The (underdamped) Langevin equation is the system of stochastic differential equations on ℝ^2d given by 

    dQ_t=P_t/mdt,     
    dP_t=(-∇ V(Q_t)-γP_t/m)dt+√(2γ/β) dW_t,

where m>0 is the mass, β>0 is proportional to the inverse temperature, γ>0 is the drag coefficient,  W_t is a Wiener process, and V:ℝ^d→ℝ is a smooth potential. The appropriate  ρ^* is a Gaussian measure with mean 0 and covariance matrix m/β I.  
The generator A is an extension of the differential operator 

    A = 	γ/βΔ_p - γ(p/m)^T ∇_p_=S + ( p/m)^T ∇_q-∇ V(q)^T∇_p_=T .

This is the model originally considered in <cit.>
and several  modifications of this models have also been shown to be hypocoercive. For example <cit.> consider a Langevin equation with a modified kinetic energy (non-quadratic) so that that ρ^* is not Gaussian and the diffusion needs not be hypoelliptic.  Further generalizations of the Langevin equations with general ρ^* are also considered in <cit.>. 



  * (Hybrid Hamiltonian Monte Carlo)  In this randomized version of Hamiltonian Monte-Carlo  introduced by <cit.>, 
 the system follows Hamiltonian equations  of motion  with Hamiltonian V(q) + p^2/2m for an  exponentially distributed amount of time, after which the momentum is resampled from the Gaussian measure ρ^*.  The generator has the form 

    A     =  λ(Π - I )_=S + ( p/m)^T ∇_q-∇ V^T∇_p_=T .



  * (Bouncy Particle Sampler)  In this sampler, introduced originally in <cit.>, a particle starting at time t_0 in the state (q_0,p_0) moves freely  p(t)=p(t_0) and q(t) =q(t_0) + t p(t_0)/m  up to the random time t_0 + τ. The updating time τ is governed by two mechanisms: either the velocity of the particle is refreshed,  i.e.,  p is sampled from the Gaussian ρ^* (this occurs at rate λ), or the particle “bounces", i.e., it undergoes  a Newtonian elastic collision on the hyperplane tangential to the gradient of the energy and  the momentum is updated according to 
the rule 

    R(q) p =  p  -   p^T ∇ V(q)    /∇ V^2∇ V  .

The time at which this happens is   governed by an inhomogeneous Poisson process of intensity 
λ(q,p) =   [( p/m)^T  ∇ V(q)]^+. 
If we set R f( q,p)  =  f(q, R(q) p)  then the generator is 

    A     =  (p/m)^T ∇_q    +    [( p/m)^T  ∇ V(q)]^+  (R - I)   + λ (Π - I)  ,

and elementary computations shows that μ^*=ν^*×ρ^* is invariant 
and  





    S    =    |( p/m)^T  ∇ V(q)|  (R - I)  +  λ(  Π - I )   , 
    
    T   =   ( p/m)^T ∇_q  +    ( p/m)^T  ∇ V(q) (R - I)    .



  * (Zig-Zag Sampler)  In the zig-zag sampler, contrary to the other examples, the velocity is discrete, and, for example, ρ^* is the uniform 
distribution on {-1,1}^d.  As in the bouncy sampler, the trajectories are piecewise linear.  At updating  times,  the (randomly chosen) i'th component 
of the velocity is reversed; see  <cit.> for a more detailed discussion. The generator of the Markov process has the form 

    A =   v^T ∇_q    +    ∑_i=1^d  [  v_i ∂_q_i V(q)]^+  (R_i - I)   + λ (Π - I)   ,

where R_i f(q,v) = f(q, v - 2 (e_i^T v) e_i) (with e_i the standard basis vector in ℝ^d). A computation similar to the one for the bouncy sampler shows that 

    S    =    ∑_i=1^d |  v_i   ∂_q_i V (q) |  (R_i - I)  +  λ(  Π - I )   , 
    
    T   =   v ∇_q  +    ∑_i=1^d   v_i ∂_q_i V(q)  (R_i - I)    .





Note  that for all the examples considered, it is easy to verify that 
one has the identity 

    T Π = p/m∇_q Π

(with the convention that p/m=v for the zig-zag sampler). 
This fact is used to establish the following functional analytic estimates (see <cit.>)   which are the basis for the hypocoercive estimates (for the convenience of the reader the proof is in Appendix <ref>).   













Define

    B= (I +  (T Π)^* (T Π))^-1 (- T Π)^*  .

The operators S,  T, and B have the following properties:


  * B1 = B^†1 = 0,

  * S = (I -Π) S (I- Π),

  * T Π = (I- Π) T Π,

  * B = Π B = Π B (I - Π)  and B and TB are bounded operators with Bf ≤ 1/2  (I - Π) f and T B f ≤ (I - Π) f. 


 
 Next, define the family of modified scalar products on L^2(μ^*),  
 
    ⟨ f , g⟩_ϵ=⟨ f, g⟩ + ϵ⟨ f ,(B+B^*) g⟩ ,    ϵ∈ (0,1) .

As B≤ 1/2,  ⟨· ,  ·⟩_ϵ is an inner product which  is equivalent to ⟨· ,  ·⟩. 
As a consequence of Lemma <ref> one obtains for suitable
f with μ^*[f]=0:

    ⟨ A f ,   f ⟩_ϵ
    =   ⟨ S f ,  f ⟩ + ϵ[ 
    ⟨ B S f,f ⟩  +  ⟨  B T  f,f  ⟩  +  ⟨ S B f ,   f ⟩ -  ⟨ T B f , f ⟩]   
    
    =   ⟨  (S - ϵ TB) (I-Π)f ,  (I-Π)  f ⟩  + ϵ⟨ B T Π  f ,  Π f ⟩
        + ϵ[ ⟨ B S (I-Π) f ,  Π f ⟩  +  ⟨ B T (I-Π) f ,  Π f ⟩]  ,

where we have used that SB=0.   The various terms in (<ref>) 
can be bounded as follows:


  * The term ⟨ (S-ϵ TB) (I-Π)f ,  (I-Π) f⟩ is controlled by the dissipative term in the p-variables (since TB is bounded) and it is not difficult to see that in the cases considered here we have a Poincaré inequality in the p-variables (averaged over ν^*):

    ⟨ f , -S  f ⟩≥λ_p (I-Π) f^2

for some λ_p>0. For the Langevin equation λ_p=γ/β is the spectral gap of the Ornstein-Uhlenbeck process, while for the other examples we can take λ_p=λ from the velocity resampling mechanism.  

  * For the term ⟨ B T Π  f ,  Π f ⟩, note that using (<ref>) together with the Poincaré inequality for the measure ν^*, we have 
 
    ⟨   f , (TΠ^† TΠ) f ⟩ =  Π(p^2/m^2) 
    	 ∇_q Π f≥Π(p^2/m^2) C_ν^* Π f^2     ,
	
where C_ν^* is the Poincaré constant for the measure ν^*. Then, since
 - BTΠ = (I+(TΠ)^† TΠ)^-1 (TΠ)^† TΠ, by 
functional calculus we have  

    ⟨ -BTΠ f, Π f ⟩≥( 1 - (1 + Π(p^2/m^2) C_ν^*)^-1)Π f ^2 ≡λ_q Π f ^2 .






  * For the off-diagonal terms it is enough to show that they are bounded, i.e., 

    BT(I - Π)f + BS(I - Π)f≤ R_0(I- Π)f .

The bound of the first term is the technical part of the proof; for the Langevin equation this is proved in <cit.>, and is generalized in <cit.> for the other samplers (see Lemma 29 and Lemma 32 in particular and the bound in Section 3.3 as well as the bound in Lemma 11 which is specific to the zig-zag sampler).

 






Based on these estimates, one has constants λ_q,λ_p,R_0≥ 0 such that for any f with μ^*[f]=0:

    ⟨ -A f ,  f ⟩_ϵ    ≥ [    Π f; (I-Π)f ]^T[     ϵλ_q -ϵ R_0/2; -ϵ R_0/2    λ_p-ϵ ][    Π f; (I-Π)f ]
       ≥Λ(ϵ) _μ^*[f]  ,

where  

    Λ(ϵ)≡(λ_q-1)ϵ+λ_p -√((( λ_q+1)ϵ-λ_p )^2+ϵ^2 R_0^2)/2
 is the smallest eigenvalue  of the matrix in eq:matrix-hypo; Λ(ϵ) is positive if  

    0<ϵ≤ 4 λ_q λ_p /( 4 λ_q + R_0).


In the next section, we  show how the Poincaré inequality (<ref>) for the modified inner product (<ref>) can be used to derive non-asymptotic confidence intervals and UQ bounds for hypocoercive systems, having in mind the four examples outlined above.







































































































































































































































































































































































































































































































  

 
 























§ CONCENTRATION INEQUALITIES AND PERFORMANCE GUARANTEES VIA FEYNMANN-KAC SEMIGROUPS
  
In this section, we prove our main new results for hypocoercive systems:


  * A concentration inequality and corresponding non-asymptotic confidence intervals in Section <ref>.

  * UQ bounds in Section <ref>.

  The former are obtained by an adaptation of the technique from <cit.> and <cit.> to hypocoercive systems, which we first summarize.



 §.§ Background


As in <cit.>, we will prove Bernstein-type concentration inequalities.  The following related  elementary facts will be used repeatedly (see e.g. the discussion of sub-gamma random variables in Chapter 2 in <cit.>):

Consider the convex function Ψ_v,b given by 

    Ψ_v,b(λ)     = λ^2 v/2(1-λ b)   for  0 ≤λ < 1/b  .

Its (one-sided) Legendre transform  Ψ_v,b^* is 

    Ψ_v,b^*(r)     =sup_0≤λ < 1/b{λ r - Ψ_v,b(λ)} 
    = 2 r^2/v (1 + √(1 + 2br/v))^2  for  r ≥ 0

and the inverse of the Legendre transform  Ψ_v,b^*  is 

    (Ψ_v,b^*)^-1(η)     = inf_λ>0{Ψ_v,b(λ)+ η/λ} = √(2 v η) + b η  for η≥ 0   .


 



Now we summarize the method of <cit.>:

Let 𝒳 be a Polish space  and suppose we have  time homogeneous, 𝒳-valued, càdlàg Markov processes  (Ω,ℱ,ℱ_t,X_t,P^x), x∈𝒳, with initial distributions (X_0)_*P^x=δ_x for all x.  For an initial measure μ, write P^μ = ∫ P^x  dμ(x).    


We assume that μ^* is an invariant ergodic measure on 𝒳 
consider the real Hilbert space L^2(μ^*)  with scalar product 
⟨·, ·⟩.
We consider  the strongly continuous Markov semigroup 
𝒫_t^V:L^2(μ^*)→ L^2(μ^*) given by 

    𝒫_t f(x)=E^x[f(X_t)]

and whose generator we denote by (A,D(A)).   

More generally, for a bounded measurable V:𝒳→ℝ, 
define the Feynman-Kac semigroup 
𝒫_t^V:L^2(μ^*)→ L^2(μ^*) by

    𝒫_t^V[f](x)=E^x[f(X_t)e^∫_0^t V(X_s)ds],

which is a strongly continuous semigroup with generator (A+V,D(A)).  
If  we set

    κ(V)≡sup{⟨ (A+V)g,g⟩:g∈ D(A), g =1}
 
then, by definition (and as long as κ(V)<∞), for any g ∈ D(A)  we have 

    ⟨ (A + V - κ(V)) g  ,  g ⟩≤ 0
 
and thus by the Lumer-Philipps theorem (see e.g. Chapter IX in <cit.>)  the semigroup generated by   A + V - κ(V) is a contraction semigroup on L^2(μ^*).  This implies that

    𝒫_t^V ≤  e^t κ(V) ,   t≥ 0

(note that eq:Kac_semigroup_bound also trivially holds if κ(V)=∞). Therefore by the Chernov bound we have 

    P^μ(1/T∫_0^T f(X_t)dt-μ^*[f]>r)
       ≤inf_λ >0 e^-λ T r E^μ[e^λ∫_0^T  f(X_t) dt]   
       ≤inf_λ >0 e^-λ T r∫𝒫_T^λf(1) dμ
       ≤inf_λ>0 e^-λ T rdμ/dμ^*𝒫_T^λf
       ≤dμ/dμ^* e^-Tsup_λ>0{λ r- κ(λf)} .

This basic insight, first noted by <cit.>, can also be extended to unbounded V.  From here, one can obtain explicit concentration inequalities 
by  further bounding κ(λf) (which contains the Dirichlet form  ⟨ A g  ,g⟩)  using  L^2(μ^*)-functional inequalities, such as a Poincaré inequality  (or log-Sobolev inequalities, Lyapunov functions, and so on...);  see <cit.> for many such examples.  
























 §.§ Concentration inequalities


In the hypocoercive  examples considered in this paper, the generator is non-reversible and there is no Poincaré inequality with 
respect to the L^2(μ^*)-scalar product  but, as discussed in Section 2, there is  a Poincaré inequality for an equivalent modified scalar product.  In the following theorem, we show that one still obtains concentration inequalities in this more general setting. 


(Concentration inequalities). Let (Ω,ℱ,ℱ_t,X_t,P^x), x∈𝒳, be  𝒳-valued càdlàg Markov processes  with invariant ergodic measure  μ^*. 

Let ⟨·,·⟩_# be an inner product on L^2(μ^*) such that 


  * The induced norms ·_# and · are equivalent:  there exists  
 0<c≤ C<∞ such that c·≤·_#≤ C·. 

  * For all g∈ L^2(μ^*),  we have  ⟨ g,1⟩_#=⟨ g,1⟩. 

  * A Poincaré inequality holds for ⟨·,·⟩_#, i.e.,  we have α>0 such that

    g_#^2≤α⟨ -Ag,g⟩_#     for all g∈ D(A) with μ^*[g]=0.

 
For bounded f, let M_f denote the multiplication operator 
with f=f - μ^*[f].  We have the following concentration inequalities for T>0:

    P^μ(±[ 1/T∫_0^T f(X_t)dt-μ^*[f]]≥ r)≤ c^-1dμ/dμ^* e^-T Ψ^*_v_±, b_±(r) ,

where Ψ^*_ν, b is given in (<ref>) and 














 
    v_±= 2 α1/2(M_± f+M_±f^†)1_#^2 ,      b_± = αmax{0, sup_g_#=1⟨ M_±fg,g⟩_#} .









We emphasize that M_f^† is the adjoint with respect to the ⟨·,·⟩_#-inner product.  Also ν_± and b_± can be replaced by any upper bounds on these quantities, for example in terms  of the L^2(μ^*)-norm (see the calculation for the hypocoercive examples in Section <ref> below). 


  The proof is a modification of  the  strategy used in <cit.>.  We start as in  L2_concentration_ineq but use the Lumer-Phillips theorem  for the  ·_# norm instead since, by equivalence of the norms, 𝒫^λf_t is also a strongly continuous semigroup on (L^2(μ^*),·_#) with the same generator.  Using the Chernov bound, the equivalence of the norm and the fact that, by Assumption 2, 1_# = ⟨ 1, 1 ⟩_# =⟨ 1, 1 ⟩ =1, we obtain

    P^μ(1/T∫_0^T f(X_t)dt ≥μ^*[f]+r)
         ≤inf_λ >0 e^ -λ Tr E^μ[ e^λ∫_0^T f(X_t)dt] 
        = inf_λ >0 e^ -λ Tr∫𝒫^λf_T(1)dμ/dμ^*dμ^*
       ≤inf_λ > 0 e^ -λ Trdμ/dμ^*𝒫^λf_T(1)
       ≤inf_λ >0 e^ -λ Trdμ/dμ^* c^-1𝒫^λf_T_#1_#
       ≤ c^-1dμ/dμ^* e^-T sup_λ> 0 ( λ r - κ_#(λf) ,

where,  by the Lumer-Phillips Theorem applied to L^2(μ^*) with the scalar product ⟨·, ·⟩_#,  

    κ_#( λf )≡sup{⟨ (A+ λf)g,g⟩_# : g∈ D(A),g_#=1}.












Next we use  the following lemma proved in <cit.>, which is a generalization of a result in 
<cit.>, which itself was a simplification of the argument originally used in <cit.>.  For completeness, the proof is given in the appendix.  


Let H be  a real Hilbert space, A:D(A)⊂ H→ H a linear operator, and M:H→ H a bounded linear operator.  
Assume there exists α>0 and x_0∈ H with x_0=1 such that

    ⟨ Mx_0,x_0⟩=0    and    ⟨ Ax,x⟩≤ - α^-1P^⊥ x^2

for all x∈ D(A), where P^⊥ is the orthogonal projector onto x_0^⊥.
Then    

    sup_x∈ D(A),x=1⟨ (A+λ M)x,x⟩≤λ^2 α V/1- λα K = Ψ_2α V, α K(λ)

for 0≤λ < 1/α K, where 

    V = 1/2(M+M^†)x_0^2  ,    K=max{0, sup_y=1⟨ My,y⟩} .




To use this result we take x_0=1, A to be the generator on  (L^2(μ^*),·_#), and M=M_f. By Assumption 2, we have 
⟨ Mx_0 , x_0⟩_#=⟨f , 1 ⟩_# =⟨f , 1 ⟩ =0.  This assumption also implies that 
 the projection onto 1^⊥ (for both  scalar products) is given by P^⊥ f = f and 
 
    ⟨ Ag,1⟩_#=⟨ Ag,1⟩=0,    g∈ D(A).

  Combined with Assumption 3 and the fact that A[1]=0  we get 

    ⟨ Ag,g⟩_#=   ⟨ Ag,g⟩_#≤ -α^-1g^2_#=-α^-1P^⊥ g^2_#,

and thus we can apply Lemma <ref> to obtain 

    κ_#(λf)=sup_g∈ D(A),g_#=1⟨ (A+λf)g,g⟩_#≤Ψ_v_+,b_+(λ)

for all 0≤λ< 1/b_+,  where

    v_+=2 α1/2(M_f+M_f^†)1_#^2 ,   b_+ = αmax{0, sup_g_#=1⟨ M_fg,g⟩_#}

 (as was given in (<ref>)).  Therefore 

    P^μ(1/T∫_0^T f(X_t)dt ≥μ^*[f]+r)    ≤ c^-1dμ/dμ^* e^ - T sup_0≤λ<1/b_+{λ r - Ψ_v_+,b_+(λ)}
        = c^-1dμ/dμ^* e^ - T Ψ^*_v_+,b_+(r) .

The lower bound is obtained by replacing f by -f and this concludes the proof. 

































































































































































































































































As an immediate corollary we obtain a  non-asymptotic confidence interval. 

(Confidence intervals).
Under the same assumptions as in Theorem <ref>,
given a time T and a confidence level 0 < 1-δ < 1 we have 

    P^μ(1/T∫_0^Tf(X_t)dt-μ^*[f]∈(-r_-,r_+))≥ 1-δ

where    

    r_± =√(2 v_±1/Tlog(2N/δ)) + b_±1/Tlog(2N/δ) ,





with N = c^-1dμ/dμ^* and v_± and b_± given in (<ref>).


 Define  η= 1/Tlog( 2N/δ) (note that N≥ 1 follows from Assumptions 1 and 2 of Theorem <ref>), so that r_± = (Ψ^*_v_±,b_±)^-1(η), with r_±  given as in (<ref>).  Using r=r_± in the concentration bound in Theorem <ref> we  find 

    P^μ(±[1/T∫_0^Tf(X_t)dt-μ^*[f]] ≥ r_±) ≤  N e^- T η=δ/2.

The result (<ref>) then follows from a union bound.
































 


 §.§ Robustness bounds on steady state bias due to model form uncertainty


Following on the recent results in <cit.>, we also use  
concentration inequalities to obtain bounds on the bias of the expectation of  
ergodic averages when the process itself is subject to (model-form) uncertainty. 


We think of  the Markov process (X_t,P^μ) considered in Section 
<ref> as the baseline process and consider  
an alternative stochastic process (X_t,P^μ) with initial distribution (X_0)_*P^μ=μ and let E^μ be the associated expectation.  

The requirements on the alternative process are very minimal.  In particular, we are not assuming (X_t,P^μ) is a Markov processes.

 We will compare the two processes using relative entropy; we  assume absolute continuity of the path-space distributions on  finite time windows [0,T], i.e., P^μ_T≪ P^μ_T, and also assume the relative entropy is finite:
 
    R(P^μ_T||P^μ_T) < ∞ .

See the supplementary material to <cit.> for a collection of techniques that can be used to bound  the path-space relative entropy (<ref>) for various classes of alternative models.

Given an observable f we consider the ergodic averages 
 
    F_T= 1/T∫_0^T f(X_t) dt  ,     F_T= 1/T∫_0^T f(X_t) dt ,

and are interested in bounding the bias 
between the baseline and the alternative processes:

    Bias:  E^μ[F_T] - E^μ[F_T]  .

























(Uncertainty Quantification bounds).
Let (X_t,P^x), x∈𝒳, be a family of Markov process satisfying the assumptions of Theorem <ref>, μ be an initial distribution, and  (X_t,P^μ) be an alternative process with 
R(P^μ_T||P^μ_T) < ∞.  Then for any bounded measurable f we have

    ±( E^μ [ F_T] - E^μ [F_T ])  ≤   √( 2 v_±η_T)+  b_±η_T   + C/c1-e^-α T/Td μ/dμ^* Var_μ^*[f] ,

where v_± and b_± are given in (<ref>) and 

    η_T =1/T(log(c^-1)+ logd μ/dμ^* +  R(P^μ_T||P^μ_T) ) .

If, in addition, the process (X_t,P^μ) is ergodic with invariant measure μ^*,  the limit

    η_∞ =  lim_T→∞1/T R(P^μ_T||P^μ^*_T)

exists for the relative entropy rate, and dμ/dμ^*<∞, then we have the steady-state bias bound 

    ±( μ^* [f]  -  μ^* [f] )    ≤√( 2 v_±η_∞)+ b_±η_∞ .





 The proof proceeds along the same line as in <cit.> to which we refer for more details.   
The starting point is the Gibbs information inequality 
<cit.>:  for g bounded and measurable and  
probability measures  Q and Q

    ±(  E_QE[g]-E_Q[g]) ≤inf_λ >0{log E_Q[e^±λ 
    (g - E_Q[g])]  +R(Q ||Q)/λ} .
 




This is a direct consequence of the Gibbs variational principle for the relative entropy, <cit.>. 

We apply the bound to the measures P^μ_T,  P^μ_T (distributions on path-space up to time T) and  g(x)=∫_0^T f(x_t) dt (a bounded measurable function of paths, x, up to time T) and then divide both sides by T: 

    ±( E^μ [ F_T] -  E^μ [F_T ] ) 
    
          ≤inf_λ >0{log E^μ[ e^±λ T(F_T-E^μ[F_T]]  +R(P^μ_T||P^μ_T) /λ T}
          ≤inf_λ >0{log E^μ[ e^±λ T(F_T-μ^*[f]]  +R(P^μ_T||P^μ_T) /λ T}_=(I)∓(E^μ[F_T] - μ^*[f])_=(II) .
    
The term (II) only involves the baseline process and is easily bounded, for example using the  Poincaré inequality for the scalar product ⟨·,·⟩_ϵ:

    |(II)|= | E^μ[ 1/T∫_0^T f(X_t)   dt]  | 
       ≤1/T∫_0^T |⟨d μ/dμ^*,𝒫_t f⟩|dt  
       ≤1/T∫_0^T e^-t/αd μ/dμ^*C/cfdt 
        =C/c1-e^-T/α/T/αd μ/dμ^*√( Var_μ^*[f]) .

To bound the term (I),  we use Lemma <ref> to bound the moment generating function, similarly to the proof of Theorem <ref>:

    (I)      = inf_λ >0{log∫𝒫^±λf_T (1)dμ  +R(P^μ_T||P^μ_T) /λ T}
       ≤inf_λ >0{log( c^-1dμ/dμ^*  e^ T κ_#(±λf))       +R(P^μ_T||P^μ_T) /λ T}
          =  inf_λ >0{κ_#(±λf) + η_T/λ}
       ≤inf_λ >0{Ψ_v_±,b_±(λ) + η_T/λ}
       = (Ψ_v_±,b_±^*)^-1(η_T) = √(2 v_±η_T) + b_±η_T  .

Finally, by taking  T →∞ we obtain  the  bounds in ModPoincare_UQ_bound_infinity








 §.§ Application to hypocoercive samplers


Theorems <ref> and <ref> 
for hypocoercive MCMC samplers follow rather immediately from Corollary <ref> and from Theorem <ref>.
We first verify the three assumptions in Theorem <ref>. 
The modified scalar product  is ⟨ f , g ⟩_ϵ = 
⟨ f , g ⟩ + ϵ⟨ f , G g ⟩ 
with G1=0 and G≤ 1. Therefore we  
we have  c=(1-ϵ)^1/2, C=(1+ϵ)^1/2, and 
⟨ f  ,  1 ⟩_ϵ =  ⟨ f  ,  1 ⟩,
and, for ϵ>0 sufficiently small (see eq:Lambda_pos), by eq:matrix-hypo we have α=1+ϵ/Λ(ϵ).  

Since ⟨ M_fg,g⟩_ϵ≤f_∞g^2 (1+ ϵ) ≤1+ϵ/1-ϵf_∞g^2_ϵ 
we have 

    b_± = αmax{0, sup_g_ϵ=1⟨ M_±fg,g⟩_ϵ}≤(1+ϵ)^2/1-ϵf_∞/Λ(ϵ) .
    
Furthermore, using self-adjointness of G, we have 

    M_f^†=    (I+ ϵ G)^-1M_f(I+ ϵ G) 
    = M_f + ϵ (I+ ϵ G)^-1 (M_fG -GM_f),

and thus, since G1=0,

    1/2(M_f+M_f^*)1=f-ϵ/2 (I+ϵ G )^-1 Gf .

Therefore

    1/2(M_f+M_f^*)1_ϵ^2
       = 
    ⟨ (I-ϵ/2 (I+ϵ G )^-1 G)f ,  (I+ ϵ G)  (I-ϵ/2 (I+ϵ G )^-1 G) f⟩
       =⟨ (I-ϵ/2 (I+ϵ G )^-1 G)f ,  
    (I+ ϵ/2 G) f⟩
       ≤(1 + ϵ/21/1 - ϵ)(1 + ϵ/2)  
    f^2 = 1 - ϵ^2/4/1-ϵ Var_μ^*[f] ,

and so 

    v_±≤ (1+ϵ) (1 - ϵ^2/4)/1-ϵ2 _μ^*[f]/Λ(ϵ) .


































































































































































































































































































































































































































































  

 
 











 

































































































































































§ SOME PROOFS



 §.§ Proof of Lemma <ref>




Let x∈ D(A) with x=1.  Define a =⟨ x_0,x⟩ so that    
P^⊥ x^2=1-|a |^2 and |a |≤ 1 with equality if and only if P^⊥ x=0. We can decompose x=a  x_0+√(1-|a |^2)v, where: (a) P^⊥ x=0, |a|=1, and v=0 or (b) P^⊥ x≠ 0, v=P^⊥ x/√(1-|a|^2),and v=1.   In either case, v⊥ x_0. 

Using 
⟨ Mx_0,x_0⟩ =0 and ⟨ A x , x⟩≤ -  α^-1P^⊥ x 
we obtain  

    ⟨ (A+ λ M)x,x⟩
    
       ≤   - α^-1 (1-|a |^2) +2λ a √(1-|a |^2)⟨ v, 1/2 (M + M^†) x_0⟩ +λ (1-|a|^2) ⟨ Mv,v⟩
       ≤   2λ |a| √(1-|a|^2) V^1/2 -(1-|a |^2) ( α^-1-λ K) ,
	
where V=1/2 (M + M^†) x_0^2 and K = max{0, sup_v=1⟨ Mv,v⟩}.  
Restricting to 0≤λ  <1/α K and using |a|≤ 1  we can estimate 

    sup_x∈ D(A),x=1⟨ (A+λ M)x,x⟩≤   sup_r≥ 0(2λ V^1/2 r-(α^-1-λ K )r^2)=λ^2 α V /1-λα K .








 §.§ Proof of Proposition <ref>


   The first property follows from A 1=A^†1=0 and Π1=1.



For (2),  it easy to verify that  SΠ =0 and taking adjoint gives Π S=0.   

For (3), note that  T Π f = v ∇_q Π f and thus 
Π T Π f =  Π (v  ∇_q Π f) =  (∇_q Π f ) Π v =0 (since the velocity v has mean zero).  

For (4), note that  by (3) we have Π T Π =0 and thus B Π  =0.  On the other hand, by definition of B we have the identity 

    Bf +  (T Π)^* (T Π) Bf =  Π T f  ,

and thus Π B = B. 

Taking the scalar product of eq:id01 with Bf and using Π B=B and T Π = (I - Π) T Π we obtain 

    ⟨ Bf ,  Bf⟩ + ⟨ T Bf, TBf ⟩    = ⟨ - T B f   ,  (I - Π) f ⟩
       ≤ ( I- Π)f  TB f
       ≤1/4 ( I- Π)f ^2 +     TB f^2  .

The last inequality gives Bf ≤1/2 ( I- Π)f while the first inequality gives TB f≤ ( I- Π)f.






plain


