Fast Bayesian Coresets via Subsampling and Quasi-Newton Refinement

• URL: http://arxiv.org/abs/2203.09675v1
• Date: Fri, 18 Mar 2022 01:04:39 GMT
• Title: Fast Bayesian Coresets via Subsampling and Quasi-Newton Refinement
• Authors: Cian Naik, Judith Rousseau, Trevor Campbell
• Abstract summary: We propose a Bayesian coreset construction algorithm that first selects a uniformly random subset of data, and then optimize the weights using a novel quasi-Newton method. Our algorithm is simple to implement, does not require the user to specify a low-cost posterior approximation, and is the first to come with a general high-probability bound on the KL divergence of the output coreset posterior.
• Score: 15.426481600285728
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bayesian coresets approximate a posterior distribution by building a small weighted subset of the data points. Any inference procedure that is too computationally expensive to be run on the full posterior can instead be run inexpensively on the coreset, with results that approximate those on the full data. However, current approaches are limited by either a significant run-time or the need for the user to specify a low-cost approximation to the full posterior. We propose a Bayesian coreset construction algorithm that first selects a uniformly random subset of data, and then optimizes the weights using a novel quasi-Newton method. Our algorithm is simple to implement, does not require the user to specify a low-cost posterior approximation, and is the first to come with a general high-probability bound on the KL divergence of the output coreset posterior. Experiments demonstrate that the method provides orders of magnitude improvement in construction time against the state-of-the-art black-box method. Moreover, it provides significant improvements in coreset quality against alternatives with comparable construction times, with far less storage cost and user input required.

Related papers

• Function Space Bayesian Pseudocoreset for Bayesian Neural Networks [16.952160718249292]
  A Bayesian pseudocoreset is a compact synthetic dataset summarizing essential information of a large-scale dataset. In this paper, we propose a novel Bayesian pseudocoreset construction method that operates on a function space. By working directly on the function space, our method could bypass several challenges that may arise when working on a weight space.
  arXiv  Detail & Related papers  (2023-10-27T02:04:31Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• Bayesian Pseudo-Coresets via Contrastive Divergence [5.479797073162603]
  We introduce a novel approach for constructing pseudo-coresets by utilizing contrastive divergence. It eliminates the need for approximations in the pseudo-coreset construction process. We conduct extensive experiments on multiple datasets, demonstrating its superiority over existing BPC techniques.
  arXiv  Detail & Related papers  (2023-03-20T17:13:50Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  We introduce data structures for solving robust regression through gradient descent (SGD) Our algorithm effectively runs $T$ steps of SGD with importance sampling while using sublinear space and just making a single pass over the data.
  arXiv  Detail & Related papers  (2022-07-16T03:09:30Z)
• Posterior Coreset Construction with Kernelized Stein Discrepancy for Model-Based Reinforcement Learning [78.30395044401321]
  We develop a novel model-based approach to reinforcement learning (MBRL) It relaxes the assumptions on the target transition model to belong to a generic family of mixture models. It can achieve up-to 50 percent reduction in wall clock time in some continuous control environments.
  arXiv  Detail & Related papers  (2022-06-02T17:27:49Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  We consider a smooth and strongly convex objective function using a Newton method. We show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage.
  arXiv  Detail & Related papers  (2022-04-20T07:14:21Z)
• Bayesian inference via sparse Hamiltonian flows [16.393322369105864]
  A Bayesian coreset is a small, weighted subset of data that replaces the full dataset during Bayesian inference. Current methods tend to be slow, require a secondary inference step after coreset construction, and do not provide bounds on the data marginal evidence. We introduce a new method -- sparse Hamiltonian flows -- that addresses all three of these challenges.
  arXiv  Detail & Related papers  (2022-03-11T02:36:59Z)
• Nys-Curve: Nystr\"om-Approximated Curvature for Stochastic Optimization [20.189732632410024]
  The quasi-Newton method provides curvature information by approximating the Hessian using the secant equation. We propose an approximate Newton step-based DP optimization algorithm for large-scale empirical risk of convex functions with linear convergence rates.
  arXiv  Detail & Related papers  (2021-10-16T14:04:51Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective [30.963638533636352]
  We propose and analyze a novel algorithm for coreset selection. We provide explicit convergence rate guarantees and present an empirical evaluation on a variety of benchmark datasets.
  arXiv  Detail & Related papers  (2020-07-01T19:34:59Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.