Deterministic Approximate EM Algorithm; Application to the Riemann Approximation EM and the Tempered EM

• URL: http://arxiv.org/abs/2003.10126v3
• Date: Mon, 2 May 2022 11:55:32 GMT
• Title: Deterministic Approximate EM Algorithm; Application to the Riemann Approximation EM and the Tempered EM
• Authors: Thomas Lartigue (ARAMIS, CMAP), Stanley Durrleman (ARAMIS), St\'ephanie Allassonni\`ere (CRC)
• Abstract summary: We introduce a theoretical framework, with state-of-the-art convergence guarantees, for any deterministic approximation of the E step. We analyse theoretically and empirically several approximations that fit into this framework, for intractable E-steps. We showcase how new non-studied profiles can more successfully escape adversarial initialisations.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Expectation Maximisation (EM) algorithm is widely used to optimise non-convex likelihood functions with latent variables. Many authors modified its simple design to fit more specific situations. For instance, the Expectation (E) step has been replaced by Monte Carlo (MC), Markov Chain Monte Carlo or tempered approximations, etc. Most of the well-studied approximations belong to the stochastic class. By comparison, the literature is lacking when it comes to deterministic approximations. In this paper, we introduce a theoretical framework, with state-of-the-art convergence guarantees, for any deterministic approximation of the E step. We analyse theoretically and empirically several approximations that fit into this framework. First, for intractable E-steps, we introduce a deterministic version of MC-EM using Riemann sums. A straightforward method, not requiring any hyper-parameter fine-tuning, useful when the low dimensionality does not warrant a MC-EM. Then, we consider the tempered approximation, borrowed from the Simulated Annealing literature and used to escape local extrema. We prove that the tempered EM verifies the convergence guarantees for a wider range of temperature profiles than previously considered. We showcase empirically how new non-trivial profiles can more successfully escape adversarial initialisations. Finally, we combine the Riemann and tempered approximations into a method that accomplishes both their purposes.

Related papers

• Rethinking Approximate Gaussian Inference in Classification [25.021782278452005]
  In classification tasks, softmax functions are ubiquitously used to produce predictive probabilities. We propose a simple change in the learning objective which allows the exact computation of predictives. We evaluate our approach combined with several approximate Gaussian inference methods on large- and small-scale datasets.
  arXiv  Detail & Related papers  (2025-02-05T17:03:49Z)
• Riemannian Federated Learning via Averaging Gradient Stream [8.75592575216789]
  This paper develops and analyzes an efficient Federated Averaging Gradient Stream (RFedAGS) algorithm. Numerical simulations conducted on synthetic and real-world data demonstrate the performance of the proposed RFedAGS.
  arXiv  Detail & Related papers  (2024-09-11T12:28:42Z)
• On the Approximability of Stationary Processes using the ARMA Model [1.8008841825105588]
  We use the spectral lemma to connect function approximation on the unit circle to random variable approximation. Our results focus on approximation error of the random variable rather than the prediction error as in some classical infimum results by Szego, Kolmogorov, and Wiener.
  arXiv  Detail & Related papers  (2024-08-20T07:42:42Z)
• Iterative Methods for Full-Scale Gaussian Process Approximations for Large Spatial Data [9.913418444556486]
  We show how iterative methods can be used to reduce computational costs in calculating likelihoods, gradients, and predictive distributions with full-scale approximations (FSAs)<n>We introduce a novel preconditioner and show theoretically and empirically that it accelerates the conjugate gradient method's convergence speed and mitigates its sensitivity with respect to the FSA parameters.<n>In our experiments, it outperforms existing state-of-the-art preconditioners for Vecchia approximations.
  arXiv  Detail & Related papers  (2024-05-23T12:25:22Z)
• Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
  We study infinite-horizon average-reward Markov decision processes (AMDPs) in the context of general function approximation. We propose a novel algorithmic framework named Local-fitted Optimization with OPtimism (LOOP) We show that LOOP achieves a sublinear $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret, where $d$ and $beta$ correspond to AGEC and log-covering number of the hypothesis class respectively
  arXiv  Detail & Related papers  (2024-04-19T06:24:22Z)
• Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction [4.578425862931332]
  This study focuses on the crucial reduction mechanism used in both Euclidean and Riemannian settings. Motivated by Euclidean methods, we introduce R-based methods to replace the outer loop with computation triggered by a coin flip. Using R- as a framework, we demonstrate its applicability to various important settings.
  arXiv  Detail & Related papers  (2024-03-11T12:49:37Z)
• Riemannian Laplace Approximation with the Fisher Metric [5.982697037000189]
  Laplace's method approximates a target density with a Gaussian distribution at its mode. For complex targets and finite-data posteriors it is often too crude an approximation. We develop two alternative variants that are exact at the limit of infinite data.
  arXiv  Detail & Related papers  (2023-11-05T20:51:03Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  We show that policies under study avoid strict saddle points / submanifolds with probability 1. This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
  arXiv  Detail & Related papers  (2023-11-04T11:12:24Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• A Unified Convergence Theorem for Stochastic Optimization Methods [4.94128206910124]
  We provide a fundamental unified convergence theorem used for deriving convergence results for a series of unified optimization methods. As a direct application, we recover almost sure convergence results under general settings.
  arXiv  Detail & Related papers  (2022-06-08T14:01:42Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)

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.