The stochastic interpolation method: A simple scheme to prove replica formulas in Bayesian inference

Jean Barbier, Nicolas MacrisarXiv 2017 · OpenReview

Abstract

In recent years important progress has been achieved towards proving the validity of the replica predictions for the (asymptotic) mutual information (or "free energy") in Bayesian inference problems. The proof techniques that have emerged appear to be quite general, despite they have been worked out on a case-by-case basis. Unfortunately, a common point between all these schemes is their relatively high level of technicality. We present a new proof scheme that is quite straightforward with respect to the previous ones. We call it the adaptive interpolation method because it can be seen as an extension of the interpolation method developped by Guerra and Toninelli in the context of spin glasses, with an interpolation path that is adaptive. In order to illustrate our method we show how to prove the replica formula for three non-trivial inference problems. The first one is symmetric rank-one matrix estimation (or factorisation), which is the simplest problem considered here and the one for which the method is presented in full details. Then we generalize to symmetric tensor estimation and random linear estimation. We believe that the present method has a much wider range of applicability and also sheds new insights on the reasons for the validity of replica formulas in Bayesian inference.

Introduction

In statistical physics and information theory, researchers use the "replica method" to predict the fundamental limits of inference problems—for example, exactly how much noise a dataset can have before it becomes mathematically impossible to reconstruct the original signal. These predictions yield "replica symmetric formulas" for the system's mutual information (or "free energy").

While physicists have successfully used these formulas for decades, rigorously proving that they are mathematically exact is notoriously difficult. Existing proof techniques, such as spatial coupling or the Aizenman-Sims-Starr cavity method, are highly technical and usually custom-tailored to specific problems. This paper addresses the need for a unified, simpler, and more direct mathematical scheme to prove these replica formulas across a wide variety of Bayesian inference problems.

The Adaptive Interpolation Method

The authors develop the adaptive interpolation method, which builds upon the Guerra-Toninelli interpolation technique originally used in spin glass theory. This technique gradually transforms a complex, highly interacting mathematical model into a simple, decoupled "mean-field" model where variables are easy to analyze. The novel approach presented here introduces two key components:

  • Small, Adaptive Steps: Instead of a single, fixed interpolation path, the method breaks the interpolation into discrete steps. At each step, the "trial parameters" (acting as artificial signal-to-noise ratios) are adapted dynamically based on the system's behavior in the previous step.
  • Exploiting Nishimori Identities: In a Bayesian setting, the authors leverage "Nishimori identities"—mathematical correlation identities that naturally arise from Bayes' rule. These identities prove that the system's "overlap" (how closely an estimate aligns with the ground truth) tightly concentrates around its mean.
Visualization of the discrete interpolation steps ($k$) and the evolution of the system from a coupled state to a decoupled mean-field state.

By combining the concentration of the overlap with the dynamically adapted trial parameters, the error terms in the interpolation perfectly cancel out. This allows the authors to squeeze the true free energy between matching upper and lower bounds, proving the formula is exact.

Key Insights and Results

A fundamental insight of this work is that Bayesian problems are mathematically "nicer" than general spin glasses. In models like the Sherrington-Kirkpatrick model, overlaps fluctuate wildly. However, in Bayesian inference, the Nishimori identities force concentration, which is the underlying reason why replica symmetric formulas are valid. The adaptive interpolation method exploits this fact directly.

The authors provide rigorous, self-contained proofs of the replica symmetric formulas for three major inference problems:

  1. Symmetric rank-one matrix estimation: Recovering a matrix from noisy pairwise products.
  2. Symmetric rank-one tensor estimation: Recovering a signal from noisy multi-way products.
  3. Gaussian random linear estimation: Also known as compressive sensing, recovering a signal from noisy random linear projections.

In all three cases, they successfully prove that as the system size goes to infinity, the true asymptotic free energy perfectly matches the predictions of the replica symmetric potential.

Limitations and Future Work

The current proofs assume the signal's prior distribution has bounded support for technical convenience, though this could likely be relaxed to requiring only finite moments. While this paper focuses on "dense" problems (complete graphs), adapting the method to "sparse" problems, such as LDPC error-correcting codes, remains an active area of research. Additionally, the authors suggest that formalizing a continuous version of their method using stochastic calculus (Ito integrals) is a promising direction for future theoretical development.

Summary updated

Abstract

In recent years important progress has been achieved towards proving the validity of the replica predictions for the (asymptotic) mutual information (or "free energy") in Bayesian inference problems. The proof techniques that have emerged appear to be quite general, despite they have been worked out on a case-by-case basis. Unfortunately, a common point between all these schemes is their relatively high level of technicality. We present a new proof scheme that is quite straightforward with respect to the previous ones. We call it the adaptive interpolation method because it can be seen as an extension of the interpolation method developped by Guerra and Toninelli in the context of spin glasses, with an interpolation path that is adaptive. In order to illustrate our method we show how to prove the replica formula for three non-trivial inference problems. The first one is symmetric rank-one matrix estimation (or factorisation), which is the simplest problem considered here and the one for which the method is presented in full details. Then we generalize to symmetric tensor estimation and random linear estimation. We believe that the present method has a much wider range of applicability and also sheds new insights on the reasons for the validity of replica formulas in Bayesian inference.
BibTeX
@misc{barbier2017stochastic,
  author = {Jean Barbier and Nicolas Macris},
  title = {{The stochastic interpolation method: A simple scheme to prove replica formulas in Bayesian inference}},
  year = {2017},
  eprint = {1705.02780},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1705.02780},
}
Figure