Concentration of discrepancy-based approximate Bayesian computation via Rademacher complexity

Sirio Legramanti, Daniele Durante, Pierre AlquierThe Annals of Statistics 2022 · arXiv

TL;DR

This paper introduces a unified theoretical framework for "summary-free" Approximate Bayesian Computation (ABC) by linking posterior concentration to Rademacher complexity. By treating popular discrepancies (like MMD and Wasserstein distance) as Integral Probability Semimetrics (IPS), the authors derive explicit, uniform concentration bounds that hold even in misspecified or non-i.i.d. settings.

What Problem Does This Paper Address?

Approximate Bayesian Computation (ABC) is a go-to method for performing inference when the likelihood function is intractable. Traditional ABC relies on choosing "summary statistics," which can be a "black art"—pick the wrong ones, and you lose critical information.

Recently, researchers have moved toward "summary-free" ABC, which compares the entire empirical distribution of observed data to synthetic data using discrepancies like Maximum Mean Discrepancy (MMD) or Wasserstein distance. However, the theory behind these methods was fragmented. Most existing proofs were discrepancy-specific and relied on hard-to-verify "regularity conditions" on the unknown true data-generating process.

The authors aim to bridge this gap with a unified theory that provides explicit, verifiable bounds on how quickly the ABC posterior concentrates around the truth as the sample size grows.

Methods

The researchers leverage two key concepts from statistical learning theory:

  1. Integral Probability Semimetrics (IPS): They show that most popular summary-free discrepancies belong to the IPS class. An IPS measures the distance between two distributions by looking at the maximum difference in expectations over a specific class of functions $\mathcal{F}$.
  2. Rademacher Complexity: This is the "secret sauce" of the paper. It measures the "richness" or "flexibility" of the function class $\mathcal{F}$.

By connecting these two, the authors prove that the concentration of the ABC posterior is directly governed by the Rademacher complexity of the discrepancy being used. This allows them to derive bounds that are uniform (they hold regardless of the true data-generating process) and constructive (the bounds depend on known properties of the chosen discrepancy). They also extend this theory to $\beta$-mixing processes, allowing ABC to be used rigorously for time-series and other dependent data.

Datasets

As a theoretical work, the paper uses controlled simulations to validate the insights:

  • Misspecified Huber Contamination Model: A bivariate Student’s $t$-distribution perturbed by a "contaminating" distribution. This tests how robust the ABC posterior is when the model is slightly wrong.
  • Non-i.i.d. Gaussian AR(1) Process: A time-series model with contamination, used to evaluate the theory's extension to dependent data.
  • Comparisons: They evaluate MMD (with Gaussian kernels), Wasserstein-1 distance, summary-based ABC (using the mean/covariance), and KL divergence.

Key Insights and Ideas

  • The "Richness" Trade-off: If a discrepancy's function class $\mathcal{F}$ is too "rich" (high Rademacher complexity), the ABC posterior might not be well-defined in the limit. For example, the Total Variation (TV) distance is often too rich for continuous data in ABC.
  • MMD as a Safe Default: MMD with bounded kernels (like the Gaussian kernel) is highlighted as a robust choice because its Rademacher complexity is guaranteed to vanish at a rate of $1/\sqrt{n}$, ensuring posterior concentration even without knowing if the true data-generating process is "well-behaved."
  • Inflation of the Support: In settings with a fixed tolerance threshold $\epsilon$, the authors show that the support of the ABC posterior is "inflated" by a factor proportional to the Rademacher complexity. As the complexity goes to zero, you recover the standard theoretical limit.
  • Robustness to Contamination: The theory explains why certain discrepancies are robust. For instance, MMD and Wasserstein-1 are shown to concentrate in a neighborhood of the "uncontaminated" model even when the data is messy.

Key Results

  • Theorem 3.1 & 3.3: These provide the core mathematical result—explicit upper and lower bounds for the ABC acceptance probability and posterior concentration.
  • Convergence Rates: In the i.i.d. case, the ABC posterior concentrates at a rate of roughly $[ \log(n)/n ]^{1/2}$. In the non-i.i.d. ($\beta$-mixing) case, the rate slows down to approximately $n^{-1/4}$.
  • Simulation Performance: In the contaminated bivariate $t$ experiment, MMD achieved the lowest Mean Squared Error (MSE) across all contamination levels ($\alpha = 0.05$ to $0.15$), significantly outperforming summary-based methods which failed to handle the location shift caused by contamination.

Limitations and Future Work

  • Unbounded Spaces: While the theory is very general, applying it to Wasserstein distance or MMD with unbounded kernels in unbounded data spaces still requires some assumptions about the existence of moments (e.g., the data can't have "infinitely heavy" tails).
  • Pessimistic Rates: The authors acknowledge that the $n^{-1/4}$ rate for non-i.i.d. data might be pessimistic for certain models and suggest that future refinements of the Rademacher bounds for mixing processes could sharpen this.
  • Beyond IPS: The current framework doesn't directly cover $f$-divergences like KL or Hellinger distance, though the authors suggest this as a promising direction for future "unified" research.

Summary updated

Abstract

There has been an increasing interest on summary-free solutions for approximate Bayesian computation (abc) that replace distances among summaries with discrepancies between the empirical distributions of the observed data and the synthetic samples generated under the proposed parameter values. The success of these strategies has motivated theoretical studies on the limiting properties of the induced posteriors. However, there is still the lack of a theoretical framework for summary-free abc that (i) is unified, instead of discrepancy-specific, (ii) does not necessarily require to constrain the analysis to data generating processes and statistical models meeting specific regularity conditions, but rather facilitates the derivation of limiting properties that hold uniformly, and (iii) relies on verifiable assumptions that provide more explicit concentration bounds clarifying which factors govern the limiting behavior of the abc posterior. We address this gap via a novel theoretical framework that introduces the concept of Rademacher complexity in the analysis of the limiting properties for discrepancy-based abc posteriors, including in non-i.i.d. and misspecified settings. This yields a unified theory that relies on constructive arguments and provides more informative asymptotic results and uniform concentration bounds, even in those settings not covered by current studies. These key advancements are obtained by relating the asymptotic properties of summary-free abc posteriors to the behavior of the Rademacher complexity associated with the chosen discrepancy within the family of integral probability semimetrics (ips). The ips class extends summary-based distances, and also includes the widely implemented Wasserstein distance and maximum mean discrepancy (mmd), among others. As clarified in specialized theoretical analyses of popular ips discrepancies and via illustrative simulations, this new perspective improves the understanding of summary-free abc.
BibTeX
@article{legramanti2022concentration,
  author = {Sirio Legramanti and Daniele Durante and Pierre Alquier},
  title = {{Concentration of discrepancy-based approximate Bayesian computation via Rademacher complexity}},
  journal = {The Annals of Statistics},
  year = {2022},
}
Figure