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:
- Unified Inference: It supports both Maximum A Posteriori (MAP) and Minimum Mean Squared Error (MMSE) estimation.
- 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).
- 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.
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.
- 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