Introduction
Discrepancy-based ABC

Concentration and robustness ofdiscrepancy-based ABC
Pierre Alquier

Séminaire Parisien de Statistique
Institut Henri Poincaré
14 Novembre 2022

Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Co-authors and paper
S. Legramanti, D. Durante & P. Alquier (2022). Concentration and robustness ofdiscrepancy–based ABC via Rademacher complexity. Preprint arXiv :2206.06991.

Sirio Legramanti(University of Bergamo)

Pierre Alquier, RIKEN AIP

Daniele Durante(Bocconi University, Milan)

Discrepancy-based ABC

IntroductionDiscrepancy-based ABC

Contents
1Introduction
Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

2Discrepancy-based ABC
Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

Estimators, randomized estimators and Bayes ruleY1:n = Y1 , . . . , Yn i.i.d from µ∗ ,model : (µθ , θ ∈ Θ),
estimator : θ̂ = θ̂(Y1:n ),randomized estimator : ρ̂(·) = ρ̂(Y1:n )(·) probability
measure on Θ.
Examples of randomized estimators :posterior : ρ̂(θ) = π(θ|Y1:n ) ∝ L(θ; Y1:n )π(θ),| {z }|{z}likelihood

prior

fractional/tempered posterior : ρ̂(θ) ∝ [L(θ; Y1:n )]α π(θ),
Gibbs estimator : ρ̂(θ) ∝ exp[−η R(θ; Y1:n )]π(θ).
| {z }
loss

Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABCRandomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

Evaluating randomized estimators
Assume in this slide that µ∗ = µθ0 : “the truth is in the model”.
Statistical performance of an estimator :consistency : d(θ̂, θ0 ) −−−→ 0 ( in proba., a.s., ...) ?
n→∞rate of convergence : EY1:n [d(θ̂, θ0 )] ≤ rn −−−→ 0 ?
n→∞...
For a randomized estimator :contraction rate :Pθ∼ρ̂ [d(θ, θ0 ) ≥ rn ] −−−→ 0 ( in proba., a.s., ...) ?
n→∞hi
average risk : EY1:n Eθ∼ρ̂ [d(θ, θ0 )] ≤ rn ?
...
Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

Approximate Bayesian InferenceWell-known conditions to prove contraction of theposterior,
tools from ML for randomized estimators : PAC-Bayesbounds.
Given a “non-exact” algorithm targetting ρ̂ instead ofπ(·|Y1:n ) : variational approximations, ABC, etc., we canquantify how well ρ̂ approximates π(·|Y1:n ) ?
study ρ̂ as a randomized estimator and study its
contraction/convergence.

Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

Contents
1

Introduction
Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

2Discrepancy-based ABC
Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

Reminder on ABC
Approximate Bayesian Computation (ABC)
INPUT : sample Y1:n = (Y1 , . . . , Yn ), model (µθ , θ ∈ Θ), priorπ, statistic S, metric δ and threshold ϵ.
(i) sample θ ∼ π,(ii) sample Z1:n = (Z1 , . . . , Zn ) i.i.d. from µθ :if δ(S(Y1:n ), S(Z1:n )) ≤ ϵ return θ,else goto (i).

OUTPUT : ϑ ∼ ρ̂.
discrete sample space, if S =identity and ϵ = 0, ABC isactually exact : ρ̂(·) = π(·|Y1:n ).
general case : ABC not exact, we can ask two questions :12is ρ̂(·) a good approximation of π(·|Y1:n ) ?
is ρ̂ a good randomized estimator ?
Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

Reminder on IPM
Integral Probability Metrics (IPM)
Let F be a set of real-valued, measurable functions and put
dF (µ, ν) = sup EX ∼µ [f (X )] − EX ∼ν [f (X )] .
f ∈FMüller, A. (1997). Integral probability metrics and their generating classes of functions. Applied
Probability.

In general, only a semimetric. However, in many cases, it isactually a metric : dF (µ, ν) = 0 ⇒ µ = ν. Examples :total variation : F = {1A , A measurable},
Kolmogorov : F = {1(−∞,x] , x ∈ R},
Wasserstein : F = set of 1-Lipschitz functions,
Dudley...
Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

Example : Maximum Mean Discrepancy (MMD)
RKHS (H, ⟨·, ·⟩H ) with kernel k(x, y ) = ⟨ϕ(x), ϕ(y )⟩H .
If ∥ϕ(x)∥H = k(x, x) ≤ 1 then EX ∼µ [ϕ(X )] is well-defined .
The map µ 7→ EX ∼µ [ϕ(X )] is one-to-one if k is characteristic.
Gaussian kernel k(x, y ) = exp(−∥x − y ∥2 /γ 2 ) satisfies theseassumption.

F = {f ∈ H : ∥f ∥H ≤ 1}.
dF (µ, ν) = sup EX ∼µ [f (X )] − EX ∼ν [f (X )]f ∈F= EX ∼µ [ϕ(X )] − EX ∼ν [ϕ(X )]Pierre Alquier, RIKEN AIP

Discrepancy-based ABCH.

Introduction
Discrepancy-based ABC

Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

IPM and statistical estimation
We define the “empirical probability distribution”
n1Xµ̂Y1:n :=δY .
n i=1 i
Minimum distance estimatorθ̂ := arg min dF (µθ , µ̂Y1:n ).
θ∈ΘTheorem
If dF is the MMD for a bounded & characteristic kernel,
2
E [dF (µθ̂ , µ∗ )] ≤ inf dF (µθ , µ∗ ) + √ .
θ∈ΘnPierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

Robust estimation with MMD
2
E [dF (µθ̂ , µ∗ )] ≤ inf dF (µθ , µ∗ ) + √ .
θ∈Θnwell-specified case, µ∗ = µθ0 ,√E [dF (µθ̂ , µθ0 )] ≤ 2/ n.
Huber contamination model µ∗ = (1 − ε)µθ0 + εν,dF (µθ0 , µ∗ ) = sup EX ∼µθ0 f (X ) − (1 − ε)EX ∼µθ0 f (X ) − εEX ∼ν f (X )f ∈F= ε sup EX ∼µθ0 f (X ) − EX ∼ν f (X ) ≤ 2εf ∈F√
E [dF (µθ̂ , µθ0 )] ≤ 4ε + 2/ n.
Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

MDE and robustness : toy experiment
Model : N (θ, 1), X1 , . . . , Xn i.i.d N (θ0 , 1), n = 100 and werepeat the exp. 200 times. Kernel k(x, y ) = exp(−|x − y |).

mean abs. error

θ̂MLE θ̂MMDk θ̂KS
0.081 0.094 0.088

Now, ε = 2% of the observations drawn from a Cauchy.
mean abs. error

0.276 0.095 0.088

Now, ε = 1% are replaced by 1, 000.
mean abs. error

Pierre Alquier, RIKEN AIP

10.008 0.088 0.082

Discrepancy-based ABCIntroduction
Discrepancy-based ABC

Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

References on minimum MMD estimation
Dziugaite, G. K., Roy, D. M., & Ghahramani, Z. (2015). Training generative neural networks via
maximum mean discrepancy optimization. UAI 2015.

Briol, F. X., Barp, A., Duncan, A. B., & Girolami, M. (2019). Statistical Inference for Generative
Models with Maximum Mean Discrepancy. Preprint arXiv.

Chérief-Abdellatif, B.-E. and Alquier, P. (2022). Finite Sample Properties of Parametric MMD
Estimation : Robustness to Misspecification and Dependence. Bernoulli.

Alquier, P., Chérief-Abdellatif, B.-E., Derumigny, A. and Fermanian, J.-D. Estimation of copulas
via Maximum Mean Discrepancy. JASA (to appear).

Alquier, P. and Gerber, M. (2020). Universal Robust Regression via Maximum Mean Discrepancy.
Preprint arXiv.

Wolfer, G. and Alquier, P. Variance-Aware Estimation of Kernel Mean Embedding. Preprint
arXiv :2210.06672.
Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Contents
1Introduction
Randomized estimators and Bayes rule
Approximate Bayesian Computation (ABC)
Integral Probability Metric (IPM)

2Discrepancy-based ABC
Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Discrepancy-based ABC
Approximate Bayesian Computation (ABC)
INPUT : sample Y1:n , model (µθ , θ ∈ Θ), prior π, IPM dF andthreshold ϵ.
(i) sample θ ∼ π,(ii) sample Z1:n i.i.d. from µθ :if dF (µ̂Y1:n , µ̂Z1:n ) ≤ ϵ return θ,else goto (i).

OUTPUT : ϑ ∼ ρ̂ϵ .
Rermark : when dF is the MMD with kernel k,XXX
dF (µ̂Y1:n , µ̂Z1:n ) =k(Yi , Yj ) − 2k(Yi , Zj ) +k(Zi , Zj ).
i,jPierre Alquier, RIKEN AIPi,jDiscrepancy-based ABCi,jIntroduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Approximation of the posterior
Bernton, E., Jacob, P. E., Gerber, M. & Robert, C. P. (2019). Approximate Bayesian
Computation with the Wasserstein distance. JRSS-B.

Contains a general result that can be applied here.
TheoremAssumeµθ has a continuous density fθ and for
Q some neighborhood
V of Y1:n we have supθ∈Θ supv1:n ∈V ni=1 fθ (vi ) < +∞.
v1:n 7→ dF (µ̂Y1:n , µ̂v1:n ) is continuous.
Then∀ measurable set A, ρ̂ϵ (A) −−→ π(A|Y1:n ).
ϵ→0Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Assumptions for contraction(C1) Y-valued Y1:n = (Y1 , . . . , Yn ) i.i.d from µ∗ , put :ϵ∗ := inf dF (µθ , µ∗ ).
θ∈Θ(C2) prior mass condition : there is c > 0, L ≥ 1 such thatπ θ ∈ Θ : dF (µθ , µ∗ ) − ϵ∗ ≤ ϵ ≥ cϵL(C3) functions in F are bounded :sup sup |f (y )| ≤ b.
f ∈F y ∈Y(C4) the Rademacher complexity Rn (F) satisfies
Rn (F) −−−→ 0.
n→∞Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Reminder on Rademacher complexity

Rademacher complexity"
Rn (F) := sup EY1 ,...,Yn ∼µ Eε1 ,...,εnµ#n1X
εi f (Yi ) .
supf ∈F ni=1

where ε1 , . . . , εn are i.i.d Rademacher variables :P(ϵ1 = 1) = P(ϵ1 = −1) = 1/2.

Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABCIntroduction
Discrepancy-based ABCExamples
TV : F = {1A , A measurable},Rn (F) ↛ 0 in general.
Kolmogorov : F = {1(−∞,x] , x ∈ R},
rlog(n + 1)
Rn (F) ≤ 2→ 0.
nWasserstein : F = set of 1-Lipschitz functions,
Rn (F) → 0 if X is bounded, see Corollary 8 in
Sriperumbudur, B.K., Fukumizu, K., Gretton, A., Schölkopf, B., Lanckriet, G.R. (2010).
Non-parametric estimation of integral probability metrics. IEEE International Symposium on
Information Theory.

MMD :rRn (F) ≤supy ∈Y k(y , y ).
nPierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Contraction of discrepancy-based ABC
Theorem 1
Under (C1)-(C4), with ϵ := ϵn = ϵ∗ + ϵ̄n with ϵ̄n → 0,nϵ̄2n → ∞ and ϵ̄n /Rn (F) → ∞. Then, for any sequence
Mn > 1, 2 · 3Lθ ∈ Θ : dF (µθ , µ∗ ) > ϵ∗ + rn
≤cMns2 log( Mε̄Ln )4ϵ̄nnwhere rn =+ 2Rn (F) + b,3n

ρ̂ϵn



with probability → 1 with respect to the sample Y1:n .
Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

ExamplespAssume Rn (F) ≤ c 1/np (MMD, Kolmogorov...).
Take Mn = n and ϵ̄n = log(n)/n to get 2 · 3Lθ ∈ Θ : dF (µθ , µ∗ ) > ϵ∗ + rn≤cnp
where rn = Olog(n)/n .

ρ̂ϵnLarger Rn (F) will lead to slower rates.

Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Removing (C3)-(C4)if we remove (C3)-(C4), we cannot use classicalconcentration results on dF (µ∗ , µ̂Y1:n ) and dF (µθ , µ̂Z1:n ).
we can still provide a result under the assumption that“some concentration holds”, as
Bernton, E., Jacob, P. E., Gerber, M. & Robert, C. P. (2019). Approximate Bayesian
Computation with the Wasserstein distance. JRSS-B.

for the Wasserstein distance.
however, this will impose assumptions on µ∗ , {µθ , θ ∈ Θ}and might lead to slower contraction rates. In our paper,
we illustrate this with MMD with unbounded kernels :rsupy ∈Y k(y , y )Rn (F) ≤= +∞.
nPierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABCExample : MMD-ABC with unbounded kernel
Theorem 2
Under (C1)-(C2), and(C5) EY ∼µ∗ [k(Y , Y )] < +∞,(C6) supθ∈Θ EZ ∼µθ [k(Z , Z )] < +∞,ϵn = ϵ∗ + ϵ̄n with ϵ̄n → 0. Then, for some C > 0, for any
sequence Mn > 1, with proba. → 1,ρ̂ϵnθ ∈ Θ : dF (µθ , µ∗ ) > ϵ∗ + rn

where rn =For example Mn =≤4ϵ̄nM2+ 2 n2L .
3n ϵ̄

CMn

√
n we can get rn = O(1/n2L+1 ).

Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

Experiments in the Gaussian case
2.5

2.0

α0.00

1.5

0.05
0.10
1.0

0.15

0.5

0.0

MMD

Wasserstein

KL

Pierre Alquier, RIKEN AIP

γ -divergence``Exact`` Gaussian

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABCConclusion
we provide an analysis of discrepancy-based ABC for alarge class of IPM.
in particular, ABC with MMD leads to robust estimation,
without assumptions on the model nor on the truth.
note that other discrepancies were studied and probably
more should be investigatedFrazier, D. T. (2020). Robust and efficient Approximate Bayesian Computation : A minimum
distance approach. Preprint arXiv.
Nguyen, H. D., Arbel, J., Lü, H. and Forbes, F. (2020). Approximate Bayesian computation via
the energy statistic. IEEE Access.

important extension to non i.i.d observations (time series,etc.). Note that strong concentration of dF (µ∗ , µ̂Y1:n ) isknown in this setting (our joint paper with B.-E.
Chérief-Abdellatif, Bernoulli 2022).
Pierre Alquier, RIKEN AIP

Discrepancy-based ABC

Introduction
Discrepancy-based ABC

Discrepancy-based ABC
Discrepancy-based ABC approximates the posterior
Contraction of discrepancy-based ABC

La fin終わり
ありがとう ございます。

Pierre Alquier, RIKEN AIP

Discrepancy-based ABC