Source-linked AI summary
Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent
Trevor Campbell, Tamara Broderick
TL;DR
Scalable Bayesian inference can underestimate posterior uncertainty, including when Bayesian coresets approximate large datasets. The paper develops GIGA, which optimally scales coreset log-likelihoods, and reports improved posterior approximation with theoretical guarantees and experimental validation.
Problem
Existing scalable inference methods, including Bayesian coreset constructions, can provide unreliable posterior approximations and underestimate posterior uncertainty.
Method
GIGA greedily selects coreset points and reweights them along a geodesic while optimally scaling the coreset log-likelihood.
Results
GIGA provides uniformly bounded relative error and asymptotic exponential error decay while retaining the computational complexity of prior coreset methods.
Takeaways & Limitations
Optimal coreset log-likelihood scaling substantially improves posterior approximation quality without sacrificing the low computational cost and simple implementation of prior methods.
Takeaways & Limitations
The geodesic reweighting guarantee assumes initialization with the most aligned vector and a positive optimal objective.
Abstract
from arXiv · showhide
Coherent uncertainty quantification is a key strength of Bayesian methods. But modern algorithms for approximate Bayesian posterior inference often sacrifice accurate posterior uncertainty estimation in the pursuit of scalability. This work shows that previous Bayesian coreset construction algorithms---which build a small, weighted subset of the data that approximates the full dataset---are no exception. We demonstrate that these algorithms scale the coreset log-likelihood suboptimally, resulting in underestimated posterior uncertainty. To address this shortcoming, we develop greedy iterative geodesic ascent (GIGA), a novel algorithm for Bayesian coreset construction that scales the coreset log-likelihood optimally. GIGA provides geometric decay in posterior approximation error as a function of coreset size, and maintains the fast running time of its predecessors. The paper concludes with validation of GIGA on both synthetic and real datasets, demonstrating that it reduces posterior approximation error by orders of magnitude compared with previous coreset constructions.
1. Introduction
Scalable Bayesian inference can compromise posterior uncertainty, and existing Bayesian coresets are particularly prone to underestimating posterior variance. The paper identifies suboptimal log-likelihood scaling as the cause and introduces GIGA to address it.
- MCMC offers strong Bayesian guarantees but typically costs Θ(NT), making it intractable for modern large-scale datasets.
- Scalable variational methods can converge to bad local optima and either overestimate or underestimate posterior variance.
- Bayesian coresets select and reweight M ≪ min{N, T} data points, enabling MCMC at O(M(N + T)) computational cost.
- Existing coreset constructions underestimate posterior uncertainty because they scale the coreset log-likelihood suboptimally, producing overweighted coresets with overly certain posteriors.
- GIGA optimally scales the coreset log-likelihood while retaining predecessor computational complexity, yielding uniformly bounded relative error and asymptotic exponential error decay.
2. Bayesian Coresets
Bayesian coresets approximate full-data log-likelihoods with sparse weighted combinations so standard MCMC can operate on much smaller datasets. The section explains how simplex-constrained constructions distort scaling and posterior uncertainty, motivating optimal rescaling.
- Bayesian Coresets: MCMC on the full dataset costs Θ(NT), whereas MCMC on a coreset reduces the likelihood workload through a small weighted subset.
- Bayesian Coresets: A Bayesian coreset approximates the full log-likelihood using nonnegative weights on a subset with cardinality ∥w∥0 ≪ N.
- Bayesian Coresets: The coreset construction problem is a cardinality-constrained vector approximation problem for log-likelihood vectors.
- Approximation Methods: Frank–Wolfe achieves geometric convergence O(ν^M), while importance sampling is limited to the Monte Carlo rate O(M^-1) with high probability.
- Posterior Uncertainty Underestimation: Replacing the cardinality constraint with a simplex constraint forces both importance sampling and Frank–Wolfe to scale the coreset log-likelihood roughly by σ rather than ∥L∥.
- Posterior Uncertainty Underestimation: Because σ ≥ ∥L∥, the resulting weights add artificial data and produce overly certain posterior approximations.
- Posterior Uncertainty Underestimation: For every M, there are problems where Frank–Wolfe and importance-sampling coresets after M iterations have arbitrarily large error relative to ∥L∥.
- GIGA: GIGA uses the cardinality constraint’s scale invariance to maintain optimal log-likelihood scaling during greedy construction.
3. Greedy Iterative Geodesic Ascent (GIGA)
GIGA separates optimal log-likelihood scaling from directional optimization, then builds a coreset greedily on the unit hypersphere by geodesic alignment and line search. The resulting approximation error is proportional to ∥L∥ and decays geometrically with coreset size.
- Radial optimization: GIGA first solves the optimal log-likelihood scaling analytically, then optimizes the normalized approximation on the unit hyperspherical manifold.This replaces the simplex-based formulation with an alignment problem whose objective depends on the directions of L(w) and L.
- Guarantee: Theorem 3.1 establishes approximation error proportional to ∥L∥ with geometric decay in M, while the convergence proof combines an O(1/t) intermediate bound with a geometric-decay argument.The paper states that the resulting solution is optimally scaled and has decaying relative error.
- Initialization: The algorithm normalizes the total and data log-likelihood vectors, initializes zero weights, and iteratively maintains a normalized coreset direction.The implementation initializes w0 = 0 and uses normalized vectors ℓn, ℓ, and ℓ(w).
- Output scaling: After M iterations, the algorithm rescales the normalized coreset weights optimally to produce weights for the original unnormalized log-likelihood vectors.The final rescaling uses the norm of L, the norms of the data vectors, and the alignment between ℓ(wM) and ℓ.
- Greedy point selection: At each iteration, GIGA selects the data point whose geodesic direction is most aligned with the geodesic from the current iterate to the target.This greedy choice is designed to produce the largest decrease in approximation error.
- Reweighting: After selecting a point, GIGA performs a constrained line search along the geodesic between the current iterate and that point, then updates the weights.The step γt is constrained to [0,1], and the update preserves feasibility while maximizing alignment with the target direction.
4. Experiments
The experiments compare GIGA with random subsampling and Frank–Wolfe on synthetic and regression datasets, evaluating reconstruction, coreset size, posterior error, and computation time. GIGA achieves substantially lower errors and improved representation efficiency while maintaining performance across inference settings.
- 4.1. Synthetic Gaussian Inference: Across 1,000 Gaussian-inference replications, GIGA reduced median relative posterior-variance error to 3%, compared with 48% for FW.
- 4.2. Synthetic Vector Sum Approximation: On the synthetic vector dataset, GIGA reduced reconstruction error by 2–4 orders of magnitude versus FW across construction iterations and significantly outperformed RND.The experiment used 20 datasets of 10^6 50-dimensional vectors and measured 2-norm reconstruction error and coreset size.
- 4.2. Synthetic Vector Sum Approximation: GIGA stopped growing its coreset at size 120, while FW continued adding points until its coreset was over twice as large.
- 4.3. Bayesian Posterior Approximation: The posterior-approximation comparison covered multiple datasets and models, with results evaluated against coreset size and total computation time over 20 trials.The evaluation used Hamiltonian Monte Carlo and full-data posterior samples as the reference.
- 4.3. Bayesian Posterior Approximation: In logistic and Poisson regression, GIGA produced a 3–4 orders-of-magnitude reduction in posterior error and correctly scaled posterior uncertainty across coreset sizes.Distances were measured using posterior Fisher information distance and compared with RND and FW.
5. Conclusion
The paper concludes that GIGA is a practical Bayesian coreset algorithm that improves posterior approximation by scaling the coreset log-likelihood optimally. Its theoretical guarantees and experiments support this improvement without sacrificing simplicity or low computational cost.
- GIGA is a novel Bayesian coreset construction algorithm designed to improve posterior approximation quality.
- Unlike previous algorithms, GIGA scales the coreset log-likelihood optimally, while remaining simple, computationally inexpensive, and free of tuning parameters.
- The paper’s theoretical guarantees and experimental results reflect the improvement in posterior approximation produced by GIGA.
A.1. Orthonormal vectors
The orthonormal-vector experiment evaluates GIGA, Frank–Wolfe, and random subsampling on a high-dimensional dataset aligned with coordinate axes. It compares reconstruction error and representation efficiency.
- The experiment used 5,000 unit vectors in R^5000, each aligned with one coordinate axis.
- Coresets were constructed using uniformly random subsampling, Frank–Wolfe, and GIGA.
- The methods were compared using 2-norm reconstruction error between L(w) and L and representation efficiency measured by coreset size.
A.2. Alternate inference algorithms
Alternate-inference experiments reran the posterior-approximation evaluation with random-walk Metropolis–Hastings and NUTS instead of Hamiltonian Monte Carlo. The results generally corroborated the main-text findings, with NUTS showing an S-shaped computation-time curve caused by path-length adaptation.
- The experiment replaced Hamiltonian Monte Carlo with random-walk Metropolis–Hastings and the No-U-Turn Sampler.For random-walk Metropolis–Hastings, the procedure used 50,000 simulated steps, including 25,000 warmup steps and 25,000 sampling steps.
- The alternate-inference results generally corroborated the main-text results.
- With NUTS, performance versus computation time followed an S-shaped curve caused by dynamic path-length adaptation.
B. Technical Results and Proofs
The technical results establish bounds underlying the coreset construction and evaluate reconstruction error and coreset size on a synthetic axis-aligned dataset.
- Proof bounds: The proof begins by establishing a τ√J_t bound for the relevant geometric quantity.
- Proof bounds: The analysis represents ℓ(w_t) using orthogonal components involving d and ℓ, with d formed as a conic combination of the data directions.
- Experiments: The synthetic experiment compares random subsampling, Frank–Wolfe, and GIGA using 2-norm reconstruction error and coreset size.
- Experiments: Figures 6 and 7 report the Section 4.3 experiment with posterior inference performed using random-walk Metropolis–Hastings and NUTS, respectively.
- Proof bounds: The derived bound holds for all J_t ∈ [0, 1], with the active regime restricted to sufficiently small J_t.
C. Cap-tree Search
The cap-tree search organizes unit-vector data into spherical regions and uses bounds to prune candidate points during the next-point maximization.
- Search procedure: Selecting the next coreset point requires solving a maximization with O(N) complexity.
- Limitations: Tree construction and search remain an open efficiency problem because construction costs can outweigh search benefits and gains diminish for high-dimensional vectors.
- Tree structure: Each tree node is a spherical cap defined by a unit central direction and dot-product bound, containing data from its child leaves.
- Search procedure: The search evaluates lower and upper objective bounds for nodes and prunes a node when its upper bound is below the current best lower bound.
- Optimization: The optimization decomposes vectors into components aligned with u, v, and complementary basis directions before solving for the relevant coefficients.
- Optimization: The derivation handles boundary cases by checking feasibility at γ = 1 and γ = −1 and otherwise solving an unconstrained derivative condition.
D. Datasets
The paper identifies online sources for the Phishing, DS1, and BikeTrips datasets and describes the construction sources for AirportDelays.
- Dataset sources: The Phishing dataset is identified by an online source.
- Dataset sources: The DS1 dataset is identified by an online source at komarix.org/ac/ds/.
- Dataset sources: The BikeTrips dataset is identified by the UCI Machine Learning Repository.
- Dataset construction: The AirportDelays dataset combines flight-delay data with historical weather information.