Local convexity of the TAP free energy and AMP convergence for Z2-synchronization

Abstract

We study mean-field variational Bayesian inference using the TAP approach, for Z2-synchronization as a prototypical example of a high-dimensional Bayesian model. We show that for any signal strength $\lambda >1$ (the weak-recovery threshold), there exists a unique local minimizer of the TAP free energy functional near the mean of the Bayes posterior law. Furthermore, the TAP free energy in a local neighborhood of this minimizer is strongly convex. Consequently, a natural-gradient/mirror-descent algorithm achieves linear convergence to this minimizer from a local initialization, which may be obtained by a constant number of iterates of Approximate Message Passing (AMP). This provides a rigorous foundation for variational inference in high dimensions via minimization of the TAP free energy. We also analyze the finite-sample convergence of AMP, showing that AMP is asymptotically stable at the TAP minimizer for any $\lambda >1$, and is linearly convergent to this minimizer from a spectral initialization for sufficiently large $\lambda$. Such a guarantee is stronger than results obtainable by state evolution analyses, which only describe a fixed number of AMP iterations in the infinite-sample limit. Our proofs combine the Kac-Rice formula and Sudakov-Fernique Gaussian comparison inequality to analyze the complexity of critical points that satisfy strong convexity and stability conditions within their local neighborhoods.

62 pages

References in corpus (9)

• Edward: A library for probabilistic modeling, inference, and criticism
• A framework to characterize performance of LASSO algorithms
• Asymptotic normality and valid inference for Gaussian variational approximation
• The Lasso with general Gaussian designs with applications to hypothesis testing
• The Loss Surfaces of Neural Networks with General Activation Functions
• A spin-glass model for the loss surfaces of generative adversarial networks
• The replica-symmetric free energy for Ising spin glasses with orthogonally invariant couplings
• Variational Inference in high-dimensional linear regression
• Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction

Cited by in corpus (2)

• Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization
• Minimum ${\ell }_1$-norm interpolators: Precise asymptotics and multiple descent