Vector Approximate Survey Propagation for Model-Mismatched Estimation (Or: How to Achieve Kabashima's 1RSB Prediction)

For approximate inference in high-dimensional generalized linear models (GLMs), the performance of an estimator may significantly degrade when mismatch exists between the postulated model and the ground truth. In mismatched GLMs with rotation-invariant measurement matrices, Kabashima et al. proved vector approximate message passing (VAMP) computes exactly the optimal estimator if the replica symmetry (RS) ansatz is valid, but it becomes inappropriate if RS breaking (RSB) appears. Although the one-step RSB (1RSB) saddle point equations were given for the optimal estimator, the question remains: how to achieve the 1RSB prediction? This paper answers the question by proposing a new algorithm, vector approximate survey propagation (VASP). VASP derives from a reformulation of Kabashima's extremum conditions, which later links the theoretical equations to survey propagation in vector form and finally the algorithm. VASP has a complexity as low as VAMP, while embracing VAMP as a special case. The SE derived for VASP can capture precisely the per-iteration behavior of the simulated algorithm, and the SE's fixed point equations perfectly match Kabashima's 1RSB prediction, which indicates VASP can achieve the optimal performance even in a model-mismatched setting with 1RSB. Simulation results confirm VASP outperforms many state-of-the-art algorithms.