{'fraction_non_alphanumeric': 0.062202753441802254, 'fraction_numerical': 0.0243161094224924, 'mean_word_length': 3.60261685319289, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 67, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 51, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Polynomial time guarantees for sampling based posterior inference in high-dimensional generalised linear models

The problem of computing posterior functionals in general high-dimensional statistical models with possibly non-log-concave likelihood functions is considered. Based on the proof strategy of [56], but using only local likelihood conditions and without relying on M-estimation theory, non-asymptotic statistical and computational guarantees are provided for gradient based MCMC algorithms. Given a suitable initialiser, these guarantees scale polynomially in key algorithmic quantities. The abstract results are applied to several concrete statistical models, including density estimation, nonparametric regression with generalised linear models and a cononical statistical non-linear inverse problem from PDEs.


Introduction
Posterior inference for high-dimensional statistical models is increasingly important in contemporary applications, particularly in the physical sciences and in engineering [60,65,24]. Computing relevant functionals such as the posterior mean, mode or quantiles often relies on iterative sampling algorithms. Without additional structural assumptions, however, the mixing times of these algorithms can scale exponentially in the model dimension p or the sample size n [20,71]. In this case, valid inference on an underlying ground truth requiring p ≍ n ρ , ρ > 0, is intractable. Overcoming such computational hardness barriers is crucial to allow for efficient sampling based Bayesian procedures.
Here, the data Z (n) = (Z i ) n i=1 are observations in a statistical model depending on a ground truth θ 0 ∈ ℓ 2 (N) with log-likelihood function ℓ n and prior density π. Suppose that the computational complexity of some MCMC algorithm arises mainly from the number of iterations. In this case, existing guarantees for practically feasible mixing times, growing at most polynomially in n, p, are essentially limited to strongly concave ℓ n with Lipschitz-gradients [13,19,43,75]. When ℓ n is non-linear, both properties are generally not satisfied, even for Gaussian priors. Relevant examples include mixture models, statistical non-linear inverse problems [49,48,31,1,52] and generalised linear models (GLMs) [47]. For related discussions on MCMC in different statistical settings and closely related optimisation algorithms see [4,59,66,39,44,57,6,12].
In a recent contribution Nickl and Wang [56] obtain polynomial time sampling guarantees in a specific non-linear example involving a partial differential equation (PDE). To go beyond the non-concave setting, the key-idea, which was later extended by [8] to other PDEs, is to rely on the Fisher information for providing a natural statistical notion of curvature for the log-likelihood function near θ 0 . By combining empirical process techniques with tools from Bayesian nonparametrics [28], there exists a high-dimensional region B ⊂ R p of parameters near θ 0 , where the posterior measure concentrates most of its mass and where ℓ n is locally strongly concave with high probability. Convexifying −ℓ n yields a surrogate posterior measure, whose log-density logπ(·|Z (n) ) is globally strongly concave with Lipschitz-gradients, and which is close to the true posterior measure in Wasserstein distance with high probability. Given a problem-specific initialiser θ init ∈ R p to identify the region B in a data-driven fashion,π(·|Z (n) ) can be leveraged to generate approximate samples of the posterior by a gradient-based Langevin MCMCscheme with cost depending polynomially on p and n, based on recent results by Durmus and Mouline [18].
In the present work we extend this proof strategy beyond the PDE setting to general high-dimensional statistical models. While [56,8] rely upon M-estimation theory for the maximum-a-posteriori (MAP) estimator to show the log-concave approximation of the posterior measure, our proof takes a novel route and is fully Bayesian. This turns out to be crucial in regression models with unbounded and possibly non-Lipschitz regression functions. Assuming only local likelihood conditions, we obtain non-asymptotic sampling guarantees for posterior functionals with polynomial dependence of key algorithmspecific parameters simultaneously on n, p and the target precision level. The abstract hypotheses are verified for concrete statistical models in density estimation and nonparametric regression under Bernstein conditions, including Gaussian and Poisson measurement errors. To demonstrate our approach in a canonical example from the inverse problem literature, we discuss in detail sampling for an elliptic PDE, sometimes called Darcy's problem (see [53] and Section 3.7 of [65]), with a non-Lipschitz forward map.
We further prove that the Langevin Markov chain based on the surrogate density takes exponentially in n many steps to leave the region of local curvature, where it coincides with π(·|Z (n) ). Our results therefore imply that upon initialising into a region of sufficient local curvature even a standard vanilla Langevin MCMC algorithm is able to compute posterior aspects at polynomial cost. This is consistent with related results for gradient based optimisation algorithms that local curvature near the global optimum can improve the rate of convergence [5]. Sampling algorithms, on the other hand, necessarily have to explore the full parameter space and therefore depend more heavily on global properties of the underlying target distribution. Note that, even if an initialiser near θ 0 is available, it is not clear if the computation of posterior functionals, which depend on the whole posterior measure, is feasible. The existence of a suitable initialiser is postulated here, and finding one in polynomial time may be in itself a non-trivial task. We discuss this issue in some concrete examples. Since Gaussian priors are of particular interest in practice, we cannot restrict to compact parameter regions a-priori, which introduces substantial technical challenges.
Bayesian inference in high-dimensional models has been intensely studied in the literature [34,25,27,38,68,73,26]. Guarantees for MCMC-based posterior sampling algorithms were obtained, e.g., by [32,6], showing that sampling at polynomial cost is possible, in principle. Their assumptions are, however, rather restrictive and not explicit in their quantitative dependence on n and p, see [56] for a discussion and additional references. Starting with [13] several works focus on obtaining non-asymptotic results for Langevin-type algorithms and strongly log-concave target measures [50,17]. To break the 'curse of dimensionality', and often also the 'curse of non-linearity', other sampling approaches replace the complex posterior measure by a more simple object [58,74,63], yielding empirically efficient procedures, but with unclear relation to the true posterior measure.
Conceptually, the approximation by a log-concave measure is different from the more traditional Gaussian Laplace-type approximations [64,33,63,6], where the posterior is replaced by a quadratic with constant covariance matrix relative to a well-chosen centring point (often the MAP estimator). In contrast, we leave the log-likelihood function locally unchanged. This added flexibility seems to be crucial for obtaining the fast convergence towards the posterior measure in our results. Related to this are Bernstein-von Mises theorems, which generally do not hold in high-dimensional settings [11,23]. In particular, [54] have recently shown that no such theorem exists for Darcy's problem, while we show that efficient MCMC-sampling is possible (see also [53,Remark 5.4.2]). This paper is organised as follows: In Section 2 the main results are demonstrated for nonparametric generalised linear models. Section 3 develops the approximation by the surrogate posterior measure in a general context and presents convergence guarantees for the surrogate and vanilla Langevin sampler. In Section 4, applications to several statistical models are discussed in detail, including density estimation, nonparametric regression and Darcy's problem. Proofs are deferred to Section 5 and to the Appendix.
We write a b if a ≤ Cb for a universal constant C, and a ≍ b if a b and b a. For a measurable space (O, A), equipped with a measure ν O , let L p (O), 1 ≤ p ≤ ∞, be the spaces of p-integrable A-measurable functions with respect to ν O , normed by · L p , and denote by ℓ p (N) the usual spaces of p-summable sequences with norm · ℓ p . Set · = · ℓ 2 . For a matrix M ∈ R p×p let M op be the operator norm. The minimal and maximal eigenvalues of a positive symmetric matrix Σ are denoted by λ min (Σ), λ max (Σ).
For two Borel probability measures µ 1 , µ 2 on R p with finite second moments the (squared) Wasserstein distance is defined as where the infimum is computed over all couplings µ of µ 1 , µ 2 . Denote by C k (O), 0 ≤ k ≤ ∞, the spaces of k-times differentiable real-valued functions. For a real-valued function f : R p → R, its gradient and Hessian, if existing, are denoted by ∇f , ∇ 2 f , respectively. We say that f is Lipschitz if the norm f Lip = sup x,y∈R p ,x =y x−y is finite. Moreover, we say f is globally m f -strongly concave and has Λ f -Lipschitz gradients

Main results for generalised linear models
In this section we illustrate our main results in the concrete setting of the GLMs introduced by Nelder and Wedderburn in [51]. They comprise several important non-linear statistical regression models such as Gaussian, Poisson and logistic regression. Bayesian inference for GLMs is a classical topic [16], for posterior contraction in high-dimensional GLMs see, e.g., [27,26,77]. As far as we know, the available posterior sampling guarantees in the literature apply only to Gaussian and logistic regression with canonical link functions, cf. the examples in [13,75]. Let Θ ⊂ ℓ 2 (N) be a parameter space containing R p . Let (X , A) be a measurable space equipped with a measure ν X and let ξ be a probability measure on R. Set ν = ξ ⊗ ν X . For an orthonormal basis (e k ) k≥1 of L 2 (X ) let Φ(θ) = ∞ k=1 θ k e k and let g : I → R be an invertible and continuous link function on some interval I ⊂ R.
Suppose that n independent observations such that the law of the response variables Y i follows conditional on X i = x a one-parameter exponential family with If p X denotes the ν X -density of the covariates X i , then this means that the coordinate ν-densities p θ are of the form with A(h) = log R e yh dξ(y) and where the natural parameter is given by the generally non-linear scalar-valued function The observations Z (n) follow then the nonparametric regression model

Prior and posterior
Introduce for α ∈ R the ℓ 2 (N)-Sobolev spaces Assuming that the data are generated according to P n θ 0 for a parameter θ 0 ∈ h α (N) with regularity α ≥ 0, a popular 'sieve' prior distribution puts independent scalar Gaussian priors with increasing variances on the first p coefficients θ ∈ R p , that is, Let π ≡ π n denote the density of Π. The posterior measure Π(·|Z (n) ) then arises from the observations Z (n) using Bayes' formula with probability density where the log-likelihood function of the data Z (n) equals up to additive constants (not depending on θ) Note that this is independent of p X . Together with the Gaussian prior the log-posterior density is strongly concave if ℓ n is concave, and has Lipschitz gradients if ℓ n does. Both properties generally fail for an arbitrary link function g and hold even for the canonical link only in exceptional cases.
is linear, A is convex and ℓ n concave. For Gaussian and logistic regression with A(x) = x and A(x) = log(1 + e x ), respectively, A ′′ is bounded and ∇ℓ n uniformly Lipschitz. See Remark 8 for a comment on sampling guarantees in this case.
Example 2. In Poisson regression with the canonical link we have A(x) = e x − 1 and the Lipschitz constant of ∇ℓ n grows exponentially as θ → ∞. Since the Gaussian prior is supported on all of R p , the Lipschitz-property cannot be enforced by restricting to θ in a ball of fixed Euclidean radius.

Local curvature
Instead of sampling directly from Π(·|Z (n) ) let us first determine a high-dimensional and statistically informative set of parameters, where the curvature of ℓ n can be quantified depending on n and p. Our candidate for this is where η > 0 and θ * ,p = (θ 0,1 , . . . , θ 0,p ) is the R p -projection of θ 0 , which we assume to be a sufficiently good approximation of θ 0 . To identify the region B suppose also that we dispose of a 'proxy' θ init ∈ B, which will also serve as the initialiser of the MCMC scheme in the next section. We will establish that the eigenvalues of −∇ 2 ℓ n (θ) are on B, up to an absolute factor, contained in the interval [n, np 1/2 ] with high P n θ 0 -probability as soon as the map b in (3) is uniformly bounded on B. Sufficient conditions for this are as follows.
Condition 3. Suppose that θ 0 ∈ h α (N) for α > 1 and let p ≤ Cn 1/(2α+1) , C > 0. The radius of B is η = p −1/2 , and θ * ,p , θ init are such that c 0 > 0. The design is bounded in the sense that c −1 X ≤ p X (x) ≤ c X for all x ∈ X and some c X > 0, and the basis functions satisfy sup k≥1 sup x∈X |e k (x)| ≤ c X .
A suitable proxy θ init can be computed at polynomial cost from the data Z (n) , for instance, by the estimators in [22,45,72]. Note that the radius η is much larger than the minimax rate n −α/(2α+1) for an α-smooth ground truth in the underlying regression model, cf. [10]. While the region B shrinks as p → ∞, its radius η n −α/(2α+1) is large relative to the typical size of a ball around θ * ,p on which most of the posterior mass is concentrated with high P n θ 0 -probability (for a precise definition see (14) below). For an alternative initialisation with constant radius η see Remark 7.
With this we define in (17) a surrogate log-likelihood functionl n , which coincides with ℓ n on B and which ism-strongly concave withΛ-Lipschitz gradients form ≍ n, Λ ≍ np 1/2 . This induces the surrogate posterior measureΠ(·|Z (n) ) with densitỹ It coincides with Π(·|Z (n) ) on measurable subsets of B up to random normalising factors.

Sampling guarantees
A standard MCMC approach for sampling from the Gibbs-type measure with density (9) is the unadjusted Langevin algorithm [62]. It takes an initialiserθ 0 , a step size γ > 0 and independent p-dimensional Gaussian innovations ξ k ∼ N (0, I p×p ) as input, and produces a Markov chain with iteratesθ k ∈ R p , wherẽ We initialise atθ 0 ≡ θ init ∈ B. Sincel n coincides with ℓ n on a set where the posterior puts most of its mass, we expect that the invariant measure of the Markov chain is close to the true posterior measure, while the global concavity leads to fast mixing. In our first main result we derive an exponential concentration inequality under the law of the Markov chain, denoted by P, for the approximation of posterior functionals by ergodic averages. It requires a sufficiently small γ, a burn-in time J in ≥ 1 and a precision level ε > 0, which is lower bounded according to the sample size and a discretisation 'bias' relative to the continuous time formulation of (11) as γ → 0. Note that the theorem is explicit in the dependence of constants on p, n and non-asymptotic in the sense that whenever the hypotheses hold for pairs p, n, then so do the conclusions, which are informative only as n → ∞.
Theorem 4. Suppose the data arise in a GLM with coordinate densities (2) and g ∈ C 3 (I). Let Condition 3 be satisfied and let (θ k ) k≥1 be the Markov chain with iterates (11). For c > 0 suppose that γ ≤ cn .
This result implies that if γ −1 depends polynomially on p, n, then the number of iterations J + J in = O(n ρ p ρ ′ ε −ρ ′′ ), ρ, ρ ′ , ρ ′′ > 0, necessary to approximate posterior functionals at precision ε, grows at most polynomially in n, p and ε −1 with high P n θ 0 × P-probability. Consider next the Markov chain with iterates depending on the true posterior density Since we start from θ init ∈ B, the iterates coincide withθ k , as long as the latter has not exited from the region of local curvature B. This will happen 'eventually' due to the Gaussian innovations. We will prove, however, that it takes in average exponentially in n many steps J out ≫ J in to do so for the first time. Combined with Theorem 4 this yields polynomial time sampling guarantees for the posterior using (ϑ k ) k≥0 . We write again P for the law of this Markov chain.
Theorem 5. Under the assumption of Theorem 4 suppose that γ ≤ cn −1 p −1 , J out = c ′ e c ′′ n 1/(2α+1) for c ′ , c ′′ > 0 and p ≤ C(log n) −(2α+1/2) n 2α 2α+1 · 1 2α+1/2 . Then there exist c 1 , c 2 , c 3 , c 4 > 0 such that with P n θ 0 -probability at least 1 − c 2 exp(−c 1 n 1/(2α+1) ) for all In the final result of this section we recover the ground truth θ 0 with high P n θ 0 × Pprobability by approximating the posterior mean using f (θ) = θ in the last theorem. We clearly see the impact of statistical and computational errors on the approximation. Recall that n −α/(2α+1) is the frequentist minimax rate of convergence for estimating an α-smooth θ 0 . Theorem 6. Under the assumptions of Theorem 5 there exist c 1 , c 2 , c 3 > 0 such that with P n θ 0 × P-probability at least 1 − c 2 exp(−c 1 n 1/(2α+1) ) for all J + J in ≤ J out Remark 7 (Initialisation in the GLM model). Deviating from the general setting below, It can be shown that the results in this section remain true if the set B in the construction ofl n is replaced by B log n , where B ρ = {θ ∈ R p : θ − θ * ,p ≤ c 1 , θ α ≤ ρ} for any large enough c 1 > 0 (it is actually sufficient to take B c 0 if an upper bound θ 0 α ≤ c 0 is known), yielding a larger Lipschitz constantΛ. This means it is enough to initialise into a compact parameter set, which can be done by grid search in logarithmic time. This observation seems less relevant for GLMs, because good initialisers exist, but may be useful for other statistical models. Remark 8 (Log-concave likelihood functions). In Example 1 we can directly apply known sampling results for log-concave measures, e.g. [18,Theorem 5], which depend critically on the condition number Λ π /m π ≍ p 2α . Using our machinery this is replaced by the smaller quantity Λ/m ≍ p 1/2 , leading to faster mixing, even in the ideal case of a concave log-likelihood function.

General sampling guarantees
Let us now consider a more general statistical setup. As before, Θ ⊂ ℓ 2 (N) denotes a parameter space containing R p . We are given n independent observations with values in Z n , where (Z, A) is a measurable space, drawn from a product measure P n θ = ⊗ n i=1 P θ , θ ∈ Θ. Let p θ denote the probability density of P θ with respect to a dominating measure ν. The log-likelihood function is The Bayesian approach assumes θ ∼ Π for a prior probability measure Π ≡ Π n on Θ, supported on R p , and which may depend on n. We suppose that it has a Lebesgue density π ≡ π n . The posterior distribution is then induced by the density (1) up to normalising factors.

Main assumptions
The convergence guarantees below will be formulated with respect to a fixed ground truth θ 0 ∈ Θ generating the data Z (n) . Let θ * ,p ∈ R p be a high-dimensional approximation of θ 0 (not necessarily its R p -projection as in Section 2). A fundamental assumption for all the following considerations is that the posterior measure contracts around θ * ,p at a certain 'rate' δ n > 0 with high P n θ 0 -probability and that a small ball condition holds for the 'normalising factors'. Both conditions can be verified by standard tools from Bayesian nonparametrics, following the seminal work [25].
Assumption A. The data Z (n) arise from the law P n θ 0 for a fixed θ 0 ∈ Θ. There exist c 0 > 0 and θ * ,p ∈ R p with θ * ,p ≤ c 0 as well as a sequence 0 < δ n → 0 such that for some β ≥ 1, any c > 0 and any sufficiently large L there are C 1 , C 2 , C 3 , C 4 > 0 with Besides asking for posterior contraction, we also require the prior density to be strongly log-concave and have a Lipschitz gradient.
Assumption B. The prior log-density log π is m π -strongly concave and has Λ π -Lipschitz gradients for some Λ π , m π > 0. The unique maximiser θ π,max ∈ R p satisfies θ π,max ≤ c 0 . Moreover, the fourth moments of the prior are uniformly (in n and p) bounded.
In order to approximate the posterior by a log-concave surrogate measure, the curvature and growth of the log-likelihood function need to be quantified relative to the sample size and the model dimension on a local region close to θ * ,p with high P n θ 0 -probability.
Assumption C. There exist 0 < η ≤ 1, an event E with P n θ 0 (E) ≥ 1 − c ′ e −cnδ 2 n for c, c ′ > 0, and a region B = {θ ∈ R p : θ − θ * ,p ≤ η} such that θ → ℓ n (θ) ∈ C 2 (B), P n θ 0 -almost surely, and such that for some c max ≥ c min > 0, κ 1 , κ 2 , κ 3 ≥ 0 the following holds on E: Note that ℓ n is not restricted outside of B. The assumption η ≤ 1 is natural given the local nature of the assumption, and simplifies some proofs. We conclude with a condition on the magnitudes of p, η as well as a 'curvature' parameter K, which appears in the Lipschitz constantΛ in Theorem 10. The upper and lower bounds on p and η are used, among others, in the proof of the Wasserstein approximation of the posterior.
Remark 9. The lower bound δ n p κ 1 +κ 3 for η can be improved to δ n p κ 3 /2 by an analysis of the MAP estimator, cf. [8,Condition 3.5]. This may be difficult in concrete cases, e.g. in the example of Section 4.3. On the other hand, our lower bound is satisfied in the examples considered here and by [56,8]. Compared to the latter two references, our lower bound on K is typically much smaller and independent of η.

The surrogate posterior
We construct a globally concave surrogate log-likelihood functionl n : R p → R such that ℓ n agrees with ℓ n onB Our construction is similar to Definition 3.5 of [56], but leads generally to a smaller Lipschitz constantΛ. Set for K > 0 and two smooth auxiliary functions: a 'cut-off function' v : R p → [0, 1] and a globally convex function v η : We define now analogously to (1) the 'surrogate' posterior measureΠ(·|Z (n) ) with densitỹ It has the following properties.
Theorem 10. Under Assumption D the following holds on the event E: (ii)l n ism-strongly concave and hasΛ-Lipschitz gradients withΛ = 7K andm = c min np −κ 3 .

Log-concave approximation of the posterior
We show next that the surrogate posterior concentrates around θ * ,p with high probability at the same rate δ n as the true posterior. The result and its proof are of independent interest, since it dispenses with the usual construction of Hellinger tests and relies only on the log-concavity ofΠ(·|Z (n) ).
Proposition 11. Under Assumption D there exist for any c > 0 and any sufficiently large We conclude by showing that the surrogate and true posteriors are exponentially close in Wasserstein distance. The proof generalises the specific argument of Theorem 4.14 in [56] and requires, in particular, no analysis of the MAP estimator.

Polynomial time sampling guarantees
Suppose that the gradient ∇l n can be evaluated at polynomial cost and we are therefore left with quantifying the number of iterates k in (10) to approximate the posterior up to a target precision level. Combining the Wasserstein approximation in Theorem 12 with standard non-asymptotic sampling bounds for strongly log-concave potentials with Lipschitz-gradients, the distance of the law L(θ k ) to the true posterior measure can be quantified in terms of k and a sufficiently small step size γ. Convergence as k → ∞ is only achieved if γ → 0 and n → ∞.
Theorem 13. Set B(γ) = 36γpΛ 2 /m 2 + 12γ 2 pΛ 4 /m 3 and let γ ≤ 2/(m + Λ). Let (θ k ) k≥1 be the Markov chain with iterates (10). Under Assumption D there exists a constant c W ≡ C(c 0 , c max , c min ) such that for all k ≥ 1 on the eventẼ This yields the following result on the computation of posterior functionals by ergodic averages up to a target precision ε after a burn-in period J in .
Theorem 14. Let γ ≤ 2/(m + Λ), consider a precision level ε ≥ 16e −nδ 2 n + 8B(γ) and suppose that the burn-in time satisfies Under Assumption D there exists a constant c F > 0 such that for all Lipschitz functions f : R p → R with f Lip = 1 and all J ≥ 1 on the eventẼ Polynomial time convergence guarantees after J +J in iterations with high probability under P n θ 0 × P are obtained from this when γ −1 , ε −1 , m, η −1 and Λ π exhibit most polynomial growth in p, n. Next, let τ = inf{k ≥ 1 :θ k / ∈B} denote the first time the Markov chain (θ k ) k≥0 leaves from the regionB, where ℓ n andl n coincide according to Theorem 10. We can quantify the probability (under P) to exit before a time J.

Theorem 15. Grant Assumption D and suppose that
Then there exist c 1 , c 2 , c 3 , c 4 > 0 such that on an eventĒ with P n If η 2 m 2 /(γpΛ 2 ) n ρ for ρ > 0 (this holds for the applications in the next section), and given a computational budget of at most J ≍ n ρ ′ , ρ ′ > 0, many steps, we conclude that the Markov chain (ϑ k ) 0≤k≤J , obtained by the vanilla Langevin-MCMC algorithm in (12), will stay within the region of local curvature with high P n θ 0 × P-probability. Combining the last two theorems yields the following result.
Theorem 16. Grant Assumption D and let the conditions in (19) be satisfied. Let J in , ε, c F be as in Theorem 14 and let (ϑ k ) k≥1 be the Markov chain with iterates (12). Then there exist c 1 , c 2 , c 3 , c 4 > 0 such that on an eventĒ with P n In particular, taking f (θ) = θ and assuming that θ * ,p is sufficiently close to the datagenerating truth θ 0 , we obtain the following guarantee on recovering θ 0 by an ergodic average of (ϑ k ) k≥0 . In view of the statistical error it is enough to restrict to a target precision level ε δ Corollary 17. In the setting of Theorem 16 assume

Applications
In this section we verify the assumptions from Section 3.1 for density estimation and for nonparametric regression models with error distributions in general exponential families. For regression, first a general setting is considered, followed by Darcy's problem. Polynomial time sampling guarantees are obtained from the general results in Section 3.4. We focus on the Gaussian prior from (4). As in Section 2, (e k ) k≥1 is an orthonormal basis of L 2 (X ) with respect to a measure ν X on X , Φ(θ) = ∞ k=1 θ k e k for θ ∈ ℓ 2 (N).

Density estimation
Suppose that we observe an i.i.d. sample (X i ) n i=1 from a density p θ relative to ν X . Following [73], who study posterior contraction with different priors, assume where is strongly concave only on bounded subsets in Θ. Implementations of the posterior distribution using MCMC have been discussed in various works [40,41,68,46], but computational guarantees have not been addressed previously. Since constants are not identifiable, we may assume the basis functions e k are centered with respect to ν X . Suitable initialisers with η = p −1/2 can be obtained from [72,70]. Remark 7 applies here as well.
Theorem 18. Suppose the data arise according to the coordinate densities (20). Let Condition 3 be satisfied, but without the design restriction, and assume X e k (x)dν X (x) = 0, k ≥ 1. Then the results of Theorems 4-6 hold true under the same restrictions on γ, ε, J in , J out .

Nonparametric regression
Suppose that we observe independent random vectors (Y i , X i ) n i=1 from a regression model with marginal densities (2) and with for a known forward operator G : Θ → L 2 (X ). This includes the GLMs from Section 2 and non-linear operators G, which appear in the context of non-linear inverse problems [48,31,1]. Posterior sampling guarantees have been obtained by [56,8] for Gaussian measurement errors with the canonical link function for specific operators G, which are globally bounded and Lipschitz. Here we allow for general exponential families and operators G. Let us first translate the assumptions from Section 3.1 into conditions on G. Following ideas from the Bayesian inverse problem literature, posterior contraction follows from establishing posterior contraction around G(θ * ,p ), combined with stability and local Lipschitz properties. The growth bounds in Assumption C correspond to L ∞ (X )-and L 2 (X )-bounds for G on B.
Condition G1. Suppose that θ 0 ∈ h α (N), α > 1/2, and that there exist θ * ,p ∈ R p , The design is bounded and there exists β ≥ 1 such that the following holds for all θ, θ ′ ∈ ℓ 2 (N): . . , 5 such that the following holds for all v ∈ R p with v ≤ 1 and all θ = θ ′ ∈ B: With this we establish Assumption D. It immediately yields the polynomial time sampling guarantees from Section 3.4.
Proposition 19. Suppose the data arise in a nonparametric regression model with coordinate densities (2), b as in (21) and g ∈ C 3 (I) for a forward operator G satisfying Conditions G1 and G2 and such that for all large enough n Then Assumption D holds for

Darcy's problem
Suppose that X is a bounded domain in R d with smooth boundary ∂X . Let ∇u and ∇ · u = d i=1 ∂ i u denote the gradient and divergence operators, respectively. For a conductivity f ∈ C γ (X ), γ ∈ N, consider the divergence form operator For source g 1 ∈ C ∞ (X ) and boundary values g 2 ∈ C ∞ (∂X ) let u ≡ u f be the solution to the boundary value problem For strictly positive f the operator L f is uniformly elliptic and classical solutions u f ∈ C 2 (X ) exist by standard elliptic PDE theory (e.g., Theorem 6.14 in [29]). Details on the analytical properties of the PDE (26) relevant to our analysis are collected in Section 6.1.3.
The function u f typically represents the density of some quantity within the region X and the PDE describes diffusion within X at equilibrium [21]. Determining the unknown conductivity f from noisy observations of u f is a popular example in the inverse problem literature, called Darcy's problem, see [14,9,55] and the references therein. For a fixed and consider the measurement model in Section 4.2 with G(θ) = u f θ for known g 1 and g 2 . For Gaussian measurement errors, posterior contraction in this model for different Gaussian process priors is studied by [31], while [54] show that no Bernstein-von Mises theorem holds.
In the following, in order to use elliptic PDE-regularity theory in L 2 , we choose for (e k ) k≥1 the eigenbasis of the negative Dirichlet Laplacian −∆ = −∇ · ∇ with associated eigenvalues (λ k ) k≥1 . This leads to a rather large regularity assumption on α and can possibly be relaxed by using Schauder estimates instead. Moreover, we restrict to d ≤ 3 to simplify the proofs using Sobolev embeddings.
The design is bounded and the solutions u f θ satisfy for all c > 0, some µ, c ′ > 0, possibly depending on c and Condition (28) ensures injectivity of the forward operator, which is necessary to show (22). It holds for a large class of models f , g 1 , g 2 (see [53, Proposition 2.1.5]), for instance, as soon as g 1 > 0 on X .
Theorem 21. Suppose the data arise from the nonparametric regression model with coordinate densities (2), b as in (21) and g ∈ C 3 (I) for the forward operator G(θ) = u f θ . Assume that Condition 20 is satisfied. Then the results of Theorem 4 hold for Moreover, the results of Theorems 5 and 6 hold for

Proofs for Section 2: GLMs
The specific results for GLMs follow from applying the general statements in Section 3 to the regression model in Section 4.
By modifying the final constant c 2 in the statements of Theorems 4, 5, 6 it is enough to consider any sufficiently large n. Observe first the following lemma.

Proofs for Section 3.3: The surrogate posterior
Proof of Theorem 10. Part (i) is true by the construction ofl n in (17) and the condition on the initialiser in Assumption D. The supplement follows immediately from part (ii).
By the triangle inequality sup θ∈B |ℓ n (θ) − ℓ n (θ init )| ≤ 2c max n(δ n p κ 1 η + p κ 2 η 2 /2). Combining the last two displays and noting thatv vanishes outside of B yields by the chain rule for θ ∈ R p using η ≥ δ n p κ 1 +κ 3 and with K from Assumption D. Consequently, Together with (29) and K/6 ≥ c min n we thus obtain the wanted curvature bound ofl n : At last, the gradient-Lipschitz bound follows for θ = θ ′ ∈ R p from Proof of Proposition 11. Let c > 0, L ≥ 1. Define two balls with centres θ * ,p Let D c denote the event in (15) and consider alsoD = {Π(U |Z (n) ) ≥ 1 − e −cnδ 2 n /4}. In view of Assumptions A and C, by taking L large enough, we may restrict ourselves in the proof to the high probability eventẼ = E ∩ D ∩D.
We first study the surrogate posterior measure of the setŨ . For large enough n (and by increasing the final constant c 2 in the statement), Assumption D and L ≥ 1 provide us with the relation max(δ n , L 1/β δ 1/β n ) ≤ L 1/βδ n,p ≤ (log n) −1 η ≤ 3η/8.
On the event E, this means by Theorem 10(i) ℓ n (θ) =l n (θ) for any θ from the setŨ .

Exit time of the surrogate Markov chain
In this section we prove Theorem 15. The main idea is to relate the discrete time Markov chain (θ k ) k≥0 to a continuous time Langevin diffusion process with gradient potential ∇π(·|Z (n) ). This reduces the problem of computing the exit time of (θ k ) k≥0 fromB to the corresponding exit time of the diffusion process. This is achieved by comparing to a suitable Ornstein-Uhlenbeck process, whose exit time can be bounded analytically.
Proof of Theorem 15. For the proof we may restrict to the event E. By increasing the final constant c 1 in the statement, it is enough to consider any sufficiently large n. By extending the probability space carrying the Markov chain we can further assume without loss of generality that it also supports a p-dimensional Brownian motion (W t ) t≥0 with respect to a filtration (F t ) t≥0 satisfying the usual conditions (see [37, Section 5.2.A]). For fixed data Z (n) denote by f (θ) = logπ(·|Z (n) ) the log-density of the surrogate posterior measure. With this associate two p-dimensional stochastic differential equations for t ≥ 0, both starting at L 0 =L 0 = θ init . Since f is strongly m-concave and has Λ-Lipschitz gradients on E, cf. the supplement in Theorem 10, classical results for stochastic differential equations (e.g., [37, Theorem 5.2.9]) verify that (38) has a unique strong solution (L t ) t≥0 with respect to the filtration (F t ) t≥0 . The process (L t ) t≥0 is simply the continuous time interpolation of (θ k ) k≥0 in the sense that L(L γ , . . . ,L Jγ ) = L(ϑ 1 , . . . , ϑ J ).
Lemma 24. In the setting of Theorem 15 we have for some c, c ′ > 0, all large enough n and x m/p log n P sup .
Proof. Recall that p-dimensional Brownian motion for p ≥ 2 does not hit points Palmost surely [36,Theorem 18.6]. By Girsanov's theorem this also holds for the diffusion process L on any finite time interval. We can therefore apply Itô's formula to the function θ → θ − θ * ,p (which is only non-smooth at the point θ * ,p ) such that Let (V t ) t≥0 be a p-dimensional Ornstein-Uhlenbeck process satisfying By a comparison argument for scalar Itô processes [35] we get L t − θ * ,p ≤ V t − θ * ,p P-almost surely for all t ≥ 0.
The process (V t ) t≥0 has the explicit solution Assumption C, the lower bound on η from Assumption D as well as m ≥ c min np −κ 3 imply ∇ℓ n (θ * ,p ) ≤ (c max /c min )(log n) −1 ηm. Together with (19) this means for large enough n, ∇f (θ * ,p ) ≤ ∇ℓ n (θ * ,p ) + ∇ log π(θ * ,p ) ≤ ηm/8. Since also θ init − θ * ,p ≤ η/8 by Assumption D and using that ac + a(1 − c) = a for a, c ∈ R we have With this conclude from (39) Let (W i,t ) t≥0 denote the coordinate processes of (W t ) t≥0 . Using x ≤ p 1/2 max 1≤i≤p |x i | for x ∈ R p together with a union bound the last probability is upper bounded by We can now apply a well-known result on the exit time of a scalar Brownian motion from an interval, cf. [37, Remark 2.8.3], which gives Obtain the claim from x m/p log n. Proof. We begin by applying Lemma 22 of [18] (their equation (51)) to the strongly convex function U = −f and κ = (2mΛ)/(m + Λ), ε = κ/4 such that for all k ≥ 1 Since L 0 =L 0 , this yields inductively Now, ∇f is Λ-Lipschitz, and so using γ ≤ m/( √ 54Λ 2 ) ≤ Λ −1 , κ ≥ m and recalling that L solves (38), we have with V = sup 0≤t≤Jγ W t − W ⌊t/γ⌋γ where we have used again the inequality x ≤ p 1/2 max 1≤i≤p |x i | for x ∈ R p and a union bound together with To conclude, use (W i,t − W i,⌊t⌋ ) k−1≤t≤k d = (W 1,t ) 0≤t≤1 and apply (40), noting γ m/Λ 2 and η m/p log n.

Proofs for Section 3.4: Polynomial time sampling guarantees
We prove now the remaining results in Section 3.4. Observe first the following crude upper bound on the distance between the initialiser and the mode of the surrogate posterior.
Proof of Theorem 13. Apply Theorem 5 of [18] (in the form stated as Proposition A.4 in [56]) to the strongly log-concave measure µ =Π(·|Z (n) ) from Theorem 10 with unique maximiser θ max such that The claim follows from the triangle inequality for the Wasserstein distance, Theorem 12 and Lemma 26.
Proof of Theorem 16. If A is the event whose probability we want to upper bound, then P(A) ≤ P(A, τ > J + J in ) + P(τ ≤ J + J in ). Sinceθ k = ϑ k for all k ≤ J + J in < τ , the result follows immediately from Theorems 14 and 15.
We preceed the proof of the final result by the following Lemma on contraction of the posterior mean around the ground truth, which adapts arguments from [49] to our setting. Under Assumptions A and B, there exist c, c ′ > 0 such that for any large enough L Proof. Recall the set U = θ ∈ R p : θ − θ * ,p ≤ L 1/β δ 1/β n from the proof of Proposition 11 and the high probability eventẼ defined there such that, onẼ, Π(U c |Z (n) ) ≤ e −cnδ 2 n for any c > 0 and sufficiently large L. The Jensen inequality shows Arguing as in (37) we thus find that with high probability the first term in the last line is smaller than e −nδ 2 n . Using the bias condition θ 0 − θ * ,p ≤ c 0 δ 1/β n , we obtain for the last display with high probability the upper bound e −nδ 2 n + (L 1/β + c 0 )δ 1/β n . Modifying the constant L yields the claim.
Proof of Corollary 17. For large enough c > 0 we have by Lemma 27 with sufficiently high P n θ 0 -probability Θ θdΠ(θ|Z (n) )−θ 0 ≤ cδ 1/β n . Hence, with the coordinate functions using in the last line the inequality x ≤ √ p max i=1,...,p |x i |, x ∈ R p , and a union bound. Conclude now by Theorem 16 for the 1-Lipschitz maps f i .

Sufficient moment conditions for constructing the surrogate likelihood
In this section we verify the local growth conditions on the log-likelihood function from Assumption C under moment conditions. We use the notations from Section 3.
Theorem 28. Let 0 < η ≤ 1, κ 1 , κ 2 , κ 3 , κ 4 ≥ 0 and B = {θ ∈ R p : θ − θ * ,p ≤ η} and suppose that θ → ℓ n (θ) ∈ C 2 (B), P n θ 0 -almost surely. Then Assumption C holds for some c min , c max > 0, if there exist C > 0, C 1 ≥ C 2 > 0 such that for all v ∈ R p with v ≤ 1 and all i = 1, . . . , n the following conditions hold: The proof of this theorem is based on the classical Bernstein inequality (see, e.g., Proposition 3.1.8 in [30]) and a chaining argument for empirical processes with mixed tails, cf. Theorem 3.5 of [15]. In the proof we denote for a metric space T and a metric d by N (T, d, ε) the minimal number of closed d-balls of radius ε necessary to cover T .
Lemma 29 (Bernstein's inequality). Let X 1 , . . . , X n be real-valued centred and independent random variables such that E θ 0 |X i | q ≤ (q!/2)σ 2 c q−2 for some σ > 0, c > 0 and all 1 ≤ i ≤ n, q ≥ 2. Then Lemma 30. Let U be a measurable subset of R p with diameter sup θ,θ ′ ∈U θ−θ ′ = D > 0. Let h θ : Z → R, θ ∈ U , be a family of functions such that for some σ p , c p > 0, all q ≥ 2 and all i = 1, . . . , n Consider the empirical process . Then there exists a universal constant M ≥ 1 such that for all t ≥ 1, t ′ ≥ 0 Proof. Write Z n (θ) = n i=1 h θ,i with independent and centred random variables The moment assumptions in (42) and (43) hold for the h θ,i with constants 3σ p and 3c p . Fix any θ, θ ′ ∈ U . Then the Bernstein inequality in Lemma 29 gives for t ≥ 0 The last line implies that Z n has a mixed tail with respect to the metrics [15,Equation (3.8)]. Since the set U has diameter sup θ,θ ′ ∈U d 1 (θ, θ ′ ) = 3c p D with respect to d 1 and diameter 3c p D √ 2n with respect to d 2 , using Proposition 4.3.34 and equation (4.171) in [30] yields for the metric entropy integrals with respect to d 1 and d 2 the upper bounds and in the same way Together with the mixed tail property in (45) infer from Theorem 3.5 of [15] the existence of an absolute constant M ≥ 1 such that for any t ≥ 1 The result follows from the triangle inequality and from applying (44) to t = t ′ .
With this let us prove the main result of this section.
Proof of Theorem 28. For constants C 3 , C 4 > 0, to be determined lateron, set τ 1 = C 3 nδ n p κ 1 , τ 2 = C 4 np −κ 3 and define b(θ) = ∇ℓ n (θ) − E n θ 0 ∇ℓ n (θ), Σ(θ) = ∇ 2 ℓ n (θ) − E n θ 0 ∇ 2 ℓ n (θ). We will prove the claim for the event E = E 1 ∩ E 2 , where Recall the min-max characterisation of the eigenvalues of a symmetric matrix A ∈ R p×p such that With this conclude using the mean boundedness assumptions in part (ii) of the statement of the theorem (with q = 2) for θ ∈ B that E n θ 0 ∇ 2 ℓ n (θ) op ≤ C 1 np κ 2 , and therefore that we have on E In the same way, ∇ℓ n (θ * ,p ) ≤ (C 3 + C 1 )nδ n p κ 1 on E, proving Assumption C(i) for c max = max(C 3 , C 4 ) + C 1 , while the mean curvature lower bound in part (iii) yields by Weyl's inequality for θ ∈ B From this obtain Assumption C(ii) for c min = C 2 − C 4 , as long as C 4 < C 2 .
We are therefore left with showing P n θ 0 (E c ) ≤ C ′ e −Cnδ 2 n for suitable C 3 , C 4 . By adjusting C ′ it suffices to prove this for n large enough. We will use a contraction argument for quadratic forms, commonly used in random matrix theory. For 0 < δ ≤ 1 and N = N ({v ∈ R p : v ≤ 1, · , δ) let v 1 , . . . , v N be the centres of a minimal open cover for the Euclidean unit ball with radius δ. This implies for v ∈ R p with v ≤ 1 For the same v i we also get |v ⊤ b(θ * ,p )| ≤ |v ⊤ i b(θ * ,p )| + δ b(θ * ,p ) . Taking δ = 1/4 and maximising over v in the unit ball and over i then gives By applying union bounds this means for j = 1, 2  [30] and the growth conditions in part (i) yield N ≤ e p log 12 ≤ e 3Cnδ 2 n . To prove the wanted high probability bounds we are left with establishing that the probabilities in the last display are each smaller than C ′ e −4Cnδ 2 n for some C ′ > 0. For this we apply the two lemmas above to the empirical processes b(θ * ,p ) and Σ(θ), uniformly for The mean boundedness conditions in (ii) show E θ 0 |h θ (Z i )| q ≤ (q!/2)σ 2 c q−2 for σ = C 1 p κ 1 , c = C 1 p κ 2 and all q ≥ 2. We can therefore apply Lemma 29 to t = 4Cnδ 2 n . The growth conditions in part (i) imply δ n p κ 2 ≤ p −κ 3 ≤ p κ 1 . This means, if we set Using again the conditions in part (ii) verifies (42) and (43) If M is the constant from the statement of Lemma 30 and Taking n large enough, the growth conditions in part (i) provide us for any c > 0 with the upper bound max(δ n p κ 2 , ηδ n p κ 4 , δ 2 n p κ 4 ) ≤ cp −κ 3 . This implies that the expression in the last display is upper bounded by τ 2 /4 = (C 4 /4)np −κ 3 for a suitable C 4 < C 2 . Lemma 30 now implies the wanted upper bound P n θ 0 (sup θ∈B |v ⊤ Σ(θ)v| > τ 2 /4) ≤ 3e −4Cnδ 2 n . This finishes the proof.

Appendix
6.1 Proofs for specific models in Section 4

Density estimation
The density estimation model fits into the setting in Section 3 with Z (n) = (X i ) n i=1 , Z = X , ν = ν X , δ n = n −α/(2α+1) . By modifying the final constant c 2 in the statements of Theorems 4, 5, 6 it is enough to consider any sufficiently large n. We begin by checking the assumptions in Section 3.1 for the density estimation model. Proof. Let us make a few preliminary observations, which will be used in the proof without further mention. Since the basis functions e k are bounded, we have Φ(θ) L ∞ θ ℓ 1 for θ ∈ ℓ 1 (N). Fixing a radius r > 0 therefore yields the existence of a constant The operators A : L ∞ (X ) → R, A(u) = log X e u(x) dν X (x), are Fréchet differentiable with derivatives obtained according to the chain rule for u, h ∈ L ∞ (X ) by In particular, if θ, θ ′ ∈ ℓ 1 (N), then Fix now θ, θ ′ with θ ℓ 1 , θ ′ ℓ 1 ≤ r. Using that X Φ(θ ′ )dν X = 0 by the centring of the e k , we have by (46) and the Cauchy-Schwarz inequality and therefore On the other hand, it follows from (46) and (47) that A(Φ(·)) is uniformly Lipschitz on the set {θ : θ ℓ 1 ≤ r}, because We write Φ x θ = Φ(θ)(x) and denote by X a generic copy of Z i = X i . Observe for v ∈ R p the identities Note that v ⊤ ∇ 2 ℓ(θ)v is not random. After these preparations let us verify Assumptions A, C and D. For this it suffices to check the conditions of Theorems 40 and 28 for suitable κ 1 , . . . , κ 4 . Theorem 40(i): Approximation. Consider r > 0 and θ ∈ B n,r . Since α > 1/2, there exists r ′ ≡ r ′ (r) with It follows for θ and θ 0 ∈ h α (N) The first part of inequality (74) follows from (49), (8) such that For the second part note that the log-likelihood function θ → ℓ(θ) = log p θ is uniformly bounded on B n,r such that for q ≥ 2 by (50) Theorem 40(ii): Hellinger distance. Let r > 0, θ, θ ′ ∈ ℓ 2 (N) with θ α , θ ′ α ≤ r and set u = (Φ X θ + Φ X θ ′ )/2. Arguing as in the proof of the corresponding statement in Proposition 19 we get h 2 (θ, θ ′ ) = 2 − 2e −x where Upper and lower bounding this non-random quantity gives by (49) The result follows from (58). Theorem 28(ii): Local mean boundedness. A key step is to note that there exists r ′ > 0 with B ⊂ θ ∈ ℓ 1 (N) : θ ℓ 1 ≤ r ′ , because for θ ∈ B θ ℓ 1 ≤ θ − θ * ,p ℓ 1 + θ * ,p ℓ 1 p 1/2 θ − θ * ,p + θ * ,p α 1.
By the help of this proposition we can now obtain the three theorems in Section 2.3 from exactly the same proof as in Section 5.1, with the same choices for γ, ε, J in and J out .

Nonparametric regression
Proof of Proposition 19. Let us make a few preliminary observations used in the proof without further mention. Recall b(θ) = (A ′ ) −1 • g −1 • G(θ). By Assumptions G1(ii) and G2(ii), the range of the map (θ, x) → G(θ)(x), evaluated for θ in the convex hull R = conv(B ∪ {θ 0 }) and x ∈ X , is a bounded subset of R. Since A is smooth and convex, and g ∈ C 3 (I) is invertible, this means there exists a constant M > 0 such that We write b x θ = b(θ)(x) and denote by (Y, X) a generic copy of (Y i , X i ). Frequently, we will use that the bounded design implies for θ, θ ′ ∈ ℓ 2 (N) The assumption that θ → G(θ)(x) ∈ C 2 (B) at every x ∈ X implies θ → b x θ ∈ C 2 (B). The properties of G in Assumption G1 all transfer to the map b immediately, as do the statements on G and its first derivative in Assumption G2. Regarding second derivatives we find for v ∈ R p , v = 1, At last, observe for v ∈ R p the identities With these preparations let us to verify Assumptions D for some κ 1 , . . . , κ 4 . For this it suffices to check the conditions of Theorems 40 and 28. Theorem 40(i): Approximation. Consider r > 0 and θ ∈ B n,r . The first part of inequality (74) follows from a Taylor expansion of A at b X θ 0 such that by (54) and For the part inequality let λ ∈ R be sufficiently small such that for some c > 0 By G2, (55), the Cauchy-Schwarz inequality and the last line is up to a constant lower bounded by Obtain the claim with κ 3 = k 5 by the assumption that ηp max(2k 3 ,k 4 ) log n ≤ p −k 5 . Theorem 28(i): Growth conditions. These follow immediately from the conditions in the proposition for the obtained κ i , noting that η ≥ δ n , k 4 ≤ k 2 , k 3 ≤ k 1 such that C max(δ n p κ 2 , ηδ n p κ 4 , δ 2 n p κ 4 ) log n = δ n max(p k 1 , p 2k 3 , p k 4 , ηp 3k 1 , ηp k 2 , δ n p 3k 1 , δ n p k 2 ) log n = δ n max(p max(k 1 ,2k 3 ,k 4 ) , ηp max(3k 1 ,k 2 ) ) log n ≤ p −k 5 .
Assumption D: The form of K follows by plug-in of κ 2 .

Darcy's problem
We will recall first some relevant analytical properties of the PDE (26), give a stability estimate for the forward operator G based on the condition (28), analyse further analytical properties of G and conclude with the proof of Theorem 21.
Some PDE facts Let us state a few well-known facts from the theory of elliptic PDEs. Details can be found in [67,Section 5A]. For multi-indeces i = (i 1 , . . . , i d ) let D i be the weak partial derivative operators. Denote the classical L 2 (X )-Sobolev spaces of integer order s ≥ 0 by They satisfy a Sobolev embedding [67,Proposition 4.3], Let H s 0 (X ) be the subspace of functions in H s (X ) that vanish on the boundary of X in the trace sense. Their topological dual spaces are denoted by (H s 0 (X )) * . For f ∈ C 1 (X ) the divergence form operator L f takes functions in H 2 0 (X ) to L 2 (X ). If f is strictly positive on X , then it has (e.g., by [21,Theorem 6.3.4]) a linear, continuous inverse operator L −1 f : L 2 (X ) → H 2 0 (X ). In particular, we have Another scale of Sobolev spacesH s (X ) is induced by the eigensystem (λ k , e k ) n k=1 of the negative Dirichlet Laplacian, wherẽ which is equipped with the inner product Due to the presence of a boundary they generally differ from the Sobolev spaces H s (X ), but it can be shown that and the · H s -and · Hs -norms are equivalent on H s (X ). By Weyl's law the eigenvalues satisfy for constants 0 < c 1 < c 2 < ∞ and hence the map Φ : h s/d (N) →H s (X ), Φ(θ) = ∞ k=1 θ k e k is an isomorphism with It follows from the last three displays and the Sobolev embedding (59) that for γ > k + d/2, k ∈ N ∪ {0}, In particular, if θ γ/d ≤ r, then we have for a constant C r > 0 We require the following quantitative elliptic regularity estimates with explicit constants depending on the conductivity.

Lemma 32.
We have for f ∈ C γ+1 (X ), γ ≥ 0, and w ∈ H γ+2 (X ) Proof. It suffices to note that Then there exists a constant C ≡ C(f min , c) such that the following statements hold: Proof. Parts (i) and (ii) follow from [55,Lemmas 21 and 23]. For (iii) use duality to find for z ∈ H 1 0 (X ) concluding by the Poincaré inequality. Applying this to z = L −1 Since the partial derivative operators are bounded operators from H 1 (X ) to L 2 (X ), the result follows by duality, the divergence theorem and the Cauchy-Schwarz inequality such that Proof. If u f = g 2 = 0 on ∂X, then [55,Lemma 23] shows the first inequality for a constant C ≡ C(γ, f min , X , g 1 ) and the second one follows from the Sobolev embedding H γ (X ) ⊂ C k (X ). For general g 2 ∈ C ∞ (∂X ) we can assume without loss of generality that it extends to a function in C ∞ (X ) (e.g., by taking g 2 as the solution of the PDE (26) for the standard Laplacian with f ≡ 1, g 1 = 0, which is smooth, cf. [29,Theorem 8.14]) and note thatū f = u f −g 2 solves the PDE (26) with right hand side g 1 = f −L f g 2 andū f = 0 on ∂X . Then what has been shown so far applies toū f and we obtain the second inequality (and thus also the first) with A stability estimate Then there exists a constant C ≡ C(γ, f min , X , g 1 , g 2 , c) > 0 such that Proof. For h ∈ C ∞ c (X ) the claim in (i) follows from [54, Lemma 1] (it is easy to check that the requirement f ∈ C ∞ (X ) in the proof can be reduced to f ∈ C 1 (X )), and extends by taking limits to h ∈ H 1 0 (X ). For (ii) the proof of [54, Proposition 3] applies: (65) below) and hence by (i) and Lemma 32 Lemma 36. Let θ, θ ′ ∈ h α (N), dα > 1 + d/2, with θ α , θ ′ α ≤ c for some c > 0, and suppose that (64) holds for f = f θ . Then there exists a constant C ≡ C(α, f min , X , g 1 , g 2 , c) > 0 such that Proof. Let γ = dα such that β = (γ + 1)/(γ − 1). Use first x ≤ e x − 1 for x ≥ 0 and (62) to the extent that Apply Lemma 35(ii) to the last term. To conclude observe for Analytical properties of the forward map Lemma 37. Let θ, θ ′ ∈ h α (N), dα > 1 + d/2, with θ α , θ ′ α ≤ c for some c > 0. Then there exists a constant C ≡ C(α, c) such that Lemma 34, and This allows for applying L −1 f θ ′ and we get Lemma 33 combined with (63) yields By duality, the divergence theorem and writing G(θ) = u f θ the last term equals The result follows then from Lemma 34 and (62) such that Proof. Let us write G(f ) = u f such that G(θ) = G(f θ ). We will establish for and h, h ′ ∈ H α (X ) as h H α → 0 and h ′ H α → 0, respectively, that with continuous linear operators A 1 (f ) : H α (X ) → C(X ), A 2 (f ) : H α (X ) × H α (X ) → C(X ) given by This implies that G is two-times continuously Fréchet differentiable with derivatives the claim follows from the chain rule and from replacing G(f θ ) = u f θ . Consider now h, h ′ ∈ H α (X ) with sufficiently small · H α -norms such that f + h, f + h ′ are strictly positive on X and G(f + h), G(f + h ′ ), G(f ) are well-defined with values in H 2 (X ). Using (65) twice we get Since G(f + h) = L −1 f +h g 1 , applying several times Lemmas 33(i) and G2 and suppressing constants depending on f C 1 , we get implying (66) by (70) and the Sobolev embedding H 2 (X ) ⊂ L ∞ (X ) for d ≤ 3. Next, we have

With this write
Arguing as after (70) gives and the same upper bound applies to R 3 L ∞ . At last, for w ∈ L 2 (X ) observe that and so (67) follows from arguing as in the last display, such that

Proof of Theorem 21
We first verify the conditions of Proposition 19 in the following lemma.
Proof. Since dα ≥ 7 > 1 + d/2, Assumption G1(ii) can be verified from the stability and Lipschitz estimates in Lemmas 36 and 37 for the stated β. The Lipschitz estimate and (8) also yield Assumption G1(i). We are therefore left with checking Assumption G2. Let θ ∈ B and v ∈ R p , v ≤ 1. Then θ * ,p α ≤ θ 0 α ≤ c 0 for α ≥ 7/d gives which in view of (62), (63) and In particular, by Lemma 34 for C ′ > 0 These properties will be used tacitly in the following proof. As before we will suppress constants not depending on n, p. The gradient and Hessian of G were computed in Proposition 38. Assumption G2(i): Use (72) and 37. Assumption G2(ii): The required differentiability follows from Proposition 38. For the sup-norm bounds observe first by Lemma 33(i) and similarly such that Lemma 33(i) implies for w ∈ L 2 (X ), w ′ ∈ H 2 (X ) Then, e Φ(θ) − e Φ(θ ′ ) , and so the terms in the last display are upper bounded up to constants by p 3/d θ − θ ′ w L 2 , p 6/d θ − θ ′ w H 2 , p 4/d θ − θ ′ and p 4/d θ − θ ′ , respectively. Combining these estimates with Lemmas 32(ii), 33(i) and with the Lipschitz bound from Lemma 37 we obtain In all, Assumption G2(i) holds with k 1 = 1/d, k 2 = 7/d.
Assumption G2(iii): Use Lemma 33(iii) to the extent that as well as From this and · L 2 ≤ · H 1 obtain the result with k 3 = 0, k 4 = 2/d. Assumption G2(iv): An interpolation inequality for Sobolev spaces (see e.g., [ Applying this to w = L −1 f θ L f θ,v u f θ and observing the inequalities Recall the stability estimate from Lemma 35(ii), which yields for h = e Φ(θ) Φ(v) ∈ H 1 0 (X ) (here we use that Φ(θ) ∈ H 1 0 (X )) while Lemma 34 and (62) provide us with the upper bound The last three displays yield the wanted lower bound with k 5 = 6/d.

This gives B(γ)
γp 1+16/d + γ 2 p 1+26/d n and the results in Theorem 4 follow in the present model from Theorems 13 and 14.

Posterior contraction with rescaled Gaussian priors
In this section we formulate a general contraction result for the posterior Π(·|Z (n) ) from Section 3 around a sufficiently regular ground truth θ 0 ∈ h α (N) for the Gaussian prior in (4), achieving the high probability bounds in Assumption A. The proof follows closely [30,Theorem 7.3.1] and [31,Theorem 13], using Bernstein-type moment conditions and a stability condition for the Hellinger distance. We include a proof for the convenience of the reader. In the following, we use the notation of Section 3 and define for θ, θ ′ ∈ Θ the squared Hellinger distance as For a definition of the metric entropy see Section 5.5.