Predicting What You Already Know Helps: Provable Self-Supervised Learning

Introduction

Self-supervised learning revitalizes machine learning models in computer vision, NLP, and control problems (see reference therein ). Training a model with auxiliary tasks based only on input features reduces the extensive costs of data collection and semantic annotations for downstream tasks. It is also known to improve the adversarial robustness of models . Self-supervised learning creates pseudo labels solely based on input features, and solves auxiliary prediction tasks (or pretext tasks) in a supervised manner. However, the underlying principles of self-supervised learning are mysterious since it is a-priori unclear why predicting what we already know should help. We thus raise the following question:

What conceptual connection between pretext and downstream tasks ensures good representations? What is a good way to quantify this?

As a thought experiment, consider a simple downstream task of classifying desert, forest, and sea images. A meaningful pretext task is to predict the background color of images (known as image colorization ). Denote $X_{1},X_{2},Y$ to be the input image, color channel, and the downstream label respectively. Given knowledge of the label $Y$, one can possibly predict the background $X_{2}$ without knowing much about $X_{1}$. In other words, $X_{2}$ is approximately independent of $X_{1}$ conditional on the label $Y$. Consider another task of inpainting the front of a building ($X_{2}$) from the rest ($X_{1}$). While knowing the label “building” ($Y$) is not sufficient for successful inpainting, adding additional latent variables $Z$ such as architectural style, location, window positions, etc. will ensure that variation in $X_{2}$ given $Y,Z$ is small. We can mathematically interpret this as $X_{1}$ being approximate conditionally independent of $X_{2}$ given $Y,Z$.

The main insight that we exploit in this work is that with approximate conditional independence (as in the above examples), a method that predicts $X_{2}$ from $X_{1}$ will inadvertently implicitly encode and learn to predict $Y$ (and $Z$) from $X_{1}$ as an intermediate step, and then predict $X_{2}$ from $Y$This is formally demonstrated in the proof sketch of Lemma 3.1.. Building upon this insight, we make the following contributions.

The goal of this paper, as in statistical learning theory, is to investigate the statistical connections between the random variables of input features (in this paper $(X_{1},X_{2})$) and downstream labels $Y$, and show how specific connections can guarantee a successful learning procedure. For self-supervised learning (SSL), success is measured using the following 2 notions, 1) expressivity, i.e. does the learned representation from SSL have the ability to express the ground truth prediction function for labels $Y$, and 2) sample complexity, i.e. can it do so with way fewer labeled samples than what would be required without SSL.

In this work, we establish theoretical analysis for self-supervised learning fulfilling these goals.

We provide generalization guarantees for a class of self-supervised algorithms under a statistical assumption of approximate conditional independence (ACI). Specifically, we show

small representation error: the learned representation can almost linearly separate downstream targets, and

small estimation error: learning the predictor for downstream tasks only require very few number of samples.

Our analysis focused on reconstruction-based SSL methods () is presented in sections 3 and 4. In Section 5, we instantiate the bound from the analysis in the topic modeling framework, a standard generative model for text , where $X_{1}$ and $X_{2}$ are chosen to be two halves of a text document. Although data can be sampled from a potentially infinite mixtures of $k$ underlying topics, an appropriate ACI assumption can be shown that leads to a downstream sample complexity of $\mathcal{O}(k)$.

We also build the connection and extend the analysis to a variant of the SimSiam method, a non-linear canonical correlation analysis (CCA) method for self-supervised learning in Section 6. Further connecting this to alternating conditional expectation (ACE) algorithm , we show how this problem is related to decomposing the conditional distribution $X_{2}\mid X_{1}$.

We quantify our notion of ACI by a certain partial covariance matrix (Definition 4.1) and our risk bound scales linear with it. We verify this and other aspects of our main generalization bound (Theorem 4.2) using simulation experiments in Section 7. We also find that pretext task experimentally helps when CI is approximately enforced in text domain. We further demonstrate on a real-world image dataset that a pretext task-based linear model performs at least as well as many baselines.

1 Related work

There has been a flurry of self-supervised methods lately. One class of methods reconstruct images from corrupted or incomplete versions of it, like denoising auto-encoders , image inpainting , and split-brain autoencoder . Pretext tasks are also created using visual common sense, including predicting rotation angle , relative patch position , recovering color channels , solving jigsaw puzzle games , and discriminating images created from distortion . We refer to the above procedures as reconstruction-based SSL. Another popular paradigm is contrastive learning . The idea is to learn representations that bring similar data points closer while pushing randomly selected points further away or to maximize a contrastive-based mutual information lower bound between different views . A popular approach for text domain is based on language modeling where models like BERT and GPT create auxiliary tasks for next word predictions . The natural ordering or topology of data is also exploited in video-based , graph-based or map-based SSL. For instance, the pretext task is to determine the correct temporal order for video frames as in .

Theory for SSL:

2 Overview of results:

Section 2 introduces notation, setup, and the self-supervised learning procedure considered in this work. In Section 3, we analyze downstream sample complexity under exact CI and unlimited labeled data to highlight the key ideas. Section 4 presents our main result with relaxed conditions: under ACI with latent variables, and assuming finite samples in both pretext and downstream tasks, for various function classes, and both regression and classification tasks. Section 5 demonstrates our results with an example in the setting of topic modeling. In Section 6 we extend our results to self-supervised tasks that enforce two views of data to have similar representations, or namely SimSiam . Experiments verifying our theoretical findings are in Section 7. Proofs of most results are in the Appendix.

Preliminary

which captures the correlation between $X$ and $Y$ setting aside the effect of $Z$.

2 Setup and methodology

We study this simplified version in the main text, where in practice, the SSL procedure may utilize an encoder-decoder structure, while the downstream task uses both $X_{1}$ and $X_{2}$ to predict $Y$. We incorporate these extensions in Appendix C.3 and H.

With finite samples, performance of a learned representation $\psi$ on the downstream task depends on the following quantities that capture expressivity and sample complexity respectively:

Guaranteed recovery with conditional independence

In this section, we focus on the case where the input $X_{1}$ and pretext target $X_{2}$ are conditionally independent (CI) given the downstream label $Y$. While this is a strong assumption that is rarely satisfied in practice, it helps us understand the role of CI with clean results and builds up to our main results with ACI with latent variables in Section 4. As a warm-up, we show how CI helps when $(X_{1},X_{2},Y)$ are jointly Gaussian to give us a flavor for the results to follow in Appendix B. We then analyze it for general random variables under two settings: (a) when the function class used for $\psi$ is universal, (b) when $\psi$ is restricted to be a linear function of given features. For now we assume access to a large amount of unlabeled data so as to learn the optimal $\psi^{*}$ perfectly and this will be relaxed later in Section 4. The general recipe for the results is as follows:

1. Find a closed-form expression for the optimal solution $\psi^{*}$ for the pretext task. 2. Use conditional independence to show that optimal $f^{*}$ is linear in $\psi^{*}$, i.e., $e_{\text{apx}}(\psi^{*})$ is small. 3. Exploit the low rank structure of $\psi^{*}$ to show small estimation error on downstream tasks.

Here $Y$ can be interpreted as the multi-class labels where $k$ is the number of classes. For regression problems, one can think about $Y$ as the discretized values of continuous labels. We do not specify the dimension for $Y$ since $Y$ could be arbitrarily encoded but the results only depend on $k$ and the variance of $Y$ (conditional on the input $X_{1}$).

1 Universal function class.

This tells us that although $f^{*}$ could be nonlinear in ${\bm{x}}_{1}$, it is guaranteed to be linear in $\psi^{*}({\bm{x}}_{1})$.

Lemma is proved by law of total expectation:

Given that $\psi^{*}$ is good for downstream, we now care about the sample complexity. We will need to assume that the representation has some nice concentration properties. We make an assumption about the whitened data $\psi^{*}(X_{1})$ to ignore scaling factors.

We note that all bounded random variables satisfy sub-gaussian property.

Fix a failure probability $\delta\in(0,1)$, under the same assumption as Lemma 3.1 and Assumption 3.2 for $\psi^{*}$, if additionally $n_{2}\gg\rho^{4}(k+\log(1/\delta))$, then the excess risk of the learned predictor ${\bm{x}}_{1}\rightarrow\hat{\bm{W}}^{\top}\psi^{*}({\bm{x}}_{1})$ on the downstream task satsifies

2 Function class induced by feature maps.

The optimal function in $\mathcal{H}$ is $\psi^{*}({\bm{x}}_{1})={\bm{\Sigma}}_{X_{2}\phi_{1}}{\bm{\Sigma}}_{\phi_{1}\phi_{1}}^{-1}\phi_{1}({\bm{x}}_{1})$, where ${\bm{\Sigma}}_{X_{2}\phi_{1}}:={\bm{\Sigma}}_{X_{2}\phi_{1}(X_{1})}$ and ${\bm{\Sigma}}_{\phi_{1}\phi_{1}}:={\bm{\Sigma}}_{\phi_{1}(X_{1})\phi_{1}(X_{1})}$.

We again show the benefit of CI, but only comparing the performance of $\psi^{*}$ to the original features $\phi_{1}$. Since $\psi^{*}$ is linear in $\phi_{1}$, it cannot have smaller approximation error than $\phi_{1}$. However CI will ensure that $\psi^{*}$ has the same approximation error as $\phi_{1}$ and enjoys better sample complexity.

(Bounded approx. error; Condition 3 in )) We have almost surely

(CI with approximation error) Fix a failure probability $\delta\in(0,1)$, under the same assumption as Lemma 3.4, Assumption 3.2 for $\psi^{*}$ and Assumption 3.3, if $n_{2}\gg\rho^{4}(k+\log(1/\delta))$, then the excess risk of the learned predictor ${\bm{x}}_{1}\rightarrow\hat{\bm{W}}^{\top}\psi^{*}({\bm{x}}_{1})$ on the downstream task satisfies:

Thus with SSL, the requirement of labels is reduced from complexity for $D_{1}$ to $\mathcal{O}(k)$.

Beyond conditional independence

Approximate conditional independence: Our new assumption will generalize Assumption 3.1 in two ways, 1) we allow for additional latent variables $Z$ that together with $Y$ could potentially make $X_{1}$ and $X_{2}$ independent, and 2) we allow this conditional independence to be approximate. Note that allowing for extra latent variable can trivially make $X_{1}$ and $X_{2}$ to be conditionally independent by picking a large enough $Z$ (e.g. $Z=(X_{1},X_{2}))$. However the following assumption, that needs the pretext target $X_{2}$ to correlate with all instances of variable $\bar{Y}=[Y,Z]$ (analogous to Lemma 3.1), will impose this restriction on how large $Z$ can be.

Suppose there exists latent variable $Z\in\mathcal{Z},|\mathcal{Z}|=m$ that ensures ${\bm{\Sigma}}_{\phi_{\bar{y}}X_{2}}\text{ is full column rank and }\|{\bm{\Sigma}}_{Y\phi_{\bar{y}}}{\bm{\Sigma}}_{X_{2}\phi_{\bar{y}}}^{\dagger}\|_{2}=1/\beta$, where $A^{\dagger}$ is pseudo-inverse, and $\phi_{\bar{y}}$ is the one-hot embedding for $\bar{Y}=[Y,Z]$.

Just as in Section 3, this assumption will not assume away the problem (Example 3.1 can be suitably extended). The additional term $1/\beta$ here captures both the “scale” of $X_{2}$ and also the strength of correlation between $X_{2}$ and $[Y,Z]$ that was discussed after Lemma 3.1. For ${\bm{\Sigma}}_{\phi_{\bar{y}}X_{2}}$ to be full column rank, it is essential that $d_{2}\geq km$, and this already gives an upper bound on the size of $Z$. Given this restriction on $Z$ (and thus $\bar{Y}$), we define the notion of approximate conditional independence.

Firstly we note that this is indeed an extension of exact CI, since exact CI in both cases will imply that $\epsilon_{\text{CI}}=0$. We present a unified analysis in the appendix that shows the $\epsilon_{\text{CI}}$ for the second case is same as the first case, with covariance operators instead of matrices (A direct derivation is in Claim D.7). We also present more relaxed and general form of the above assumptions in Appendix G.1. With this assumption, we are ready to present our main bound.

(Bounded approximation error on pretext phase ) There exists a universal constant $b_{0}$, such that $\|{\bm{\Sigma}}_{\phi_{1}\phi_{1}}^{-1/2}\phi_{1}(X_{1})a(X_{1})^{\top}\|_{F}\leq b_{0}\sqrt{d_{2}}$ almost surely.

Example: Topic Modeling

In this section, we will demonstrate how our framework can be instantiated for mixed-membership models including topic models, not just clustering. Topic modeling for text has a rich literature and is used for analyzing and designing algorithms for information retrieval, dimensionality reduction and data analysis for large text corpora. We describe the basic setup below, followed by how our results for reconstruction-based SSL can be instantiated to learn such models.

Sample a topic mixture $\mu\sim\tau$, where $\tau$ is some underlying distribution over $\Delta_{k}$, i.e. $\tau\in\Delta_{\Delta_{[k]}}$

For each $i\in[N]$, sample a topic $t_{i}\sim\mu$ and sample a word $x_{i}\sim A_{t_{i}}$ from the topic

A crucial property of topic model described above is that words in the document are sampled independently given the topic mixture $\mu$, thus giving us the property: $X_{1}\perp X_{2}\mid\mu$. Although the cardinality of $\mu\in\Delta_{[k]}$ (that implicitly shows up in Theorem 4.2) is infinite, we can still show the benefit of SSL using our theoretical framework. We will show appropriate bounds for $\epsilon_{\text{CI}}$ and $\beta$, that show up in Theorem 4.2, using the topic model generative process.

$\bar{Y}$ takes $k$ distinct values, i.e. $|\bar{\mathcal{Y}}|=k$

$X_{1}$ and $X_{1}$ are uncorrelated given $\bar{Y}$, which implies $\epsilon_{\text{CI}}=0$.

$\beta^{-1}\leq\kappa\|w\|_{2}/\lambda_{\min}(A)$

Conditional distribution decomposition: SimSiam, CCA, ACE

In this section we establish the connection between SimSiam and non-linear CCA between $X_{1}$ and $X_{2}$ and the alternating conditional expectation (ACE) algorithm. We show how our previous analysis can be extended to this setting and how the problem relates to decomposing the conditional distribution of $X_{2}\mid X_{1}$.

In the previous sections, we used $\psi$ to predict $X_{2}$ given $X_{1}$. As discussed in Remark C.1, we could have predicted $\eta(X_{2})$ from $X_{1}$ for any function $\eta$, with all bounds depending on the function $\eta$. An alternative is to avoid choosing a specific $\eta$, but instead simultaneously learn an $\eta$ that can be easily predicted from $X_{1}$. We further show how our problem setup and analysis can capture the popular method of SimSiam, an SSL method that does not use negative samples.

For zero-mean representation functions $\psi:\psi_{i}\in L^{2}(X_{1}),\eta:\eta_{i}\in L^{2}(X_{2}),i\in[k]$, we consider the generalized alternating conditional expectation (ACE) algorithm () that optimizes the following:

In the setting for the SimSiam method, $X_{1}$ and $X_{2}$ are two randomly augmented images. The non-linear CCA problem is almost identical to SimSiam, except that we use normalization of representation instead of stop-gradient to prevent representation collapse. CCA maximizes the inner product of the representations for each positive pairs $(X_{1},X_{2})$ generated from their joint distribution. At the same time, the normalization constraint ensures that the representation doesn’t collapse to trivial function, so we do not need negative samples. We now demonstrate how our previous analysis can easily apply to non-linear CCA.

In the same setting of Theorem 6.1, and suppose the learned $\psi$ satisfies Assumption 3.2, then we have:

We assume $Y$ is almost deterministic when predicting from either $X_{1}$ or $X_{2}$. Specifically, there exists a classifier $g_{1}^{*}$ such that $P_{X_{1},Y}(g_{1}^{*}(x)\neq y)\leq\alpha$; there exists $g_{2}^{*}$ such that $P_{X_{2},Y}(g_{2}^{*}(x)\neq y)\leq\alpha$.

Under the same setting and algorithm as Corollary 6.2, if additionally we assume $\alpha$-Bayes error (Assumption 6.1), we have that the generalization error also satisfies:

where $\lambda$ is the $k$-th maximal correlation between $X_{1}$ and $X_{2}$.

When the joint distribution of $X_{1},X_{2}$ is non-degenerate, $\lambda<1$. Therefore when Bayes error is small, the learned representation will yield a good downstream performance.

This corollary and the clustering setting is inspired by Theorem 3.7 in , which showed a similar result for a spectral contrastive loss. Our corollary here shows that non-linear CCA achieves similar guarantees as spectral contrastive loss, without needing any negative samples.

2 Connection to ACE algorithm and maximal correlation

Due to Courant–Fischer–Weyl min-max principle, the top singular value of $\mathcal{T}$ can be computed by the variational problem

The top $k$ singular vectors of $\mathcal{T}$ can be computed by the variational problem

ACE algorithm (Eqn. (5)) with $k$-dimensional vector-valued functions solves the ($k+1$)-SVD of $\mathcal{T}$, and the top singular vectors of $\mathcal{T}$ is always achieved by constant functions $u(x_{1})\equiv 1$ and $v(x_{2})\equiv 1$.

The second proposition shows that the variational form can be solved by the famous ACE algorithm of Breiman and Friedman .

The generalized ACE algorithm solves (4), and is equivalent to the solution of non-linear CCA as in (5).

Therefore the solution of ACE is equivalent to that of non-linear CCA.

In summary, these two propositions show that calculating the SVD of $\mathcal{T}$ corresponds to conducting the alternating conditional expectation algorithm .

Finally, the generalized maximal correlation between $X_{1}$ and $X_{2}$ is associated with the singular values of $\mathcal{T}$.

For every $k\geq 1$, we define the $k$-th maximal correlation between $X_{1}$ and $X_{2}$ as:

Experiments

In this section, we empirically verify our claim that SSL performs well when ACI is satisfied. More details for experiments can be found in Section K, including experiments in the text domain.

Computer Vision Task.

We verify if learning from $\psi$ is more effective than learning directly from $X_{1}$, in a realistic setting (without enforcing conditional independence). Specifically, we test on the Yearbook dataset , and try to predict the date when the portraits are taken (denoted as $Y_{D}$), which ranges from $1905$ to $2013$. We resize all the portraits to be $128$ by $128$. We crop out the center $64$ by $64$ pixels (the face), and treat it as $X_{2}$, and treat the outer rim as $X_{1}$ as shown in Figure 2. Our task is to predict $Y_{D}$, which is the year when the portraits are taken, and the year ranges from $1905$ to $2013$. For $\psi$, we learn $X_{2}$ from $X_{1}$ with standard image inpainting techniques , and full set of training data (without labels). After that we fix the learned $\psi$ and learn a linear model to predict $Y_{D}$ from $\psi$ using a smaller set of data (with labels). Besides linear model on $X_{1}$, another strong baseline that we compare with is using ResNet18 to predict $Y_{D}$ from $X_{1}$. With the full set of training data, this model is able to achieve a Mean Absolute Difference of $6.89$, close to what state-of-the-art can achieve . ResNet18 has similar amount of parameters as our generator, and hence roughly in the same function class. We show the MSE result as in Figure 2. Learning from $\psi$ is more effective than learning from $X_{1}$ or $X_{2}$ directly, with linear model as well as with ResNet18. Practitioner usually fine-tune $\psi$ with the downstream task, which leads to more competitive performance .

Conclusion

In this work we theoretically quantify how an approximate conditional independence assumption that connects pretext and downstream task data distributions can give sample complexity benefits of self-supervised learning on downstream tasks. Our theoretical findings are also supported by experiments on simulated data and also on real CV and NLP tasks. We would like to note that approximate CI is only a sufficient condition for a useful pretext task. We leave it for future work to investigate other mechanisms by which pretext tasks help with downstream tasks.

References

Appendix A Some Useful Facts

For a covariance matrix of joint distribution for variables $X,Y$, the covariance matrix is

Its inverse matrix ${\bm{\Sigma}}^{-1}$ satisfies

A.2 Relation to Conditional Independence

When $X_{1}\bot X_{2}|Y$, the partial covariance between $X_{1},X_{2}$ given $Y$ is :

For random variables $X_{1},X_{2}$ and a random variable $Y$ with finite values, conditional independence $X_{1}\bot X_{2}|Y$ is equivalent to:

A.3 Technical Facts for Matrix Concentration

We include this covariance concentration result that is adapted from Claim A.2 in :

And we will also use Claim A.2 from for concentrating subgaussian random variable.

Each $t$-th column of $Z$ is an $n$-dim vector that is i.i.d sampled from Gaussian distribution $\mathcal{N}(0,{\bm{\Sigma}}_{tt})$.

Each term satisfy ${\bm{\Sigma}}_{kk}^{-1}\|\mathbf{P}{\bm{z}}_{t}\|^{2}\sim\chi^{2}(d)$, and therefore with probability at least $1-\delta^{\prime}$ over ${\bm{z}}_{t}$,

Using union bound, take $\delta^{\prime}=\delta/k$ and summing over $t\in[k]$ we get:

Let $X_{1},\cdots,X_{m}$ be independent zero-mean vector-valued random variables. Let

Therefore by vector Bernstein Inequality, with probability at least $1-\delta/d$, $\|X\|\leq\sigma(1+\sqrt{\log(d/\delta)})$. Then by taking union bound, we get that $\|\mathbf{P}{\bm{Z}}\|^{2}=\sum_{j=1}^{d}\|{\bm{u}}_{j}^{\top}{\bm{Z}}\|^{2}\lesssim\sigma^{2}d(1+\log(d/\delta))$ with probability $1-\delta$.

Appendix B Warm-up: jointly Gaussian variables

Under Assumption B.1, the representation function and optimal prediction that minimize the population risk can be expressed as follows:

Under Assumption B.1, B.2, if ${\bm{\Sigma}}_{X_{2}Y}$ has rank $k$, we have $f^{*}({\bm{x}}_{1})\equiv{\bm{W}}^{*}\psi^{*}({\bm{x}}_{1})$, i.e., $e_{\text{apx}}(\psi^{*})=0$.

Next we consider the estimation error that characterizes the number of samples needed to learn a prediction function $f({\bm{x}}_{1})=\hat{{\bm{W}}}\psi^{*}({\bm{x}}_{1})$ that generalizes.

Fix a failure probability $\delta\in(0,1)$. Under Assumption B.1,B.2, if $n_{2}\gg k+\log(1/\delta)$, excess risk of the learned predictor ${\bm{x}}_{1}\rightarrow\hat{\bm{W}}\psi^{*}({\bm{x}}_{1})$ on the target task satisfies

This assumption lets introduce some reasonable latent variables that capture the information between $X_{1}$ and $X_{2}$ apart from $Y$. ${\bm{\Sigma}}_{X_{2}\bar{Y}}$ being full rank says that all directions of $\bar{Y}$ are needed to predict $X_{2}$, and therefore $Z$ is not redundant. For instance, when $Z=X_{1}$, the assumption is trivially true but $Z$ is not the minimal latent information we want to add. Note it implicitly requires $d_{2}\geq k+m$.

Under Assumption B.1, B.3, we have $f^{*}({\bm{x}}_{1})\equiv{\bm{W}}^{*}\psi^{*}({\bm{x}}_{1})$, i.e., the approximation error $e_{\text{apx}}(\psi^{*})$ is 0. We can also generalize Theorem B.3 by replacing $k$ by $k+m$.

Appendix C Omitted Proofs with Conditional Independence

Let selector operator $\bm{S}_{y}$ be the mapping such that $\bm{S}_{y}\bar{Y}=Y$, we overload it as the matrix that ensure $\bm{S}_{y}{\bm{\Sigma}}_{\bar{Y}X}={\bm{\Sigma}}_{YX}$ for any random variable $X$ as well.

Therefore by rearranging both sides, we have:

The last inequality is derived from Claim A.4 and the fact that each row of ${\bm{N}}$ follows gaussian distribution $\mathcal{N}(0,{\bm{\Sigma}}_{YY|X_{1}})$. Therefore

Let the representation function $\psi$ be defined as:

With Lemma 3.1 we know $e_{\text{apx}}=0$, and therefore ${\bm{W}}^{*}\psi(X_{1})\equiv f^{*}(X_{1})$. Next from basic inequality and the same proof as in Theorem B.3 we have:

And therefore we could easily conclude that:

C.2 Omitted proof of linear model with approximation error

Recall $\hat{\bm{W}}=\operatorname*{arg\,min}_{{\bm{W}}}\|{\bm{Y}}-\psi({\bm{X}}_{1}){\bm{W}}\|^{2}_{F}$. We have the basic inequality,

With Assumption 3.3 and by concentration $0.9\frac{1}{n_{2}}{\bm{X}}_{1}{\bm{X}}_{1}^{\top}\preceq{\bm{\Sigma}}_{X_{1}}\preceq 1.1\frac{1}{n_{2}}{\bm{X}}_{1}{\bm{X}}_{1}^{\top}$, we have

Denote $\psi({\bm{X}}_{1})={\bm{X}}_{1}\bm{B}$, where $\bm{B}={\bm{\Sigma}}_{X_{1}}^{-1}{\bm{\Sigma}}_{X_{1}X_{2}}$ is rank $k$ under exact CI since ${\bm{\Sigma}}_{X_{1}X_{2}}={\bm{\Sigma}}_{X_{1}Y}{\bm{\Sigma}}_{Y}^{-1}{\bm{\Sigma}}_{YX_{2}}$. We have

Finally, by concentration we transfer the result from empirical loss to excess risk and get:

C.3 Argument on Denoising Auto-encoder or Context Encoder

We note that since $X_{1}\bot X_{2}|Y$ ensures $X_{1}\bot h(X_{2})|Y$ for any deterministic function $h$, we could replace $X_{2}$ by $h(X_{2})$ and all results hold. Therefore in practice, we could use $h(\psi(X_{1}))$ instead of $\psi(X_{1})$ for downstream task. Specifically with denoising auto-encoder or context encoder, one could think about $h$ as the inverse of decoder $D$ ($h=D^{-1}$) and use $D^{-1}\psi\equiv E$ the encoder function as the representation for downstream tasks, which is more commonly used in practice.

This section explains what we claim in Remark C.1. For context encoder, the reconstruction loss targets to find the encoder $E^{*}$ and decoder $D^{*}$ that achieve

where $X_{2}$ is the masked part we want to recover and $X_{1}$ is the remainder.

If we naively apply our theorem we should use $D^{*}(E^{*}(\cdot))$ as the representation, while in practice we instead use only the encoder part $E^{*}(\cdot)$ as the learned representation. We argue that our theory also support this practical usage if we view the problem differently. Consider the pretext task to predict $(D^{*})^{-1}(X_{2})$ instead of $X_{2}$ directly, namely,

and then we should indeed use $E(X_{1})$ as the representation. On one hand, when $X_{1}\bot X_{2}|Y$, it also satisfies $X_{1}\bot(D^{*})^{-1}(X_{2})|Y$ since $(D^{*})^{-1}$ is a deterministic function of $X_{2}$ and all our theory applies. On the other hand, the optimization on (13) or (14) give us similar result. Let

where $L:=\|(D^{*})^{-1}\|_{\text{Lip}}$ is the Lipschitz constant for function $(D^{*})^{-1}$. This is to say, in practice, we optimize over (13), and achieves a good representation $E^{*}(X_{1})$ such that $\epsilon_{\text{pre}}\leq L\sqrt{\epsilon}$ and thus performs well for downstream tasks. (Recall $\epsilon_{\text{pre}}$ is defined in Theorem 4.2 that measures how well we have learned the pretext task.)

Appendix D Omitted Proofs Beyond Conditional Independence

As before, for simplicity we assume all data is centered in this case.

$\sigma_{k+m}({\bm{\Sigma}}_{Y\bar{Y}}^{\dagger}{\bm{\Sigma}}_{\bar{Y}X_{2}})=\beta>0$ $\sigma_{k}(\bm{A})$ denotes $k$-th singular value of $\bm{A}$, and $\bm{A}^{\dagger}$ is the pseudo-inverse of $\bm{A}$. and ${\bm{\Sigma}}_{X_{2},\bar{Y}}$ is of rank $k+m$, where $\bar{Y}=[Y,Z]$.

When $X_{1}$ is not exactly CI of $X_{2}$ given $Y$ and $Z$, the approximation error depends on the norm of $\|{\bm{\Sigma}}_{X_{1}}^{-1/2}{\bm{\Sigma}}_{X_{1},X_{2}|\bar{Y}}\|_{2}$. Let $\hat{\bm{W}}$ be the solution from Equation 2.2.

Under Assumption D.1 with constant $\epsilon_{\text{CI}}$ and $\beta$, then the excess risk satisfies

Let ${\bm{V}}:=f^{*}({\bm{X}}_{1})\equiv{\bm{X}}_{1}{\bm{\Sigma}}^{-1}_{X_{1}X_{1}}{\bm{\Sigma}}_{1Y}$ be our target direction. Denote the optimal representation matrix by $\Psi:=\psi({\bm{X}}_{1})\equiv{\bm{X}}_{1}\bm{A}$ (where $\bm{A}:={\bm{\Sigma}}_{X_{1}X_{1}}^{-1}{\bm{\Sigma}}_{X_{1}X_{2}}$).

Next we will make use of the conditional covariance matrix:

and plug it in into the definition of $\Psi$:

where ${\bm{L}}:={\bm{X}}_{1}{\bm{\Sigma}}^{-1}_{X_{1}X_{1}}{\bm{\Sigma}}_{X_{1}\bar{Y}}{\bm{\Sigma}}_{\bar{Y}}^{-1}{\bm{\Sigma}}_{\bar{Y}X_{2}}$ and ${\bm{E}}:={\bm{X}}_{1}{\bm{\Sigma}}^{-1}_{X_{1}X_{1}}{\bm{\Sigma}}_{X_{1}X_{2}|\bar{Y}}$. We analyze these two terms respectively.

For ${\bm{L}}$, we note that span$({\bm{V}})\subseteq$span$({\bm{L}})$: ${\bm{L}}{\bm{\Sigma}}^{\dagger}_{X_{2}\bar{Y}}{\bm{\Sigma}}_{\bar{Y}}={\bm{X}}_{1}{\bm{\Sigma}}^{-1}_{X_{1}X_{1}}{\bm{\Sigma}}_{X_{1}\bar{Y}}$. By right multiplying the selector matrix $S_{Y}$ we have: ${\bm{L}}{\bm{\Sigma}}^{\dagger}_{X_{2}\bar{Y}}{\bm{\Sigma}}_{\bar{Y}Y}={\bm{X}}_{1}{\bm{\Sigma}}^{-1}_{X_{1}X_{1}}{\bm{\Sigma}}_{X_{1}Y}$, i.e., ${\bm{L}}\bar{\bm{W}}={\bm{V}}$, where $\bar{\bm{W}}:={\bm{\Sigma}}^{\dagger}_{X_{2}\bar{Y}}{\bm{\Sigma}}_{\bar{Y}Y}$. From our assumption that $\sigma_{r}({\bm{\Sigma}}_{\bar{Y}Y}^{\dagger}{\bm{\Sigma}}_{\bar{Y}X_{2}})=\beta$, we have $\|\bar{\bm{W}}\|_{2}\leq\|{\bm{\Sigma}}_{X_{2}\bar{Y}}^{\dagger}{\bm{\Sigma}}_{\bar{Y}}\|_{2}\leq 1/\beta$. (Or we could directly define $\beta$ as $\sigma_{k}({\bm{\Sigma}}_{Y\bar{Y}}^{\dagger}{\bm{\Sigma}}_{\bar{Y}X_{2}})\equiv\|\bar{\bm{W}}\|_{2}$. )

By concentration, we have ${\bm{E}}={\bm{X}}_{1}{\bm{\Sigma}}^{-1}_{X_{1}X_{1}}{\bm{\Sigma}}_{X_{1}X_{2}|\bar{Y}}$ converges to ${\bm{\Sigma}}^{-1/2}_{X_{1}X_{1}}{\bm{\Sigma}}_{X_{1}X_{2}|\bar{Y}}$. Specifically, when $n\gg k+\log 1/\delta$, $\|{\bm{E}}\|_{F}\leq 1.1\|{\bm{\Sigma}}^{-1/2}_{X_{1}X_{1}}{\bm{\Sigma}}_{X_{1}X_{2}|\bar{Y}}\|_{F}\leq 1.1\epsilon_{\text{CI}}$ (by using Lemma A.2 ). Together we have $\|{\bm{E}}\bar{\bm{W}}\|_{F}\lesssim\epsilon_{\text{CI}}/\beta$.

Let $\hat{\bm{W}}=\operatorname*{arg\,min}_{{\bm{W}}}\|{\bm{Y}}-\Psi{\bm{W}}\|^{2}$. We note that ${\bm{Y}}={\bm{N}}+{\bm{V}}={\bm{N}}+\Psi\bar{\bm{W}}-{\bm{E}}\bar{\bm{W}}$ where ${\bm{V}}$ is our target direction and ${\bm{N}}$ is random noise (each row of ${\bm{N}}$ has covariance matrix ${\bm{\Sigma}}_{YY|X_{1}}$).

Next, by the same procedure that concentrates $\frac{1}{n_{2}}{\bm{X}}_{1}^{\top}{\bm{X}}_{1}$ to ${\bm{\Sigma}}_{X_{1}X_{1}}$ with Claim A.2, we could easily get

D.2 Measuring conditional dependence with cross-covariance operator

$L^{2}(P_{X})$ denotes the Hilbert space of square integrable function with respect to the measure $P_{X}$, the marginal distribution of $X$. We are interested in some function class $\mathcal{H}_{x}\subset L^{2}(P_{X})$ that is induced from some feature maps:

Linear model is a special case when feature map $\phi=Id$ is identity mapping and the inner product is over Euclidean space. A feature map with higher order polynomials correspondingly incorporate high order moments . For discrete variable $Y$ we overload $\phi$ as the one-hot embedding.

When there’s no ambiguity, we overload $\phi_{1}$ as the random variable $\phi_{1}(X_{1})$ over domain $\mathcal{F}_{1}$, and $\mathcal{H}_{1}$ as the function class over $X_{1}$. Next we characterize CI using the cross-covariance operator.

With one-hot encoding map $\phi_{y}$ and arbitrary $\phi_{1}$, $X_{1}\bot X_{2}|Y$ ensures:

A more complete discussion of cross-covariance operator and CI can be found in . Also, recall that an operator $\mathcal{C}:\mathcal{F}_{y}\rightarrow\mathcal{F}_{x}$ is Hilbert-Schmidt (HS) if for complete orthonormal systems (CONSs) $\{\zeta_{i}\}$ of $\mathcal{F}_{x}$ and $\{\eta_{i}\}$ of $\mathcal{F}_{y}$, $\|\mathcal{C}\|^{2}_{\text{HS}}:=\sum_{i,j}\langle\zeta_{j},\mathcal{C}\eta_{i}\rangle^{2}_{\mathcal{F}_{x}}<\infty$. The Hilbert-Schmidt norm generalizes the Frobenius norm from matrices to operators, and we will later use $\|\mathcal{C}_{\phi_{1}X_{2}|\phi_{y}}\|$ to quantify approximate CI.

We note that covariance operators are commonly used to capture conditional dependence of random variables. In this work, we utilize the covariance operator to quantify the performance of the algorithm even when the algorithm is not a kernel method.

D.3 Omitted Proof in General Setting

For feature maps $\phi_{1}$ with universal property, we have:

For general feature maps, we instead have:

To prove Claim D.5, we show the following lemma:

Let $\phi:\mathcal{X}\rightarrow\mathcal{F}_{x}$ be a universal feature map, then for random variable $Y\in\mathcal{Y}$ we have:

D.4 Omitted Proof for Main Results

We first prove a simpler version without approximation error.

For a fixed $\delta\in(0,1)$, under Assumption 4.1, 3.2, if there is no approximation error, i.e., there exists a linear operator $A$ such that $f^{*}(X_{1})\equiv A\phi_{1}(X_{1})$, if $n_{1},n_{2}\gg\rho^{4}(d_{2}+\log 1/\delta)$, and we learn the pretext tasks such that:

Then we are able to achieve generalization for downstream task with probability $1-\delta$:

Let $\Psi^{*},{\bm{L}},{\bm{E}},{\bm{V}}$ be defined as follows:

Let ${\bm{V}}=f^{*}({\bm{X}}_{1}^{\text{down}})\equiv f^{*}_{\mathcal{H}_{1}}({\bm{X}}_{1}^{\text{down}})\equiv\phi({\bm{X}}_{1}^{\text{down}})\mathcal{C}^{-1}_{\phi_{1}}\mathcal{C}_{\phi_{1}Y}$ be our target direction. Denote the optimal representation matrix by

where ${\bm{L}}=\phi({\bm{X}}_{1}^{\text{down}})\mathcal{C}^{-1}_{\phi_{1}\phi_{1}}\mathcal{C}_{\phi_{1}\phi_{\bar{y}}}\mathcal{C}_{\phi_{\bar{y}}}^{-1}\mathcal{C}_{\phi_{\bar{y}}X_{2}}$ and ${\bm{E}}=\phi({\bm{X}}_{1}^{\text{down}})\mathcal{C}^{-1}_{\phi_{1}\phi_{1}}\mathcal{C}_{\phi_{1}X_{2}|\bar{Y}}$.

In this proof, we denote $S_{Y}$ as the matrix such that $S_{Y}\phi_{\bar{y}}=Y$. Specifically, if $Y$ is of dimension $d_{3}$, $S_{Y}$ is of size $d_{3}\times|\mathcal{Y}||\mathcal{Z}|$. Therefore $S_{Y}{\bm{\Sigma}}_{\phi_{y}A}={\bm{\Sigma}}_{YA}$ for any random variable $A$.

where $\bar{\bm{W}}:={\bm{\Sigma}}_{X_{2}\phi_{\bar{y}}}^{\dagger}{\bm{\Sigma}}_{\phi_{\bar{y}}Y}$ satisfies $\|\bar{\bm{W}}\|_{2}=1/\beta$. Therefore span$({\bm{V}})\subseteq$span$({\bm{L}})$ since we have assumed that ${\bm{\Sigma}}_{X_{2}\phi_{\bar{y}}}^{\dagger}{\bm{\Sigma}}_{\phi_{\bar{y}}Y}$ to be full rank.

On the other hand, ${\bm{E}}=\phi_{1}({\bm{X}}_{1}^{\text{down}})\mathcal{C}^{-1}_{\phi_{1}\phi_{1}}\mathcal{C}_{\phi_{1}X_{2}|\bar{Y}}$ concentrates to $\mathcal{C}^{-1/2}_{\phi_{1}\phi_{1}}\mathcal{C}_{\phi_{1}X_{2}|\phi_{\bar{y}}}$. Specifically, when $n\gg k+\log 1/\delta$, $\frac{1}{n_{2}}\|{\bm{E}}\|^{2}_{F}\leq 1.1\|\mathcal{C}^{-1/2}_{\phi_{1}\phi_{1}}\mathcal{C}_{\phi_{1}X_{2}|\phi_{\bar{y}}}\|^{2}_{F}\leq 1.1\epsilon^{2}_{\text{CI}}$ (by using Lemma A.3 ). Together we have $\|{\bm{E}}\bar{\bm{W}}\|_{F}\lesssim\epsilon_{\text{CI}}/\beta$.

Also, the noise term after projection satisfies $\|P_{[\Psi,{\bm{E}},{\bm{V}}]}{\bm{N}}\|\lesssim\sqrt{d_{2}(1+\log d_{2}/\delta)}\sigma$ as using Corollary A.6. Therefore $\Psi=\Psi^{*}-{\bm{E}}^{\text{pre}}={\bm{L}}+{\bm{E}}-{\bm{E}}^{\text{pre}}$.

Recall that $\hat{\bm{W}}=\operatorname*{arg\,min}_{{\bm{W}}}\|\psi({\bm{X}}_{1}^{\text{down}}){\bm{W}}-{\bm{Y}}\|_{F}^{2}.$ And with exactly the same procedure as Theorem D.1 we also get that:

With the proper concentration we also get:

Next we move on to the proof of our main result Theorem 4.2 where approximation error occurs.

The proof is a combination of Theorem 3.5 and Theorem D.8. We follow the same notation as in Theorem D.8. Now the only difference is that an additional term $a({\bm{X}}_{1}^{\text{down}})$ is included in ${\bm{Y}}$:

From re-arranging $\frac{1}{2n_{2}}\|{\bm{Y}}-\Psi\hat{\bm{W}}\|_{F}^{2}\leq\frac{1}{2n_{2}}\|{\bm{Y}}-\Psi\bar{\bm{W}}\|_{F}^{2}$,

Then with similar procedure as in the proof of Theorem 3.5, and write $\Psi$ as $\phi(X_{1}^{\text{down}})\bm{B}$, we have:

D.5 Principal Component Regression

Due to the property of PCA, $\|\bm{A}_{r}-\bm{A}\|_{F}\leq\|{\bm{E}}\|_{F}$ and $\|\bm{A}_{r}-\bm{A}\|_{2}\leq\|{\bm{E}}\|_{2}$.

Similarly we have $\|\bm{A}_{r}-{\bm{L}}\|_{F}\leq 2\|{\bm{E}}\|_{F}$. ∎

This technical fact could be used to complete the proof for Remark 4.1.

Recall $\Psi^{*},{\bm{L}},{\bm{E}},{\bm{V}}$ are defined as follows:

$\Psi^{*}:=\psi^{*}({\bm{X}}_{1}^{\text{down}})$ is the optimal representation matrix. $\Psi_{r}$ is the features obtained from $r$-PCA of $\Psi^{*}$. $\Psi^{*}={\bm{L}}+{\bm{E}}$ which is low rank plus small norm. (${\bm{L}}=\phi({\bm{X}}_{1}^{\text{down}})\mathcal{C}^{-1}_{\phi_{1}\phi_{1}}\mathcal{C}_{\phi_{1}\phi_{\bar{y}}}\mathcal{C}_{\phi_{\bar{y}}}^{-1}\mathcal{C}_{\phi_{\bar{y}}X_{2}}$ and ${\bm{E}}=\phi({\bm{X}}_{1}^{\text{down}})\mathcal{C}^{-1}_{\phi_{1}\phi_{1}}\mathcal{C}_{\phi_{1}X_{2}|\bar{Y}}$. Suppose $r=|\mathcal{Y}||\mathcal{Z}|$.) Let ${\bm{V}}=f^{*}({\bm{X}}_{1}^{\text{down}})\equiv f^{*}_{\mathcal{H}_{1}}({\bm{X}}_{1}^{\text{down}})\equiv\phi({\bm{X}}_{1}^{\text{down}})\mathcal{C}^{-1}_{\phi_{1}}\mathcal{C}_{\phi_{1}Y}={\bm{L}}\bar{\bm{W}}$ be our target direction, where $\bar{\bm{W}}:={\bm{\Sigma}}_{X_{2}\phi_{\bar{y}}}^{\dagger}{\bm{\Sigma}}_{\phi_{\bar{y}}Y}$.

Due to representation learning error (finite sample in the first stage) and approximate conditional independence, the target direction ${\bm{V}}$ is not perfectly linear in $\Psi^{*}$ or its $r$-PCA features $\Psi$.

Now with PCR we learn the linear model with $\hat{\bm{W}}\leftarrow\operatorname*{arg\,min}_{{\bm{W}}}\|\Psi_{r}{\bm{W}}-{\bm{Y}}\|_{F}^{2}.$ Together with D.9 and the same procedure as Theorem D.8 we also get that:

Let $\bar{\bm{E}}={\bm{L}}-\Psi_{r}$ is of rank at most $2r$.

With concentration on the downstream labeled samples we also get the result in Remark 4.1:

Appendix E Omitted Proofs Beyond Conditional Independence

The upper bound for $1/\beta$ can be computed as follows

Appendix F Omitted Proofs on Learning the Conditional Distribution

Representation operator $\mathcal{T}:L^{2}(X_{2})\rightarrow L^{2}(X_{1})$,

Low rank approximation operator $\mathcal{L}:L^{2}(X_{2})\rightarrow L^{2}(X_{1})$,

Under conditional independence $X_{1}\bot X_{2}|Y,\mathcal{T}=\mathcal{L}.$

From the definition of $\mathcal{L}$ we can decompose it into the following two operators $\mathcal{L}=\mathcal{B}\circ\mathcal{A}$:

Operator that measures conditional independence: $\mathcal{E}:=\mathcal{T}-\mathcal{L},$

When we set $g_{y}(x_{2})=\mathcal{A}^{\dagger}\circ 1(Y=y)$, we have the following corollary:

In the same setting of Theorem F.1, suppose the $(k-1)$-th maximal correlation between $X_{2}$ and $Y$ is not zero, then we have:

Next we present the proof of Theorem F.1, Corollary 6.2 and Corollary 6.3.

F.2 Proof of Theorem F.1

The joint distribution $p_{X_{1},X_{2}}(x_{1},x_{2})$ satisfies:

Let functions $w_{1,y}(x_{1})=1(g_{1}^{*}(x_{1})=y)\in L^{2}(\mathcal{X}_{1})$, and $w_{2,y}(x_{2})=1(g_{2}^{*}(x_{2})=y)\in L^{2}(\mathcal{X}_{2}),\forall y\in[k]$. Then we have that:

First we show that $\|\mathcal{T}\|_{op}:=\max_{u\neq 0}\frac{\|\mathcal{T}u\|_{L^{2}(X_{1})}}{\|u\|_{L^{2}(X_{2})}}\leq 1$. For any $u\in L^{2}(R^{d})$, we have that

Second, let $u(x_{2})\equiv 1$ and $v(x_{1})\equiv 1$, we have $\int_{x_{1}}T(x_{1},x_{2})u(x_{2})dx_{2}=1=v(x_{1}).$ Therefore we have $\|Tu\|_{L^{2}(X_{1})}=1$ for $u=1$ and $\|u\|_{L^{2}(X_{2})}=1$. Therefore $\|T\|_{{\text{op}}}=1$. ∎

Let $w_{1,y},w_{2,y},\forall y\in[k]$ be the same from Lemma F.3. Then we have:

Therefore $\sum_{y}\|\mathcal{L}w_{2,y}-w_{1,y}\|^{2}\leq 4\alpha.$

Therefore $\sum_{y}\langle\mathcal{L}w_{2,y},w_{1,y}\rangle\geq 1-2\alpha$. $\sum_{y}\|\mathcal{L}w_{2,y}-w_{1,y}\|^{2}=\sum_{y}(\|\mathcal{L}w_{2,y}\|^{2}+\|w_{1,y}\|^{2}-2\langle w_{1,y},\mathcal{L}w_{2,y}\rangle)\leq 2-2(1-2\alpha)=4\alpha$. ∎

Let $T_{k}(x_{1},x_{2})$ be the rank-$k$ approximation of $T(x_{1},x_{2})$, i.e., $T_{k}(x_{1},x_{2})=\sum_{i=1}^{k}\sigma_{i}u_{i}(x_{1})v_{i}(x_{2})$, where $u_{i}\in L^{2}(\mathcal{X}_{1}),v_{i}\in L^{2}(\mathcal{X}_{2})$. Then with the same definition of $w_{1,y}$ and $w_{2,y}$ as Claim F.3, we have that:

where $\lambda_{k+1}$ is the ($k+1$)-th singular value of $\mathcal{T}$, i.e., the $k$-th maximal correlation between $X_{1}$ and $X_{2}$

Write the full decomposition of $T$ as $T(x_{1},x_{2})=\sum_{i=1}^{\infty}\lambda_{i}u_{i}(x_{1})v_{i}(x_{2})$. We have that:

Therefore $\sqrt{\sum_{y}\|\mathcal{T}w_{2,y}\|^{2}}\geq 1-2\alpha.$

Therefore $\sum_{y}\|P_{\mathcal{T}_{k}}w_{2,y}\|^{2}\geq\frac{(1-2\alpha)^{2}-\lambda_{k+1}^{2}}{1-\lambda_{k+1}^{2}}$ and

Therefore $\sum_{y}\|\mathcal{T}_{k}w_{2,y}-w_{1,y}\|^{2}\leq\frac{16\alpha}{1-\lambda_{k+1}^{2}}$. ∎

Therefore the second term is in Theorem F.1 and it remains to prove that the first term is small.

With Theorem F.1 and we take $g_{y}(x_{2})=w_{2,y}(x_{2})=1(g_{2}^{*}(x_{2})=y),\forall y\in[k]$ as in Lemma F.5. We only need to upper bound

Altogether we have the approximation error is upper bounded by $O(\frac{\alpha}{1-\lambda_{k}^{2}})$.

Appendix G General Results and Comparison to [62]

We now show a more general form of our results and also connect the multi-view redundancy assumption from to ours.

We first note that all our results hold for a generalized version of Assumption 4.1 and Definition 4.1 that we state below.

Suppose $\bar{Y}$ with $|\bar{Y}|\leq m$ is a discrete latent variable that satisfies

$\bar{Y}$ makes $X_{1}$ and $X_{2}$ approximately CI as in Definition 4.1, i.e.

$\bar{Y}$ also makes $X_{1}$ and $Y$ approximately CI with

${\bm{\Sigma}}_{\phi_{\bar{y}}X_{2}}\text{ is full column rank and }\|{\bm{\Sigma}}_{Y\phi_{\bar{y}}}{\bm{\Sigma}}_{X_{2}\phi_{\bar{y}}}^{\dagger}\|_{2}=1/\beta$, where $A^{\dagger}$ is pseudo-inverse, and $\phi_{\bar{y}}$ is the one-hot embedding for $\bar{Y}$.

Note that our assumptions from the main paper are a special case of Assumption G.1, with $\epsilon_{\bar{Y}}=0$ being satisfied automatically as $\bar{Y}=[Y,Z]$ is explicitly defined to contain $Y$ in it. Unlike Assumption 4.1, we do not need $Y$ to be a discrete variable, but just need $\bar{Y}$ to be discrete. We state the generalization of Theorem 4.2 below

G.2 Comparison to [62]

We show guarantees for our algorithm under the assumption from in the following special case that satisfies: (1) $X_{1}$ and $X_{2}$ are exactly CI given $\bar{Y}$ (thus $\epsilon_{\text{CI}}=0$), (2) the variation in the target $Y$ is small given $X_{1}$ and $X_{2}$. The assumption from , in our setting, is equivalent to saying that $\epsilon_{X_{1}}$ and $\epsilon_{X_{2}}$ are small, where

A similar assumption of multi-view redundancy also appears in ; however they state it in terms of information-theoretic quantities instead. We will show that these assumptions are also almost sufficient to show results in our setting. In particular we show that if $Y|X_{1},X_{2}$ is almost deterministic (which makes sense for a many regression tasks) and if $\epsilon^{2}_{X_{2}}$ is small, then $\epsilon_{\bar{Y}}$ defined in the previous subsection will be small and thus we have meaningful guarantees.

Let $\sigma^{2}_{Y}=\textrm{Var}[Y|X_{1},X_{2}]$ be the variance of $Y$. $\bar{Y}$ is as defined in Assumption G.1 with the extra condition that $X_{1}$ and $X_{2}$ are exactly CI given $\bar{Y}$. Then we have

Plugging this into Theorem G.1 will give us the desired result. Note however that we did not even use the fact that $\epsilon_{X_{1}}$ is small. Using this part of the assumption, we can get an even stronger result that shows that even though our learned representation will only $X_{1}$, if will still predict $Y|X_{1},X_{2}$ well.

Thus we see that the assumption from is strong enough for us to be able to show stronger results than just our assumption. We complete this section by proving Lemma G.2

We will also make use of the following lemma that is easily proved using Cauchy-Schwarz inequality

The proof follows from the following sequence of inequalities that uses Jensen’s inequality, conditional independence of $X_{1}$ and $X_{2}$ and the above lemma. For simplicity we assume that $Y$ is a scalar random variable, the proof is the same for vector values $Y$, except squared values will replaced by norm squared values.

Thus using the above lemma, we get the desired upper bound on $\epsilon_{\bar{Y}}$. ∎

Appendix I Theoretical analysis for classification tasks

We now consider the benefit of learning $\psi$ from a class $\mathcal{H}_{1}$ on linear classification task for label set $\mathcal{Y}=[k]$. The performance of a classifier is measured using the standard logistic loss

We assume that the optimal regressor $f^{*}_{\mathcal{H}_{1}}$ for one-hot encoding also does well on linear classification.

For a fixed $\delta\in(0,1)$, under the same setting as Theorem 4.2 and Assumption I.1, we have:

We simply follow the following sequence of steps

Appendix J Four Different Ways to Use CI

In this section we propose four different ways to use conditional independence to prove zero approximation error, i.e.,

Write ${\bm{\Sigma}}$ as the covariance matrix for the joint distribution $P_{X_{1}X_{2}Y}$.

When conditional independence is satisfied, $\bm{A}$ is block diagonal matrix, i.e., $\bm{A}_{12}$ and $\bm{A}_{21}$ are zero matrices.

where ${\bar{\rho}}_{i}=\rho_{i}\bm{B}^{-\frac{1}{2}}$ for $i\in\{1,2\}$. Also,

First using ${\bm{\Sigma}}{\bm{\Sigma}}^{-1}=I$, we get the following identities

From Equation (26) we get that ${\bm{\Sigma}}_{XY}=-{\bm{\Sigma}}_{XX}\rho\bm{B}^{-1}$ and plugging this into Equation (24) we get

We now make use of the following expression for inverse of a matrix that uses Schur complement: ${\bm{M}}/\alpha=\delta-\gamma\alpha^{-1}\beta$ is the Schur complement of $\alpha$ for ${\bm{M}}$ defined below

For ${\bm{M}}=(\bm{A}-{\bar{\rho}}{\bar{\rho}}^{\top})$, we have that ${\bm{\Sigma}}_{XX}={\bm{M}}^{-1}$ and thus

This proves Equation (21) and similarly Equation (22) can be proved.

For the second part, we will use the fact that $({\bm{I}}-{\bm{a}}\bm{b}^{\top})^{-1}={\bm{I}}+\frac{1}{1-{\bm{a}}^{\top}\bm{b}}{\bm{a}}\bm{b}^{\top}$. Thus

The other statement can be proved similarly. ∎

J.2 Closed form of Linear Conditional Expectation

Refer to Claim B.1 and proof of Lemma B.2. As this is the simplest proof we used in our paper.

J.3 From Law of Iterated Expectation

It’s easy to see that to learn $f^{*}$ from representation $\psi$, we need $A$ to have some good property, such as light tail in eigenspace, and $B$ needs to be full rank in its column space.