Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective

• URL: http://arxiv.org/abs/2007.00715v2
• Date: Thu, 25 Feb 2021 22:04:24 GMT
• Title: Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective
• Authors: Jacky Y. Zhang, Rajiv Khanna, Anastasios Kyrillidis, Oluwasanmi Koyejo
• Abstract summary: 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.
• Score: 30.963638533636352
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bayesian coresets have emerged as a promising approach for implementing scalable Bayesian inference. The Bayesian coreset problem involves selecting a (weighted) subset of the data samples, such that the posterior inference using the selected subset closely approximates the posterior inference using the full dataset. This manuscript revisits Bayesian coresets through the lens of sparsity constrained optimization. Leveraging recent advances in accelerated optimization methods, 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 to highlight our proposed algorithm's superior performance compared to state-of-the-art on speed and accuracy.

Related papers

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Exploration [2.984929040246293]
  novel noise-free Bayesian optimization strategies that rely on a random exploration step to enhance the accuracy of Gaussian process surrogate models. New algorithms retain the ease of implementation of the classical GP-UCB, but an additional exploration step facilitates their convergence.
  arXiv  Detail & Related papers  (2024-01-30T14:16:06Z)
• Random Postprocessing for Combinatorial Bayesian Optimization [0.552480439325792]
  We numerically study the effect of a postprocessing method on Bayesian optimization. We find the postprocessing method significantly reduces the number of sequential steps to find the global optimum.
  arXiv  Detail & Related papers  (2023-09-06T08:59:34Z)
• Black-box Coreset Variational Inference [13.892427580424444]
  We present a black-box variational inference framework for coresets to enable principled application of variational coresets to intractable models. We apply our techniques to supervised learning problems, and compare them with existing approaches in the literature for data summarization and inference.
  arXiv  Detail & Related papers  (2022-11-04T11:12:09Z)
• On Divergence Measures for Bayesian Pseudocoresets [28.840995981326028]
  A Bayesian pseudocoreset is a small synthetic dataset for which the posterior over parameters approximates that of the original dataset. This paper casts two representative dataset distillation algorithms as approximations to methods for constructing pseudocoresets. We provide a unifying view of such divergence measures in Bayesian pseudocoreset construction.
  arXiv  Detail & Related papers  (2022-10-12T13:45:36Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Fast Bayesian Coresets via Subsampling and Quasi-Newton Refinement [15.426481600285728]
  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.
  arXiv  Detail & Related papers  (2022-03-18T01:04:39Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)

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.