Name
Abstract | ||
|---|---|---|
Approximate message passing algorithm enjoyed considerable attention in the last decade. In this paper we introduce a variant of the AMP algorithm that takes into account glassy nature of the system under consideration. We coin this algorithm as the approximate survey propagation (ASP) and derive it for a class of low-rank matrix estimation problems. We derive the state evolution for the ASP algorithm and prove that it reproduces the one-step replica symmetry breaking (1RSB) fixed-point equations, well-known in physics of disordered systems. Our derivation thus gives a concrete algorithmic meaning to the 1RSB equations that is of independent interest. We characterize the performance of ASP in terms of convergence and mean-squared error as a function of the free Parisi parameter s. We conclude that when there is a model mismatch between the true generative model and the inference model, the performance of AMP rapidly degrades both in terms of MSE and of convergence, while for well-chosen values of the Parisi parameter s ASP converges in a larger regime and can reach lower errors. Among other results, our analysis leads us to a striking hypothesis that whenever s (or other parameters) can be set in such a way that the Nishimori condition M = Q > 0 is restored, then the corresponding algorithm is able to reach mean-squared error as low as the Bayes-optimal error obtained when the model and its parameters are known and exactly matched in the inference procedure. The remaining drawback is that we have not found a procedure that would systematically find a value of s leading to such low errors, this is a challenging problem let for future work. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1088/1742-5468/aafa7d | JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT |
Keywords | Field | DocType |
message-passing algorithms,statistical inference,analysis of algorithms | Convergence (routing),Applied mathematics,Replica,Symmetry breaking,Inference,Quantum mechanics,Survey propagation,Statistical inference,Message passing,Mathematics,Generative model | Journal |
Volume | ISSN | Citations |
abs/1807.01296 | 1742-5468 | 1 |
PageRank | References | Authors |
0.36 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabrizio Antenucci | 1 | 1 | 0.36 |
| Florent Krzakala | 2 | 977 | 67.30 |
| Pierfrancesco Urbani | 3 | 1 | 2.72 |
| Lenka Zdeborová | 4 | 1190 | 78.62 |