Critical Points and Convergence Analysis of Generative Deep Linear Networks Trained with Bures-Wasserstein Loss

Pierre Bréchet, Katerina Papagiannouli, Jing An, Guido Montúfar

This paper, recently presented at ICML 2023, explores the theoretical foundations of generative modeling by analyzing Deep Linear Networks (DLNs) trained with the Bures-Wasserstein (BW) distance. While DLNs are often used as "toy models" to understand the optimization of complex neural networks, most existing theory focuses on discriminative tasks and squared error loss. This work shifts the focus to the generative setting, providing new insights into how these networks learn probability distributions.

TL;DR

The authors provide a rigorous characterization of the optimization landscape and convergence properties for deep linear networks trained to match Gaussian distributions using the Bures-Wasserstein loss. They prove that gradient-based methods can achieve global convergence under specific initialization conditions and demonstrate that network depth acts as an "implicit accelerator" for the learning process.

What Problem Does This Paper Address?

In the world of deep learning theory, DLNs (networks with identity activations) serve as a crucial simplified model. We have a solid understanding of how they behave when minimizing Mean Squared Error (MSE), but generative models—like Wasserstein GANs (WGANs)—operate differently. They aim to minimize distances between probability distributions.

The Bures-Wasserstein distance is the natural metric for this task when dealing with centered Gaussian distributions. However, optimizing it is challenging:

  1. Non-convexity: The loss is non-convex in the network's parameter space.
  2. Non-smoothness: The loss becomes non-smooth, and its Hessian (the matrix of second derivatives) can "blow up" when the represented covariance matrix drops in rank.
  3. Landscape Complexity: It was previously unclear if these generative landscapes shared the "no bad local minima" property seen with MSE loss.

Methods

The authors model a generative network as a deep matrix factorization $W = W_N \dots W_1$, where the goal is to match a target covariance matrix $\Sigma_0$ by minimizing the BW loss $L(WW^\top, \Sigma_0)$.

To tackle the theoretical hurdles, they employed several key techniques:

  • Smooth Perturbation: They introduced a regularized version of the loss ($L_\tau$) by adding a small identity component $\tau I$ to the covariance. This ensures the loss remains smooth and strongly convex in the covariance space, making it amenable to standard analysis tools.
  • Manifold Analysis: They characterized the critical points of the loss specifically on the manifold of matrices with a fixed rank $k$.
  • Initialization Assumptions: They utilized two standard but powerful assumptions: balanced weights (where the "effort" of the transformation is spread evenly across layers) and a modified deficiency margin (ensuring the initial weights are full-rank and sufficiently close to the target).

Datasets

The study is primarily theoretical and does not use standard image or text datasets. Instead, the authors conducted numerical experiments using synthetic target covariance matrices. These targets were generated with eigenvalues following a Zipf distribution to simulate realistic data decay patterns. These experiments were used to validate the predicted convergence rates across different network depths and target singular values.

Key Insights and Ideas

  • PCA-like Critical Points: The authors found an analogue to the classical Eckart-Young-Mirsky theorem. Even for the geometrically complex BW distance, the critical points and minimizers correspond to projections onto the top eigenvectors of the target covariance matrix—essentially performing a form of PCA.
  • Depth as an Accelerator: A fascinating finding is that increasing the number of layers $N$ actually speeds up the asymptotic convergence rate. This "implicit acceleration" is a known phenomenon for MSE loss, and this paper proves it also holds for generative BW optimization.
  • Saddle Point Property: The paper shows that the BW loss landscape satisfies the "strict saddle point property" on the manifold of rank-$k$ matrices, meaning that every critical point is either a global minimizer or a saddle point with a clear direction for further descent.

Key Results

The authors established strong convergence guarantees for both continuous and discrete optimization:

  • Gradient Flow: They proved that the continuous-time gradient flow converges exponentially to the global minimizer.
  • Gradient Descent: For finite step sizes, they proved linear convergence, provided the step size is small enough.
  • Empirical Validation: Their experiments confirmed that the convergence rate depends linearly on the network depth $N$.
Logarithm of the linear convergence rate as a function of depth N and the minimum singular value of the target. Subfigure (a) shows the linear regression against depth, while (b) shows the contour plot for both variables, illustrating the linear dependencies predicted by Theorem 5.5.

Limitations and Future Work

While the paper makes significant strides, the authors acknowledge some limitations:

  • Initialization Constraints: The convergence proofs rely on the "modified deficiency margin," which requires the network to be initialized in a somewhat "good" region (full rank and relatively close to the target). Relaxing this to allow for random, near-zero initializations is a key open problem.
  • Linearity: The results are strictly for linear networks. Extending these insights to non-linear architectures (like those with ReLU activations) remains the "holy grail" of this sub-field.
  • Parameter Space Refinement: While the landscape is well-understood in the "function space" (the space of matrices), a more granular characterization of critical points directly in the high-dimensional parameter space is still needed.

Summary updated

Abstract

We consider a deep matrix factorization model of covariance matrices trained with the Bures-Wasserstein distance. While recent works have made advances in the study of the optimization problem for overparametrized low-rank matrix approximation, much emphasis has been placed on discriminative settings and the square loss. In contrast, our model considers another type of loss and connects with the generative setting. We characterize the critical points and minimizers of the Bures-Wasserstein distance over the space of rank-bounded matrices. The Hessian of this loss at low-rank matrices can theoretically blow up, which creates challenges to analyze convergence of gradient optimization methods. We establish convergence results for gradient flow using a smooth perturbative version of the loss as well as convergence results for finite step size gradient descent under certain assumptions on the initial weights.
BibTeX
@inproceedings{brechet2023critical,
  author = {Pierre Bréchet and Katerina Papagiannouli and Jing An and Guido Montúfar},
  title = {{Critical Points and Convergence Analysis of Generative Deep Linear Networks Trained with Bures-Wasserstein Loss}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=S9kFcPHqHP},
}
Figure