Fast convergence to an approximate solution by message-passing for complex optimizations

Abstract

Message-passing (MP) is a powerful tool for finding an approximate solution in optimization. We generalize it to nonlinear product-sum form, and numerically show the fast convergence for the minimum feedback vertex set and the minimum vertex cover known as NP-hard problems. From the linearity of MP in a logarithmic space, it is derived that an equilibrium solution exists in a neighborhood of random initial values. These results will give one of the reason why the convergence is very fast in collective computation based on a common mathematical background.

24 pages, 5 figures, 3 tables

References in corpus (9)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• The Bethe lattice spin glass revisited
• Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent
• Spin glass approach to the feedback vertex set problem
• Message passing for vertex covers
• Message passing methods on complex networks
• A loop enhancement strategy for network robustness
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• Target observation of complex networks