Sinkhorn EM: An Expectation-Maximization algorithm based on entropic optimal transport

• URL: http://arxiv.org/abs/2006.16548v1
• Date: Tue, 30 Jun 2020 06:03:37 GMT
• Title: Sinkhorn EM: An Expectation-Maximization algorithm based on entropic optimal transport
• Authors: Gonzalo Mena, Amin Nejatbakhsh, Erdem Varol and Jonathan Niles-Weed
• Abstract summary: Sinkhorn EM (sEM) is a variant of the expectation (EM) algorithm for mixtures based on entropic optimal transport. We show theoretically and empirically that sEM has better behavior than EM.
• Score: 11.374487003189467
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study Sinkhorn EM (sEM), a variant of the expectation maximization (EM) algorithm for mixtures based on entropic optimal transport. sEM differs from the classic EM algorithm in the way responsibilities are computed during the expectation step: rather than assign data points to clusters independently, sEM uses optimal transport to compute responsibilities by incorporating prior information about mixing weights. Like EM, sEM has a natural interpretation as a coordinate ascent procedure, which iteratively constructs and optimizes a lower bound on the log-likelihood. However, we show theoretically and empirically that sEM has better behavior than EM: it possesses better global convergence guarantees and is less prone to getting stuck in bad local optima. We complement these findings with experiments on simulated data as well as in an inference task involving C. elegans neurons and show that sEM learns cell labels significantly better than other approaches.

Related papers

• A note on the relations between mixture models, maximum-likelihood and entropic optimal transport [6.246185995463311]
  We show that performing maximum-likelihood estimation for a mixture model is equivalent to minimizing over the parameters an optimal transport problem with entropic regularization.
  arXiv  Detail & Related papers  (2025-01-21T09:55:21Z)
• Learning Mixtures of Experts with EM [28.48469221248906]
  Mixtures of Experts (MoE) are Machine Learning models that involve the input space, with a separate "expert" model trained on each partition. We study the efficiency of the Expectation Maximization (EM) algorithm for the training of MoE models.
  arXiv  Detail & Related papers  (2024-11-09T03:44:09Z)
• Network EM Algorithm for Gaussian Mixture Model in Decentralized Federated Learning [1.4549461207028445]
  We study various network Expectation-Maximization (EM) algorithms for the Gaussian mixture model. We introduce a momentum network EM (MNEM) algorithm, which uses a momentum parameter to combine information from both the current and historical estimators. We also develop a semi-supervised MNEM algorithm, which leverages partially labeled data.
  arXiv  Detail & Related papers  (2024-11-08T14:25:46Z)
• Big Learning Expectation Maximization [13.709094150105566]
  We present the Big Learning EM (BigLearn-EM), an EM upgrade that simultaneously performs joint, marginal, and orthogonally transformed marginal matchings. We empirically show that the BigLearn-EM is capable of delivering the optimal with high probability.
  arXiv  Detail & Related papers  (2023-12-19T08:07:41Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Sampling with Mollified Interaction Energy Descent [57.00583139477843]
  We present a new optimization-based method for sampling called mollified interaction energy descent (MIED) MIED minimizes a new class of energies on probability measures called mollified interaction energies (MIEs) We show experimentally that for unconstrained sampling problems our algorithm performs on par with existing particle-based algorithms like SVGD.
  arXiv  Detail & Related papers  (2022-10-24T16:54:18Z)
• Improvements to Supervised EM Learning of Shared Kernel Models by Feature Space Partitioning [0.0]
  This paper addresses the lack of rigour in the derivation of the EM training algorithm and the computational complexity of the technique. We first present a detailed derivation of EM for the Gaussian shared kernel model PRBF classifier. To reduce complexity of the resulting SKEM algorithm, we partition the feature space into $R$ non-overlapping subsets of variables.
  arXiv  Detail & Related papers  (2022-05-31T09:18:58Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  We optimize the information-theoretical generalization bound by manipulating the noise structure in SGLD. We prove that with constraint to guarantee low empirical risk, the optimal noise covariance is the square root of the expected gradient covariance.
  arXiv  Detail & Related papers  (2021-10-26T15:02:27Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)

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.