A Bregman ADMM for Bethe variational problem

Yuehaw Khoo, Tianyun Tang, Kim-Chuan Toh · 2025

Read A Bregman ADMM for Bethe variational problem by Yuehaw Khoo, Tianyun Tang, Kim-Chuan Toh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-04613.txt.

Introduction

Yuehaw Khoo and co-authors built a solver for the Bethe problem in two thousand twenty-five. The Bethe problem sits at the heart of graph models. It is not convex and misbehaves near its edge. Standard solvers lack firm proof they will settle there. Their method mixes Bregman steps with split updates. A new kind of dual update is the core twist.

The team proves best points keep all entries above zero. That fact smooths the edge where trouble starts. Proof of settling follows even without convexity. Sub-tasks split well for parallel machines. A quantum form of the problem is covered too. Number tests confirmed the method holds up well. Code was shared openly for other teams.

Catalog record

CREATORYuehaw Khoo, Tianyun Tang, Kim-Chuan Toh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE139 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-04613

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Bregman ADMM for Bethe variational problem Yuehaw Khoo, Tianyun Tang, Kim-Chuan Toh Abstract In this work, we propose a novel Bregman ADMM with nonlinear dual update to solve the Bethe variational problem (BVP), a key optimization formulation in graphical models and statistical physics. Our algorithm provides rigorous convergence guarantees, even if the objective function of BVP is non-convex and non-Lipschitz continuous on the boundary. A central result of our analysis is proving that the entries in local minima of BVP are strictly positive, effectively resolving non-smoothness issues caused by zero entries. Beyond theoretical guarantees, the algorithm possesses high level of separability and parallelizability to achieve highly efficient subproblem computation. Our Bregman ADMM can be easily extended to solve the quantum Bethe variational problem. Numerical experiments are conducted to validate the effectiveness and robustness of the proposed method. Based on this research, we have released an open-source package of the proposed method at https://github.com/TTYmath/BADMM-BVP . 1 Introduction 1.1 Graphical model and belief propagation Graphical model [ 34 ] is a powerful framework for representing multivariate distributions, with a graph encoding the dependency structure among variables. It has applications in many fields including scientific computing [ 59 ] , machine learning [ 6 ] and statistical physics [ 58 ] . A key challenge in graphical models is probabilistic inference, which we describe in the next paragraph. For a simple undirected connected graph G=([n],\mathcal{E}) , consider a pairwise Markov random field (MRF) with the joint probability distribution function given by P(x_{1},x_{2},\ldots,x_{n})=\frac{1}{Z}\prod_{ij\in\mathcal{E}}\Psi_{ij}(x_{i},x_{j})\prod_{k\in[n]}\Psi_{k}(x_{k}), (1) where x_{k} is the state of node k with r possible values, \Psi_{ij}(x_{i},x_{j}) and \Psi_{k}(x_{k}) are potential functions, and Z is a normalization constant. The goal of probabilistic inference is to determine the marginal distribution of a single random variable x_{k} . While the marginal distribution can be computed directly by summing over all other variables, this approach is generally NP-hard [ 16 ] due to the exponential growth in the state space as n increases. Belief propagation. In 1988, Pearl introduced belief propagation (BP) [ 57 ] as an approximate method to solve the probabilistic inference problem. For each edge ij (In this paper, we assume i<j when referring to ij\in\mathcal{E} .) in \mathcal{E} , BP defines message variables m_{i\rightarrow j}(x_{j}) and m_{j\rightarrow i}(x_{i}) , which are updated as follows: \displaystyle m_{i\rightarrow j}(x_{j})\leftarrow\frac{1}{z_{i,j}}\sum_{x_{i}\in[r]}\Psi_{ij}(x_{i},x_{j})\Psi_{i}(x_{i})\prod_{k\in N(i)\setminus\{j\}}m_{k\rightarrow i}(x_{i}), (2) \displaystyle m_{j\rightarrow i}(x_{i})\leftarrow\frac{1}{z_{j,i}}\sum_{x_{j}\in[r]}\Psi_{ij}(x_{i},x_{j})\Psi_{j}(x_{j})\prod_{k\in N(j)\setminus\{i\}}m_{k\rightarrow j}(x_{j}), (3) where z_{i,j} and z_{j,i} are normalization constants that prevent the messages from diverging. This iterative process can be interpreted as passing messages along the network until convergence to a fixed point. Using these messages, the marginal distributions are approximated as: \displaystyle b_{k}(x_{k}):=\frac{1}{\hat{z}_{k}}\Psi_{k}(x_{k})\prod_{i\in N(k)}m_{i\rightarrow k}(x_{k}), (4) \displaystyle b_{i,j}(x_{i},x_{j}):=\frac{1}{\bar{z}_{i,j}}\Psi_{ij}(x_{i},x_{j})\prod_{k\in N(i)\setminus\{j\}}m_{k\rightarrow i}(x_{i})\prod_{k\in N(j)\setminus\{i\}}m_{k\rightarrow j}(x_{j}), (5) where \hat{z}_{k} and \bar{z}_{i,j} are normalization constants ensuring that b_{k} and b_{i,j} are valid probability distributions. The approximations b_{k} and b_{i,j} , often referred to as beliefs, provide estimates of the marginal distributions of the joint probability P . For tree-structured graphs, BP is guaranteed to converge to the exact marginal distributions in a finite number of iterations. However, for graphs with cycles, convergence is not guaranteed [ 54 ] . Nevertheless, BP often performs remarkably well as a heuristic in practice and has been successfully applied in various domains [ 1 , 47 , 53 ] . 1.2 Bethe variational problem The practical success of BP has inspired extensive theoretical investigations. Yedidia, Freeman, and Weiss achieved a key breakthrough in their seminal works [ 83 , 84 , 82 ] , where they demonstrated that the fixed points of BP correspond to the critical points of the following Bethe variational problem (BVP) [ 73 ] : \displaystyle\min\Bigg\{ \displaystyle\sum_{ij\in\mathcal{E}}\sum_{x_{i},x_{j}\in[r]}b_{ij}(x_{i},x_{j})\ln\frac{b_{ij}(x_{i},x_{j})}{\Psi_{ij}(x_{i},x_{j})b_{i}(x_{i})b_{j}(x_{j})}+\sum_{k\in V}\sum_{x_{k}\in[r]}b_{k}(x_{k})\ln\frac{b_{k}(x_{k})}{\Psi_{k}(x_{k})}: (6) \displaystyle\forall k\in[n],\sum_{x_{k}\in[r]}b_{k}(x_{k})=1,\ \forall ij\in\mathcal{E},\ \sum_{x_{j}\in[r]}b_{ij}(x_{i},x_{j})=b_{i}(x_{i}),\ \sum_{x_{i}\in[r]}b_{ij}(x_{i},x_{j})=b_{j}(x_{j})\Bigg\}, where b_{k} and b_{ij} are the beliefs satisfying normalization and marginalization constraints. The objective function in ( 6 ), known as the Bethe free energy (BFE), was introduced by Hans Bethe in 1935 [ 8 ] . It serves as a powerful approximation tool in statistical physics [ 46 ] , simplifying the computation of free energy in systems where exact calculations are computationally infeasible. Alternatively, the BFE can be interpreted as the Kullback-Leibler (KL) divergence [ 32 ] between a tree-like probability distribution \frac{\prod_{ij\in\mathcal{E}}b_{ij}(x_{i},x_{j})}{\prod_{k\in[n]}b_{k}(x_{k})^{d_{k}-1}}, (7) where d_{k}:=|N(k)| is the degree of vertex k , and the joint distribution in ( 1 ). Since general probability distributions may not adhere to the form in ( 7 ), the minimizer of ( 6 )—and by extension, the output of the BP algorithm—provides only an approximation to the original probabilistic inference problem. BP can be viewed as a fixed-point method applied to the Karush-Kuhn-Tucker (KKT) conditions of ( 6 ), with the message variables corresponding to the Lagrange multipliers for the marginal constraints. The connection between BP and ( 6 ) offers an alternative approach to finding a fixed point of BP by directly solving the optimization problem ( 6 ) and obtaining its stationary point. However, one important limitation of the earlier works by Yedidia et al. [ 83 , 84 , 82 ] is that they considered only the variables b_{ij} and b_{k} with strictly positive entries, thereby ignoring boundary points in the feasible set of ( 6 ). If the minimizer of ( 6 ) contains zero entries, it cannot serve as a fixed point for BP. However, boundary points cannot be disregarded when solving ( 6 ), as the non-convexity makes it challenging to ensure that local minima will not have zero entries. Furthermore, zero entries pose significant challenges for optimization algorithms because the objective function is not Lipschitz-continuous on the boundary. This observation motivates the following question: Question 1.1 . Do the local minima of ( 6 ) have only positive entries? In Section 2 , we provide a positive answer to Question 1.1 by demonstrating that the entries of all local minima are bounded below by a positive constant, which depends only on the coefficients in ( 6 ). Our result not only addresses a gap in the theoretical analysis of the aforementioned works but is also critical for algorithmic design and convergence analysis, as it helps overcome the non-smoothness issue on the boundary of ( 6 ). In the next subsection, we summarize several classical algorithms for solving ( BVP ) and introduce our new algorithm, which offers several advantageous properties. 1.3 Algorithms for Bethe variational problem In this subsection, we present algorithms for solving ( BVP ), starting with a discussion of several classical approaches. Gradient descent method. Welling and Teh [ 78 ] proposed a gradient descent (GD) method to find a stationary point of ( BVP ) for binary MRFs. The key insight is that for r=2 , problem ( BVP ) can be reformulated as an unconstrained optimization problem with n variables, allowing GD to be applied. Shin refined this approach in [ 66 , 67 ] to get a polynomial time complexity bound for graphs with maximum degree \mathcal{O}(\log n) . Additionally, Leisenberger et al. [ 36 ] extended this idea using a projected quasi-Newton method to exploit second-order information. For binary pairwise MRFs with submodular cost functions, global minimizers of ( BVP ) have been explored using GD [ 77 ] . Despite its theoretical soundness,

Read the complete text