# Understanding Latent Correlation-Based Multiview Learning and Self-
Supervision: An Identifiability Perspective

Qi Lyu
School of EECS
Oregon State Univ.
&Xiao Fu
School of EECS
Oregon State Univ.
&Weiran Wang
Google Inc.
Mountain View
&Songtao Lu
IBM Research
Yorktown Heights
Contact information: Q. Lyu and X. Fu<EMAIL_ADDRESS>W.
Wang<EMAIL_ADDRESS>S. Lu<EMAIL_ADDRESS>
###### Abstract

Multiple views of data, both naturally acquired (e.g., image and audio) and
artificially produced (e.g., via adding different noise to data samples), have
proven useful in enhancing representation learning. Natural views are often
handled by multiview analysis tools, e.g., (deep) canonical correlation
analysis [(D)CCA], while the artificial ones are frequently used in self-
supervised learning (SSL) paradigms, e.g., BYOL and Barlow Twins. Both types
of approaches often involve learning neural feature extractors such that the
embeddings of data exhibit high cross-view correlations. Although intuitive,
the effectiveness of correlation-based neural embedding is mostly empirically
validated. This work aims to understand latent correlation maximization-based
deep multiview learning from a latent component identification viewpoint. An
intuitive generative model of multiview data is adopted, where the views are
different nonlinear mixtures of shared and private components. Since the
shared components are view/distortion-invariant, representing the data using
such components is believed to reveal the identity of the samples effectively
and robustly. Under this model, latent correlation maximization is shown to
guarantee the extraction of the shared components across views (up to certain
ambiguities). In addition, it is further shown that the private information in
each view can be provably disentangled from the shared using proper
regularization design. A finite sample analysis, which has been rare in
nonlinear mixture identifiability study, is also presented. The theoretical
results and newly designed regularization are tested on a series of tasks.

##  1 Introduction

One pillar of unsupervised representation learning is multiview learning.
Extracting shared information from multiple “views” (e.g., image and audio) of
data entities has been considered a major means to fend against noise and data
scarcity. A key computational tool for multiview learning is canonical
correlation analysis (CCA) (Hotelling, 1936). The classic CCA seeks linear
transformation matrices such that transformed views are maximally correlated.
A number of works studied nonlinear extensions of CCA; see kernel CCA in (Lai
& Fyfe, 2000) and deep learning-based CCA (DCCA) in (Andrew et al., 2013; Wang
et al., 2015). DCCA and its variants were shown to largely outperform the
classical linear CCA in many tasks.

In recent years, a series of self-supervised learning (SSL) paradigms were
proposed. These SSL approaches exhibit a lot of similarities with DCCA
approaches, except that the “views” are noisy data “augmenented” from the
original clean data. To be specific, different views are generated by
distorting data—e.g., using rotating, cropping, and/or adding noise to data
samples (Dosovitskiy et al., 2015; Gidaris et al., 2018; Chen et al., 2020;
Grill et al., 2020). Then, neural encoders are employed to map these
artificial views to embeddings that are highly correlated across views. This
genre—which will be referred to as artificial multiview SSL (AM-SSL)—includes
some empirically successful frameworks, e.g., BYOL (Grill et al., 2020) and
Barlow Twins (Zbontar et al., 2021).

Notably, many DCCA and AM-SSL approaches involve (explicitly or implicitly)
searching for highly correlated representations from multiple views, using
neural feature extractors (encoders). The empirical success of DCCA and AM-SSL
bears an important research question: How to understand the role of cross-view
correlation in deep multiview learning? Furthermore, how to use such
understanding to design theory-backed learning criteria to serve various
purposes?

Intuitively, it makes sense that many DCCA and AM-SSL paradigms involve latent
correlation maximization in their loss functions, as such loss functions lead
to similar/identical representations from different views—which identifies
view-invariant essential information that is often identity-revealing.
However, beyond intuition, theoretical support of latent correlation-based
deep multiview learning had been less studied, until recent works started
exploring this direction in both nonlinear CCA and AM-SSL (see, e.g., (Lyu &
Fu, 2020; von Kügelgen et al., 2021; Zimmermann et al., 2021; Tian et al.,
2021; Saunshi et al., 2019; Tosh et al., 2021)), but more insights and
theoretical underpinnings remain to be discovered under more realistic and
challenging settings. In this work, we offer an understanding to the role of
latent correlation maximization that is seen in a number of DCCA and AM-SSL
systems from a nonlinear mixture learning viewpoint—and use such understanding
to assist various learning tasks, e.g., clustering, cross-view translation,
and cross-sample generation. Our detailed contributions are:

(i) Understanding Latent Correlation Maximization - Shared Component
Identification. We start with a concept that has been advocated in many
multiview learning works. In particular, the views are nonlinear mixtures of
shared and private latent components; see, e.g., (Huang et al., 2018; Lee et
al., 2018; Wang et al., 2016). The shared components are distortion/view
invariant and identity-revealing. The private components and view-specific
nonlinear mixing processes determine the different appearances of the views.
By assuming independence between the shared and private components and
invertibility of the data generating process, we show that maximizing the
correlation of latent representations extracted from different views leads to
identification of the ground-truth shared components up to invertible
transformations.

(ii) Imposing Additional Constraints - Private Component Identification. Using
the understanding to latent correlation maximization-type loss functions in
DCCA and AM-SSL, we take a step further. We show that with carefully imposed
constraints, the private components in the views can also be identified, under
reasonable assumptions. Learning private components can facilitate tasks such
as cross-view and cross-sample data generation (Huang et al., 2018; Lee et
al., 2018).

(iii) Finite-Sample Analysis. Most existing unsupervised nonlinear mixture
identification works, e.g., those from the nonlinear independent component
analysis (ICA) literature (Hyvarinen & Morioka, 2016; 2017; Hyvarinen et al.,
2019; Khemakhem et al., 2020; Locatello et al., 2020; Gresele et al., 2020),
are based on infinite data. This is perhaps because finite sample analysis for
unsupervised learning is generally much more challenging relative to
supervised cases—and there is no existing “universal” analytical tools. In
this work, we provide sample complexity analysis for the proposed unsupervised
multiview learning criterion. We come up with a success metric for
characterizing the performance of latent component extraction, and integrate
generalization analysis and numerical differentiation to quantify this metric.
To our best knowledge, this is the first finite-sample analysis of nonlinear
mixture model-based multiview unsupervised learning.

(iv) Practical Implementation. Based on the theoretical understanding, we
propose a latent correlation-maximization based multiview learning criterion
for extracting both the shared components and private components. To realize
the criterion, a notable innovation is a minimax neural regularizer that
serves for extracting the private components. The regularizer shares the same
purpose of some known independence promoters (e.g., Hilbert-Schmidt
Independence Criterion (HSIC) (Gretton et al., 2007)) but is arguably easier
to implement using stochastic gradient algorithms.

Notation. The notations used in this work are summarized in the supplementary
material.

##  2 Background: Latent Correlation in DCCA and AM-SSL

In this section, we briefly review some deep multiview learning paradigms that
use latent correlation maximization and its close relatives.

###  2.1 Latent Correlation Maximization in DCCA

DCCA methods aim at extracting common information from multiple views of data
samples. Such information is expected to be informative and essential in
representing the data.

$\bullet$ DCCA. The objective of DCCA can be summarized as follows (Andrew et
al., 2013):

$\displaystyle\operatorname*{\textrm{maximize}}_{\bm{f}^{(1)},\bm{f}^{(2)}}~{}{\rm
Tr}\left(\mathbb{E}\left[\bm{f}^{(1)}\left(\bm{x}^{(1)}\right)\bm{f}^{(2)}\left(\bm{x}^{(2)}\right)^{\top}\right]\right),\quad\text{s.t.}~{}\mathbb{E}\left[\bm{f}^{(q)}\left(\bm{x}^{(q)}\right)\bm{f}^{(q)}\left(\bm{x}^{(q)}\right)^{\top}\right]=\bm{I},$
(1)

where $\bm{x}^{(q)}\in\mathbb{R}^{M_{q}}\sim{\cal D}_{q}$ is a data sample
from view $q$ for $q=1,2$, ${\cal D}_{q}$ is the underlying distribution of
the $q$th view, $\bm{f}^{(1)}:\mathbb{R}^{M_{1}}\rightarrow\mathbb{R}^{D}$ and
$\bm{f}^{(2)}:\mathbb{R}^{M_{2}}\rightarrow\mathbb{R}^{D}$ are two neural
networks. CCA was found particularly useful in fending against unknown and
strong view-specific (private) interference (see theoretical supports in (Bach
& Jordan, 2005; Ibrahim & Sidiropoulos, 2020)). Such properties were also
observed in DCCA research (Wang et al., 2015), while theoretical analysis is
mostly elusive.

An equivalent representation of (1) is as follows

$\displaystyle\operatorname*{\textrm{minimize}}_{\bm{f}^{(1)},\bm{f}^{(2)}}~{}\mathbb{E}\left[\left\|\bm{f}^{(1)}(\bm{x}^{(1)})-\bm{f}^{(2)}(\bm{x}^{(2)})\right\|_{2}^{2}\right],\quad\text{s.t.}~{}\mathbb{E}\left[\bm{f}^{(q)}\left(\bm{x}^{(q)}\right)\bm{f}^{(q)}\left(\bm{x}^{(q)}\right)^{\top}\right]=\bm{I},$
(2)

which is expressed from latent component matching perspective. Both the
correlation maximization form in (1) and the component matching form in (2)
are widely used in the literature. As we will see in our proofs, although the
former is popular in the literature (Andrew et al., 2013; Wang et al., 2015;
Chen et al., 2020), the latter is handier for theoretical analysis.

$\bullet$ Slack Variable-Based DCCA. In (Benton et al., 2017) and (Lyu & Fu,
2020), a deep multiview learning criterion is used:

$\operatorname*{\textrm{minimize}}_{\bm{f}^{(q)}}\sum_{q=1}^{2}\mathbb{E}\left[\left\|\bm{f}^{(q)}(\bm{x}^{(q)})-\bm{g}\right\|^{2}\right],~{}{\rm
s.t.}~{}\mathbb{E}[|g_{i}|^{2}]=1,~{}\mathbb{E}[g_{i}g_{j}]=0.$ (3)

The slack variable $\bm{g}$ represents the common latent embedding learned
from the two views. Conceptually, this is also latent correlation maximization
(or latent component matching). To see this, assume that there exists
$\bm{f}^{(q)}(\bm{x}^{(q)})=\bm{g}$ for all $\bm{x}^{(q)}$. The criterion
amounts to learning
$[\bm{f}^{(1)}(\bm{x}^{(1)})]_{k}=[\bm{f}^{(2)}(\bm{x}^{(2)})]_{k}$—which has
the maximally attainable correlation.

###  2.2 Latent Correlation Maximization/Component Matching in AM-SSL

Similar to DCCA, the goal of AM-SSL is also to find identity-revealing
embeddings of data samples without using labels. The idea is often realized
via intentionally distorting the data to create multiple artificial views.
Then, the encoders are require to produce highly correlated (or closely
matched) embeddings from such views. In AM-SSL, the views $\bm{x}^{(1)}$ and
$\bm{x}^{(2)}$ are different augmentations (e.g., by adding noise, cropping,
and rotation) of the sample $\bm{x}$.

$\bullet$ Barlow Twins. The most recent development, namely, the Barlow Twins
network (Zbontar et al., 2021) is appealing since it entails a succinct
implementation. Specifically, the Barlow Twins network aims to learn a single
encoder $\bm{f}:\mathbb{R}^{M}\rightarrow\mathbb{R}^{D}$ for two distorted
views. The cost function is as follows:

$\operatorname*{\textrm{minimize}}_{\bm{f}}~{}\sum_{i=1}^{D}~{}(1-C_{ii})^{2}+\lambda\sum_{i=1}^{D}\sum_{j\neq
i}^{D}C_{ij}^{2},~{}~{}\text{where
}C_{ij}=\frac{\mathbb{E}\left[[\bm{f}(\bm{x}^{(1)})]_{i}[\bm{f}(\bm{x}^{(2)})]_{j}\right]}{\sqrt{\mathbb{E}[[\bm{f}(\bm{x}^{(1)})]_{i}^{2}]}\sqrt{\mathbb{E}[[\bm{f}(\bm{x}^{(2)})]_{j}^{2}]}}.$

When the learned embeddings are constrained to have zero mean, i.e.,
$\mathbb{E}\left[\bm{f}(\bm{x}^{(q)})\right]=\bm{0}$, $C_{ij}$ is the cross-
correlation between $\bm{f}(\bm{x}^{(1)})$ and $\bm{f}(\bm{x}^{(2)})$. Note
that the normalized representation of cross-correlation in $C_{ij}$ is
equivalent to the objective in (1) with the orthogonality constraints.

$\bullet$ BYOL. The BYOL method (Grill et al., 2020) uses a cross-view
matching criterion that can be distilled as follows:

$\operatorname*{\textrm{minimize}}_{\bm{f}^{(1)},\bm{f}^{(2)}}~{}\mathbb{E}\left[\left\|\overline{\bm{f}}^{(1)}(\bm{x}^{(1)})-\overline{\bm{f}}^{(2)}(\bm{x}^{(2)})\right\|_{2}^{2}\right]$
(4)

where $\overline{\bm{f}}^{(q)}(\cdot)$ means that the output of the network is
normalized. In BYOL, the networks are constructed in a special way (e.g., part
of $\bm{f}^{(2)}$’s weights are moving averages of the correspond part of
$\bm{f}^{(1)}$’s weights). Nonetheless, the cross-view matching perspective is
still very similar to that in latent component matching in (2).

$\bullet$ SimSiam. The loss function of SimSiam (Chen & He, 2021) has a
similar structure as that of BYOL, but with a Siamese network, which,
essentially, is also latent component matching.

##  3 Understanding Latent Correlation Maximization

In this section, we offer understandings to latent correlation maximization
(and latent component matching) from an unsupervised nonlinear multiview
mixture identification viewpoint. We will also show that such understanding
can help improve multiview learning criteria to serve different purposes,
e.g., cross-view and cross-sample data generation.

###  3.1 Multiview as Nonlinear Mixtures of Private and Shared Components

We consider the following multiview generative model:

$\displaystyle\bm{x}_{\ell}^{(1)}=\bm{g}^{(1)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(1)}\end{bmatrix}\right),\
\bm{x}_{\ell}^{(2)}=\bm{g}^{(2)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(2)}\end{bmatrix}\right),$ (5)

where $\bm{x}_{\ell}^{(q)}\in\mathbb{R}^{M_{q}}$ is the $\ell$th sample of the
$q$th view for $q=1,2$, $\bm{z}_{\ell}\in\mathbb{R}^{D}$ is the shared
component across views, and $\bm{c}_{\ell}^{(q)}\in\mathbb{R}^{D_{q}}$
represents the private information of the $q$th view—which are the $\ell$th
samples of continuous random variables denoted by $\bm{z}\in\mathbb{R}^{D}$,
$\bm{c}^{(q)}\in\mathbb{R}^{D_{q}}$, respectively. In addition,
$\bm{g}^{(q)}(\cdot):\mathbb{R}^{D+D_{q}}\rightarrow\mathbb{R}^{M_{q}}$ is an
invertible and smooth nonlinear transformation, which is unknown. Additional
notes on (5) and the shared-private component-based modeling idea in the
literature can be found in the supplementary materials (Appendix H). We will
use the following assumption:

######  Assumption 1 (Group Independence)

Under (5), the samples $\bm{z}_{\ell}$ and $\bm{c}_{\ell}^{(q)}$ are
realizations of continuous latent random variables $\bm{z}$, $\bm{c}^{(q)}$
for $q=1,2$, whose joint distributions satisfy the following:

$\displaystyle\bm{z}\sim p(\bm{z}),\ \bm{c}^{(q)}\sim p(\bm{c}^{(q)}),\
\bm{z}\in\mathcal{Z},\ \bm{c}^{(q)}\in\mathcal{C}_{q},\quad
p(\bm{z},\bm{c}^{(1)},\bm{c}^{(2)})=p(\bm{z})p(\bm{c}^{(1)})p(\bm{c}^{(2)}),$
(6)

where $\mathcal{Z}\subseteq\mathbb{R}^{D}$,
$\mathcal{C}_{q}\subseteq\mathbb{R}^{D_{q}}$ are the continuous supports of
$p(\bm{z})$ and $p(\bm{c}^{(q)})$, respectively.

Assumption 1 is considered reasonable under both AM-SSL and DCCA settings. For
AM-SSL, the private information can be understood as random data augmentation
noise-induced components, and thus it makes sense to assume that such noise is
independent with the shared information (which corresponds to the identity-
revealing components of the data sample). In DCCA problems, the private style
information can change drastically from view to view (e.g., audio, text,
video) without changing the shared content information (e.g., identity of the
entity)—which also shows independence between the two parts. In our analysis,
we will assume that $D$ and $D_{q}$ are known to facilitate exposition. In
practice, these parameters are often selected using a validation set.

Learning Goals. Our interest lies in extracting $\bm{z}_{\ell}$ and
$\bm{c}_{\ell}^{(q)}$ (up to certain ambiguities) from the views in an
unsupervised manner. In particular, we hope to answer under what conditions
these latent components can be identified—and to what extent. As mentioned,
$\bm{z}_{\ell}$ is view/distortion-invariant and thus should be identity-
revealing. The ability of extracting it may explain DCCA and AM-SSL’s
effectiveness. In addition, the identification of $\bm{c}_{\ell}^{(q)}$ and
the mixing processes may help generate data in different views.

###  3.2 A Latent Correlation-Based Learning Criterion

Given observations from both views
$\\{\bm{x}_{\ell}^{(1)},\bm{x}_{\ell}^{(2)}\\}_{\ell=1}^{N}$ generated from
(5), we aim to understand how latent correlation maximization (or latent
component matching) helps with our learning goals. To this end, we consider
the following problem criterion:

$\displaystyle\operatorname*{\textrm{maximize}}_{\bm{f}^{(1)},\bm{f}^{(2)}}$
$\displaystyle~{}{\rm Tr}\left(\frac{1}{N}\sum_{\ell=1}^{N}\bm{f}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}_{\ell}\right)\bm{f}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}_{\ell}\right)^{\\!\top\\!}\right)$ (7a) subject to
$\displaystyle~{}\bm{f}^{(q)}\text{~{}for $q=1,2$ are invertible},$ (7b)
$\displaystyle~{}\frac{1}{N}\sum_{\ell=1}^{N}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right)\bm{f}^{(q)}_{\rm
S}\left(\bm{x}^{(q)}_{\ell}\right)^{\top}=\bm{I},~{}\frac{1}{N}\sum_{\ell=1}^{N}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right)=\bm{0},~{}q=1,2,$ (7c)
$\displaystyle~{}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}_{\ell}^{(q)}\right)\perp\\!\\!\\!\perp\bm{f}_{\rm
P}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right),~{}q=1,2,$ (7d)

where $\bm{f}^{(q)}:\mathbb{R}^{M_{q}}\rightarrow\mathbb{R}^{D+D_{q}}$ for
$q=1,2$ are the feature extractors of view $q$. We use the notations

$\bm{f}^{(q)}_{\rm
S}\left(\bm{x}^{(q)}_{\ell}\right)=\left[\bm{f}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right)\right]_{1:D},\
\bm{f}^{(q)}_{\rm
P}\left(\bm{x}^{(q)}_{\ell}\right)=\left[\bm{f}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right)\right]_{D+1:D+D_{q}},\
q=1,2,$

to denote the encoder-extracted shared and private components for each view,
respectively. Note that designating the first $D$ dimensions of the encoder
outputs to represent the shared information is without loss of generality,
since the permutation ambiguity is intrinsic.

The correlation maximization objective is reminiscent of the criteria of
learning paradigms such as DCCA and Barlow Twins. In addition, under the
constraints in (7), the objective function is also equivalent to shared
component matching that is similar to those used by BYOL and SimSiam, i.e.,

$\max_{\bm{f}^{(q)}}~{}{\rm Tr}\left(\frac{1}{N}\sum_{\ell=1}^{N}\bm{f}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}_{\ell}\right)\bm{f}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}_{\ell}\right)^{\\!\top\\!}\right)\Longleftrightarrow\min_{\bm{f}^{(q)}}~{}\frac{1}{N}\sum_{\ell=1}^{N}\left\|\bm{f}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}_{\ell}\right)-\bm{f}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}_{\ell}\right)\right\|_{2}^{2}.$

To explain the criterion, note that we have a couple of goals that we hope to
achieve with $\bm{f}^{(q)}_{\rm S}$ and $\bm{f}^{(q)}_{\rm P}$. First, the
objective function aims to maximize the latent correlation of the learned
shared components, i.e., $\bm{f}^{(q)}_{\rm S}$. This is similar to those in
DCCA and AM-SSL, and is based on the belief that the shared information should
be identical across views. Second, in (7d), we ask $\bm{f}^{(q)}_{\rm S}$ and
$\bm{f}^{(q)}_{\rm P}$ to be statistically independent for $q=1,2$. This
promotes the disentanglement of the shared and private parts of each encoder,
following in Assumption 1. Third, the invertibility constraint in (7b) is to
ensure that the latent and the ambient data can be constructed from each
other—which is often important in unsupervised learning, for avoiding trivial
solutions; see, e.g., (Hyvarinen et al., 2019; von Kügelgen et al., 2021). The
orthogonality and zero-mean constraints in (7c) are used to make the
correlation metric meaningful. In particular, if the learned components are
not zero-mean, the learned embeddings may not capture “co-variations” but
dominated by some constant terms.

###  3.3 Theoretical Understanding

We have the following theorem in terms of learning the shared components:

###### Theorem 1

(Shared Component Extraction) Under the generative model in (5) and Assumption
1, consider the population form in (7) (i.e., $N=\infty$). Assume that the
considered constraints hold over all $\bm{x}^{(q)}\in{\cal X}_{q}$ for
$q=1,2$, where ${\cal
X}_{q}=\\{\bm{x}^{(q)}|\bm{x}^{(q)}=\bm{g}^{(q)}([\bm{z}^{\\!\top\\!},(\bm{c}^{(q)})^{\\!\top\\!}]^{\\!\top\\!}),~{}\forall\bm{z}\in{\cal
Z},\forall\bm{c}^{(q)}\in{\cal C}_{q}\\}$. Denote $\widehat{\bm{f}}^{(q)}$ as
any solution of (7). Also assume that the first-order derivative of
$\widehat{\bm{f}}^{(q)}\circ\bm{g}^{(q)}$ exists. Then, we have
$\widehat{\bm{z}}=\widehat{\bm{f}}^{(q)}_{\rm
S}\left(\bm{x}^{(q)}\right)=\bm{\gamma}({\bm{z}})$ no matter if (7d) is
enforced or not, where
$\bm{\gamma}(\cdot):\mathbb{R}^{D}\rightarrow\mathbb{R}^{D}$ is an unknown
invertible function.

A remark is that $\widehat{\bm{z}}=\bm{\gamma}(\bm{z})$ has all the
information of $\bm{z}$ due to the invertibility of $\bm{\gamma}(\cdot)$.
Theorem 1 clearly indicates that latent correlation maximization/latent
component matching can identify the view/distortion-invariant information
contained in multiple views under unknown nonlinear distortions. This result
may explain the reason why many DCCA and AM-SSL schemes use latent correlation
maximization/latent component matching as part of their objectives. Theorem 1
also indicates that if one only aims to extract $\bm{z}$, the constraint in
(7d) is not needed. In the next theorem, we show that our designed constraint
in (7d) can help disentangle the shared and private components:

###### Theorem 2

(Private Component Extraction) Under the same conditions as in Theorem 1, also
assume that (7d) is enforced. Then, we further have
$\widehat{\bm{c}}^{(q)}=\widehat{\bm{f}}^{(q)}_{\rm
P}\left(\bm{x}^{(q)}\right)=\bm{\delta}^{(q)}\left({\bm{c}^{(q)}}\right)$,
where
$\bm{\delta}^{(q)}(\cdot):\mathbb{R}^{D_{q}}\rightarrow\mathbb{R}^{D_{q}}$ is
an unknown invertible function.

Note that separating $\bm{z}$ and $\bm{c}^{(q)}$ may be used for other tasks
such as cross-view translation (Huang et al., 2018; Lee et al., 2018) and
content/style disentanglement.

The above theorems are based on the so-called population case (with $N=\infty$
and the ${\cal X}_{q}$ observed). This is similar to the vast majority of
provable nonlinear ICA/factor disentanglement literature; see (Hyvarinen &
Morioka, 2016; Hyvarinen et al., 2019; Locatello et al., 2020; Khemakhem et
al., 2020). It is of interest to study the finite sample case. In addition,
most of these works assumed that the learning function $\bm{f}^{(q)}$ is a
universal function approximator. In practice, considering
$\bm{f}^{(q)}\in{\cal F}$, where ${\cal F}$ is a certain restricted function
class that may have mismatches with $\bm{g}^{(q)}$’s function class, is
meaningful. To proceed, we assume $D_{1}=D_{2}$ and $M=M_{1}=M_{2}$ for
notation simplicity and:

###### Assumption 2

Assume the following conditions hold:

(a) We have $\bm{g}^{(q)}\in\mathcal{G}$ and learn $\bm{f}^{(q)}$ from
$\mathcal{F}$, where the function classes ${\cal F}$ and ${\cal G}$ are third-
order differentiable and bounded.

(b) The Rademacher complexity (Bartlett & Mendelson, 2002) of
$\mathcal{F}^{\prime}=\\{\bm{f}_{d}:\mathbb{R}^{M}\rightarrow\mathbb{R}|\bm{f}_{d}(\bm{x})=[\bm{f}(\bm{x})]_{d},\bm{f}\in{\cal
F}\\}$ is bounded by $\mathfrak{R}_{N}$ given $N$ samples.

(c) Define
$\mathcal{G}^{-1}=\left\\{\bm{u}:\mathbb{R}^{M}\rightarrow\mathbb{R}^{D+D_{1}}|\bm{u}_{\rm
S}(\bm{x})=\bm{\gamma}(\bm{z}),\bm{u}_{\rm
S}(\bm{x})=[\bm{u}(\bm{x})]_{1:D}\right\\}$ $\forall\bm{x}\in{\cal X}_{q}$ and
any invertible $\bm{\gamma}(\cdot)$. There exists $\bm{f}\in{\cal F}$ such
that $\sup_{\bm{x}\in{\cal X}_{q}}~{}\left\|\bm{f}_{\rm S}(\bm{x})-\bm{u}_{\rm
S}(\bm{x})\right\|_{2}\leq\nu$.

(d) Any third-order partial derivative of
$[\bm{h}^{(q)}(\bm{x})]_{d}=[\bm{f}^{(q)}\circ\bm{g}^{(q)}(\bm{x})]_{d}$
resides in $[-C_{d},C_{d}]$ for all $\bm{x}\in{\cal X}_{q}$. In addition,
$[\bm{c}^{(q)}]_{j}\in[-C_{p},C_{p}]$ with $0<C_{p}<\infty$ for $j\in[D_{q}]$.

Assumption 2 specifies some conditions of the function class ${\cal F}$ where
the learning functions are chosen from. Specifically, (a) and (d) mean that
the learning function is sufficiently smooth (i.e., with bounded third-order
derivatives); (b) means that the learning function is not overly complex
(i.e., with a bounded Rademacher complexity); and (c) means that the learning
function should be expressive enough to approximate the inverse of the
generative function.

###### Theorem 3

(Sample Complexity) Under the generative model in (5), Assumption 1 and the
suite of conditions in Assumption 2, assume that
$(\bm{x}_{\ell}^{(1)},\bm{x}^{(2)}_{\ell})$ for $\ell=1,\ldots,N$ are i.i.d.
samples of $(\bm{x}^{(1)},\bm{x}^{(2)})$. Denote $\widehat{\bm{f}}^{(q)}$ as
any solution of (7) with the invertibility constraint satisfied. Then, we have
the following holds with probability of at least $1-\delta$:

$\displaystyle\mathbb{E}\left[\sum_{i=1}^{D}\sum_{j=1}^{D_{q}}\left(\nicefrac{{\partial\left[\widehat{\bm{f}}_{\rm
S}\left(\bm{x}^{(q)}\right)\right]_{i}}}{{\partial{c}_{j}^{(q)}}}\right)^{2}\right]=O\left(\left(D{\mathfrak{R}_{N}}+\sqrt{\nicefrac{{\log(1/\delta)}}{{N}}}+\nu^{2}\right)^{2/3}\right)$
(8)

for any $\bm{c}^{(q)}\in\mathcal{C}_{q}$ such that
$-C_{p}+\kappa_{j}\leq{c}_{j}^{(q)}\leq C_{p}-\kappa_{j}$ for all
$j\in[D_{q}]$ and all $i\in[D]$, where
$\kappa_{j}=\Omega((\nicefrac{{3}}{{C_{d}}})^{1/3}(4C_{f}(2D{\mathfrak{R}_{N}}+C_{f}\sqrt{\nicefrac{{\log(1/\delta)}}{{2N}}})+4\nu^{2})^{1/6})$.

If the metric on the left hand side of (8) is zero, then
$\widehat{\bm{f}}_{\rm S}\left(\bm{x}^{(q)}\right)$ is disentangled from
$\bm{c}^{(q)}$. The theorem indicates that with $N$ samples, the metric is
bounded by $O(N^{-\nicefrac{{1}}{{3}}})$. In addition, $\mathfrak{R}_{N}$
decreases when $N$ increases; e.g., a fully connected neural network with
bounded weights satisfies $\mathfrak{R}_{N}=O(N^{-\nicefrac{{1}}{{2}}})$
(Shalev-Shwartz & Ben-David, 2014). When $\mathfrak{R}_{N}$ increases (e.g.,
by using a more complex neural network), the function mismatch $\nu$ often
decreases (since ${\cal F}$ can be more expressive with a higher
$\mathfrak{R}_{N}$). In other words, Theorem 3 indicates a tradeoff between
the expressiveness of the function class $\cal{F}$ and the sample complexity.
If $\cal{F}$ comprises neural networks, the expressiveness is increased (or
equivalently, the modeling error is reduced) by increasing the width or depth
of networks. But this in turn increases $\mathfrak{R}_{N}$ and requires more
samples to reduce (8). This makes sense—one hopes to use a sufficiently
expressive learning function, but does not hope to use an excessively
expressive one, which is similar to the case in supervised learning.

##  4 Implementation

Enforcing Group Statistical Independence. A notable challenge is the
statistical independence constraint in (7d), whose enforcement is often an
art. Early methods such as (Taleb & Jutten, 1999; Hyvärinen & Oja, 2000) may
be costly. The HSIC method in (Gretton et al., 2007) which measures the
correlation of two variables in a kernel space can be used in our framework,
but kernels sometimes induce large memory overheads and are sensitive to
parameter (e.g., kernel width) selection.

In this work, we provide a simple alternative. Note that if two variables $X$
and $Y$ are statistically independent, then we have
$p(X,Y)=p(X)p(Y)\iff\mathbb{E}[\phi(X)\tau(Y)]=\mathbb{E}[\phi(X)]\mathbb{E}[\tau(Y)]$
for all measurable functions $\phi(\cdot):\mathbb{R}\rightarrow\mathbb{R}$ and
$\tau(\cdot):\mathbb{R}\rightarrow\mathbb{R}$ (Gretton et al., 2005). Hence,
to enforce group independence between variables $\widehat{\bm{z}}^{(q)}$ and
$\widehat{\bm{c}}^{(q)}$, we propose to exhaust the space of all measurable
functions $\bm{\phi}^{(q)}:\mathbb{R}^{D}\rightarrow\mathbb{R}$ and
$\bm{\tau}^{(q)}:\mathbb{R}^{D_{q}}\rightarrow\mathbb{R}$, such that

$\displaystyle\sup_{\bm{\phi}^{(q)},\bm{\tau}^{(q)}}\mathcal{R}^{(q)}=\sup_{\bm{\phi}^{(q)},\bm{\tau}^{(q)}}\nicefrac{{\left|\mathbb{Cov}\left[\bm{\phi}^{(q)}\left(\widehat{\bm{z}}^{(q)}\right),\bm{\tau}^{(q)}\left(\widehat{\bm{c}}^{(q)}\right)\right]\right|}}{{\left(\sqrt{\mathbb{V}[\bm{\phi}^{(q)}\left(\widehat{\bm{z}}^{(q)}\right)]}\sqrt{\mathbb{V}\left[\bm{\tau}^{(q)}\left(\widehat{\bm{c}}^{(q)}\right)\right]}\right)}}$
(9)

is minimized. It is not hard to show the following (see the proof in the
supplementary material):

###### Proposition 1

In (9), if $\sup_{\bm{\phi}^{(q)},\bm{\tau}^{(q)}}\mathcal{R}^{(q)}=0$ over
all measurable functions $\bm{\phi}^{(q)}$ and $\bm{\tau}^{(q)}$, then, any
$\left[\widehat{\bm{z}}^{(q)}\right]_{i}$ and
$\left[\widehat{\bm{c}}^{(q)}\right]_{j}$ for $i\in[D]$ and $j\in[D_{q}]$ are
statistically independent.

In practice, we use two neural networks to represent $\bm{\phi}^{(q)}$ and
$\bm{\tau}^{(q)}$, respectively, which blends well with the neural encoders
for algorithm design.

Reformulation and Optimization. We use deep neural networks to serve as
$\bm{f}^{(q)}$. We introduce a slack variable $\bm{u}_{\ell}$ and change the
objective to minimizing
$\mathcal{L}_{\ell}=\sum_{q=1}^{2}\|\bm{u}_{\ell}-{\bm{f}}^{(q)}_{\rm
S}(\bm{x}^{(q)}_{\ell})\|_{2}^{2}$ like in (3). The slack variable can also
make orthogonality and zero-mean constraints easier to enforce. A
reconstruction loss
$\mathcal{V}_{\ell}=\sum_{q=1}^{2}\|\bm{x}^{(q)}_{\ell}-\bm{r}^{(q)}(\bm{f}^{(q)}(\bm{x}^{(q)}_{\ell}))\|_{2}^{2}$
is employed to promote invertibility of $\bm{f}^{(q)}$, where ${\bm{r}}^{(q)}$
is a reconstruction network. Let $\bm{\theta}$ collect the parameters of
$\bm{f}^{(q)}$ and ${\bm{r}}^{(q)}$, and $\bm{\eta}$ the parameters of
$\bm{\phi}^{(q)},\bm{\tau}^{(q)}$. The overall formulation is:

$\displaystyle\min_{\bm{U},\bm{\theta}}\max_{\bm{\eta}}~{}$
$\displaystyle{\cal L}+\beta{\cal
V}+\lambda\mathcal{R},\quad\text{s.t.}~{}\frac{1}{N}\sum_{\ell=1}^{N}\bm{u}_{\ell}\bm{u}_{\ell}^{\top}=\bm{I},\
\frac{1}{N}\sum_{\ell=1}^{N}\bm{u}_{\ell}=\bm{0},$ (10)

where ${\cal L}=\nicefrac{{1}}{{N}}\sum_{\ell=1}^{N}{\cal L}_{\ell}$, ${\cal
V}=\nicefrac{{1}}{{N}}\sum_{\ell=1}^{N}{\cal V}_{\ell}$,
$\bm{U}=[\bm{u}_{1},\cdots,\bm{u}_{N}]\in\mathbb{R}^{D\times N}$, ${\cal
R}=\sum_{q=1}^{2}{\cal R}^{(q)}$, and $\beta,\lambda\geq 0$. We design an
algorithm for handling (10) with scalable updates; see the supplementary
materials for detailed implementation and complexity analysis. We should
mention that using reconstruction to encourage invertibility is often seen in
multiview learning; see, e.g., (Wang et al., 2015). Nonetheless, this needs
not to be the only invertibility-encouraging method. Other realizations such
as flow-based (e.g., (Kingma & Dhariwal, 2018)) and entropy regularization-
based approaches (e.g., (von Kügelgen et al., 2021)) are also viable—see more
in Appendix I.

##  5 Related Work - Nonlinear ICA and Latent Disentanglement

Other than the DCCA and AM-SSL works, our design for private and shared
information separation also draws insights from two topics in unsupervised
representation learning, namely, nonlinear ICA (nICA) (Hyvarinen & Morioka,
2016; 2017; Hyvarinen et al., 2019; Khemakhem et al., 2020) and latent factor
disentanglement (Higgins et al., 2017; Kim & Mnih, 2018; Chen et al., 2018;
Zhao et al., 2019; Lopez et al., 2018), which are recently offered a unifying
perspective in (Khemakhem et al., 2020). The nICA works aim to separate
nonlinearly mixed latent components to an individual component level, which is
in general impossible unless additional information associated with each
sample (e.g., time frame labels (Hyvarinen & Morioka, 2016) and class labels
(Hyvarinen et al., 2019; Khemakhem et al., 2020)) is used. Multiple views are
less studied in the context of nICA, with the recent exception in (Locatello
et al., 2020) and (Gresele et al., 2020). Nonetheless, their models are
different from ours and the approaches cannot extract the private information
from views with different nonlinear models. The concurrent work in (von
Kügelgen et al., 2021) worked on content-style disentanglement under data
augmented SSL settings and considered a similar generative model where both
shared and private components are explicitly used. A key difference is that
their model uses an identical nonlinear generative function across the views
(i.e., $\bm{g}^{(1)}=\bm{g}^{(2)}$), while we consider two possibly different
$\bm{g}^{(q)}$’s. In addition, our learning criterion is able to extract the
private information, while the work in (von Kügelgen et al., 2021) did not
consider this aspect. None of the aforementioned works offered finite sample
analysis. Our independence promoter is reminiscent of (Gretton et al., 2005),
with the extension to handle group variables.

##  6 Experiments

Synthetic Data. We first use synthetic data for theory validation; see the
supplementary materials.

###  6.1 Validating Theorem 1 \- Shared Component Learning

In this subsection, we show that latent correlation maximization (or latent
component matching) leads to shared component extraction under the model in
(5)—which can be used to explain the effectiveness of a number of DCCA and AM-
SSL formulations. This is also the objective of our formulation (7) if the
constraint in (7d) is not enforced.

Multiview MNIST Data. For proof-of-concept, we adopt a multiview MNIST dataset
that was used in (Wang et al., 2015). There, the “augmented” view of MNIST
contains randomly rotated digits and the other with additive Gaussian white
noise (Wang et al., 2015); see Fig. 1. This is similar to the data
augmentation ideas in AM-SSL. Using this multiview data, we apply different
multiview learning paradigms that match the latent representations (or
maximize the correlations of learned representations) across views. The
dataset has 70,000 samples that are 28$\times$28 images of handwritten digits.
Note that without (7d), our method can be understood as a slight variant of
(3). To benchmark our method, we use a number of DCCA and AM-SSL approaches
mentioned in Sec. 2, namely, DCCA (Wang et al., 2015), Barlow Twins (Zbontar
et al., 2021) and BYOL (Grill et al., 2020). We set $D=10$, $D_{1}=20$ and
$D_{2}=50$ through a validation set. The detailed settings of our neural
networks can be found in the supplementary material.

Since we do not have ground-truth to evaluate the effectiveness of shared
information extraction, we follow the evaluation method in (Wang et al., 2015)
and apply $k$-means to all the embeddings
$\widehat{\bm{z}}^{(1)}_{\ell}=\bm{f}_{\rm S}^{(1)}(\bm{x}^{(1)}_{\ell})$ and
compute the clustering accuracy on the test set (see the visualization of
$\widehat{\bm{z}}^{(2)}_{\ell}$ in the supplementary materials). In Fig. 1, we
show the t-SNE (Van der Maaten & Hinton, 2008) visualizations of
$\widehat{\bm{z}}^{(1)}_{\ell}$’s on a test set of 10,000 samples together
with the clustering accuracy. All results are averaged over 5 random
initializations.

By Theorem 1, all the methods under test should output identity-revealing
representations of the data samples. The reason is that the two views share
the same identity information of a sample. Indeed, from Fig. 1, one can see
that all latent correlation-maximization-based DCCA and AM-SSL methods learn
informative representations that are sufficiently distinguishable. The “shape”
of the clusters are different, which can be explained by the existence of the
invertible function $\bm{\gamma}(\cdot)$. These results corroborate our
analysis in Theorem 1.

Figure 1: t-SNE of the results on multiview MNIST from (Wang et al., 2015).
Baselines: DCCA (Wang et al., 2015), Barlow Twins (Zbontar et al., 2021) and
BYOL (Grill et al., 2020).

CIFAR10 Data. We also observe similar results using the CIFAR10 data
(Krizhevsky et al., 2009). The results can be found in the supplementary
materials, due to page limitations.

Figure 2: Evaluation on Cars3D; rows in blue boxes are w/ $\mathcal{R}$; rows
in green boxes are w/o $\mathcal{R}$.

###  6.2 Validating Theorem 2 \- Shared and Private Component Disentanglement

We use data generation examples to support our claim in Theorem 2—i.e., with
our designed regularizer ${\cal R}$ in (10), one can provably disentangle the
shared and private latent components.

Cars3D Data for Cross-sample Data Generation. We use the Cars3D dataset (Reed
et al., 2015) that contains different car CAD models. For each car image,
there are three defining aspects (namely, ‘type’, ‘elevation’ and ‘azimuth’).

We create two views as follows. We assume that given the car type that is
captured by shared variables $\bm{z}$ and the azimuths that are captured by
$\bm{c}^{(q)}$, the generation mappings $\bm{g}^{(1)}$ and $\bm{g}^{(2)}$
produce car images with low elevations and high elevations, respectively (so
they must be different mappings). Under our setting, each view has $N=8,784$
car images. We model $\bm{z}$ with $D=10$. For $\bm{c}^{(q)}$, we set
$D_{1}=D_{2}=2$. More details about our settings are in the supplementary
material.

We use the idea of cross-sample data generation to evaluate the effectiveness
of our method. To be precise, we evaluate the learned
$\widehat{\bm{f}}^{(q)}$’s by combining
$\widehat{\bm{z}}_{\ell}^{(q)}=\widehat{\bm{f}}^{(q)}_{\rm
S}(\bm{x}_{\ell}^{(q)})$ and
$\widehat{\bm{c}}_{j}^{(q)}=\widehat{\bm{f}}^{(q)}_{\rm P}(\bm{x}_{j}^{(q)})$
and generating
$\widehat{\bm{x}}_{\ell,j}^{(q)}=\widehat{\bm{r}}^{(q)}([(\widehat{\bm{z}}_{\ell}^{(q)})^{\\!\top\\!},(\bm{c}_{j}^{(q)})^{\\!\top\\!}]^{\\!\top\\!})$,
where $\widehat{\bm{r}}^{(q)}$ is the learned reconstruction network [cf Eq.
(10)]. Under our model, if the shared components and private components are
truly disentangled in the latent domain, this generated sample
$\widehat{\bm{x}}_{\ell,j}^{(q)}$ should exhibit the same ‘type’ and
‘elevation’ as those of $\bm{x}_{\ell}^{(q)}$ and the ‘azimuth’ of
$\bm{x}_{j}^{(q)}$.

Fig. 2 shows our experiment results. The proposed method’s outputs are as
expected. For example, on the left of Fig. 2, the $\bm{z}^{(1)}_{\ell}$ is
extracted from the red convertible, and the $\widehat{\bm{c}}_{j}^{(1)}$’s are
extracted from the top row. One can see that the generated
$\widehat{\bm{x}}_{\ell,j}^{(1)}$’s under the proposed method with ${\cal R}$
are all red convertibles with the same elevation, but using the azimuths of
the corresponding cars from the top row. Note that if ${\cal R}$ is not used,
then the learned $\widehat{\bm{c}}^{(q)}_{j}$ may still contain the ‘type’ or
‘elevation’ information; see the example highlighted with yellow background on
the right of Fig. 2. More results are in the supplementary material.

dSprites Data and MNIST Data for Cross-sample/Cross-view Data Generation. We
offer two extra sets of examples to validate our claim in Theorem 2. Please
see the supplementary materials.

##  7 Conclusion

In this work, we provided theoretical understandings to the role of latent
correlation maximization (latent component matching) that is often used in
DCCA and AM-SSL methods from an unsupervised nonlinear mixture learning
viewpoint. In particular, we modeled multiview data as nonlinear mixtures of
shared and private components, and showed that latent correlation maximization
ensures to extract the shared components—which are believed to be identity-
revealing. In addition, we showed that, with a carefully designed constraint
(which is approximated by a neural regularizer), one can further disentangle
the shared and private information, under reasonable conditions. We also
analyzed the sample complexity for extracting the shared information, which
has not been addressed in nonlinear component analysis works, to our best
knowledge. To realize our learning criterion, we proposed a slack variable-
assisted latent correlation maximization approach, with a novel minimax neural
regularizer for promoting group independence. We tested our method over
synthetic and real data. The results corroborated our design goals and
theoretical analyses.

Acknowledgement. This work is supported in part by the National Science
Foundation (NSF) under Project NSF ECCS-1808159, and in part by the Army
Research Office (ARO) under Project ARO W911NF-21-1-0227.

Ethics Statement. This paper focuses on theoretical analysis and provable
guarantees of learning criteria. It does not involve human subjects or other
ethics-related concerns.

Reproducibility Statement. The authors strive to make the research in this
work reproducible. The supplementary materials contain rich details of the
algorithm implementation and experiment settings. The source code of our
Python-implemented algorithm and two demos with real data are uploaded as
supplementary materials. The details of the proofs of our theoretical claims
are also included in the supplementary materials.

## References

  * Andrew et al. (2013) Galen Andrew, Raman Arora, Jeff Bilmes, and Karen Livescu.  Deep canonical correlation analysis.  In _International Conference on Machine Learning_ , pp. 1247–1255. PMLR, 2013.
  * Arora & Livescu (2013) Raman Arora and Karen Livescu.  Multi-view cca-based acoustic features for phonetic recognition across speakers and domains.  In _2013 IEEE International Conference on Acoustics, Speech and Signal Processing_ , pp. 7135–7139. IEEE, 2013.
  * Bach & Jordan (2005) Francis R Bach and Michael I Jordan.  A probabilistic interpretation of canonical correlation analysis.  2005\.
  * Bartlett & Mendelson (2002) Peter L Bartlett and Shahar Mendelson.  Rademacher and Gaussian complexities: Risk bounds and structural results.  _Journal of Machine Learning Research_ , 3(Nov):463–482, 2002.
  * Belghazi et al. (2018) Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm.  MINE: Mutual information neural estimation.  In _International Conference on Machine Learning_ , volume 80, pp. 531–540. PMLR, 10–15 Jul 2018.
  * Benton et al. (2017) Adrian Benton, Huda Khayrallah, Biman Gujral, Drew Reisinger, Shenmin Zhang, and Raman Arora.  Deep generalized canonical correlation analysis.  In _RepL4NLP at ACL_ , 2017.
  * Carroll (1968) J Douglas Carroll.  Generalization of canonical correlation analysis to three or more sets of variables.  In _Proceedings of the 76th annual convention of the American Psychological Association_ , volume 3, pp. 227–228, 1968.
  * Chen et al. (2018) Ricky TQ Chen, Xuechen Li, Roger B Grosse, and David K Duvenaud.  Isolating sources of disentanglement in variational autoencoders.  In _Advances in Neural Information Processing Systems_ , pp. 2610–2620, 2018.
  * Chen et al. (2020) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _International Conference on Machine Learning_ , pp. 1597–1607. PMLR, 2020.
  * Chen & He (2021) Xinlei Chen and Kaiming He.  Exploring simple Siamese representation learning.  In _Proceedings of Conference on Computer Vision and Pattern Recognition_ , pp. 15750–15758, 2021.
  * Cover (1999) Thomas M Cover.  _Elements of information theory_.  John Wiley & Sons, 1999.
  * Darmois (1951) G Darmois.  Analyse des liaisons de probabilité.  In _Proc. Int. Stat. Conferences 1947_ , pp. 231, 1951.
  * Davis et al. (2011) Richard A Davis, Keh-Shin Lii, and Dimitris N Politis.  Remarks on some nonparametric estimates of a density function.  In _Selected Works of Murray Rosenblatt_ , pp. 95–100. Springer, 2011.
  * Dhillon et al. (2012) Paramveer Dhillon, Jordan Rodu, Dean Foster, and Lyle Ungar.  Two step cca: A new spectral method for estimating vector models of words.  In _Proceedings of the 29th International Conference on Machine Learning (ICML-12)_ , pp. 1551–1558, New York, NY, USA, July 2012. Omnipress.
  * Dosovitskiy et al. (2015) Alexey Dosovitskiy, Philipp Fischer, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox.  Discriminative unsupervised feature learning with exemplar convolutional neural networks.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 38(9):1734–1747, 2015.
  * Duchi et al. (2011) John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12(Jul):2121–2159, 2011.
  * Fisher (1915) Ronald A Fisher.  Frequency distribution of the values of the correlation coefficient in samples from an indefinitely large population.  _Biometrika_ , 10(4):507–521, 1915.
  * Gidaris et al. (2018) Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  In _International Conference on Learning Representations_ , 2018.
  * Gong et al. (2014) Yunchao Gong, Qifa Ke, Michael Isard, and Svetlana Lazebnik.  A multi-view embedding space for modeling internet images, tags, and their semantics.  _International journal of computer vision_ , 106(2):210–233, 2014.
  * Gresele et al. (2020) Luigi Gresele, Paul K Rubenstein, Arash Mehrjou, Francesco Locatello, and Bernhard Schölkopf.  The incomplete Rosetta stone problem: Identifiability results for multi-view nonlinear ICA.  In _Proceedings of UAI 2020_ , pp. 217–227, 2020.
  * Gretton et al. (2005) Arthur Gretton, Alexander J Smola, Olivier Bousquet, Ralf Herbrich, Andrei Belitski, Mark Augath, Yusuke Murayama, Jon Pauls, Bernhard Schölkopf, and Nikos K Logothetis.  Kernel constrained covariance for dependence measurement.  In _International Conference on Artificial Intelligence and Statistics_ , volume 10, pp. 112–119. Citeseer, 2005.
  * Gretton et al. (2007) Arthur Gretton, Kenji Fukumizu, Choon Teo, Le Song, Bernhard Schölkopf, and Alex Smola.  A kernel statistical test of independence.  _Advances in Neural Information Processing Systems_ , 20, 2007.
  * Grill et al. (2020) Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Remi Munos, and Michal Valko.  Bootstrap your own latent - a new approach to self-supervised learning.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 21271–21284, 2020.
  * Gundersen et al. (2019) Gregory Gundersen, Bianca Dumitrascu, Jordan T Ash, and Barbara E Engelhardt.  End-to-end training of deep probabilistic cca on paired biomedical observations.  In _Uncertainty in artificial intelligence_ , 2019.
  * Gutmann & Hyvärinen (2010) Michael Gutmann and Aapo Hyvärinen.  Noise-contrastive estimation: A new estimation principle for unnormalized statistical models.  In _Proceedings of the thirteenth international conference on artificial intelligence and statistics_ , pp. 297–304. JMLR Workshop and Conference Proceedings, 2010.
  * Higgins et al. (2017) Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner.  Beta-VAE: Learning basic visual concepts with a constrained variational framework.  In _International Conference on Learning Representations_ , 2017.
  * Hotelling (1936) Harold Hotelling.  Relations between two sets of variates.  _Biometrika_ , 28(3/4):321–377, 1936.
  * Huang et al. (2018) Xun Huang, Ming-Yu Liu, Serge Belongie, and Jan Kautz.  Multimodal unsupervised image-to-image translation.  In _Proceedings of the European Conference on Computer Vision_ , pp. 172–189, 2018.
  * Hyvarinen & Morioka (2016) Aapo Hyvarinen and Hiroshi Morioka.  Unsupervised feature extraction by time-contrastive learning and nonlinear ica.  In _Advances in Neural Information Processing Systems_ , volume 29, 2016.
  * Hyvarinen & Morioka (2017) Aapo Hyvarinen and Hiroshi Morioka.  Nonlinear ICA of temporally dependent stationary sources.  In _International Conference on Artificial Intelligence and Statistics_ , volume 54, pp. 460–469, 20–22 Apr 2017.
  * Hyvärinen & Oja (2000) Aapo Hyvärinen and Erkki Oja.  Independent component analysis: Algorithms and applications.  _Neural Networks_ , 13(4-5):411–430, 2000.
  * Hyvarinen et al. (2019) Aapo Hyvarinen, Hiroaki Sasaki, and Richard Turner.  Nonlinear ICA using auxiliary variables and generalized contrastive learning.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 859–868, 2019.
  * Ibrahim & Sidiropoulos (2020) Mohamed Salah Ibrahim and Nicholas D Sidiropoulos.  Reliable detection of unknown cell-edge users via canonical correlation analysis.  _IEEE Trans. Wireless Commun._ , 19(6):4170–4182, 2020.
  * Kettenring (1971) Jon R Kettenring.  Canonical analysis of several sets of variables.  _Biometrika_ , 58(3):433–451, 1971\.
  * Khemakhem et al. (2020) Ilyes Khemakhem, Diederik Kingma, Ricardo Monti, and Aapo Hyvarinen.  Variational autoencoders and nonlinear ICA: A unifying framework.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 2207–2217. PMLR, 2020.
  * Kim & Mnih (2018) Hyunjik Kim and Andriy Mnih.  Disentangling by factorising.  In _International Conference on Machine Learning_ , volume 80, pp. 2649–2658. PMLR, 10–15 Jul 2018.
  * Kingma & Ba (2014) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kingma & Dhariwal (2018) Diederik P Kingma and Prafulla Dhariwal.  Glow: Generative flow with invertible 1x1 convolutions.  _arXiv preprint arXiv:1807.03039_ , 2018.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Lai & Fyfe (2000) Pei Ling Lai and Colin Fyfe.  Kernel and nonlinear canonical correlation analysis.  _International Journal of Neural Systems_ , 10(05):365–377, 2000.
  * Ledig et al. (2017) Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, et al.  Photo-realistic single image super-resolution using a generative adversarial network.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 4681–4690, 2017.
  * Lee et al. (2018) Hsin-Ying Lee, Hung-Yu Tseng, Jia-Bin Huang, Maneesh Singh, and Ming-Hsuan Yang.  Diverse image-to-image translation via disentangled representations.  In _Proceedings of the European Conference on Computer Vision_ , pp. 35–51, 2018.
  * Locatello et al. (2020) Francesco Locatello, Ben Poole, Gunnar Rätsch, Bernhard Schölkopf, Olivier Bachem, and Michael Tschannen.  Weakly-supervised disentanglement without compromises.  In _International Conference on Machine Learning_ , pp. 6348–6359. PMLR, 2020.
  * Lopez et al. (2018) Romain Lopez, Jeffrey Regier, Michael I Jordan, and Nir Yosef.  Information constraints on auto-encoding variational Bayes.  _Advances in Neural Information Processing Systems_ , 31:6114–6125, 2018.
  * Lyu & Fu (2020) Qi Lyu and Xiao Fu.  Nonlinear multiview analysis: Identifiability and neural network-assisted implementation.  _IEEE Trans. Signal Process._ , 68:2697–2712, 2020.
  * Mohri et al. (2018) Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  _Foundations of Machine Learning_.  MIT press, 2018.
  * Oord et al. (2018) Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ , 2018.
  * Rastogi et al. (2015) Pushpendre Rastogi, Benjamin Van Durme, and Raman Arora.  Multiview LSA: Representation learning via generalized CCA.  In _Proceedings of the 2015 conference of the North American chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 556–566, 2015.
  * Reed et al. (2015) Scott E Reed, Yi Zhang, Yuting Zhang, and Honglak Lee.  Deep visual analogy-making.  _Advances in Neural Information Processing Systems_ , 28:1252–1260, 2015.
  * Saunshi et al. (2019) Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar.  A theoretical analysis of contrastive unsupervised representation learning.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 5628–5637. PMLR, 09–15 Jun 2019.
  * Shalev-Shwartz & Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Socher & Fei-Fei (2010) Richard Socher and Li Fei-Fei.  Connecting modalities: Semi-supervised segmentation and annotation of images using unaligned text corpora.  In _2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , pp. 966–973. IEEE, 2010.
  * Taleb & Jutten (1999) Anisse Taleb and Christian Jutten.  Source separation in post-nonlinear mixtures.  _IEEE Trans. Signal Process._ , 47(10):2807–2820, 1999.
  * Tian et al. (2021) Yuandong Tian, Xinlei Chen, and Surya Ganguli.  Understanding self-supervised learning dynamics without contrastive pairs.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 10268–10278. PMLR, 18–24 Jul 2021.
  * Tosh et al. (2021) Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu.  Contrastive learning, multi-view redundancy, and linear models.  In _Algorithmic Learning Theory_ , pp. 1179–1206. PMLR, 2021.
  * Van der Maaten & Hinton (2008) Laurens Van der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  _Journal of machine learning research_ , 9(11), 2008.
  * von Kügelgen et al. (2021) Julius von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello.  Self-supervised learning with data augmentations provably isolates content from style.  _arXiv preprint arXiv:2106.04619_ , 2021.
  * Wang & Isola (2020) Tongzhou Wang and Phillip Isola.  Understanding contrastive representation learning through alignment and uniformity on the hypersphere.  In _International Conference on Machine Learning_ , pp. 9929–9939. PMLR, 2020.
  * Wang et al. (2015) Weiran Wang, Raman Arora, Karen Livescu, and Jeff Bilmes.  On deep multi-view representation learning.  In _International Conference on Machine Learning_ , pp. 1083–1092, 2015.
  * Wang et al. (2016) Weiran Wang, Xinchen Yan, Honglak Lee, and Karen Livescu.  Deep variational canonical correlation analysis.  _arXiv preprint arXiv:1610.03454_ , 2016.
  * Yeung & Ruzzo (2001) Ka Yee Yeung and Walter L Ruzzo.  Details of the Adjusted Rand Index and clustering algorithms, supplement to the paper an empirical study on Principal Component Analysis for clustering gene expression data.  _Bioinformatics_ , 17(9):763–774, 2001.
  * Zbontar et al. (2021) Jure Zbontar, Li Jing, Ishan Misra, Yann Lecun, and Stephane Deny.  Barlow Twins: Self-supervised learning via redundancy reduction.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 12310–12320. PMLR, 18–24 Jul 2021.
  * Zhao et al. (2019) Shengjia Zhao, Jiaming Song, and Stefano Ermon.  InfoVAE: Balancing learning and inference in variational autoencoders.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33(01):5885–5892, Jul. 2019.
  * Zhu et al. (2017) Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In _Proceedings of the IEEE international conference on computer vision_ , pp. 2223–2232, 2017.
  * Zimmermann et al. (2021) Roland S. Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel.  Contrastive learning inverts the data generating process.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 12979–12990. PMLR, 18–24 Jul 2021.

Supplementary Materials

##  Appendix A Notation

The notations used in this work are summarized in Table A.1.

Table A.1: Definition of notations. Notation | Definition
---|---
$x,\bm{x},\bm{X}$ | scalar, vector, and matrix
$[\bm{x}]_{i},x_{i}$ | both represent the $i$th element of vector $\bm{x}$
$[\bm{X}]_{ij}$ | the $i$th row, $j$th column of matrix $\bm{X}$
$p(\bm{x})$ | probability density function of random variable $\bm{x}$
${x}\perp\\!\\!\\!\perp{y}$ |  ${x}$ and ${y}$ are statistically independent, i.e., $p({x},{y})=p({x})p({y})$
$\bm{x}\perp\\!\\!\\!\perp\bm{y}$ |  ${x}_{i}\perp\\!\\!\\!\perp{y}_{j}$ for all $i,j$
$\bm{x}^{\top}$, $\bm{X}^{\top}$ | transpose of $\bm{x}$, $\bm{X}$
$\bm{J}_{\bm{f}}$ | Jocobian matrix of a vector-valued function $\bm{f}$
$\bm{I}$ | identity matrix with a proper size
$\bm{f}\circ\bm{g}$ | function composition operation
$\text{det}\bm{X}$ | determinant of a square matrix $\bm{X}$
$\mathbb{E}[\cdot]$ | expectation
$\mathbb{V}[\cdot]$ | variance
$\mathbb{Cov}[\cdot,\cdot]$ | covariance
$[N]$ | the integer set $\\{1,2,\ldots,N\\}$

##  Appendix B Proof of Theorem 1

Theorem 1. (Shared Component Extraction) Under the generative model in (5) and
Assumption 1, consider the population form in (7) (i.e., $N=\infty$). Assume
that the considered constraints hold over all $\bm{x}^{(q)}\in{\cal X}_{q}$
for $q=1,2$, where ${\cal
X}_{q}=\\{\bm{x}^{(q)}|\bm{x}^{(q)}=\bm{g}^{(q)}([\bm{z}^{\\!\top\\!},(\bm{c}^{(q)})^{\\!\top\\!}]^{\\!\top\\!}),~{}\forall\bm{z}\in{\cal
Z},\forall\bm{c}^{(q)}\in{\cal C}_{q}\\}$. Denote $\widehat{\bm{f}}^{(q)}$ as
any solution of (7). Also assume that the first-order derivative of
$\widehat{\bm{f}}^{(q)}\circ\bm{g}^{(q)}$ exists. Then, we have
$\widehat{\bm{z}}=\widehat{\bm{f}}^{(q)}_{\rm
S}\left(\bm{x}^{(q)}\right)=\bm{\gamma}({\bm{z}})$ no matter if (7d) is
enforced or not, where
$\bm{\gamma}(\cdot):\mathbb{R}^{D}\rightarrow\mathbb{R}^{D}$ is a certain
invertible functions.

We consider the formulation in (7) without (7d). When $N=\infty$ and
$\bm{x}^{(q)}\sim{\cal X}_{q}$ for $q=1,2$ are all available, the sample
average version of the formulation in (7) becomes the following expected value
version:

$\displaystyle\operatorname*{\textrm{maximize}}_{\bm{f}^{(1)},\bm{f}^{(2)}}$
$\displaystyle~{}{\rm Tr}\left(\mathbb{E}\left[\bm{f}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}_{\ell}\right)\left(\bm{f}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}_{\ell}\right)^{\\!\top\\!}\right)\right]\right)$
(B.1a) subject to $\displaystyle~{}\bm{f}^{(q)}\text{~{}for $q=1,2$ are
invertible},$ (B.1b) $\displaystyle~{}\mathbb{E}\left[\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right)\bm{f}^{(q)}_{\rm
S}\left(\bm{x}^{(q)}_{\ell}\right)^{\top}\right]=\bm{I},~{}\mathbb{E}\left[\bm{f}_{\rm
S}\left(\bm{x}^{(q)}_{\ell}\right)\right]=\bm{0},~{}q=1,2$ (B.1c)

First, note that under the generative model in (5), the maximum of the
objective function in (7) is $D$, which is obtained when every corresponding
components of the learned solutions, i.e., $\widehat{\bm{f}}^{(1)}_{\rm
S}:\mathbb{R}^{M_{1}}\rightarrow\mathbb{R}^{D}$ and
$\widehat{\bm{f}}^{(1)}_{\rm S}:\mathbb{R}^{M_{2}}\rightarrow\mathbb{R}^{D}$,
are perfectly correlated, i.e.,

$\widehat{\bm{f}}^{(1)}_{\rm
S}\left(\bm{x}^{(1)}\right)=\widehat{\bm{f}}^{(2)}_{\rm
S}\left(\bm{x}^{(2)}\right).$ (B.2)

Indeed, one may rewrite (B.1a) as

$\displaystyle\arg\min_{\bm{f}^{(1)},\bm{f}^{(2)}}~{}-2{\rm
Tr}\left(\mathbb{E}\left[\bm{f}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}_{\ell}\right)\left(\bm{f}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}_{\ell}\right)^{\\!\top\\!}\right)\right]\right)$
$\displaystyle=$
$\displaystyle\arg\min_{\bm{f}^{(1)},\bm{f}^{(2)}}~{}\bm{I}-2{\rm
Tr}\left(\mathbb{E}\left[\bm{f}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}_{\ell}\right)\left(\bm{f}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}_{\ell}\right)^{\\!\top\\!}\right)\right]\right)+\bm{I}$
$\displaystyle=$
$\displaystyle\arg\min_{\bm{f}^{(1)},\bm{f}^{(2)}}~{}\mathbb{E}\left[\left\|\bm{f}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}_{\ell}\right)-\bm{f}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}_{\ell}\right)\right\|_{2}^{2}\right]$ (B.3)

where the second equality holds because the constraint in (B.1c). Note that
the criterion in (B.3) admits the optimal solution in (B.2) under our
generative model.

Note that one solution to attain zero cost of (B.3) is

$\widehat{\bm{f}}^{(q)}_{\rm S}\left(\bm{x}^{(q)}\right)=\bm{z},~{}q=1,2.$

However, the question lies in “uniqueness”, i.e., can enforcing (B.2) always
yield $\bm{f}^{(q)}_{\rm S}\left(\bm{x}^{(q)}\right)=\bm{z}$ (up to certain
ambiguities)? This is central to learning criterion design, as the
expressiveness of function approximators like neural networks may attain zero
cost of (B.3) with undesired solutions.

Assume that a solution that satisfies (B.2) is found. Denote
$\widehat{\bm{f}}^{(q)}$ for $q=1,2$ as the solution. Combine the solution
with the generative model in (5). Then, following equality can be obtained:

$\displaystyle\bm{h}^{(1)}_{\rm S}\left(\begin{bmatrix}\bm{z}\\\
\bm{c}^{(1)}\end{bmatrix}\right)=\bm{h}^{(2)}_{\rm
S}\left(\begin{bmatrix}\bm{z}\\\ \bm{c}^{(2)}\end{bmatrix}\right),$ (B.4)

where we have

$\bm{h}_{\rm
S}^{(q)}(\bm{\omega}^{(q)})=\left[\widehat{\bm{f}}^{(q)}\circ\bm{g}^{(q)}\left(\bm{\omega}^{(q)}\right)\right]_{1:D}=\widehat{\bm{f}}_{\rm
S}^{(q)}\circ\bm{g}^{(q)}\left(\bm{\omega}^{(q)}\right),$

in which

$\bm{\omega}^{(q)}=[\bm{z}^{\top},(\bm{c}^{(q)})^{\top}]^{\top}.$

We hope to show that $\bm{h}^{(1)}_{\rm S}$ and $\bm{h}^{(2)}_{\rm S}$ are
functions of only $\bm{z}$—i.e., the functions $\widehat{\bm{f}}_{\rm
S}^{(q)}$ for $q=1,2$ only extract the shared information.

To show that $\bm{h}^{(1)}_{\rm S}$ is a function of only $\bm{z}$ but not a
function of $\bm{c}^{(1)}$, we consider the first-order partial derivatives of
$\bm{h}^{(1)}_{\rm S}$ w.r.t. $\bm{z}$ and $\bm{c}^{(1)}$, respectively.
Namely, we hope to show that the matrix consisting of all the partial
derivatives of $\bm{h}^{(1)}_{\rm S}$ w.r.t. $\bm{z}$ is full rank while any
partial derivatives of $\bm{h}^{(1)}_{\rm S}$ w.r.t. $\bm{c}^{(1)}$ is zero.

Therefore, we investigate the Jacobian of $\bm{h}^{(1)}$ which fully
characterizes all the first-order partial derivatives of the function
$\bm{h}^{(1)}_{\rm S}$ and $\bm{h}^{(1)}_{\rm P}$ w.r.t. $\bm{z}$ and
$\bm{c}^{(1)}$. Let us denote the outputs of
$\bm{h}^{(1)}=\widehat{\bm{f}}^{(1)}\circ\bm{g}^{(1)}(\bm{\omega}^{(1)})$ as
follows:

$\begin{bmatrix}\widehat{\bm{z}}\\\
\widehat{\bm{c}}^{(1)}\end{bmatrix}=\bm{h}^{(1)}\left(\begin{bmatrix}{\bm{z}}\\\
{\bm{c}}^{(1)}\end{bmatrix}\right).$ (B.5)

The Jacobian of $\bm{h}^{(1)}$ can be expressed using the following block form

$\displaystyle\bm{J}^{(1)}=\begin{bmatrix}\bm{J}^{(1)}_{11}&\bm{J}^{(1)}_{12}\\\
\bm{J}^{(1)}_{21}&\bm{J}^{(1)}_{22}\end{bmatrix},$

where $\bm{J}^{(1)}_{11}\in\mathbb{R}^{D\times D}$,
$\bm{J}^{(1)}_{12}\in\mathbb{R}^{D\times D_{1}}$,
$\bm{J}^{(1)}_{21}\in\mathbb{R}^{D_{1}\times D}$ and
$\bm{J}^{(1)}_{22}\in\mathbb{R}^{D_{1}\times D_{1}}$ are Jacobian matrices
defined as follows

$\displaystyle\bm{J}^{(1)}_{11}=\begin{bmatrix}\frac{\partial\left[\bm{h}_{\rm
S}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial
z_{1}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
S}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial z_{D}}\\\
\vdots&\ddots&\vdots\\\ \frac{\partial\left[\bm{h}_{\rm
S}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D}}{\partial
z_{1}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
S}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D}}{\partial
z_{D}}\end{bmatrix},~{}\bm{J}^{(1)}_{12}=\begin{bmatrix}\frac{\partial\left[\bm{h}_{\rm
S}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial
c^{(1)}_{1}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
S}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial
c^{(1)}_{D_{1}}}\\\ \vdots&\ddots&\vdots\\\ \frac{\partial\left[\bm{h}_{\rm
S}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D}}{\partial
c^{(1)}_{1}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
S}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D}}{\partial
c^{(1)}_{D_{1}}}\end{bmatrix},$
$\displaystyle\bm{J}^{(1)}_{21}=\begin{bmatrix}\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial
z_{1}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial z_{D}}\\\
\vdots&\ddots&\vdots\\\ \frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D_{1}}}{\partial
z_{1}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D_{1}}}{\partial
z_{D}}\end{bmatrix},~{}\bm{J}^{(1)}_{22}=\begin{bmatrix}\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial
c_{1}^{(1)}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial
c_{D_{1}}^{(1)}}\\\ \vdots&\ddots&\vdots\\\ \frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D_{1}}}{\partial
c_{1}^{(1)}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D_{1}}}{\partial
c_{D_{1}}^{(1)}}\end{bmatrix}.$

What we hope to show is that $\bm{J}^{(1)}_{12}$ is an all-zero matrix while
the determinant of $\bm{J}^{(1)}_{11}$ is non-zero.

We first show that $\bm{J}^{(1)}_{12}=\bm{0}$. Note that (B.4) holds over the
entire domain. Hence, we consider any fixed $\overline{\bm{z}}$ and
$\overline{\bm{c}}^{(2)}$. Then for all $\bm{c}^{(1)}$, the following equation
holds:

$\displaystyle\bm{h}^{(1)}_{\rm S}\left(\begin{bmatrix}\overline{\bm{z}}\\\
\bm{c}^{(1)}\end{bmatrix}\right)=\bm{h}^{(2)}_{\rm
S}\left(\begin{bmatrix}\overline{\bm{z}}\\\
\overline{\bm{c}}^{(2)}\end{bmatrix}\right)$ (B.6)

for all $\bm{c}^{(1)}\in\mathcal{C}_{1}$ with any fixed $\overline{\bm{z}}$
and $\overline{\bm{c}}^{(2)}$.

Let us define matrices $\bm{H}_{\rm S}^{(1)}$ and $\bm{H}_{\rm S}^{(2)}$,
where

$\left[\bm{H}_{\rm S}^{(q)}\right]_{i,j}=\frac{\partial\left[\bm{h}_{\rm
S}^{(q)}\left(\bm{\omega}^{(q)}\right)\right]_{i}}{\partial c_{j}^{(1)}},\
i=1,\cdots,D,\ j=1,\cdots,D_{1}.$

By taking partial derivatives of Eq. (B.6) w.r.t. ${c}_{j}^{(1)}$ for
$j=1,\ldots,D_{1}$, we have the following Jacobian:

$\displaystyle\left.\bm{H}_{\rm
S}^{(1)}\right|_{\bar{\bm{z}},{\bm{c}}^{(1)}}=\left.\bm{H}_{\rm
S}^{(2)}\right|_{\bar{\bm{z}},\bar{\bm{c}}^{(2)}}\overset{(a)}{=}\left(\left.\bm{J}_{\bm{h}^{(2)}_{\rm
S}}\right|_{\bar{\bm{z}},\bar{\bm{c}}^{(2)}}\right)\begin{bmatrix}\frac{\partial\overline{z}_{1}}{\partial
c_{1}^{(1)}}&\cdots&\frac{\partial\overline{z}_{1}}{\partial
c_{D_{1}}^{(1)}}\\\ \vdots&\ddots&\vdots\\\
\frac{\partial\overline{z}_{D}}{\partial
c_{1}^{(1)}}&\cdots&\frac{\partial\overline{z}_{D}}{\partial
c_{D_{1}}^{(1)}}\\\
\frac{\partial\overline{c}_{1}^{(2)}}{\partial{c}_{1}^{(1)}}&\cdots&\frac{\partial\overline{c}_{1}^{(2)}}{\partial{c}_{D_{1}}^{(1)}}\\\
\vdots&\ddots&\vdots\\\
\frac{\partial\overline{c}_{D_{2}}^{(2)}}{\partial{c}_{1}^{(1)}}&\cdots&\frac{\partial\overline{c}_{D_{2}}^{(2)}}{\partial{c}_{D_{1}}^{(1)}}\end{bmatrix}\overset{(b)}{=}\left(\left.\bm{J}_{\bm{h}^{(2)}_{\rm
S}}\right|_{\bar{\bm{z}},\bar{\bm{c}}^{(2)}}\right)\begin{bmatrix}\bm{0}_{D\times
D_{1}}\\\ \bm{0}_{D_{2}\times D_{1}}\end{bmatrix}=\bm{0}_{D\times D_{1}},$
(B.7)

where $\bm{J}_{\bm{h}^{(2)}_{\rm S}}\in\mathbb{R}^{D\times(D+D_{2})}$ is the
Jacobian of $\bm{h}^{(2)}_{\rm S}$, (a) is by the chain rules and (b) is
because we take derivatives of constants. The equation above holds for any
$\overline{\bm{z}}$ and $\overline{\bm{c}}^{(2)}$. Hence, the same derivation
holds for all ${\bm{z}}$ and ${\bm{c}}^{(2)}$, which leads to the conclusion
that the learned $\bm{h}_{\rm S}^{(q)}(\bm{\omega}^{(q)})$ is not a function
of $\bm{c}^{(1)}$. Note that another possibility that could lead to (B.7) is
that $\bm{h}_{\rm S}^{(q)}(\bm{\omega}^{(q)})$ always outputs a constant.
However, this is not possible because each
$\bm{h}^{(q)}=\widehat{\bm{f}}^{(q)}\circ\bm{g}^{(q)}$ is an invertible
function, which implies that any dimension of
$\bm{h}^{(q)}(\bm{\omega}^{(q)})$ cannot be a constant if $\bm{\omega}^{(q)}$
is not a constant. To be more precise, note that $\bm{x}^{(q)}$ is generated
from $\bm{\omega}^{(q)}$ that has $D+D_{q}$ dimensions. If there are $D$
dimensions (i.e., $\bm{h}_{\rm S}^{(q)}(\bm{\omega}^{(q)})\in\mathbb{R}^{D}$)
that are constants (and thus no information) in the learned generative domain,
then $\bm{x}^{(q)}$ cannot be reconstructed from that domain, which
contradicts invertibility.

Then, the Jacobian of $\bm{h}^{(1)}$ can be re-expressed by (B.7)

$\displaystyle\bm{J}^{(1)}=\begin{bmatrix}\bm{J}^{(1)}_{11}&\bm{H}_{S}^{(1)}\\\
\bm{J}^{(1)}_{21}&\bm{J}^{(1)}_{22}\end{bmatrix}=\begin{bmatrix}\bm{J}^{(1)}_{11}&\bm{0}_{D\times
D_{1}}\\\ \bm{J}^{(1)}_{21}&\bm{J}^{(1)}_{22}\end{bmatrix}.$

Next, we show that the determinant of $\bm{J}^{(1)}_{11}$ is non-zero. By the
structure of the Jacobian $\bm{J}^{(1)}$, one can see that $\widehat{\bm{z}}$
is a function of only $\bm{z}$ but not determined by $\bm{c}^{(1)}$, where we
denote as $\widehat{\bm{z}}=\bm{\gamma}(\bm{z})$. Besides, since
$\bm{h}^{(1)}$ is invertible, we have

$\left|\text{det}\bm{J}^{(1)}\right|=\left|\text{det}\bm{J}^{(1)}_{11}\right|\left|\text{det}\bm{J}^{(1)}_{22}\right|\neq
0$

by the property of determinant for block matrix. It further indicates that
$\left|\text{det}\bm{J}^{(1)}_{11}\right|\neq 0$ (so does
$\left|\text{det}\bm{J}^{(1)}_{22}\right|$), which implies that
$\bm{\gamma}(\cdot)$ is an invertible function. This proves Theorem 1.
$\square$

##  Appendix C Proof Of Theorem 2

Theorem 2. (Private Component Extraction) Under the same conditions as in
Theorem 1, also assume that (7d) is enforced, we further have
$\widehat{\bm{c}}^{(q)}=\widehat{\bm{f}}^{(q)}_{\rm
P}\left(\bm{x}^{(q)}\right)=\bm{\delta}^{(q)}\left({\bm{c}^{(q)}}\right)$,
where
$\bm{\delta}^{(q)}(\cdot):\mathbb{R}^{D_{q}}\rightarrow\mathbb{R}^{D_{q}}$ is
a certain invertible function.

Following the proof of Theorem 1, we further consider the expected value
version with (7d), i.e.,

$\displaystyle\operatorname*{\textrm{maximize}}_{\bm{f}^{(1)},\bm{f}^{(2)}}$
$\displaystyle~{}{\rm Tr}\left(\mathbb{E}\left[\bm{f}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}\right)\bm{f}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}\right)^{\\!\top\\!}\right]\right)$ (C.1a) subject
to $\displaystyle~{}\bm{f}^{(q)}\text{~{}for $q=1,2$ are invertible},$ (C.1b)
$\displaystyle~{}\mathbb{E}\left[\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}\right)\bm{f}^{(q)}_{\rm
S}\left(\bm{x}^{(q)}\right)^{\top}\right]=\bm{I},~{}\mathbb{E}\left[\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}\right)\right]=\bm{0},~{}q=1,2,$ (C.1c)
$\displaystyle~{}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}\right)\perp\\!\\!\\!\perp\bm{f}_{\rm
P}^{(q)}\left(\bm{x}^{(q)}\right),~{}q=1,2,$ (C.1d)

Again, under our generative model, any optimal solution
$(\widehat{\bm{f}}^{(1)},\widehat{\bm{f}}^{(2)})$ satisfies

$\widehat{\bm{f}}_{\rm S}^{(1)}\left(\bm{x}^{(1)}\right)=\widehat{\bm{f}}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}\right).$

We hope to further show that

$\displaystyle\widehat{\bm{c}}^{(1)}=\widehat{\bm{f}}_{\rm
P}\left(\bm{x}^{(1)}\right)=\bm{h}_{\rm
P}^{(1)}\left(\begin{bmatrix}{\bm{z}}\\\ {\bm{c}}^{(1)}\end{bmatrix}\right)$

is an invertible function-transformed version of $\bm{c}^{(1)}$, where

$\bm{h}_{\rm
P}^{(q)}(\bm{\omega}^{(q)})=\left[\widehat{\bm{f}}^{(q)}\circ\bm{g}^{(q)}\left(\bm{\omega}^{(q)}\right)\right]_{D+1:D+D_{q}}=\widehat{\bm{f}}_{\rm
P}^{(q)}\circ\bm{g}^{(q)}\left(\bm{\omega}^{(q)}\right).$

Recall that we have the following Jacobian matrix for function $\bm{h}^{(1)}$

$\displaystyle\bm{J}^{(1)}=\begin{bmatrix}\bm{J}^{(1)}_{11}&\bm{0}\\\
\bm{J}^{(1)}_{21}&\bm{J}^{(1)}_{22}\end{bmatrix},$

where the second row corresponding to function $\bm{h}_{\rm P}^{(1)}$.

Since we have shown that both $\left|\text{det}\bm{J}^{(1)}_{11}\right|\neq 0$
and $\left|\text{det}\bm{J}^{(1)}_{22}\right|\neq 0$ in Section B, we only
need to show that $\bm{J}^{(1)}_{21}$ is an all-zero matrix. To show this, we
will use the condition (C.1d). First, it is not hard to see that

$\displaystyle\bm{J}^{(1)}_{21}=\begin{bmatrix}\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial\widehat{z}_{1}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial\widehat{z}_{D}}\\\
\vdots&\ddots&\vdots\\\ \frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D_{1}}}{\partial\widehat{z}_{1}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D_{1}}}{\partial\widehat{z}_{D}}\end{bmatrix}\bm{J}^{(1)}_{11},$

by chain rules where the first matrix on the right hand side is the Jacobian
of $\widehat{\bm{c}}^{(1)}$ w.r.t. $\widehat{\bm{z}}$. By (C.1d), we have
$\widehat{\bm{c}}^{(1)}\perp\\!\\!\\!\perp\widehat{\bm{z}}$, which means that
we can observe fixed
$\tilde{\bm{c}}^{(1)}=(\widehat{c}^{(1)}_{1},\cdots,\overline{c}_{i},\cdots,\widehat{c}^{(1)}_{D_{1}})$
for any fixed $\overline{c}_{i}$ with any possible $\widehat{\bm{z}}$.
Therefore, at any specific point of $\tilde{\bm{c}}^{(1)}$, the following
always holds

$\displaystyle\frac{\partial\left[\tilde{\bm{c}}^{(1)}\right]_{i}}{\partial\widehat{z}_{j}}=\frac{\partial\overline{c}_{i}}{\partial\widehat{z}_{j}}=0,$

since the numerator is a constant. Note that the above holds for any
$\tilde{\bm{c}}^{(1)}$ with different $\overline{c}_{i}$ for $i\in[D_{1}]$,
which further means that we actually have

$\displaystyle\begin{bmatrix}\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial\widehat{z}_{1}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{1}}{\partial\widehat{z}_{D}}\\\
\vdots&\ddots&\vdots\\\ \frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D_{1}}}{\partial\widehat{z}_{1}}&\cdots&\frac{\partial\left[\bm{h}_{\rm
P}^{(1)}\left(\bm{\omega}^{(1)}\right)\right]_{D_{1}}}{\partial\widehat{z}_{D}}\end{bmatrix}=\bm{0}$

for all $\bm{h}_{\rm P}^{(1)}\left(\bm{\omega}^{(1)}\right)$ and
$\widehat{\bm{z}}$.

Therefore, $\bm{J}^{(1)}_{21}=\bm{0}_{D_{1}\times
D}\bm{J}^{(1)}_{11}=\bm{0}_{D_{1}\times D}$. Consequently, we have the
following block diagonal form for $\bm{J}^{(1)}$ by combing with Theorem 1,
i.e.,

$\displaystyle\bm{J}^{(1)}=\begin{bmatrix}\bm{J}^{(1)}_{11}&\bm{0}_{D\times
D_{1}}\\\ \bm{0}_{D_{1}\times D}&\bm{J}^{(1)}_{22}\end{bmatrix}.$

By invertibility of $\widehat{\bm{f}}^{(q)}$ and $\bm{g}^{(q)}$, we have

$\displaystyle\left|\text{det}\bm{J}^{(1)}\right|=\left|\text{det}\bm{J}^{(1)}_{11}\right|\left|\text{det}\bm{J}^{(1)}_{22}\right|\neq
0,$

which implies that $\widehat{\bm{z}}=\bm{\gamma}(\bm{z})$ and
$\widehat{\bm{c}}^{(1)}=\bm{\delta}^{(1)}\left({\bm{c}}^{(1)}\right)$ with
invertible functions $\bm{\gamma}(\cdot)$ and $\bm{\delta}^{(1)}(\cdot)$,
respectively. The same proof technique applies to $\bm{\delta}^{(2)}(\cdot)$.
$\square$

##  Appendix D Proof of Theorem 3

Theorem 3. Under the generative model in (5) and Assumptions 1 and 2, assume
that $(\bm{x}_{\ell}^{(1)},\bm{x}^{(2)}_{\ell})$ for $\ell=1,\ldots,N$ are
i.i.d. samples of $(\bm{x}^{(1)},\bm{x}^{(2)})$. Denote
$\widehat{\bm{f}}^{(q)}\in{\cal F}$ as any solution of (7) with the
invertibility constraint satisfied. Then, we have the following holds with
probability of at least $1-\delta$:
$\displaystyle\mathbb{E}\left[\sum_{i=1}^{D}\sum_{j=1}^{D_{q}}\left(\nicefrac{{\partial\left[\widehat{\bm{f}}_{\rm
S}\left(\bm{x}^{(q)}\right)\right]_{i}}}{{\partial{c}_{j}^{(q)}}}\right)^{2}\right]=O\left(\left(D{\mathfrak{R}_{N}}+\sqrt{\nicefrac{{\log(1/\delta)}}{{N}}}+\nu^{2}\right)^{2/3}\right)$
(D.1) for any $\bm{c}^{(q)}\in\mathcal{C}_{q}$ such that
$-C_{p}+\kappa_{j}\leq{c}_{j}^{(q)}\leq C_{p}-\kappa_{j}$ for all
$j\in[D_{q}]$ and all $i\in[D]$, where
$\kappa_{j}=\Omega((\nicefrac{{3}}{{C_{d}}})^{1/3}(4C_{f}(2D{\mathfrak{R}_{N}}+C_{f}\sqrt{\nicefrac{{\log(1/\delta)}}{{2N}}})+4\nu^{2})^{1/6})$.

###  D.1 A Lemma on Rademacher complexity

To derive the Rademacher complexity of the loss function, we have the
following lemma

###### Lemma 1

Consider the following function class

$\displaystyle\mathcal{H}=\left\\{l\left(\bm{x}^{(1)},\bm{x}^{(2)}\right)\left|l\left(\bm{x}^{(1)},\bm{x}^{(2)}\right)=\sum_{d=1}^{D}\left(\bm{f}_{d}^{(1)}\left(\bm{x}^{(1)}\right)-\bm{f}_{d}^{(2)}\left(\bm{x}^{(2)}\right)\right)^{2}\right.\right\\}$

where $\bm{f}_{d}^{(1)},\bm{f}_{d}^{(2)}\in\mathcal{F}^{\prime}$ are as
defined in Assumption 2. Assume that
$\left|\bm{f}^{(q)}_{d}\left(\bm{x}^{(q)}\right)\right|\leq C_{f}$ for all
$\bm{f}^{(q)}_{d}\in\mathcal{F}^{\prime}$, where $C_{f}>0$. Then, the
Rademacher complexity of class ${\cal H}$ is bounded by

$\displaystyle{\mathfrak{R}_{N}}(\mathcal{H})\leq 4DC_{f}{\mathfrak{R}_{N}}.$

Proof: First, we have the function
$\left|\bm{f}_{d}^{(1)}\left(\bm{x}^{(1)}\right)-\bm{f}_{d}^{(2)}\left(\bm{x}^{(2)}\right)\right|$
bounded within $[0,2C_{f}]$. According to the Lipschitz composition property
of Rademacher complexity (Bartlett & Mendelson, 2002), we have

${\mathfrak{R}_{N}}(\phi\circ\mathcal{F})\leq
L_{\phi}{\mathfrak{R}_{N}}(\mathcal{F})$

where $L_{\phi}$ is the Lipschitz constant of $\phi$. Here $\phi(x)=x^{2}$ and
$L_{\phi}=4C_{f}.$

Combining with the linearity property of the Rademacher complexity (Bartlett &
Mendelson, 2002), we have

$\displaystyle{\mathfrak{R}_{N}}(\mathcal{H})\leq 4DC_{f}{\mathfrak{R}_{N}}$
(D.2)

which completes the proof of the lemma. Note that (D.2) is derived by treating
$\bm{f}_{d}^{(q)}$ for $d\in[D]$ as individual functions. However,
$\bm{f}_{d}^{(q)}$ for $d\in[D]$ are the first $D$ outputs of the same
function $\bm{f}^{(q)}$—which means that many parameters of these $D$
functions are constrained to be identical. Nonetheless, this fact does not
affect the inequality in (D.2) since adding confining constraints to the
function class ${\cal H}$ only reduces the Rademacher complexity (Bartlett &
Mendelson, 2002). $\square$

###  D.2 Proof of Theorem 3

First, we bound the true risk on the view matching loss. Consider the
regression problem given
$\left(\bm{x}_{\ell}^{(1)},\bm{x}_{\ell}^{(2)}\right)$ as samples, we have

$\displaystyle\operatorname*{\textrm{minimize}}_{\bm{f}^{(1)},\bm{f}^{(2)}}~{}\frac{1}{N}\sum_{\ell=1}^{N}\left\|\bm{f}_{\rm
S}^{(1)}\left(\bm{x}_{\ell}^{(1)}\right)-\bm{f}_{\rm
S}^{(2)}\left(\bm{x}_{\ell}^{(2)}\right)\right\|_{2}^{2}.$

By Lemma 1 and (Mohri et al., 2018, Theorem 3.3), we have the following hold
with probability at least $1-\delta$

$\displaystyle\mathbb{E}\left[\left\|\bm{f}_{\rm
S}^{(1)}\left(\bm{x}_{\ell}^{(1)}\right)-\bm{f}_{\rm
S}^{(2)}\left(\bm{x}_{\ell}^{(2)}\right)\right\|_{2}^{2}\right]$
$\displaystyle\leq\frac{1}{N}\sum_{\ell=1}^{N}\left\|\bm{f}_{\rm
S}^{(1)}\left(\bm{x}_{\ell}^{(1)}\right)-\bm{f}_{\rm
S}^{(2)}\left(\bm{x}_{\ell}^{(2)}\right)\right\|_{2}^{2}$
$\displaystyle\quad+2{\mathfrak{R}_{N}}(\mathcal{H})+4C^{2}_{f}\sqrt{\frac{\log(1/\delta)}{2N}}.$

By Assumption 2(c), the first term on the right hand side can be bounded as

$\displaystyle\ \quad\frac{1}{N}\sum_{\ell=1}^{N}\left\|\bm{f}_{\rm
S}^{(1)}\left(\bm{x}_{\ell}^{(1)}\right)-\bm{f}_{\rm
S}^{(2)}\left(\bm{x}_{\ell}^{(2)}\right)\right\|_{2}^{2}$
$\displaystyle=\frac{1}{N}\sum_{\ell=1}^{N}\left\|\bm{f}_{\rm
S}^{(1)}\left(\bm{x}_{\ell}^{(1)}\right)-\bm{u}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}\right)+\bm{u}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}\right)-\bm{f}_{\rm
S}^{(2)}\left(\bm{x}_{\ell}^{(2)}\right)\right\|_{2}^{2}$
$\displaystyle\leq\frac{1}{N}\sum_{\ell=1}^{N}(\nu+\nu)^{2}=4\nu^{2}.$

where the first equality is because there exist
$\bm{u}^{(1)}\in\mathcal{G}^{-1}$ and $\bm{u}^{(2)}\in\mathcal{G}^{-1}$ such
that $\bm{u}_{\rm S}^{(1)}\left(\bm{x}^{(1)}\right)=\bm{u}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}\right)=\bm{\gamma}(\bm{z})$ and the second
inequality is by the triangle inequality.

Therefore, by plugging in ${\mathfrak{R}_{N}}(\mathcal{H})$ we have:

$\displaystyle\mathbb{E}\left[\left\|\bm{f}_{\rm
S}^{(1)}\left(\bm{x}_{\ell}^{(1)}\right)-\bm{f}_{\rm
S}^{(2)}\left(\bm{x}_{\ell}^{(2)}\right)\right\|_{2}^{2}\right]\leq\epsilon$

with the definition

$\displaystyle\epsilon$
$\displaystyle:=4\nu^{2}+8DC_{f}{\mathfrak{R}_{N}}+4C^{2}_{f}\sqrt{\frac{\log(1/\delta)}{2N}}$
$\displaystyle=4C_{f}\left(2D{\mathfrak{R}_{N}}+C_{f}\sqrt{\frac{\log(1/\delta)}{2N}}\right)+4\nu^{2}.$

Next, we use the bound of true risk to bound the energy of the entries of the
Jacobian matrix on the left hand side of Eq. (D.1). Denote $\bm{h}_{\rm
S}^{(q)}=\bm{f}_{\rm S}^{(q)}\circ\bm{g}^{(q)}$. We define the error for any
individual sample pair
$\left(\bm{x}_{\ell}^{(1)},\bm{x}^{(2)}_{\ell}\right)\sim
p\left(\bm{x}^{(1)},\bm{x}^{(2)}\right)$ as

$\displaystyle\left\|\bm{f}^{(1)}_{\rm
S}(\bm{x}_{\ell}^{(1)})-\bm{f}^{(2)}_{\rm
S}(\bm{x}_{\ell}^{(2)})\right\|_{2}^{2}=\varepsilon_{\ell},$

with $\mathbb{E}[\varepsilon_{\ell}]\leq\epsilon$.

Define another two pairs of samples, such that

$\displaystyle\left\|\bm{h}_{\rm S}^{(1)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(1)}+\Delta\bm{e}_{j}\end{bmatrix}\right)-\bm{h}_{\rm
S}^{(2)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(2)}\end{bmatrix}\right)\right\|_{2}^{2}=\varepsilon_{\widehat{\ell}},$
$\displaystyle\left\|\bm{h}_{\rm S}^{(1)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(1)}-\Delta\bm{e}_{j}\end{bmatrix}\right)-\bm{h}_{\rm
S}^{(2)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(2)}\end{bmatrix}\right)\right\|_{2}^{2}=\varepsilon_{\tilde{\ell}},$

where $\Delta>0$ and $\bm{e}_{j}$ is the unit vector in the ${c}^{(1)}_{j}$
direction. Then by triangle inequality we have

$\displaystyle\left\|\bm{h}_{\rm S}^{(1)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(1)}+\Delta\bm{e}_{j}\end{bmatrix}\right)-\bm{h}_{\rm
S}^{(1)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(1)}-\Delta\bm{e}_{j}\end{bmatrix}\right)\right\|_{2}\leq\sqrt{\varepsilon_{\widehat{\ell}}}+\sqrt{\varepsilon_{\tilde{\ell}}}.$

Define

$\psi_{ij}\left({c}^{(1)}_{j}\right):=\left[\bm{h}_{\rm
S}^{(1)}\left(\left[\bar{\bm{z}}^{\top},\left(\bar{c}_{1}^{(1)},\cdots,c_{j}^{(1)},\cdots,\bar{c}_{D_{1}}^{(1)}\right)\right]^{\top}\right)\right]_{i},$

which is a scalar function of $c_{j}^{(1)}$ with fixed $\bar{\bm{z}}$ and
$\bar{c}_{k}^{(1)}$ for $k\neq j$.

Then the element $\frac{\partial\left[\widehat{\bm{f}}_{\rm
S}\left(\bm{x}^{(1)}\right)\right]_{i}}{\partial{c}_{j}^{(1)}}$ can be
estimated using the central difference formula as

$\displaystyle\left|\frac{\partial\left[\widehat{\bm{f}}_{\rm
S}\left(\bm{x}^{(1)}\right)\right]_{i}}{\partial{c}_{j}^{(1)}}\right|$
$\displaystyle=\left|\frac{\left[\bm{h}_{\rm{S}}^{(1)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(1)}+\Delta\bm{e}_{j}\end{bmatrix}\right)-\bm{h}_{\rm{S}}^{(1)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(1)}-\Delta\bm{e}_{j}\end{bmatrix}\right)\right]_{i}}{2\Delta}-\frac{\Delta^{2}}{12}\left(\psi^{\prime\prime\prime}_{ij}(\xi_{1})+\psi^{\prime\prime\prime}_{ij}(\xi_{2})\right)\right|$
$\displaystyle\leq\frac{\left|\left[\bm{h}_{\rm{S}}^{(1)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(1)}+\Delta\bm{e}_{j}\end{bmatrix}\right)-\bm{h}_{\rm{S}}^{(1)}\left(\begin{bmatrix}\bm{z}_{\ell}\\\
\bm{c}_{\ell}^{(1)}-\Delta\bm{e}_{j}\end{bmatrix}\right)\right]_{i}\right|}{2\Delta}+\left|\frac{\Delta^{2}}{6}\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})\right|,$

where $\xi_{1}\in\left(c^{(1)}_{\ell,j},c^{(1)}_{\ell,j}+\Delta\right)$,
$\xi_{2}\in\left(c^{(1)}_{\ell,j}-\Delta,c^{(1)}_{\ell,j}\right)$ and by
intermediate value theorem
$\xi^{\prime}\in\left(c^{(1)}_{\ell,j}-\Delta,c^{(1)}_{\ell,j}+\Delta\right)$.

Since $|x_{i}|\leq\|\bm{x}\|_{\infty}\leq\|\bm{x}\|_{2}$, we have

$\displaystyle\left|\frac{\partial\left[\widehat{\bm{f}}_{\rm
S}\left(\bm{x}^{(1)}\right)\right]_{i}}{\partial{c}_{j}^{(1)}}\right|\leq\frac{\sqrt{\varepsilon_{\widehat{\ell}}}+\sqrt{\varepsilon_{\tilde{\ell}}}}{2\Delta}+\left|\frac{\Delta^{2}}{6}\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})\right|.$

By taking expectation, we have

$\displaystyle\mathbb{E}\left[\left|\frac{\partial\left[\widehat{\bm{f}}_{\rm
S}\left(\bm{x}^{(1)}\right)\right]_{i}}{\partial{c}_{j}^{(1)}}\right|\right]$
$\displaystyle\leq\frac{\mathbb{E}[\sqrt{\varepsilon_{\widehat{\ell}}}]+\mathbb{E}[\sqrt{\varepsilon_{\tilde{\ell}}}]}{2\Delta}+\left|\frac{\Delta^{2}}{6}\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})\right|$
$\displaystyle\leq\frac{\sqrt{\epsilon}}{\Delta}+\frac{\Delta^{2}}{6}|\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})|,$

where the second inequality is by Jensen’s inequality

$\mathbb{E}[\sqrt{\varepsilon_{\ell}}]\leq\sqrt{\mathbb{E}[\varepsilon_{\ell}]}\leq\sqrt{\varepsilon},$

due to the concavity of $\sqrt{x}$.

We aim to find the smallest upper bound, i.e.,

$\displaystyle\inf_{0<\Delta<\min\left\\{C_{p}+c^{(1)}_{\ell,j},C_{p}-c^{(1)}_{\ell,j}\right\\}}\frac{\sqrt{\epsilon}}{\Delta}+\frac{\Delta^{2}}{6}|\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})|.$
(D.3)

Note that the function in (D.3) is convex and smooth. We have the minimizer

$\displaystyle\Delta^{*}\in\left\\{\left(\frac{3\sqrt{\epsilon}}{|\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})|}\right)^{1/3},\min\left\\{C_{p}+c^{(1)}_{\ell,j},C_{p}-c^{(1)}_{\ell,j}\right\\}\right\\},$

which gives us the minimum

$\displaystyle\inf_{\Delta}\frac{\sqrt{\epsilon}}{\Delta}+\frac{\Delta^{2}}{6}|\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})|\leq\min\left\\{\frac{3}{2}\left(\frac{|\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})|}{3}\right)^{1/3}\epsilon^{1/3},\frac{\sqrt{\epsilon}}{\kappa_{j}}+\frac{\kappa_{j}^{2}}{6}|\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})|\right\\}.$

where
$\kappa_{j}=\min\left\\{C_{p}+c^{(1)}_{\ell,j},C_{p}-c^{(1)}_{\ell,j}\right\\}$.

If
$\kappa_{j}\geq\left(\frac{3\sqrt{\epsilon}}{|\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})|}\right)^{1/3}$,
then we can bound

$\displaystyle\mathbb{E}\left[\left|\frac{\partial\left[\widehat{\bm{f}}_{\rm
S}\left(\bm{x}^{(1)}\right)\right]_{i}}{\partial{c}_{j}^{(1)}}\right|\right]\leq\frac{3}{2}\left(\frac{|\psi^{\prime\prime\prime}_{ij}(\xi^{\prime})|}{3}\right)^{1/3}\epsilon^{1/3}.$

With fixed $N$, one can choose
$\epsilon=4C_{f}\left(2D{\mathfrak{R}_{N}}+C_{f}\sqrt{\frac{\log(1/\delta)}{2N}}\right)+4\nu^{2}$,
which gives the following bound

$\displaystyle\mathbb{E}\left[\left|\frac{\partial\left[\widehat{\bm{f}}_{\rm
S}\left(\bm{x}^{(1)}\right)\right]_{i}}{\partial{c}_{j}^{(1)}}\right|\right]\leq\frac{3}{2}\left(\frac{C_{d}}{3}\right)^{1/3}\left(4C_{f}\left(2D{\mathfrak{R}_{N}}+C_{f}\sqrt{\frac{\log(1/\delta)}{2N}}\right)+4\nu^{2}\right)^{1/3},$

if
$\kappa_{j}\geq\left(\frac{3}{C_{d}}\right)^{1/3}\left(4C_{f}\left(2D{\mathfrak{R}_{N}}+C_{f}\sqrt{\frac{\log(1/\delta)}{2N}}\right)+4\nu^{2}\right)^{1/6}$.

Considering all $i,j$ pairs, we have

$\displaystyle\mathbb{E}\left[\sum_{i=1}^{D}\sum_{j=1}^{D_{1}}\left|\frac{\partial\left[\widehat{\bm{f}}_{\rm
S}\left(\bm{x}^{(1)}\right)\right]_{i}}{\partial{c}_{j}^{(1)}}\right|\right]\leq\frac{3}{2}DD_{1}\left(\frac{C_{d}}{3}\right)^{1/3}\left(4C_{f}\left(2D{\mathfrak{R}_{N}}+C_{f}\sqrt{\frac{\log(1/\delta)}{2N}}\right)+4\nu^{2}\right)^{1/3}.$

Since $\|\cdot\|_{2}$ is upper bounded by $\|\cdot\|_{1}$, we have

$\displaystyle\mathbb{E}\left[\sum_{i=1}^{D}\sum_{j=1}^{D_{1}}\left(\frac{\partial\left[\widehat{\bm{f}}_{\rm
S}\left(\bm{x}^{(1)}\right)\right]_{i}}{\partial{c}_{j}^{(1)}}\right)^{2}\right]\leq\frac{9}{4}D^{2}D^{2}_{1}\left(\frac{C_{d}}{3}\right)^{2/3}\left(4C_{f}\left(2D{\mathfrak{R}_{N}}+C_{f}\sqrt{\frac{\log(1/\delta)}{2N}}\right)+4\nu^{2}\right)^{2/3},$

which completes the proof. The same holds for $q=2$ by role symmetry.

##  Appendix E Proof of Proposition 1

The claim can be proved by contradiction. Take $q=1$ for example. Suppose that
there exists two elements $\widehat{z}^{(1)}_{i}$ and $\widehat{c}^{(1)}_{j}$
that are dependent but (9) is $0$. Let

$\phi_{1}=\bm{e}_{i}^{\\!\top\\!},\quad\tau_{1}=\bm{e}_{j}^{\\!\top\\!},$

which are valid choices. Then, we have

$\mathbb{Cov}[\phi_{1}(\widehat{\bm{z}}^{(1)}),\tau_{1}(\widehat{\bm{c}}^{(1)})]=\mathbb{E}[\widehat{z}^{(1)}_{i}\widehat{c}^{(1)}_{j}]-\mathbb{E}[\widehat{z}^{(1)}_{i}]\mathbb{E}[\widehat{c}^{(1)}_{j}].$

Note that by definition of independence, we have

$\mathbb{E}[\widehat{z}^{(1)}_{i}\widehat{c}^{(1)}_{j}]=\mathbb{E}[\widehat{z}^{(1)}_{i}]\mathbb{E}[\widehat{c}^{(1)}_{j}]\Longleftrightarrow\widehat{z}^{(1)}_{i}\perp\\!\\!\\!\perp\widehat{c}^{(1)}_{j}.$

Hence, $\widehat{z}^{(1)}_{i}$ and $\widehat{c}^{(1)}_{j}$ being dependent
means that

$\mathbb{E}[\widehat{z}^{(1)}_{i}\widehat{c}^{(1)}_{j}]-\mathbb{E}[\widehat{z}^{(1)}_{i}]\mathbb{E}[\widehat{c}^{(1)}_{j}]\neq
0.$

Consequently, one can see that

$\displaystyle\sup_{\phi_{1},\tau_{1}}~{}\mathbb{Cov}[\phi_{1}(\widehat{\bm{z}}^{(1)}),\tau_{1}(\widehat{\bm{c}}^{(1)})]\geq\mathbb{Cov}[\phi_{1}(\widehat{\bm{z}}^{(1)}),\tau_{1}(\widehat{\bm{c}}^{(1)})]|_{\phi_{1}=\bm{e}_{i}^{\\!\top\\!},\tau_{1}=\bm{e}_{j}^{\\!\top\\!}}=\mathbb{Cov}[\widehat{z}^{(1)}_{i}\widehat{c}^{(1)}_{j}]\neq
0.$

The above is a contradiction to our assumption that holds.

On the other hand, if $\widehat{z}^{(1)}_{i}$ and $\widehat{c}^{(1)}_{j}$ are
independent for all $i\in[D]$ and $j\in[D_{1}]$, then we have

$\displaystyle\mathbb{E}[\phi(\widehat{z}^{(1)}_{i})\tau(\widehat{c}^{(1)}_{j})]-\mathbb{E}[\phi(\widehat{z}_{i})]\mathbb{E}[\tau(\widehat{c}^{(1)}_{j})]=0,$

for all $i\in[D]$ and $j\in[D_{1}]$, for any
$\phi:\mathbb{R}\rightarrow\mathbb{R}$ and
$\tau:\mathbb{R}\rightarrow\mathbb{R}$.

##  Appendix F Detailed Algorithm Implementation

Recall that the proposed criterion is

$\displaystyle\operatorname*{\textrm{maximize}}_{\bm{f}^{(1)},\bm{f}^{(2)}}$
$\displaystyle~{}{\rm Tr}\left(\frac{1}{N}\sum_{\ell=1}^{N}\bm{f}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}_{\ell}\right)\bm{f}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}_{\ell}\right)^{\\!\top\\!}\right)$ (F.1a) subject
to $\displaystyle~{}\bm{f}^{(q)}\text{~{}for $q=1,2$ are invertible},$ (F.1b)
$\displaystyle~{}\frac{1}{N}\sum_{\ell=1}^{N}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right)\bm{f}^{(q)}_{\rm
S}\left(\bm{x}^{(q)}_{\ell}\right)^{\top}=\bm{I},~{}\frac{1}{N}\sum_{\ell=1}^{N}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right)=\bm{0},~{}q=1,2,$ (F.1c)
$\displaystyle~{}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}_{\ell}^{(q)}\right)\perp\\!\\!\\!\perp\bm{f}_{\rm
P}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right),~{}q=1,2,$ (F.1d)

We will use neural networks to parameterize the functions that we aim to
learn. To move forward, first, as we have shown in the proof of Theorem 1, Eq.
(F.1) is equivalent to the following:

$\displaystyle\operatorname*{\textrm{minimize}}_{\bm{f}^{(1)},\bm{f}^{(2)}}~{}$
$\displaystyle\frac{1}{N}\sum_{\ell=1}^{N}\left\|\bm{f}_{\rm
S}^{(1)}\left(\bm{x}^{(1)}_{\ell}\right)-\bm{f}_{\rm
S}^{(2)}\left(\bm{x}^{(2)}_{\ell}\right)\right\|_{2}^{2}$ (F.2a) subject to
$\displaystyle\frac{1}{N}\sum_{\ell=1}^{N}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right)\bm{f}^{(q)}_{\rm
S}\left(\bm{x}^{(q)}_{\ell}\right)^{\top}=\bm{I},~{}\frac{1}{N}\sum_{\ell=1}^{N}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right)=\bm{0},~{}q=1,2$ (F.2b)
$\displaystyle~{}{\bm{f}^{(q)}\text{~{}for $q=1,2$ are invertible},}$ (F.2c)
$\displaystyle~{}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}_{\ell}^{(q)}\right)\perp\\!\\!\\!\perp\bm{f}_{\rm
P}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right),~{}q=1,2,$ (F.2d)

Note that we have manifold constraints on both neural networks $\bm{f}_{\rm
S}^{(1)}$ and $\bm{f}_{\rm S}^{(2)}$. Directly optimizing over such manifold
constraints may be costly and challenging. To reduce the difficulty of this
constrained problem, we introduce a slack variable $\bm{u}_{\ell}$ and recast
the formulation in (F.2) as follows:

$\displaystyle\operatorname*{\textrm{minimize}}_{\bm{f}^{(1)},\bm{f}^{(2)},\bm{u}_{\ell}}~{}$
$\displaystyle{\cal L}=\frac{1}{N}\sum_{\ell=1}^{N}{\cal
L}_{\ell}=\frac{1}{N}\sum_{\ell=1}^{N}\sum_{q=1}^{2}\left\|\bm{u}_{\ell}-{\bm{f}}^{(q)}_{\rm
S}(\bm{x}^{(q)}_{\ell})\right\|_{2}^{2}$ (F.3a) subject to
$\displaystyle\frac{1}{N}\sum_{\ell=1}^{N}\bm{u}_{\ell}\bm{u}_{\ell}^{\top}=\bm{I},\
\frac{1}{N}\sum_{\ell=1}^{N}\bm{u}_{\ell}=\bm{0}.$ (F.3b)
$\displaystyle~{}{\bm{f}^{(q)}\text{~{}for $q=1,2$ are invertible},}$ (F.3c)
$\displaystyle~{}{\bm{f}_{\rm
S}^{(q)}\left(\bm{x}_{\ell}^{(q)}\right)\perp\\!\\!\\!\perp\bm{f}_{\rm
P}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right),~{}q=1,2,}$ (F.3d)

Ideally, we hope that $\bm{u}_{\ell}=\bm{\gamma}(\bm{z}_{\ell})$. Introducing
$\bm{u}_{\ell}$ makes the $\bm{f}^{(1)}$ and $\bm{f}^{(2)}$ subproblems
unconstrained. This is a commonly used reformulation in neural network based
multiview matching (see (Benton et al., 2017; Lyu & Fu, 2020)), which is
reminiscent of the MAX-VAR formulation of CCA (Kettenring, 1971; Carroll,
1968; Rastogi et al., 2015). Such reformulations oftentimes make algorithm
design easier, since the constraints are simplified.

The inveritibility and independence constraints in (F.3c) and (F.3d) are also
not straightforward to enforce. Instead of directly enforcing the
invertibility constraint in (F.3c), we design a regularization term.
Specifically, we use the idea of autoencoder that reconstructs the samples
from their latent representations $\bm{f}^{(q)}(\bm{x}^{(q)}_{\ell})$. We
define a regularizer

$\displaystyle\mathcal{V}=\frac{1}{N}\sum_{\ell=1}^{N}\mathcal{V}_{\ell}=\frac{1}{N}\sum_{\ell=1}^{N}\sum_{q=1}^{2}\left\|\bm{x}^{(q)}_{\ell}-\bm{r}^{(q)}(\bm{f}^{(q)}(\bm{x}^{(q)}_{\ell}))\right\|_{2}^{2},$
(F.4)

as the reconstruction loss, where ${\bm{r}}^{(q)}$’s are the reconstruction
neural networks. Note that the above term being zero does not necessarily
indicate that the function $\bm{f}^{(q)}$ is invertible, since this term is
only imposed on limited number of samples. But in practice, this idea is
effective in learning invertible transformations—also see (Wang et al., 2015;
Lyu & Fu, 2020).

To promote the statistical independence constraint in (F.3d), we use the
designed independence regularizer, i.e.,

$\displaystyle\sup_{\bm{\phi}^{(q)},\bm{\tau}^{(q)}}\mathcal{R}^{(q)}=\sup_{\bm{\phi}^{(q)},\bm{\tau}^{(q)}}\frac{\left|\mathbb{Cov}\left[\bm{\phi}^{(q)}\left(\widehat{\bm{z}}^{(q)}\right),\bm{\tau}^{(q)}\left(\widehat{\bm{c}}^{(q)}\right)\right]\right|}{\left(\sqrt{\mathbb{V}[\bm{\phi}^{(q)}\left(\widehat{\bm{z}}^{(q)}\right)]}\sqrt{\mathbb{V}\left[\bm{\tau}^{(q)}\left(\widehat{\bm{c}}^{(q)}\right)\right]}\right)},$
(F.5)

where $\bm{\phi}^{(q)}$ and $\bm{\tau}^{(q)}$ are again represented by neural
networks.

Let $\bm{\theta}$ collect the parameters of $\bm{f}^{(q)}$ and
${\bm{r}}^{(q)}$, and $\bm{\eta}$ the parameters of $\bm{\phi}^{(q)}$ and
$\bm{\tau}^{(q)}$. Putting all the terms together, our working cost function
is summarized as follows:
$\displaystyle\min_{\bm{U},\bm{\theta}}\max_{\bm{\eta}}~{}$
$\displaystyle\frac{1}{N}\sum_{\ell=1}^{N}{\cal
L}_{\ell}(\bm{\theta},\bm{U})+\beta\frac{1}{N}\sum_{\ell=1}^{N}{\cal
V}_{\ell}(\bm{\theta})+\lambda\mathcal{R}(\bm{\theta},\bm{\eta}),$ (F.6a)
subject to
$\displaystyle\frac{1}{N}\sum_{\ell=1}^{N}\bm{U}\bm{U}^{\top}=\bm{I},\
\frac{1}{N}\bm{U}\bm{1}=\bm{0},$ (F.6b) where
$\bm{U}=[\bm{u}_{1},\cdots,\bm{u}_{N}]\in\mathbb{R}^{D\times N}$, and $\beta$
and $\lambda$ are nonnegative and ${\cal R}=\sum_{q=1}^{2}{\cal R}^{(q)}$.

In terms of algorithm design, we propose to handle $\bm{U}$, $\bm{\theta}$ and
$\bm{\eta}$ cyclically when the other two are fixed, i.e., alternating
optimization (AO).

First, we use stochastic gradient descent and ascent for the unconstrained
$\bm{\theta}$ and $\bm{\eta}$ subproblems. To proceed, we sample a batch of
data indexed by ${\cal B}\subseteq[N]$. Then, $\bm{\theta}$ and $\bm{\eta}$
can be updated by any stochastic gradient based optimizers, e.g., the plain-
vanilla stochastic gradient descent/ascent,

$\displaystyle\bm{\theta}$
$\displaystyle\leftarrow\bm{\theta}-\gamma\left(\frac{1}{|\mathcal{B}|}\sum_{\ell\in{\mathcal{B}}}(\nabla_{\bm{\theta}}{\mathcal{L}}_{\ell}(\bm{\theta},\bm{U})+\beta\nabla_{\bm{\theta}}{\mathcal{V}}_{\ell}(\bm{\theta}))+\lambda\widehat{\nabla}_{\bm{\theta}}{\mathcal{R}}(\bm{\theta},\bm{\eta})\right),$
$\displaystyle\bm{\eta}$
$\displaystyle\leftarrow\bm{\eta}+\delta\left(\lambda\widehat{\nabla}_{\bm{\eta}}{\mathcal{R}}(\bm{\theta},\bm{\eta})\right),$

where $\gamma$ and $\delta$ are the step sizes for the updates of
$\bm{\theta}$ and $\bm{\eta}$, respectively. The stochastic gradients of
${\cal L}$, ${\cal V}$ are defined as follows:

$\displaystyle\widehat{\nabla}_{\bm{\theta}}{\cal L}$
$\displaystyle:=\frac{1}{|\mathcal{B}|}\sum_{\ell\in{\mathcal{B}}}\nabla_{\bm{\theta}}{\mathcal{L}}_{\ell}(\bm{\theta},\bm{U})$
(F.7a) $\displaystyle\widehat{\nabla}_{\bm{\theta}}{\cal V}$
$\displaystyle:=\frac{1}{|\mathcal{B}|}\sum_{\ell\in{\mathcal{B}}}\nabla_{\bm{\theta}}{\mathcal{V}}_{\ell}(\bm{\theta}).$
(F.7b)

In addition, the terms $\widehat{\nabla}_{\bm{\theta}}\mathcal{R}$ and
$\widehat{\nabla}_{\bm{\eta}}\mathcal{R}$ are defined similarly. Taking the
latter as an example. We have
$\widehat{\nabla}_{\bm{\eta}}\mathcal{R}=\sum_{q=1}^{2}\widehat{\nabla}_{\bm{\eta}}\mathcal{R}^{(q)}$,
and $\widehat{\nabla}_{\bm{\eta}}\mathcal{R}^{(q)}$ is estimated by taking
gradient w.r.t. $\bm{\eta}$ of the following batch-estimated
$\mathcal{R}^{(q)}$ (the same holds for
$\widehat{\nabla}_{\bm{\theta}}\mathcal{R}$):

$\displaystyle{\mathcal{R}}^{(q)}_{\cal B}:=$ (F.8a)
$\displaystyle\frac{\left|\frac{1}{|\mathcal{B}|}\sum\limits_{\ell\in\mathcal{B}}\left(\bm{\phi}^{(q)}\left(\widehat{\bm{z}}^{(q)}_{\ell}\right)-\frac{1}{|\mathcal{B}|}\sum\limits_{\ell\in\mathcal{B}}\bm{\phi}^{(q)}\left(\widehat{\bm{z}}^{(q)}_{\ell}\right)\right)\left(\bm{\tau}^{(q)}\left(\widehat{\bm{c}}_{\ell}^{(q)}\right)-\frac{1}{|\mathcal{B}|}\sum\limits_{\ell\in\mathcal{B}}\bm{\tau}^{(q)}\left(\widehat{\bm{c}}_{\ell}^{(q)}\right)\right)\right|}{\sqrt{\frac{1}{|\mathcal{B}|}\sum\limits_{\ell\in\mathcal{B}}\left(\bm{\phi}^{(q)}\left(\widehat{\bm{z}}^{(q)}_{\ell}\right)-\frac{1}{|\mathcal{B}|}\sum\limits_{\ell\in\mathcal{B}}\bm{\phi}^{(q)}\left(\widehat{\bm{z}}^{(q)}_{\ell}\right)\right)^{2}}\sqrt{\frac{1}{|\mathcal{B}|}\sum\limits_{\ell\in\mathcal{B}}\left(\bm{\tau}^{(q)}\left(\widehat{\bm{c}}_{\ell}^{(q)}\right)-\frac{1}{|\mathcal{B}|}\sum\limits_{\ell\in\mathcal{B}}\bm{\tau}^{(q)}\left(\widehat{\bm{c}}_{\ell}^{(q)}\right)\right)^{2}}}$
$\displaystyle\widehat{\nabla}_{\bm{\eta}}\mathcal{R}^{(q)}:=\nabla_{\bm{\eta}}{\cal
R}^{(q)}_{{\cal B}}$ (F.8b)
$\displaystyle\widehat{\nabla}_{\bm{\theta}}\mathcal{R}^{(q)}:=\nabla_{\bm{\theta}}{\cal
R}^{(q)}_{{\cal B}}.$ (F.8c)

It was shown in (Fisher, 1915) that the correlation coefficient is computed
using random samples of Gaussian variables, the estimator in (F.8a) for ${\cal
R}^{(q)}$ is asymptotically unbiased. For other distributions, the estimation
also works well in practice; see, e.g., DCCA based works in (Wang et al.,
2015).

Consider more general stochastic optimizers, e.g., Adam (Kingma & Ba, 2014)
and Adagrad (Duchi et al., 2011). Then, the updates can be summarized as
follows:

$\displaystyle\bm{\theta}$
$\displaystyle\leftarrow\texttt{SGD\\_optimizer}\left(\bm{\theta},\widehat{\nabla}_{\bm{\theta}}{\cal
L}+\beta\widehat{\nabla}_{\bm{\theta}}{\cal
V}+\lambda\widehat{\nabla}_{\bm{\theta}}{\cal R}\right)$ (F.9)
$\displaystyle\bm{\eta}$
$\displaystyle\leftarrow\texttt{SGD\\_optimizer}\left(\bm{\eta},-\widehat{\nabla}_{\bm{\eta}}{\cal
R}\right).$ (F.10)

where (F.10) uses the negative stochastic gradient since it is an ascending
step, while stochastic optimizers are by default descending the objective
function.

The $\bm{U}$ subproblem consists of (F.3a) and (F.3b). It can be re-expressed
as follows by expanding (F.3a):

$\displaystyle\quad\
\frac{1}{N}\sum_{\ell=1}^{N}\sum_{q=1}^{2}\left\|\bm{u}_{\ell}-{\bm{f}}^{(q)}_{\rm
S}(\bm{x}^{(q)}_{\ell})\right\|_{2}^{2}$
$\displaystyle=\frac{1}{N}\sum_{\ell=1}^{N}\text{Tr}\left(2\bm{u}_{\ell}\bm{u}_{\ell}^{\top}-2\bm{u}_{\ell}\left({\bm{f}}^{(1)}_{\rm
S}\left(\bm{x}^{(1)}_{\ell}\right)+{\bm{f}}^{(2)}_{\rm
S}\left(\bm{x}^{(2)}_{\ell}\right)\right)^{\top}+\sum_{q=1}^{2}\bm{f}_{\rm
S}^{(q)}\left(\bm{x}^{(q)}_{\ell}\right)\bm{f}^{(q)}_{\rm
S}\left(\bm{x}^{(q)}_{\ell}\right)^{\top}\right).$

Note that the first term is a constant by (F.3b) and the last term does not
involve $\bm{u}_{\ell}$. Then, we rewrite the $\bm{u}_{\ell}$ subproblem as

$\displaystyle\operatorname*{\textrm{maximize}}_{\bm{U}}~{}$
$\displaystyle\text{Tr}\left(\bm{U}\left(\bm{F}^{(1)}+\bm{F}^{(2)}\right)\right),$
(F.11) subject to $\displaystyle\frac{1}{N}\bm{U}\bm{U}^{\top}=\bm{I},\
\frac{1}{N}\bm{U}\bm{1}=\bm{0},$

where $\bm{F}^{(q)}=\left[{\bm{f}}_{\rm
S}^{(q)}(\bm{x}^{(q)}_{1}),\cdots,{\bm{f}}_{\rm
S}^{(q)}(\bm{x}^{(q)}_{N})\right]$. This is an orthogonal projection onto the
set of row zero-mean and orthogonal matrices. It is shown in (Lyu & Fu, 2020,
Lemma 1) that such a projection problem, although nonconvex, can be solved to
optimality via a mean-removed singular value decomposition (SVD) procedure,
i.e.,

$\displaystyle\bm{U}\leftarrow\sqrt{N}\bm{ST}^{\top},\ \text{with
}\bm{SDT}^{\top}=\text{SVD}\left(\left(\bm{F}^{(1)}+\bm{F}^{(2)}\right)\bm{W}\right),$
(F.12)

where $\bm{W}=\bm{I}_{N}-\frac{1}{N}\bm{1}\bm{1}^{\top}$ removes the mean of
$\bm{F}^{(1)}+\bm{F}^{(2)}$, $\bm{D}\in\mathbb{R}^{D\times D}$ holds the
singular values, $\bm{S}\in\mathbb{R}^{D\times D}$ and
$\bm{T}\in\mathbb{R}^{N\times D}$ are the left and right orthogonal matrices
in the SVD, respectively.

To summarize, an alternating optimization algorithm is summarized in Algorithm
1. Notice that we use two different batch sizes (denoted as ${\cal B}_{1}$ and
${\cal B}_{2}$ in line 1 of Algorithm 1) to construct the gradient estimations
for $\widehat{\nabla}_{\bm{\theta}}{\cal L},\
\widehat{\nabla}_{\bm{\theta}}{\cal V}$ and
$\widehat{\nabla}_{\bm{\theta}}{\cal R},\ \widehat{\nabla}_{\bm{\eta}}{\cal
R}$, respectively. The reason is that accurately estimating of ${\mathcal{R}}$
using (F.8a) often requires a relatively large batch size, while small batches
may suffice for the gradient estimations of ${\cal L}$ and ${\cal V}$,
according to our extensive simulations.

Data: $\bm{x}_{\ell}^{(q)}$ for $\ell=1,\cdots,N$ and $q=1,2$

Result: $\bm{f}^{(q)},\ {\bm{r}}^{(q)}$

1

2while  _stopping criterion is not reached_ do

3 $\bm{U}\leftarrow\sqrt{N}\bm{ST}^{\top}\text{with
}\bm{SDT}^{\top}=\text{SVD}\left(\left(\bm{F}^{(1)}+\bm{F}^{(2)}\right)\bm{W}\right)$;

4

5 while  _stopping criterion is not reached_ do

draw a random batch $\mathcal{B}_{1}$ and ${\cal B}_{2}$;

// use $|{\cal B}_{2}|>|{\cal B}_{1}|$

6

7 $\widehat{\nabla}_{\bm{\theta}}{\cal L}\leftarrow\frac{1}{|{\cal
B}_{1}|}\sum_{\ell\in{\cal B}_{1}}\nabla_{\bm{\theta}}{\cal L}_{\ell}$;

8 $\widehat{\nabla}_{\bm{\theta}}{\cal V}\leftarrow\frac{1}{|{\cal
B}_{1}|}\sum_{\ell\in{\cal B}_{1}}\nabla_{\bm{\theta}}{\cal V}_{\ell}$;

$\widehat{\nabla}_{\bm{\eta}}{\cal
R}\leftarrow\sum_{q=1}^{2}\nabla_{\bm{\eta}}{\cal R}_{{\cal B}_{2}}^{(q)}$;

// using ${\cal B}_{2}$ and (F.8a), (F.8b)

9

$\widehat{\nabla}_{\bm{\theta}}{\cal
R}\leftarrow\sum_{q=1}^{2}\nabla_{\bm{\theta}}{\cal R}_{{\cal B}_{2}}^{(q)}$ ;

// using ${\cal B}_{2}$ and (F.8a), (F.8c)

10

$\bm{\theta}\leftarrow\texttt{SGD\\_optimizer}\left(\bm{\theta},\widehat{\nabla}_{\bm{\theta}}{\cal
L}+\beta\widehat{\nabla}_{\bm{\theta}}{\cal
V}+\lambda\widehat{\nabla}_{\bm{\theta}}{\cal R}\right)$ ;

// descent

11

$\bm{\eta}\leftarrow\texttt{SGD\\_optimizer}\left(\bm{\eta},-\lambda\widehat{\nabla}_{\bm{\eta}}{\cal
R}\right)$ ;

// ascent

12

13

14 end while

15

16 end while

17

Algorithm 1 Proposed Algorithm.

Computational Complexity. Tab. LABEL:tab:complexity summarizes the
computational complexity of each step. Specifically, line 2 requires computing
a thin SVD, which requires ${O}(ND^{2})$ flops. Note that this is linear in
the number of samples $N$, and $D$ is the dimension of the shared component,
which is often relatively small in practice.

Inside the inner loop line 4-10, lines 5 and 6 construct the gradient
estimations w.r.t. $\bm{\theta}$ and $\bm{\eta}$. These two steps cost
${O}(|\mathcal{B}_{1}|d_{\bm{\theta}})$ flops. Similarly, lines 7 and 8 use
${O}(|\mathcal{B}_{2}|d_{\bm{\eta}})$ and
${O}(|\mathcal{B}_{2}|d_{\bm{\theta}})$ flops, respectively. Note that we have
used $d_{\bm{\theta}}$ and $d_{\bm{\eta}}$ to denote the parameter dimensions
of the encoder/reconstruction and the independence-promoting networks,
respectively. Typically, $|\mathcal{B}_{1}|$ and $|\mathcal{B}_{2}|$ are small
numbers compared to $N$ (e.g., $|\mathcal{B}_{1}|=128,|\mathcal{B}_{2}|=512$
while $N$ could easily exceed $10^{5}$). For line 9 and 10, when a first-order
stochastic optimizer (e.g., plain-vanilla SGD, ADAM, Adagrad) is used, this
step has a computational complexity that is linear in terms of the network
size.

One can see that all the steps scale linearly with size of the neural networks
or the sample size, which makes the algorithm easy to run with large-scale
data sets and large-size neural feature extractors.

Table F.1: Computational complexity of the proposed algorithm in each iteration, where $d_{\bm{\theta}}$ and $d_{\bm{\eta}}$ denote the parameter dimensions of the encoder/reconstruction and the independence-promoting networks, respectively. | Complexity (flops)
---|---
Line 2 | ${O}(ND^{2})$
Line 5 | ${O}(|\mathcal{B}_{1}|d_{\bm{\theta}})$
Line 6 | ${O}(|\mathcal{B}_{1}|d_{\bm{\theta}})$
Line 7 | ${O}(|\mathcal{B}_{2}|d_{\bm{\eta}})$
Line 8 | ${O}(|\mathcal{B}_{2}|d_{\bm{\theta}})$
Line 9 | ${O}(d_{\bm{\theta}})$
Line 10 | ${O}(d_{\bm{\eta}})$
Overall | ${O}\left(ND^{2}+(|\mathcal{B}_{1}|+|\mathcal{B}_{2}|)d_{\bm{\theta}}+|\mathcal{B}_{2}|d_{\bm{\eta}}\right)$

##  Appendix G Experiments: More Details and Additional Validations

In this section, we show all the experiment results with greater details,
e.g., results under more metrics, more setting details, and more
demonstrations. We also include more real data experiments using the CIFAR10
(Krizhevsky et al., 2009) and dSprites data (Higgins et al., 2017).

###  G.1 Synthetic Data - Validating Main Theorems

In this subsection, we describe the synthetic data experiments. For synthetic
data, we generate the shared $\bm{z}\in\mathbb{R}^{2}$ that is uniformly drawn
from the unit circle, with noise $\mathcal{N}(0,0.02^{2})$ added to each
dimension. The private components are scalars $c^{(1)}\sim\mathcal{N}(0,2.0)$
and $c^{(2)}\sim\text{Laplace}(0,4.0)$. The shared-to-private energy ratios
for the two views are approximately -6 dB and -18 dB. The sample size is
$N=5,000$. And we use two different one-hidden-layer neural networks with 3
neurons and softplus activation to represent the invertible $\bm{g}^{(q)}$’s.
The network parameters are drawn from standard normal distribution.

The shared component $\bm{z}$ and the t-SNE of $\bm{x}^{(1)}$ and
$\bm{x}^{(2)}$ are shown in Fig. G.1. One can see that by incorporating strong
noise and nonlinear transformations, the shape of circle is hardly to be
identified in both views.

Figure G.1: Left: $\bm{z}$; middle: t-SNE of $\bm{x}^{(1)}$; right: t-SNE of
$\bm{x}^{(2)}$.

In our simulations, $\bm{f}^{(q)}$ is represented by a three-hidden-layer
multi-layer perceptrons (MLPs) with 256 neurons in each layer with ReLU
activations. In addition, $\bm{\phi}^{(q)}$ and $\bm{\tau}^{(q)}$ are
represented by two-hidden-layer MLPs with 128 neurons in each layer. We set
batch size to be 1000, $\beta=1.0$, $\lambda=0.1$. We use the Adam optimizer
(Kingma & Ba, 2014) with initial learning rate $0.001$ for all the parameters.
Besides, we also regularize the network parameters using
$\|\bm{\eta}\|_{2}^{2}$ with a regularization parameter $0.1$. This often
helps improve numerical stability when optimizing cost functions involving
neural networks. We run lines 1-1 of Algorithm 1 for 10 epochs to update
$\bm{\theta}$ and $\bm{\eta}$.

For ablation study, we test the methods with different combinations of ${\cal
L}$, ${\cal R}$ and ${\cal V}$, i.e.,

  * (i)

the proposed method (${\cal L}+{\cal V}+{\cal R}$);

  * (ii)

the proposed without independence regularization (${\cal L}+{\cal V}$);

  * (iii)

the proposed without reconstruction (${\cal L}+{\cal R}$);

  * (iv)

the proposed with only latent correlation maximization (${\cal L}$);

  * (v)

we also test the performance with HSIC (Gretton et al., 2007) as the
independence regularizer (${\cal L}+{\cal V}+\texttt{HISC}$);

All methods stop when the average matching loss $\mathcal{L}$ reaches $0.01$.
The learned components by the proposed method are shown in Fig. G.2. One can
see that the estimated shared components are matched, while the second view
exhibits relatively large noise level as expected. For the estimated private
components, one can see that both $\delta^{(1)}(\cdot)$ and
$\delta^{(2)}(\cdot)$ are approximately invertible functions.

Figure G.2: (a) Scatter plot of $\widehat{\bm{z}}^{(1)}$; (b)
$\widehat{c}^{(1)}$ as a function of ${c}^{(1)}$; (c) Scatter plot of
$\widehat{\bm{z}}^{(2)}$; (d) $\widehat{c}^{(2)}$ as a function of
${c}^{(2)}$.

To evaluate the performance of the synthetic experiment, we compute mutual
information (MI) between groups of random variables of interest (measured by
the mutual information neural estimation (MINE) (Belghazi et al., 2018) and
Gaussian kernel density estimation (KDE) (Davis et al., 2011)). The results
are averaged from 10 random trials.

One can see that all methods successfully extract the information about
$\bm{z}$ in the sense that both $\widehat{\bm{z}}^{(q)}=\widehat{\bm{f}}_{\rm
S}^{(q)}(\bm{x}^{(q)})$ for $q=1,2$ have similarly high MIs with $\bm{z}$.
Besides, all methods output $\widehat{\bm{z}}^{(q)}$ and $\widehat{{c}}^{(q)}$
($c^{(q)}$) that have small MIs—meaning that they are not dependent.

Although most loss functions using latent correlation maximization extract the
shared $\bm{z}$’s information well, the difference is articulated in
extracting the private information. The proposed
$\mathcal{L}+\mathcal{V}+\mathcal{R}$ objective has the best performance on
that regard. The method $\mathcal{L}+\mathcal{V}+\texttt{HSIC}$ also works
reasonably well since HSIC serves the same purpose as ${\cal R}$ does—but with
a kernel-based implementation.

Moreover, by looking at the last two columns, one can see that the methods
with ${\cal R}$ and ${\cal V}$ perform the best in removing the information of
$\bm{z}$ from $c^{(q)}$. This corroborates our analysis that both (7b)
(invertibility) and (7d) (independence) are vital to achieve private-shared
information disentanglement.

Tab. LABEL:ap_tab:synthetic shows the results, with all the entries averaged
over 10 random trials. One can see that the results via the Gaussian KDE are
consistent with those under MINE. That is, the proposed ${\cal L}+{\cal
V}+{\cal R}$ exhibits the best performance in terms of extracting and
disentangling the shared and private information.

Table G.1: Mutual information (MI) between groups of variables. “$\uparrow$”:
high score preferred; “$\downarrow$”: low score preferred; “n/a”: not
applicable; $\widehat{\bm{z}}^{(q)}=\widehat{\bm{f}}_{\rm S}^{(q)}$ for
$q=1,2$.

|  $\widehat{\bm{z}}^{(1)}$,$\bm{z}$ $(\uparrow)$ |  $\widehat{\bm{z}}^{(2)}$,$\bm{z}$ $(\uparrow)$ | $\widehat{\bm{z}}^{(1)}$,${c}^{(1)}$ $(\downarrow)$ | $\widehat{\bm{z}}^{(2)}$,${c}^{(2)}$ $(\downarrow)$ |  $\widehat{{c}}^{(1)}$,${c}^{(1)}$ $(\uparrow)$ |  $\widehat{{c}}^{(2)}$,${c}^{(2)}$ $(\uparrow)$ |  $\widehat{{c}}^{(1)}$,$\bm{z}$ $(\downarrow)$ |  $\widehat{{c}}^{(2)}$,$\bm{z}$ $(\downarrow)$
---|---|---|---|---|---|---|---|---
Metric | MINE-based MI Estimation (Belghazi et al., 2018)
$\mathcal{L}$ | 2.32$\pm$0.06 | 2.36$\pm$0.10 | 0.01$\pm$0.00 | 0.00$\pm$0.00 | 0.45$\pm$0.13 | 0.33$\pm$0.07 | 0.39$\pm$0.14 | 0.43$\pm$0.04
$\mathcal{L}+\mathcal{V}$ | 2.37$\pm$0.05 | 2.38$\pm$0.08 | 0.01$\pm$0.00 | 0.01$\pm$0.00 | 0.55$\pm$0.09 | 0.33$\pm$0.08 | 0.31$\pm$0.06 | 0.43$\pm$0.05
$\mathcal{L}+\mathcal{R}$ | 2.32$\pm$0.05 | 2.33$\pm$0.07 | 0.02$\pm$0.01 | 0.00$\pm$0.00 | 0.90$\pm$0.42 | 0.22$\pm$0.12 | 0.09$\pm$0.06 | 0.22$\pm$0.12
$\mathcal{L}+\mathcal{V}+\mathcal{R}$ | 2.43$\pm$0.04 | 2.39$\pm$0.09 | 0.01$\pm$0.01 | 0.01$\pm$0.00 | 1.22$\pm$ 0.33 | 0.85$\pm$0.23 | 0.04$\pm$0.02 | 0.11$\pm$0.03
$\mathcal{L}+\mathcal{V}+$HSIC | 2.48$\pm$0.09 | 2.43$\pm$0.08 | 0.01$\pm$0.00 | 0.01$\pm$0.01 | 0.68$\pm$0.25 | 0.52$\pm$0.14 | 0.04$\pm$0.01 | 0.07$\pm$0.02
Metric | Gaussian kernel density estimate (KDE)-based MI Estimation
$\mathcal{L}$ | 2.73$\pm$0.22 | 2.88$\pm$0.22 | 0.00$\pm$0.00 | 0.00 | 0.33$\pm$0.13 | 0.01$\pm$0.02 | 0.34$\pm$0.13 | 0.37$\pm$0.06
$\mathcal{L}+\mathcal{V}$ | 2.95$\pm$0.21 | 2.91$\pm$0.26 | 0.00$\pm$0.01 | 0.00 | 0.38$\pm$0.11 | 0.01$\pm$0.02 | 0.24$\pm$0.04 | 0.39$\pm$0.07
$\mathcal{L}+\mathcal{R}$ | 2.83$\pm$0.18 | 2.86$\pm$0.15 | 0.00 | 0.00 | 0.72$\pm$0.40 | 0.10$\pm$0.10 | 0.08$\pm$0.07 | 0.28$\pm$0.16
$\mathcal{L}+\mathcal{V}+\mathcal{R}$ | 3.27$\pm$0.07 | 2.88$\pm$0.25 | 0.00$\pm$0.01 | 0.00 | 0.99$\pm$0.30 | 0.35$\pm$0.11 | 0.03$\pm$0.04 | 0.08$\pm$0.03
$\mathcal{L}+\mathcal{V}+$HSIC | 3.35$\pm$0.16 | 2.95$\pm$0.33 | 0.00 | 0.00 | 0.78$\pm$0.22 | 0.06$\pm$0.06 | 0.05$\pm$0.02 | 0.02$\pm$0.01

###  G.2 Synthetic Data - Robustness to Strong Private Interference

In this subsection, we demonstrate the performance of the proposed method
under different levels of private component energy (which are often considered
interference) (Ibrahim & Sidiropoulos, 2020; Bach & Jordan, 2005; Lyu & Fu,
2020). First, we define the shared-to-private ratio (SPR) for the $q$-th view
as

$\displaystyle{\rm
SPR}=10\log_{10}\left(\frac{\frac{1}{DN}\sum_{\ell=1}^{N}\|\bm{z}_{\ell}\|_{2}^{2}}{\frac{1}{D_{q}N}\sum_{\ell=1}^{N}\|\bm{c}^{(q)}_{\ell}\|_{2}^{2}}\right)~{}{\rm
dB}.$

For the experiment, we make both views have identical SPRs. We test the
performance under SPR=-10 dB, -20 dB and -30 dB, respectively.

Tab. LABEL:ap_tab:synthetic_spr shows the evaluation results averaged from 10
trials. One can see that as SPR decreases, the MI between the extracted
$\widehat{\bm{z}}$ and $\bm{z}$ decreases—but only gracefully. The slight
decline of performance is because the matching of two views becomes harder
when the private components get stronger. However, even if SPR=-30 dB, the
extraction and disentanglement of private and shared information are still
clearly achieved. Such robustness to strong private interference is considered
a key feature of linear CCA (Ibrahim & Sidiropoulos, 2020) and post-nonlinear
CCA (Lyu & Fu, 2020). Our analysis and evaluation in this work show that such
resilience is also inherited by the proposed approach.

Table G.2: Mutual information (MI) between groups of variables under different
SPR. “$\uparrow$”: high score preferred; “$\downarrow$”: low score preferred;
$\widehat{\bm{z}}^{(q)}=\widehat{\bm{f}}_{\rm S}^{(q)}$ for $q=1,2$.

|  $\widehat{\bm{z}}^{(1)}$,$\bm{z}$ $(\uparrow)$ |  $\widehat{\bm{z}}^{(2)}$,$\bm{z}$ $(\uparrow)$ |  $\widehat{\bm{z}}^{(1)}$,${c}^{(1)}$ $(\downarrow)$ |  $\widehat{\bm{z}}^{(2)}$,${c}^{(2)}$ $(\downarrow)$ |  $\widehat{{c}}^{(1)}$,${c}^{(1)}$ $(\uparrow)$ |  $\widehat{{c}}^{(2)}$,${c}^{(2)}$ $(\uparrow)$ |  $\widehat{{c}}^{(1)}$,$\bm{z}$ $(\downarrow)$ |  $\widehat{{c}}^{(2)}$,$\bm{z}$ $(\downarrow)$
---|---|---|---|---|---|---|---|---
SPR | MINE-based MI Estimation (Belghazi et al., 2018)
-10 dB | 2.41$\pm$0.07 | 2.43$\pm$0.05 | 0.01$\pm$0.01 | 0.01$\pm$0.01 | 1.72$\pm$0.41 | 0.52$\pm$0.10 | 0.02$\pm$0.01 | 0.19$\pm$0.03
-20 dB | 1.81$\pm$0.10 | 2.15$\pm$0.09 | 0.10$\pm$0.06 | 0.01$\pm$0.01 | 1.41$\pm$0.15 | 1.15$\pm$0.07 | 0.08$\pm$0.04 | 0.06$\pm$0.02
-30 dB | 1.16$\pm$0.07 | 1.55$\pm$0.10 | 0.11$\pm$0.09 | 0.07$\pm$0.04 | 1.77$\pm$0.42 | 0.73$\pm$0.14 | 0.03$\pm$0.02 | 0.14$\pm$0.11

###  G.3 Synthetic Data - Sensitivity to Hyperparameters

In this subsection, we investigate the sensitivity to the key hyperparameters
$\beta$ and $\lambda$. The results are shown in Tab.
LABEL:ap_tab:synthetic_beta and Tab. LABEL:ap_tab:synthetic_lambda,
respectively. One can see that for the reconstruction regularization parameter
(i.e., $\beta$) does not affect the results too much unless it was set to be
overly large (i.e., $\beta=1$ or $100$ in our simulation). This makes sense,
since reconstruction is for preventing trivial degenerate solutions, and
giving this part too much attention may not really help the learning goals
(e.g., shared and private information extraction) reflected in the other parts
of the loss function. From Tab. LABEL:ap_tab:synthetic_lambda, one can see
that the choice of $\lambda$ affects the performance slightly more than
$\beta$. It makes sense, since $\lambda$ reflects the attention that the
algorithm puts on the private component extraction part. We should mention
that, for real data analysis with a downstream task (e.g., classification),
one can choose these hyperparameters using a validation set.

Table G.3: Mutual information (MI) between groups of variables with different
$\beta$ (i.e. reconstruction term). “$\uparrow$”: high score preferred;
“$\downarrow$”: low score preferred;
$\widehat{\bm{z}}^{(q)}=\widehat{\bm{f}}_{\rm S}^{(q)}$ for $q=1,2$.

|  $\widehat{\bm{z}}^{(1)}$,$\bm{z}$ $(\uparrow)$ |  $\widehat{\bm{z}}^{(2)}$,$\bm{z}$ $(\uparrow)$ |  $\widehat{\bm{z}}^{(1)}$,${c}^{(1)}$ $(\downarrow)$ |  $\widehat{\bm{z}}^{(2)}$,${c}^{(2)}$ $(\downarrow)$ |  $\widehat{{c}}^{(1)}$,${c}^{(1)}$ $(\uparrow)$ |  $\widehat{{c}}^{(2)}$,${c}^{(2)}$ $(\uparrow)$ |  $\widehat{{c}}^{(1)}$,$\bm{z}$ $(\downarrow)$ |  $\widehat{{c}}^{(2)}$,$\bm{z}$ $(\downarrow)$
---|---|---|---|---|---|---|---|---
$\lambda=1e^{-1}$ | MINE-based MI Estimation (Belghazi et al., 2018)
$\beta=1e^{-2}$ | 2.13$\pm$0.26 | 2.11$\pm$0.33 | 0.01$\pm$0.01 | 0.01$\pm$0.00 | 0.77$\pm$0.03 | 0.48$\pm$0.18 | 0.13$\pm$0.02 | 0.17$\pm$0.07
$\beta=1e^{-1}$ | 2.16$\pm$0.23 | 2.12$\pm$0.21 | 0.01$\pm$0.01 | 0.01$\pm$0.00 | 1.09$\pm$0.37 | 0.70$\pm$0.20 | 0.10$\pm$0.06 | 0.16$\pm$0.07
$\beta=1e^{0}$ | 2.41$\pm$0.13 | 2.38$\pm$0.12 | 0.01$\pm$0.00 | 0.01$\pm$0.00 | 1.48$\pm$0.08 | 0.93$\pm$0.17 | 0.02$\pm$0.00 | 0.10$\pm$0.04
$\beta=1e^{1}$ | 2.34$\pm$0.19 | 2.28$\pm$0.08 | 0.04$\pm$0.04 | 0.02$\pm$0.02 | 0.86$\pm$0.40 | 0.41$\pm$0.21 | 0.15$\pm$0.10 | 0.52$\pm$0.26
$\beta=1e^{2}$ | 2.32$\pm$0.01 | 1.77$\pm$0.07 | 0.07$\pm$0.02 | 0.40$\pm$0.05 | 0.58$\pm$0.04 | 0.21$\pm$0.03 | 0.31$\pm$0.01 | 0.69$\pm$0.05

Table G.4: Mutual information (MI) between groups of variables with different
$\lambda$ (i.e. independence regularizer). “$\uparrow$”: high score preferred;
“$\downarrow$”: low score preferred;
$\widehat{\bm{z}}^{(q)}=\widehat{\bm{f}}_{\rm S}^{(q)}$ for $q=1,2$.

|  $\widehat{\bm{z}}^{(1)}$,$\bm{z}$ $(\uparrow)$ |  $\widehat{\bm{z}}^{(2)}$,$\bm{z}$ $(\uparrow)$ |  $\widehat{\bm{z}}^{(1)}$,${c}^{(1)}$ $(\downarrow)$ |  $\widehat{\bm{z}}^{(2)}$,${c}^{(2)}$ $(\downarrow)$ |  $\widehat{{c}}^{(1)}$,${c}^{(1)}$ $(\uparrow)$ |  $\widehat{{c}}^{(2)}$,${c}^{(2)}$ $(\uparrow)$ |  $\widehat{{c}}^{(1)}$,$\bm{z}$ $(\downarrow)$ |  $\widehat{{c}}^{(2)}$,$\bm{z}$ $(\downarrow)$
---|---|---|---|---|---|---|---|---
$\beta=1e^{0}$ | MINE-based MI Estimation (Belghazi et al., 2018)
$\lambda=1e^{-2}$ | 2.36$\pm$0.09 | 2.34$\pm$0.05 | 0.01$\pm$0.00 | 0.01$\pm$0.00 | 0.56$\pm$0.18 | 0.51$\pm$0.14 | 0.25$\pm$0.07 | 0.36$\pm$0.08
$\lambda=1e^{-1}$ | 2.41$\pm$0.13 | 2.38$\pm$0.12 | 0.01$\pm$0.00 | 0.01$\pm$0.00 | 1.48$\pm$0.08 | 0.93$\pm$0.17 | 0.02$\pm$0.01 | 0.10$\pm$0.04
$\lambda=1e^{0}$ | 2.04$\pm$0.12 | 2.00$\pm$0.11 | 0.04$\pm$0.01 | 0.02$\pm$0.00 | 0.71$\pm$0.17 | 0.37$\pm$0.10 | 0.15$\pm$0.06 | 0.22$\pm$0.03
$\lambda=1e^{1}$ | 1.49$\pm$0.18 | 1.55$\pm$0.11 | 0.17$\pm$0.07 | 0.17$\pm$0.10 | 0.61$\pm$0.04 | 0.17$\pm$0.07 | 0.23$\pm$0.02 | 0.16$\pm$0.05
$\lambda=1e^{2}$ | 0.80$\pm$0.23 | 0.96$\pm$0.36 | 0.46$\pm$0.13 | 0.28$\pm$0.07 | 0.18$\pm$0.08 | 0.22$\pm$0.06 | 0.75$\pm$0.37 | 0.57$\pm$0.18

###  G.4 Real Data - More on Validating Theorem 1

Multiview MNIST Data. In this subsection, we provide more details and
evaluation results on the MNIST experiment. The way of generating such two
views (as shown in Fig. 1 of the main text) of MNIST data is similar to the
data augmentation ideas used in AM-SSL, e.g., rotation, adding noise,
cropping, flipping (Chen et al., 2020; Grill et al., 2020). We aim to match
the two views and try to learn the shared representations, which should encode
the class label information. The dataset has 70,000 samples that are
28$\times$28 images of handwritten digits. For the latent dimension, we set
$D=10$, $D_{1}=20$ and $D_{2}=50$. In particular, since the second view
consists of large random noise that are not of interest, we only add the
independence regularizer $\mathcal{R}^{(1)}$ on the first view (i.e., the
rotated digits) to learn the private component of $\bm{x}_{\ell}^{(1)}$. The
learned $\widehat{\bm{c}}_{\ell}^{(1)}$ was used to generate new samples; see
the illustration in our main text.

The network structure used for all methods is shown in Tab. G.5. The network
structure for $\bm{\phi}^{(q)}$ and $\bm{\tau}^{(q)}$ are MLPs with three
hidden layers of 64 neurons. For hyperparameters, we set batch size to be
$|\mathcal{B}_{1}|=100$ and $|\mathcal{B}_{2}|=1000$, $\beta=1.0$,
$\lambda=100.0$. For optimizer, we also use Adam (Kingma & Ba, 2014) with
initial learning rate $0.001$ for $\bm{\theta}$ and $1.0$ for $\bm{\eta}$. And
we add squared $\ell_{2}$ regularization for both $\bm{\theta}$ and
$\bm{\eta}$, with different regularization parameters that are $0.0001$ and
$0.1$, respectively. We also run the SGD optimizer for 10 epochs to update
$\bm{\theta}$ and $\bm{\eta}$.

Table G.5: Network structures for the MNIST experiment. Encoders | Decoders
---|---
input: $\bm{x}^{(q)}_{\ell}\in\mathbb{R}^{28\times 28\times 1}$ | input: $\bm{f}^{(q)}(\bm{x}^{(q)}_{\ell})\in\mathbb{R}^{D+D_{q}}$
$4\times 4$ Conv, 64 ReLU, stride 2 | FC 256, ReLU
$4\times 4$ Conv, 32 ReLU, stride 2 | FC $7\times 7\times 32$, ReLU
FC 256, ReLU |  $4\times 4$ Conv_Trans, 64 ReLU, stride 2
FC $D+D_{q}$ |  $4\times 4$ Conv_Trans, 1, stride 2

In Tab. G.6, we show more evaluation results on the learned shared information
across views. To be specific, we feed the learned
$\widehat{\bm{z}}_{\ell}^{(1)}$’s to a classifier and the $k$-means algorithm,
to observe if the learned representations improve the performance of
supervised and unsupervised learning tasks. For the classification task, we
split the data as 50,000/10,000/10,000 for training/validation/test sets. We
train a linear support vector machine (SVM) using the training data. The
performance is measured by classification error (ERR). For the clustering
task, we use the standard $k$-means to cluster on all the data samples. After
clustering, we report the performance on the test set. We use a number of
metrics to measure performance, namely, clustering accuracy (ACC), normalized
mutual information (NMI), and adjusted Rand index (ARI) (Yeung & Ruzzo, 2001).
Among these metrics, ARI ranges from $-1$ to $+1$, with 1 being the best and
$-1$ the worst and NMI range from 0 to 1 with 1 being the best.

The “Baseline” denotes the results of simply applying SVM and $k$-means onto
the raw data of the first view, i.e., $\bm{x}_{\ell}^{(1)}$ for
$\ell=1,\ldots,N$. All the results of algorithms that involve stochastic
methods are averaged over 5 random initializations. One can see that all
methods have comparably good results in terms of learning informative
representations across views. The results empirically validate our Theorem 1
that latent correlation maximization is a useful criterion to extract the
shared information with guarantees. In particular, Barlow Twins performs
slightly better in terms of benefiting downstream classification and
clustering tasks. Nonetheless, the proposed method can also guarantee
extracting private information and facilitate cross-view image generation (see
the experiments in the main text), which is out the reach of Barlow Twins and
BYOL.

In addition to showing the visualization of the learned embedding of the firs
view in Fig. 1 of the main paper, we also plot the t-SNE of the learned
representation $\widehat{\bm{z}}_{\ell}^{(2)}$ of the second view (i.e., the
noisy digits). The results are shown in Fig. G.3. One can see that the
visualization and clustering accuracy are similar to those obtained from
$\widehat{\bm{z}}^{(1)}_{\ell}$.

Figure G.3: t-SNE of the results on multiview MNIST of the second view.
Baselines: DCCA (Wang et al., 2015), Barlow Twins (Zbontar et al., 2021) and
BYOL (Grill et al., 2020) . Table G.6: The classification error (first row)
and clustering results (rows 2 to 4) of the two-view MNIST dataset.
“$\uparrow$”: high score preferred; “$\downarrow$”: low score preferred.

| Baseline | $\mathcal{L}+\mathcal{V}+\mathcal{R}$ | $\mathcal{L}+\mathcal{V}$ | DCCA | DCCAE | Barlow Twins | BYOL
---|---|---|---|---|---|---|---
ERR ($\downarrow$) | 13.40% | 2.81%$\pm$0.21% | 2.95%$\pm$0.23% | 2.87%$\pm$0.16% | 2.85%$\pm$0.05% | 2.05%$\pm$0.07% | 2.67%$\pm$0.22%
ACC ($\uparrow$) | 37.35% | 97.03%$\pm$0.13% | 96.80%$\pm$0.40% | 97.02%%$\pm$0.12% | 96.95%$\pm$0.12% | 98.06%$\pm$0.06% | 95.56%$\pm$0.41%
NMI ($\uparrow$) | 0.337 | 0.922$\pm$0.003 | 0.923$\pm$0.007 | 0.922$\pm$0.003 | 0.920$\pm$0.003 | 0.947$\pm$0.002 | 0.895$\pm$0.023
ARI ($\uparrow$) | 0.216 | 0.936$\pm$0.003 | 0.931$\pm$0.009 | 0.935$\pm$0.003 | 0.934$\pm$0.002 | 0.958$\pm$0.001 | 0.904$\pm$0.047

Augmented CIFAR10 Data for SSL. We also use the CIFAR10 dataset (Krizhevsky et
al., 2009) to validate Theorem 1. The CIFAR10 dataset contains 50,000 and
10,000 images of size $32\times 32$ for training and testing, respectively.
There are 10 different classes. We use ResNet18 as the backbone network for
learning the representation. Since CIFAR10 images are small, we replace the
first 7x7 Conv layer of stride 2 with 3x3 Conv layer of stride 1. We also
remove the max pooling layer. We follow the evaluation method in (Chen & He,
2021) to stop the algorithms after one hundred epochs. In terms of data
augmentation, we use the pipeline of different transformations in Tab. G.7.
Note that for the proposed method, we only impose constraint (7c) since our
goal here in this task is to extract essential shared information.

Table G.7: Augmentation Used for CIFAR10 to Generate Multiple Views. Transformation | Value | Probability
---|---|---
ColorJitter | brightness=0.8, contrast=0.8, saturation=0.8, hue=0.2 | 0.8
GrayScale | - | 0.2
RandomResizedCrop | scale=(0.2, 1.0), ratio=(0.75, 4/3) | -