Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLocal convexity of the TAP free energy and AMP convergence for Z2-synchronization
94
0
0.0
(
0
)
Added by
Song Mei
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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 finite 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.
rate research
Read More
The cavity and TAP equations are high-dimensional systems of nonlinear equations of the local magnetization in the Sherrington-Kirkpatrick model. In the seminal work [Comm. Math. Phys., 325(1):333-366, 2014], Bolthausen introduced an iterative scheme that produces an asymptotic solution to the TAP equations if the model lies inside the Almeida-Thouless transition line. However, it was unclear if this asymptotic solution coincides with the local magnetization. In this work, motivated by the cavity equations, we introduce a new iterative scheme and establish a weak law of large numbers. We show that our new scheme is asymptotically the same as the so-called Approximate Message Passing algorithm, a generalization of Bolthausens iteration, that has been popularly adapted in compressed sensing, Bayesian inferences, etc. Based on this, we confirm that our cavity iteration and Bolthausens scheme both converge to the local magnetization as long as the overlap is locally uniformly concentrated.
We consider the mixed $p$-spin mean-field spin glass model with Ising spins and investigate its free energy in the spirit of the TAP approach, named after Thouless, Anderson, and Palmer. More precisely, we define and compute the generalized TAP correction, and establish the corresponding generalized TAP representation for the free energy. In connection with physicists replica theory, we introduce the notion of generalized TAP states, which are the maximizers of the generalized TAP free energy, and show that their order parameters match the order parameter of the ancestor states in the Parisi ansatz. We compute the critical point equations of the TAP free energy that generalize the classical TAP equations for pure states. Furthermore, we give an exact description of the region where the generalized TAP correction is replica symmetric, in which case it coincides with the classical TAP correction, and show that Plefkas condition is necessary for this to happen. In particular, our result shows that the generalized TAP correction is not always replica symmetric on the points corresponding to the Edwards-Anderson parameter.
In a recent paper [14], we developed the generalized TAP approach for mixed $p$-spin models with Ising spins at positive temperature. Here we extend these results in two directions. We find a simplified representation for the energy of the generalized TAP states in terms of the Parisi measure of the model and, in particular, show that the energy of all states at a given distance from the origin is the same. Furthermore, we prove the analogues of the positive temperature results at zero temperature, which concern the ground-state energy and the organization of ground-state configurations in space.
We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results stemming from the geometry of Banach spaces with textit{scaling inequalities} used in analysing the convergence of optimization methods. In particular, we establish loca
We provide a theoretical treatment of over-specified Gaussian mixtures of experts with covariate-free gating networks. We establish the convergence rates of the maximum likelihood estimation (MLE) for these models. Our proof technique is based on a novel notion of emph{algebraic independence} of the expert functions. Drawing on optimal transport theory, we establish a connection between the algebraic independence and a certain class of partial differential equations (PDEs). Exploiting this connection allows us to derive convergence rates and minimax lower bounds for parameter estimation.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
