Inference in Multi-Layer Networks with Matrix-Valued Unknowns

Parthe Pandit, Mojtaba Sahraee-Ardakan, Sundeep Rangan, Philip Schniter, Alyson K. FletcherarXiv 2020 · arXiv

Abstract

This paper introduces ML-Mat-VAMP, an algorithm that extends Approximate Message Passing (AMP) to infer matrix-valued hidden variables in multi-layer stochastic networks. A central contribution is the derivation of a rigorous State Evolution (SE) framework, which provides exact deterministic predictions of the algorithm's performance in high-dimensional settings. This work bridges the gap between efficient heuristic inference and provable theoretical guarantees for non-convex multi-layer models.

Introduction

In deep learning and signal processing, "inverting" a network—estimating inputs or hidden states from observed outputs—is a critical task. While standard gradient-based optimizers like ADAM are widely used, they often lack strong theoretical guarantees in non-convex landscapes. Previous research into Approximate Message Passing (AMP) provided a path toward provable performance, but it was primarily restricted to vector-valued signals.

Modern problems such as multi-task learning, sketched clustering, and neural network training require estimating matrices rather than single vectors. ML-Mat-VAMP addresses this by enabling efficient inference on matrix-valued unknowns while maintaining the ability to mathematically predict the error at every step of the process.

Methods

The proposed Multi-Layer Matrix VAMP (ML-Mat-VAMP) algorithm is built on three key pillars:

  1. Unified Inference: It supports both Maximum A Posteriori (MAP) and Minimum Mean Squared Error (MMSE) estimation.
  2. Modular Architecture: The algorithm decomposes complex multi-layer problems into sequences of simpler "denoising" steps. It handles non-linearities through row-wise operations and linear layers via computationally efficient Singular Value Decompositions (SVD).
  3. State Evolution (SE): This theoretical framework uses deterministic recursive equations to track the mean-squared error (MSE). In the "large system limit" (where the number of rows $N \to \infty$ but the number of columns $d$ is fixed), SE perfectly predicts the algorithm's behavior.
Architecture of the multi-layer network and the corresponding ML-Mat-VAMP inference stages.

Experimental Validation

The authors validated the framework using synthetic datasets designed to mimic a two-layer neural network learning task. By treating the weight matrix as the unknown input to a multi-layer network, the learning process is reframed as an inference problem.

Inputs and weights were generated as i.i.d. Gaussians, with output noise added at 10dB and 15dB levels. To test the "large system limit," the model used a fixed number of hidden units ($d=4$) while varying the number of training samples ($N$) from 200 to 4000.

Key Results and Insights

Numerical experiments confirmed that the State Evolution (SE) predictions match the actual performance of the ML-Mat-VAMP algorithm almost perfectly.

Comparison of ML-Mat-VAMP performance against ADAM-MAP and theoretical State Evolution (SE) predictions at 10 dB and 15 dB SNR.
  • Theory vs. Practice: As shown in the plots, the SE predictions (green) align with the empirical results (orange), demonstrating that the high-dimensional interactions between layers simplify into predictable Gaussian noise patterns.
  • Comparison to ADAM: ML-Mat-VAMP achieved Mean Squared Error comparable to the ADAM optimizer but within a framework that allows for rigorous asymptotic analysis.
  • Predictable Generalization: Unlike many deep learning theories that offer only loose upper bounds, this framework provides an exact prediction of the test error.

Limitations and Future Work

While powerful, the current theoretical proof assumes weight matrices are "rotationally invariant" (Haar distributed). Extending these guarantees to highly structured matrices, such as those found in convolutional layers, remains an open challenge. Additionally, future work will explore scaling laws where the number of columns $d$ grows alongside $N$, and test the algorithm's stability in much deeper generative models.

Summary updated

Abstract

We consider the problem of inferring the input and hidden variables of a stochastic multi-layer neural network from an observation of the output. The hidden variables in each layer are represented as matrices. This problem applies to signal recovery via deep generative prior models, multi-task and mixed regression and learning certain classes of two-layer neural networks. A unified approximation algorithm for both MAP and MMSE inference is proposed by extending a recently-developed Multi-Layer Vector Approximate Message Passing (ML-VAMP) algorithm to handle matrix-valued unknowns. It is shown that the performance of the proposed Multi-Layer Matrix VAMP (ML-Mat-VAMP) algorithm can be exactly predicted in a certain random large-system limit, where the dimensions $N\times d$ of the unknown quantities grow as $N\rightarrow\infty$ with $d$ fixed. In the two-layer neural-network learning problem, this scaling corresponds to the case where the number of input features and training samples grow to infinity but the number of hidden nodes stays fixed. The analysis enables a precise prediction of the parameter and test error of the learning.
BibTeX
@misc{pandit2020inference,
  author = {Parthe Pandit and Mojtaba Sahraee-Ardakan and Sundeep Rangan and Philip Schniter and Alyson K. Fletcher},
  title = {{Inference in Multi-Layer Networks with Matrix-Valued Unknowns}},
  year = {2020},
  eprint = {2001.09396},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.09396},
}
Figure