\section{Introduction}

 
\subsection{Log-concave statistical models \label{sec:log-concave-model}}

In this paper, we consider a statistical model $(\mathbb{P}_{\theta})_{\theta \in \mathbb{R}^d}$ parametrized by a parameter $\theta \in \mathbb{R}^d$. 
We assume that each distribution $\mathbb{P}_{\theta}$ defines a probability measure on   $(\mathbb{R}^q,\mathcal{B}(\mathbb{R}^q))$
and that all the distributions $\mathbb{P}_{\theta}$ are absolutely continuous with respect to the Lebesgue measure $\lambda_q$, we denote by $\pi_\theta$ the corresponding density:

$$
\forall \xi \in \mathbb{R}^q \qquad 
\pi_\theta(\xi):=\frac{\text{d}\mathbb{P}_{\theta}}{\text{d}\lambda_q}(\xi).
$$
We assume that we observe  $n$ i.i.d. realizations $(\xi_1,\ldots,\xi_n)$, sampled according to  $\mathbb{P}_{\theta^{\star}}$  where $\theta^{\star}$ is an unknown parameter. We are then interested in Bayesian statistical procedures designed to recover $\theta^\star$.
In all the paper, we restrict our study to the specific class of \textit{log-concave models} where the distributions are described by:
\begin{equation}\label{eq:ptheta}
\pi_{\theta}(\xi) :=  e^{-U(\xi,\theta)},
\end{equation} where  {$(\xi,\theta) \longmapsto U(\xi,\theta)=- \log(\pi_{\theta}(\xi))$} is assumed to be a convex function.
 Note that implicitly, the normalizing constant 
$
Z_{\theta} := \int_{\mathbb{R}^q} e^{-U(\xi,\theta)} \text{d}\xi
$
is assumed to be equal to $1$, which is not restrictive up to a modification of $U$.

 
{Besides the Gaussian toy model that trivially fall{s} into our framework, log-concave statistical models have a longstanding history in a wide range of applied mathematics and it seems almost  impossible to  enumerate exhaustively the range of possible applications.
 {For instance, the log-concave setting appears} with exponential families thanks to the
Pitman-Koopman-Darmois Theorem, in  extreme value theory, tests (chi-square distributions), Bayesian statistics among others.  Log-concave distributions also play a central role in probability and functional analysis (\cite{Poincare_log_concave,Bobkov-aop}), or geometry (see \textit{e.g.} \cite{KLS}). 
 The log-concave property is commonly used in economics (for example the density of customer's utility parameters is generally assumed to  satisfy this property \cite{Bagnoli_economics}), 
in game theory (see \textit{e.g.} \cite{Caplin_competition} and \cite{Tirole_contracts}), in political science and social choice (see \textit{e.g.}  \cite{Caplin_election}) or in econometrics (for example through the Roy model, see \textit{e.g.} \cite{Heckman_roy}){.}


 An important example comes from all distributions that are built with a multivariate convex function $U: \mathbb{R}^d \times \mathbb{R}^q \longrightarrow \mathbb{R}$ and where the first $d$ coordinates are considered as the hidden parameter $\theta$ while the $q$ other ones are the observations.
Starting from a convex function $U: \mathbb{R}^q \longrightarrow \mathbb{R}^q$,  translation models $(\xi,\theta)\longmapsto e^{-U(\xi-\theta)}$ also generate typical examples of log-concave models in $(\xi,\theta)$.
Many other distributions satisfy the log-concave property: Gumbel and Weibull distributions with a shape parameter larger than 1. 
 In particular, this includes a large class of parametric probability distributions such as Gaussian or Laplace models, logistic regression models, Subbotin distributions,  Gamma or Wishart distributions, Beta and uniform distributions on real intervals among others.   
We refer to \cite{SW} for a detailed  survey on properties of log-concave distributions, to \cite{Walther} for a list of modeling and application issues and to \cite{Samworth} for non-parametric density estimation procedures of log-concave distributions.
}


\subsection{Bayesian estimation of $\theta^{\star}$}
We briefly sketch Bayesian strategies for estimating $\theta^{\star}$

\noindent
 Considering a prior distribution $\Pi_0$ on  $\theta$,  we assume that $\Pi_0$ is absolutely continuous with respect to the Lebesgue measure $\lambda_q$ on $\mathbb{R}^d$. 
Without any {possible confusion} with the familiy of densities  $(\pi_\theta)_{\theta \in \mathbb{R}^d}$, the associated density of the prior is denoted by $\pi_0$
and we further assume that $\pi_0$ is also log-concave: $\pi_0(\theta):= e^{-V_0(\theta)}$
where $V_0$ encodes the prior knowledge on $\theta$. We emphasize that this last assumption is not restrictive since the prior distribution is chosen by the user.
We  denote by {$\pi_n$  the density of the posterior distribution} (that depends on the  observations $\mathbf{\xi^n}:= (\xi_1,\ldots,\xi_n)$) given by:
$\pi_n(\theta)\,\propto \,\pi_{0}(\theta)\prod_{k=1}^n \pi_{\theta}(\xi_k ).$
The posterior distribution is a data-driven probability distribution that  may be written as:
\begin{equation}\label{eq:def_wn}
\forall \theta\in \mathbb{R}^d \qquad \pi_n(\theta)=\frac{e^{-W_n(\mathbf{\xi^n},\theta)}}{Z_n(\mathbf{\xi^n})}\pi_0(\theta)
\quad \text{where}
\quad 
 W_n(\mathbf{\xi^n},\theta)=\sum_{i=1}^nU(\xi_i,\theta).
\end{equation}  The quantity $Z_n(\mathbf{\xi^n})$ corresponds to the normalizing constant and depends as well on $\mathbf{\xi^n}$:
$$
Z_n(\mathbf{\xi^n}) = \int_{\mathbb{R}^d} \pi_0(\theta) e^{-W_n(\mathbf{\xi^n},\theta)} \text{d} \theta.
$$
It is well known that  the posterior distribution enjoys consistency properties (see \textit{e.g.} \cite{Schwartz,IbraHas}):  under mild assumptions on the prior distribution and on the statistical model, the posterior distribution concentrates its mass around $\theta \in \mathbb{R}^d$ whose distribution is close to $\mathbb{P}_{\theta^{\star}}$.
 
With additional metric and identifiability assumptions, some stronger results may be obtained   in general parametric or non-parametric models. We refer to the seminal contribution of \cite{GhosalGhoshvdVaart} and the references therein,  to the work of \cite{CasvdV} for an extension to less standard situations of high-dimensional models and to \cite{vZvdV} for infinite dimensional models. 
The posterior distribution may be used to define 
Bayesian estimators, in particular, we shall introduce the popular posterior mean estimator of $\theta^{\star}$ defined by:
\begin{equation}
\label{eq:posterior_mean}
\widetilde{\theta}_n = \int_{\mathbb{R}^d} \theta \pi_n(\theta) \text{d}\theta.
\end{equation}
This estimator is usually consistent and a popular issue  is to establish \textit{rates of convergence} towards $\theta^{\star}$ through some $L^p$-criterion, \textit{i.e.} find a sequence $\epsilon_n \longrightarrow 0$ such that:
\begin{equation}\label{eq:statbound}
\mathbb{E}_{\theta^\star} \left(|\widetilde{\theta}_n-\theta^\star|^p\right) \leq \varepsilon_n^p,
\end{equation}
for a given $p>1$. Nevertheless, when a such bound is obtained,   the story is not over. Actually, the theoretical posterior mean given by Equation \eqref{eq:posterior_mean} being generally not explicit, the practical use of the above statistical bounds certainly requires to provide computable algorithms that may approximate $\widetilde{\theta}_n$.  In particular, it is legitimate to look for a tractable estimator 
$\widehat{\theta}_n$ that approaches an $\varepsilon_n$-neighborhood of $\widetilde{\theta}_n$ with as less operations as possible. 

\subsection{Langevin Monte Carlo discretization and practical estimator}\label{sec:intro_disc}

To approximate $\widetilde{\theta}_n$, it is commonly used  to write $\pi_n$  as a Gibbs field:
\begin{equation}\label{eq:tildeW}
\pi_n(\theta)\, \propto \,  \exp(-\widetilde W_n(\mathbf{\xi^n},\theta)) \quad \text{with} \quad 
\widetilde{W}_n(\theta)  = \sum_{i=1}^n U(\xi_i,\theta)+\log \left(\frac{1}{\pi_0(\theta)}\right).\end{equation}
Under some mild assumptions on $\widetilde W_n$, it is well known that a such probability measure is the unique invariant distribution   of the (over-damped) Langevin diffusion defined by:
\begin{eqnarray}\label{eq:diffusion}
dX^{(n)}_t =- \nabla\widetilde W_n(X^{(n)}_t)dt + \sqrt 2 dB_t,
\end{eqnarray} 
where $(B_t)$ is a $d$-dimensional standard Brownian motion.
Thus, the probability $\pi_n$ can be approximated using the long-time ergodic convergence of $(X^{(n)}_t)_{t\ge0}$ towards $\pi_n$. One can  distinguish two types of convergences towards $\pi_n$: the convergence of the distribution of $X^{(n)}_t$ as $t\rightarrow+\infty$ or the $a.s.$ convergence of the occupation measure  of $(X^{(n)}_t)_{t\ge0}$. 
 
 Here, we build   our algorithm with the second type of convergence, which requires only one path of the diffusion.
 We are thus led to consider the occupation measure applied to the identity function denoted by $\mathbf{I}_d$. In this case, this is nothing but the Cesaro average:
\begin{equation}
\label{def:cesaro_shift}
\forall n \in \mathbb{N}^\star \quad \forall t >0 \qquad \widehat{\theta}_{n,t} := \frac{1}{t} \int_{0}^tX^{(n)}_s \text{d}s.
\end{equation}

{In  \eqref{def:cesaro_shift}, Cesaro averages are based on the ``true'' diffusion but to obtain a tractable algorithm, we need to introduce Cesaro averages of some discretization schemes of  \eqref{def:cesaro_shift}.}
For this purpose,  we consider a  positive step size $\gamma$ and introduce a constant step-size explicit Euler-Maruyama scheme related to $X^{(n)}$ {(omitting the index $n$ for simplicity)}:
\begin{equation}
\label{eq:Euler_def}
\forall k \ge 0 \quad \bar{X}_{t_{k+1}}:=\bar{X}_{t_k}-\gamma \nabla \widetilde{W}_n(\bar{X}_{t_k})+\sqrt{2} \zeta_{k+1}  \quad  \text{with} \quad t_k=k \gamma,
\end{equation}
where   for all $k\ge1$, $\zeta_k={B}_{{t_{k}}}-{B}_{t_{k-1}}$ and $({B}_t)_{t\ge0}$ is a standard $d$-dimensional Brownian motion. 
It is possible to define a continuous affine interpolation of \eqref{eq:Euler_def} but from a practical point of view, it will be more comfortable to consider some initialization and ending times in the discrete grid $(t_k)_{k \ge 0}$. 

For any time horizon $t_N>0$, the approximation of $\widehat{\theta}^{\gamma}_{n,t_N}$ with a step-size $\gamma$ is given by:
\begin{equation}\label{def:tgn}
\widehat{\theta}^{\gamma}_{n,t_N} :=
\displaystyle\frac{1}{N}{\sum_{j=0}^{N-1}  \bar{X}_{t_j}},
\end{equation}
which corresponds to the Cesaro average of the discretized trajectory \eqref{eq:Euler_def}. 


{This Cesaro construction first appeared in \cite{talay}  where some convergence properties of the empirical measure of the Euler scheme with constant step size were investigated. In a series of recent papers (among others, see \cite{lamberton_pages,LP03,pagespanloup2012} or \cite{pagespanloup2018} for a \textit{multilevel} extension), the decreasing-step setting has also been studied. Compared with these papers, the novelty of our work is that, we  propose some non-asymptotic quantitative bounds (see Section \ref{sec:contribplan} for details about the corresponding results). 
Note that for ease of presentation, we prefered to mainly consider the (less technical) constant step setting.}


  
   
\subsection{Contributions and plan of the paper.} \label{sec:contribplan} 
{Our main results are stated in Section \ref{sec:main}}. We address two main points:



\begin{itemize}
\item \textbf{The Bayesian consistency}: \textit{i.e.}  the  distance between the  posterior mean $\widetilde{\theta}_n$ and $\theta^\star$.
\end{itemize}

The Bayesian consistency is studied in  Section \ref{sec:bayes}. First, Theorem \ref{theo:consistency} derives an upper bound of the $L^p$ loss in terms of the \textit{Poincar\'e constant} of the model (which is assumed to satisfy a uniformity condition).  Compared with the literature on this problem (see $e.g.$ \cite{Jordan-Wainwright}), this result is  written under general assumptions on the family of log-concave models and does not require specific assumptions related to a dynamical system. Second, Theorem \ref{theo:lower_bound} proves that our upper bound is minimax optimal for a large class of models.




\begin{itemize}
\item \textbf{The  numerical question} related to the approximation of $\widetilde{\theta}_n$ by a computable algorithm. 
\end{itemize}

 Our main results about Cesaro-type LMC and optimal tuning of the parameters (in terms of $n$ and $d$) are Theorems \ref{theo:learning_weak_convex} and \ref{theo:learning_strong_convex} whose complete study is devoted to Section \ref{sec:disc_c} and Section \ref{sec:discretisation}. Our approach based on the \textit{Poisson equation}, $i.e.$ on the inversion of the infinitesimal generator of the diffusion with a quantitative point of view, will allow to obtain Theorem \ref{cor:thmPoisson} (weakly convex case) and Theorem \ref{cor:thmPoissonSC} (strongly convex case).
 On this numerical topic, our main  contribution is the (almost) quantitative study of the weakly convex case (with the help of the Kurdyka-\mathcal{L} ojasiewicz inequality introduced in $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$) based on quantitative controls on the solution of the \textit{Poisson equation} (and on its derivatives). Nevertheless, the Poisson approach seems also of interest in the strongly convex case, the results being very close to \cite{durmus} but slightly improve the dependence in the parameters of the model. This is probably due to the fact that Poisson approach does not require to couple the Euler scheme with the continuous process (see Remark \ref{rmqdurmusmus} for details). 

In the two cases, we obtain some  explicit bounds on the distance between the discretized Cesaro average and the posterior mean. These bounds lead to  an optimal tuning in terms of $n$ and $d$ in the weakly convex setting.

 
 

 In short, for both weakly and strongly convex situations, for some given $n$ and $d$, we first exhibit an  $\varepsilon_n$ that upper-bounds the ($L^p$-type) error between $\widetilde{\theta}_n$ and $\theta^\star$. Then, for this $\varepsilon_n$, we  aim at tuning  the procedure \eqref{def:tgn} in order to {obtain} an $\varepsilon_n$-approximation\footnote{By $\varepsilon$-approximation, we mean an approximation of the target with an $L^p$-error {of the order} ${\mathcal O}(\varepsilon)$.} of $\widetilde{\theta}_n$ with a minimal computational cost. 
  This cost $N_{\varepsilon_n}$ (number of iterations of the Euler scheme) will be explicited  as an amount of operations upper bounded by $n^a d^b$, where $a$ and $b$ are some positive numbers that will be explicited below.
Our main contribution states that Bayesian learning can be optimally performed in polynomial time less than $n^a d^b$ operations for typically weakly convex situations with explicit $a$ and $b$, and in even
$ n d$ operations in strongly convex cases.\\
 {For an improved readability of the work, numerous proofs and technical results are deferred to the Appendix.


  
{\subsection{Notations }

\begin{itemize}
\item{}  The notation $a\lesssim_{uc}b$ means that $a\le c b$ where $c$ is a \textit{universal constant}, $i.e.$ independent of any of the relevant parameters of the problems. 
\item{} {The usual scalar product on $\mathbb{R}^d$ is denote by $\langle\,,\,\rangle$ and the induced Euclidean norm by $|\,.\,|$. The set $\mathbb{M}_{d,d}$ refers to the set of real $d \times d$ matrices. The Frobenius norm on $\mathbb{M}_{d,d}$ is denoted by $\|\,.\,\|_F$: for any $A\in\mathbb{M}_{d,d}$, $\|A\|_F^2=\sum_{1\le i,j\le d} A_{i,j}^2.$ We also denote by $\nsp{.}$ the spectral norm, defined for any matrix $A$ by $\nsp{A}=\sup_{|x|=1} |Ax| = \sqrt{\bar{\lambda}_{A^t A}} $, where $\bar{\lambda}_{A^t A}$ refers to the maximal eigenvalue of the symmetric matrix ${A^t A}$.} 
\item{} {For a Lipschitz continuous function $f:\mathbb{R}^d\rightarrow\mathbb{R}^{d'}$, we denote by $[f]_1$ its related Lipschitz constant. When $f$ is ${\mathcal C}^1$, its Jacobian matrix denoted by $Df$ maps from $\mathbb{R}^d$ to $\mathbb{M}_{d,d'}$. When $Df$ is Lipschitz {for} the spectral norm $\nsp{.}$, we denote by $[Df]_{1,\star}$ the related Lipschitz constant. As usual the notations $\nabla$ and $\Delta$ will hold for the gradient and the Laplacian.}  
\item{}  In the sequel,  we call upon to different distances on the space of probability measures: the $p$-Wasserstein distance is denoted by $\mathcal W_p$, $p\in[1,\infty[$ (mainly used with $p=1$ or $p=2$ in this paper). We recall that
$$\mathcal{W}_p(\mathbb{P}_{\theta_1},\mathbb{P}_{\theta_2})=\left(\inf_{\pi\in\Pi(\mathbb{P}_{\theta_1},\mathbb{P}_{\theta_1})}\int_{\mathbb R^q}d(x,y)^p\pi(x,y)\right)^{1/p},$$
where $\Pi(\mathbb{P}_{\theta_1},\mathbb{P}_{\theta_2})$ stands for the set of all coupling measures of $\mathbb{P}_{\theta_1}$ and $\mathbb{P}_{\theta_2}$. The Kullback-Leibler divergence is denoted by $KL(\mathbb{P}_{\theta_1},\mathbb{P}_{\theta_2})$ and is classically defined by
$$KL(\mathbb{P}_{\theta_1},\mathbb{P}_{\theta_2})=\int_{\mathbb R^q}\log\left(\frac{\pi_{\theta_1}(\xi)}{\pi_{\theta_2}(\xi)}\right)\pi(\theta_1)(\xi)d\xi.$$
\end{itemize}
}









 





 

\section{Main results and discussion \label{sec:main}}
In our work, two sources of randomness are considered. The first one is derived from the observations {$\mathbf{\xi^n}= (\xi_1,\ldots,\xi_n)$}. The notations $\mathbb{P}_{\theta}$ and $\mathbb{E}_{\theta}$ refer to the probability and expectation on {the unknown distribution of} the sampling process. The second source of randomness is related to the posterior distribution $\pi_n$ over $\mathbb{R}^d$: for any Borelian  $\mathcal{B}$ of $\mathbb{R}^d$, $\pi_n(\mathcal{B})$ is the probability of $\mathcal{B}$ when $\theta$ is sampled according to $\pi_n$, conditionally to the observations. Hence, $\mathbb{E}_{\pi_n}$ is the expectation when $\theta \sim \pi_n$, conditionally to {$\mathbf{\xi^n}$}.\\
\subsection{Functional inequality and Assumption $(\mathbf{PI_U})$}\label{sec:functional}



For any measure $\mu$  and $f\in L^1(\mu)$,   $\mu(f)$ refers to the mean value of $f$, and when  $f\in L^2(\mu)$, $Var_{\mu}(f)$ is the variance of $f$:
$$
\mu(f) := \int_{\mathbb{R}^q} f(\xi) \text{d}\mu(\xi) \qquad \text{and} \qquad 
Var_{\mu}(f) := \int_{\mathbb{R}^q} [f(\xi)-\mu(f)]^2 \text{d}\mu(\xi).
$$
A crucial property of log-concave measures is that they satisfy a Poincar\'e inequality. This will be used extensively in the rest of the paper. We refer to \cite{Ledoux,BGL} for a complete presentation and some applications on concentration inequalities and Markov processes. 


\begin{defi}[Poincar\'e inequality]
A measure $\mu$ satisfies a Poincar\'e inequality with  $C_P(\mu)$ if
$$
\forall f \in L^2(\mu) \qquad Var_{\mu}(f) \leq  C_P(\mu) \mu(\vert\nabla f\vert^2).
$$
 \end{defi}
  
 
We   remind an important result obtained in \cite{Bobkov-aop} (see also 
 \cite{Poincare_log_concave}) that establishes the existence of a Poincaré inequality for every log-concave probability distribution.
 \begin{thm}[\label{theo:log-concave_poincare}\cite{Bobkov-aop,KLS}]
 Every log-concave measure $\mu$ satisfies a Poincar\'e inequality: a universal constant $K$ exists such that:
$$
 C_P(\mu) \leq 4 K^2 Var_{\mu}(\mathbf{I}_d),
 $$
 where $\mathbf{I}_d$ refers to the identity map: $\mathbf{I}_d: \xi \longmapsto \xi$.
 \end{thm}
Since $(\xi,\theta) \longmapsto U(\xi,\theta)$ is a convex function, 
Theorem \ref{theo:log-concave_poincare} implies  that for all $\theta \in \mathbb{R}^d$, $\mathbb{P}_{\theta}$ satisfies a Poincaré inequality of constant $C_P(\mathbb{P}_{\theta})$.
We introduce   an assumption that stands for a uniform   bound of the collection of Poincaré constants $C_P(\mathbb{P}_{\theta})$.

\begin{ass}[Uniform Poincaré Inequality $(\mathbf{PI_U})$\label{ass:upi}]
A constant $C^U_P$ exists such that
$$
\forall \theta \in \mathbb{R}^d \qquad C_P(\mathbb{P}_{\theta}) \leq C^U_P.
$$
\end{ass}

We emphasize that according to Theorem \ref{theo:log-concave_poincare}, a uniform bound on the variance of each distribution $\mathbb{P}_{\theta}$ over $\theta \in \mathbb{R}^d$ entails $(\mathbf{PI_U})$.
{Note that the uniform upper bound on the Poincar\'e constant involved in the family of distributions $(\pi_{\theta})_{\theta \in \theta}$ is needed to obtain some concentration rates that are independent from the value of $\theta$.}






\subsection{Bayesian consistency\label{sec:sub:bayes}}
\subsubsection{Assumptions $(\mathbf{A}_L)$ and $(\mathbf{I_{W_1}(c)})$}






We introduce some mild assumptions necessary to
obtain some consistency  rates of $\widetilde{\theta}_n$.
First, we  handle smooth functions $(\xi,\theta) \longmapsto U(\xi,\theta)$
and assume that:
\begin{ass}[Assumption $(\mathbf{A}_L)$]
$U$ satisfies the $\mathcal{C}^1_L$ hypothesis: \textit{i.e.} the partial gradient of $U$ with respect to $\theta$ is a L-Lipschitz function of $\theta$ and of $\xi$:
$$
\forall \xi  \in \mathbb{R}^q \quad \forall \theta_1,\theta_2 \in \mathbb{R}^d: \qquad 
|\nabla_\theta U(\xi,\theta_1)-\nabla_\theta U(\xi,\theta_2)| \leq L |\theta_1-\theta_2|,
$$
and
$$
\forall (\xi_1,\xi_2)  \in \mathbb{R}^q \quad \forall \theta  \in \mathbb{R}^d: \qquad 
|\nabla_\theta U(\xi_1,\theta)-\nabla_\theta U(\xi_2,\theta)| \leq L |\xi_1-\xi_2|.
$$
\end{ass}


{\begin{rmq} Let us mention that Assumption $(\mathbf{A}_L)$ is standard in the optimization community (see \cite{Nesterov,Bubeck}). Essentially, this allows to quantify the error made when using a first order Taylor expansion. In optimization theory, $L$-smooth functions are then used to produce descent lemmas. Here it will be used for lower-bounding the normalizing constants of the Bayesian posterior distributions (see Equation \eqref{eq:minoration_intermediaire}).
This assumption also appears in the recent contribution \cite{Jordan-Wainwright} but the L-smooth property is only assumed for the function $\theta \longmapsto \mathbb{E}_{\theta^\star}[U(\xi,\theta)]$ associated with either a strong or weak convex assumption on $U$  (Assumptions (S.1) or (W.1) of \cite{Jordan-Wainwright}).
\end{rmq}}

To make the estimation problem tractable, we need to manipulate statistically identifiable models.
If statistical identifiability is a free result for any $L^1$ location model when $U(\xi,\theta)=U(\xi-\theta)$, this is no longer the case in general   models, even log-concave ones. We therefore introduce an identifiability assumption, which will useful for our theoretical results.

\begin{ass}[Assumption $(\mathbf{I_{W_1}(c)})$ - Wasserstein identifiability]
A strictly increasing map $c: \mathbb{R}_+ \longrightarrow \mathbb{R}_+$ and a $1$-Lipschitz function $\Psi$ exist such that $c(0)=0$ and :
$$
{\forall \theta_1,\theta_2\,\in\,\mathbb{R}^d,\quad}|\pi_{\theta_1}(\Psi)-\pi_{\theta_2}(\Psi)| \geq c(|\theta_1-\theta_2|).
$$
Furthermore, we shall assume that a pair $(b_1,b_2)\in \{\mathbb{R}_+^{\star}\}^2$ and $\alpha_c$>0 exists such that:
\begin{equation}\label{eq:ic}
\forall \Delta \geq 0 \qquad 
c(\Delta) \geq b_1 \Delta^{\alpha_c} \mathbf{1}_{\Delta \leq 1} + b_2 [\log(\Delta)+1] \mathbf{1}_{\Delta \geq 1}. 
\end{equation}
\end{ass}


\begin{rmq}\noindent  Assumption
$(\mathbf{I_{W_1}(c)})$ is a quantitative identifiability condition. It implies in particular that
$$
\mathcal{W}_1(\mathbb{P}_{\theta_1},\mathbb{P}_{\theta_2}) \geq c(|\theta_1-\theta_2|),
$$
where $\mathcal{W}_1(\mathbb{P}_{\theta_1},\mathbb{P}_{\theta_2})$ refers to the Wasserstein distance between $\mathbb{P}_{\theta_1}$ and $\mathbb{P}_{\theta_2}$. The constants $b_1$ and $b_2$ are not fundamental in our forthcoming analysis but  $\alpha_c$  plays a central role:  it  asserts how the distributions $\pi_{\theta_1+\delta}$ moves from  $\pi_{\theta_1}$ for small values of $\delta$ (see   Section \ref{sec:sub:discussion}).
{It is straightforward to verify that $(\mathbf{I_{W_1}(c)})$ is satisfied in the location models with $\Psi=\mathbf{I}_d$ since in that case
$
|\pi_{\theta_1}(\mathbf{I}_d)-\pi_{\theta_2}(\mathbf{I}_d)|=|\theta_1-\theta_2|. 
$}

All along our work, we consider $b_1$ and $L$ involved in Assumption $(\mathbf{I_{W_1}(c)})$ and $(\mathbf{A}_L)$ as fixed quantities, that describe the variations of $U$ and therefore the variations of the distribution $(\mathbb{P}_{\theta})_{\theta \in \mathbb{R}^d}$. Since $b_1$ quantifies how $\pi_{\theta}$ moves when $\theta$ moves, a link exists between $b_1$ and $L$ since oppositely $L$ quantifies in $(\mathbf{A}_L)$ an upper bound of variation of $U(\theta,.)$ itself, and therefore an upper bound of variation of $\pi_{\theta}$. Even though an interesting question that is related to contamination models (see \textit{e.g.} \cite{Cai-Wu,Laurent-Marteau-Maugis}), we have chosen to leave  open the analysis between $b_1$ and $L$, and simply assume in what follows that $b_1>0$ and $L>0$ are fixed constants independent from $n$ and $d$.
\end{rmq}



\begin{rmq}
Our identifiability condition with the Wasserstein distance is different from what is usually studied with mixture models where label permutations need to be considered. In mixture models, $\theta$ commonly refers to a collection of weights of components $(\omega_i)_{1 \leq i \leq K}$ +locations of components $(p_i)_{1 \leq i \leq K}$ and identifiability is then related to a conditions that is close to:
$$
d(\mathbb{P}_{\theta_1},\mathbb{P}_{\theta_2}) \geq \mathcal{W}_1(\mu_{\theta_1},\mu_{\theta_2}) \quad \text{with} \quad \mu_{\theta} = \sum_{i=1}^K \omega_i(\theta) \delta_{p_i(\theta)},
$$
where $\mathcal{W}_1(\mu_{\theta_1},\mu_{\theta_2})$ is the Wasserstein distance between the mixing distributions $\mu_{\theta_1}$ and $\mu_{\theta_2}$.
We refer to \cite{Ho1,Ho2} and the references therein for some recent statistical work on identifiability and consistency rates in finite mixture models. Another popular subject of investigation is the effet of the size of the weights $(\omega_i)_{1 \leq i \leq K}$ on the identifiability and estimation, in particular in contamination models. We refer for example to \cite{Gadat_mix} for a detailed understanding of the effect of the contamination level on the identifiability of Gaussian mixture models, and therefore on $b_1$ involved in $(\mathbf{I_{W_1}(c)})$.
However, we emphasize that the model we are considering are log-concave, which is far from being the case with mixtures.
\end{rmq}

\begin{rmq}
Besides our log-concave framework, we could imagine use $(\mathbf{I_{W_1}(c)})$ in more general statistical models such as location-scale mixture models even though these models are from being log-concave and much more challenging in terms of identifiability. We refer to \cite{Gadat_mix,Heinrich-Kahn} and the references therein for some recent contributions in this direction. As an example, using the dual formulation of the $W_1$ distance, it may be shown that for a location/scale Gaussian model $\mathcal{N}_{\mu,\sigma^2}$, $\alpha_c=1$ for the dependency on the means $|\mu_1-\mu_2|$. Regarding the dependency in terms of $(\sigma_1,\sigma_2)$, the same strategy with $f(x)=|x|$ yields $\alpha_c=1$ for $|\sigma_1-\sigma_2|$. In the multivariate setting, the situation is already more difficult, and we refer to \cite{Dowson} for an exact value of the $W_2$ distance that upper bounds the $W_1$ one and it seems reasonnable to think that $\alpha_c=1$ in this situation for location/scale Gaussian models.
\end{rmq}


\begin{rmq}
{ This natural separation assumption is related to the hypothesis testing in the statistical model. Statistical test has a longstanding history in Bayesian literature (see \textit{e.g.} \cite{LeCam,Birge,GhosalGhoshvdVaart,CasvdV} among others). In general, the former papers build some global statistical tests using metric considerations with covering arguments on the statistical models. In particular this is done using Hellinger distance or the Kullback-Leibler divergence. 
Here, our assumption is related to a separation with the help of the $\mathcal{W}_1$  distance over  $\mathbb{P}_{\theta}$.  The function $\Psi$ involved in $(\mathbf{I_{W_1}(c)})$ will be then used to build a global test.}
\end{rmq}

In a sense, a link  exists between the conjunction of $(\mathbf{A}_L) + (\mathbf{I_{W_1}(c)})$ and a metric complexity (in terms of covering numbers) as used in the seminal contribution \cite{GhosalGhoshvdVaart}[Equation (2.2)]. In particular, it is  straightforward to prove that if $N(\varepsilon,\theta\cap K,d_{KL})$ is the covering number of the statistical model with the KL  divergence and if $K$ is a compact subset of $\mathbb{R}^d$, then
$$
\log N(\varepsilon, K,d_{KL}) \lesssim d \log(\sqrt{L} \varepsilon^{-1}).
$$
Hence, $(\mathbf{I_{W_1}(c)})$ shall be thought of as a way to both ``compactify'' the space where   $\theta$ is living and  make a local link between $d(\mathbb{P}_\theta,\mathbb{P}_{\theta^\star})$ and $|\theta-\theta^\star|$. This is useful to avoid sieve considerations (see \textit{i.e.} \cite{GhosalGhoshvdVaart,vZvdV,ShenWasserman} for example) and {this} allows to quantify the tail behaviour of the posterior distribution $\pi_n$ far away from $\theta^\star$ (see \textit{e.g.} \cite{CasvdV}).

Finally, $(\mathbf{I_{W_1}(c)})$ { also has} a tight link with Assumption $(W.1)$ of \cite{Jordan-Wainwright} that assumes that if $F(\theta):= \mathbb{E}_{\theta^\star} [\log \pi_\theta(\xi)]$, then for $h$ a non-decreasing convex function such that $h(0)=0$:
$$
\langle \nabla F(\theta),\theta^\star-\theta \rangle \ge h(|\theta-\theta^\star|),
$$
For any $\theta \in \mathbb{R}^d$, we introduce $\theta_t=\theta^\star+t(\theta-\theta^\star)$ and $f_\theta(t)=KL(\mathbb{P}_{\theta_t},\mathbb{P}_{\theta^\star})$.
 A straightforward computation shows that Assumption $(W.1)$ implies that:
\begin{align*}
KL(\mathbb{P}_{\theta},\mathbb{P}_{\theta^\star})& = f_\theta(1)= f_\theta(0)+\int_{0}^1 f'_\theta(s) \text{d} s \\
& = \int_{0}^1 \langle \nabla F(\theta_s),\theta^\star-\theta \rangle \text{d}s  = \int_{0}^1 \frac{\langle \nabla F(\theta_s),\theta^\star-\theta_s \rangle}{s} \text{d}s \ge \int_{0}^1 \frac{h(s |\theta-\theta^\star|) }{s} \text{d}s \\
& \ge \int_{0}^1 \frac{h(0)+ h'(0) s |\theta-\theta^*|}{s} \text{d}s = h'(0) |\theta-\theta^*|,\\
\end{align*}
where we used in the last line the convexity of $h$. The previous inequality is not trivial when $h'(0)>0$.
Oppositely, if $h'(0)=0$, it is reasonable to assume that $h$ is $\beta$-H\"older around $\theta^\star$ with $\beta>1$ and we obtain again a local inequality of the form $KL(\mathbb{P}_{\theta},\mathbb{P}_{\theta^\star}) \gtrsim  |\theta-\theta^\star|^{\beta}$ near $\theta^\star$. In the meantime, since $h$ is non-decreasing, it is also possible to use
$
\int_{0}^1 \frac{h(s |\theta-\theta^\star|) }{s} \text{d}s \ge \int_{1/2}^1 \frac{h(s |\theta-\theta^\star|) }{s} \text{d}s \ge h\left(\frac{|\theta-\theta^\star|}{2}\right)$. Therefore, $(W.1)$ implies that a $\beta \ge 1$ exists such that:
$$
KL(\mathbb{P}_{\theta},\mathbb{P}_{\theta^\star}) \gtrsim |\theta-\theta^\star|^\beta \wedge  h\left(\frac{|\theta-\theta^\star|}{2}\right).
$$
The link between $(\mathbf{I_{W_1}(c)})$ and $(W.1)$ is then made with the help of functional inequalities: if  $\mathbb{P}_{\theta^\star}$ is strongly log-concave, then $\mathbb{P}_{\theta^\star}$ satisfies the $T_1$ inequality (see \textit{e.g.} \cite{Ledoux}) and $W_1(\mathbb{P}_{\theta},\mathbb{P}_{\theta^\star}) \lesssim \sqrt{KL(\mathbb{P}_{\theta},\mathbb{P}_{\theta^\star})}$. More generally, if $P_{\theta^\star}$ satisfies a sub-Gaussian concentration inequality, \cite{Bobkov-Gotze} shows that this Talagrand inequality still holds. Hence, both $(\mathbf{I_{W_1}(c)})$ and $(W.1)$ of \cite{Jordan-Wainwright} implies a lower bound on the KL-divergence in many log-concave reasonable situations, and the existence of convenient statistical tests.






\subsubsection{Bayesian consistency \label{sec:sub:bayes}}
\bigskip\hphantom{}

\noindent\textit{Upper bound}
{We obtain the next result \textit{ which is still valid besides the log-concave settings}. We have chosen to keep this setting for the sake of readability, even though $(\mathbf{PI_U})$ is sufficient here to guarantee the result.}

The next result states an upper bound on the $L^p$ loss between the posterior mean $\widetilde{\theta}_n$ and $\theta^{\star}$. We define
\begin{equation}\label{def:epsn}
 \varepsilon_n^2 := \left(C^U_P L^2\right)^{1/\alpha_c}  \left( \frac{d \log n}{n}\right)^{1/\alpha_c},
 \end{equation}
and consider situations where $n$ is large enough (with respect to $d$) in order to  guarantee that $b_1 \varepsilon_n^{\alpha_c} \leq 1$ where $b_1$ is defined in $(\mathbf{I_{W_1}(c)})$. We then have the following result.

\begin{thm}\label{theo:consistency} If $\pi_0 =e^{-V_0}$ is a $\mathcal{C}^1(\mathbb{R}^d,\mathbb{R})$ log-concave prior with $V_0 \in \mathcal{C}^1_1$, if $(\mathbf{PI_U})$, $(\mathbf{A}_L)$ and $(\mathbf{I_{W_1}(c)})$ hold, and if $(d,n)$ are such that $b_1 \varepsilon_n^{\alpha_c} \leq 1$, then:
$$
\forall p > 1 \qquad 
\left(\mathbb{E }_{\theta^{\star}} \left[\left|\widetilde{\theta}_n-\theta^{\star}\right|^p\right] \right)^{1/p} \lesssim_{uc}
K(U)  
\left( \frac{  d\log(n)}{n}\right)^{{\frac{1}{2 \alpha_c}}},
$$
with  $K(U)= \left(\sqrt{C^U_P} L\right)^{\frac{1}{\alpha_c}}$
and $C^U_P$ is the Poincaré constant given in  $(\mathbf{PI_U})$ (Assumption \ref{ass:upi})
\end{thm}

\begin{rmq}\label{rem:d_vs_n}
In particular, when $p=2$, we recover the standard mean square error rate.
We emphasize that our consistency result makes sense only when considering some situations where the dimension $d$ is smaller than $n$ the number of observations, so that $\varepsilon_n$ is asymptotically vanishing when $n \rightarrow + \infty$. Therefore, our model is not concerned by high dimensional situations where $d$ may be larger than $n$.

If the separation provided by $(\mathbf{I_{W_1}(c)})$ is sharp, \textit{i.e.} when $\alpha_c=1$, the $L^2$ loss is proportional to {$\sqrt{\frac{d}{n}}$} (up to a $\log$-term), which is the optimal loss in many statistical models. Our upper bound is deteriorated when $\alpha_c$ increases, \textit{i.e.} when the separation of the distributions $\mathbb{P}_{\theta}$ near $\mathbb{P}_{\theta^{\star}}$ is ``flat'', \textit{i.e.} when  the Wasserstein distance $\mathcal{W}_1(\mathbb{P}_\theta,\mathbb{P}_{\theta^{\star}}) \sim b_1 \|\theta-\theta^{\star}\|^{1+\varepsilon}$ for $\varepsilon>0$ near $\theta^{\star}$. Below in Theorem \ref{theo:lower_bound}, we extend this optimality result to a larger range of values for $\alpha_c$.
\end{rmq}
 It is worth mentionning the recent work of \cite{Jordan-Wainwright} that provides a similar analysis and derives a similar contraction rate: 
Using the notations of \cite{Jordan-Wainwright}, we observe that the  value $\alpha$ of their Corollary 1 corresponds to $\alpha_c+1$, essentially because of the definition of $F$ that is the Kullback Leibler divergence between $\pi_{\theta}$ and $\pi_{\theta^\star}$ and remarking that
$$
\langle \nabla F(\theta),\theta-\theta^\star \rangle = \mathbb{E}_{\theta^\star}[\langle \theta-\theta^\star,\partial_{\theta} U(\xi,\theta)] \lesssim |\theta-\theta^\star|^{1+\alpha_{c}}.
$$
Therefore, in the worst situation where $\beta=0$ in \cite{Jordan-Wainwright},  the associated rate of convergence is $(d/n)^{\frac{1}{2(\alpha-1)}} = (d/n)^{\frac{1}{2\alpha_c}}$, which is exactly the  result we obtain in Theorem \ref{theo:consistency}.
 In particular, in the situation of the Bayesian logistic regression, the noise inherited from this model is bounded so that $\beta=0$, which leads to the same result both for Theorem \ref{theo:consistency} and Corollary 1 of \cite{Jordan-Wainwright}.


\bigskip
 				
 				\noindent
\textit{Lower bound}
  In order to assess the accuracy of the Bayesian posterior mean estimator, we study and derive a lower bound of estimation following the minimax paradigm. 
In this view, we introduce  $\mathcal{F}_{\alpha_c}^L$ the set of
 models $(\mathbb{P}_{\theta})_{\theta \in \mathbb{R}^d}$ such that $(\mathbf{I_{W_1}(c)})$, $(\mathbf{PI_U})$ and $(\mathbf{A}_L)$ hold.}

We then define $r_{n,d}(\alpha_c)$ as the following \textit{minimax risk} given by:
$$
r_{n,d}(\alpha_c) := \inf_{\hat{\vartheta}_n} \sup_{\mathcal{F}_{\alpha_c}^L} \mathbb{E}\left[\|\hat{\vartheta}_n - \theta^\star\|_2\right],
$$
where the above infimum is taken over the set of all possible estimators
$\hat{\vartheta}_n$ constructed from the observations $\mathbf{\xi^n}$. Hence,
$r_{n,d}(\alpha_c)$  is the best achievable $L^2$ risk of estimation of $\theta^\star$ in the worst situation  under the assumptions of Theorem \ref{theo:consistency}. We obtain the following result.

\begin{thm}\label{theo:lower_bound} Over the class $\mathcal{F}_{\alpha_c}^L$, a constant $\kappa(L)$ exists such that:
$$
r_{n,d}(\alpha_c) \ge \kappa(L) \left( \frac{d}{n} \right)^{\frac{1}{2\alpha_c}}
$$
\end{thm}
We shall conclude from Theorem \ref{theo:consistency} and Theorem \ref{theo:lower_bound} 
that the Bayesian posterior mean estimator achieves an optimal rate of estimation in terms of $n$ and $d$ up to a $\log(n)^{1/\alpha_c}$ term. 

\subsubsection{Comments}		
We provide below several comments on Theorem \ref{theo:consistency}.
First, we emphasize that our results apply in any log-concave situations included the weakly convex case.
					 	
\noindent
Theorem \ref{theo:consistency} describes the behaviour of the posterior \textit{mean} $\int \theta \text{d} \pi_n(\theta)$ and not of the entire posterior distribution as classically studied in Bayesian statistics. In a sense, such a result seems less informative than the knowledge of the behaviour of the entire distribution $\pi_n$. However, a good behaviour of the posterior mean requires a sharp control of the tails of the posterior distributions whereas a ``contraction rate'' relative to the Hellinger distance (or with other distances such as the Kullback-Leibler or total variation ones) sometimes blur{s} the tail behaviour of the posterior. We refer to \cite{CasvdV} for an illustration in high dimensional linear models of the efforts needed to extend posterior concentration to posterior mean consistency.

\noindent 
If we now pay attention to the convergence rate obtained in Theorem \ref{theo:consistency}, we emphasize that when the separation is sharp, \textit{i.e.} when $\alpha_c=1$ in $(\mathbf{I_{W_1}(c)})$, we obtain the standard minimax convergence rate $\frac{d}{n}$ up to a $\log(n)$ term, and this result is in a sense non-asymptotic (a universal constant could be exhibited with a price of a huge technicalicity). In comparison with \cite{Jordan-Wainwright}, we also obtain{ed} a slightly better convergence rate  of $(d/n)^{1/\alpha_c}$  (see Corollary 1 of \cite{Jordan-Wainwright}). But in general situations, their value of $\beta$ is equal to $1$   so that the rates derived from Theorem \ref{theo:consistency} and Corollary 1 of \cite{Jordan-Wainwright} are equivalent.

















\subsection{Discretization in the weakly convex settings} 

 The main contribution of our paper is to carry out a precise study of the weakly convex situation (\textit{e.g.} when the underlying function is convex but not strongly convex). If we could derive the convergence rate of the continuous Cesaro average with the help of simple functional inequalities and Poincare constants, it is no longer the case when dealing with discretized Cesaro average. To bypass this difficulty, we are then led to introduce some functional inequalities that are slightly more parametric (see $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ below).
\subsubsection{General result} {In this section, we focus on the discretization procedure in the general weakly convex situation.}
 We still assume   $(\mathbf{A}_L)$  and introduce for any convex function $W$ {a set of inequalities that are related to the Kurdyka-\mathcal{L} ojasiewicz inequality (see \textit{e.g.} \cite{Lojasiewicz,Kurdyka}). This type of inequality is widely used 
in optimization and geometry to extend results from the strongly convex case to the more difficult weakly convex settings (see \textit{e.g.} \cite{ Bolte,Gadat-Panloup}).}
{For this purpose, for any matrix $B$, we denote  by ${\rm Sp}(B)$ the spectrum of B.}
We set:
\begin{equation}\label{def:lambda}
\bar{\lambda}_{\nabla^2 W}(x) := \sup \{{\rm Sp}(\nabla^2 W(x))\} \quad \text{and} \quad \underline{\lambda}_{\nabla^2 W}(x) = \inf \{{\rm Sp}(\nabla^2 W(x))\}.
\end{equation}
 
  

{\begin{ass}[Assumption $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$]  {$W$ is a positive ${\mathcal C}^2$-function with $\min W=_{uc} 1$} and there exist $0\le q\le r<1$ {and positive $\mathfrak{c}_1$ and ${\mathfrak{c}_2}$} such that,
$$\forall x\in\mathbb{R}^d,   \qquad \mathfrak{c}_1 W(x)^{-r}\le \underline{\lambda}_{\nabla^2 W}(x)\le \bar{\lambda}_{\nabla^2 W}(x)\le {\mathfrak{c}_2} W(x)^{-q}.$$
\end{ass}}

{Assumption $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ implies that (see Lemma \ref{lem:gradW} in appendix for details)
$$ \limsup_{|x|\rightarrow+\infty} |\nabla W|^2 W^{q-1}(x)<+\infty\quad \textnormal{and}\quad  \liminf_{|x|\rightarrow+\infty} |\nabla W|^2 W^{r-1}(x){>-\infty}.$$
In the case $r=q$, it implies a global standard Kurdyka-\mathcal{L} ojasiewicz assumption (see \textit{e.g.} \cite{Gadat-Panloup} for a recent application for stochastic gradient descent, and the seminal contributions of \cite{Lojasiewicz}).}
\noindent  The case $r=1$ corresponds to the limiting Laplace case, whereas $r=0$ (and $q=0$) is associated to the strongly convex case. In particular, the complexity of the procedure will of course increase with $r$. {Finally, note that since $\nabla W$ is $L$-Lipschitz,
the eigenvalues of $\nabla^2 W(x)$ are uniformly bounded, which implies  that 
$q\ge0$ in $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ is given by $(\mathbf{A}_L)$.
Assumption 2.4 $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$  relates the behaviour of the spectrum of the Hessian (which translates some information on the curvature of the landscape) with the size of the potential itself and
 $r>q \ge 0$ is associated to some lack of strong convexity in some directions of the landscape function. Interestingly, thanks to $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ and the convexity assumption, some tights relationship exist between $W(x)$, $|\nabla W(x)|$ and the eigenvalues of $\nabla^2 W(x)$.
}

\begin{rmq}\label{rmqexample1} 
\noindent Let us consider $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ with $W(x)=(1+|x|^2)^p$ with $p\in(1/2,1]$. We verify that
$$\nabla W(x)=2p  W(x)^{(p-1)/p }x\quad\textnormal{and}\quad (\nabla^2 W(x))_{ij}=4p(p-1) x_i x_j W(x)^{(p-2)/p}+2p\delta_{ij}W(x)^{(p-1)/p}.$$
Moreover, for any vector $u$ with $|u|=1$,
$$\langle \nabla^2 W(x) u, u\rangle =2p(1+|x|^2)^{p-1}\left(1-2(1-p)\frac{\langle x,u\rangle ^2}{1+|x|^2}\right).$$
It implies that:
$$\underline{\lambda}_{\nabla^2 W}(x)\ge 2p(1-2(1-p))(1+|x|^2)^{p-1}=2p(1-2(1-p)) W(x)^{-\frac{1-p}{p}},$$
and 
$$\overline{\lambda}_{\nabla^2 W}(x)\le  (1+|x|^2)^{p-1}=2p W(x)^{-\frac{1-p}{p}}.$$
This entails $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ with $r=q=(1-p)/p$.




\end{rmq}
Under $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$, we are able to obtain exponential  bounds for the Euler scheme denoted by  $\bar{X}^{\gamma}$ and for the diffusion $X$ (see  Lemma \ref{lem:expbounds1cont} and Proposition \ref{lem:expbounds2scheme} of in Appendix B),  which in turn involve the following quantitative controls of the moments. 

\begin{prop} 
\label{lem:expbounds22}  Assume $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$.  {Assume that $W(x^\star)\le 1$}. Suppose that  $\gamma\le\gamma_0:= \frac{1}{4 d L + 1}$, then
 a locally finite positive function $p\mapsto c_p$ on $(0,+\infty)$, independent of $W$,  such that for any $p>0$,
$$\sup_{t\ge0} \mathbb{E}_x[W ^p (X_{t})]+\sup_{t\ge0} \mathbb{E}_x[W ^p (\bar{X}^{\gamma}_{t})]\le c_p \left(  W^p (x)+\Upsilon^p\right),$$
where $\Upsilon$ is a positive number that satisfies:
$$1\le \Upsilon\le c_r {({\mathfrak{c}_2}\vee L)^{\frac{1}{1+q-r}}}{\mathfrak{c}_1^{-\frac{1}{1-r}}}\log(1+dL) d^{\frac{1}{1+q-r}},$$ 
where $c_r$ is a constant depending only on $r$.
\begin{rmq} Note that in the particular case $q=0$, we obtain $\Upsilon\le c_r (L/\mathfrak{c}_1)^{\frac{1}{1-r}} \log(1+dL) d^{\frac{1}{1-r}}$ so that when $r=q=0$ (that corresponds to the strongly convex setting) we obtain $\Upsilon\,\propto \,\frac{L}{\mathfrak{c}_1} d\log (1+dL)$.
It is worth saying that the previous bound is universal, but may be improved in some situations with specific statistical models.
\end{rmq}
 
\end{prop}



{
We are now able to state our first bounds on the complexity of the discretization procedure. This general and technical result is divided into two cases $(i)$ and $(ii)$ leading respectively to a complexity of order $\varepsilon^{-4}$ and $\varepsilon^{-3}$ (the second case requires additional assumptions on $W$). Then, each case is divided into two parts $(a)$ and $(b)$. In Statement $(a)$, the result gives the dependency on the whole set of parameters whereas $(b)$ only focuses on the dimension $d$ (in order to provide a bound which is less precise but more simple to read). 
}


\begin{thm}\label{cor:thmPoisson}
Assume  {$(\mathbf{A}_L)$}, $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ and that $\gamma\le \gamma_0:= \frac{1}{8}((d (L\vee {\mathfrak{c}_2}))^{-1}\wedge \frac{1}{8})$. Let $f$ be a ${\mathcal C}^2$ function from $\mathbb{R}^d$ to $\mathbb{R}^{d'}$ with $d'\le d$, $[f]_1\le 1$ and $[Df]_{1,\star}\le 1$.
Let $\varepsilon>0$ and $\mathfrak{e}>0$.\\

\begin{itemize}
\item $(i.a)$  If $\gamma_\varepsilon =  \frac{\mathfrak{c}_1^{2(1+\mathfrak{e})}}{d L^2 \Upsilon^{2r(1+\mathfrak{e})}} \varepsilon^2 \wedge 
\frac{d}{{\mathfrak{c}_2} \Upsilon^{1-q-2r \mathfrak{e}}}  \wedge
\frac{d}{{\mathfrak{c}_2} 
(1+q)^{\frac{1-q}{1+q}} {\mathfrak{c}_2}^{\frac{1-q}{1+q}} \Upsilon^{-2r \mathfrak{e}}|x_0-x^\star|^{2 \frac{1-q}{1+q}}}
 \wedge
\frac{\Upsilon^{2r(1+\mathfrak{e})+q-1} d L^2}{{\mathfrak{c}_2} \mathfrak{c}_1^{2(1+\mathfrak{e})}}$
and


$$
N_{\varepsilon} \ge \Upsilon^{\frac{1+3r}{2}(1+\mathfrak{e})} \mathfrak{c}_1^{-\frac{3}{2}(1+\mathfrak{e})} \gamma_{\varepsilon}^{-1} \epsilon^{-1} \vee d' \Upsilon^{2r(1+\mathfrak{e})} \mathfrak{c}_1^{-2(1+\mathfrak{e})} \gamma_{\varepsilon}^{-1} \varepsilon^{-2}
$$

 
\noindent
  then,  a constant $c_{\mathfrak{e},r,q}$  exists independent from $\mathfrak{c}_1$, ${\mathfrak{c}_2}$, $L$, $d$, $\varepsilon$ such that:
\begin{equation} \label{eq:MSEleeps}
 {\mathcal E}_\varepsilon:=\mathbb{E}_{x_0}\left[\left|\frac{1}{N_\varepsilon}\sum_{k=1}^{N_\varepsilon} \bar{X}_{k\gamma}^{\gamma}-\pi(\mathbf{I}_d)\right|^2\right]\le c_{\mathfrak{e},r,q}{\varepsilon^2}\quad\textnormal{{with $\pi\,\propto \, e^{-W}$}}.
 \end{equation}

\item $(i.b)$ If $\varepsilon \in (0,1\wedge (d' d^{-\frac{1-r}{2(1+q-r)}})]$, $\gamma_\varepsilon=\varepsilon^{2}d^{-(1+\frac{2r}{1+q-r}+\mathfrak{e})}$ and $N_\varepsilon=\varepsilon^{-4} d' d^{1+\frac{4r}{1+q-r}+\mathfrak{e}}$, then
 ${\mathcal E}_\varepsilon\le c\varepsilon^2$ where $ c$  only depends on $\mathfrak{e},r,q,\mathfrak{c}_1,{\mathfrak{c}_2}$ and $L$ (but not  on $d$ and $\varepsilon$).\\
\item  $(ii.a)$ Assume furthermore that $W$ is ${\mathcal C}^3$ with $D^2 W$ $\tilde{L}$-Lipschitz for $\nsp{.}$ and that
$$\|\vec{\Delta}(\nabla W)\|_{2,\infty}^2:=\sup_{x\in\mathbb{R}^d} |\vec{\Delta}(\nabla W)(x)|^2<+\infty,$$
where $\vec{\Delta}(\nabla W)=(\Delta \partial_{1} W,\ldots,\Delta \partial_{1} W)$. Then, if $\gamma_\varepsilon= c_{2,1} \varepsilon$ with 
$$c_{2,1}=  \mathfrak{c}_1^{1+\mathfrak{e}}\min\left(\frac{1}{L {\mathfrak{c}_2}^{\frac{1}{2}} \Upsilon^{\frac{1-q+2r}{2}(1+\mathfrak{e})}},\frac{ \mathfrak{c}_1^{1+\mathfrak{e}}}{L\tilde{L} d \Upsilon^{2r(1+\mathfrak{e})}},\frac{1}{\|\vec{\Delta}(\nabla W)\|_{2,\infty} \Upsilon^{r(1+\mathfrak{e})}}\right),$$
and 
$$c_{1,2}=\max\left( \frac{d' \Upsilon^{2r(1+\mathfrak{e})}}{\mathfrak{c}_1^{2(1+\mathfrak{e})}},\varepsilon \frac{\Upsilon^{\frac{1+3r}{2}(1+\mathfrak{e})}}{\mathfrak{c}_1^{\frac{3}{2}+\mathfrak{e}}}  \right),$$
and $ N_\varepsilon=\frac{c_{1,2}}{c_{2,1}} \varepsilon^{-3}$, then the conclusion of $(i.a)$ holds true.\\
\item 
$(ii.b)$ Under the assumptions of $(ii.a)$, assume that a constant $C$ independent on $d$ exists such that $\|\vec{\Delta}(\nabla W)\|_{2,\infty}^2 \leq C d^{2\rho} $ with $\rho\ge0$. 
If $\varepsilon\in (0,1\wedge (d' d^{-\frac{1-r}{2(1+q-r)}})]$,
 $\gamma_\varepsilon=\varepsilon d^{-\max(1+\frac{2r}{1+q-r},  \rho+\frac{r}{1+q-r})-\mathfrak{e}}$ and $N_\varepsilon=\varepsilon^{-3}d' d^{\max(1+\frac{4r}{1+q-r},\rho+\frac{3r}{1+q-r})+\mathfrak{e}}$, then the conclusion of $(i.b)$ holds true with a positive constant $c$ which only depends on $\mathfrak{e},r,q,\mathfrak{c}_1,{\mathfrak{c}_2}$, $L$ and $\tilde{L}$ (but not  on $d$ and $\varepsilon$).\\

\end{itemize}


 


 
\end{thm} 
\begin{rmq} \label{rmqlaplacien} {Since $\|\vec{\Delta}(\nabla W)\|_{2,\infty}^2={\sup_{x\in\mathbb{R}^d}\sum_{i=1}^{d} (\sum_{j=1}^d \partial_{i,j,j}^3 W(x)})^2$,
the condition  $\|\vec{\Delta}(\nabla W)\|_{2,\infty}^2\le C d^{2\rho} $ }reasonably holds with $\rho \le 3/2$ (if each $\partial_{i,j,j}^3 W$ is bounded by a universal constant) and may hold with lower $\rho$ when the coordinates of the dynamical system are not ``fully connected'' (for instance if $W_i$ depends only on $x_i$, we get $\rho=3/2$).   {When $\rho\le 1+\frac{r}{1+q-r}$ (which is always the case when $r\ge 1/2$),  we obtain the same dependency in $d$ in $(ii.b)$ as in $(i.b)$ but with $\varepsilon^{-3}$ instead of $\varepsilon^{-4}$.}
\end{rmq}



\subsubsection{Application to Bayesian learning}
A consequence of Theorem \ref{cor:thmPoisson} is stated below when we observe a $n$ i.i.d. sample $\xi^{n}$ and when $\varepsilon_n$ refers to the statistical accuracy defined in \eqref{def:epsn} given by $\varepsilon_n= (d/n)^{\frac{1}{2\alpha_c}}$ (we omit the logarithmic term) and when we implicitely assume that $d$ is smaller than $n$, \textit{i.e.} that the sequence $\varepsilon_n \rightarrow 0$ as $n \rightarrow + \infty$ (see Remark \ref{rem:d_vs_n}).













\begin{thm}\label{theo:learning_weak_convex} Assume $(\mathbf{I_{W_1}(c)})$,   $(\mathbf{A}_L)$ and $(\mathbf{PI_U})$.
 Suppose that for any $\xi\in\mathbb{R}^q$, $U(\xi,.)$ satisfies $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ with  $\mathfrak{c}_1$, {${\mathfrak{c}_2}$, $r$ and $q$} independent of $\xi$. Assume furthermore that $r=q$. For the following tunings of $\gamma_{\varepsilon_n}$ and $N_{\varepsilon_n}$ given by:

\begin{itemize}
\item[$(i)$] If  $r \ge 1$, then $\gamma_{\varepsilon_n} = d^{-(2r+1-\alpha_c^{-1})}  n^{-2r-\alpha_c^{-1}},$
and $N_{\varepsilon_n}  = n^{2 \alpha_c^{-1}+4r} d^{1+4r-2\alpha_c^{-1}}.$


\item[$(ii)$] If  $ r=q=0$, then
$\gamma_{\varepsilon_n} =n^{-2}$
and
$
{N_{\varepsilon_n}} =  n^{\frac{1}{2}(1+\alpha_c^{-1})} d^{\frac{1}{2}(1-\alpha_c^{-1})}.
$
\item[$(iii)$] For any $r \in (0,1)$, we have
$
\gamma_{\varepsilon_n}= n^{-(2r+\alpha_c^{-1})}d^{-1-2r+\alpha_c^{-1}} \wedge n^{-\frac{2}{1+r}} d^{\frac{2r}{1+r}},
$
and 
$$
N_{\varepsilon_n} = \gamma_{\varepsilon_n}^{-1} \left[ n^{\frac{1}{2}\alpha_c^{-1}-\frac{3}{2}(1-r)} d^{\frac{1+3r}{2} -\frac{1}{2} \alpha_c^{-1}}\vee d^{2r-\alpha_c^{-1}} n^{\alpha_c^{-1}-2(1-r)}\right].
$$
\end{itemize}
we can find a constant $C$ that depends on $q,r,\mathfrak{c}_1,{\mathfrak{c}_2}$ but not on $d$ and $n$ such that:
$$
\mathbb{E}[\|\widehat{\theta}^{\gamma}_{n,t_N}-\theta^\star\|^2] \leq C \varepsilon_n^2
$$
\end{thm}















\subsection{Discretization in the strongly convex setting} 
 This paragraph concerns the $L$-smooth  and strongly convex case, which is defined as follows. 
\begin{ass}[Assumption $(\mathbf{SC}_\rho)$]
We assume that for any $\xi \in \mathbb{R}^q$, $U(\xi,.)$ is $\rho$-strongly convex: \textit{i.e.}, for any $\xi \in \mathbb{R}^q$:
$$
\forall z \in \mathbb{R}^d \quad  \forall \theta \in \mathbb{R}^d: \qquad ^t z \nabla^2_{\theta} U(\xi,\theta) z \ge \rho |z|^2.
$$
\end{ass}
\begin{thm}\label{cor:thmPoissonSC}
Assume  {$(\mathbf{A}_L)$} with $L\ge 1$ and $(\mathbf{SC}_\rho)$.  Let $\bar{X}^{\gamma}$ denote the Euler scheme with constant step-size $\gamma$ initialized at $x_0$. 
 Let $f$ be a ${\mathcal C}^2$ function from $\mathbb{R}^d$ to $\mathbb{R}^{d'}$ with $d'\le d$,  $[f]_1\le 1$ and $[Df]_{1,\star}\le 1$ and consider $\varepsilon>0$


\noindent  (i)  If $\gamma_\varepsilon=  \frac{\rho^2}{L^2 d } \varepsilon^2 \wedge \frac{\rho}{L^2}  \wedge \frac{d}{L^2 |x_0-x^\star|^2}$ and  
$
N_\varepsilon \ge d' \rho^{-2}  \gamma_{\varepsilon}^{-1} \varepsilon^{-2} \vee  \sqrt{d} \rho^{-3/2} \varepsilon^{-1} \gamma_{\varepsilon}^{-1}
$
, then:
\begin{equation*}
 \mathbb{E}_{x_0}\left[\left|\frac{1}{N_\varepsilon}\sum_{k=1}^{N_\varepsilon} \bar{X}_{k\gamma}^{\gamma}-\pi(\mathbf{I}_d)\right|^2\right]\lesssim_{uc} {\varepsilon^2}.
 \end{equation*}


\noindent
 (ii) Assume furthermore that $W$ is ${\mathcal C}^3$ with $D^2 W$ $\tilde{L}$-Lipschitz for $\nsp{.}$ and that
$\|\vec{\Delta}(\nabla W)\|_{2,\infty}^2<+\infty.$
If $\gamma_\varepsilon=  \mathfrak{b}_2^{-\frac{1}{2}} \varepsilon$ with:
$$ \mathfrak{b}_2=
d^2+\frac{L^4 d}{\rho^3}+
L^2 {\left( \frac{1 }{\rho^2}+ \frac{\tilde{L}^2}{\rho^4}\right)}
+
\frac{ \|\vec{\Delta}(\nabla W)\|_{2,\infty}^2 }{\rho^2  } 
+{2   \frac{L^4 }{\rho^2}  |x_0-x^\star|^2},$$
and $ N_\varepsilon=\varepsilon^{-3} \frac{\sqrt{\mathfrak{b}_2} d'}{\rho^2} \vee \gamma_{\varepsilon}^{-1} \vee d \gamma_{\varepsilon}^{-1} \rho^{-1}$, then:
\begin{equation*}
 \mathbb{E}_{x_0}\left[\left|\frac{1}{N_\varepsilon}\sum_{k=1}^{N_\varepsilon} \bar{X}_{k\gamma}^{\gamma}-\pi(\mathbf{I}_d)\right|^2\right]\lesssim_{uc} {\varepsilon^2}.
 \end{equation*}


\end{thm} 

\begin{rmq}\label{rmqdurmusmus}
{Note that in $(i)$, when $\varepsilon$ is small enough and $x_0$ sufficiently close to $x^\star$, we have  $\gamma_\varepsilon=  \frac{\rho^2}{L^2 d }\varepsilon^2$ . In this case, for a $\mathcal{C}^2$ function, the computational cost induced by $(i)$ is of the order $\mathcal{O}\left( \frac{d d' L^2}{\rho^4} \varepsilon^{-4}\right)$.}
This result slightly improves the bound derived in \cite{durmus} with the same dependency in $d$ and $\varepsilon$ and a better one in terms of $\rho$ and $L$, with a completely different method of proof. We also observe that we recover in this case the limiting case $r=q=0$ of Theorem \ref{cor:thmPoisson} $i)$ and $ii)$ with a sharp dependency in terms of $\rho$ and $L$.


If now the function $f$ is more regular and three times differentiable and if $\|\vec{\Delta}(\nabla W)\|_{2,\infty}^2 \lesssim_{uc} \rho^{-2}(L \tilde{L}d)^{{2}}$ (see Remark \ref{rmqlaplacien} for a discussion on $\|\vec{\Delta}(\nabla W)\|_{2,\infty}^2$), then the computational cost becomes $\mathcal{O}_{id}\left( \frac{d L^2}{\rho^4} \varepsilon^{-3}\right)$. Up to our knowledge, this result is new for deriving an $\varepsilon$ approximation M.S.E. cost.
\end{rmq}

The next theorem gives a quantitative setup to attain an $\varepsilon_n^2$ accuracy for a discrete LMC procedure with a constant step-size $\gamma$ where  $\varepsilon_n^2 = (d/n)^{\alpha_c^{-1}}$ is defined by \eqref{def:epsn} in the situation where  $\varepsilon_n \rightarrow 0$ as $n \rightarrow + \infty$.


\begin{thm}\label{theo:learning_strong_convex}
Assume that $(\mathbf{I_{W_1}(c)})$, $(\mathbf{A}_L)$, $(\mathbf{PI_U})$ and $(\mathbf{SC}_\rho)$ hold and that $|\theta_0-\theta^\star|^2 \lesssim_{uc} d$. For the following tunings of parameters:
 \begin{itemize}
\item $(i.a)$ if $\gamma_{\varepsilon_n} =  n^{-2}$ and $N_{\varepsilon_n} =  n^{\frac{1}{2}(1+\alpha_c^{-1})} d^{\frac{1}{2}(1-{\alpha_c}^{-1})}$ operations.
\item $(i.b)$ if $|\hat{\theta}^{\gamma}_{n,0} - \theta^\star|^2 \leq d n^{-2}$, $\gamma =  n^{-1}$ and $N = n \vee d$ operations.
\end{itemize} 
then a constant $C$ that depends on $\alpha_c,L,\rho$ but not on $d$ and $n$ exists such that:
$$\mathbf{E}\left[\left|\widehat{\theta}^{\gamma}_{n,t_N}-\theta^\star\right|^2\right] \leq C \varepsilon_n^2.$$
\end{thm}
\noindent This result deserves several comments.
\begin{itemize}
\item 
This theorem indicates that the step size should be chosen as  $\gamma \propto n^{-2}$ (first case) or $\gamma\, \propto \, n^{-1} $ (second case), which becomes smaller when $n$ increases. This   is due to the sharper statistical accuracy we can expect with the posterior mean when we have a large amount of observations.



\item A stricking point derived from the previous result is that the tuning
$(\gamma,N) = (n^{-2},n)$ is ``universal'', which means that regardless the value of $\alpha_c$, the computation of the posterior mean with an explicit Euler scheme with step-size $n^{-2}$ and $nd$ iterates leads to an optimal statistical result.
If we now consider that each iteration of the LMC has a cost $d$, the global cost of the procedure is then $ n d$.
 
 
 \item We also observe that our results of Theorem \ref{theo:learning_weak_convex} and of Theorem \ref{theo:learning_strong_convex}
 match, \textit{i.e.}, the cost of learning in strongly convex situation is identical to the one obtained under $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ when $r=q=0$.

\item We  observe that with Assumption $(\mathbf{SC}_\rho)$, besides the obvious curse of dimensionality for large $d$ concerning the \textit{statistical} accuracy of $\widehat{\theta}_n$, there is no burst of the 
\textit{computational} cost, which remains polynomial in terms of $n$ and $d$. 
\item Finally, it is worth saying that in the previous statement, we did not use the $\mathcal{C}^3$ assumption to assess the cost of the Bayesian learning, essentially because the potential improvement is strongly model dependent owing to the size of $\|\vec{\Delta}(\nabla W)\|_{2,\infty}^2$. It could be certainly helpful in some very specific situations.
\end{itemize}





\subsection{Discussion on the discretization results \label{sec:sub:discussion}}
  









 











 




 
 

\textit{Polynomial cost.}
Overall, the leading take-home message when considering the discrete approximation and the concrete estimator is that  in both strongly and weakly convex case, we obtain a complexity that evolves as a polynomial of $n$ and $d$, the complexity being much lower in the strongly convex case. 
The worst situation is attained when $r$ is close to $1$, and $\alpha_c = 1$, and we obtain in that case a computational cost of the order $n^{4} d^{3}$  (by applying Theorem \ref{theo:learning_weak_convex} $(ii)$).
All the more, we observe that in our results, the complexity of Bayesian learning is seriously damaged with the loss of strong convexity, both in terms of $n$ and $d$, and this loss is parametrically described with the help of Assumption $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$.

\textit{Lack of log-concavity.}
 Behind our polynomial cost result, the log-concave assumption plays a central role: withouth a such assumption, sampling has to be considered with specific models and specific algorithms.
 To bypass the absence of log-concavity, a popular strategy relies on the existence of a functional inequality satisfied by the target measure. For example, \cite{Jordan-Flammarion} (see also \cite{Improved_LSI}) assumes the existence of a  log-Sobolev inequality (LSI) and obtain a total variation mixing time of the order $K d \varepsilon^{-2}$. A such LSI is then shown to be verified with the help of a perturbation approach (see \cite{Holley}) for strongly log-concave distributions outside a ball of radius $R$, but the dependency of $K$ may be exponentially large with $R$, so that the overall cost depends on a balance between $d$ and $R$.
   As a new example of the role of functional inequalities, in \cite{Ho3}, the authors obtain a polynomial computational cost with a reflected Metropolis-Hastings random walk, that is well suited for symmetric mixture model (which is not log-concave) and is far different from a pure Langevin strategy.
   
   \noindent Interestingly, our approach relies on the Poisson equation (that could be studied in non-convex situations) whereas  \cite{Ho3}  relies on functional inequalities such as the Poincar\'e one.

\textit{Existing results on MSE.}
As indicated above,  we obtained the complexity to compute an 
$\varepsilon$-approximation of the posterior mean with the M.S.E. loss, \textit{i.e.} the complexity to guarantee that the M.S.E. becomes smaller than $\varepsilon^2$. This is the purpose of Theorem \ref{cor:thmPoisson} and Theorem 
\ref{cor:thmPoissonSC}
  respectively in the weakly and strongly convex cases.
   The related orders of complexity  are given in Table \ref{table:complexity}, where we also draw some comparisons with some state of the art results related to the complexity of Bayesian sampling. Up to our knowledge, the only paper that derives an ad-hoc study of the M.S.E. criterion is \cite{durmus}, that obtains a computational cost of the order $d \varepsilon^{-4}$ and $d \varepsilon^{-3}$ in the strongly convex case. If our results are rather similar to those of \cite{durmus} in the strongly convex case (same dependency in terms of $d$ and $\varepsilon$), we largely improve the state of the art in the weakly convex situation.
   

\textit{Existing results with other criteria.}
   Other results are related to some different criteria and for our purpose, these results are stated up to a normalization factor: actually, in the recent papers \cite{Durmus3,Dalalyan2} (see also \cite{Jordan-acceleration}) that we compare with, the complexity is defined in a slightly different way, omitting the Monte-Carlo factor. More precisely, oppositely to our paper based on a Cesaro average (involving only one path), these papers use a classical Monte-Carlo approach to approximate $\pi(f)$ (for a given function $f$) by $N_{MC}^{-1}(Z_1+\ldots+Z_{N_{MC}})$ where
  $(Z_j)_{1 \le j \le N_{MC}}$ denotes an $i.i.d.$ sequence of  $N_{MC}$ i.i.d. random variables. Then, for a given $\varepsilon$, these papers define the complexity as the number $n_\varepsilon$ of iterations of the Euler-scheme to compute $Z_1$. In order to draw some fair comparisons, we need to consider the ``true'' complexity, $i.e.$ to multiply their complexity $n_\varepsilon$ by $MC(\varepsilon)={\rm Var}(Z_1)\varepsilon^{-2}$, $i.e.$ by the number of Monte-Carlo simulations that are necessary to obtain a Monte-Carlo M.S.E  lower than $\varepsilon^2$. Furthermore, since the involved function is $\mathbf{I}_d$, it is reasonable to assume that  ${\rm Var}(Z_1)\propto d$, so that we assume that the true complexity of the compared papers is $n_\varepsilon d \varepsilon^{-2}$.

 
 Finally, former works  state results with different distances: Total Variation, Kullback-Leibler, $W_1$ or $W_2$. We only consider $W_1$ or $W_2$ results in Table \ref{table:complexity}, which {seem to be} the only ones that can apply to the non-bounded (Lipschitz) function $\mathbf{I}_d$, the KL divergence and TV distance being too weak   to draw some conclusions on the posterior mean approximation. In particular, we do not report in Table \ref{table:complexity} the TV results presented in \cite{Durmus3} or KL results in \cite{Dalalyan}. First, we emphasize that we obtain in our work the best dependency (in terms of $\varepsilon$) in the weakly-convex situation, thanks to our parametric $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ assumption. It would be very tempting to understand the behaviour of KLMC and $\alpha$-KLMC within this framework. 
  Second, we recover the good dependency on $d$ and $\varepsilon$ of the LMC in the strongly convex situation. At last, LMC is outperformed by KLMC in this same setting as reported in \cite{Dalalyan-Bernoulli} when $\varepsilon$ is small enough.







 \small{

\small{
\begin{table*}\centering
\ra{1.3}
\begin{tabular}{@{}lrrrcrrrcrrr@{}}\toprule
 & \multicolumn{3}{c}{$(\mathbf{SC}_\rho)$ and $(\mathbf{A}_L)$} & \phantom{abc}& \multicolumn{3}{c}{$\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ (or weakly convex) and $(\mathbf{A}_L)$} &
\phantom{acc} \\
\cmidrule{2-4} \cmidrule{6-8} 
& $\gamma$

 & $N(\varepsilon)$   &&&  $\gamma$ 
 & $N(\varepsilon)$   \\ \midrule
This work - LMC - $\mathcal{C}^2$ & $  \mathcal{O}( \frac{\rho^2}{L^2 d} \varepsilon^{{2}})$   & $   \mathcal{O}( \frac{d L^2}{\rho^4 } \varepsilon^{{-4}})$  &  & &$  \mathcal{O}(d^{-(1+ \frac{2r}{1+q-r})}  \varepsilon^{2})$   &$  \mathcal{O}_{id}(d^{1+ \frac{4r}{1+q-r}} \varepsilon^{-4})$   \\
This work - LMC - $\mathcal{C}^3$ & $  \mathcal{O}( \frac{\rho}{L^2 d} \varepsilon^{{}})$    & $   \mathcal{O}( \frac{d L^2}{\rho^4 } \varepsilon^{{-3}})$ & &  & $  \mathcal{O}(d^{1+ \frac{2r}{1+q-r}} \varepsilon)$   &$  \mathcal{O}_{id}(d^{1+ \frac{4r}{1+q-r}} \varepsilon^{-3})$   \\
  \cite{durmus} - LMC - $\mathcal{C}^2$ & $  \mathcal{O}(\frac{\rho^3}{d L^4}\varepsilon^{2})$    &$ \mathcal{O}(\frac{d L^4}{\rho^4} \varepsilon^{-4})$  \\
    \cite{durmus} - LMC - $\mathcal{C}^3$ & $  {\mathcal{O}(\frac{\rho}{d L^2}\varepsilon)}$    &$ {\mathcal{O}(\frac{d L^2}{\rho^4} \varepsilon^{-3})}$  \\
\cite{Durmus3} - LMC  - $\mathcal{C}^2$ & $  {\mathcal{O}(\frac{\rho}{d L}\varepsilon^2)}$  
 &$ {\mathcal{O}(\frac{d^2 L}{\rho^2} \varepsilon^{-4})}$  \\
  \cite{Dalalyan-Bernoulli} -  KLMC  $\mathcal{C}^2$ & $  \mathcal{O} (\frac{\rho}{L \sqrt{d}}\varepsilon)$
  & $\mathcal{O}_{id}(\frac{d^2 L}{\rho} \varepsilon^{-3})$ \\% & - &  - & - &&  \\
  \cite{Dalalyan2} - $\alpha$-KLMC  - $\mathcal{C}^2$ &  &   &  && $  \mathcal{O}_{id}(d^{-1} \varepsilon^4)$
  & $\mathcal{O}_{id}(d^3 \varepsilon^{-7})$\\
  \cite{Dalalyan2} - $\alpha$-KLMC  - $\mathcal{C}^3$   &  &   &  && $  \mathcal{O}_{id}(d^{-1/2} \varepsilon^3)$ 
   & $\mathcal{O}_{id}(d^3 \varepsilon^{-6})$\\

\bottomrule
\end{tabular}
\caption{Complexity $N(\varepsilon)$ of an $\varepsilon$-approximation of the Mean-Squared Error with a constant step-size $\gamma$ of several methods. Left: strongly convex case (with dependency on $d$, $\rho$ and $L$), Right: weakly convex case with dependency on $d$.
LMC: overdamped Langevin Monte Carlo, KLMC: Kinetic Langevin Monte Carlo, $\alpha$-KLMC: $\alpha$ penalized KLMC. 
\label{table:complexity}}
\end{table*}  }

 



\section{Minimax Bayesian posterior mean consistency}\label{sec:bayes}
This paragraph is dedicated to the proof of Theorem \ref{theo:consistency} (Bayesian consistency rate) and of Theorem \ref{theo:lower_bound} (minimax rate).
 
 



\subsection{Poincare inequality and consequences}
 We   state a  famous result for the family $(\mathbb{P}_{\theta})_{\theta \in \mathbb{R}^d}$ of  Bobkov and Ledoux (see \textit{e.g.} \cite{BL}), borrowed in \cite{Ledoux}\footnote{In \cite{BL}, the authors assume that the function $f$ is   bounded. 
{However, when} the concentration function $\frac{\delta^2}{4C k}\wedge\frac{\delta}{2\sqrt{C k}}$ {goes} to $\infty$ when $\delta\to\infty$, {the boundedness assumption can be removed (see Proposition 1.7 in \cite{Ledoux} for details)}.
}. 




\begin{prop}\label{prop:BK}
Assume $(\mathbf{PI_U})$, then for any differentiable k-Lipschitz real function $f$:
$$
\forall \theta \in \theta \quad \forall n \in \mathbb{N}^* \qquad 
\mathbb P_{\theta}\left(\left| \frac 1n\sum_{i=1}^nf(\xi_i)-\pi_\theta(f)\right| \geq\delta\right)\leq 2e^{-n\frac{\delta^2}{4k^2 C^U_P}\wedge\frac{\delta}{2 k \sqrt{ C^U_P}}}.$$
\end{prop}

 
 We will apply this result for $f=\Psi$ involved in  $(\mathbf{I_{W_1}(c)})$ and with $f=\nabla U_{\theta}$. In particular, using Proposition \ref{prop:BK}, we obtain the following result (see the proof in appendix A).



\begin{cor}\label{lem:BK}

 Let  $(\mathbf{I_{W_1}(c)})$ holds and denote by $\Psi$ the corresponding 1-Lipschitz function. Then,
\begin{itemize}\item[$i)$]
$$\forall \theta \in \mathbb{R}^{{d}} \qquad \mathbb P_{\theta}\left(\left|\frac 1n\sum_{i=1}^n\Psi({\xi}_i)-\mathbb E_\theta \Psi(\xi_1)\right|\geq\delta\right)\leq 2 e^{-n\frac{\delta^2}{4 C^U_P}\wedge\frac{\delta}{2\sqrt{C^U_P}}}.$$

\item[$ii)$]
$$
\forall \theta \in \mathbb{R}^{{d}} \qquad 
\mathbb P_{\theta}\left(\left|\frac 1n\sum_{i=1}^n\nabla_{\theta} U(\xi_i,\theta)\right|\geq\delta\right)\leq 2 d e^{-n\frac{\delta^2}{4 L^2 C^U_P  d}\wedge\frac{\delta}{2 L \sqrt{C^U_P  d}}}.$$
\end{itemize}
\end{cor}



Corollary \ref{lem:BK} will be an essential ingredient for the construction of some efficient statistical tests in the family of probability distributions $(\mathbb{P}_{\theta})_{\theta \in \mathbb{R}^d}$. This key corollary is used in Section \ref{sec:tests}.
\subsection{Consistency rate of the posterior mean}\label{sec:consistency}
To study the behavior of $(\widetilde{\theta}_n)_{n \ge 0}$
 introduced in Equation \eqref{eq:posterior_mean},
 we adopt the presentation of \cite{CasvdV} and in particular the link between the posterior mean and the posterior distribution. As noticed in  \cite{CasvdV}, there is an important need to upper bound the tail of the posterior distribution (far from $\theta^{\star}$).
  To this end, for a non-negative sequence $(\varepsilon_n)_{n\geq 1}$ fixed later on, we introduce the separation radius:
\begin{equation}\label{eq:ran}
r_{n}=\varepsilon_n+r,\end{equation}
where $r$ will vary from $0$ to $+ \infty$. 
\subsubsection{Statistical tests} \label{sec:tests}
 

Statistical tests have a long standing history in Bayesian literature (see \textit{e.g.} \cite{LeCam,GhosalGhoshvdVaart}) to obtain consistency results as well as rates of convergence of Bayes procedures.
We introduce an appropriate family of tests $(\phi_n^r)_{n\geq 1}$ parametrized by $r>0$ (see Equation \eqref{eq:ran}) and
 defined for $n\in\mathbb N^\star$ by:
 \begin{equation}\label{def:tests}
\phi_n^r\left(\mathbf{\xi^{n}}\right) = \mathbf{1}_{\left| \frac{1}{n} \sum_{i=1}^n \Psi(\xi_i) - \pi_{\theta^\star}(\Psi) \right| \geq \frac{c(r_{n})}{2}}. 
\end{equation}
It is expected that $\phi_n^r$ is equal to $0$ with an overwhelming probability under the null hypothesis $\mathbb{P}_{\theta^{\star}}$ whereas $\phi_n^r$ it is equal to $1$ w.o.p.  under $\mathbb{P}_{\theta}$ when $|\theta-\theta^{\star}|$ is large enough thanks to $(\mathbf{I_{W_1}(c)})$.
We prove the following estimations in appendix A of the first and second type error of  $(\phi_n^r)_{n\geq1}$.

\begin{prop}\label{prop:test} The sequence of tests $(\phi_n^r)_{n\geq1}$ satisfies
\begin{itemize}
\item[$i)$] 
$
\mathbb{P}_{\theta^{\star}} \left( \phi_n^r\left(\mathbf{\xi^{n}}\right)
=1\right) \leq 2  e^{-n \frac{c(r_{n})^2}{ 16 C^U_P} \wedge \frac{c(r_{n})}{4 \sqrt{C^U_P}}},
$
\item[$ii)$] 
$
 \sup_{\theta \, : \, |\theta-\theta^{\star}| \geq r_{n}} \mathbb{P}_{\theta} \left(\phi_n^r\left(\mathbf{\xi^{n}}\right)
=0 \right) \leq 
 2   e^{-n \frac{c(r_{n})^2}{16 C^U_P} \wedge \frac{c(r_{n})}{4 \sqrt{C^U_P}}}.
$
\end{itemize}
 

\end{prop}

The next result is a technical estimation related to the denominator (normalizing constant) involved in the posterior distribution distribution. A simple application of Corollary \ref{lem:BK} yields the next result.

\begin{lem}\label{lem:petite_boule}
For any $t>0$, define the sets
$\mathcal A_n^t =\left\{\left| \frac 1n\sum_{i=1}^n\nabla_{\theta} U(\xi_i,\theta^\star)\right| \leq t\right\},$ then:
 $$
\forall n \in \mathbb{N}^\star \quad \forall t>0 \qquad  
 \mathbb{P}_{\theta^{\star}}(\{\mathcal{A}_n^{t}\}^{c}) \leq 2 d e^{-n \left( \frac{t^2}{4 L^2 C^U_P d} \wedge \frac{t}{2 L \sqrt{C^U_P {d}  }}\right)}.$$
\end{lem}


\subsubsection{Proof of the posterior mean consistency \label{sec:proof-posterior}}


\begin{proof}[Proof of Theorem \ref{theo:consistency}] 
Our proof adopts the strategy  of \cite{CasvdV}.


\noindent \underline{Step 1: Decomposition of the quadratic risk.}
We remark that  for all $n\in\mathbb N^\star$:
\begin{align}
\mathbb{E}_{\theta^{\star}}\left[\left|\widetilde{\theta}_n-\theta^{\star}\right|^p\right] & =  \mathbb{E}_{\theta^{\star}} \left[ \left| \int_{\mathbb R^d} (\theta - \theta^{\star}) \text{d}\pi_n(\theta) \right|^p \right] \nonumber\\
& \leq   \mathbb{E}_{\theta^{\star}} \left[  \int_{\mathbb R^d}  \left|\theta - \theta^{\star}  \right|^p \text{d}\pi_n(\theta)\right] \nonumber\\
& =   p \mathbb{E}_{\theta^{\star}} \left[  \int_{0}^\infty t^{p-1} \pi_n(|\theta-\theta^{\star}| \geq t) \text{d}t \right]\nonumber\\
& = p \mathbb{E}_{\theta^{\star}} \left[  \int_{0}^{\varepsilon_n} t^{p-1} \pi_n(|\theta-\theta^{\star}| \geq t) \text{d}t+\int_{\varepsilon_n}^\infty t^{p-1} \pi_n(|\theta-\theta^{\star}| \geq t) \text{d}t \right]\nonumber\\
&\leq   \varepsilon_n^p + p \int_{0}^{+ \infty}  r_{n}^{p-1}  \mathbb{E}_{\theta^{\star}} \left[ \pi_n(|\theta-\theta^{\star}| \geq r_{n})\right] \text{d}r, \label{eq:bornequad}
\end{align}
where we used the Jensen inequality in the second line, an integration by part in the third line, a direct integration $\int_0^{\varepsilon_n} p t^{p-1} \text{d} t =  \varepsilon_n^p$ in the last line associated with the Fubini relationship.

\noindent
\underline{Step 2: Use of the tests $(\phi_n^r)_{n\geq1}$.}
We now use the tests $(\phi_n^r)_{n\geq1}$ and the sets $(\mathcal A_n^t)$, we can write:
\begin{align}
\mathbb{E}_{\theta^{\star}} \left[ \pi_n(|\theta-\theta^{\star}| \geq r_{n}  )
\right] = & \,\mathbb{E}_{\theta^{\star}} \left[ \phi_n^r(\mathbf{\xi^{n}}) \pi_n(|\theta-\theta^{\star}| \geq r_{n}  )
\right]\nonumber  \\
&+ \mathbb{E}_{\theta^{\star}} \left[ (1- \phi_n^r(\mathbf{\xi^{n}})) \pi_n(|\theta-\theta^{\star}| \geq r_{n}  ) \mathbf{1}_{\mathcal{A}_n^t}
\right]\nonumber \\ 
& + \mathbb{E}_{\theta^{\star}} \left[ (1- \phi_n^r(\mathbf{\xi^{n}})) \pi_n(|\theta-\theta^{\star}| \geq r_{n}  ) \mathbf{1}_{\{\mathcal{A}_n^t\}^c}
\right] .\label{eq:introtest}
\end{align}
From this expression we can deduce the following inequality:
\begin{align*}
\mathbb{E}_{\theta^{\star}} \left[ \pi_n(|\theta-\theta^{\star}| \geq r_{n}  )
\right]\leq&\, \mathbb{E}_{\theta^{\star}} \left[ \phi_n^r(\mathbf{\xi^{n}})\right] +  \mathbb{E}_{\theta^{\star}} \left[ (1- \phi_n^r(\mathbf{\xi^{n}})) \pi_n(|\theta-\theta^{\star}| \geq r_{n}  ) \mathbf{1}_{\mathcal{A}_n^{t}}
\right] \\& + \mathbb{P}_{\theta^{\star}}(\{\mathcal{A}_n^{t}\}^c).
\end{align*}

\noindent
$\bullet$
Study of $\mathbb{E}_{\theta^{\star}} \left[ (1- \phi_n^r(\mathbf{\xi^{n}})) \pi_n(|\theta-\theta^{\star}| \geq r_{n}  ) \mathbf{1}_{\mathcal{A}_n^t}\right]$. We write that:
\begin{align}
\displaystyle\pi_n(|\theta-\theta^{\star}| \geq r_{n}  )  &= \int_{\theta \, : \, |\theta-\theta^{\star}| \geq r_{n} } \text{d}\pi_n(\theta)  = \frac{\displaystyle\int_{\theta \, : \, |\theta-\theta^{\star}| \geq r_{n} }  \frac{e^{-W_n(\mathbf{\xi^n},\theta)}}{e^{-W_n(\mathbf{\xi^n},\theta^{\star})}}\text{d}\pi_0(\theta)}{\displaystyle\int_{\mathbb{R}^d }  \frac{e^{-W_n(\mathbf{\xi^n},\theta)}}{e^{-W_n(\mathbf{\xi^n},\theta^{\star})}}\text{d}\pi_0(\theta)}.\label{eq:numerateur_denominateur}
\end{align}
At this stage, we  control the denominator and the numerator separately.  Let us denote by $Z_t = \pi_0(B(\theta^{\star},t))$ the prior mass of the Euclidean ball centered at $\theta^{\star}$ and of radius $t$. We have \begin{align*}
\log \left( \int_{\mathbb{R}^d} \frac{e^{-W_n(\mathbf{\xi^n},\theta)}}{e^{-W_n(\mathbf{\xi^n},\theta^{\star})}}d\pi_0(\theta) \right) & \geq  
\log \left( \int_{B(\theta^{\star},t)} \frac{e^{-W_n(\mathbf{\xi^n},\theta)}}{e^{-W_n(\mathbf{\xi^n},\theta^{\star})}}\text{d} \pi_0(\theta) \right)
\\ 
& \geq \log \left( \int_{B(\theta^{\star},t)} \frac{e^{-W_n(\mathbf{\xi^n},\theta)}}{e^{-W_n(\mathbf{\xi^n},\theta^{\star})}} \frac{\text{d} \pi_0(\theta)}{Z_t} \right) + \log Z_t \\
& \geq 
\int_{B(\theta^{\star},t)}  \sum_{i=1}^n [U(\xi_i,\theta^{\star})-U(\xi_i,\theta)] \frac{\text{d} \pi_0(\theta)}{Z_t}  + \log Z_t,
\end{align*}
where we used the Jensen inequality in the last line with the concave function $\log$ and the normalized measure $\text{d} \pi_0 Z_t^{-1}$ over $B(\theta^{\star},t)$.
Using that 
$\nabla_\theta U(\xi,.)$ is L-Lipschitz we get
$$ 
\forall x \in \mathbb{R}^d \qquad 
U(\xi,\theta_1)-U(\xi,\theta_2) \leq \langle \theta_1-\theta_2, \nabla_{\theta} U(\xi,\theta_2)\rangle + \frac{L}{2} \|\theta_1-\theta_2\|^2,$$
for all $(\theta_1,\theta_2)\in \mathbb{R}^d$, which implies that:
$$
\forall i \in \{1,\ldots,n\} \quad \forall \theta \in \mathbb{R}^q \qquad 
\left|U(\xi_i,\theta)-U(\xi_i,\theta^{\star}) - \langle \theta-\theta^{\star},\nabla U(\xi_i,\theta^{\star})\rangle\right| \leq \frac{L}{2} |\theta-\theta^{\star}|^2.
$$
 Using a sum over $i$ and the triangle inequality, we then deduce that:
$$
\forall \theta \in \mathbb{R}^d \quad \sum_{i=1}^n U(\xi_i,\theta^\star)-U(\xi_i,\theta) \geq - \left| \langle \theta-\theta^{\star},\sum_{i=1}^n \nabla_{\theta} U(\xi_i,\theta^{\star} )\rangle \right| - n \frac{L}{2} |\theta-\theta^{\star}|^2.
$$
The Cauchy-Schwarz inequality yields:
$$
\left| \langle \theta-\theta^{\star},\sum_{i=1}^n \nabla_\theta U(\xi_i,\theta^{\star}) \rangle \right| \leq |\theta-\theta^{\star} | \, \left| \sum_{i=1}^n \nabla_\theta U(\xi_i,\theta^{\star})\right|.
$$
An integration over $B(\theta^{\star},t)$ with the normalized measure $\pi_0 Z_t^{-1}$  leads to:
\begin{align*}
\log \left( \int_{\mathbb{R}^d} \frac{e^{-W_n(\mathbf{\xi^n},\theta)}}{e^{-W_n(\mathbf{\xi^n},\theta^{\star})}}\text{d}\pi_0(\theta) \right) & \geq - n \frac{L}{2}  t^2 \frac{ \pi_0(B(\theta^{\star},t)) }{Z_t} - t \left\| \sum_{i=1}^n \nabla_{\theta} U(\xi_i,\theta^{\star})\right\| + \log(Z_t) \nonumber\\
& \geq - n \frac{L}{2}  t^2  - t \left\| \sum_{i=1}^n \nabla_\theta U(\xi_i,\theta^{\star})\right\| +  \log (Z_t).
\end{align*}
To lower bound the denominator, we use the set $\mathcal A_n^t$ and we have
\begin{align}
\log \left( \int_{\mathbb{R}^d} \frac{e^{-W_n(\mathbf{\xi^n},\theta)}}{e^{-W_n(\mathbf{\xi^n},\theta^{\star})}}\text{d}\pi_0(\theta) \right)\mathbf 1_{\mathcal A_n^t} & \geq\left( - n \frac{L}{2}  t^2  - t \left\| \sum_{i=1}^n \nabla_\theta U(\xi_i,\theta^{\star})\right\| + \log(Z_t)\right)\mathbf 1_{\mathcal A_n^t} \nonumber\\
& \geq\left( - nt^2 \left(\frac{L}{2}+1\right)   +  \log (Z_t)\right)\mathbf 1_{\mathcal A_n^t}.\label{eq:minoration_intermediaire}
\end{align}
Using \eqref{eq:minoration_intermediaire} with \eqref{eq:numerateur_denominateur} and the Jensen Inequality, we have
\begin{align*}
\lefteqn{\mathbb{E}_{\theta^{\star}} \left( (1-\phi_n^r(\mathbf{\xi^{n}})) \pi_n(|\theta-\theta^{\star}| \geq r_{n}) \mathbf{1}_{\mathcal{A}_n^{t}} \right)} \\
& \leq \frac{ \mathbb{E}_{\theta^{\star}} \left[ (1-\phi_n^r(\mathbf{\xi^{n}})) \int_{\theta: |\theta-\theta^{\star}| \geq r_{n}} \frac{e^{-W_n(\mathbf{\xi^n},\theta)}}{e^{-W_n(\mathbf{\xi^n},\theta^{\star})}} \text{d}\pi_0(\theta) \right]}{Z_t e^{- n \left(\frac{L}{2}+1\right) t^2 }} \\
& \leq \int_{\theta: |\theta-\theta^{\star}| \geq r_{n}}
\mathbb{E}_{\theta^{\star}} \left[ (1-\phi_n^r(\xi^n))\frac{e^{-W_n(\mathbf{\xi^n},\theta)}}{e^{-W_n(\mathbf{\xi^n},\theta^{\star})}} \right]  \text{d}\pi_0(\theta) e^{n t^2  \left(  \frac{L}{2}  + 1 \right) }(Z_t )^{-1} \\
& \leq(Z_t )^{-1} e^{n t^2 \left(  \frac{L}{2}  + 1 \right)}\sup_{\{\theta \, : |\theta-\theta^{\star}| \geq r_{n}\}}\mathbb{E}_{\theta} \left[ 1-\phi_n^r(\mathbf{\xi^{n}})  \right] \\
& \leq 2   e^{n t^2 \left(  \frac{L}{2}  + 1 \right)-\log \pi_0(B(\theta^{\star},t))} e^{-n \frac{c(r_{n})^2}{16 C^U_P} \wedge \frac{c(r_{n})}{4 \sqrt{C^U_P}}},
\end{align*}
where in the penultimate line we used a change of measure from $\mathbb{P}_{\theta^{\star}}$ to $\mathbb{P}_{\theta}$.



\noindent
$\bullet$
Study of $\mathbb{E}_{\theta^{\star}} \left[ \phi_n^r(\mathbf{\xi^{n}})\right]$.
Using the  first type error given by $i)$ of Proposition \ref{prop:test}, we have:
$$
\mathbb{E}_{\theta^{\star}}[\phi_n^r(\mathbf{\xi^{n}})] 
 \leq 2  e^{-n \frac{c(r_{n})^2}{16 C^U_P} \wedge \frac{c(r_{n})}{4 \sqrt{C^U_P}}}.
$$



\noindent
$\bullet$
Study of $\mathbb{E}_{\theta^{\star}} \left[ (1- \phi_n^r(\mathbf{\xi^{n}})) \pi_n(|\theta-\theta^{\star}| \geq r_{n}  ) \mathbf{1}_{\{\mathcal{A}_n^t\}^c}\right]$. We introduce the dependency in $r$ and $n$ to upper bound $\mathbb{P}_{\theta^{\star}}(\{\mathcal{A}_n^{t}\}^c)$ with $t $ and apply Lemma \ref{lem:petite_boule}. We have:
 $$\mathbb{P}_{\theta^{\star}}(\{\mathcal{A}_n^{t}\}^{c}) \leq 2 d e^{-n \left( \frac{t^2}{4 L^2 C^U_P d} \wedge \frac{t}{2 L \sqrt{C^U_P  d}}\right)}.$$
We then obtain that:
\begin{align}
\lefteqn{
\mathbb{E}_{\theta^{\star}} \left[ \pi_n(|\theta-\theta^{\star}| \geq r_{n}  )
\right] } \nonumber \\
& \leq 4   e^{n t^2 \left(  \frac{L}{2}  + 1 \right)-\log \pi_0(B(\theta^{\star},t))} e^{-n \frac{c(r_{n})^2}{16 C^U_P}\wedge \frac{c(r_{n})}{4 \sqrt{C^U_P}}}+2 d e^{-n \left( \frac{t^2}{4 L^2 C^U_P d} \wedge \frac{t}{2 L \sqrt{C^U_P  d}}\right)}. \label{eq:intermediaire}
\end{align}
\noindent
\underline{Step 3: Small ball calibration and prior mass}
 We   now adjust the different parameters in order to obtain the best   rate for $(\widetilde{\theta}_n)_{n\geq0}$. 
  We  choose $t$ that depends on $r$ and $n$, \textit{i.e.} $t=t_{r,n}$ according to:
$$
t_{r,n} =  \frac{c(r_{n}) \wedge \sqrt{c(r_{n})}}{A},
$$
with $A$ chosen sufficiently large such that $A = \sqrt{32 (L+1) C^U_P \vee \sqrt{C^U_P}}$, so that:
$$
n t_{r,n}^2 \left(  \frac{L}{2}  + 1 \right) - n \frac{c(r_{n})^2}{16 C^U_P}\wedge \frac{c(r_{n})}{4 \sqrt{C^U_P}} \leq 
- n \frac{c(r_{n})^2}{32 C^U_P}\wedge \frac{c(r_{n})}{8 \sqrt{C^U_P}}.
$$
The previous inequality may be verified by considering the value of $c(r_{n})$ and its position in comparison to $1$ and to $2 \sqrt{C^U_P}$.
In the meantime, we get that:

$$
-\log \pi_0(B(\theta^{\star},t_{r,n})) \leq - \log \pi_0\left( B(\theta^{\star},A^{-1}[c(\varepsilon_n) \wedge \sqrt{c(\varepsilon_n)}])\right).
$$
We introduce $\varepsilon_n$ as:
$$
\varepsilon_n =  \left(L^2 C^U_P d \frac{\log n}{n}\right)^{1/2 \alpha_c},
$$
and consider $n$ large enough such that $ \varepsilon_n \leq 1$ and $b_1 \varepsilon_n^{\alpha_c} < 1$ (where $b_1$ is given in Assumption $(\mathbf{I_{W_1}(c)})$), then:
 $$
-\log \pi_0(B(\theta^{\star},t_{r,n})) \leq - \log \pi_0\left( B(\theta^{\star},A^{-1}c(\varepsilon_n)) \right).
$$
Since $\pi_0 = e^{-V_0}$ with $V_0$ a $\mathcal{C}_1^1$ function, we then deduce that: 
$$
\forall \delta>0, \quad 
\forall \theta \in B(\theta^{\star},\delta): \qquad |V_0(\theta)-V_0(\theta^{\star})| \leq \delta \|\nabla V(\theta^{\star})\| + \frac{1}{2} \delta^2,
$$
which implies:
\begin{align*}
\lefteqn{- \log \pi_0(B(\theta^{\star},t_{r,n}))} \\
 &\leq - \log \left( \int_{B(\theta^{\star},A^{-1}c(\varepsilon_n))} e^{V_0(\theta^{\star}) - A^{-1}c(\varepsilon_n) \|\nabla V(\theta^{\star})\| - A^{-2}c(\varepsilon_n)^2/2} \text{d} \lambda_d(\theta) \right) \\
& = -V_0(\theta^{\star}) + A^{-1}c(\varepsilon_n) \|\nabla V(\theta^{\star})\| + \frac{A^{-2}c(\varepsilon_n)^2}{2} + d \log (A c(\varepsilon_n)^{-1})- \log \lambda_d (B(0,1))\\
& \leq -V_0(\theta^{\star}) + A^{-1} c(a \varepsilon_2) \|\nabla V(\theta^{\star})\| + \frac{A^{-2} c(a \varepsilon_2)^2}{2} + d \log (c(\varepsilon_n)^{-1}).
\end{align*} 
Using the behaviour of $c$ near $0$ (see $(\mathbf{I_{W_1}(c)})$), a constant $C_{\theta^{\star}}$ exists such that:
$$
- \log \pi_0(B(\theta^{\star},t_{r,n})) \leq \log(C_{\theta^{\star}}) + d \alpha_c \log(\varepsilon_n^{-1}).
$$
We then obtain  with $K=32 \vee 4 A^2$ that a universal $q$ exists such that  \eqref{eq:intermediaire} may be upper bounded as:
\begin{align*}
\mathbb{E}_{\theta^{\star}} \left[ \pi_n(|\theta-\theta^{\star}| \geq r_{n}  )
\right] & \le q d e^{-\frac{n}{K} \left[ \frac{c(r_{n})^2}{L^2 C^U_P d} \wedge \frac{c(r_{n})}{L \sqrt{C^U_P d}} \right]+ d \alpha_c \log(\varepsilon_n^{-1})}.
\end{align*}
Finally, Equation \eqref{eq:ic} yields:
\begin{align}\label{eq:deviation}
\mathbb{E}_{\theta^{\star}} \left[ \pi_n(|\theta-\theta^{\star}| \geq r_{n})
\right] & \le q d e^{-\frac{n}{K} b_1^2 \frac{\{r_{n}\}^{2 \alpha_c}}{L^2 C^U_P d}} \mathbf{1}_{r_{n} \leq 1}
+q d e^{-\frac{n}{K} b_2 \frac{ \log(r_{n})+1}{L \sqrt{C^U_P d}}} \mathbf{1}_{r_{n} \geq 1}.
\end{align}


\noindent
\underline{Step 4: Convergence rate}
 We use \eqref{eq:bornequad} and \eqref{eq:deviation} and obtain that:

\begin{eqnarray*}
\mathbb{E}_{\theta^{\star}}[\|\widetilde{\theta}_n-\theta^{\star}\|^p] &\lesssim_{uc} & \varepsilon_n^p   + d \int_{0}^{+ \infty} r_{n}^{p-1} \left(
 e^{-\frac{n}{K} b_1^2 \frac{\{r_{n}\}^{2 \alpha_c}}{L^2 C^U_P d}} \mathbf{1}_{r_{n} \leq 1} +  e^{-\frac{n}{K}  b_2 \frac{ \log(r_{n})+1}{L \sqrt{C^U_P d}}} \mathbf{1}_{r_{n} \geq 1}\right)\text{d}r\\
& \lesssim_{uc} &  \varepsilon_n^p + d \left[ \int_{\varepsilon_n}^{1} r^{p-1} 
  e^{- \frac{n}{K}  b_1^2 \frac{r^{2\alpha_c}}{L^2 C^U_P d}} \text{d}r+
\int_{1}^{+\infty} r^{p-1} e^{- \frac{n}{K}  b_2 \frac{\log(r)+1}{L \sqrt{C^U_P d}}} \text{d}r\right].
\end{eqnarray*}
Using the value of $\varepsilon_n$ we introduced in Step 2,
we then observe that:
$$
\int_{\varepsilon_n}^{+ \infty} r^{p-1}  e^{- \frac{n}{K}   b_1^2 \frac{r^{2\alpha_c}}{L^2 C^U_P d}} \text{d}r \leq  \left( \frac{K L^2 C^U_P d}{ b_1^2 n}\right)^{p/2\alpha_c}  (2 \alpha_c)^{-1}\int_{b_1^2 K \log n}^{+ \infty} v^{p/2\alpha_c-1}e^{-v} \text{d}v 
=  \mathcal{O}_{uc}(\varepsilon_n^p).
$$
The second integral may be made exponentially small (in terms of $n$). We then observe that the leading contribution of the $L^p$ loss is then brought by $\varepsilon_n^p$.
\end{proof}


\subsection{ Minimax lower bound (proof of Theorem \ref{theo:lower_bound})}\label{sec:lower_bound}
 
Below, we establish a lower bound of estimation that matches with the Bayesian consistency rate we derive in Theorem \ref{theo:consistency} in terms of $n$ and $d$.


\begin{proof}[Proof of Theorem \ref{theo:lower_bound}]
 For this purpose, we introduce $\varphi_{\alpha_c}$ defined by:
$$
\varphi_{\alpha_c}(x) = sgn(x) |x|^{\alpha_c} \mathbf{1}_{|x| \leq 1} + x   \mathbf{1}_{|x| > 1},
$$
and the family of multivariate Gaussian distributions $\mathbb{P}_{\theta} = \mathcal{N}(\delta \mu_{\alpha_c}(\theta),I_d)$ with  $\delta>0$ defined later on and 
$$
\forall i \in \{1,\ldots,d\} \qquad 
\mu_{\alpha_c}(\theta)_i = \varphi_{\alpha_c}(\theta_i).
$$
Considering all positions of $x$ and $y$, we observe that a constant $c$ exists such that:
$$
\forall (x,y) \in \mathbb{R}^2 \qquad 
|\varphi_{\alpha_c}(x)-\varphi_{\alpha_c}(y)| \ge c |x-y|^{\alpha_c}
$$

As a translation model, it is immediate to verify that:
\begin{align*}
W_1(\mathbb{P}_{\theta_1},\mathbb{P}_{\theta_2})^2& = \delta^2 |\mu_{\alpha_c}(\theta_1)- \mu_{\alpha_c}(\theta_2)|_2^2 \\
& =  \delta^2  \sum_{i=1}^d |\varphi_{\alpha_c}(\theta_1^i)-\varphi_{\alpha_c}(\theta_2^i)|^2\\
& \ge \delta^2  c^2 d \left(\frac{1}{d}\sum_{i=1}^d | \theta_1^i - \theta_2^i |^{2 \alpha_c}\right) \\
& \ge d \delta^2   c^2 \left(\frac{1}{d}\|\theta_1-\theta_2\|^{2}\right)^{ \alpha_c} = c^2 \delta^2   d^{1-\alpha_c} \|\theta_1-\theta_2\|_2^{2 \alpha_c}
\end{align*}
where we applied the Jensen inequality in the previous line with the convex function $r\longmapsto r^{\alpha_c}$ with $\alpha_c \ge 1$.
Therefore, we observe that when $\delta=d^{-(1-\alpha_c)/2}$, the family $\mathbb{P}_{\theta}$ satisfies $(\mathbf{I_{W_1}(c)})$.
In the meantime, straightforward computations show that $(\mathbf{PI_U})$ and $(\mathbf{A}_L)$ also hold for this statistical model so that this statistical model belongs to the $\mathcal{F}_{\alpha_c}^L$ class used in the statement of the result.\\




In this statistical model, we then derive a lower bound of estimation with the $L^2$ risk applying the Fano Lemma associated with the Varshamov-Gilbert Lemma. We introduce the Hamming distance $\rho(\omega,\omega')$ defined by: 
$$
\forall (\omega,\omega') \in \{0,1\}^d \times \{0,1\}^d \qquad 
\rho(\omega,\omega') = \sum_{j=1}^d \mathbf{1}_{\omega^j \neq \omega'^j}.
$$
The Varshamov-Gilbert yields the existence of $M=\lfloor e^{d/32}\rfloor$ points in $\{0,1\}^d$ denoted by $(\omega_1,\ldots,\omega_M)$ such that 
$$
\forall j \neq k \qquad \rho(\omega_j,\omega_k) \ge \frac{d}{4}.
$$
With this net over $\{0,1\}^d$, we introduce the net $\theta_1,\ldots,\theta_M$ defined by
$$
\theta_i = \beta \omega_i,
$$
for some $\beta>0$ chosen later on.
 We then verify that:
$$
\forall j \neq k \qquad 
\|\theta_j-\theta_k\|_2 \ge \beta  \frac{\sqrt{d}}{2}.
$$
In the meantime,  the Kullback divergence for Gaussian distributions leads to:
$$
KL(\mathbb{P}_{\theta_i},\mathbb{P}_{\theta_j}) = \frac{n}{2} \delta^2 |\mu_{\alpha_c}(\theta_i) - \mu_{\alpha_c}(\theta_j)|_2^2 \leq \frac{n}{2} d^{\alpha_c} \beta^{2 \alpha_c}
$$
where we used that the maximal value of the Hamming distance is $d$ and $d \delta^2 = d^{\alpha_c}$. We then apply the Fano Lemma and observe that:
$$
\inf_{\hat{\theta}_n} \sup_{\theta} \mathbb{P}_{\theta}\left( |\hat{\theta}_n-\theta|_2 \ge \frac{\beta \sqrt{d}}{8} \right) \ge c >0
$$
as soon as:
$$
\frac{\frac{n}{2} d^{\alpha_c} \beta^{2 \alpha_c} + \log(2)}{d/32} < 1.
$$
We then choose $\beta$ as large as possible, \textit{i.e.} we choose $\beta$ such that:
$$
\beta = b \left(\frac{d^{1-\alpha_c}}{n}\right)^{\frac{1}{2 \alpha_c}} = b \left(\frac{d}{n}\right)^{\frac{1}{2 \alpha_c}} d^{-1/2}.
$$
This entails a minimax lower bound for the $L^2$ rate of the order:
$$
r_{n,d}(\alpha_c) \gtrsim \sqrt{d} \beta \simeq \left(\frac{d}{n}\right)^{\frac{1}{2\alpha_c}}.
$$
 \end{proof}




 




















 
\section{Discretization of the Langevin procedure - Weakly convex case }\label{sec:disc_c}


The weakly convex (\textit{i.e.} not uniformly strongly convex) case is tackled {with a completely different approach with the help of Assumption $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$. Actually, in the weakly convex case, a series of properties disappear. For instance, one can not  easily control the pathwise distance between the process and its discretization. The problem is then  significantly harder and we choose here to make use of the inversion of the Poisson equation, which leads to a relatively tractable formulation of  the error between the discretized Cesaro average and the invariant distribution (applied to the identity function). } 
In particular, this ``Poisson equation approach'' is in the continuity of  \cite{lamberton_pages,pages_menozzi}) and has a long-standing history in the study of central limit theorem for Markov chains. 
We refer to \cite{Meyer,Neveu,Revuz,Meyn_Poisson} for seminal contributions on additive functionals of Markov chains.
We first stay at an informal level in this paragraph for the sake of readability.
We sketch the general idea behind the use of this equation with an   Euler scheme.

Again, we first state some general results with a diffusion process $(X_t)_{t \geq 0}$ solution of:
\begin{equation}\label{eq:EDS} 
dX_t=- \nabla W(X_t) dt+ \sqrt{2}  dB_t.\end{equation}




\subsection{How to use the Poisson equation $f-\pi(f)= \mathcal{L}  g$?}

This approach is based on the inversion of the operator ${\mathcal L}$ of the diffusion. For a given function $f$, we recall that the solution of the Poisson equation is the function $g$ such that $\pi(g)=0$ and that satisfies:
$$ f-\pi(f)={\mathcal L} g,$$
where $\pi$ denotes the invariant distribution of the diffusion (see below for background on existence and uniqueness of the solution). 
We consider $g$ the solution of the Poisson equation.

$\bullet$
For such a solution, a first important ingredient is based on the following remark: if $(X_t)_{t\ge0}$ is a Markov process with generator ${\mathcal L}$ and $g$ belongs to the (extended) domain, then the Ito formula yields:
$$
g(X_t)=  g(X_0) + \int_{0}^t {\mathcal L} g(X_s) \text{d}s + \mathcal{M}_t^g,
$$
so that
\begin{equation}\label{eq:extmart}
\int_0^t f(X_s)-\pi(f) \text{d}s= \int_0^t {\mathcal L} g(X_s) \text{d}s- (g(X_t)- g(X_0))
\end{equation}
is a local martingale (and certainly a true martingale under appropriate conditions). Thus, the control of the distance between 
$(\frac{1}{t}\int_0^t f(\xi_s))_{t\ge0}$ and $\pi(f)$ can be tackled from a martingale point of view. 

$\bullet$
The second main interest of this approach is the possibility to specify that our estimator involves $f=\mathbf{I}_d$, which is an important ingredient of the approximation of $\pi(f)$. Such a precision is  untractable when we handle distances between probability distributions.\\







  
 

{We first state that the Poisson equation is well-posed in our setting and recall a classical formulation of this solution. {The proof is postponed to the Appendix B.} Note that this result is only stated under the assumptions of our main theorems but may be certainly extended to a more general setting (see \cite[Corollary 3.2]{CCG} for a more general result).}
\begin{prop}[Poisson equation]\label{theo:poisson} 
{Assume $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ and suppose that $W$ is ${\mathcal C}^3$ with bounded third derivatives. 
Then, Equation \eqref{eq:EDS}  admits a unique invariant distribution and for any ${\mathcal C}^2$-function $f$ with bounded derivatives,  the problem  $\mathcal{L} g = f-\pi(f)$ is well-posed on the set of ${\mathcal C}^2$-functions such that $\pi(g)=0$ and the unique solution is given by:
$$
g(x) = \int_{0}^{+ \infty} [\pi(f)-P_s f(x)] {\rm d}s.
$$}
\end{prop}






Note that in what follows, we will solve this equation $d$ times for a multivariate function $f=(f^1,\ldots,f^{{d'}})$ ({and will mainly consider the case  $f=\mathbf{I}_d$ for applications to Bayesian estimation}).
\subsection{Poisson equation and discretization}\label{sec:poissonbisbis}

In the  discretized case, the aim is then to mimick the martingale property of Equation \eqref{eq:extmart} but some additional error terms appear with the discretization approximation. Such ideas have been strongly studied in \cite{lamberton_pages,pages_menozzi} but since the solution to the Poisson equation is not explicit (in general), 
the previous works have usually made \textit{ad hoc} assumptions on the function $g$ and its derivatives. For our purpose, we identify the key properties satisfied by the solution when $f=\mathbf{I}_d$ in terms of the dimensional dependence.







 
 
 



















We observe that $(\bar{X}_{t_k})_{k \ge 1}$, 
computed through the recursion
$$
\bar{X}_{t_k} = - \gamma \nabla W(\bar{X}_{t_{k-1}}) + \sqrt{2 \gamma}  \zeta_k,
$$
where $(\zeta_k)_{k \ge 0}$ is an i.i.d. sequence of standard $d$-dimensional Gaussian random variables, 
is a sequence of discrete time observations of the continuous time process $(\bar{X}_t)_{t \ge 0}$ defined by:
\begin{equation}\label{barxt}
\forall t \in [t_k,t_{k+1}] \qquad 
d \bar{X}_{t} = -   \nabla W(\bar{X}_{t_k}) dt + \sqrt{2}  dB_t,
\end{equation}
with $\sqrt{\gamma} \zeta_k = B_{t_k}-B_{t_{k-1}}$.

Considering a \textit{multivariate} function $g=(g^1,\ldots, g^{{d'}}):\mathbb{R}^d\rightarrow\mathbb{R}^{{d'}}$, 
we denote by $Dg=[\nabla g^1{;} \ldots{;} \nabla g^{{d'}}]$ {its Jacobian matrix} {which maps from $\mathbb{R}^d$ to the space of $d'\times d$-matrices.} Similarly, $\Delta g$ refers to the vector built with $(\Delta g^1, \ldots, \Delta g^{{d'}})$.
For  $s >0$, we define $\underline{s}$ the largest grid point in $(t_k)_{k \ge 0}$ below $s$:
\begin{equation}\label{def:s}
\underline{s} := \sup \{t_k \, : t_k \le s \}.
\end{equation}
We then observe that:
$$g(\bar{X}_t)=g(x)+\int_0^t \bar{\mathcal L} g(\bar{X}_s,\bar{X}_{\underline{s}}) \text{d}s+ {\mathcal M}_t^{(g)},$$
where  $\underline{s}$ is  defined in \eqref{def:s},  $\bar{\mathcal{L}}$ is given by:
\begin{equation}\label{def:LL_b}
 \bar{\mathcal{L}} g(x,\underline{x})=-  D g(x) \nabla W(\underline{x}) + \Delta g(x),
 \end{equation}
and ${\mathcal M}^{(g)}$ is {the  $\mathbb{R}^d$-valued local martingale} defined by:
\begin{equation}\label{eq:martingale_g}
 {\mathcal M}_t^{(g)}=  \sqrt{2} \int_0^t   D g(\bar{X}_s) \text{d}B_s.
 \end{equation} 
Similarly, the definition of $\mathcal{L}$ shall be extended to multivariate functions by
\begin{equation}\label{def:LL}
\mathcal{L} g(x)={(\mathcal{L} g^1(x),\ldots\mathcal{L} g^{{d'}}(x))} = - D g(x) \nabla W(x) + \Delta g(x).
\end{equation}






\noindent We first state some useful technical results for the proof of Theorem \ref{cor:thmPoisson} {whose proofs 
 ar postponed to  Appendix B}




\begin{lem}\label{lem:gradWmaindoc} Assume $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$. Then, $\forall x\in\mathbb{R}^d$,
$$ \frac{\mathfrak{c}_1}{1-r}\left( W^{1-r}(x)-W^{1-r}(x^\star)\right)\le   |\nabla W(x)|^2\le \frac{{\mathfrak{c}_2}}{1-r}\left( W^{1-q}(x)-W^{1-q}(x^\star)\right).$$
Furthermore, $\forall x\in\mathbb{R}^d$,
\begin{equation}\label{eq:asympdob}
W^{1+r}(x)-W^{1+r}(x^\star)\ge (1+r)\mathfrak{c}_1|x-x^\star|^2\;\textnormal{and}\;W^{1+q}(x)-W^{1+q}(x^\star)\le \frac{{\mathfrak{c}_2}(1+q)}{1-q}|x-x^\star|^2.
\end{equation}
\end{lem}

 
 
 
  
{In this second technical result, we obtain some crucial bounds related to the solution of the Poisson equation under Assumption $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$.}
\begin{prop}\label{prop:fundamentalbounds2} Assume $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ with $\mathfrak{KL}>0$, $\mathfrak{c}_1>0$ and $r\in[0,1]$. {Let $f:\mathbb{R}^d\rightarrow\mathbb{R}^{d'}$ be a Lispchitz ${\mathcal C}^2$-function with $[f]_1\le 1$ and $[Df]_{1,\star}\le 1$}.    Then, $g{:\mathbb{R}^d\rightarrow\mathbb{R}^{d'}}$ is  a ${\mathcal C}^2$-function and for every $\mathfrak{e}\in(0,1)$, a constant  $c_\mathfrak{e}$ exists (which only depends on $\mathfrak{e}$ {and not on the other parameters}), such that for any $x$:
\begin{enumerate}

\item[$i-a)$]

{$\nsp{Dg(x)}{\le} c_\mathfrak{e} \mathfrak{c}_1^{-1-\mathfrak{e}} \left(W^{r(1+\mathfrak{e})}(x)+\Upsilon^{r(1+\mathfrak{e})}\right).$}

\item[$i-b)$]
{
If $W(x_0)\lesssim_{uc} \Upsilon$,
$\sup_{t\ge0}\mathbb{E}_{x_0}[\nsp{Dg(\bar{X}_t)}^2]{\le} c_\mathfrak{e}   \mathfrak{c}_1^{-2(1+\mathfrak{e})} \Upsilon^{2r(1+\mathfrak{e})}.$}
{
\item[$ii-a)$] If $W(x^\star)\lesssim_{uc}\Upsilon$,
$| g(x)-g(x^\star)|^2{\le}
c_\mathfrak{e} \mathfrak{c}_1^{-3-2\mathfrak{e}} \left({W}^{(1+3r)(1+\mathfrak{e})}(x)+ \Upsilon^{(1+3r)(1+\mathfrak{e})}\right).
 $
\item[$ii-b)$] If $W(x_0)\lesssim_{uc} \Upsilon$, then
$\sup_{t\ge0} \mathbb{E}_{x_0}[| g(\bar{X}_t)-g(x_0)|^2]{\le} c_\mathfrak{e} \mathfrak{c}_1^{-3-2\mathfrak{e}}  \Upsilon^{(1+3r)(1+\mathfrak{e})}.$}
{
\item[$iii-a)$] Assume that $\nabla^2 W$ is $\tilde{L}$-Lipschitz for the norm $\nsp{.}$. Then, for any $x, y\in\mathbb{R}^d$ with $x\neq y$,
$$\frac{\nsp{Dg(y)-Dg(x)}}{|y-x|}{\le}  c_\mathfrak{e} \mathfrak{c}_1^{-2(1+\mathfrak{e})}\tilde{L}\left(W^{2r(1+\mathfrak{e})}(x)+W^{2r(1+\mathfrak{e})}(y)+\Upsilon^{2r(1+\mathfrak{e})}\right).$$
\item[$iii-b)$] Set $\tilde{X}_{{t}}=\bar{X}_{\underline{t}}-(t-\underline{t}) \nabla W(\bar{X}_{\underline{t}})$. If $W(x_0)\lesssim_{uc} \Upsilon$,
$$\mathbb{E}_{x_0}\left[|(Dg(\bar{X}_{{t}})-Dg(\tilde{X}_{{t}}))(\nabla W(\bar{X}_{\underline{t}}+\Delta_{\underline{t}t})-\nabla W(\bar{X}_{\underline{t}}))|^2\right]{\le} \mathfrak{c}_\mathfrak{e} (L \tilde{L} \mathfrak{c}_1^{-2(1+\mathfrak{e})}(t-\underline{t}))^2 d^2 \Upsilon^{4r(1+\mathfrak{e})}.$$
}
\end{enumerate}
\end{prop}

\begin{proof}[Proof of Theorem  \ref{cor:thmPoisson}]

The plan of the proof is the same for $i)$ and $ii)$ and is decomposed into three steps. Steps 1 and 2  are common whereas the last one is treated separately.

\noindent \textit{\underline{Step 1: Decomposition of $\pi_N(f)-\pi(f)$.}}
We observe that:
\begin{align*}
\pi_N(f)-\pi(f) & := \frac{1}{t_N} \sum_{k=1}^N \gamma_k f(\bar{X}_{t_{k-1}}) -\pi(f)
 = \frac{1}{t_N} \sum_{k=1}^N  \int_{t_{k-1}}^{t_k} f(\bar{X}_{\underline{s}}) \text{d}s -\pi(f)\\

 &= \frac{1}{t_N} \int_{0}^{t_N} [f(\bar{X}_{\underline{s}}) - \pi(f)] \text{d}s\nonumber\\
& = \frac{1}{t_N} \int_{0}^{t_N} [f(\bar{X}_{s}) - \pi(f)] \text{d}s  + \frac{1}{t_N} \int_{0}^{t_N} [f(\bar{X}_{\underline{s}}) - f(\bar{X}_{s})] \text{d}s
\end{align*}
Now, we may use the Poisson equation $f-\pi(f)={\mathcal L} g$ and deduce that:
\begin{align*}
&\pi_N(f)-\pi(f)= \frac{1}{t_N} \int_{0}^{t_N} {\mathcal L}  g(\bar{X}_{s}) \text{d}s+ \frac{1}{t_N} \int_{0}^{t_N} [{f}(\bar{X}_{\underline{s}})- {f}(\bar{X}_{s})] \text{d}s\\
& = 
\frac{1}{t_N} \int_{0}^{t_N} \bar{{\mathcal L}}  g(\bar{X}_s,\bar{X}_{\underline{s}}) \text{d}s+ \frac{1}{t_N} \int_{0}^{t_N} [{\mathcal L} g(\bar{X}_{s})-\bar{{\mathcal L}}  g(\bar{X}_s,\bar{X}_{\underline{s}})] \text{d}s  + \frac{1}{t_N} \int_{0}^{t_N} [{f}(\bar{X}_{\underline{s}})- {f}(\bar{X}_{s})] \text{d}s.
\end{align*}
{where $\bar{{\mathcal L}}$ has been defined in \eqref{def:LL_b}.}
To handle the first term of the right-hand side, we use the  Ito formula to obtain:
$$
g(\bar{X}_{t_N}) = g(x_{0})+
\int_{0}^{t_N} \bar{{\mathcal L}}  g(\bar{X}_s,\bar{X}_{\underline{s}}) \text{d}s+ \mathcal{M}_{t_N}^{(g)}\quad\textnormal{with}\quad \mathcal{M}_{t_N}^{(g)}=2\int_0^{t_N} Dg(\bar{X}_s) \text{d}B_s.
$$ 
By \eqref{def:LL_b}, we remark that
$$
{\mathcal L} g(x) - \bar{{\mathcal L}}g(x,\underline{x}) =  D g(x) [\nabla W(\underline{x})-\nabla W(x)].
$$
We then obtain that:
\begin{align}
\pi_N(f)-\pi(f) = 
& = \overbrace{\frac{g(\bar{X}_{t_N}) - g(x_{0})}{t_N}}^{:=A_{t_N}^{(0)}} - \overbrace{\frac{\mathcal{M}_{t_N}^{(g)}}{t_N}}^{:=A_{t_N}^{(1)}}  + \overbrace{\frac{1}{t_N} \int_{0}^{t_N} Dg(\bar{X}_{{s}})[\nabla W(\bar{X}_{\underline{s}})-\nabla W(\bar{X}_{s})] \text{d}s}^{:=A_{t_N}^{(2)}} \nonumber\\
 &+\underbrace{ \frac{1}{t_N} \int_{0}^{t_N} [ f(\bar{X}_{\underline{s}}) - f(\bar{X}_{s})] \text{d}s}_{:=A_{t_N}^{(3)}}.

\end{align}

\noindent The rest of the proof consists in studying the mean-squared error related to each term of the above righ-hand side and to deduce the result the upper-bound for  $\mathbb{E}|\pi_N(f)-\pi(f)|^2$.\\

\noindent \underline{\textit{Step 2: Mean squared error related to $A_{t_N}^{(0)}$, $A_{t_N}^{(1)}$ and $A_{t_N}^{(3)}$}:}\\


\noindent $\bullet$ By Proposition \ref{prop:fundamentalbounds2} $ii)-b)$, {there exists a constant $c_\mathfrak{e}$ depending only on $\mathfrak{e}$ (and which may change from line to line) such that},
{
$$ \mathbb{E}_{x_0}\left|A_{t_N}^{(0)}\right|^2=\mathbb{E}_{x_0}\left| \frac{g(\bar{X}_{t_N}) - g(\bar{X}_{0})}{t_N} \right|^2
\le c_\mathfrak{e} \mathfrak{c}_1^{-3-2\mathfrak{e}}  \frac{\Upsilon^{(1+3r)(1+\mathfrak{e})}}{t_N^2}.$$
}

\noindent $\bullet$ Let us consider the martingale term $A_{t_N}^{(1)}$:
$$ \mathbb{E}_{{x_0}}[|{\mathcal M}_{t_N}^{(g)}|^2]= 2 \int_0^{t_N}   \mathbb{E}_{x_0}\|D g(\bar{X}_s)\|_F^2 \text{d}s,$$
where $\|.\|_F$ refers to the Frobenius norm. Then, since for a {$d'\times d$-matrix $A$, $\|A\|_F^2\le {\rm Tr}(A A^T)\le d' \nsp{A}^2$},
Proposition \ref{prop:fundamentalbounds2} implies:
{
$$\mathbb{E}_{{x_0}}\left|A_{t_N}^{(1)}\right|^2 \le c_\mathfrak{e}   \mathfrak{c}_1^{-2(1+\mathfrak{e})} \frac{d' \Upsilon^{2r(1+\mathfrak{e})}}{t_N}  .$$}
\noindent $\bullet$ Let us now consider $A_{t_N}^{(3)}$.  On $[t_{k-1},t_k)$:
\begin{equation}
 \bar{X}_s-\bar{X}_{\underline{s}} =-(s-\underline{s}) \nabla W(\bar{X}_{\underline{s}}) + \Delta_{\underline{s}s}. \label{eq:dif_bxs_bx}
 \end{equation}
 with $\Delta_{\underline{s} s}=\sqrt{2}(B_s-B_{t_{k-1}})$.
 Thus, by Taylor formula, there exists  $\xi(s)\in [\bar{X}_{\underline{s}},\bar{X}_{\underline{s}}+ \Delta_{\underline{s}s}]$ such that
 $$f(\bar{X}_s)-f(\bar{X}_{\underline{s}})= {f(\bar{X}_s)-f(\bar{X}_s- (s-\underline{s}) \nabla W(\bar{X}_{\underline{s}})}+ Df(\xi_2(s)) \Delta_{\underline{s}s}.$$
Thus, 
$$\int_{t_{k-1}}^{t_k}
  f(\bar{X}_s)-f(\bar{X}_{\underline{s}})\text{d}s=\underbrace{\int_{t_{k-1}}^{t_k} Df(\bar{X}_{\underline{s}}) \Delta_{\underline{s}s}\text{d}s}_{\Delta N_k}+R(s)$$
where 
$$|R(s)|\le [f]_1 (s-\underline{s})  |\nabla W(\bar{X}_{\underline{s}}) |+ [Df]_{1,\star} |\Delta_{\underline{s}s}|^2.$$

 
 
 
 
  On one hand, since $(\Delta N_k)_{k\ge1}$ is a sequence of martingale increments (and $[f]_1\le 1$),  
\begin{align*}
\mathbb{E}_{{x_0}}\left[\left(\frac{1}{t_N}\sum_{k=1}^N\Delta N_k\right)^2\right]&=\frac{1}{t_N^2}\sum_{k=1}^N\mathbb{E}_{{x_0}}|\Delta N_k|^2
\le \frac{[f]_1^2}{t_N^2} \sum_{k=1}^N \mathbb{E} \left|
\int_{t_{k-1}}^{t_k} (B_s-B_{t_{k-1}}) \text{d}s\right|^2\\
& \le  \frac{ N}{t_N^2} 
\mathbb{E} \left|
\int_{0}^{\gamma} B_s \text{d}s\right|^2 \le \frac{1}{N\gamma^2} \mathbb{E} \left|
\int_{0}^{\gamma} (\gamma-s) \text{d}B_s \right|^2 \le  \frac{ d \gamma}{3N}.
\end{align*}
On the other hand, the Jensen inequality (combined with the fact $[f]_1\le 1$ and $[Df]_{1,\star}\le 1$) yields:





\begin{align*}
\mathbb{E}_{{x_0}}\left[\left(\frac{1}{t_N}\int_0^{t_N} R(s) ds\right)^2\right]
&\le \frac{2}{t_N}\int_0^{t_N} \left((s-\underline{s})^2 \mathbb{E}\left|\nabla W(\bar{X}_{\underline{s}}) \right|^2+2\mathbb{E} |\Delta_{\underline{s}s}|^4\right) ds\\
&\le \frac{2}{3}\gamma^2 \sup_{s\ge1} \mathbb{E}\left|\nabla W(\bar{X}_{\underline{s}}) \right|^2+ \frac{10 d^2}{t_N}\int_0^{t_N}(s-\underline{s})^2 ds\\
&\lesssim_{uc} \frac{{\mathfrak{c}_2} \gamma^2}{1-q} (W^{1-q}(x_0)+\Upsilon^{1-q})+ d^2\gamma^2,
\end{align*}
where in the last inequality, we used Lemma \ref{lem:gradWmaindoc} and Proposition \ref{lem:expbounds22} $ii)$.  
We deduce from what precedes that:
{
\begin{align*}
\mathbb{E}_{{x_0}}\left|A_{t_N}^{(3)}\right|^2\lesssim_{uc} \frac{d\gamma^2}{t_N}+\frac{{\mathfrak{c}_2} \gamma^2}{1-q}(\Upsilon^{1-q}+W(x_0)^{1-q})+d^2\gamma^2.
\end{align*}
}





\noindent \underline{\textit{Step 3: Mean squared error related to $A_{t_N}^{(2)}$}} The study of this term is isolated not only because its study is more involved, but also because this term differentiates the bound of $i)$ and $ii)$.

\noindent We separate the drift and the diffusion components and recall that $\Delta_{\underline{s}s}=\sqrt{2}(B_s-B_{\underline{s}})$. We have:
 
 \begin{align*}
A_{t_N}^{(2)} =& -\overbrace{\frac{1}{t_N} \int_{0}^{t_N} Dg(\bar{X}_{{s}})[\nabla W(\bar{X}_{s})-\nabla W(\bar{X}_{\underline{s}}+\Delta_{\underline{s}s})] {\rm d}s}^{:=A_{t_N}^{(2,1)}}\\
&- \underbrace{\frac{1}{t_N} \int_{0}^{t_N} Dg(\bar{X}_{{s}})[\nabla W(\bar{X}_{\underline{s}}+\Delta_{\underline{s}s})-\nabla W(\bar{X}_{\underline{s}})]{\rm d}s}_{:=A_{t_N}^{(2,2)}}.
\end{align*}
{Since $\nabla W$ is $L$-Lipschitz, Equation \eqref{eq:dif_bxs_bx} yields 
$|\nabla W(\bar{X}_{s})-\nabla W(\bar{X}_{\underline{s}}+\Delta_{\underline{s}s})|\le  L|s-\underline{s}|. |\nabla W(\bar{X}_{\underline{s}})|$}. Then, Jensen and Cauchy-Schwarz inequalities imply that:
$$\mathbb{E}_{{x_0}}[|A_{t_N}^{(2,1)}|^2]\le \frac{L^2}{t_N} \int_{0}^{t_N}(s-\underline{s})^2 \mathbb{E}_{{x_0}}[\nsp{Dg(\bar{X}_{{s}})}^2]\mathbb{E}_{{x_0}}[|\nabla W (\bar{X}_{\underline{s}})|^2] {\rm d}s.$$
Using $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$, Proposition \ref{lem:expbounds22} $ii)$, Proposition \ref{prop:fundamentalbounds2} $i-b)$, we have:
{
$$\sup_{s\ge0}\mathbb{E}_{x_0}[\nsp{Dg(\bar{X}_{{s}})}^2]\mathbb{E}_{x_0}[|\nabla W (\bar{X}_{\underline{s}})|^2] \lesssim_{uc} c_\mathfrak{e}   \mathfrak{c}_1^{-2(1+\mathfrak{e})} \Upsilon^{2r(1+\mathfrak{e})} {\mathfrak{c}_2} (\Upsilon^{1-q} + W(x_0)^{1-q})
 ,$$}
so that:
{
$$\mathbb{E}_{{x_0}}[|A_{t_N}^{(2,1)}|^2]\lesssim_{uc}  L^2  \mathfrak{c}_1^{-2(1+\mathfrak{e})}{\mathfrak{c}_2}   (\Upsilon^{(1-q+2r)(1+\mathfrak{e})}+\Upsilon^{2r(1+\mathfrak{e})} W(x_0)^{1-q}) \gamma^2.$$
}
We finally separate the study of $ A_{t_N}^{(2,2)}$ into two cases, respectively for $i)$ and $ii)$.\\

\noindent \underline{\textit{Step 4a: End of Proof of Theorem \ref{cor:thmPoisson} $(i.a)$}:}
The Cauchy-Schwarz inequality yields
\begin{equation}\label{eq:firstview}
\mathbb{E}_{{x_0}}[|A_{t_N}^{(2,2)}|^2]\le \frac{L^2}{t_N} \int_{0}^{t_N} \mathbb{E}_{{x_0}}[\nsp{Dg(\bar{X}_{{s}})}^2]\mathbb{E}_{{x_0}}[|\Delta_{\underline{s}s}|^2] {\rm{d}}s 
\le \frac{2L^2}{t_N} \int_{0}^{t_N} \mathbb{E}_{{x_0}}[\nsp{Dg(\bar{X}_{{s}})}^2] d (s-\underline{s}) {\rm{d}}s
.
\end{equation}
Again Proposition \ref{prop:fundamentalbounds2} $i-a)$ implies that:
$$\mathbb{E}_{{x_0}}[|A_{t_N}^{(2,2)}|^2]\lesssim_{uc}  c_\mathfrak{e}\frac{L^2}{t_N} \int_0^{t_N}   \mathfrak{c}_1^{-2(1+\mathfrak{e})} \Upsilon^{2r(1+\mathfrak{e})} d (s-\underline{s}) {{\rm{d}}s}\lesssim_{uc}  c_\mathfrak{e}   \mathfrak{c}_1^{-2(1+\mathfrak{e})} L^2  {\Upsilon^{2r(1+\mathfrak{e})} d} {\gamma}.$$
{Collecting the bounds obtained for $A_{t_N}^{(0)}$, $A_{t_N}^{(1)}$, $A_{t_N}^{(2,1)}$, $A_{t_N}^{(2,2)}$ and $A_{t_N}^{(3)}$,
we get:
\begin{align}
 &\mathbb{E}\Big|\frac{1}{t_N} \sum_{k=1}^N \gamma_k {f}(\bar{X}_{t_{k-1}}) -\pi(f)\Big|^2\lesssim_{uc} \max\left( \mathfrak{c}_1^{-3-2\mathfrak{e}}  \frac{\Upsilon^{(1+3r)(1+\mathfrak{e})}}{t_N^2},\mathfrak{c}_1^{-2(1+\mathfrak{e})} \frac{d' \Upsilon^{2r(1+\mathfrak{e})}}{t_N}, \frac{d \gamma^2}{t_N}\right) \label{eq:first3452}\\
 &+
\max\left( {\mathfrak{c}_2} \gamma^2 (\Upsilon^{1-q}+W^{1-q}(x_0)), L^2  \mathfrak{c}_1^{-2(1+\mathfrak{e})}{\mathfrak{c}_2}   {\Upsilon^{2r(1+\mathfrak{e})}}(\Upsilon^{1-q}+W(x_0)^{1-q})) \gamma^2,
 \mathfrak{c}_1^{-2(1+\mathfrak{e})} L^2  {\Upsilon^{2r(1+\mathfrak{e})} d} {\gamma}\right).\label{eq:first3453}
\end{align}
}

In order to deduce Theorem \ref{cor:thmPoisson} $i.a)$, we need to calibrate $\gamma$ and $N$ in order that whole these terms be dominated by 
$\varepsilon^2$ up to a constant depending only on $r$, $\mathfrak{e}$ and $q$. 
{The largest dependency in terms of $\gamma$ is induced by the last term in \eqref{eq:first3453} and we choose:
\begin{equation} 
\label{eq:gamma_principale}
\gamma \leq \frac{\mathfrak{c}_1^{2(1+\mathfrak{e})}}{d L^2 \Upsilon^{2r(1+\mathfrak{e})}} \varepsilon^2.
\end{equation}
The other terms that involve $\gamma$ are upper bounded as follows:
$$
\frac{{\mathfrak{c}_2} \gamma^2}{1-q}(\Upsilon^{1-q}+W(x_0)^{1-q}) \leq \varepsilon^2 
\frac{\mathfrak{c}_1^{2(1+\mathfrak{e})}}{d L^2 \Upsilon^{2r(1+\mathfrak{e})}} \frac{ \gamma {\mathfrak{c}_2} (\Upsilon^{1-q}+W(x_0)^{1-q})}{1-q},
$$
so that $\gamma$ must satisfy:
$$
\gamma \leq \frac{\Upsilon^{2r(1+\mathfrak{e})} d L^2}{{\mathfrak{c}_2} \mathfrak{c}_1^{2(1+\mathfrak{e})}}(\Upsilon^{q-1} \wedge W(x_0)^{q-1}).
$$
Using Lemma \ref{lem:gradWmaindoc}, we have
$$
W(x_0)^{q-1} \geq \frac{1}{ (1+q)^{\frac{1-q}{1+q}}`\mathfrak{c}_1^{\frac{1-q}{1+q}} |x_0-x^\star|^{2 \frac{1-q}{1+q}}}.
$$
\noindent
In the same way, the middle term in \eqref{eq:first3453} induces that:
$$
\gamma \leq \frac{d}{{\mathfrak{c}_2} \Upsilon^{1-q-2r \mathfrak{e}}} \wedge \frac{d}{{\mathfrak{c}_2} 
(1+q)^{\frac{1-q}{1+q}}`\mathfrak{c}_1^{\frac{1-q}{1+q}} \Upsilon^{-2r \mathfrak{e}}|x_0-x^\star|^{2 \frac{1-q}{1+q}}
}.
$$
}



Let us now consider \eqref{eq:first3452} to calibrate $N_\varepsilon$. We identify again the largest element (in terms of $t_N$) and choose $t_N$ such that:
$$
t_N \ge \varepsilon^{-2} \frac{d' \Upsilon^{2r(1+\mathfrak{e})}}{\mathfrak{c}_1^{2(1+\mathfrak{e})}},
$$
so that the   dependency on $\varepsilon$ is translated by:
$$
N_{\varepsilon} \ge \varepsilon^{-4} \frac{d' d L^2 \Upsilon^{4 r(1+\mathfrak{e})}}{\mathfrak{c}_1^{4(1+\mathfrak{e})}} \vee \varepsilon^{-2}  \frac{d'  \Upsilon^{(2 r)(1+\mathfrak{e})}(\Upsilon^{1-q} + W(x_0)^{1-q}){\mathfrak{c}_2} }{d \mathfrak{c}_1^{2(1+\mathfrak{e})}} \vee \varepsilon^{-2} \frac{\Upsilon^{1-q} {\mathfrak{c}_2}}{d L^2}.
$$
The two other terms of \eqref{eq:first3452} must also be upper bounded by $\varepsilon^2$. Using the constraint on $\gamma$ induced by \eqref{eq:gamma_principale} and $t_N = N_{\varepsilon} \gamma$, we verify that:
$$
 \frac{d \gamma^2}{t_N} \leq \varepsilon^2 \frac{\mathfrak{c}_1^{2(1+\mathfrak{e})}}{L^2 \Upsilon^{2r(1+\mathfrak{e})} N_{\varepsilon}},
$$
so that $N_{\varepsilon}$ must satisfy:
$$
N_{\varepsilon} \ge \frac{\mathfrak{c}_1^{2(1+\mathfrak{e})}}{L^2 \Upsilon^{2r(1+\mathfrak{e})} }.
$$
Finally, the last term involved in \eqref{eq:first3452} is automatically upper bounded by $\varepsilon^2$ since $t_N \ge 1$ induces the constraint
$$ t_N \ge \varepsilon^2 \frac{1}{d' \mathfrak{c}_1 \Upsilon^{(1+r)(1+\mathfrak{e})}}.$$ \\




For Theorem \ref{cor:thmPoisson} $(i.b)$, we remark that 
$\Upsilon \leq c (\log d) d^{\frac{1}{1+q-r}}$ where $c$ depends on $\mathfrak{e},r,q,\mathfrak{c}_1,{\mathfrak{c}_2}$ and $L$ but not on $\varepsilon$ and $d$. Plugging this estimate of $\Upsilon$ into \eqref{eq:first3452} and \eqref{eq:first3453} leads to 
\begin{align*}
 \mathbb{E}\Big|\frac{1}{t_N} \sum_{k=1}^N \gamma_k {f}(\bar{X}_{t_{k-1}}) -\pi(f)\Big|^2\leq c  d^{\tilde{\mathfrak{e}}} \max\left( \frac{d^{\frac{1+3r}{1+q-r}}}{t_N^2},\frac{d' d^{\frac{2r}{1+q-r}}}{t_N},d^{\frac{1-q+2r}{1+q-r}}\gamma^2,  d^{1+\frac{2r}{1+q-r}} {\gamma}\right),
\end{align*}
where $\tilde{\mathfrak{e}}$ denotes an arbitrary small positive number. The result easily follows using that the first term is smaller than the second one under the condition  $\varepsilon\le d' d^{-\frac{1-r}{2(1+q-r)}}$.\\




  

\noindent \underline{\textit{Step 4b: End of Proof of Theorem \ref{cor:thmPoisson} $(ii.a)$}:}
 The proof is given for any choice of $q$ and $r$ but the statement is valid only when $r=q$.

It is possible to exploit the centering of $\Delta_{\underline{s}s}$. We decompose into two parts and we decompose $A_{t_N}^{(2,2)}$ as follows:
\begin{equation}\label{def:atn22}
\begin{split}
A_{t_N}^{(2,2)}&=\overbrace{\frac{1}{t_N} \int_{0}^{t_N} (Dg(\bar{X}_{{s}})-Dg(\tilde{X}_{\underline{s}}))[\nabla W(\bar{X}_{\underline{s}}+\Delta_{\underline{s}s})-\nabla W(\bar{X}_{\underline{s}})] ds}^{:=\circled{1}}\\
&+\underbrace{\frac{1}{t_N} \int_{0}^{t_N} Dg(\tilde{X}_{\underline{s}})[\nabla W(\bar{X}_{\underline{s}}+\Delta_{\underline{s}s})-\nabla W(\bar{X}_{\underline{s}})] ds,}_{:=\circled{2}}
\end{split}
\end{equation}
where $\tilde{X}_{\underline{s}}=\bar{X}_{\underline{s}}-(s-\underline{s})\nabla W(\bar{X}_{\underline{s}})$. For the first term, we use  the Jensen inequality and Proposition \ref{prop:fundamentalbounds2} $iii-b)$. We obtain that:
\begin{equation}\label{eq:ocircqun}
\mathbb{E}_{{x_0}}[|\circled{1}|^2]\lesssim_{uc}  \mathfrak{c}_\mathfrak{e} (L \tilde{L} \mathfrak{c}_1^{-2(1+\mathfrak{e})})^2 d^2 \Upsilon^{4r(1+\mathfrak{e})} \frac{1}{t_N} \int_{0}^{t_N}(s-\underline{s})^2
\text{d}s = \mathfrak{c}_\mathfrak{e}  (L \tilde{L} \mathfrak{c}_1^{-2(1+\mathfrak{e})})^2 d^2 \Upsilon^{4r(1+\mathfrak{e})}\frac{\gamma^2}{3}
\end{equation}


Let us finally consider $\circled{2}$. 
We introduce the martingale $(M_t)_{t \ge 0}$ defined as:
$$
M_t = \int_{0}^t \nabla^2 W(\bar{X}_{\underline{u}} + \Delta_{\underline{u}u}) \text{d}B_u.
$$
Using the {It\^o} formula, we obtain that:

\begin{align*}
\nabla W(\bar{X}_{\underline{s}}+\Delta_{\underline{s}s})-\nabla W (\bar{X}_{\underline{s}}) &= \int_{\underline{s}}^{s} \nabla^2 W(\bar{X}_{\underline{s}} + \Delta_{\underline{s}u}) \text{d}B_u + \int_{\underline{s}}^s \vec{\Delta}(\nabla W)(\bar{X}_{\underline{s}}+ \Delta_{\underline{s}u}) \text{d}u \\
& = M_s-M_{\underline{s}} + \int_{\underline{s}}^s \vec{\Delta}(\nabla W)(\bar{X}_{\underline{s}}+ \Delta_{\underline{s}u}) \text{d}u.
\end{align*}
where for a vector field $\phi:\mathbb{R}^d\mapsto\mathbb{R}^d$, $\vec{\Delta} \phi=(\Delta \phi_1,\ldots,\Delta \phi_d)^T$ with $\Delta$ standing for the Laplacian operator.
We use this decomposition into $\circled{2}$ and observe that:
\begin{align*}
\circled{2} &=\frac{1}{t_N} \int_{0}^{t_N} Dg(\tilde{X}_{\underline{s}}) \left( M_s-M_{\underline{s}}\right) \text{d}s +\frac{1}{t_N} \int_{0}^{t_N} Dg(\tilde{X}_{\underline{s}})
 \int_{\underline{s}}^{s} \vec{\Delta}(\nabla W)(\bar{X}_{\underline{s}} + 
\Delta_{\underline{s}u}) \text{d}u \text{d}s.
\end{align*}
The Young inequality yields:
\begin{equation}\label{def2a2b}
\mathbb{E}[|\circled{2}|^2] \leq 2 \underbrace{\mathbb{E} \left[ \left|\frac{1}{t_N} \int_{0}^{t_N} Dg(\tilde{X}_{\underline{s}}) \left( M_s-M_{\underline{s}}\right) \text{d}s  \right|^2\right]}_{:=\circled{2a}}+
2 \underbrace{\mathbb{E} \left[ \left|\frac{1}{t_N} \int_{0}^{t_N} Dg(\tilde{X}_{\underline{s}}) \int_{\underline{s}}^{s} \vec{\Delta}(\nabla W)(\bar{X}_{\underline{s}} + 
\Delta_{\underline{s}u}) \text{d}u\text{d}s \right|^2\right]}_{:=\circled{2b}}
\end{equation}
We first deal with \circled{2a} and use the martingale decomposition, we obtain that:
\begin{equation}
\circled{2a} = 
\mathbb{E}\Big[ \Big| \frac{1}{t_N} \sum_{k=1}^{N}  \underbrace{\int_{t_{k-1}}^{t_k}
Dg(\tilde{X}_{t_{k-1}}) (M_s-M_{t_{k-1}}) \text{d}s}_{:=\Delta N_k}  \Big|^2 \Big] = \frac{1}{t_N^2}  \sum_{k=1}^N \mathbb{E}[\mathbb{E}[|\Delta N_k|^2 \, \vert \mathcal{F}_{t_{k-1}}]],\label{eq:decomposition_2a}
\end{equation}
where we used that $\mathbb{E}[\Delta N_k \, \vert \mathcal{F}_{t_{k-1}}]=0$.  Standard computations show that:
\begin{align*}
\mathbb{E}[|\Delta N_k|^2 \, \vert \mathcal{F}_{t_{k-1}}]&=
\mathbb{E} \left[ \int_{t_{k-1}}^{t_k} \int_{t_{k-1}}^{t_k}  
\{Dg(\tilde{X}_{t_{k-1}}) (M_v-M_{t_{k-1}})\}^T Dg(\tilde{X}_{t_{k-1}}) (M_u-M_{t_{k-1}}) \text{d}u \text{d}v  \, \vert \mathcal{F}_{t_{k-1}}\right]\\
& =  \int_{t_{k-1}}^{t_k} \int_{t_{k-1}}^{t_k}  
{\rm Tr}\left( \mathbb{E} \left[
Dg(\tilde{X}_{t_{k-1}})^T Dg(\tilde{X}_{t_{k-1}}) (M_u-M_{t_{k-1}}) (M_v-M_{t_{k-1}})^T\, \vert \mathcal{F}_{t_{k-1}}\right] \right) \text{d}u \text{d}v \\

 & = 2 \int_{t_{k-1}}^{t_k} \int_{t_{k-1}}^{u}  
{\rm Tr}\left(
Dg(\tilde{X}_{t_{k-1}})^T Dg(\tilde{X}_{t_{k-1}}) 
 \mathbb{E} \left[(M_u-M_{t_{k-1}}) (M_v-M_{t_{k-1}})^T\, \vert \mathcal{F}_{t_{k-1}}\right] \right)  \text{d}v \text{d}u.
\end{align*}
The last conditional expectation deserves a specific study: for any pair $(i,j)\in \{1,\ldots,d\}^2$ and any $t_{k-1}\leq v \leq u \leq t_{k}$,  we have:
\begin{align*}
\mathbb{E}  \big(\big[ \big((M_u-M_{t_{k-1}})& (M_v-M_{t_{k-1}})^T\big)_{i,j} \, \vert \mathcal{F}_{t_{k-1}} \big] \big) = 
\mathbb{E} \left(\left[ (M_u^{(i)}-M^{(i)}_{t_{k-1}}) (M^{(j)}_v-M^{(j)}_{t_{k-1}}) \, \vert \mathcal{F}_{t_{k-1}} \right] \right)\\
 &=  \int_{t_{k-1}}^{ v} \sum_{\ell=1}^d \mathbb{E}[ \nabla^2 W^{i,\ell}(\bar{X}_{t_{k-1}}+\Delta_{t_{k-1},s})\nabla^2 W^{j,\ell}(\bar{X}_{t_{k-1}}+\Delta_{t_{k-1},s}) \, \vert \mathcal{F}_{t_{k-1}}]\text{d}s,
\end{align*}
where the previous equality comes from the independent Brownian increments coordinates per coordinates and from $u \wedge v=v$. This induces the matricial equality:
$$
\mathbb{E} \left[  (M_u-M_{t_{k-1}}) (M_v-M_{t_{k-1}})^T  \, \vert \mathcal{F}_{t_{k-1}} \right] =
\int_{t_{k-1}}^{ v}\mathbb{E}[ \nabla^2 W(\bar{X}_{t_{k-1}}+\Delta_{t_{k-1},s})\nabla^2 W(\bar{X}_{t_{k-1}}+\Delta_{t_{k-1},s})^T \, \vert \mathcal{F}_{t_{k-1}}]\text{d}s.
$$
Noting that 
$$
{\rm Tr}\left(
Dg(\tilde{X}_{t_{k-1}})^T Dg(\tilde{X}_{t_{k-1}}) \right) 
=\|  Dg(\tilde{X}_{t_{k-1}})\|_{F}^2,
$$
we then deduce that:
\begin{equation}
\mathbb{E}[|\Delta N_k|^2 \, \vert \mathcal{F}_{t_{k-1}}]\nonumber\\

 


  = 2 \mathbb{E} \left[ \int_{t_{k-1}}^{t_k} \int_{t_{k-1}}^{u}  \int_{t_{k-1}}^{v}  \|  Dg(\tilde{X}_{t_{k-1}}) 
   \nabla^2 W(\bar{X}_{t_{k-1}}+\Delta_{t_{k-1},s})\|_{F}^2 \text{d}s \text{d}v \text{d}u
 \, \vert \mathcal{F}_{t_{k-1}}
 \right].\label{eq:Delta_Nk_conditionnel}
\end{equation}
Plugging Equation \eqref{eq:Delta_Nk_conditionnel} into Equation \eqref{eq:decomposition_2a}, we deduce that:
\begin{equation}\label{def2aa}
\circled{2a} = \frac{2}{t_N^2} \sum_{k=1}^N   \int_{t_{k-1}}^{t_k} \int_{t_{k-1}}^{u}  \int_{t_{k-1}}^{v}  \mathbb{E} \left[\|  Dg(\tilde{X}_{t_{k-1}}) 
   \nabla^2 W(\bar{X}_{t_{k-1}}+\Delta_{t_{k-1},s})\|_{F}^2\right] \text{d}s \text{d}v \text{d}u.
\end{equation}

We then use the relationship between the spectral and the Frobenius norm and the fact that the spectral norm is {an operator} norm, we observe that for any $k$ and $s \in [t_{k-1},t_k]$:
\begin{align}
\|Dg(\tilde{X}_{t_{k-1}})\nabla^2 W(\bar{X}_{t_{k-1}}+\Delta_{t_{k-1},s})\|_F^2 & \leq
d' \nsp{Dg(\tilde{X}_{t_{k-1}})\nabla^2 W(\bar{X}_{t_{k-1}}+\Delta_{t_{k-1},s})}^2\nonumber \\
& \leq d' \nsp{\nabla^2 W(\bar{X}_{t_{k-1}}+\Delta_{t_{k-1},s})}^2  \nsp{Dg(\tilde{X}_{t_{k-1}})}^2\nonumber\\
& \leq d' L^2 \ \nsp{Dg(\tilde{X}_{t_{k-1}})}^2,\label{defdfll}
\end{align}
where we use that $\nabla W$ is a L-Lipschitz function. We then use Proposition \ref{prop:fundamentalbounds2} $i-b)$, a slight adaptation of Proposition \ref{lem:expbounds22} to get the same bounds for $\mathbb{E}[\nsp{Dg(\tilde{X}_{\underline{t}})}^2]$ as for $\mathbb{E}[\nsp{Dg(\bar{X}_{\underline{t}})}^2]$. We conclude that:

\begin{equation}
\circled{2a}  \lesssim_{uc} \frac{c_{\mathfrak{e}} L^2 \mathfrak{c}_1^{-2r(1+\mathfrak{e})} d\Upsilon^{2r(1+\mathfrak{e})}  }{t_N^2} \sum_{k=1}^{N} \int_{t_{k-1}}^{t_k} \int_{t_{k-1}}^u \int_{t_{k-1}}^v \text{d}s \text{d}v \text{d}u =  c_{\mathfrak{e}} L^2 \mathfrak{c}_1^{-2(1+\mathfrak{e})} d'\Upsilon^{2r(1+\mathfrak{e})}\frac{\gamma}{N}
\label{eq:terme1}
\end{equation}







Let us finally consider $\circled{2b}$. By Jensen inequality, 
\begin{align}
\circled{2b} & \leq \mathbb{E}\left[\frac{1}{t_N} \int_{0}^{t_{N}}  \left|  Dg(\tilde{X}_{\underline{s}}) 
\int_{\underline{s}}^s  \vec{\Delta}(\nabla W)(\bar{X}_{\underline{s}}+ \Delta_{\underline{s}u}) \text{d}u \right|^2 \text{d}s\right]\nonumber\\
& \leq \mathbb{E}\left[\frac{1}{t_N} 
\int_{0}^{t_{N}} \nsp{Dg(\tilde{X}_{\underline{s}})}^2 \|\vec{\Delta}(\nabla W)\|_{2,\infty}^2 (s-\underline{s})^2 
\text{d}s\right] \nonumber\\
& \leq \frac{ \|\vec{\Delta}(\nabla W)\|_{2,\infty}^2 }{t_N} \int_{0}^{t_N}
\mathbb{E}[ \nsp{Dg(\tilde{X}_{\underline{s}})}^2](s-\underline{s})^2 \text{d}s\label{eq:terme2exact}\\
& \lesssim_{uc}  \|\vec{\Delta}(\nabla W)\|_{2,\infty}^2 \gamma^2 \mathfrak{c}_1^{-2(1+\mathfrak{e})} \Upsilon^{2r(1+\mathfrak{e})},\label{eq:terme2}
\end{align}
where the last inequality follows from Proposition \ref{prop:fundamentalbounds2}. \\

\noindent By \eqref{eq:ocircqun}, \eqref{eq:terme1} and \eqref{eq:terme2}, we are now able to give a new bound for $A_{t_N}^{(2,2)}$:

\begin{align*}
 \mathbb{E}\left|A_{t_N}^{(2,2)}\right|^2&\lesssim_{uc}  \mathfrak{c}_\mathfrak{e}  \mathfrak{c}_1^{-2(1+\mathfrak{e})} \gamma^2 \max\left(  \mathfrak{c}_1^{-2(1+\mathfrak{e})}(L\tilde{L})^2 d^2 \Upsilon^{4r(1+\mathfrak{e})},\|\vec{\Delta}(\nabla W)\|_{2,\infty}^2  \Upsilon^{2r(1+\mathfrak{e})}\right)\\
 &+c_{\mathfrak{e}}  \mathfrak{c}_1^{-2(1+\mathfrak{e})} d'\Upsilon^{2r(1+\mathfrak{e})}\frac{(L\gamma)^2}{t_N}.
\end{align*}




{Collecting the bounds obtained for $A_{t_N}^{(0)}$, $A_{t_N}^{(1)}$, $A_{t_N}^{(2,1)}$, $A_{t_N}^{(2,2)}$ and $A_{t_N}^{(3)}$,
we get (using that $L\gamma\le 1$):
\begin{align}
& \mathbb{E}\Big|\frac{1}{t_N} \sum_{k=1}^N \gamma_k {\mathbf{I}_d}(\bar{X}_{t_{k-1}}) -\pi(\mathbf{I}_d)\Big|^2\lesssim_{uc} c_\mathfrak{e} \max\left( \mathfrak{c}_1^{-3-2\mathfrak{e}}  \frac{\Upsilon^{(1+3r)(1+\mathfrak{e})}}{t_N^2},\mathfrak{c}_1^{-2(1+\mathfrak{e})} \frac{d' \Upsilon^{2r(1+\mathfrak{e})}}{t_N} \right) \label{eq:first3454}\\
 &+
c_\mathfrak{e}  \mathfrak{c}_1^{-2(1+\mathfrak{e})} \gamma^2 \max\left( L^2{\mathfrak{c}_2}  {\Upsilon^{(1-q+2r)(1+\mathfrak{e})}} , (\mathfrak{c}_1^{-(1+\mathfrak{e})}L\tilde{L} d)^2 \Upsilon^{4r(1+\mathfrak{e})},\|\vec{\Delta}(\nabla W)\|_{2,\infty}^2  \Upsilon^{2r(1+\mathfrak{e})}\right).\label{eq:first3455}
\end{align}
}
In order to ensure that $\eqref{eq:first3455}\le c_{\mathfrak{e},r,q}\varepsilon^2$, we fix $\gamma_\varepsilon= c_{2,1} \varepsilon$ with 
$$ c_{2,1}=  \mathfrak{c}_1^{1+\mathfrak{e}}\min\left(L^{-1}{\mathfrak{c}_2}^{-\frac{1}{2}}  {\Upsilon^{-\frac{1-q+2r}{2}(1+\mathfrak{e})}} , \mathfrak{c}_1^{1+\mathfrak{e}}(L\tilde{L})^{-1} d^{-1} \Upsilon^{-2r(1+\mathfrak{e})},\|\vec{\Delta}(\nabla W)\|_{2,\infty}^{-1}  \Upsilon^{-r(1+\mathfrak{e})}\right).$$
Then, the condition on $N_\varepsilon$ comes from \eqref{eq:first3454} with exactly the same form as in $(i.b)$ (since the right-hand side of \eqref{eq:first3454} is the same as in 
\eqref{eq:first3452}). This concludes the proof of $(ii.a)$.\\

{For $(ii.b)$, we use that $\Upsilon\le c (\log d) d^{\frac{1}{1+q-r}}$ where $c$ does not depend on $d$ so that the previous bound leads to:  }
\begin{align*}
 \mathbb{E}\Big|\frac{1}{t_N} \sum_{k=1}^N \gamma_k {\mathbf{I}_d}(\bar{X}_{t_{k-1}}) -\pi(\mathbf{I}_d)\Big|^2\leq c  d^{\tilde{\mathfrak{e}}} \max\left( \frac{d^{\frac{1+3r}{1+q-r}}}{t_N^2},\frac{d'd^{\frac{2r}{1+q-r}}}{t_N},\gamma^2 d^{2+\frac{4r}{1+q-r}},  \gamma^2 d^{2\rho+\frac{2r}{1+q-r}}\right),
\end{align*}
where $\tilde{\mathfrak{e}}$ denotes an arbitrary small positive number. 
Setting $\gamma_\varepsilon=\varepsilon d^{-\max(1+\frac{2r}{1+q-r},\rho+\frac{r}{1+q-r})-\tilde{\mathfrak{e}}}$ allows to control the two last terms. Then, one sets $N_\varepsilon=d'd^{\frac{2r}{1+q-r}}\gamma_{\varepsilon}^{-1}\varepsilon^{-2}$ in order to control the second term and finally checks that the first one is also controlled by $c\varepsilon^2$ under this condition  and the fact that $\varepsilon\le d' d^{-\frac{1-r}{2(1+q-r)}}$ (where $c$ does not depend on $d$). 



\end{proof}


 \subsection{Bayesian learning with discrete LMC - weakly convex case - Theorem \ref{theo:learning_weak_convex}}
\label{sec:learning_weak}



\begin{proof}[Proof of Theorem \ref{theo:learning_weak_convex}]

We know that for any $\xi$, $U(\xi,.)$ satifies $(\mathbf{A}_L)$. It implies that $W_n$ is $nL$-smooth.
 Since  $U(\xi,.)$ satisfies $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$, a direct computation shows that $W_n$ satisfies $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ with $q=0$ and ${\mathfrak{c}_2}=nL$.

In the meantime, Assumption $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ on each $U(\xi,.)$ implies that:
\begin{align*}
\underline{\lambda}(\nabla^2 W_n) &= \underline{\lambda} \left( \sum_{i=1}^n {\nabla^2 }U(\xi_i,.)\right) \\
& \ge \sum_{i=1}^n \underline{\lambda}(\nabla^2 U(\xi_i,.))\\
& \ge \sum_{i=1}^n \mathfrak{c}_1 U(\xi_i,.)^{-r} = n \left(\frac{1}{n} \sum_{i=1}^n \mathfrak{c}_1 U(\xi_i,.)^{-r}\right)\\ 
& \ge \{\mathfrak{c}_1 n^{1-r}\} W_n^{-r}(\mathbf{\xi^n},x),
\end{align*}
where we applied the Jensen inequality to the convex function $u \mapsto u^{-r}$. Thus $\mathbf{(H}^{q,r}_{\mathfrak{KL}})$ holds with the pair $(\tilde{\mathfrak{c}_1}=\mathfrak{c}_1 n^{1-r},r)$ and  $(\tilde{{\mathfrak{c}_2}}=nL,0)$. By Proposition \ref{lem:expbounds22}, we thus deduce that
$$\sup_{t\ge0} \mathbb{E}_x[W_n ^p (X_{t})]+\sup_{t\ge0} \mathbb{E}_x[W_n ^p (\bar{X}_{t})]\le c_p \left(  W_n^p (x)+\Upsilon^p_n\right),$$
with 
$$
\Upsilon_n =c_r (n L) (\mathfrak{c}_1 n^{1-r})^{\frac{-1}{1-r}} d  \log(1+dnL) =c_{r,L,\mathfrak{c}_1,\mathfrak{e}} d n^{\mathfrak{e}}
$$
where $\mathfrak{e}$ is an arbitrary small number and $c_{r,L,\mathfrak{c}_1,\mathfrak{e}}$ is a constant depending only on $r$, $L$, $\mathfrak{c}_1$ and $\mathfrak{e}$.
We are now able to apply Theorem \ref{cor:thmPoisson}(i.a) with $\Upsilon=\Upsilon_n$. We observe that $\gamma_{\varepsilon_n}$ must be chosen such that
$$
\gamma_{\varepsilon_n} = \frac{n^{2(1-r)}}{d n^2 d^{2r(1+\mathfrak{e})}}\varepsilon_n^2 \wedge \frac{d}{n d^{1-q-2 r \mathfrak{e}}} \wedge \frac{d}{n d^{-2 r \mathfrak{e}} (d n)^{\frac{1-q}{1+q}}} \wedge \frac{d^{2r+q-1} d n^2}{n n^{2(1-r)}}
$$
For $n$ large enough, the minimum is then related to
$$
\gamma_{\varepsilon_n} =n^{-(2r+\alpha^{-1})} d^{\alpha^{-1}-1-2r} \wedge \frac{d^{q+2 r \mathfrak{e}}}{n} \wedge \frac{d^{\frac{2q}{1+q}+2 r \mathfrak{e}}}{n^{\frac{2}{1+q}}} \wedge \frac{d^{2r+q}}{n^{1-2r}}.
$$ 
We then verify that when $n \ge d$, we have:
$$
\forall q \in [0,1] \qquad 
\frac{d^{\frac{2q}{1+q}+2 r \mathfrak{e}}}{n^{\frac{2}{1+q}}} \leq \frac{d^{q+2 r \mathfrak{e}}}{n} \leq \frac{d^{2r+q}}{n^{1-2r}},
$$
so that
$$
\gamma_{\varepsilon_n} = n^{-(2r+\alpha^{-1})} d^{\alpha^{-1}-1-2r}
\wedge \frac{d^{\frac{2q}{1+q}+2 r \mathfrak{e}}}{n^{\frac{2}{1+q}}}.
$$
 We observe that 
$$
N_{\varepsilon_n} = \gamma_{\varepsilon_n}^{-1} \left[ 
\underbrace{d^{\frac{1+3r}{2}} n^{-\frac{3}{2}(1-r)} \left(\frac{n}{d}\right)^{\frac{1}{2\alpha_c}}}_{:=A} \vee \underbrace{d^{2r} n^{-2(1-r)} \left(\frac{n}{d}\right)^{\frac{1}{\alpha_c}}}_{:=B}
\right] 
$$
The study is then made explicit by considering some specific cases.
\begin{itemize}
\item If $r \ge 1$, we observe that $B \ge A$ for all values of $t \in [0,1)$. In that case we also verify that 
$
\gamma_{\varepsilon_n}^{-1} = n^{2r+\alpha^{-1}} d^{2r+1-\alpha^{-1}}.
$
The overall cost of computation is then given by
$$
N_{\varepsilon_n} = n^{2 \alpha_c^{-1}+4r} d^{1+4r-2\alpha_c^{-1}}.
$$
\item If $r=q=0$, since $d<n$, we verify that:
$$
\gamma_{\varepsilon_n}^{-1} = n^{\alpha_c^{-1}}d^{1-\alpha_c^{-1}} \vee n^2 = n^{2}
$$
and 
$$
N_{\varepsilon_n} = n^{\frac{1}{2}(1+\alpha_c^{-1})} d^{\frac{1}{2}(1-\alpha_c^{-1})}
$$

\end{itemize}

\end{proof}

















\section{Discretization of the Langevin procedure - Strongly convex case}\label{sec:discretisation}

 
We adapt the proof of Theorem \ref{cor:thmPoisson} to the strongly convex case and to this end, start with an adaptation of Proposition \ref{prop:fundamentalbounds2}:
\begin{prop}\label{prop:bisbis} Assume $(\mathbf{SC}_\rho)$. {Let $f:\mathbb{R}^d\rightarrow\mathbb{R}^{d'}$ be a Lispchitz ${\mathcal C}^2$-function with $[f]_1\le 1$ and $[Df]_{1,\star}\le 1$}.    Then, $g$ is  a ${\mathcal C}^2$-function and for every $\mathfrak{e}\in(0,1)$, a constant  $c_\mathfrak{e}$ exists (which only depends on $\mathfrak{e}$ and not on $d$), such that for any $x$:
\begin{enumerate}

\item[$i)$]

{$\nsp{Dg(x)}\le \frac{1}{\rho}.$}
\item[$ii)$] Let $\gamma \in (0,\rho/(2L^2)]$. Then,
$$\sup_{t\ge0} \mathbb{E}_{x_0}[| g(\bar{X}_t)-g(x_0)|^2]\le \frac{4}{\rho^2} \left(|x_0-x^\star|^2+ \frac{d}{\rho}\right).$$
\item[$iii)$] Assume that $\nabla^2 W$ is $\tilde{L}$-Lipschitz for the norm $\nsp{.}$. Then, {$x\mapsto Dg(x)$ is Lipschitz and its related Lipschitz constant 
$[Dg]_{1,\star}$ satisfies:}
$$[Dg]_{1,\star}=\sup_{x\neq y} \frac{\nsp{Dg(y)-Dg(x)}}{|y-x|}\le 
\left( {\frac{2 \tilde{L} }{\rho^2}} + {\frac{1}{2 \rho}}\right).$$
\end{enumerate}
\end{prop}

\begin{proof}[Proof of Theorem  \ref{cor:thmPoissonSC}]
(i) We follow the proof of Theorem  \ref{cor:thmPoisson}(i). Keeping the notations of the proof of Theorem  \ref{cor:thmPoisson},  we first deduce from $(ii)$ that
$$\mathbb{E}_{x_0}\left|A_{t_N}^{(0)}\right|^2\le \frac{4}{\rho^2 t_N^2} \left(|x_0-x^\star|^2+ \frac{d}{\rho}\right)\le \frac{8d}{\rho^3 t_N^2}$$
since $|x_0-x^\star|^2\le d/\rho$.


Second, by the deterministic bound $i)$ of Proposition \ref{prop:bisbis}: $\nsp{Dg(x)} \le \rho^{-1}$  and the arguments given in the proof of Theorem \ref{cor:thmPoisson}, we have:
$$\mathbb{E}_{{x_0}}\left|A_{t_N}^{(1)}\right|^2\le \frac{d'}{\rho^2 t_N}.$$
For $A_{t_N}^{(3)}$, we remark that the only modification comes from the control of 
$\sup \mathbb{E}|\nabla W(\bar{X}_{\underline{s}})|^2$.
Since $\nabla W$ is $L$-Lipschitz and $\nabla W(x^\star)=0$,  
$$\mathbb{E}|\nabla W(\bar{X}_{\underline{s}})|^2\le L^2 \mathbb{E}[|\bar{X}_{\underline{s}}-x^\star|^2].$$
By Lemma 5.1 of \cite{egea-panloup}, we deduce that 
$$\mathbb{E}|\nabla W(\bar{X}_{\underline{s}})|^2\le L^2\left(|x_0-x^\star|^2+ {\frac{2d}{\rho}}\right)\le \frac{8L^2d}{\rho},$$
since $|x_0-x^\star|^2\le d/\rho$.
\begin{align*}
\mathbb{E}_{{x_0}}\left|A_{t_N}^{(3)}\right|^2\le \frac{d\gamma^2}{3 t_N}+
{L^2 \gamma^2 \left(|x_0-x^\star|^2+\frac{d}{\rho}\right)}
+10d^2\gamma^2.
\end{align*}

For $A_{t_N}^{(2,1)}$, the fact that $\nsp{Dg(x)}\le \rho^{-1}$  yields:
\begin{align*}
\mathbb{E}_{{x_0}}[|A_{t_N}^{(2,1)}|^2]&\le \frac{L^2}{\rho^2 t_N} \int_{0}^{ t_N}(s-\underline{s})^2 \mathbb{E}_{{x_0}}[|\nabla W (\bar{X}_{\underline{s}})|^2] {\rm d}s\\
&\le  \frac{L^2}{\rho^2t_N}\times  { L^2\left(|x_0-x^\star|^2+ {\frac{2d}{\rho}}\right)}\times N \gamma^3 = { 
 \frac{L^4}{\rho^2}\times  \left(|x_0-x^\star|^2+ \frac{2d}{\rho} \right)\times \gamma^2 
}
\end{align*}





Finally, for $A_{t_N}^{(2,2)}$, we deduce from \eqref{eq:firstview} that
\begin{equation*}
\mathbb{E}_{{x_0}}[|A_{t_N}^{(2,2)}|^2]\le \frac{L^2}{\rho^2 t_N} \int_{0}^{t_N} E_{{x_0}}[|\Delta_{\underline{s}s}|^2] {\rm{d}}s 
\le \frac{2L^2 d}{\rho^2 t_N} \int_{0}^{t_N} (s-\underline{s}) {\rm{d}}s\le \frac{2L^2 d}{\rho^2}\gamma 
.
\end{equation*}
Thus, collecting the previous bounds and $L^2 d / \rho \leq L^4 d / \rho^3$:
\begin{align*}
\mathbb{E}\Big|\frac{1}{t_N} \sum_{k=1}^N \gamma_k {f}(\bar{X}_{t_{k-1}}) -\pi(f)\Big|^2 & \le \frac{d'}{\rho^2 t_N}+\frac{8d}{\rho^3 t_N^2}+\frac{d\gamma^2}{3 t_N}+10d^2\gamma^2+ \frac{8 L^4 d}{\rho^3} \gamma^2+\frac{2L^2 d}{\rho^2}\gamma\\
& + {2 \frac{L^4 }{\rho^2}  \gamma^2 |x_0-x^\star|^2}.
\end{align*}
{The larger term above regarding the size of $\gamma$ is $L^2 \rho^{-2 }d  \gamma$ and we are led to choose $\gamma \leq \frac{\rho^2}{2 L^2 d }\varepsilon^2$. We now verify the size of the other terms.}
Obviously we have:
$$
{d^2 \gamma^2 \leq d^2 \frac{\rho^4}{L^4 d^2} \varepsilon^4  \leq \varepsilon^4}
$$
since $\rho \leq L$.
We  observe that:
$$
{\frac{L^4 d }{\rho^3} \gamma^2 \leq \frac{L^4 d}{\rho^3} \frac{\rho^2 }{L^2 d} \varepsilon^2 \gamma = \varepsilon^2  \left(\frac{L^2}{\rho} \gamma\right)}
$$
At last, the terms involving the initial condition may be upper bounded in the same way:
$$
{2 \frac{L^4 }{\rho^2} \gamma^2 |x_0-x^\star|^2 \leq \varepsilon^2 \times \frac{\rho^2}{2 L^2 d} \left(\gamma |x_0-x^\star|^2 \times 2 \frac{L^4 }{\rho^2} \right) \leq 
\varepsilon^2 \times \frac{\gamma |x_0-x^\star|^2 L^2}{d}.
}
$$
{Using again that $\rho \leq L$, we then deduce that we have to choose $\gamma$ such that:
$$
\gamma \leq \frac{\rho^2}{L^2 d } \varepsilon^2 \wedge \frac{\rho}{L^2}  \wedge \frac{d}{L^2 |x_0-x^\star|^2}.
$$
}
{ Now, fix $N \ge\varepsilon^{-4} \frac{L^2}{\rho^4} d' d $ in such a way that $\frac{d'}{\rho^2 t_N}\le 2\varepsilon^2$.
Then,
$$\frac{8d}{\rho^3 t_N^2}= \frac{d'}{\rho^2 t_N} \times \frac{8 d}{\rho d' t_N}
\le \varepsilon^2 \times \frac{16 d }{\rho  d' t_N} \le 16 \varepsilon^2,$$
under the condition $N \ge \frac{d}{d' \rho} \gamma^{-1}$.
 Finally, since $\gamma\le \frac{\varepsilon^2}{d}$ and $N \ge 1$ it is obvious that $\frac{d\gamma^2}{3 t_N}\le \varepsilon^2/2$. The result follows.}\\

\noindent $(ii)$ As in $(i)$, we follow the proof of Theorem  \ref{cor:thmPoisson}(ii). With the notations of this proof, we check that the only difference between $(i)$ and $(ii)$ comes from the control of $A_{t_N}^{(2,2)}$. Actually, in this part, owing to a further expansion, $\mathbb{E}_{{x_0}}[|A_{t_N}^{(2,2)}|^2]$ is controlled by $\mathbb{E}_{{x_0}}[|\circled{1}|^2]+\mathbb{E}[|\circled{2}|^2]$ where $\circled{1}$ and $\circled{2}$ are defined in \eqref{def:atn22}.
On the one hand, by Proposition \ref{prop:bisbis}(iii), the Jensen inequality and $(a+b)^2 \leq 2 a^2+2b^2$: 
\begin{align*}
\mathbb{E}_{{x_0}}[|\circled{1}|^2]&\le L^2{ \left( \frac{1 }{2 \rho^2}+ \frac{8 \tilde{L}^2}{\rho^4}\right)} \frac{1}{t_N}\int_0^{t_N} \mathbb{E}[ |\Delta_{\underline{s}s}|^4] ds\\
&\le  L^2 {\left( \frac{1 }{2 \rho^2}+ \frac{8 \tilde{L}^2}{\rho^4}\right)}(4d^2-d)\frac{1}{t_N} \int_0^{t_N} (s-\underline{s})^2 ds\le  \frac{4\gamma^2}{3 } L^2 {\left( \frac{1 }{2 \rho^2}+ \frac{8 \tilde{L}^2}{\rho^4}\right)}.
\end{align*}
For $\mathbb{E}[|\circled{2}|^2]$, we recall that this term is divided into two parts denoted by $\circled{2a}$ and $\circled{2b}$ (see \eqref{def2a2b}. 
On the one hand,  by \eqref{def2aa}, \eqref{defdfll} and Proposition \ref{prop:bisbis}(i),
\begin{equation*}
\circled{2a} \le  \frac{2 d' L^2 }{\rho^2 t_N^2} \sum_{k=1}^N   \int_{t_{k-1}}^{t_k} \int_{t_{k-1}}^{u}  \int_{t_{k-1}}^{v}  \text{d}s \text{d}v \text{d}u\le 
\frac{ d' L^2 \gamma^2}{3\rho^2 t_N}.
\end{equation*}
Finally, for $\circled{2b}$, we derive from \eqref{eq:terme2exact} and Proposition \ref{prop:bisbis}(i) that, 
$$\circled{2b}\le \frac{ \|\vec{\Delta}(\nabla W)\|_{2,\infty}^2 }{\rho^2 t_N} \int_{0}^{t_N}
(s-\underline{s})^2 \text{d}s\le \frac{ \|\vec{\Delta}(\nabla W)\|_{2,\infty}^2 \gamma^2}{3 \rho^2 }.$$
Finally, we get
$$\mathbb{E}_{x_0}[|A_{t_N}^{(2,2)}|^2]\le \gamma^2 \left(
L^2 {\left( \frac{d'}{2 \rho^2}+ \frac{8 \tilde{L}^2}{\rho^4}\right)}
+\frac{ \|\vec{\Delta}(\nabla W)\|_{2,\infty}^2 }{3 \rho^2 }\right),$$
where we used that {$\frac{ d' L^2 }{3 \rho^2 t_N}\le
 L^2 \left( \frac{d' }{2 \rho^2}+ \frac{8 \tilde{L}^2}{\rho^4}\right)$} since $t_N \ge 1$.
 Collecting the whole bounds and replacing the one of $i)$ by the one we just obtained, we deduce that:
\begin{align*}
&\mathbb{E}\Big|\frac{1}{t_N} \sum_{k=1}^N \gamma_k {f}(\bar{X}_{t_{k-1}}) -\pi(f)\Big|^2\le \frac{\frac{d'}{\rho^2}+\frac{8d}{\rho^3 t_N}}{t_N}+
{\mathfrak{b}_2}\gamma^2 \\
&\textnormal{where} \quad\mathfrak{b}_2 \lesssim_{uc} d^2+\frac{L^4 d}{\rho^3}+
L^2 {\left( \frac{d' }{\rho^2}+ \frac{\tilde{L}^2}{\rho^4}\right)}
+
\frac{ \|\vec{\Delta}(\nabla W)\|_{2,\infty}^2 }{\rho^2  } 
+{\left(L^2  + \frac{L^4 }{\rho^2} \right)  |x_0-x^\star|^2} 
,
\end{align*}
where we used that $\frac{d\gamma^2}{3 t_N}\le \gamma^2 (L^4 d)/\rho^3$ since $\rho\le L$ and that $L\ge 1$.
For a given $\varepsilon$, we thus fix $\gamma_\varepsilon= \mathfrak{b}_2^{-\frac{1}{2}} \varepsilon$ so that ${\mathfrak{b}_2}\gamma^2\le \varepsilon^2$. Then, we fix  
$ N_\varepsilon=\varepsilon^{-3} \frac{\sqrt{\mathfrak{b}_2} d'}{\rho^2} \vee \gamma_{\varepsilon}^{-1} \vee d \gamma_{\varepsilon}^{-1} \rho^{-1}$, that implies that   $\frac{d'}{\rho^2 t_N}\le \varepsilon^2$. 
It remains to observe that $8 d / (\rho t_N) \leq 8$, the result then follows.
\end{proof}






 
 







The purpose of this paragraph is finally to prove the complexity bound stated in the strongly convex situation.
 
\begin{proof}[Proof of Theorem \ref{theo:learning_strong_convex}]
We first consider $(i.a)$.
We shall apply the above results  in our Bayesian framework. Given the set of $n$ observations $(\xi_1,\ldots,\xi_n)$, we have:
$$W_n(\mathbf{\xi^n},x) = \sum_{i=1}^n U(\xi_i,x).
$$
Assuming that $U(\xi,.)$ satisfies $(\mathbf{A}_L)$, the triangle inequality shows that $W_n(\mathbf{\xi^n},.)$ satisfies  $(\mathbf{A}_{n L})$ regarless the value of $\mathbf{\xi^n}$.
{In} the meantime, assuming that $U(\xi,.)$ satisfies $(\mathbf{SC}_\rho)$ yields 
$  W_n(\mathbf{\xi^n},.)$ is $n \rho$-strongly convex \textit{i.e.} satisfies $(\mathbf{ SC}_{n\rho})$. The result in then straightforward observing that the condition on $\gamma$ is driven by $\gamma_{\varepsilon_n} \leq \frac{d}{n^2 L^2 |\theta_0-\theta^\star|^2} = \mathcal{O}_{id}(n^{-2})$ and pluging it in the value of $N_{\varepsilon_n}$.

Concerning $(i.b)$, we shall verify that the constraint on $\gamma$ is brought by $A_{t_N}^{(2,1)}$ that should verify $n d \gamma^2 \leq \varepsilon_n^2$. Then the constraint on $N$ is then deduced in the same way.
\end{proof}



