Spectral Approximate Inference
This work addresses the challenge of poor approximations and non-convergence in iterative methods for graphical model inference, particularly in hard instances like low-temperature regimes, offering a more reliable solution for practitioners in machine learning and statistics.
The authors tackled the computationally intractable problem of approximating the partition function in graphical models by proposing a novel spectral approach, which includes an FPTAS for low-rank coupling matrices and a spectral mean-field scheme for high-rank cases, resulting in improved robustness in running time and accuracy without convergence issues.
Given a graphical model (GM), computing its partition function is the most essential inference task, but it is computationally intractable in general. To address the issue, iterative approximation algorithms exploring certain local structure/consistency of GM have been investigated as popular choices in practice. However, due to their local/iterative nature, they often output poor approximations or even do not converge, e.g., in low-temperature regimes (hard instances of large parameters). To overcome the limitation, we propose a novel approach utilizing the global spectral feature of GM. Our contribution is two-fold: (a) we first propose a fully polynomial-time approximation scheme (FPTAS) for approximating the partition function of GM associating with a low-rank coupling matrix; (b) for general high-rank GMs, we design a spectral mean-field scheme utilizing (a) as a subroutine, where it approximates a high-rank GM into a product of rank-1 GMs for an efficient approximation of the partition function. The proposed algorithm is more robust in its running time and accuracy than prior methods, i.e., neither suffers from the convergence issue nor depends on hard local structures, as demonstrated in our experiments.