Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> We consider an Ising model in which the spins are coupled by infinite-ranged random interactions independently distributed with a Gaussian probability density. Both "spinglass" and ferromagnetic phases occur. The competition between the phases and the type of order present in each are studied. <s> BIB001 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> Abstract The Sherrmgton-Kirkpatrick model of a spin glass is solved by a mean field technique which is probably exact in the limit of infinite range interactions. At and above T c the solution is identical to that obtained by Sherrington and Kirkpatrick (1975) using the n → O replica method, but below T c the new result exhibits several differences and remains physical down to T = 0. <s> BIB002 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> This book contains a detailed and self-contained presentation of the replica theory of infinite range spin glasses. The authors also explain recent theoretical developments, paying particular attention to new applications in the study of optimization theory and neural networks. About two-thirds of the book are a collection of the most interesting and pedagogical articles on the subject. <s> BIB003 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> Abstract This article reviews Markov chain methods for sampling from the posterior distribution of a Dirichlet process mixture model and presents two new classes of methods. One new approach is to make Metropolis—Hastings updates of the indicators specifying which mixture component is associated with each observation, perhaps supplemented with a partial form of Gibbs sampling. The other new approach extends Gibbs sampling for these indicators by using a set of auxiliary parameters. These methods are simple to implement and are more efficient than previous ways of handling general Dirichlet process mixture models with non-conjugate priors. <s> BIB004 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> 1. Mean-field theory of phase transitions 2. Mean-field theory of spin glasses 3. Replica symmetry breaking 4. Gauge theory of spin glasses 5. Error-correcting codes 6. Image restoration 7. Associative memory 8. Learning in perceptron 9. Optimization problems A. Eigenvalues of the Hessian B. Parisi equation C. Channel coding theorem D. Distribution and free energy of K-Sat References Index <s> BIB005 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio α of clauses to variables less than a threshold α c are almost always satisfiable, whereas those with a ratio above this threshold are almost always unsatisfiable. We show the existence of an intermediate phase below α c , where the proliferation of metastable states is responsible for the onset of complexity in search algorithms. We introduce a class of optimization algorithms that can deal with these metastable states; one such algorithm has been tested successfully on the largest existing benchmark of K-satisfiability. <s> BIB006 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> We study the satisfiability of randomly generated formulas formed by M clauses of exactly K literals over N Boolean variables. For a given value of N the problem is known to be most difficult when α = M/N is close to the experimental threshold αc separating the region where almost all formulas are SAT from the region where all formulas are UNSAT. Recent results from a statistical physics analysis suggest that the difficulty is related to the existence of a clustering phenomenon of the solutions when α is close to (but smaller than) αc. We introduce a new type of message passing algorithm which allows to find efficiently a satisfying assignment of the variables in this difficult region. This algorithm is iterative and composed of two main parts. The first is a message-passing procedure which generalizes the usual methods like Sum-Product or Belief Propagation: It passes messages that may be thought of as surveys over clusters of the ordinary messages. The second part uses the detailed probabilistic information obtained from the surveys in order to fix variables and simplify the problem. Eventually, the simplified problem that remains is solved by a conventional heuristic. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 <s> BIB007 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> Compressed sensing aims to undersample certain high-dimensional signals, yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible when the object to be recovered is sufficiently sparse in a known basis. Currently, the best known sparsity-undersampling tradeoff is achieved when reconstructing by convex optimization -- which is expensive in important large-scale applications. Fast iterative thresholding algorithms have been intensively studied as alternatives to convex optimization for large-scale problems. Unfortunately known fast algorithms offer substantially worse sparsity-undersampling tradeoffs than convex optimization. We introduce a simple costless modification to iterative thresholding making the sparsity-undersampling tradeoff of the new algorithms equivalent to that of the corresponding convex optimization procedures. The new iterative-thresholding algorithms are inspired by belief propagation in graphical models. Our empirical measurements of the sparsity-undersampling tradeoff for the new algorithms agree with theoretical calculations. We show that a state evolution formalism correctly derives the true sparsity-undersampling tradeoff. There is a surprising agreement between earlier calculations based on random convex polytopes and this new, apparently very different theoretical formalism. <s> BIB008 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> During the last decade, the data sizes have grown faster than the speed of processors. In this context, the capabilities of statistical machine learning methods is limited by the computing time rather than the sample size. A more precise analysis uncovers qualitatively different tradeoffs for the case of small-scale and large-scale learning problems. The large-scale case involves the computational complexity of the underlying optimization algorithm in non-trivial ways. Unlikely optimization algorithms such as stochastic gradient descent show amazing performance for large-scale problems. In particular, second order stochastic gradient and averaged stochastic gradient are asymptotically efficient after a single pass on the training set. <s> BIB009 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> “Approximate message passing” (AMP) algorithms have proved to be effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution. In this paper, we provide rigorous foundation to state evolution. We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed Gaussian entries. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with a large number of short cycles in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory. <s> BIB010 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> We propose an iterative scheme for the solutions of the TAP-equations in the Sherrington–Kirkpatrick model which is shown to converge up to and including the de Almeida–Thouless line. The main tool is a representation of the iterations which reveals an interesting structure of them. This representation does not depend on the temperature parameter, but for temperatures below the de Almeida–Thouless line, it contains a part which does not converge to zero in the limit. <s> BIB011 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> We consider a class of approximated message passing (AMP) algorithms and characterize their high-dimensional behavior in terms of a suitable state evolution recursion. Our proof applies to Gaussian matrices with independent but not necessarily identically distributed entries. It covers --in particular-- the analysis of generalized AMP, introduced by Rangan, and of AMP reconstruction in compressed sensing with spatially coupled sensing matrices. The proof technique builds on the one of [BM11], while simplifying and generalizing several steps. <s> BIB012 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> The replica extension theory has been developed for the purpose of investigating spin glass systems in the replica symmetry breaking phase. The replica extension theory is a replica theory for a specific sample and has the scheme of the one-step replica symmetry breaking ansatz. In this paper, using the Plefka expansion, we propose the perturbative expansion of Gibbs free energies of Ising systems with the replica extension theory, and we derive the explicit form of the second-?and third-order approximations. Our Plefka expansion systematically provides perturbative approximations taking the one-step replica symmetry breaking into account. In some numerical experiments, we show that our perturbative approximations are quantitatively superior to conventional perturbative approximations that do not take the one-step replica symmetry breaking into account in the spin glass phase. <s> BIB013 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> In a recent article (Proc. Natl. Acad. Sci., 110(36), 14557-14562), El Karoui et al. study the distribution of robust regression estimators in the regime in which the number of parameters p is of the same order as the number of samples n. Using numerical simulations and `highly plausible' heuristic arguments, they unveil a striking new phenomenon. Namely, the regression coefficients contain an extra Gaussian noise component that is not explained by classical concepts such as the Fisher information matrix. We show here that that this phenomenon can be characterized rigorously techniques that were developed by the authors to analyze the Lasso estimator under high-dimensional asymptotics. We introduce an approximate message passing (AMP) algorithm to compute M-estimators and deploy state evolution to evaluate the operating characteristics of AMP and so also M-estimates. Our analysis clarifies that the `extra Gaussian noise' encountered in this problem is fundamentally similar to phenomena already studied for regularized least squares in the setting n <s> BIB014 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> Many questions of fundamental interest in todays science can be formulated as inference problems: Some partial, or noisy, observations are performed over a set of variables and the goal is to recover, or infer, the values of the variables based on the indirect information contained in the measurements. For such problems, the central scientific questions are: Under what conditions is the information contained in the measurements sufficient for a satisfactory inference to be possible? What are the most efficient algorithms for this task? A growing body of work has shown that often we can understand and locate these fundamental barriers by thinking of them as phase transitions in the sense of statistical physics. Moreover, it turned out that we can use the gained physical insight to develop new promising algorithms. Connection between inference and statistical physics is currently witnessing an impressive renaissance and we review here the current state-of-the-art, with a pedagogical focus on the Ising model which formulated as an inference problem we call the planted spin glass. In terms of applications we review two classes of problems: (i) inference of clusters on graphs and networks, with community detection as a special case and (ii) estimating a signal from its noisy linear measurements, with compressed sensing as a case of sparse estimation. Our goal is to provide a pedagogical review for researchers in physics and other fields interested in this fascinating topic. <s> BIB015 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> To model modern large-scale datasets, we need efficient algorithms to infer a set of $P$ unknown model parameters from $N$ noisy measurements. What are fundamental limits on the accuracy of parameter inference, given finite signal-to-noise ratios, limited measurements, prior information, and computational tractability requirements? How can we combine prior information with measurements to achieve these limits? Classical statistics gives incisive answers to these questions as the measurement density $\alpha = \frac{N}{P}\rightarrow \infty$. However, these classical results are not relevant to modern high-dimensional inference problems, which instead occur at finite $\alpha$. We formulate and analyze high-dimensional inference as a problem in the statistical physics of quenched disorder. Our analysis uncovers fundamental limits on the accuracy of inference in high dimensions, and reveals that widely cherished inference algorithms like maximum likelihood (ML) and maximum-a posteriori (MAP) inference cannot achieve these limits. We further find optimal, computationally tractable algorithms that can achieve these limits. Intriguingly, in high dimensions, these optimal algorithms become computationally simpler than MAP and ML, while still outperforming them. For example, such optimal algorithms can lead to as much as a 20% reduction in the amount of data to achieve the same performance relative to MAP. Moreover, our analysis reveals simple relations between optimal high dimensional inference and low dimensional scalar Bayesian inference, insights into the nature of generalization and predictive power in high dimensions, information theoretic limits on compressed sensing, phase transitions in quadratic inference, and connections to central mathematical objects in convex optimization theory and random matrix theory. <s> BIB016 </s> Approximate Survey Propagation for Statistical Inference <s> I. INTRODUCTION A. General Motivation <s> This article is an extended version of previous work of the authors [40, 41] on low-rank matrix estimation in the presence of constraints on the factors into which the matrix is factorized. Low-rank matrix factorization is one of the basic methods used in data analysis for unsupervised learning of relevant features and other types of dimensionality reduction. We present a framework to study the constrained low-rank matrix estimation for a general prior on the factors, and a general output channel through which the matrix is observed. We draw a paralel with the study of vector-spin glass models - presenting a unifying way to study a number of problems considered previously in separate statistical physics works. We present a number of applications for the problem in data analysis. We derive in detail a general form of the low-rank approximate message passing (Low- RAMP) algorithm, that is known in statistical physics as the TAP equations. We thus unify the derivation of the TAP equations for models as different as the Sherrington-Kirkpatrick model, the restricted Boltzmann machine, the Hopfield model or vector (xy, Heisenberg and other) spin glasses. The state evolution of the Low-RAMP algorithm is also derived, and is equivalent to the replica symmetric solution for the large class of vector-spin glass models. In the section devoted to result we study in detail phase diagrams and phase transitions for the Bayes-optimal inference in low-rank matrix estimation. We present a typology of phase transitions and their relation to performance of algorithms such as the Low-RAMP or commonly used spectral methods. <s> BIB017
Many problems in data analysis and other data-related science can be formulated as optimization or inference in high-dimensional and non-convex landscapes. General classes of algorithms that are able to deal with some of these problems include Monte Carlo and Gibbs-based sampling BIB004 , variational mean field methods  , stochastic gradient descent BIB009 and their variants. Approximate message passing (AMP) algorithms BIB002 BIB008 is another such class that has one very remarkable advantage over all the before mentioned: for a large class of models where instances are generated from a probabilistic model, the performance of AMP on large such instances can be tracked via a so-called state evolution BIB011 BIB010 BIB012 . This development has very close connections to statistical physics of disordered systems because the state evolution that describes AMP coincides with fixed-point equations that arise from the replica and cavity methods as known in the theory of glasses and spin glasses BIB003 . AMP and its state evolution have been so far mainly used in two contexts. On the one hand, for optimization in cases where the associated landscape is convex. This the the case e.g. in the original work of Donoho, Maleki, Montanari BIB008 where 1 -norm minimization for sparse linear regression is analyzed, or in the study of the socalled M-estimators BIB014 BIB016 . On the other hand, in the setting of Bayes-optimal inference where the model that generated the data is assumed to be known perfectly, see e.g. BIB015 BIB017 , where the so-called Nishimori conditions ensure that the associated posterior probability measure is of so-called replica symmetric kind in the context of spin glasses BIB003 BIB005 . Many (if not most) of inference and optimization problems that are solved in the currently most challenging applications are highly non-convex and the underlying model that generated the data is not known. It is hence an important general research direction to understand the behavior of algorithms and find their more robust generalizations encompassing such settings. In the present paper we make a step in this general direction for the class of AMP algorithms. We analyze in detail the phase diagram and phases of convergence of the AMP algorithm on a prototypical example of a problem that is non-convex and not in the Bayes-optimal setting. The example we choose is rank-one matrix estimation problem that has the same phase diagram as the Sherrington-Kirkpatrick (SK) model with ferromagnetic bias BIB001 . AMP reproduces the corresponding replica symmetric phase diagram with region of non-convergence being given by the instability towards replica symmetry breaking (RSB). We note that while this phase diagram is well known in the literature on spin glasses, its algorithmic consequences are obscured in the early literature by the fact that unless the AMP algorithm is iterated with the correct time-indices BIB011 convergence is not reached, see discussion e.g. in BIB015 . Our main contribution is the development of a new type of approximate message passing algorithm that takes into account breaking of the replica symmetry and reduces to AMP for a special choice of parameters. We call this the approximate survey propagation (ASP) algorithm, following up on the influential work on survey propagation in sparse random constraint satisfaction problems BIB006 BIB007 . We show that there are regions (away from the Nishimori line) in which ASP converges while AMP does not, and where at the same time ASP provides lower estimation error than AMP. We show that the state evolution of ASP leads to the one-step-replica symmetry breaking (1RSB) fixed-point equations well known from the study of spin glasses. This is the first algorithm that provably converges towards fixed-points of the 1RSB equations. Again we stress that, while the 1RSB phase diagram and corresponding physics of the ferromagnetically biased SK model is well-known, its algorithmic confirmation is new to our knowledge: even if the 1RSB versions of the Thouless-Anderson-Palmer (TAP) BIB002 equations was previously discussed, e.g. in BIB003 BIB013 , the corresponding time-indices in ASP are crucial in order to reproduce this phase diagram algorithmically. Our work gives a concrete algorithmic meaning to the 1RSB fixed-point equations, and can thus be potentially used to understand this concept independently of the heuristic replica or cavity methods.