Entropic Herding
- URL: http://arxiv.org/abs/2112.11616v2
- Date: Tue, 9 May 2023 02:41:24 GMT
- Title: Entropic Herding
- Authors: Hiroshi Yamashita, Hideyuki Suzuki, and Kazuyuki Aihara
- Abstract summary: Herding is a deterministic algorithm used to generate data points that can be regarded as random samples.
We propose an extension of the herding algorithm, called entropic herding, which generates a sequence of distributions instead of points.
- Score: 3.039568795810294
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Herding is a deterministic algorithm used to generate data points that can be
regarded as random samples satisfying input moment conditions. The algorithm is
based on the complex behavior of a high-dimensional dynamical system and is
inspired by the maximum entropy principle of statistical inference. In this
paper, we propose an extension of the herding algorithm, called entropic
herding, which generates a sequence of distributions instead of points.
Entropic herding is derived as the optimization of the target function obtained
from the maximum entropy principle. Using the proposed entropic herding
algorithm as a framework, we discuss a closer connection between herding and
the maximum entropy principle. Specifically, we interpret the original herding
algorithm as a tractable version of entropic herding, the ideal output
distribution of which is mathematically represented. We further discuss how the
complex behavior of the herding algorithm contributes to optimization. We argue
that the proposed entropic herding algorithm extends the application of herding
to probabilistic modeling. In contrast to original herding, entropic herding
can generate a smooth distribution such that both efficient probability density
calculation and sample generation become possible. To demonstrate the viability
of these arguments in this study, numerical experiments were conducted,
including a comparison with other conventional methods, on both synthetic and
real data.
Related papers
- Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner [6.408773096179187]
We propose a scalable algorithm for sampling random realizations of the prior and posterior of GP models.
The proposed algorithm leverages inducing points approximation with sparse grids, as well as additive Schwarz preconditioners.
arXiv Detail & Related papers (2024-08-01T00:19:36Z) - Connection between single-layer Quantum Approximate Optimization
Algorithm interferometry and thermal distributions sampling [0.0]
We extend the theoretical derivation of the amplitudes of the eigenstates, and the Boltzmann distributions generated by single-layer QAOA.
We also review the implications that this behavior has from both a practical and fundamental perspective.
arXiv Detail & Related papers (2023-10-13T15:06:58Z) - Adversarial Likelihood Estimation With One-Way Flows [44.684952377918904]
Generative Adversarial Networks (GANs) can produce high-quality samples, but do not provide an estimate of the probability density around the samples.
We show that our method converges faster, produces comparable sample quality to GANs with similar architecture, successfully avoids over-fitting to commonly used datasets and produces smooth low-dimensional latent representations of the training data.
arXiv Detail & Related papers (2023-07-19T10:26:29Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
We show the first tight characterization of the optimal Hessian-dependent sample complexity.
A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances.
The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
arXiv Detail & Related papers (2023-06-21T17:03:22Z) - Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise.
In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
arXiv Detail & Related papers (2023-06-13T01:18:16Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications.
This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
arXiv Detail & Related papers (2023-01-30T15:46:39Z) - An Algebraically Converging Stochastic Gradient Descent Algorithm for
Global Optimization [14.336473214524663]
A key component in the algorithm is the randomness based on the value of the objective function.
We prove the convergence of the algorithm with an algebra and tuning in the parameter space.
We present several numerical examples to demonstrate the efficiency and robustness of the algorithm.
arXiv Detail & Related papers (2022-04-12T16:27:49Z) - A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective.
We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
arXiv Detail & Related papers (2021-10-07T17:51:10Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data.
We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem.
In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
arXiv Detail & Related papers (2020-06-11T19:40:38Z) - Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
We consider distributed optimization problems where forming the Hessian is computationally challenging and communication is a bottleneck.
We develop unbiased parameter averaging methods for randomized second order optimization that employ sampling and sketching of the Hessian.
We also extend the framework of second order averaging methods to introduce an unbiased distributed optimization framework for heterogeneous computing systems.
arXiv Detail & Related papers (2020-02-16T09:01:18Z)
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.