Identifiability of deep generative models without auxiliary information

Introduction

One of the key paradigm shifts in machine learning (ML) over the past decade has been the transition from handcrafted features to automated, data-driven representation learning, typically via deep neural networks. One complication of automating this step in the ML pipeline is that it is difficult to provide guarantees on what features will (or won’t) be learned. As these methods are being used in high stakes settings such as medicine, health care, law, and finance where accountability and transparency are not just desirable but often legally required, it has become necessary to place representation learning on a rigourous scientific footing. In order to do this, it is crucial to be able to discuss ideal, target features and the underlying representations that define these features. As a result, the ML literature has begun to move beyond consideration solely of downstream tasks (e.g. classification, prediction, sampling, etc.) in order to better understand the structural foundations of deep models.

Deep generative models (DGMs) such as variational autoencoders (VAEs) (Kingma and Welling 2013; Rezende et al. 2014) are a prominent example of such a model, and are a powerful tool for unsupervised learning of latent representations, useful for a variety of downstream tasks such as sampling, prediction, classification, and clustering. Despite these successes, training DGMs is an intricate task: They are susceptible to posterior collapse and poor local minima (Yacoby et al. 2020; Dai et al. 2020; He et al. 2018; Wang et al. 2021), and characterizing their latent space remains a difficult problem (Klys et al. 2018; Van Den Oord et al. 2017, e.g.). For example, does the latent space represent semantically meaningful or practically useful features? Are the learned representations stable, or are they simply artifacts of peculiar choices of hyperparameters? These questions have been the subject of numerous studies in recent years (Schott et al. 2021; Luise et al. 2020; Locatello et al. 2019; Bansal et al. 2021; Csiszárik et al. 2021; Lenc and Vedaldi 2015, e.g.), and in order to better understand the behaviour of these models and address these questions, the machine learning literature has recently turned its attention to fundamental identifiability questions (Khemakhem et al. 2020a; D’Amour et al. 2020; Wang et al. 2021). Identifiability is a crucial primitive in machine learning tasks that is useful for probing stability, consistency, and robustness. Without identifiability, the output of a model can be unstable and unreliable, in the sense that retraining under small perturbations of the data and/or hyperparameters may result in wildly different models. Formally, identifiability means the parametrization of the model is injective. See Section 2 for details. In the context of deep generative models, the model output of interest is the latent space and the associated representations induced by the model.

In this paper, we revisit the identifiability problem in deep latent variable models and prove a surprising new result: Identifiability is possible under commonly adopted assumptions and without conditioning in the latent space, or equivalently, without weak supervision or side information in the form of auxiliary variables. This contrasts a recent line of work that has established fundamental new results regarding the identifiability of VAEs that requires conditioning on an auxiliary variable $u$ that renders each latent dimension conditionally independent (Khemakhem et al. 2020a). While this result has been generalized and relaxed in several directions (Hälvä and Hyvarinen 2020; Hälvä et al. 2021; Khemakhem et al. 2020b; Li et al. 2019; Mita et al. 2021; Sorrenson et al. 2019; Yang et al. 2021; Klindt et al. 2020; Brehmer et al. 2022), fundamentally these results still crucially rely on the side information $u$. We show that this is in fact unnecessary—confirming existing empirical studies (Willetts and Paige 2021; Falck et al. 2021, e.g)—and do so without sacrificing any representational capacity. What’s more, the model we analyze is closely related to deep architectures that have been widely used in practice (Dilokthanakul et al. 2016; Falck et al. 2021; Jiang et al. 2016; Johnson et al. 2016; Lee et al. 2020; Li et al. 2018; Willetts et al. 2019; Lee et al. 2020): We show that there is good reason for this, and provide new insight into the properties of these models and support for their continued use.

More specifically, we consider the following generative model for observations $x$:

This model has been widely studied in the literature from a variety of different perspectives:

Nonlinear ICA. When the $z_{i}$ are mutually independent, (1) recovers the standard nonlinear ICA model that has been extensively studied in the literature (Hyvärinen and Pajunen 1999; Achard and Jutten 2005; Zhang and Chan 2008; Hyvarinen and Morioka 2017; Hyvarinen et al. 2019; Hyvarinen and Morioka 2016). Although our most general results do not make independence assumptions, our results cover nonlinear ICA as a special case (see Section 3.4 for more discussion).

VAE with mixture priors. When the prior over $z$ is a mixture model (e.g. such as a GMM), the model (1) is closely related to popular autoencoder architectures such as VaDE (Jiang et al. 2016), SVAE (Johnson et al. 2016), GMVAE (Dilokthanakul et al. 2016), DLGMM (Nalisnick et al. 2016), VampPrior (Tomczak and Welling 2018), MFC-VAE (Falck et al. 2021), etc. Although such VAEs with mixture priors have been used extensively in applications, theoretical results are missing.

Warped mixtures. Another closely related model is the warped mixture model of Iwata et al. 2013, which is a Bayesian version of (1). Once again, theoretical guarantees for these models are lacking.

iVAE. Finally, (1) is also the basis of the iVAE model introduced by Khemakhem et al. 2020a, where identifiability (up to certain equivalences) is proved when there is an additional auxiliary variable $u$ that is observed such that z_{i}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 4.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 4.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 4.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 4.0mu{\scriptscriptstyle\perp}}}z_{j}\,|\,u.

Driven by this recent interest from both applied and theoretical perspectives, our main results (Theorems 3.2, 3.3) show that the model (1) is identifiable up to various linear equivalences, without conditioning or auxiliary information in the latent space. In fact, we develop a hierarchy of results under progressively stronger assumptions on the model, beginning with affine equivalence and ending up with a much stronger equivalence up to permutations only. See Table 1 for a summary.

In order to develop this hierarchy, we prove several technical results of independent interest:

First, we establish a novel identifiability result for nonparametric mixtures (Theorem C.2);

Second, we show how to use the mixture prior to strengthen existing identifiability results for nonlinear ICA (Theorem D.1);

Third, we extend existing results (Kivva et al. 2021) on the recovery of structured multivariate discrete latent variable models to recovery under an unknown affine transformation (Theorem F.1).

Our proof techniques—based on elementary tools from analytic function theory and mixture identifiability—are new and depart from existing work in this area. As a consequence, the analysis itself provides new insight into the structure and behaviour of deep generative models.

This problem is widely studied, and has garnered significant recent interest, so we focus only on the most closely related work here.

Classical results on nonlinear ICA (Hyvärinen and Pajunen 1999) establish the nonidentifiability of the general model (i.e. without restrictions on $z$ and $f$); see also Darmois 1951; Jutten et al. 2003. More recently, Khemakhem et al. 2020a proved a major breakthrough by showing that given side information $u$, identifiability of the entire generative model is possible up to certain (nonlinear) equivalences. Since this pathbreaking work, many generalizations have been proposed (Hälvä and Hyvarinen 2020; Hälvä et al. 2021; Khemakhem et al. 2020b; Li et al. 2019; Mita et al. 2021; Sorrenson et al. 2019; Yang et al. 2021; Klindt et al. 2020; Brehmer et al. 2022), all of which require some form of auxiliary information. Other approaches to identifiability include various forms of weak supervision such as contrastive learning (Zimmermann et al. 2021), group-based disentanglement (Locatello et al. 2020), and independent mechanisms (Gresele et al. 2021). Non-identifiability has also been singled out as a contributing factor to practical issues such as posterior collapse in VAEs (Wang et al. 2021; Yacoby et al. 2020).

Our approach is to avoid additional forms of supervision altogether, and enforce identifiability in a purely unsupervised fashion. Recent work along these lines includes Wang et al. 2021, who propose to use Brenier maps and input convex neural networks, and Moran et al. 2021 who leverage sparsity and an anchor feature assumption. Aside from different assumptions, the main difference between this line of work and our work is that their work only identifies the latent space $P(Z)$, whereas our focus is on jointly identifying both $P(Z)$ and $f$. In fact, we provide a decoupled set of assumptions that allow $f$ or $P(Z)$ or both to be identified. Thus, we partially resolve in the affirmative an open problem regarding model identifiability raised by the authors in their discussion.

Another distinction between this line of work and the current work is our focus on architectures and modeling assumptions that are standard in the deep generative modeling literature, specifically ReLU nonlinearities and mixture priors. As noted above, there is a recent tradition of training variational autoencoders with mixture priors (Dilokthanakul et al. 2016; Falck et al. 2021; Jiang et al. 2016; Johnson et al. 2016; Lee et al. 2020; Li et al. 2018; Willetts et al. 2019; Lee et al. 2020). Our work builds upon this empirical literature, showing that there is good reason to study such models: Not only have they been shown to be more effective compared to vanilla VAEs, we show that they have appealing theoretical properties as well. In fact, recent work (Willetts and Paige 2021; Falck et al. 2021) has observed precisely the identifiability phenomena studied in our paper, however, this work lacks rigourous theoretical results to explain these observations.

Another related line of work studies identification in graphical models with latent variables, albeit without any explicit connection to deep generative models (Pearl and Verma 1992; Evans 2016; Markham and Grosse-Wentrup 2020; Kivva et al. 2021).

Finally, since a key step in our proof involves the analysis of a nonparametric mixture model (see Appendix C for details), it is worth reviewing previous work in mixture models. See Allman et al. 2009 for an overview. Of particular use for the present work are Teicher 1963 and Barndorff-Nielsen 1965, wherein the identifiability of Gaussian and exponential family mixtures, respectively, are proved. Specifically for nonparametric mixtures, existing results consider product mixtures (Teicher 1967; Hall and Zhou 2003), grouped observations (Ritchie et al. 2020; Vandermeulen et al. 2019), symmetric measures (Hunter et al. 2007; Bordes et al. 2006), and separation conditions (Aragam et al. 2020). For context, we note here that a discrete VAE can be interpreted as a mixture model in disguise: This is a perspective that we leverage in our proofs. We are not aware of previous work in the deep generative modeling literature that exploits this connection to prove identifiability results.

Preliminaries

We first introduce the main generative model that we study and its properties, and then proceed with a brief review of identifiability in deep generative models.

$P(Z)$ is a (possibly degenerate) Gaussian mixture model with an unknown number of components $J\geq 1$, i.e.

where $p(z)$ is the density of $P(Z)$ with respect to some base measure, and $\varphi(z;\mu_{j},\Sigma_{j})$ is the gaussian density with mean $\mu_{j}$ and covariance $\Sigma_{j}$.

$f$ is a piecewise affine function, such as a multilayer perceptron with ReLU (or leaky ReLU) activations.

Recall that an affine function is a function $x\mapsto Ax+b$ for some matrix $A$. As already discussed, special cases of this model have been extensively studied in both applications and theory, and both (P1)-(F1) are quite standard in the literature on deep generative models and represent a useful model that is widely used in practice (Dilokthanakul et al. 2016; Falck et al. 2021; Jiang et al. 2016; Johnson et al. 2016; Lee et al. 2020; Li et al. 2018; Willetts et al. 2019; Lee et al. 2020, e.g.). In particular, when $J=1$ this is simply a classical VAE with an isotropic Gaussian prior (see Section 3.4 for more discussion).

The assumption that $P(Z)$ is a GMM can be replaced with more general exponential family mixtures (Barndorff-Nielsen 1965) as long as (a) the resulting mixture prior $p(z)$ is an analytic function and (b) the exponential family is closed under affine transformations.

Under assumptions (P1)-(F1), the model (1) has universal approximation capabilities. In fact, any distribution can be approximated by a mixture model (2) with sufficiently many components $J$ (Nguyen and McLachlan 2019, e.g.). Alternatively, when $J$ is bounded, by taking $f$ to be a sufficiently deep and/or wide ReLU network, any distribution can be approximated by $f(Z)$ (Lu and Lu 2020; Teshima et al. 2020, e.g.), even if $f$ is invertible (Ishikawa et al. 2022). Thus, there is no loss in representational capacity in (P1)-(F1). To the best of our knowledge, our results are the first to establish identifiability of both the latent space and decoder for deep generative models without conditioning in the latent space or weak supervision. We note that Wang et al. 2021 and Moran et al. 2021 also propose deep architectures that identify the latent space, but not the decoder.

A statistical model is specified by a (possibly infinite-dimensional, as in our setting) parameter space $\Theta$, a family of distributions $\mathcal{P}$, and a mapping $\pi\mathrel{\mathop{\mathchar 58\relax}}\Theta\to\mathcal{P}$; i.e. $\pi(\theta)\in\mathcal{P}$ for each $\theta\in\Theta$. In more conventional notation, we define $\mathcal{P}=\{p_{\theta}\mathrel{\mathop{\mathchar 58\relax}}\theta\in\Theta\}$, in which case $p_{\theta}=\pi(\theta)$. A statistical model is called identifiable if the parameter mapping $\pi$ is one-to-one (injective). In practical applications, the strict definition of identifiability is too strong, and relaxed notions of identifiability are sufficient. Classical examples include identifiability up to permutation, re-scaling, or orthogonal transformation. More generally, a statistical model is identifiable up to an equivalence relation $\sim$ defined on $\Theta$ if $\pi(\theta)=\pi(\theta^{\prime})\implies\theta\sim\theta^{\prime}$. For more details on the different notions of identifiability in deep generative models, see Khemakhem et al. 2020a; Khemakhem et al. 2020b; Roeder et al. 2021.

More precisely, we use the following definition. Let $f_{\sharp}P$ denote the pushforward measure of $P$ by $f$.

If the noise $\varepsilon$ has a known distribution, then $f_{\sharp}P$ is identifiable from the convolution $(f_{\sharp}P)\ast\varepsilon$. Hence, this definition can be automatically extended to the setup with known noise. This definition also can be extended to transformations besides affine transformations (e.g. permutations, translations, etc.) in the obvious way.

Identifiability is a crucial property for a statistical model: Without identifiability, different training runs may lead to very different parameters, making training unpredictable and replication difficult. The failure of identifiability, also known as underspecification and ill-posedness, has recently been flagged in the ML literature as a root cause of many failure modes that arise in practice (D’Amour et al. 2020; Yacoby et al. 2020; Wang et al. 2021). As a result, there has been a growing emphasis on identification in the deep learning literature, which motivates the current work. Finally, in addition to these reproducibility and interpretability concerns, identifiability is a key component in many applications of latent variable models including causal representation learning (Schölkopf et al. 2021), independent component analysis (Comon 1994), and topic modeling (Arora et al. 2012; Anandkumar et al. 2013). See Ran and Hu 2017 for additional discussion and examples.

It is well-known that assuming independence of the latent factors—i.e. Z_{i}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 4.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 4.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 4.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 4.0mu{\scriptscriptstyle\perp}}}Z_{j}—is insufficient for identifiability (Hyvärinen and Pajunen 1999). Recent work, starting with iVAE, shows identifiability by additionally assuming that a $k$-dimensional auxiliary variable $u$ is observed such that $p(z\,|\,u)$ is conditionally factorial, i.e. Z_{i}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 4.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 4.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 4.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 4.0mu{\scriptscriptstyle\perp}}}Z_{j}\,|\,U. This extra information serves to break symmetries in the latent space and is crucial to existing proofs of identifiability.

To make the connection with this work clear, observe that assumption (P1) is equivalent to assuming that there is an additional hidden state $U\in\{1,\ldots,J\}$ such that $P(Z=z\,|\,U=j)=p_{j}(z)$ and $P(U=j)=\lambda_{j}$. More generally, $U=(U_{1},\ldots,U_{k})$ may be multivariate. In this way, a direct parallel between our work and previous work is evident, with several crucial caveats:

We do not assume that $U$ is observed—even partially—or known in any way;

We allow for the $Z_{i}$ to be arbtrarily dependent even after conditioning on $U$, and this dependence need not be known;

We do not even require the number of states $J$ to be known, and we do not require any bounds on $J$ (e.g. iVAE requires $J\geq m+1$).

In the case where $U$ is multivariate (i.e $k\mathrel{\mathop{\mathchar 58\relax}}=\dim(U)>1$), we do not require the number of latent dimensions $k$, the state spaces, or their dependencies to be known.

The original iVAE paper only proves identifiability of $f$ up to a nonlinear transformation (see Lemma G.1 in Appendix G for details). By contrast, we will show identifiability of $f$ up to an affine transformation, without knowing $U$.

In order to break the symmetry without knowing anything about $U$ or its dependencies, we develop fundamentally new insights into nonparametric identifiability of latent variable models.

Main results

For any positive integer $d$, let $[d]=\{1,\ldots,d\}$. By (P1), we can write the model (1) as follows. Let $U=(U_{1},\ldots,U_{k})\in[d_{1}]\times\cdots[d_{k}]$ where $d_{i}\mathrel{\mathop{\mathchar 58\relax}}=\dim(U_{i})$ and $k\mathrel{\mathop{\mathchar 58\relax}}=\dim(U)$; we allow $U$ to be multivariate ($k>1$) and dependent—i.e., we do not assume that the $U_{i}$ are marginally independent. It follows trivially from (P1) that $P(U_{1}=u_{1},\ldots,U_{k}=u_{k})\in\{\lambda_{1},\ldots,\lambda_{J}\}$ and $J=\prod_{i}d_{i}$, where we recall that $J$ is the unknown number of mixture components in $P(Z)$. Denote the marginal distribution of $U$, which depends on $\lambda_{j}$, by $P_{\lambda}$. The variables $(U,Z)$ are unobserved and encode the underlying latent structure:

Here, $P_{\lambda}$ is the distribution on $U$ described above. Our goal is to identify the latent distribution $P(U,Z)$ and/or the nonlinear decoder $f$ from the marginal distribution $P(X)$ induced by (3). We will additionally assume throughout that $m\leq n$; see Remark 3.3 for a discussion of the overcomplete case with $m>n$.

Our main results (Theorems 3.2-3.3) provide a hierarchy of progressively stronger conditions under which $P(U,Z)$, $f$, or both, can be identified in progressively stronger ways. The idea is to illustrate explicitly what conditions are sufficient to identify the latent structure up to affine equivalence (the weakest notion of identifiability we consider), equivalence up to permutation, scaling, and translation, and permutation equivalence (the strongest notion of identifiability we consider, and the strongest possible for any latent variable model).

We defer the statement of the main results to Section 3.3, after the main conditions have been described. As a preview to the main results, we first present the following corollary:

Suppose $k=\dim(U)=1$ , $J\geq 1$, $(U,Z)$ are unobserved, and $X$ is observed. (a) If $f$ is an invertible ReLU network, then both $P(U,Z)$ and $f$ are identifiable up to an affine transformation. (b) If $f$ is only weakly injective (cf. (F2)), then $P(U,Z)$ is still identifiable up to an affine transformation.

For comparison, Corollary 3.1 already strengthens existing results, since $U$ is not required to be known and we are able to identify $f$. In fact, the latter answers an open question raised by Wang et al. 2021. What’s more, this is just the weakest result implied by our main results: Under stronger assumptions on the latent structure, the affine equivalence presented above can be strengthened further.

Taken together, the results in this section have the following concrete implication for practitioners: For stably training variational autoencoders, there is now compelling justification to work with a GMM prior and deep ReLU/Leaky-ReLU networks. As we saw above, this is commonly done in practice already.

To distinguish cases where $f$ is and is not identifiable, we require the following technical definition. Recall that for sets $A,B$, $f^{-1}(A)=\{x\mathrel{\mathop{\mathchar 58\relax}}f(x)\in A\}$ and $f(B)=\{f(x)\mathrel{\mathop{\mathchar 58\relax}}x\in B\}$.

For piecewise affine functions assumption (F2) is weaker than assumption (F3), which in turn is weaker than (F4). Therefore, for piecewise affine functions we have the chain of implications:

In the sequel, we mostly focus on (F2) and (F4) for simplicity; although we prove results for (F3) in Appendix D.1. See also Remarks 3.2, 3.5.

At the same time, $x\mapsto 0$ and $x\mapsto|x|$ are not even weakly injective.

In Appendix H, we show that ReLU networks or Leaky ReLU networks are generically observably injective (and hence also weakly injective) under simple assumptions on their architecture.

We restrict attention to the case $m\leq n$, which is a standard assumption, as it is common to think of a latent space to be a low-dimensional representation of the observed space. In the overcomplete case, i.e. when $m>n$, we believe that identifiability is unlikely unless stronger assumptions are made, or weaker notions of identifiability are considered. To see this, consider the projection $f(x,y)=x$, which is trivially affine. Then we can arbitrarily transform the $y$-coordinate without changing $P$, i.e. $(f\circ g)_{\sharp}P=f_{\sharp}P$, where $g(x,y)=(x,h(y))$ for any $h$. As an example of identifiability in the overcomplete regime under stronger assumptions, when the auxiliary variable $u$ is known, Khemakhem et al. 2020b show that the feature maps $f$ and $g$ in conditional energy-based models (for which $p(x\mid u)\propto\exp(f(x)^{T}g(u))$) can be identified up to an affine transformation.

2 Possible assumptions on ZZ

Our weakest result requires no additional assumptions on $Z$ beyond (P1); see Corollary 3.1. Under stronger assumptions, more can be concluded. As with the previous section, the assumptions presented here are not necessary, but may be imposed in order to extract stronger results.

The first condition is a mild condition that allows us to strengthen affine identifiability:

Z_{i}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 4.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 4.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 4.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 4.0mu{\scriptscriptstyle\perp}}}Z_{j}\mid U for all $i\neq j$ and there exist a pair of states $U=u_{1}$ and $U=u_{2}$ such that all $(\left(\Sigma_{u_{1}}\right)_{tt}/\left(\Sigma_{u_{2}}\right)_{tt}\mid t\in[m])$ are distinct. (Note that this implies $J\geq 2$).

The second condition is more technical, and is only necessary if $k>1$ and we wish to identify $P(U)$ in addition to $P(Z)$. In fact, not only will we recover $P(U)$, but also the (unknown) number of hidden variables (i.e. $k$) and their state spaces (i.e. $d_{j}$). Note that $P(U)$ is not needed to sample from (1), as long as we have $P(Z)$. Before introducing this condition, we need a preliminary definition.

Let $U_{-i}$ denote $\{U_{j}\mathrel{\mathop{\mathchar 58\relax}}j\neq i\}$. We define \nbhd(U_{i})=[m]\setminus\{t\mathrel{\mathop{\mathchar 58\relax}}Z_{t}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 4.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 4.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 4.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 4.0mu{\scriptscriptstyle\perp}}}U_{i}\mid U_{-i}\} and $\nbhd(Z_{i})=\{t\mathrel{\mathop{\mathchar 58\relax}}Z_{i}\in\nbhd(U_{t})\}$. For a subset $Z^{\prime}\subset Z$, $\nbhd(Z^{\prime})=\cup_{Z_{i}\in Z^{\prime}}\nbhd(Z_{i})$.

The neighborhood $\nbhd(U_{i})$ collects the variables $Z_{t}$ that depend on $U_{i}$ directly.

For all $Z^{\prime}\subset Z$ and $u_{1}\neq u_{2}$, $P(Z^{\prime}\,|\,\nbhd(Z^{\prime})=u_{1})\neq P(Z^{\prime}\,|\,\nbhd(Z^{\prime})=u_{2})$;

If $P(U^{\prime},Z,X)=P(U,Z,X)$, then $\dim(U^{\prime})\leq\dim(U)$; and

For any $U_{i}\neq U_{j}$ the set $\nbhd(U_{i})$ is not a subset of $\nbhd(U_{j})$.

Condition (P3) is a “maximality” condition that is adapted from Kivva et al. 2021: We are interested in identifying the most complex latent structure with the most number of hidden variables. This is in fact necessary since we can always merge two (or more) hidden variables into a single hidden variable without changing the joint distribution. Moreover, if two distinct hidden variables $U_{i}\neq U_{j}$ have the same neighborhood (or one is a subset of another), then it is known that $P(U)$ cannot be identified (Pearl and Verma 1992; Evans 2016; Kivva et al. 2021). Evidently, if we seek to learn $P(U)$ in addition to $P(Z)$, then this must be avoided. Finally, as the proof will indicate, this condition is slightly stronger than what is needed (see Remark F.2 for details).

Condition (P3) should be contrasted with the stronger “anchor words” assumption that has appeared in prior work (Arora et al. 2012; Arora et al. 2013; Moran et al. 2021): In fact, the existence of an anchor word for each $U_{j}$ automatically implies that $\nbhd(U_{i})$ is not a subset of $\nbhd(U_{j})$ for $i\neq j$. Thus, anchor words are a sufficient but not necessary condition for identifiability, whereas Condition (P3) is indeed necessary as described above.

More details and discussion on these assumptions can be found in Appendix F.

3 Main identifiability results

When $\dim(U)=1$, there is no additional structure in $U$ to learn, and so the setting simplifies considerably. We begin with this special case before considering the case of general multivariate $U$.

Assume $\dim(U)=1$. Under (P1)-(F1), we have the following:

(F2)$\implies P(U,Z)$ is identifiable from $P(X)$ up to an affine transformation of $Z$.

(F2)+(P2)$\implies P(U,Z)$ is identifiable from $P(X)$ up to permutation, scaling, and/or translation of $Z$.

In either (a) or (b), if additionally (F4) holds and $f$ is continuous, then $f$ is also identifiable from $P(X)$ up to an affine transformation.

The next result generalizes Theorem 3.2 to arbitrary (possibly multivariate) discrete $U$. This is an especially challenging case: Unlike previous work such as iVAE that assumes $U$ (and hence its structure) is known, we do not assume anything about $U$ is known. Thus, everything about $U$ must be reconstructed based on $P(X)$ alone, hence the need for (P3) to identify $P(U)$ below.

(F2)$\implies P(Z)$ is identifiable from $P(X)$ up to an affine transformation.

(F2)+(P2)$\implies P(Z)$ is identifiable from $P(X)$ up to permutation, scaling, and/or translation.

(F2)+(P2)+(P3)$\implies(k,d_{1},\ldots,d_{k},P(U))$ are identifiable from $P(X)$ up to a permutation of $U$, and $P(Z)$ is identifiable up to permutation, scaling, and/or translation.

In any of (a), (b), or (c), if additionally (F4) holds and $f$ is continuous, then $f$ is also identifiable from $P(X)$ up to an affine transformation.

Without (P3), Kivva et al. 2021 have shown that it is not possible to recover the high-dimensional latent state $U$, however, we can still identify the continuous latent state $Z$, which is enough to generate random samples from the model (1). In order to have fine-grained control over the individual variables in $U$, however, it is necessary to assume (P3).

If the assumption (F2) that $f$ is weakly injective is removed, then the claim of Theorem 3.2 is not true anymore. Consider $g(x)=f(x)=|x|$ and

It is easy to verify that $P$ cannot be transformed into $P^{\prime}$ by an affine transformation, but $f_{\sharp}P$ and $g_{\sharp}P^{\prime}$ are equally distributed.

4 Special cases

Our main results contain some notable special cases that warrant additional discussion.

The classical, vanilla VAE (Kingma and Welling 2013; Rezende et al. 2014) with an isotropic Gaussian prior is equivalent to (3) with $J=1$. In this case, $U$ is trivial and the Gaussian distribution $P(Z)$ can be transformed by an affine map to a standard isotropic Gaussian $\mathcal{N}(0,I)$. In this case, Theorem 3.2(c) shows that $f$ is identifiable from $P(X)$ up to an orthogonal transformation. In fact, this case can readily be deduced from known results on the identifiability of ReLU networks, e.g. Stock and Gribonval 2021.

Although the $J=1$ case is already identifiable, there are clear reasons to prefer a clustered latent space: It is natural to model data that has several clusters by a latent space that has similar clusters (e.g. Figure 2). Although in principle any distribution can be approximated by $f(Z)$ where $Z\sim\mathcal{N}(0,I)$ and $f$ is piecewise affine, such $f$ is likely to be extremely complex. At the same time, the same distribution may have a representation with $Z$ being a simple GMM and $f$ being a simple piecewise affine function. Clearly, the latter representation is preferable to the former and can likely be more robustly learned in practice. This is consistent with previous empirical work (Dilokthanakul et al. 2016; Falck et al. 2021; Jiang et al. 2016; Johnson et al. 2016; Lee et al. 2020; Li et al. 2018; Willetts et al. 2019).

In classical linear ICA (Comon 1994), we observe $X=AZ$, where $Z$ is assumed to have independent components. Compared to the general model (1), this corresponds to the special case where $f$ is linear and $\varepsilon=0$. In our most general setting under (F2) only, our results imply that $P(Z)$ can be recovered up to an affine transformation without assuming independent components, which might seem surprising at first. This is, however, easily explained: In this case, $X$ is also a GMM, and hence $P(Z)$ can already be trivially recovered up to the affine transformation $z\mapsto Az$. This follows from well-known identifiability results for GMMs (Teicher 1963). This provides some intuition to how the mixture prior assumption (P1) helps to achieve identifiability.

In classical nonlinear ICA, one assumes the model (1) with (a) no assumptions on $f$ and (b) independence assumptions in the latent space. It is well-known that this model is nonidentifiable (Hyvärinen and Pajunen 1999). Our problem setting is distinguished from the classical nonlinear ICA model via assumptions (P1)-(F1). While we do not require the $Z_{i}$ to be mutually independent, we impose assumptions on the form of $f$. It is precisely this inductive bias that allows us to recover identifiability. As a result, our identifiability theory does not contradict known results such as the Darmois construction (Darmois 1951) discussed in Hyvärinen and Pajunen 1999.

5 Counterexamples

A natural question is whether or not the mixture prior (P1) or the piecewise affine nonlinearity (F1) can be relaxed while still maintaining identifiability. In fact, it is not hard to show this is not possible: If either (P1) or (F1) is broken, then the model (1) becomes nonidentifiable. Of course, this is entirely expected given known negative results on nonlinear ICA (Hyvärinen and Pajunen 1999).

If $f$ is allowed to be arbitrary, but (P1) is still enforced, then (1) is no longer identifiable: Pick any two GMMs $P=\sum_{j=1}^{J}\lambda_{j}N(\mu_{j},\Sigma_{j})$ and $P^{\prime}=\sum_{j=1}^{J^{\prime}}\lambda_{j}^{\prime}N(\mu_{j}^{\prime},\Sigma_{j}^{\prime})$. Then we can always find a function $g$ such that $g_{\sharp}P^{\prime}=f_{\sharp}P$ (e.g. use the inverse CDF transform), and $g\neq f$.

Experiments

There has been extensive work already to verify empirically that the model (1) under (P1)-(F1) is identifiable. For example, Willetts and Paige 2021 observe that deep generative models with clustered latent spaces are empirically identifiable, and compared this directly to models that rely on side information, and Falck et al. 2021 show that meaningful latent variables can be learned consistently in a fully unsupervised manner even when $U$ has high-dimensional structure. Moreover, Falck et al. 2021 indicate that high-dimensional structure is important for improved performance. Beyond these, it is well-known that VAEs with mixture priors such as VaDE (Jiang et al. 2016) achieve competitive performance on many benchmark tasks; see Dilokthanakul et al. 2016; Falck et al. 2021; Johnson et al. 2016; Lee et al. 2020; Li et al. 2018; Willetts et al. 2019; Lee et al. 2020 for additional experiments and verification. Building upon the established success of these methods, we augment these experiments as follows: 1) We use simple examples to verify that the likelihood indeed has a unique minimizer at the ground truth parameters; 2) We train VaDE on (misspecified) simulated toy models; and 3) We measure stability (up to affine transformations) of the learnt latent spaces on real data. To measure this, we report the Mean Correlation Coefficient (Khemakhem et al. 2020b, Appendix A.2) metric, which is standard, and an $L^{2}$-based alignment metric (denoted by $\dist_{\Aff,L2}$). Definitions of these metrics and additional details on the experiments can be found in Appendix J.

We simulated models satisfying (P1)-(F1) by randomly choosing weights and biases for a single-layer ReLU network and randomly generating a GMM with $J=2$ or 3 components. These models are simple enough that exact computation of the MLE along the likelihood surface is feasible via numerical integration (Figure 1). In all our simulations (50 total), the ground truth was the unique minimizer of the negative log-likelihood, as predicted by the theory. These examples also illustrate a small-scale test of misspecification in the theoretical model: We include cases where $J$ is misspecified and $f$ fails to satisfy (F4), but the MLE succeeds anyway.

In our experiments on synthetic datasets we consider, to obtain an experimental evidence of identifiability of model (3) we fit VaDE to observed data 5 times (see Figure 2). Let $Z^{(1)},Z^{(2)},\ldots,Z^{(5)}$ be the learned latent spaces. For every pair $Z^{(i)},Z^{(j)}$ we evaluate the MCC and $\dist_{\Aff,L2}$ loss.

For instance, for the pinwheel dataset with three clusters as in Figure 2, the average $\dist_{\Aff,L2}(p_{1},p_{2})$ across 20 pairs $Z^{(i)},Z^{(j)}$ is 0.113 with standard deviation 0.065. The average weak MCC is 0.87 and the average strong MCC is 1.0. This shows strong evidence of recovery of the latent space up to affine transformations.

We measure stability of the learnt latent space by training MFCVAE (Falck et al. 2021) on MNIST 10 times with different initializations and then comparing the latent representations learnt. It becomes computationally infeasible to compute $\dist_{\Aff,L2}$ therefore we report only MCC. The strong MCCs are computed to be $0.7$ (ReLU), $0.69$ (LeakyReLU) and the weak MCCs are computed to be $0.91$ (ReLU), $0.94$ (LeakyReLU). These observations validate the observations first made in Willetts and Paige 2021, who ran extensive experiments on VaDE and iVAE on several large datasets including MNIST, SVHN and CIFAR10. These strong correlations confirm our theory and are of particular importance to practitioners for whom stability of learning is of the essence.

Conclusion

We have proved a general series of results describing a hierarchy of identifiability for deep generative models that are currently used in practice. Our experiments confirm both on exact and approximate simulations that identifiability indeed holds in practice. An obvious direction for future work is to study finite-sample identifiability problems such as sample complexity and robustness (i.e. how many samples are needed to ensure that the global minimizer of the likelihood is reliably close to the ground truth?). Theoretical questions aside, developing a better understanding of the ELBO and its effect on optimization is an important practical question. For example, an important limitation of the current set of results is that they apply only to the likelihood, which is known to be nonconvex and intractable to optimize (see Figure 1 for concrete examples). It is an important open question to use these insights to develop better algorithms and optimization techniques that work on finite-samples with misspecified models (i.e. real data).

More generally, although our assumptions map onto architectures and priors that are widely used in practice, it is important to emphasize the relevant distinction between models and estimators. That is, the architectures used in practice represent the estimators used, and may not reflect realistic assumptions on the model itself (which is typically misspecified). For example, the piecewise affine assumption may not accurately reflect valid assumptions about real-world problems. Given the lack of purely unsupervised, nonparametric identifiability results in the literature, we view our results as an important technical step towards understanding practical identifiability for deep generative models. Thus, an important future direction is to replace our assumptions with more appropriate modeling assumptions that are relevant for practical applications.

Acknowledgements

We thank anonymous reviewers for useful comments and suggestions. G.R. was partially supported by NSF grants CCF-1816372 and CCF-200892. B.A. was supported by NSF IIS-1956330, NIH R01GM140467, and the Robert H. Topel Faculty Research Fund at the University of Chicago Booth School of Business. P.R. was supported by ONR via N000141812861, and NSF via IIS-1909816, IIS-1955532, IIS-2211907.

References

Appendix A Detailed comparisons

Since the original iVAE paper (Khemakhem et al. 2020a), there have been many generalizations and extensions proposed. We pause here to provide a more detailed comparison of our results against this developing literature. For a comparison against iVAE, see Section 2.

We first discuss related work that assumes auxiliary information is available (i.e. $U$ is known), then discuss more recent work that does not assume any auxiliary information; the ensuing comparisons are then presented in alphabetical order.

Hälvä and Hyvarinen 2020 achieves identifiability in the fully unsupervised regime for the model in which the latent state is defined by a Hidden Markov Model (HMM). The proof of identifiability in Hälvä and Hyvarinen 2020 invokes Gassiat et al. 2016 to essentially recover the HMM transition matrix and the auxiliary variable $U$ from $X$, reducing the problem to Khemakhem et al. 2020a. Our Theorem C.1 shows that identifiability in fully unsupervised regime is possible even without additional structure given here by the time-dependency according to Markov dynamics.

Khemakhem et al. 2020b extend Khemakhem et al. 2020a by observing that the conditional independence Z_{i}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 4.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 4.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 4.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 4.0mu{\scriptscriptstyle\perp}}}Z_{j}\mid U is not required for identifiability, so they propose a more general IMCA framework for conditional energy-based models. However, identifiability in Khemakhem et al. 2020b still critically relies on observing an auxiliary variable (in their setting, this is a dependent variable $Y$). Our Theorem C.1 achieves same type of identifiability as Khemakhem et al. 2020b (up to affine transformation) without relying on conditional independence or an auxiliary variable.

Sorrenson et al. 2019 extends the iVAE identifiability theory of Khemakhem et al. 2020a by showing that a stronger notion of identifiability can be achieved if $Z$ is distributed according to factorial GMM (instead of a general exponential family as in Khemakhem et al. 2020a). More specifically, given the auxiliary information $U$, they show that $Z$ can be recovered up to permutation and scaling of the variables $Z_{i}$. By contrast, in Theorem E.2, we show that under similar assumptions $Z_{i}$ are identifiable up to permutation and scaling and importantly, we do this only from $X$, without using $U$ in any way. We also do not require the GMM to be factorial. Finally, our proof technique is different: While Sorrenson et al. 2019 relies on Khemakhem et al. 2020a (and hence, for instance, require $J\geq m+1$), our proof is independent of Khemakhem et al. 2020a.

Yang et al. 2021 studies identifiability of the model (3) under the assumption that $f$ is volume preserving and $Z$ comes from a conditionally factorial exponential family, similar to iVAE. They prove that if $U$ is known, (P2) holds, and $f$ is twice differentiable, then $Z$ is identifiable up to permutation and non-linear functions applied to each $Z_{i}$ (i.e., $Z_{i}=h_{i}(Z_{\tau(i)}$). If additionally $Z$ is a GMM, then $Z$ can be recovered up to permutation, scaling, and translation. In comparison, we do not require $U$ to be known, and we do not require $f$ to be volume preserving or even differentiable everywhere. We show that under the same assumption (P2) the latent variables $Z_{i}$ can be recovered up to permutation, scaling, and translation if $f$ is only assumed to be piecewise affine. Additionally, we show that a weaker notion of identifiability holds if $Z$ is not assumed to be conditionally factorial.

Zimmermann et al. 2021 considers a contrastive model in which samples arrive in pairs, which is a type of weak supervision. Additionally, it is assumed that the latent variables are sampled uniformly from a convex body, and that $f$ is differentiable and injective. By comparison, our model allows for more general non-uniform mixture priors, non-injective and non-smooth $f$, and is fully unsupervised.

Falck et al. 2021 propose a novel Multifacet VAE (MFCVAE) model for unsupervised deep clustering. Their model has the following form

Through empirical experiments, Falck et al. 2021 emphasizes the importance of high-dimentional structure of $U$ and shows how it results in improved clustering performance. The key idea is that while the number of meaningful clusters in the data may be very large, there may be meaningful individual categorical variables $U_{i}$ (“facets”) with a much smaller number of states, which may be easier to learn. In this way, by simultaneously performing clustering for each “facet” $U_{i}$ one can learn meaningful fine-grained clusters in the data. Note that $k$ binary variables $U_{i}$ result in $J=2^{k}$ fine-grained clusters in the data.

Compared to our work, Falck et al. 2021 is focused on practical implementation details, and lacks a formal identifiability theory. In fact, our results provide precisely such a formal identifiability theory in a more general setting. If $p(x|z)$ is modeled by ReLU/leaky-ReLU NN, MFCVAE is a special case of our model (3) with high-dimensional $U$. More specifically, the MFCVAE model (5) restricts our model (3) to the case when $u_{i}$ are independent and $\nbhd(U_{i})=\{i\}$. In particular, it satisfies assumption (P3). Therefore, Theorem 3.3 implies that for MFCVAE with diagonal covariances $\Sigma_{u_{j}}$, $\dim(U),\dim(U_{j})$, $P(U)$ are identifiable from $P(X)$ up to a permutation of $U$, and $P(Z)$ is identifiable up to permutation, scaling, and/or translation.

Kivva et al. 2021 establishes the identifiability of latent representations for non-parametric measurement models $U\rightarrow X$. Their result crucially relies on the fact that observed variables are conditionally independent X_{i}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 4.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 4.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 4.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 4.0mu{\scriptscriptstyle\perp}}}X_{j}\mid U. Our Theorem F.1 significantly generalizes this result, by showing the same guarantees for the model (3) that allows arbitrarily complex dependencies between the observed variables $X$.

Moran et al. 2021 propose a sparse VAE and prove that the latent space of this model is identifiable. Similar to Wang et al. 2021, identifiability of $f$ is not addressed. Their identifiability results also assume an anchor feature assumption, which we do not require. Even our strongest assumption (P3) is weaker compared to the anchor feature assumption (see Remark 3.4). Moreover, we do not require any sparsity assumptions.

Wang et al. 2021 propose LIDVAE as a way to identify the latent space of a VAE without auxiliary information, however, their approach only guararantees identifiability of $P(Z)$, and does not address $f$ (this is acknowledged by the authors in their discussion as an open question). By restricting $f$ to be a Brenier map, they guarantee that the likelihood is injective, which leads to identifiability of $P(Z)$. Compared to Wang et al. 2021 our work restricts $f$ in a different way (i.e. by an injective ReLU network), which matches common practice. Moreover, we show that both $f$ and the multivariate $U$ structure (i.e. in addition to $P(Z)$) are identifiable under mild additional assumptions.

Appendix B Proof outline

We will prove the main results by breaking the argument into four phases:

(Appendix D) Second, we show that if $f$ is continuous and injective, then $f$ is identifiable up to an affine transformation (Theorem D.1). This result strengthens existing identifiability results in nonlinear ICA by exploiting the mixture prior, which is crucial in the sequel.

(Appendix E) Next, we show that if $Z$ is conditionally factorial GMM, then under mild generic assumptions, the individual variables $Z_{i}$ can be recovered (up to permutation, scaling and translation) (Theorem E.1).

(Appendix F) Finally, since for conditionally factorial $Z$ we are able to recover the individual variables $Z_{i}$, we show how we can apply the theory developed in Kivva et al. 2021 to recover the multivariate discrete latent variable $U$, its dimension, domain sizes of each $U_{i}$ and $\Pr(U,Z)$ (Theorem F.1). Since we can only recover $Z$ up to permutation, scaling and translation, the results from Kivva et al. 2021 cannot be applied directly, and we show how to perform this recovery under an unknown affine transformation.

Each of these phases tackles a particular level of the identifiability hierarchy described in the main theorems. A detailed proof outline of each main theorem is provided below; technical proofs can be found in the subsequent appendices.

A notable difference between Theorems 3.2 ($k=1$) and 3.3 ($k>1$) is the conclusion in the latent space: Theorem 3.2 identifies $P(U,Z)$ jointly whereas Theorem 3.3 identifies $P(Z)$ and $P(U)$ separately. The reason is simple: If $U$ is 1-dimensional, i.e., $k=1$, then $P(U,Z)$ for (3) is trivially identifiable from $P(Z)$, since $P(Z)$ is assumed to be a GMM by (P1). Indeed, since finite mixture of Gaussians are identifiable, we can recover $P(U=u)$ and $P(Z\mid U=u)$ as mixture weights and corresponding Gaussian components. This extends to more general exponential mixtures as in Remark 2.1, see Barndorff-Nielsen 1965 for details.

When $k>1$, the situation is considerably more nontrivial, as one also needs to learn the high-dimensional structure of $U$.

We assume $\varepsilon=0$ without any loss of generality; i.e. it is sufficient to consider the noiseless case. This follows from a standard deconvolution argument as in Khemakhem et al. 2020b (see Step I of the proof of Theorem 1).

Since $P(Z)$ is identifiable up to an affine transformation by part a), claim follows from Theorem E.1.

As with Theorem 3.2, we assume $\varepsilon=0$ without loss of generality.

Since $P(Z)$ is identifiable up to an affine transformation by part a), by Theorem E.1, $Z_{i}$ are identifiable up to permutation, scaling and translation.

Appendix C Identifiability of ZZ up to an affine transformation via nonparametric mixtures

In this section we prove that if in model (3) the function $f$ is weakly injective, then $Z$ is identifiable up to an affine transformation. More specifically, we prove the following:

We will prove this result by first proving a result on identifiability of nonparametric mixtures that may be of independent interest.

In other words, a mixture model whose components are piecewise affine transformations of a Gaussian is identifiable. To see this more clearly, observe that

To the best of our knowledge, this identifiability result for a nonparametric mixture model is new to the literature. In Theorem C.2, the transformation and number of components is allowed to be unknown and arbitrary, and no separation or independence assumptions are needed.

We recall that a $m$-dimensional Gaussian distribution $\mathcal{N}(\mu,\Sigma)$ with covariance $\Sigma$ and mean $\mu$ has the following density function

We say that a Gaussian mixture distribution

is in reduced form if $\lambda_{j}>0$ for every $j\in[J]$ and for every $i\neq j\in[J]$ we have $(\mu_{i},\Sigma_{i})\neq(\mu_{j},\Sigma_{j})$.

In the proofs we use the notion of real analytic functions. We remind the definition for reader’s convenience.

Assume that there exists a ball $B(x_{0},\delta)$ such that $P$ and $P^{\prime}$ induce the same measure on $B(x_{0},\delta)$. Then $P\equiv P^{\prime}$, i.e., $J=J^{\prime}$ and for some permutation $\tau$ we have $\lambda_{i}=\lambda^{\prime}_{\tau(i)}$ and $(\mu_{i},\Sigma_{i})=(\mu^{\prime}_{\tau(i)},\Sigma^{\prime}_{\tau(i)})$.

Follows from the identity theorem for real analytic functions and the identifiability of finite GMMs. ∎

We make the following useful observation.

Let $0<\delta<\delta_{0}$. Then, for $\mu_{ij}^{\prime}=A_{i}\mu_{k}+b_{i}$ and $\Sigma_{ij}=A_{i}\Sigma_{j}A_{i}^{T}$, and every $x\in B(x_{0},\delta)$ we have

C.2 Identifiability of nonparametric mixtures

First we prove our identifiability theorem under the assumption that $f$ and $g$ are invertible in the neighborhood of the same point.

Combining this identifiability result with results of Section C.1, we obtain the proof of our main identifiability result for non-parametric mixtures.

C.3 Proof of Theorem C.1

Appendix D Identifiability of ff

In this section we show that if $f$ is continuous piecewise affine and injective then it is identifiable from $P(X)$ up to an affine transformation.

Assume that $(U,Z,X)$ are distributed according to model (3). Assume that $f$ is continuous piecewise affine and satisfies (F4) (i.e., $f$ is injective).

Before proving this theorem, we provide an example that shows that assumption (F2) does not guarantee that $f$ can be recovered uniquely up to an affine transformation in Theorem C.1.

Define a pair of piecewise affine functions (see also Figure 3)

Then it is easy to see that $f(Y)$ and $g(Y)$ have the same distribution, but $f$ cannot be transformed into $g$ by an affine transformation.

In order to prove Theorem D.1 we need to show that for a mixture of Gaussians $P$ and a pair of piecewise affine functions $f,g$ if $f_{\sharp}P=g_{\sharp}P$, then $f=h\circ g$ for some invertible affine $h$. We first consider the case when $g$ is the identity.

If $f$ is not affine, then there exist an $(m-1)$-dimensional affine subspace $L$, $z_{0}\in L$ and $\delta>0$ such that the following holds: The subspace $L$ divides $B(z_{0},\delta)$ into two sets (formally, these are “half-balls”) $B^{+}$ and $B^{-}$ such that $f_{+}(z)\mathrel{\mathop{\mathchar 58\relax}}=f|_{B^{+}}(z)=A_{1}z+b_{1}$ and $f_{-}(z)\mathrel{\mathop{\mathchar 58\relax}}=f|_{B^{-}}(z)=A_{2}z+b_{2}$, where $(A_{1},b_{1})\neq(A_{2},b_{2})$ and $A_{1},A_{2}$ are invertible.

as multisets (i.e. including repetitions). Let $\mu_{*}=\dfrac{1}{J}\sum\limits_{j=1}^{J}\mu_{j}$. Then, since $f_{+}$ and $f_{-}$ are affine we get $f_{+}(\mu_{*})=f_{-}(\mu_{*})=\mu_{*}$. By translating $Y$ and adjusting $f$ accordingly, we may assume that $\mu^{*}=0$. In this case, $b_{1}=b_{2}=0$. Moreover, since $f_{+}(z)=f_{-}(z)$ for $z\in L$, we get

as multisets (i.e. including repetitions). This implies that

Hence, $\det(A_{1})^{2}=\det(A_{2})^{2}=1$, and $\det(A_{1}^{-1}A_{2})^{2}=1$. By (17), $A_{1}^{-1}A_{2}$ is the identity map on $L$. Let $v$ be a unit vector orthogonal to $L$ (in the direction of $B^{+}$). Then we get that either $A_{1}^{-1}A_{2}v=v$, or $A_{1}^{-1}A_{2}v=-v$. In the latter case $A_{1}(y_{0}+(\delta/2)v)=A_{2}(y_{0}-(\delta/2)v)$, which means that $f$ is not injective. This contradicts Lemma C.5. Therefore, we must have $A_{1}^{-1}A_{2}v=v$, and so, by (17), $A_{1}=A_{2}$.

Therefore, $f_{+}=f_{-}$, which contradicts $(A_{1},b_{1})\neq(A_{2},b_{2})$. It follows that $f$ must be affine. ∎

Hence the claim of the theorem holds for $h=h_{0}\circ h_{1}$. ∎

Immediately follows from Theorems C.1 and D.3. ∎

In this section we discuss the case (F3). In particular, show that in (3) under the weaker assumption (F3), $f$ is identifiable up to an affine transformation on the preimage of every connected open set onto which $f$ is injective.

Let $Z~\sim\sum\limits_{i=1}^{J}\lambda_{i}\mathcal{N}(\mu_{i},\Sigma_{i})$ and $Z^{\prime}\sim\sum\limits_{j=1}^{J^{\prime}}\lambda_{j}^{\prime}\mathcal{N}(\mu_{j}^{\prime},\Sigma_{j}^{\prime})$ be a pair of variables with GMM distribution (in reduced form). Suppose that $f(Z)$ and $g(Z^{\prime})$ are equally distributed.

Therefore, for $h=(h_{0}\circ h_{1})$, we have $g(y)=(f\circ h^{-1})(z)$ for every $z\in g^{-1}(\mathcal{D})$. ∎

Let $f$ be a continuous piecewise affine function that satisfies (F3). Denote

Appendix E Identifiability of ZZ up to a permutation, scaling and translation

where $\Sigma_{j}$ is diagonal for every $j\in[J]$. In the setup of model (3) this just means that Z_{i}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 4.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 4.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 4.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 4.0mu{\scriptscriptstyle\perp}}}Z_{j}\mid U.

Let $J\geq 2$, and $\lambda_{j}>0$ for all $j\in[J]$. Let $Z=(Z_{1},Z_{2},\ldots,Z_{m})$ be given by

The translation $b$ is impossible to recover without stronger assumptions, as $b$ corresponds to an arbitrary translation in the $Z$ space. In other words, choice of $b$ determines the origin in the coordinate space of $Z$ and it can be completely arbitrary.

A slightly different version of Theorem E.1 under different assumptions appeared in Yang et al. 2021. The main difference is that Yang et al. 2021 assumed that $f$ is volume-preserving but nonlinear, whereas we restrict to the general (i.e. not necessarily volume-preserving) linear case.

Without loss of generality assume $i_{1}=1$ and $i_{2}=2$.

Let $\Sigma_{i}$ be the covariance matrices of $Z_{i}$ and let $\widetilde{\Sigma}_{i}$ be the covariance matrices of $Y_{i}$ for $i\in[J]$. Clearly

The matrices $\widetilde{\Sigma}_{i}$ are PSD. Therefore, using SVD we can find PSD matrices $V_{i}$, such that for every $i\in[J]$,

Moreover, such a decomposition is unique up to an orthogonal matrix, i.e., for every pair of such decompositions $\widetilde{\Sigma}_{i}=V_{i}V_{i}^{T}=V_{i}^{\prime}(V_{i}^{\prime})^{T}$ there exists a unitary matrix $R$ such that $V_{i}R=V_{i}^{\prime}$. Therefore, for every $i\in[J]$ there exists a matrix $R_{i}$, such that

Since $R_{1}$ and $R_{2}^{-1}$ are unitary and $\left(\Sigma_{1}^{-1/2}\Sigma_{2}^{1/2}\right)$ is diagonal, they can be determined from the SVD of $V_{1}^{-1}V_{2}$. Moreover, they can be determined uniquely up to a permutation matrix since all diagonal entries of $\Sigma_{1}^{-1/2}\Sigma_{2}^{1/2}$ are distinct. In other words, using SVD for $\left(V_{1}^{-1}V_{2}\right)$ we can find $R_{1}^{\prime}$ such that for some permutation matrix $P$ we have

As an immediate corollary we can deduce the following theorem from Theorem C.1.

Assume that $(U,Z,X)$ are distributed according to model (3) and that $f$ is weakly injective. Suppose that Z_{i}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 4.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 4.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 4.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 4.0mu{\scriptscriptstyle\perp}}}Z_{j}\mid U for all $i\neq j$. Moreover, assume that there exist a pair of states $U=u_{1}$ and $U=u_{2}$ such that all $(\left(\Sigma_{u_{1}}\right)_{tt}/\left(\Sigma_{u_{2}}\right)_{tt}\mid t\in[m])$ are distinct.

Then $P(U,Z)$ is identifiable from $P(X)$ up to permutation, scaling ans translation of $Z_{i}$.

Now, by Theorem E.1, we can find $A^{\prime}$ such that $Z^{\prime}=(A^{\prime})^{-1}Y=QDZ+(A^{\prime})^{-1}b$, where $Q$ is a permutation matrix and $D$ is a diagonal matrix. This means, that we can recover $Z$ up to permutation, shift and scaling of individual variables $Z_{i}$. ∎

Appendix F Identifiability of multivariate UU structure

When $k=1$, $P(Z)$ contains all the information about $P(U,Z)$, however, when $k>1$ (i.e. $U$ is multivariate), this may not be true anymore. It is not even obvious that $P(Z)$ must contain information about the true dimension of $U$. The distribution $P(U,Z)$ may contain interesting dependencies between individual variables $U_{i}$ and $Z_{j}$.

Previously, Kivva et al. 2021 studied necessary and sufficient conditions for identifiability of $P(U)$ when $Z$ is observed under the so-called measurement model. A key limitation of Kivva et al. 2021 is that it requires the observed variables to be conditionally independent, which is not the case in our setting. Ultimately, this is a consequence of $Z$ being unobserved: Previous work such as Kivva et al. 2021 assumes there is only a single layer of hidden variables connected to the observations. In our setting, under (3), we need to recover $U$ from $Z$, the latter of which is unobserved. As a result, if we can only identify $Z$ up to an affine transformation (e.g., like in Theorem C.1); i.e. we can only recover $Z^{\prime}=AZ+b$, then it almost surely will not be conditionally factorial. Hence, the results from Kivva et al. 2021 cannot be applied directly for weak (e.g., up to affine transformation, or as in Khemakhem et al. 2020a) notions of identifiability of $Z$.

Luckily, in Section E, we showed how to recover the true $Z$ from $Z^{\prime}=AZ+b$. This will enable us to identify $P(U)$ in Theorem 3.3(c). In the remainder of this appendix, we outline these details.

The neighborhoods $\nbhd(Z_{i})$ define a bipartite graph between $(U_{1},\ldots,U_{k})$ and $(Z_{1},\ldots,Z_{m})$ that is described in Kivva et al. 2021. Since this graph is not needed for our purposes, we proceed without further mention of this graph. The assumptions below have been re-phrased accordingly.

Kivva et al. 2021 show that assumptions (L1)-(L4) below are necessary for identifiability of $U$.

(No twins) For any $U_{i}\neq U_{j}$ we have $\nbhd(U_{i})\neq\nbhd(U_{j})$.

(Maximality) There is no $U^{\prime}$ such that:

$U^{\prime}$ is obtained from $U$ by splitting a hidden variable (equivalently, $U$ is obtained from $U^{\prime}$ by merging a pair of vertices);

(Nondegeneracy) The distribution over $(U,Z)$ satisfies:

(Subset condition) For any pair of distinct variables $U_{i},U_{j}$ the set $\nbhd(U_{i})$ is not a subset of $\nbhd(U_{j})$.

We prove the following identifiability result.

Assume that $(U,Z,X)$ are distributed as in (3) and that $f$ satisfies (F2). Assume further that (P2)-(P3) hold and $P(U=u)>0$ for all $u$ in the domain of $U$.

The assumptions of Theorem F.1 are stronger than those of Theorem E.2, so by Theorem E.2, $P(Z)$ is identifiable up to a permutation, scaling and translation of $Z$.

Combined with the positivity assumption $P(U=u)>0$, the assumptions (L1)-(L4) are weaker than assumption (P3). Indeed, (P3) (a) is equivalent to (L3) (b); (P3) (c) is equivalent to (L4) and implies (L1); and, finally, (P3) (b) and (c) together imply (L2).

As the proof indicates, assumptions (L1)-(L4) are weaker than (P3), so Theorem F.1 implies part (c) of Theorem 3.3.

Appendix G Equivalence in iVAE

In this section we compare the equivalence relation up to which iVAE (Khemakhem et al. 2020a) guarantees identifiability and equivalence up to an affine transformation. While iVAE achieves the best possible identifiability under the assumptions they make, we show that identifiability up to an affine transformation is considerably stronger.

Recall that iVAE (Khemakhem et al. 2020a) considers the following model, which differs from (3) by assuming that $Z$ has conditionally factorial exponential family distribution:

Here $T_{i}=(T_{1},T_{2},\ldots T_{t})$ are sufficient statistics, $Q_{i}$ is the base measure and $\lambda_{i,j}$ parameters depending on $u$. iVAE defines the following equivalence relation:

This type of identifiability allows for essentially any (synchronized) changes to $Z$ and $f$:

Moreover, if $Z$ has exponential family distribution with statistics $T$, then $Z^{\prime}=\varphi^{-1}(Z)$, has an exponential family distribution with statistics $T^{\prime}$, and $f(Z)\sim f^{\prime}(Z^{\prime})$.

We have $(f^{\prime})^{-1}=\varphi^{-1}\circ f^{-1}$, so $T^{\prime}\circ(f^{\prime})^{-1}=T\circ f$. Hence $(f,T,\sigma)\sim(f^{\prime},T^{\prime},\sigma^{\prime})$, where in (27) $A$ is the identity map and $c=0$.

Since $Z$ comes from an exponential family distribution, we can write

Let $Z^{\prime}=\varphi^{-1}(Z)$. Then by the change of variable formula

where $Jac(\varphi)$ is the Jacobian of $\varphi$. Hence $Z^{\prime}$ indeed has an exponential family distribution with statistics $T^{\prime}$. Clearly, $f^{\prime}(Z^{\prime})=(f\circ\varphi\circ\varphi^{-1})(Z)\equiv f(Z)$. ∎

In other words, the equivalence relation (27) allows an arbitrary (possibly highly nonlinear) change of basis in the latent $Z$ space. In principle, this may indicate, that any meaningful analysis of the $Z$ space in this setup may be challenging.

G.2 GMMs give more robust identifiability

The next result was also observed in Sorrenson et al. 2019. We present a slightly simplified proof for completeness.

For product measures, there are no cross-terms $z_{i}z_{j}$.

This means that for every $i$ there exists a polynomial $p_{i}$ of degree at most $2$ such that $z_{i}=p_{i}(z^{\prime}_{1},\ldots,z_{m}^{\prime})$. Assume that for some $i$, we have $\deg(p_{i})=2$. Then it is easy to verify (say, by using lexicographical order on monomials) that $\deg(p_{i}^{2})=4$. If $z^{\prime}$ is defined on an open neighbourhood, we get a contradiction with (31) as $z_{i}^{2}$ can be written as a degree-2 polynomial over variables $z_{j}^{\prime}$. Therefore, every $p_{i}$ is a polynomial of degree at most 1. But this means that that $z=Mz^{\prime}+c$ for some matrix $M$ and a vector $c$. Moreover, since $A$ is invertible, $M$ is invertible as well. ∎

Appendix H Conditions on ReLU Neural Network that guarantee that it is an observable injection

For completeness, in this section we provide simple sufficient conditions on ReLU architectures that guarantee that it is an observable injection (cf. (F3)) and simple sufficient conditions on leaky-ReLU architectures which guarantee that it is injection (cf. (F4)). For a more comprehensive account of identifiability in ReLU networks, see Stock and Gribonval 2021.

We recall the definitions of ReLU and leaky-ReLU (with parameter $a>0,\ a\neq 1$) activation functions

A standard choice of $a$ for leaky-ReLU is $a=0.01$.

Let $n_{1},n_{2},\ldots,n_{t}\geq n_{0}=m$ and $\sigma$ be an activation function. Define

The function families $\mathcal{F}_{\RELU}^{m\hookrightarrow n}$, $\mathcal{F}_{\LRELU}^{m\hookrightarrow n}$ are genuinely nonparametric: There is no bound on the number of layers.

In the arguments below we do not rely on the fact that the activation function is the same on every layer, or even the same across the nodes of the same layer. However, we will give proofs only in this case, to simplify the presentation.

ReLU networks under similar assumptions were also studied in Khemakhem et al. 2020b.

We prove the claim by induction on the depth of the NN. If $t=1$, we have $f=h_{1}$ and the claim is trivial. Assume that we already proved the lemma for all $t\leq s-1$. We prove the claim for $t=s$. We can write $f$ as $f=h_{t}\circ\sigma\circ g$ where $g\in\mathcal{F}^{m\hookrightarrow n_{t-1}}_{\RELU}$.

Clearly, any $f=h_{t}\circ\sigma\circ h_{t-1}\circ\sigma\circ\ldots\sigma\circ h_{1}\in\mathcal{F}_{\LRELU}$ is a piecewise affine function. The $\LRELU$ activation function is invertible, so $f$ is invertible. Finally, since $f$ is a piecewise affine transformation, for almost all $y\in B(x_{0},\delta)$ there exists $\delta_{y}$ such that $f^{-1}$ is an affine function on $B(y,\delta_{y})$. ∎

Let $f=h_{t}\circ\sigma\circ h_{t-1}\circ\sigma\circ\ldots\sigma\circ h_{1}\in\mathcal{F}^{m\hookrightarrow n}_{\LRELU}$. Assume that $m=n_{0}\leq n_{1}\leq\ldots\leq n_{t}=n$, then generically $f$ satisfies (F4).

Generically, every $h_{i}$ has full column rank, and so is injective. Since $\LRELU$ is injective, we get that $f$ is injective. ∎

We conclude with an example of a very simple $\LRELU$ NN that is not even weakly injective.

Then $(h_{2}\circ\sigma\circ h_{1})(x)=(3x/2,x/2)$ for $x\geq 0$ and $(h_{2}\circ\sigma\circ h_{1})(x)=(3x/2,-x/2)$ for $x<0$ (see Figure 4). Let $h_{3}(x,y)=y$. Then $f(x)\mathrel{\mathop{\mathchar 58\relax}}=(h_{3}\circ\sigma\circ h_{2}\circ\sigma\circ h_{1})(x)=|x|/2$. By Remark 3.6, this implies that $f$ is not invertible at every point except 0.

Appendix J Experiment details

Previous work has relied on the Mean Correlation Coefficient (MCC) as a metric to quantify identifiability. For consistency with previous work, we report this metric, but also propose a new metric to quantify identifiability up to an affine transformation. There are two challenges in designing such a metric: Firstly, for two Gaussian mixtures, standard distance metrices such as TV-distance or KL-divergence do not have a closed form. Secondly, we need to find an affine map $A$ that best aligns a pair of Gaussian mixtures. Therefore, developing a metric to quantify identifiability up to an affine transformation has natural challenges. We propose $\dist_{\Aff,L2}$, defined below, as an additional metric in this setting.

In this work, we consider two different metrics. For a pair of distributions $p_{1},p_{2}$, we define $\dist_{\Aff,L2}$ loss as

The other metric we consider is the Mean Correlation Coefficient (MCC) metric which had been used in prior works (Khemakhem et al. 2020b; Willetts and Paige 2021). See Khemakhem et al. 2020b for a detailed discussion. There are two versions of MCC that have been used:

The strong MCC is defined to be the MCC before alignment via the affine map $A$.

The weak MCC is defined to be the MCC after alignment.

In our experiments, we report both the strong MCC and weak MCC. Moreover, all reported MCCs are out-of-sample, i.e. the optimal affine map $A$ is computed over half the dataset and then reused for the other half of the dataset.

To find the affine map $A$ that best aligns the two GMMs, we use two approaches. One approach is to use Canonical Correlation Analysis (CCA) as was done in prior works in computing MCC.

We describe an alternative approach now. Given two GMMs, we iterate over all permutations of the components and for each fixed permutation, we find the best map $A$ that maps the components accordingly. In an ideal setting, we would want to find $A$ to align not just the means but also the covariance matrices but unfortunately this is a challenging optimization problem. Therefore, we instead find $A$ that maps the means of the first GMM to the means of the second GMM. The map $A$ can be found by solving a least-squares optimization problem which is straightforward using a Singular Value Decomposition (SVD). In practice, we find that this technique of matching the means works well.

J.2 Implementation

For VaDE (Jiang et al. 2016), we use the implementation available at https://github.com/mperezcarrasco/Pytorch-VaDE. For MFCVAE (Falck et al. 2021), we use the author implementation available at https://github.com/FabianFalck/mfcvae. For iVAE (Khemakhem et al. 2020a), we use the implementation available at https://github.com/MatthewWilletts/algostability. Experiments were performed on an NVIDIA Tesla K80 GPU with 12GB memory.

J.3 Setup

Our experiments consist of three different setups, designed to probe different aspects of identifiability. First, we checked the exact log-likelihood for a unique global minimizer on simple toy models (Appendix J.3.1). We then used VaDE (Jiang et al. 2016) to train a practical VAE on a simulated dataset where the ground truth latent space is known (Appendix J.3.2). Finally, we compared the performance of MFCVAE (Falck et al. 2021) against iVAE on MNIST (Appendix J.3.3). The last experiment is based on previous work by Willetts and Paige 2021 that compares iVAE to VaDE; we successfully replicated these experiments using MFCVAE as an additional baseline that closely aligns with our assumptions.

The fact that our theory closely aligns with and replicates existing empirical work illustrates that the model (3) is not merely a theoretical curiosity, but in fact practically relevant in modern applications. In our view, this is a significant advantage compared to related work.

We simulated random models of the form (1) as follows:

Randomly select $(\lambda_{1},\ldots,\lambda_{J})$ from a uniform grid by discretizing the simplex;

Randomly select $(\mu_{1},\ldots,\mu_{J})$ from a uniform grid on the hypercube;

Randomly select coefficients $(\alpha_{1},\alpha_{2})$, weights $(\beta_{1},\beta_{2})$, and biases $(\pi_{1},\pi_{2})$ from a uniform grid on the hypercube.

Given these parameters, the prior $P(Z)$ is defined as in (2) and the decoder $f$ is defined to be the following single-layer ReLU network

As a result of the simulation mechanism, the following important cases of misspecification naturally arise:

We allow $\lambda_{j}=0$, i.e. the model allows for $J=3$ components, but the true model only has two nontrivial components.

We allow $\alpha_{j}=0$ and $\beta_{j}=0$, i.e. the model allows for up to two neurons in the hidden layer, but the true model only has one nontrivial neuron.

$f$ is not forced to be injective or even weakly injective, i.e. assumptions (F2)-(F4) are not checked explicitly.

After generating a pair $(f,P(Z))$, the exact negative log-likelihood is approximated via numerical integration. An exhaustive grid search is performed over all parameters to identify the global minimizers. The computational cost of this step limited the complexity of the models that could be tested, hence the restriction to simple toy models in this experiment. In all runs, the ground truth was the unique global minimizer of the negative log-likelihood, as predicted by our theory. Since the problem is nonconvex, there often exist additional (non-global) local minima (see e.g. Figure 1), however, the global minimizer is always unique up to affine equivalence. That is, due to affine equivalence, in some cases there is more than one global minimizer, but in all such cases it is easy to check that the different minimizers are indeed affinely equivalent. Multiple minimizers also arise when certain parameters (e.g. $\lambda_{j}$ or $\alpha_{j}$) vanish, again, these are easily checked.

J.3.2 Simulated data

We consider 4 synthetic datasets described below: Pinwheel and three different copies of the “Random parallelograms” dataset

See Section 4 for results of the simulated experiments on the “pinwheels” dataset (see Johnson et al. 2016). In those experiments we use 5000 samples and set $m=n=2$. In that experiment we used the same neural network architecture as discussed below for “Random parallelograms”.

We simulate an artificial dataset “Random parallelograms” as follows: We generate 3 randomly oriented parallelograms in the plane. After that, an $n$-dimensional observed distribution is obtained by sampling points uniformly at random from these parallelograms and by adding Gaussian noise to every sampled point.

We fit VaDE to each (observed) dataset 5 times (see Figures 2, 5-7). Let $Z^{(1)},Z^{(2)},\ldots,Z^{(5)}$ be the learned latent spaces. For every pair $Z^{(i)},Z^{(j)}$ we evaluate the MCC and $\dist_{\Aff,L2}$ loss. We report means of the MCCs/losses and their standard deviations in Table 2.

For the VaDE training, we use a sequential neural network architecture with LeakyReLU activations for the encoder, with four fully connected layers of the following dimentions: $n\rightarrow 64\rightarrow 512\rightarrow 64\rightarrow m$. For the decoder, we use a sequential neural network architecture with LeakyReLU activations, with four fully connected layers of the following dimentions: $m\rightarrow 64\rightarrow 512\rightarrow 512\rightarrow n$. We pretrain the autoencoder for 15 epochs and then run VaDE training for 20 epochs.

In all experiments with simulated data we set $m=2$. We set the number of observed samples to be $5000$.

J.3.3 Real data

We run MFCVAE (Falck et al. 2021) on the MNIST dataset 10 times with different initializations. For all the 45 pairs of runs, we compute the strong MCC (before alignment) and weak MCC (after alignment with CCA of dimension $5$). For these experiments, we omit the $\dist_{\Aff,L2}$ metric since it’s computationally infeasible with a large number of components. The mean and standard deviation of the MCCs are reported in Table 3. As a baseline, we also report the same metrics for 10 runs of iVAE (Khemakhem et al. 2020a) on identical architecture and latent dimension, but recall that iVAE has additional access to the true digit labels $U$.

As recommended in Falck et al. 2021, we set the dimension of the latent space to be $5$ and number of components to be $25$. No hyperparameter tuning was done. The architectures we use are as follows:

Arch1: The encoder is a sequential neural network architecture with fully connected layers of dimensions $n\rightarrow 500\rightarrow 1000\rightarrow m$. The decoder is also a sequential neural network architecture with fully connected layers of dimensions $m\rightarrow 500\rightarrow 500\rightarrow n$.

Arch2: The encoder is a sequential neural network architecture that is fully connected with dimensions $n\rightarrow 256\rightarrow 512\rightarrow 512\rightarrow m$. The decoder is similarly a sequential neural network architecture with fully connected layers of dimensions $m\rightarrow 512\rightarrow 256\rightarrow n$.

Arch3: The encoder is a sequential neural network architecture that is fully connected with dimensions $n\rightarrow 128\rightarrow 256\rightarrow 128\rightarrow 128\rightarrow m$. The decoder is again a sequential neural network architecture with fully connected layers of dimensions $m\rightarrow 128\rightarrow 128\rightarrow n$.

The work Willetts and Paige 2021 ran extensive experiments comparing VaDE and iVAE. We augment these experiments by using MFCVAE instead of VaDE. We observe that even without access to $U$, MFCVAE has competitive performance (stability) in recovering the latent space as compared to iVAE which has full access to $U$. This offers strong evidence for stability of training, as predicted by our theory.

For purely illustrative purposes, we also show the output of MFCVAE on MNIST. In Figure 8, we show samples synthetically generated from each learnt cluster. In Figure 9, we visualize the true datapoint $x$ and the corresponding reconstructed $\widehat{x}$ for four different datapoints in each cluster. For similar experiments on other datasets and other architectures, we refer the reader to Falck et al. 2021.