Convergence of Expectation-Maximization Algorithm with Mixed-Integer Optimization

• URL: http://arxiv.org/abs/2401.17763v2
• Date: Wed, 17 Apr 2024 11:03:36 GMT
• Title: Convergence of Expectation-Maximization Algorithm with Mixed-Integer Optimization
• Authors: Geethu Joseph,
• Abstract summary: This paper introduces a set of conditions that ensure the convergence of a specific class of EM algorithms. Our results offer a new analysis technique for iterative algorithms that solve mixed-integer non-linear optimization problems.
• Score: 5.319361976450982
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The convergence of expectation-maximization (EM)-based algorithms typically requires continuity of the likelihood function with respect to all the unknown parameters (optimization variables). The requirement is not met when parameters comprise both discrete and continuous variables, making the convergence analysis nontrivial. This paper introduces a set of conditions that ensure the convergence of a specific class of EM algorithms that estimate a mixture of discrete and continuous parameters. Our results offer a new analysis technique for iterative algorithms that solve mixed-integer non-linear optimization problems. As a concrete example, we prove the convergence of the EM-based sparse Bayesian learning algorithm in [1] that estimates the state of a linear dynamical system with jointly sparse inputs and bursty missing observations. Our results establish that the algorithm in [1] converges to the set of stationary points of the maximum likelihood cost with respect to the continuous optimization variables.

Related papers

• On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights [0.0]
  We revisit the framework introduced by Fazylab et al. to construct Lyapunov functions for optimization algorithms in discrete and continuous time. For smooth, strongly convex objective functions, we relax the requirements necessary for such a construction. We prove convergence rates that improve on those available in the literature.
  arXiv  Detail & Related papers  (2023-05-15T14:03:16Z)
• n-Step Temporal Difference Learning with Optimal n [5.945710235932345]
  We consider the problem of finding the optimal value of n in the n-step temporal difference (TD) learning. Our objective function for the optimization problem is the average root mean squared error (RMSE)
  arXiv  Detail & Related papers  (2023-03-13T12:44:32Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• 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)
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
  We develop a general recipe for analyzing the convergence of iterative algorithms for a class of regression models. deterministicly, we accurately capture both the convergence rate of the algorithm and the eventual error floor in the finite-sample regime. We show sharp convergence rates for both higher-order algorithms based on alternating updates and first-order algorithms based on subgradient subgradients.
  arXiv  Detail & Related papers  (2021-09-20T21:48:19Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity with bounds dependence on the confidence level that is either negative-power or logarithmic. We propose novel stepsize rules for two gradient methods with clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives [97.16266088683061]
  The article rigorously establishes why symplectic discretization schemes are important for momentum-based optimization algorithms. It provides a characterization of algorithms that exhibit accelerated convergence.
  arXiv  Detail & Related papers  (2020-02-28T00:32:47Z)

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.