SKM 2023 – wissenschaftliches Programm
DY 11: Focus Session: Physics Meets ML II – Understanding Machine Learning as Complex Interacting Systems (joint session DY/TT)
DY 11.5: Hauptvortrag
Montag, 27. März 2023, 17:00–17:30, ZEU 250
Analysing the dynamics of message passing algorithms — •Manfred Opper1,2 and Burak Cakmak1 — 1Institut für Softwaretechnik und Theoretische Informatik, Technische Universität Berlin, 10587, Germany — 2Centre for Systems Modelling and Quantitative Biomedicine, University of Birmingham, B15 2TT, United Kingdom
Message passing algorithms are deterministic methods which are designed for efficiently computing marginal statistics for probabilistic, Bayesian data models used in machine learning and statistics. Such algorithms have been developed in parallel within the machine learning and the statistical physics communities. They often provide highly accurate approximations at a much higher speed compared to exact Monte Carlo sampling. The fixed points of such algorithms can be analysed for high dimensional models (under the assumption of specific data distributions) using the replica method of statistical physics. In this talk we will focus on the dynamical properties of the algorithms. Applying dynamical functional techniques to the nonlinear dynamics, the degrees of freedom which interact via a random matrix can be decoupled in the limit of large systems resulting in exact stochastic single node dynamics. For general dynamical models, it is hard to further analyse this effective dynamics due to the occurence of memory terms. Surprisingly, for message passing algorithms memory terms are absent and exact results for convergence rates and stability can be derived for specific data distributions.