Inference in Deep Networks in High Dimensions

Alyson K. Fletcher, Sundeep Rangan

TL;DR

This paper introduces Multi-Layer Vector Approximate Message Passing (ML-VAMP), a novel algorithm for output-to-input inference in deep neural networks. Crucially, the authors prove that ML-VAMP's mean-squared error can be exactly predicted in high dimensions using simple scalar equations, even when dealing with highly ill-conditioned weight matrices. This provides a rare, rigorous theoretical guarantee for analyzing the exact performance of deep network inversion.

What Problem Does This Paper Address?

Deep generative networks are exceptionally good at modeling complex data like images, audio, and text. However, many practical tasks require us to run these networks in reverse—a process called output-to-input inference. For example, in image inpainting (restoring missing parts of an image), we treat the corrupted image as the output and try to infer the original input or hidden states that generated it.

While standard feedforward propagation is computationally trivial, inverting a deep network is generally intractable due to the complex, non-linear activation functions at each layer. Researchers typically rely on heuristic optimization methods like Maximum A Posteriori (MAP) estimation via gradient descent or variational autoencoders (VAEs). While these methods often work well in practice, they lack rigorous analytical tools to guarantee how close their estimates are to the optimal solution. This paper bridges that gap by providing an algorithm with precise, mathematically provable performance bounds in high dimensions.

Methods

The authors propose Multi-Layer Vector Approximate Message Passing (ML-VAMP), which is derived from the framework of expectation propagation (EP).

Key methodological features include:

  • Multi-Layer Extension: It extends previous Vector Approximate Message Passing (VAMP) methods from simple linear systems to multi-layer networks containing alternating linear stages (weight matrices and biases) and non-linear stages (activation functions like ReLU or Sigmoid).
  • Orthogonal Invariance: Unlike traditional Approximate Message Passing (AMP) algorithms that fail when weight matrices are highly correlated or poorly conditioned, ML-VAMP assumes weight matrices are orthogonally invariant. This allows the algorithm to handle arbitrary condition numbers robustly.
  • State Evolution (SE): The core theoretical contribution is showing that in the Large System Limit (where layer dimensions grow to infinity), the mean-squared error (MSE) of the algorithm can be exactly tracked at each iteration using a set of deterministic, scalar State Evolution equations.

Datasets

The algorithm was evaluated using two setups:

  1. Synthetic Random Networks: Randomly generated multi-layer perceptrons (MLPs) with Gaussian i.i.d. weights and an orthogonally invariant observation matrix designed with a fixed, challenging condition number ($\kappa = 10$).
  2. MNIST Dataset: The standard benchmark of 28x28 pixel handwritten digits, used to evaluate a practical image inpainting task via a trained Variational Autoencoder (VAE).

Key Insights and Ideas

  • Overcoming the Conditioning Bottleneck: Traditional AMP algorithms are notoriously fragile when moving away from ideal i.i.d. Gaussian matrices. By utilizing Singular Value Decomposition (SVD) inside the linear estimation steps, ML-VAMP inherently corrects for ill-conditioned weight matrices.
  • Exact Asymptotic Predictability: The "aha" moment of the paper is Theorem 1, which proves that a complex, high-dimensional, non-linear dynamical system (the execution of ML-VAMP across multiple layers) simplifies perfectly into scalar state equations in the large system limit. This means you can accurately predict exactly how well the algorithm will perform before running it.
  • Decoupling Layers: ML-VAMP effectively decouples the multi-layer inference problem into a sequence of independent, local estimation problems at each layer, passing "messages" (estimates and variances) back and forth to reach consensus.

Key Results

  • Flawless Theory-to-Practice Match: In synthetic experiments, the empirical normalized mean-squared error (NMSE) matched the theoretical State Evolution (SE) predictions within approximately 1 dB across all iterations and measurement counts.
Fig. 1. Simulation with a randomly generated neural network. Left panel: Normalized mean squared error (NMSE) for ML-VAMP and the predicted value from the state evolution as a function of the iteration with M = 300 measurements. Right panel: Final NMSE for ML-VAMP and the SE prediction as a function of the measurements
  • Massive Computational Speedups: For the MNIST image inpainting task, ML-VAMP achieved visual reconstruction quality virtually identical to MAP estimation and Stochastic Gradient Langevin Dynamics (SGLD). However, ML-VAMP required only 20 iterations, compared to 500 iterations for MAP and 10,000 samples for SGLD, demonstrating its potential as a highly efficient reconstruction tool.

Limitations and Future Work

  • Structural Assumptions: The rigorous proofs rely on the assumption that weight matrices are random and orthogonally invariant. While the algorithm still performed remarkably well on a real-world trained MNIST VAE, the theoretical guarantees do not strictly apply to arbitrary, highly structured learned weights (e.g., convolutional layers).
  • Inference vs. Learning: The paper focuses entirely on inference (where network parameters are already known and fixed). The authors suggest that a natural next step is extending ML-VAMP to learning problems (parameter estimation) by combining it with Expectation-Maximization (EM) techniques.

Summary updated

Abstract

Deep generative networks provide a powerful tool for modeling complex data in a wide range of applications. In inverse problems that use these networks as generative priors on data, one must often perform inference of the inputs of the networks from the outputs. Inference is also required for sampling during stochastic training on these generative models. This paper considers inference in a deep stochastic neural network where the parameters (e.g., weights, biases and activation functions) are known and the problem is to estimate the values of the input and hidden units from the output. While several approximate algorithms have been proposed for this task, there are few analytic tools that can provide rigorous guarantees in the reconstruction error. This work presents a novel and computationally tractable output-to-input inference method called Multi-Layer Vector Approximate Message Passing (ML-VAMP). The proposed algorithm, derived from expectation propagation, extends earlier AMP methods that are known to achieve the replica predictions for optimality in simple linear inverse problems. Our main contribution shows that the mean-squared error (MSE) of ML-VAMP can be exactly predicted in a certain large system limit (LSL) where the numbers of layers is fixed and weight matrices are random and orthogonally-invariant with dimensions that grow to infinity. ML-VAMP is thus a principled method for output-to-input inference in deep networks with a rigorous and precise performance achievability result in high dimensions.
BibTeX
@inproceedings{fletcher2018inference,
  author = {Alyson K. Fletcher and Sundeep Rangan},
  title = {{Inference in Deep Networks in High Dimensions}},
  booktitle = {ISIT},
  year = {2018},
  doi = {10.1109/isit.2018.8437792},
}

Loading related content...

Figure