PaperlayerView exact revision on arXiv

Source-linked AI summary

Coresets for Scalable Bayesian Logistic Regression

Jonathan H. Huggins, Trevor Campbell, Tamara Broderick

arXiv:1605.06423v3stat.COcs.DSstat.ML

TL;DR

Large-scale Bayesian inference is computationally expensive, motivating methods that avoid processing all observations while retaining Bayesian modeling benefits. This paper constructs weighted coresets for Bayesian logistic regression, with guarantees for fixed datasets and broad data-generating models. In experiments, coreset posteriors often outperform random subsampling by orders of magnitude in MMD, while coreset construction adds negligible overhead.

  • Problem

    Large-scale Bayesian inference is difficult because standard algorithms are computationally expensive, while existing scalable methods can require random access or constant-fraction sampling and may lack rigorous quality guarantees.

  • Method

    The paper exploits data redundancy to construct a weighted subset for Bayesian logistic regression that uniformly approximates the full-data log-likelihood and can be built in streaming or distributed settings.

  • Results

    Coreset-based posteriors are orders of magnitude better than random-subsampling posteriors in maximum mean discrepancy in many cases, including a 100-dimensional real-world dataset, with negligible construction overhead.

  • Takeaways & Limitations

    The coreset can be used with existing posterior inference algorithms as a compact, theoretically analyzed representation of the data.

  • Takeaways & Limitations

    Experiments used at most 1 million examples because calculating the true posterior was infeasible for extremely large datasets.

Abstract

from arXiv · show

The use of Bayesian methods in large-scale data settings is attractive because of the rich hierarchical models, uncertainty quantification, and prior specification they provide. Standard Bayesian inference algorithms are computationally expensive, however, making their direct application to large datasets difficult or infeasible. Recent work on scaling Bayesian inference has focused on modifying the underlying algorithms to, for example, use only a random data subsample at each iteration. We leverage the insight that data is often redundant to instead obtain a weighted subset of the data (called a coreset) that is much smaller than the original dataset. We can then use this small coreset in any number of existing posterior inference algorithms without modification. In this paper, we develop an efficient coreset construction algorithm for Bayesian logistic regression models. We provide theoretical guarantees on the size and approximation quality of the coreset -- both for fixed, known datasets, and in expectation for a wide class of data generative models. Crucially, the proposed approach also permits efficient construction of the coreset in both streaming and parallel settings, with minimal additional effort. We demonstrate the efficacy of our approach on a number of synthetic and real-world datasets, and find that, in practice, the size of the coreset is independent of the original dataset size. Furthermore, constructing the coreset takes a negligible amount of time compared to that required to run MCMC on it.

1. Introduction

Large-scale Bayesian inference is hindered by computational and data-access constraints, while existing scalable methods either limit efficiency or lack rigorous quality guarantees. This paper instead exploits redundancy through coresets for Bayesian logistic regression, with theoretical, computational, and empirical support.

  • Motivation: Large datasets make even repeated per-observation operations burdensome and can exceed a single machine’s physical memory.These constraints have limited practitioners’ access to richer Bayesian models, uncertainty quantification, and prior specification.
  • Prior approaches: Existing scalable Bayesian methods modify MCMC or variational inference through subsampling, streaming, or distributed processing.The approaches include stochastic variational inference, subsampling MCMC, consensus MCMC, and streaming variational Bayes.
  • Prior approaches: Random-subset methods can require random data access and a constant fraction of the dataset at each iteration, limiting their computational gains.Consensus MCMC and streaming variational Bayes improve efficiency but lack rigorous justification and inference-quality guarantees.
  • Coreset approach: The paper uses data redundancy to construct a weighted subset, or coreset, that modifies the dataset rather than a particular posterior inference algorithm.Representative points can cover redundant observations while distinctive points remain important to include.
  • Contributions: The logistic-regression coreset uniformly approximates the full-data log-likelihood within a user-specified parameter-space ball, with high-probability guarantees for a fixed dataset.The paper also shows bounded parameter space is necessary for a nontrivial coreset.
  • Contributions: The method supports streaming and distributed construction, expected-performance analysis, and use with inference algorithms accessing the log-likelihood gradient as a black box.Experiments on synthetic and real-world datasets report robust hyperparameter behavior, orders-of-magnitude MMD advantages over random subsampling in many cases, and negligible construction overhead.

2. Problem Setting

The paper formalizes Bayesian coreset approximation by requiring a weighted dataset to approximate the full-data log-likelihood uniformly over parameters. It connects this approximation to marginal likelihood accuracy and specifies a sampling-based logistic-regression construction.

  • Bayesian posterior: The Bayesian setting starts with dataset observations, a prior density over parameters, and a likelihood for each observation.The posterior is formed from the prior and the likelihood contributions of the dataset.
  • Coreset definition: A weighted dataset is constructed as a smaller representation of the original data for approximate Bayesian inference.The coreset uses weighted observations rather than requiring the full dataset during inference.
  • Coreset definition: An ε-coreset approximates the full-data log-likelihood with a multiplicative error uniformly over the parameter space.This approximation defines the coreset notion used for Bayesian inference.
  • Approximation guarantee: The approximate posterior’s marginal likelihood approximates the true marginal likelihood when the coreset satisfies the log-likelihood approximation condition.Proposition 2.1 establishes this relationship for arbitrary non-positive log-likelihood functions satisfying the stated bound, assuming finite marginal likelihoods.
  • Construction algorithm: The algorithm requires data, a k-clustering, a radius R, a tolerance ε, and a failure rate as construction inputs.The displayed algorithm is explicitly titled the construction of a logistic regression coreset.
  • Construction algorithm: The construction samples M coreset points using importance probabilities derived from sensitivity upper bounds and assigns weights to sampled observations.Only observations with non-zero resulting weights are retained in the coreset.

3. Coresets for Logistic Regression

The paper constructs logistic-regression coresets by sampling according to efficiently computed sensitivity upper bounds, with guarantees for bounded parameter spaces. Its analysis explains when sensitivities remain compressible, while extending construction to streaming and parallel settings.

  • Coreset Construction: Sensitivity quantifies each data point’s redundancy, and the algorithm samples points with probabilities based on efficiently computed upper bounds.Sampled points receive inverse-probability weights, producing an ε-coreset with high probability.
  • Coreset Size: The coreset size is governed by the mean sensitivity, desired error, and a quantity related to the VC dimension, which is D + 1 here.Small coresets require most sensitivities and their upper bounds to be much smaller than N, ideally with constant mean sensitivity.
  • Coreset Construction: With probability at least 1 − δ, Algorithm 1 constructs an ε-coreset in O(Nk) time for Θ = B_R.The required k-clustering can also be obtained with k-means++ in O(Nk) time.
  • Sensitivity Lower Bounds: Unbounded Θ is nontrivial: even arbitrarily close data vectors can have σ_n(R^D) = N, the maximum possible sensitivity.These worst-case and average-case results motivate restricting the parameter space to a Euclidean ball B_R.
  • Streaming and Parallel Settings: The construction supports streaming and distributed computation through standard coreset composition methods, while retaining black-box compatibility with inference algorithms.The analysis also characterizes expected upper-bound performance for a wide class of data-generating distributions.

4. Experiments

Experiments evaluate coreset construction cost, posterior approximation, and robustness on synthetic and real-world logistic-regression datasets. Coresets generally match or outperform random subsampling while remaining inexpensive to construct.

  • Constructing Coresets: Except for very small coresets, MCMC inference took longer than coreset construction.Construction time was compared with inference including 10,000 MCMC iterations.
  • Experimental Setup: The evaluation used synthetic and real-world datasets, with experiments repeated 20 times for each subset size.Synthetic and real-data test splits are described in the Figure 2 caption.
  • Sensitivity: Coreset performance was robust to the tested choices of clustering and sensitivity hyperparameters.Similar results were obtained for 4 ≤ k ≤ 8 and 2.5 ≤ a ≤ 3.5.
  • Posterior Approximation Quality: On synthetic data, coresets matched or outperformed random subsampling in test log-likelihood and improved MMD by 1–2 orders of magnitude.The coreset never performed worse in MMD on the reported synthetic experiments.
  • Posterior Approximation Quality: On real datasets, coresets generally matched or outperformed random subsampling, with exceptions on larger ChemReact subsets and the smallest Webspam subset.Webspam performance was approximately equal overall, while CovType showed no reported disadvantage across almost all subset sizes.
  • Posterior Approximation Quality: High-quality posterior approximations were obtained with coresets many orders of magnitude smaller than the full datasets, sometimes using only a few hundred points.The paper reports corresponding reductions in memory and computational requirements for inference.

Appendix A. Marginal Likelihood Approximation

The proof uses the non-positivity of the log-likelihoods, the multiplicative error assumption, and Jensen’s inequality.

  • Proof: The argument assumes that both log-likelihood functions are non-positive.This condition is used together with the multiplicative error assumption.
  • Proof: The proof applies the multiplicative error assumption to relate the approximate and original log-likelihoods.The supplied passage identifies this assumption as a central step.
  • Proof: Jensen’s inequality is used in deriving the marginal-likelihood approximation.The passage lists Jensen’s inequality among the proof ingredients.

Appendix B. Main Results

The appendix develops the coreset construction theory for logistic regression, including sensitivity bounds, range-space dimension, and algorithmic complexity. It establishes an O(Nk) construction procedure.

  • Approximation Guarantee: Coresets can be sampled using a theorem that provides uniform approximation guarantees with probability at least 1 − δ.The theorem selects elements independently according to sensitivity-based probabilities.
  • Coreset Framework: A coreset approximates the logistic-regression log-likelihood uniformly over the parameter space up to multiplicative error.In the application, fn(θ) = −ln p(Yn | Xn, θ).
  • Sensitivity Construction: The sensitivity values determine sampling probabilities and must be constructed efficiently for logistic regression.The framework requires bounding mean sensitivity and computing the individual sensitivity values.
  • Sensitivity Construction: The sensitivity bound for each point can be calculated in O(k) time.The calculation uses cluster membership, cluster means, and a sum over clusters.
  • Range-Space Dimension: The logistic-regression function family has dimension at most D + 1.This dimension bound follows from the corresponding hyperplane concept class.
  • Algorithmic Complexity: The coreset construction algorithm has overall complexity O(Nk).Sensitivity calculation takes O(Nk) time and coreset sampling takes O(N) time.

Appendix C. Sensitivity Lower Bounds

The appendix constructs difficult logistic-regression instances for which highly similar data vectors can still induce separated likelihood behavior. These constructions support sensitivity lower bounds.

  • Geometric Construction: For the constructed vectors, parameter vectors can be chosen with bounded norm to distinguish selected examples.The supplied construction specifies θk with a norm constraint and positive inner-product inequalities.
  • Geometric Construction: Separated unit vectors can be embedded as vectors whose pairwise inner products are at least 1 − ϵ′.The construction preserves near-alignment while retaining a separation property for suitable parameter choices.
  • Likelihood Separation: The vector construction uses δ² = ϵ′/2 and a parameter α to control the logistic-loss separation.The proof invokes the bound φ(s)/φ(−s) ≤ e^−s for s ≥ 0.
  • Random-Vector Argument: With probability at least 1/2, random unit vectors are pairwise (1 − ϵ)-orthogonal.The result follows from Hoeffding’s inequality and a union bound over vector pairs.
  • Lower-Bound Consequence: Applying the clustering sensitivity bound to these constructions yields the stated lower-bound result.The proof combines Lemma 3.1 with the lower bound in Theorem 3.4.

Appendix D. A Priori Expected Sensitivity Upper Bounds

The appendix derives expected sensitivity bounds for mixture-generated data by conditioning on component counts and controlling their concentration around mixture weights. It then extends the result to special cases and related Gaussian-mixture calculations.

  • The proof conditions on mixture-component labels and partitions datapoints according to their generating components.
  • Component proportions |C_i|/N are expected to concentrate around mixture weights π_i as N grows.
  • The finite-sample argument splits the expectation according to whether component proportions remain close to π_i.
  • A union bound and Hoeffding’s inequality control the probability of atypical component proportions.
  • Choosing ϵ = N^-r for 0 < r < 1/2 yields η_i = max(π_i − N^-r, 0) for the asymptotic analysis.
  • Corollary 3.9 follows directly from Proposition 3.8 when π_1 = 1 and π_i = 0 for i ≥ 2.

Appendix E. Further Experimental Details

The experiments use datasets summarized in Table 1 and implement the coreset with approximations that substantially accelerate construction while retaining sensitivity control over the full dataset. Posterior comparisons use adaptive Metropolis-adjusted Langevin sampling.

  • The implementation replaces adjusted leave-one-out centers with original centers Q_i, causing at most a 1% sensitivity change in practice.This substitution produces an order-of-magnitude speed-up in the algorithm.
  • The clustering step uses a random subset of size L = min(1000k, 0.025N) to obtain k centers, then evaluates clustering quantities on the full dataset.The selected subset size becomes independent of N as N grows.
  • Although subsampling selects cluster centers, sensitivity upper bounds are still calculated across the entire dataset to capture rare influential patterns.Influential points are expected to lie far from cluster centers.
  • Table 1 summarizes the datasets used for the experiments.
  • Posterior inference uses adaptive Metropolis-adjusted Langevin sampling, with step-size adaptation during the first T/2 of T iterations.The remaining iterations provide approximate posterior samples, with a targeted acceptance rate of 0.574.
Loading 1605.06423v3…