Approximate Survey Propagation for Statistical Inference - Archive ouverte HAL Access content directly
Journal Articles Journal of Statistical Mechanics: Theory and Experiment Year : 2019

Approximate Survey Propagation for Statistical Inference

(1, 2) , (3, 4) , (1) , (1)
1
2
3
4

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 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. Contents
Fichier principal
Vignette du fichier
approximate_survey.pdf (1.47 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

cea-01933008 , version 1 (23-11-2018)

Identifiers

Cite

Fabrizio Antenucci, Florent Krzakala, Pierfrancesco Urbani, Lenka Zdeborová. Approximate Survey Propagation for Statistical Inference. Journal of Statistical Mechanics: Theory and Experiment, 2019, 2019, pp.023401. ⟨10.1088/1742-5468/aafa7d⟩. ⟨cea-01933008⟩
100 View
180 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More