PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Optimization Landscape of Maximum Mean Discrepancy

Itai Alon, Amir Globerson, Ami Wiesel

arXiv:2110.13452v2cs.LGstat.ML

TL;DR

Generative-model training has limited theoretical guarantees, including for non-convex implicit objectives. The paper analyzes population MMD landscapes in several Gaussian settings and finds that gradient descent can converge only to global minimizers. The results include low-rank covariance and Gaussian-mixture cases, with finite fake-sample performance remaining below the infinite-fake-sample version.

  • Problem

    Theoretical properties of generative-model training remain limited, including when non-convex MMD objectives can be globally optimized.

    Source: §1 · p. 1

  • Method

    The paper analyzes the population-loss MMD optimization landscape for Gaussian distributions with unknown mean, low-rank covariance, and Gaussian mixtures.

    Source: §1 · pp. 1–2

  • Results

    For these three settings, the MMD landscape is benign, so gradient descent can converge only to global minimizers.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results include low-rank covariance and Gaussian-mixture cases, and MMD offers an advantage over MLE in covariance learning.

    Source: §5 · p. 9

    Empirical evaluation suggests finite fake samples do not perform as well as the infinite-fake-sample version, OSMMD; the effect of fake-sample size remains for future study.

    Source: §5 · p. 9

Abstract

from arXiv · show

Generative models have been successfully used for generating realistic signals. Because the likelihood function is typically intractable in most of these models, the common practice is to use "implicit" models that avoid likelihood calculation. However, it is hard to obtain theoretical guarantees for such models. In particular, it is not understood when they can globally optimize their non-convex objectives. Here we provide such an analysis for the case of Maximum Mean Discrepancy (MMD) learning of generative models. We prove several optimality results, including for a Gaussian distribution with low rank covariance (where likelihood is inapplicable) and a mixture of Gaussians. Our analysis shows that that the MMD optimization landscape is benign in these cases, and therefore gradient based methods will globally minimize the MMD objective.

1 Introduction

The paper studies the limited theoretical understanding of MMD learning and analyzes whether its non-convex objectives can be globally optimized. It reports benign landscapes for three population-loss settings and situates this analysis among prior work on implicit models, MMD, and Gaussian mixtures.

1 Introduction

  • The study addresses limited theoretical understanding of generative-model training, especially when training approximates the underlying distribution and how many samples are required.Source: §1 · p. 1
  • MLE is not directly applicable to complex models when point probabilities are hard to calculate; implicit models instead compare generated and real samples using a divergence.Source: §1 · p. 1
  • For population loss in three settings, MMD has a benign landscape, so gradient descent can converge only to global minimizers.The settings include Gaussian distributions with unknown mean, low-rank covariance, and mixtures of Gaussians.Source: §1 · pp. 1–2

1.1 Related Work

2 Problem Setup

The setup studies population MMD between data from a true parameter and samples from a parameterized generator, asking when optimization recovers the true parameter. The analysis applies a strict-saddle strategy to characterize when descent methods can reach global minimizers.

2 Problem Setup

  • Data are i.i.d. draws from Pθ*, and the parameter-estimation goal is to recover θ* from those observations.Pθ denotes a distribution on X defined by parameter vector θ.Source: §2 · p. 3
  • The target is to minimize population MMD between generated samples and data from the true parameter, seeking optimization that reaches θ = θ*.The population case takes both sample sizes to infinity and uses a Gaussian RBF kernel.Source: §2 · p. 3
  • A characteristic-kernel MMD is zero exactly when the model and target distributions are equal, but its loss is usually non-convex and may be hard to optimize.Source: §2 · p. 3
  • The analysis uses the strict-saddle property and absence of non-global local minima to show that gradient descent can converge only to a global minimizer.The strict-saddle property requires each critical point to be a local minimum or have a negative Hessian eigenvalue.Source: §2 · p. 3

3 Theoretical Results

The MMD objective has a benign optimization landscape in three parameter-estimation settings: Gaussian means, low-rank Gaussian covariance, and symmetric Gaussian-mixture means. In these cases, its stationary points and gradient behavior support gradient-based convergence to global minima.

3 Theoretical Results

  • Across the three settings, MMD has no nonglobal local minima and only strict saddles besides global minima, supporting gradient-based convergence to a global optimum.The settings are Gaussians with unknown mean, Gaussians with unknown low-rank covariance, and mixtures of Gaussians with unknown means.Source: §3 · p. 3

3.1 Gaussian with Unknown Mean

  • For a Gaussian with known covariance and unknown mean, the MMD loss is quasi-convex with its sole stationary point at the true mean, which is the global minimum.If the true mean is within radius r of initialization, choosing σ2 ≥ 2r ensures a strongly convex objective and linear GD convergence.Source: §3.1 · pp. 3–4
  • In the unknown-mean Gaussian case, gradients can vanish far from the true mean, but increasing the width can widen the convex region.The paper contrasts MMD's quasi-convex landscape with MLE's strongly convex objective.Source: §3.1 · p. 4

3.2 Gaussian with Unknown Covariance

  • For the rank-one unknown-covariance model, ±a* are global minima, the origin is a maximum, and the remaining stationary points are strict saddles.The result also holds for ϵ = 0; a Lipschitz gradient supports the conclusion that GD avoids saddle points and bad local minima.Source: §3.2 · pp. 4–5

3.3 Mixture of Two Gaussians with Unknown Mean

  • For a symmetric Gaussian mixture with known covariance and unknown nonzero mean, ±µ* are global minima, zero is a global maximum, and the other stationary points are strict saddles.In the one-dimensional illustration, poor width choices produce inflection points with small but nonzero derivatives; tuning width permits a Hessian bound used for the GD guarantee.Source: §3.3 · pp. 5–6

4 Experiments

The experiments evaluate MMD, OSMMD, MLE, and WGAN on Gaussian and mixture parameter estimation, with results generally in line with the predicted global convergence of MMD. MMD performs better than WGAN in the reported mean-estimation and linear-unmixing comparisons, while covariance experiments highlight MLE’s difficulty near singularity.

4 Experiments

  • The experiments evaluate methods on three parameter-estimation settings and report empirical results in line with the expected global convergence of MMD.The approaches include standard MMD, analytically computed OSMMD, MLE, and WGAN.Source: §4 · pp. 6–7

4.1 Gaussian with Unknown Mean

  • MMD significantly outperforms WGAN for unknown-mean estimation in both a Gaussian and a symmetric two-Gaussian mixture; OSMMD coincides with MLE.The reported results suggest the gap to optimality can be eliminated by increasing the fake-sample count n.Source: §4.1 · p. 7, Figure 4 · p. 7, Figure 5 · p. 7

4.2 Gaussian with Unknown Covariance

  • For covariance estimation as ε varies, MLE fails to recover the unknown covariance in the near-singular case, while MLE does not exist at ε = 0.Both algorithms use the same number of iterations and learning rate.Source: §4.2 · p. 7, Figure 6 · p. 8
  • With ε = 1·10−5, MLE fails in all zero-mean covariance experiments; OSMMD is significantly better than the other methods, and MMD is second best.WGAN performs worse than the MMD baselines and requires significant hyperparameter tuning.Source: §4.2 · p. 8, Figure 7 · p. 8
  • In the unknown-covariance two-Gaussian mixture, the results show qualitative behavior similar to the single-Gaussian case.The authors report that extensive WGAN parameter exploration did not improve its performance beyond the reported result.Source: §4.2 · p. 8, Figure 8 · p. 8

4.3 Linear Unmixing

  • Linear unmixing estimates the unknown matrix A from X = AB + W; the reported setting uses d = 10, r = 3, n = 100, VCA initialization, and 5000 epochs.The accuracy comparison is presented for different noise variances.Source: §4.3 · p. 8, Table 1 · p. 9
  • MMD shows a clear advantage over WGAN in linear unmixing.Both methods require a suitable initialization such as VCA and perform poorly otherwise.Source: §4.3 · p. 9, Table 1 · p. 9

5 Conclusions

The paper studies MMD optimization for Gaussian models with low-rank covariance and Gaussian mixtures, finding benign landscapes despite non-convexity while identifying challenges and open questions.

5 Conclusions

  • Non-convex optimization can have bad local optima, and relatively few theoretical results characterize when such methods work.Source: §5 · p. 9
  • MMD can be globally optimized despite non-convexity for low-rank-covariance Gaussians and Gaussian mixtures, which the paper treats as building blocks of more complex cases.The covariance-learning setting also offers an advantage over MLE.Source: §5 · p. 9
  • In some cases, gradients vanish as the parameter diverges, motivating bandwidth choices that keep gradients sufficiently large.The theoretical properties of the resulting method, closer to MMD-GAN, remain to be explored.Source: §5 · p. 9
  • The effect of fake-sample size on the landscape and sample complexity remains open; empirical evaluation suggests finite-sample MMD performs well, though not as well as infinite-fake-sample OSMMD.Source: §5 · p. 9

A.1 End of Proof of Theorem 2

The proof computes a Hessian and uses equation (12) to establish that a* is a descent direction.

A.1 End of Proof of Theorem 2

  • The proof computes the Hessian, dropping positive constants in the calculation.Source: §A.1 · p. 11
  • Equation (12) ensures that a* is a descent direction.Source: §A.1 · p. 11

A.2 End of Proof of Theorem 3

The proof analyzes a case by computing the Hessian and showing that μ* is an eigenvector with a negative eigenvalue; the following subsection introduces Lemma 4.

A.2 End of Proof of Theorem 3

  • In case (B), the proof uses ∥μ − μ*∥2 = ∥μ + μ*∥2 and substitutes into the equation again.Source: §A.2 · p. 11
  • The Hessian is computed, and μ* is shown to be an eigenvector with a negative eigenvalue, using Taylor expansion and μ* ≠ 0.Source: §A.2 · p. 11

B LEMMAS

  • Lemma 4 is introduced for μ ∈ R^d and a positive definite matrix Σ ∈ R^{d×d}.Source: B LEMMAS · p. 12

B.1 Proof of Lemma 4

This proof section introduces Gaussian-integral and matrix-identity tools, states gradient and Hessian formulas for the MMD loss, and bounds expressions across vector directions.

B.1 Proof of Lemma 4

  • The proof invokes a normal-density integral and the Woodbury matrix identity.The integral is described using a specified mean and covariance.Source: §B.1 · p. 12
  • Lemmas 5 and 6 provide the gradient and Hessian of the MMD loss, respectively.Source: §B.1 · pp. 12–13
  • The proof bounds expressions by considering directions relative to a and a*, with some terms bounded over vector norms.It considers directions orthogonal to a, a*, or both, and notes that one term converges to zero as ∥a∥ approaches zero or infinity.Source: §B.1 · pp. 14–16

C EXPERIMENTS

This section presents experiment-detail tables for Gaussian and GMM settings with unknown means or covariances, including an epsilon comparison for the Gaussian unknown-covariance case.

C.1 Graphs Parameters

  • The experiments include a Gaussian setting with unknown mean in Table 2 and a Gaussian setting with unknown covariance in Table 4; Table 6 covers unknown-covariance experiments comparing epsilon.Source: Table 2 · p. 17, Table 4 · p. 17, Table 6 · p. 17
  • Experiment details include GMM settings with unknown means in Table 3 and GMM settings with unknown covariance in Table 5.Source: Table 3 · p. 17, Table 5 · p. 17
  • Table 7 is specifically an epsilon comparison for the Gaussian unknown-covariance setting.Source: Table 6 · p. 17

C.2 Linear Unmixing

The linear-unmixing experiments describe MMD and WGAN setups and report final results averaged over 50 trials. The setup uses VCA initialization and 256 fake samples per iteration over 5000 iterations for each noise variance.

C.2 Linear Unmixing

  • For each noise variance, the experiments use VCA initialization, 256 fake samples per iteration, and 5000 iterations.Source: §C.2 · p. 18
  • Table 7 describes the MMD and WGAN setups.Source: Table 7 · p. 18
  • Final experimental results are averaged over 50 trials, and Table 8 reports linear-unmixing results.Source: §C.2 · p. 18, Table 8 · p. 18

Related papers

Loading 2110.13452v2…