PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust and Scalable Bayes via a Median of Subset Posterior Measures

Stanislav Minsker, Sanvesh Srivastava, Lizhen Lin, David B. Dunson

arXiv:1403.2660v3math.STcs.DCcs.LGstat.TH

TL;DR

Robust Bayesian methods remain insufficiently understood, and even one outlier can pull the usual posterior far from the true parameter. The paper splits data into disjoint groups, combines their subset posteriors through a median, and reports credible sets with strong frequentist coverage and often similar width to usual posterior credible sets.

  • Problem

    Robust Bayesian methods are not sufficiently well understood, and even one outlier can make the usual posterior concentrate far from the true parameter.

    Source: §1 · p. 2, §3.1 · p. 12

  • Method

    The method splits data into disjoint groups, samples each subset posterior in parallel, and combines them into a median probability measure called the M-Posterior.

    Source: §1 · p. 2

  • Results

    The M-Posterior is centered at a robust estimator, and its credible sets often have the same width as usual posterior credible sets while admitting strong frequentist coverage guarantees.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Despite losing interactions among data groups, the combined result still admits strong guarantees, while splitting the data gives advantages in robustness to outliers.

    Source: §1 · p. 2

    When the number of groups is large, the M-Posterior can become too flat and overestimate uncertainty because each subgroup posterior uses a much smaller sample.

    Source: §3.1 · p. 13, §3.3 · p. 18

Abstract

from arXiv · show

We propose a novel approach to Bayesian analysis that is provably robust to outliers in the data and often has computational advantages over standard methods. Our technique is based on splitting the data into non-overlapping subgroups, evaluating the posterior distribution given each independent subgroup, and then combining the resulting measures. The main novelty of our approach is the proposed aggregation step, which is based on the evaluation of a median in the space of probability measures equipped with a suitable collection of distances that can be quickly and efficiently evaluated in practice. We present both theoretical and numerical evidence illustrating the improvements achieved by our method.

1. Introduction

The paper proposes a Bayesian approach designed to handle outliers without modeling or removing them and to scale through parallel analysis of data subsets. It combines subset posteriors using a median, addressing the lack of a general, rigorously justified way to aggregate subset results.

1. Introduction

  • The approach is presented as provably robust to outliers without assumptions about their distribution or preprocessing, and scalable through parallel computation on data subsets.The introduction frames massive-data resource limits and severe contamination as key challenges.Source: §1 · p. 2
  • The method splits data into disjoint subsets, samples each subset posterior in parallel, and combines the draws into a median posterior measure.The paper says the resulting measure retains strong guarantees despite losing interactions among data in different groups.Source: §1 · p. 2
  • The M-Posterior is centered at a robust estimator, with credible sets often similar in width to usual-posterior sets and strong frequentist coverage guarantees.The introduction points to Section 3.3 for the exact statements.Source: §1 · p. 2

1.1. Discussion of related work

  • Existing approaches commonly model outliers or remove them, whereas this paper bypasses both steps and quantifies robustness through concentration properties under arbitrary contamination.The paper also identifies a gap in general, rigorously justified methods for combining subset posteriors into one distribution.Source: §1.1 · p. 3
  • Distributed Bayesian methods include repeated likelihood communication and stochastic-approximation approaches, while existing subset-posterior combinations have dimension or model restrictions and are not provably robust.The paper distinguishes its approach from subset-draw averaging and kernel-density or Weierstrass approximations.Source: §1.1 · pp. 3–4

2. Preliminaries

The preliminaries establish geometric and metric medians as robust aggregators and introduce distances between measures chosen for computational tractability. They describe how median aggregation preserves concentration under contamination and how distance choice affects empirical approximation rates.

2.1. Notation

  • The notation section specifies Euclidean distances, Dirac measures, and reproducing-kernel Hilbert space kernels.Source: §2.1 · pp. 4–5

2.2. Generalizations of the univariate median

  • Geometric medians of independent, weakly concentrated estimators improve concentration geometrically while preserving the estimation rate up to a constant.The paper applies this result to posterior distributions from disjoint data subsets.Source: §2.2 · p. 7
  • With at most ⌊κm⌋ arbitrary outliers, at most that many subset estimators can be affected, while their median remains close to θ0 with high probability.Source: §2.2 · p. 7
  • Although its general breakdown point is zero, the estimator remains consistent with o(n) outliers, the best possible without additional assumptions.Source: §2.2 · p. 7

2.3. Distances between probability measures

  • The paper selects measure distances that admit accurate numerical approximation, and RKHS structure supports fast numerical approximation of the geometric median.Source: §2.3 · p. 8
  • Kernel-based empirical-measure distance errors can have dimension-free order m^-1/2 + n^-1/2, whereas Wasserstein bounds scale as m^-1/(D+1) + n^-1/(D+1).Source: §2.3 · p. 9

3. Contributions and main results

The section develops the median posterior (M-posterior), including theoretical guarantees for convergence and robustness and stochastic approximations to address uncertainty inflation from small subsets. It also describes its approximate normality and confidence-set properties, and a method for selecting the number of subsets to ensure a stated frequentist coverage guarantee.

3.1. Construction of robust posterior distribution

  • The M-Posterior aggregates subset posteriors by a median under tractable probability-measure distances, addressing the risk that even one arbitrary outlier can pull an ordinary posterior far from the truth.The construction evaluates medians using the FL or Fk norms.Source: §3.1 · pp. 12–13

3.2. Convergence of posterior distribution and robust Bayesian inference

  • Under stated concentration conditions, median-posterior guarantees improve exponentially over the single-posterior result and extend to ⌊κm⌋ arbitrary outliers when κ < 1/3.The cited passages do not provide the complete bound values.Source: §3.2 · p. 15
  • The paper extends convergence guarantees to RKHS-induced distances under kernel-comparison and prior conditions, and identifies the M-Posterior mean as a robust estimator of θ0.The tractable-distance results rely on assumptions relating the chosen metric to Hellinger or Euclidean distance.Source: §3.2 · pp. 17–18

3.3. Bayesian inference based on stochastic approximation of the posterior distribution

  • When many small groups make the M-Posterior too flat and inflate uncertainty, repeating each subset observation m times creates stochastic approximations whose median yields better credible-set coverage.Each stochastic approximation is described as approximating the full-data likelihood.Source: §3.3 · pp. 18–19
  • Under the stated regularity conditions, the M-posterior is well approximated by a normal distribution.The conditions include a kernel of type (3.9), a differentiable-in-quadratic-mean parametric family with well-behaved bracketing numbers, and a regular prior.Source: §3.3 · p. 21
  • The estimator θ* is the center of a confidence set, and the stated M-posterior bound holds at finite sample sizes.The cited result specifies a confidence-set level and diameter, but those expressions are incomplete in the supplied passages.Source: §3.3 · p. 21
  • The confidence bound is not uniform in m because θ* depends on m; it holds only for a given confidence level 1−n^-A.This limitation qualifies the credible-set coverage interpretation.Source: §3.3 · p. 23
  • For a target coverage level of at least 1−n^-A, choose m=A log n and use the corresponding M-posterior credible set.The passage interprets the bound as giving this frequentist coverage guarantee for the (1−n^-A)-credible set.Source: §3.3 · p. 23

4. Numerical algorithms and examples

The section presents algorithms for combining subset posteriors and evaluates their robustness, uncertainty quantification, and computational performance in simulations and General Social Survey data. Across these examples, stochastic approximation improves interval coverage calibration, while the real-data analysis reports faster computation and lower memory use than the overall posterior.

4. Numerical algorithms and examples

  • The algorithms use Weiszfeld’s method to estimate subset-posterior weights, then discard atoms with weights below 1/(2m) before approximating M-Posterior.The authors report empirical evidence in favor of this thresholding step.Source: §4 · pp. 23–24
  • Partitioning into m = 2k + 1 subsets guarantees robustness to k outliers of arbitrary nature.The section recommends m ≲ √n as a rule of thumb; larger m can overestimate uncertainty.Source: §4 · pp. 24–25
  • For Gaussian process regression, when S = cn and m^2 < n^ε, the reported running-time improvement is O(m^2) over the standard approach.The comparison assumes access to m machines in parallel.Source: §4 · p. 25

4.1. Numerical analysis: simulated data

  • As outlier magnitude increased, M-Posterior coverage remained robust, while consensus and overall posterior coverage fell to 0%.M-Posterior credible intervals were fairly similar in width to those from the overall posterior, and slightly wider without large outliers.Source: §4.1 · pp. 26–27, Figure 1 · p. 26, Figure 2 · p. 27
  • Stochastic approximation produced shorter M-Posterior intervals with empirical coverage closer to theoretical values than the version without approximation.Without approximation, coverage overcompensated for uncertainty at all tested α levels.Source: §4.1 · p. 27, Figure 3 · p. 28, Figure 4 · p. 29

4.2. Real data analysis: General social survey

  • On General Social Survey data, M-Posterior was at least 10 times faster for m = 20 and 8 times faster for m = 10, using less than 25% of the overall posterior’s memory.Its coverage of test-data maximum-likelihood estimates was better, although the overall posterior was more concentrated.Source: §4.2 · p. 29

A.1. Proof of Theorem 2.1

The proof of Theorem 2.1 considers geometric medians of independent estimators in a Hilbert space and medians in a metric space. Its argument uses the event that more than half of the estimators lie within ε of the target.

A.1. Proof of Theorem 2.1

  • The proof treats independent estimators in a Hilbert space and defines their geometric median as the estimator of interest.It also states a metric-space case for independent random variables.Source: §A.1 · p. 33
  • The stated parameter conditions include 0 < q < α < 1/2 in the Hilbert-space case, with γ constrained by α and q.The proof invokes a geometric-median lemma and Chernoff bounds.Source: §A.1 · pp. 33–34
  • When more than half of the estimators are within ε of θ0, the proof bounds the geometric median’s distance from θ0 by 3ε.The argument uses the triangle inequality and the definition of the geometric median.Source: §A.1 · pp. 34–35

A.2. Proof of Theorem 3.1

The proof of Theorem 3.1 uses testing arguments and Bayes’ formula to bound posterior mass outside a Hellinger-distance neighborhood. It also applies probability bounds to control terms in the argument.

A.2. Proof of Theorem 3.1

  • The proof notes that the Hellinger distance is bounded by 1 and uses Chebyshev’s inequality in a probability bound.The displayed bound depends on l and ε.Source: §A.2 · pp. 35, 37
  • The argument estimates a remaining term using Bayes’ formula and a lemma from Ghosal, Ghosh and Van Der Vaart (2000).It also relies on an assumption on the prior Π.Source: §A.2 · pp. 35–36
  • The proof invokes test functions to bound posterior mass outside a Hellinger-distance neighborhood of θ0.The testing result is attributed to Theorem 7.1 of Ghosal, Ghosh and Van Der Vaart (2000).Source: §A.2 · p. 36

A.3. Proof of Theorem 3.8

The proof of Theorem 3.8 proceeds by applying testing bounds and probability estimates, with the distance specified as Hellinger or Euclidean. It then combines these bounds to obtain the result.

A.3. Proof of Theorem 3.8

  • The proof carries forward a probability bound involving constants C and C1, then introduces a constant K̃ = min(K/2, 1).The displayed fragments tie the bound to l and ε.Source: §A.3 · p. 38
  • The proof uses test functions for a distance d specified as Hellinger or Euclidean.The cited testing bound is from Theorem 7.1 of Ghosal, Ghosh and Van Der Vaart (2000).Source: §A.3 · pp. 38–39
  • The argument combines its bounds before concluding the proof.The combination is stated to yield the result.Source: §A.3 · p. 39

A.4. Proof of Theorem 3.11

The proof uses Hellinger-distance sets and bounds on the numerator and denominator of a posterior expression. It then applies a rescaled version of Theorem 3.10 to obtain the stated probability bound.

A.4. Proof of Theorem 3.11

  • The proof defines E_l using parameters whose Hellinger distance from P_0 is at least Rε_l.The passage gives h(P_θ, P_0) as the distance criterion.Source: §A.4 · p. 39
  • The denominator is bounded below using an event B_l and a bound attributed to Lemma 8.1 of Ghosal, Ghosh and Van Der Vaart (2000).Source: §A.4 · pp. 39–40
  • The numerator bound for γ = ε_l is extended to γ = Lε_l for any L ≥ 1, with the same probability.Source: §A.4 · p. 40
  • The proof combines numerator and denominator bounds for (A.11) to obtain a probability bound.The passage specifies choosing R large enough to satisfy a condition involving c1, m, and C, but its final bound is incomplete.Source: §A.4 · p. 40

A.5. Proof of Proposition 3.13

The proof first reduces the claim to priors restricted to a large compact set, then uses a classical argument for compactly supported priors.

A.5. Proof of Proposition 3.13

  • The proof reduces the result to the case of a prior restricted to a large compact set, then follows a classical argument.The passage points to Van der Vaart (2000) for the latter step.Source: §A.5 · p. 40
  • The compact-set reduction bounds the probability of parameters outside the set using the theorem’s numerator and denominator bounds.The argument uses an assumed inequality between Hellinger and Euclidean distances.Source: §A.5 · pp. 40–41

B.1. Probabilistic parafac model

This section describes a two-level probabilistic parafac model for responses and its posterior sampling scheme. It also presents response-pair posterior comparisons, including the model’s representation of uswar and abort as independent.

B.1. Probabilistic parafac model

  • The model has two levels: prior probabilities for latent classes and parameters, followed by latent variables and parameters specific to training-data respondents.Source: §B.1 · p. 41
  • The model assigns Dirichlet priors to question-response probabilities and specifies Gamma and fixed values for its hyperparameters.The stated choices are a Gamma prior on α with scale and shape 1, and α1 = α2 = 1.Source: §B.1 · p. 41
  • The figure compares dashed subset-posterior densities, M-Posteriors for m = 10 and m = 20, and the overall posterior for four response pairs.For uswar and abort, the caption says the model recognizes that the responses should be independent.Source: Figure 6 · p. 42, §B.1 · p. 42
  • A Gibbs sampler produces posterior samples of π_c1,...,c9, while π_ci,cj samples marginalize the other seven questions.The sampling scheme adapts the original p-parafac sampler for subset posteriors using stochastic approximation.Source: §B.1 · p. 42
  • The reported sampling setup uses 10,000 iterations, collects every fifth sample after a 5,000-iteration burn-in, and caps memory at 16GB for subsets and 64GB overall.The experiments used Matlab on 2.6GHz, 16-core cluster nodes.Source: §B.1 · p. 42

B.2. Dirichlet process mixture model sampling for the stochastic approximation

For a Dirichlet process mixture example, the section describes stochastic approximation of subset likelihoods and a Gibbs sampler. The sampler uses tractable full conditionals for latent variables and unknown parameters.

B.2. Dirichlet process mixture model sampling for the stochastic approximation

  • The example augments a Dirichlet process mixture sampling model with latent variables and raises the complete-data likelihood to an appropriate power for stochastic approximation.The authors report excellent performance with this approach in other contexts, including matrix completion.Source: §B.2 · p. 43
  • The model partitions data into m subsets of size l and applies stochastic approximation to each subset’s complete-data likelihood.The setup begins with i.i.d. observations modeled using Dirichlet process mixtures.Source: §B.2 · p. 43
  • The Gibbs sampler iterates through five steps because the latent-variable and parameter full conditionals are tractable in standard distributions.Source: §B.2 · p. 43
  • The listed updates include sampling latent assignments Z_ji and stick-breaking variables V_h from their conditional distributions.Source: §B.2 · p. 44
  • The implementation fixes σ_θ = 100, sets a_α = b_α = 1, and uses a_0 = b_0 = 0.01.These choices are described as following standard conventions.Source: §B.2 · p. 44

B.3. Selection of the optimal number of subsets m

The heuristic evaluates M-Posteriors over a candidate range of m values and selects their median using the metric median.

B.3. Selection of the optimal number of subsets m

  • The heuristic selects the median among candidate M-Posteriors.It first evaluates the M-Posterior for each m in the candidate range [m1, m2].Source: §B.3 · p. 44
  • The candidates span m values from m1 to m2.Source: §B.3 · p. 44
  • The selection uses med0, the metric median defined in equation (2.3).Source: §B.3 · p. 44
Loading 1403.2660v3…