Exact solution to the random sequential dynamics of a message passing algorithm

• URL: http://arxiv.org/abs/2101.01571v2
• Date: Tue, 2 Mar 2021 20:09:56 GMT
• Title: Exact solution to the random sequential dynamics of a message passing algorithm
• Authors: Burak \c{C}akmak and Manfred Opper
• Abstract summary: We analyze the random sequential dynamics of a message passing algorithm for Ising models with random interactions in the large system limit. The em de Almedia-Thouless stability criterion of the static problem is found to be necessary and sufficient for the global convergence of the random sequential dynamics.
• Score: 4.066211670342284
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyze the random sequential dynamics of a message passing algorithm for Ising models with random interactions in the large system limit. We derive exact results for the two-time correlation functions and the speed of convergence. The {\em de Almedia-Thouless} stability criterion of the static problem is found to be necessary and sufficient for the global convergence of the random sequential dynamics.

Related papers

• Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems [2.66854711376491]
  Proposed dynamics are based on the proximal augmented Lagrangian. We leverage various structural properties to establish global (exponential) convergence guarantees. Our assumptions are much weaker than those required to prove (exponential) stability of various primal-dual dynamics.
  arXiv  Detail & Related papers  (2024-08-28T17:43:18Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Analysis of Random Sequential Message Passing Algorithms for Approximate Inference [18.185200593985844]
  We analyze the dynamics of a random sequential message passing algorithm for approximate inference with large Gaussian latent variable models. We derive a range of model parameters for which the sequential algorithm does not converge.
  arXiv  Detail & Related papers  (2022-02-16T17:16:22Z)
• 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)
• Stability and Identification of Random Asynchronous Linear Time-Invariant Systems [81.02274958043883]
  We show the additional benefits of randomization and asynchrony on the stability of linear dynamical systems. For unknown randomized LTI systems, we propose a systematic identification method to recover the underlying dynamics.
  arXiv  Detail & Related papers  (2020-12-08T02:00:04Z)
• A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions [17.14287157979558]
  We propose an adaptively weighted gradient Langevin dynamics (SGLD) for learning in big data statistics. The proposed algorithm is tested on benchmark datasets including CIFAR100.
  arXiv  Detail & Related papers  (2020-10-19T19:20:47Z)
• 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)
• A Dynamical Mean-Field Theory for Learning in Restricted Boltzmann Machines [2.8021833233819486]
  We define a message-passing algorithm for computing magnetizations in Boltzmann machines. We prove the global convergence of the algorithm under a stability criterion and compute convergence rates showing excellent agreement with numerical simulations.
  arXiv  Detail & Related papers  (2020-05-04T15:19:31Z)
• 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.