PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jason D. Lee, Qi Lei, Nikunj Saunshi, Jiacheng Zhuo

arXiv:2008.01064v2cs.LGstat.ML

TL;DR

The paper asks why predicting known information in self-supervised learning helps downstream prediction. It uses approximate conditional independence to analyze reconstruction-based methods and nonlinear CCA, proving useful representations and downstream sample-complexity benefits.

  • Problem

    The principles explaining why self-supervised pretext tasks help downstream prediction remain unclear, despite their broad use.

  • Method

    The paper analyzes reconstruction-based self-supervised learning under approximate conditional independence and extends the analysis to nonlinear CCA.

  • Results

    The analysis provides generalization guarantees, including representations that can almost linearly separate downstream tasks and topic-modeling sample complexity of O(k).

  • Takeaways & Limitations

    Approximate conditional independence is a sufficient condition for useful pretext tasks, supported by experiments on simulated, computer-vision, and NLP data.

  • Takeaways & Limitations

    The guarantees require approximate conditional independence and, in one formulation, a dimensional restriction d2 ≥ km.

Abstract

from arXiv · show

Self-supervised representation learning solves auxiliary prediction tasks (known as pretext tasks) without requiring labeled data to learn useful semantic representations. These pretext tasks are created solely using the input features, such as predicting a missing image patch, recovering the color channels of an image from context, or predicting missing words in text; yet predicting this \textit{known} information helps in learning representations effective for downstream prediction tasks. We posit a mechanism exploiting the statistical connections between certain {\em reconstruction-based} pretext tasks that guarantee to learn a good representation. Formally, we quantify how the approximate independence between the components of the pretext task (conditional on the label and latent variables) allows us to learn representations that can solve the downstream task by just training a linear layer on top of the learned representation. We prove the linear layer yields small approximation error even for complex ground truth function class and will drastically reduce labeled sample complexity. Next, we show a simple modification of our method leads to nonlinear CCA, analogous to the popular SimSiam algorithm, and show similar guarantees for nonlinear CCA.

1 Introduction

The paper explains why reconstruction-based self-supervised learning can produce useful representations: approximate conditional independence lets pretext prediction implicitly encode downstream labels and latent variables. It develops generalization guarantees, analyzes topic modeling and nonlinear CCA, and validates the theory experimentally.

  • Core intuition: Approximate conditional independence between pretext components lets predicting X2 from X1 implicitly encode Y and latent variables Z, enabling downstream prediction through the learned representation.The intuition is that X2 can be predicted from Y with limited information about X1 once Y is known.
  • Theoretical guarantees: The paper provides generalization guarantees under approximate conditional independence, including small representation error and small estimation error for downstream predictors.The learned representation can almost linearly separate downstream classes, while the downstream predictor requires very few labeled samples.
  • Reconstruction-based SSL: The analysis focuses on reconstruction-based methods and instantiates its bounds in topic modeling, where two document halves serve as the pretext components.An appropriate approximate conditional independence assumption can support downstream learning even with potentially infinite mixtures of underlying topics.
  • Nonlinear CCA: A variant connected to SimSiam yields nonlinear canonical correlation analysis, which the paper relates to alternating conditional expectation and conditional-distribution decomposition.This extends the analysis beyond reconstruction-based objectives to a nonlinear CCA method for self-supervised learning.
  • Empirical validation: The paper quantifies approximate conditional independence using a partial covariance matrix, derives a risk bound scaling linearly with it, and tests the bound in simulations and real-world images.Experiments also find benefits when conditional independence is approximately enforced in text and show that a pretext-task linear model performs at least as well as many baselines on images.

2 Preliminary

This section defines the notation, variables, and two-step self-supervised learning procedure used throughout the paper. It also separates downstream performance into approximation error, measuring expressivity, and estimation error, measuring sample complexity.

  • Problem setup: The framework uses X1 as the pretext-task input, X2 as its target, and Y as the downstream label, with specified domains and joint distribution.For finite labels, Y is represented using one-hot encoding.
  • Learning procedure: Step 1 learns a representation ψ(x1) close to the best predictor of X2 from X1 within a setting-specific function class H.The target representation is ψ* := arg ming∈H E∥X2 − g(X1)∥2.
  • Learning procedure: Step 2 fits a linear regression of Y on ψ(X1), producing f(·) = EL[Y |ψ(·)].The downstream weights minimize expected squared prediction error over X1 and Y.
  • Performance measures: Approximation error measures whether Y is linearly predictable from ψ by comparing Wψ(X1) with the optimal predictor f* := E[Y |X1 = x1].It quantifies downstream expressivity in the infinite-sample limit.
  • Performance measures: Estimation error measures downstream sample complexity using n2 i.i.d. samples and excess risk from linear regression on the learned representation.The excess risk incorporates both approximation and estimation errors.

3 Guaranteed recovery with conditional independence

Under conditional independence X1⊥X2|Y, the optimal reconstruction representation can make downstream prediction linear, even when the original target function is nonlinear. With suitable rank and concentration assumptions, this preserves approximation error while reducing labeled-data requirements to depend on the number of classes k rather than feature complexity.

  • General conditional independence: Conditional independence lets the optimal representation ψ*(x1) = E[X2|X1 = x1] encode information about Y|X1 so that downstream prediction is linear in ψ*.When A_y,: = E[X2|Y = y] has rank k = |Y|, the approximation error is eapx(ψ*) = 0, even if f* is nonlinear in x1.
  • General conditional independence: The rank-k condition on E[X2|Y] ensures that the pretext target captures information from every prediction class without requiring Y to be linear in X2.The representation may improve on X2 by ignoring information irrelevant to downstream prediction.
  • Linear function class: For a linear function class ψ(x1) = Bφ1(x1), the optimal representation has a closed-form covariance solution, ψ*(x1) = ΣX2φ1Σφ1φ1^-1φ1(x1).The expression is the optimal function in the restricted linear class H1.
  • Linear function class: Under CI and the rank-k condition, the learned linear representation preserves the original features’ approximation error: eapx(ψ*) = eapx(φ1).Because ψ* is linear in φ1, it cannot have smaller approximation error, while CI ensures it has the same approximation error and better sample complexity.
  • Sample complexity: O(k) labels are sufficient with SSL, reducing the label requirement from complexity for D1 to O(k) when n2 ≫ ρ4(k + log(1/δ)).The guarantee assumes the optimal representation is learned perfectly and satisfies the stated subgaussian concentration condition.

4 Beyond conditional independence

Section 4 extends the framework from exact to approximate conditional independence, allowing latent variables Z and quantifying residual dependence through ε_CI. Under these conditions, SSL representations support downstream linear prediction with estimation error plus approximation terms, while reducing labeled sample complexity to Õ(km).

  • Finite-sample SSL: The finite-sample method learns a representation from n1 unlabeled pretext samples, then fits a linear classifier using n2 labeled downstream samples.The analysis considers linear representations H1 and universal-approximation spaces Hu.
  • Approximate conditional independence: Approximate conditional independence permits latent variables Z and measures the remaining dependence between X1 and X2 conditional on [Y, Z] through ε_CI.Exact conditional independence implies ε_CI = 0, and the definition differs according to whether the representation space is H1 or Hu.
  • Excess-risk bound: Theorem 4.2 bounds downstream excess risk under approximate conditional independence, sufficiently large n1 and n2, and controlled pretext prediction error.The resulting error includes finite-sample estimation and approximation contributions from ε_CI and ε_pre.
  • Excess-risk bound: The learned representation is approximately low rank: high-signal features associated with Y and Z enable linear downstream learning, while ε_CI and ε_pre contribute approximation error.Keeping the top km principal components further improves the excess-risk bound.
  • Sample complexity: Õ(km) labeled samples suffice under approximate conditional independence, compared with complexity scaling in H for traditional supervised learning with complicated models.This reduction is attributed to learning the representation from unlabeled data and then solving the downstream task with a linear layer.

5 Example: Topic Modeling

The topic-model example instantiates reconstruction-based self-supervised learning by predicting one document half from the other using normalized bag-of-words representations. Conditional independence given the latent topic mixture enables the framework’s guarantees, including O(k) downstream sample complexity.

  • Topic-model setup: Documents are generated from latent topic mixtures, with each topic represented by a vocabulary distribution collected in matrix A.A document samples a topic mixture, then independently samples topics and words from the corresponding topic distributions.
  • Reconstruction SSL: Reconstruction SSL splits each document into two halves and learns ψ(X1) to predict X2 using normalized bag-of-words vectors.The representation class is ψ(·) = Bφ1(·), and training minimizes ||ψ(X1) − X2||2.
  • Downstream task: The downstream target is linear in the document’s posterior topic mixture, with zero-mean σ2-subgaussian noise.The target is Y = w⊤E[µ|X] + N, and prediction error is measured in expectation against the optimal conditional-mean predictor.
  • Theoretical guarantee: Words are conditionally independent given the topic mixture, yielding X1 ⊥ X2 | µ and enabling the framework to bound its dependence parameters.The example uses the topic-model generative process to establish appropriate bounds for ϵCI and β in Theorem 4.2.
  • Theoretical guarantee: O(k) samples suffice for the downstream task under the topic-model corollary’s resulting upper bound.The corollary identifies a latent variable making the conditional-independence error zero and the conditional expectation linear in its posterior.

6 Conditional distribution decomposition: SimSiam, CCA, ACE

This section connects SimSiam, nonlinear CCA, and ACE through conditional-distribution decomposition. It shows that generalized ACE is equivalent to nonlinear CCA and that the resulting representations retain downstream guarantees, including under small Bayes error.

  • Connection between SimSiam, CCA, and ACE: The analysis connects SimSiam with nonlinear CCA between paired views and with the ACE algorithm for decomposing the conditional distribution of X2 given X1.The paired variables X1 and X2 are jointly distributed views, such as randomly augmented images.
  • Connection between SimSiam, CCA, and ACE: Instead of selecting a fixed target transformation η(X2), the method can jointly learn η that is readily predictable from X1, capturing negative-sample-free SimSiam.The formulation uses learned representation functions on both views and normalization to prevent collapse.
  • Guarantees for nonlinear CCA: Theorem 6.1 and its corollaries provide approximation and generalization guarantees for nonlinear CCA representations, including guarantees when the Bayes error is small.The bounds depend on the learned representation’s cross-view correlations and extend to finer-grained labels by replacing Y with [Y, Z].
  • ACE and operator decomposition: Generalized ACE with k-dimensional vector-valued functions solves the (k + 1)-SVD of the conditional-expectation operator, whose top singular vectors are constant functions.The zero-mean constraints remove the constant top singular component, leaving the subsequent singular vectors for the representation coordinates.
  • ACE and operator decomposition: The generalized ACE objective is equivalent to nonlinear CCA, so calculating the operator’s SVD corresponds to conducting alternating conditional expectation.The equivalence is stated both as a proposition and in the section summary.

7 Experiments

Experiments test the claim that self-supervised learning performs well when approximate conditional independence is satisfied, using synthetic simulations and a Yearbook computer-vision task. Results show excess risk follows the predicted dependence on label cardinality and conditional-independence error, while the representation is also evaluated against direct learning from image inputs.

  • Simulations: Synthetic Gaussian-mixture simulations vary label cardinality k and approximate conditional independence ϵCI under linear and universal function classes.Labels are sampled uniformly from {1, ..., k}; the linear setting uses identity features, while the universal setting uses ψ*=E[Y|X1].
  • Simulations: With d1=50, d2=40, n1=4000, and n2=1000, MSE scales linearly with k and with ϵCI for the linear function class.The result is reported as consistent with Theorems 3.5 and 4.2.
  • Simulations: For the universal function class, the same phenomenon appears when predicting Y from X1 with RBF-kernel linear regression as the baseline.The experiments use the same parameter settings and report verification of Theorems 3.2 and 4.2 with Hu.
  • Computer Vision Task: The Yearbook task evaluates whether learning from ψ outperforms learning directly from X1 without enforcing conditional independence.Portrait dates YD range from 1905 to 2013; images are resized to 128×128, with the central 64×64 face treated as X2 and the outer rim as X1.

8 Conclusion … A.3 Technical Facts for Matrix Concentration

The paper establishes that approximate conditional independence can make self-supervised pretext tasks beneficial for downstream learning, with theoretical and experimental support. Its appendices connect conditional independence to partial covariance and collect Gaussian, sub-Gaussian, projection, and Bernstein concentration facts used in the analysis.

  • 8 Conclusion: Approximate conditional independence is a sufficient condition for downstream sample-complexity benefits from self-supervised learning, supported by simulated, computer-vision, and natural-language experiments.The authors leave investigation of other sufficient conditions for useful pretext tasks to future work.
  • A.1 Relation of Inverse Covariance Matrix and Partial Correlation: Partial covariance is defined as the covariance of residuals after predicting X from Y, written ΣXX·Y = cov(X − E[L[X|Y]], X − E[L[X|Y]]).The appendix introduces this relation for covariance matrices of jointly distributed variables.
  • A.2 Relation to Conditional Independence: Conditional independence X1⊥X2|Y implies zero partial covariance between X1 and X2 given Y.The appendix states this as Fact A.1 and relates it to an adapted characterization of conditional independence.
  • A.2 Relation to Conditional Independence: For arbitrary feature maps, conditional independence yields mean-zero residual features after conditioning on the one-hot encoding of Y.The residuals are defined as φ̄1(X1) = φ1(X1) − E[φ1(X1)|φy(Y)] and analogously for φ̄2(X2).
  • A.3 Technical Facts for Matrix Concentration: For Gaussian samples, covariance concentration applies when n ≫ k + log(1/δ), for a rank-k matrix B independent of X, with probability at least 1 − δ.The claim assumes each xi ∼ N(0, ΣX).
  • A.3 Technical Facts for Matrix Concentration: For ρ^2-sub-Gaussian samples, the analogous concentration claim assumes n ≫ ρ^4(k + log(1/δ)) for a rank-k matrix B independent of X.The stated probability guarantee is at least 1 − δ.
  • A.3 Technical Facts for Matrix Concentration: For a Gaussian matrix Z and a rank-d projection P, projected column norms follow χ^2(d) concentration and a union bound yields the stated probability guarantee.Each column is sampled from a Gaussian distribution, and the projection result is combined across columns using δ′ = δ/k.
  • A.3 Technical Facts for Matrix Concentration: The appendix also invokes vector Bernstein inequality to bound projections of matrices with independent mean-zero sub-Gaussian rows.The proof decomposes the projection using an orthogonal basis, establishes zero means, and applies a union bound to obtain the projection norm bound.

B Warm-up: jointly Gaussian variables · C Omitted Proofs with Conditional Independence · C.1 Omitted Proof for General Random Variables

Under joint Gaussianity and conditional independence, the learned representation exactly supports linear downstream prediction and reduces labeled sample complexity from approximately O(d1) to O(k). The omitted proofs extend this exact-representation and estimation-error analysis to latent-variable conditional independence and general random variables.

  • B Warm-up: jointly Gaussian variables: Under joint Gaussianity and conditional independence, the optimal downstream predictor is exactly linear in the learned representation.The approximation error is 0 when ΣX2Y has rank k.
  • B Warm-up: jointly Gaussian variables: The rank condition on ΣX2Y ensures X2 captures every information direction of Y, while the representation selects sufficient features for predicting Y.Full column rank implies E[X2|Y] has rank k.
  • B Warm-up: jointly Gaussian variables: The learned linear predictor requires n2 ≫ k + log(1/δ) pretext-task samples to achieve the stated excess-risk guarantee with probability at least 1 −δ.The theorem’s sample requirement depends on k rather than the full input dimension.
  • B Warm-up: jointly Gaussian variables: Self-supervised learning reduces labeled sample complexity from approximately O(d1) to approximately O(k) compared with directly predicting Y from X1.The reduction follows because the downstream task uses the lower-dimensional learned representation.
  • B Warm-up: jointly Gaussian variables: With latent variables Z and conditional independence given (Y, Z), the approximation error remains 0 and the estimation guarantee generalizes by replacing k with k + m.The latent-variable assumption requires ΣX2 ¯Y to have rank k + m, where ¯Y = [Y, Z].
  • C Omitted Proofs with Conditional Independence: The omitted Gaussian proofs derive exact prediction by using the left inverse of ΣX2Y to express E[Y|X1] as a linear function of the representation.This establishes that there is no approximation error in using ψ to predict Y.
  • C.1 Omitted Proof for General Random Variables: For general random variables, the representation combines the conditional label distribution f(x1) with class-conditional means of X2, and a rank-|Y| pseudoinverse recovers f(x1) exactly.The construction uses A_y,: = E[X2|Y = y] and B = A† with BA = I.
  • C.1 Omitted Proof for General Random Variables: The general-random-variable proof then transfers the zero approximation error to estimation bounds using centered noise, a k-dimensional projection, and a sample condition n ≫ ρ^4(k + log(1/δ)).The noise rows are independent samples from a centered distribution with E[∥N∥2|X1] ≤ σ2.

C.2 Omitted proof of linear model with approximation error … D.3 Omitted Proof in General Setting

The omitted proofs extend the paper’s guarantees from approximate linear reconstruction to practical encoder representations and broader dependence settings. They formalize conditional dependence with covariance operators and show how universal feature maps support the general result.

  • C.2 Omitted proof of linear model with approximation error: The linear-model proof decomposes Y into approximation error, a linear target component, and mean-zero noise before transferring empirical loss to excess risk.It uses conditional independence to express the linear target through the learned feature representation.
  • C.3 Argument on Denoising Auto-encoder or Context Encoder: Because deterministic transformations preserve conditional independence, downstream prediction may use transformed learned representations rather than the original reconstruction output.The remark specifically allows replacing X2 with h(X2), including decoder inverses in denoising auto-encoders or context encoders.
  • C.3 Argument on Denoising Auto-encoder or Context Encoder: For encoder-only representations, the reconstruction analysis gives ϵpre ≤ L√ϵ when reconstruction error is at most ϵ and the inverse decoder has Lipschitz constant L.This explains why optimizing the reconstruction objective can yield a representation E*(X1) suitable for downstream tasks.
  • D.1 Warm-up: Jointly Gaussian Variables: The general-setting extension introduces approximate conditional independence of X1 and X2 given both the label Y and latent variable Z.In the Gaussian warm-up, departures from exact conditional independence contribute approximation error through the conditional cross-covariance.
  • D.1 Warm-up: Jointly Gaussian Variables: The Gaussian analysis bounds the representation error from conditional dependence by a term proportional to ϵCI/β.The proof identifies the conditional covariance contribution E and combines it with the target-direction analysis.
  • D.2 Measuring conditional dependence with cross-covariance operator: Cross-covariance operators generalize covariance matrices to feature spaces, and their Hilbert-Schmidt norm quantifies approximate conditional independence.With one-hot labels, exact conditional independence makes the relevant conditional cross-covariance operator vanish.
  • D.3 Omitted Proof in General Setting: For universal feature maps, the general result represents conditional expectations through covariance operators, while general feature maps yield the corresponding restricted formulation.Universality supplies density in the square-integrable function space, enabling the operator-based characterization.

D.4 Omitted Proof for Main Results … F.1 Introducing the Operators on the Hilbert Spaces

The appendices prove the main generalization results, analyze principal component regression, verify the topic-modeling example under exact conditional independence, and formulate Hilbert-space operators for conditional-distribution learning.

  • D.4 Omitted Proof for Main Results: Theorem D.8 establishes downstream generalization with probability 1 −δ in the no-approximation-error setting under Assumptions 4.1 and 3.2.The result assumes a linear operator A with f∗(X1) ≡ Aφ1(X1) and n1, n2 ≫ ρ4(d2 + log 1/δ).
  • D.4 Omitted Proof for Main Results: The proof decomposes representation error into conditional-independence, pretext-learning, and projected-noise terms, yielding ∥E W̄∥F ≲ ϵCI/β and a combined estimator bound.The combined bound is ∥Ψ Ŵ − V∥ ≤ 2∥E W̄∥ + 2∥Epre W̄∥ + ∥P[Ψ,E,V,Epre]N∥.
  • D.4 Omitted Proof for Main Results: With approximation error, Theorem 4.2 combines Theorems 3.5 and D.8 and adds the term a(Xdown1) to the downstream response.The proof controls the resulting regression error using the same decomposition strategy as Theorem 3.5.
  • D.5 Principal Component Regression: For A = L + E with rank(L) = r, rank-r PCA satisfies ∥Ar − L∥F ≤ 2∥E∥F and ∥Ar − L∥2 ≤ 2∥E∥2.This perturbation fact supports the proof of Remark 4.1 on principal component regression.
  • D.5 Principal Component Regression: PCR learns a linear model on r-PCA features, while finite-sample representation error and approximate conditional independence prevent the target direction from being perfectly linear.The resulting error is bounded by projected noise plus the low-rank approximation term ∥P[Ψr,L]N∥ + ∥ĒW̄∥.
  • E.1 Proof for topic modeling example: In the topic-modeling example, defining latent variable Ȳ from E[μ|X1] gives ϵCI = 0 because independently sampled words satisfy X1 ⊥ X2|μ.The proof also shows E[Y|X1] = w⊤E[Ȳ|X1], establishing the stated prediction relationship.
  • F.1 Introducing the Operators on the Hilbert Spaces: Section F.1 defines conditional-expectation operators on L2 spaces and uses an SVD of T to construct the representation ψ(x1) = [u1(x1), · · · uk(x1)].The operator B maps h to E[h(Y)|X1 = x1], while A† is the inverse operator of A.
  • F.1 Introducing the Operators on the Hilbert Spaces: The resulting representation is connected to the conditional label distribution, with y(x1) = P(Y = y|X1 = x1), and Corollary F.2 assumes nonzero maximal correlation.Theorem F.1 and Corollary F.2 restate the operator-based approximation and representation guarantees.

F.2 Proof of Theorem F.1 · G General Results and Comparison to [TKH20b]

The proof establishes the spectral properties and approximation bounds needed for Theorem F.1, including an O(α/(1−λ_{k+1}^2)) error bound. The following section generalizes the results and connects the multi-view redundancy assumption to the assumption in [TKH20b].

  • F.2 Proof of Theorem F.1: The representation ψ is formed from the left singular vectors of T_k, so every linear predictor ψ(x_1)^⊤w corresponds to T_k composed with some function on X_2.This correspondence is established through the singular-function expansion of T_k.
  • F.2 Proof of Theorem F.1: The top eigenvalue of T is 1, and its operator norm satisfies ∥T∥op = 1.The proof obtains the norm equality using the constant function and Jensen’s inequality.
  • F.2 Proof of Theorem F.1: The label-indicator functions satisfy a reconstruction discrepancy bounded by 4α under the approximate-independence condition.The displayed bound is Σ_y(∥Lw2,y∥2 + ∥w1,y∥2 − 2⟨w1,y,Lw2,y⟩) ≤ 4α.
  • F.2 Proof of Theorem F.1: The rank-k approximation T_k yields a total label-indicator error bounded by 16α/(1−λ_{k+1}^2).This bound controls Σ_y ∥T_kw2,y − w1,y∥2.
  • F.2 Proof of Theorem F.1: The next singular value obeys |λ_{k+1}| ≤ ϵCI because T decomposes as a rank-k operator L plus error E.The proof identifies λ_{k+1} as the (k + 1)-th singular value, or the k-th maximal correlation between X_1 and X_2.
  • F.2 Proof of Theorem F.1: Corollary F.2 follows by choosing g_i^* so that the second term in Theorem F.1 is zero, leaving only the first approximation term.The proof uses L = B ◦ A and identifies L ◦ A† ◦ 1(y = i) with E[Y = i|X_1].
  • F.2 Proof of Theorem F.1: The resulting approximation error is upper bounded by O(α/(1−λ_k^2)).This conclusion is obtained in the proof of Corollary 6.3 after selecting g_y(x_2) as the label-indicator function.
  • G General Results and Comparison to [TKH20b]: Section G presents a more general form of the results and connects the multi-view redundancy assumption to the assumption from [TKH20b].The passage introduces both the generalization and the comparison, while the latter is identified as a connection between assumptions.

G.1 General Results … J.4 From E[X2|X1, Y ] = E[X2|Y ]

The appendix generalizes the paper’s guarantees beyond discrete labels, compares them with multi-view redundancy assumptions, and extends the analysis to classification and several conditional-independence proofs. It also shows when predicting from X1 alone matches prediction from the full input and derives representations whose downstream targets are linearly recoverable.

  • G.1 General Results: The generalized latent-variable assumption permits discrete latent variables that approximately conditionally independent X1, X2, and Y, yielding a Theorem G.1 guarantee with an additional ϵ^2_Ȳ error term.Unlike the main assumption, Y itself need not be discrete; the latent variable Ȳ must be discrete and satisfy the stated rank condition.
  • G.2 Comparison to [TKH20b]: Under [TKH20b]’s stronger multi-view assumptions, the method obtains meaningful guarantees when Y|X1, X2 is nearly deterministic and ϵ^2_X2 is small.The assumptions include exact conditional independence of X1 and X2 given Ȳ and small conditional target variation.
  • H Showing E[Y |X1] ≈E[Y |X1, X2]: If the Bayes error of (X1, Y) is low, predicting E[Y|X1] is nearly as effective as predicting E[Y|X1, X2], with discrepancy controlled by 2k Bayes-error(PX1,Y).The comparison combines the SSL approximation bound with the Bayes-error bound from Lemma H.1.
  • I.1 Classification tasks: For classification, linear regression on one-hot targets over learned representations produces a linear classifier with a guarantee inherited from the SSL representation bound.The result assumes the best one-hot regressor in H1 already performs well under classification loss.
  • J Four Different Ways to Use CI: Conditional independence plus non-degeneracy implies that E[Y|X1] can be expressed as W E[X2|X1], establishing zero approximation error through four proof strategies.The appendix presents most arguments in the jointly Gaussian case and extends them by replacing variables with feature maps.
  • J.1 Inverse Covariance Matrix: The inverse-covariance argument shows that conditional independence makes the relevant covariance block matrix block diagonal, and E[Y|X1] lies in the same direction as E[X2|X1].The block structure follows from vanishing off-diagonal blocks in the inverse covariance matrix.
  • J.2 Closed form of Linear Conditional Expectation: The closed-form conditional-expectation proof is identified as the simplest proof used in the paper.The appendix refers to Claim B.1 and the proof of Lemma B.2 for this derivation.
  • J.3 From Law of Iterated Expectation: Without conditional independence, the learned representation has the form ψ(x1) = Ax1 + Bf*(x1), while conditional independence sets A = 0 and permits recovery when X2 retains sufficient information about Y.Recovery requires ΣX2Y|X1 to have rank matching the dimension of Y.

K More on the experiments

Additional simulations and vision/NLP experiments examine how sample sizes, conditional independence, and label informativeness affect downstream performance. The NLP results show that learned representations outperform the baseline, particularly with few labeled samples, and that exact conditional independence is superior to latent-variable conditioning.

  • Simulations: Excessive Risk varies with both pretext-task samples n1 and downstream-task samples n2 under strict conditional independence.The simulation fixes α = 0, k = 2, d1 = 50, and d2 = 40 while restricting the function class to linear models.
  • Computer Vision Task: Predicting gender has higher MSE than predicting dates, while conditioning on dates cancels more covariance spectrum than conditioning on gender.The reported norm is ∥Σ−1/2 X1X1ΣX1X2|YD∥F = 8.15; the authors infer that gender captures less dependence between X1 and X2, producing larger ϵCI and worse downstream performance.
  • NLP Task: On SST, learned ψ outperforms the bag-of-words baseline φ1 in both exact-label and latent-variable conditional-independence settings, especially with few labeled samples.The experiments evaluate binary sentiment classification using linear regression and linear classification; exact conditional independence performs better than conditioning with latent variables.
  • NLP Task: The NLP study simulates conditional independence by independently sampling two movie reviews from each sentiment class, or from fine-grained SST labels used as extra latent variables.The downstream task uses SST movie reviews with binary labels Y = {±1}, while the fine-grained labels are ¯Y = {1, 2, 3, 4, 5}.
Loading 2008.01064v2…