PaperlayerView exact revision on arXiv

Source-linked AI summary

Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss

Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, Tengyu Ma

arXiv:2106.04156v7cs.LGstat.ML

TL;DR

Existing theory for self-supervised learning has limited explanations of downstream adaptation because prior contrastive analyses assume conditionally independent views, unlike strongly correlated image augmentations. This paper defines a population augmentation graph and derives a contrastive loss from its spectral decomposition. Its main theorem guarantees small downstream classification error when the representation dimension exceeds the maximum number of disconnected subgraphs.

  • Problem

    Theory explaining downstream adaptation from self-supervised representations remains limited because prior contrastive analyses assume conditionally independent views, unlike strongly correlated natural-image augmentations.

    Source: §1 · pp. 1–2

  • Method

    The paper defines a population augmentation graph and proposes a contrastive loss motivated by spectral decomposition of that graph.

    Source: §1 · p. 4, §3.1 · p. 7

  • Results

    When representation dimension exceeds the maximum number of disconnected subgraphs, a linear classifier is guaranteed to achieve small downstream error.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The analysis indicates contrastive learning reduces downstream labeled-data needs, with labeled examples scaling linearly in representation dimension and dimension scaling linearly in graph cluster count.

    Source: §1 · p. 4

    The framework abstracts away optimization and does not capture the potential implicit bias of optimizers.

    Source: §7 · p. 19

Abstract

from arXiv · show

Recent works in self-supervised learning have advanced the state-of-the-art by relying on the contrastive learning paradigm, which learns representations by pushing positive pairs, or similar examples from the same class, closer together while keeping negative pairs far apart. Despite the empirical successes, theoretical foundations are limited -- prior analyses assume conditional independence of the positive pairs given the same class label, but recent empirical applications use heavily correlated positive pairs (i.e., data augmentations of the same image). Our work analyzes contrastive learning without assuming conditional independence of positive pairs using a novel concept of the augmentation graph on data. Edges in this graph connect augmentations of the same data, and ground-truth classes naturally form connected sub-graphs. We propose a loss that performs spectral decomposition on the population augmentation graph and can be succinctly written as a contrastive learning objective on neural net representations. Minimizing this objective leads to features with provable accuracy guarantees under linear probe evaluation. By standard generalization bounds, these accuracy guarantees also hold when minimizing the training contrastive loss. Empirically, the features learned by our objective can match or outperform several strong baselines on benchmark vision datasets. In all, this work provides the first provable analysis for contrastive learning where guarantees for linear probe evaluation can apply to realistic empirical settings.

1 Introduction

The paper introduces spectral contrastive learning to explain and analyze self-supervised representations when positive views are correlated, using the population augmentation graph rather than conditional independence assumptions. It proves linear-probe guarantees under graph-structure assumptions and extends them to finite samples, then reports competitive benchmark performance.

1 Introduction

  • Unlike prior analyses that assume views are conditionally independent given a label or hidden variable, this framework addresses correlated image augmentations that violate that assumption.The authors argue that conditioning on the natural image does not make prior analyses meaningfully applicable because it is too complex to serve as the hidden variable.Source: §1 · pp. 1–2
  • The framework uses within-class continuity: same-class examples may be connected by sequences of nearby natural images, with the property more salient when neighborhoods include varied augmentations.The population augmentation graph formalizes this continuity through connectivity among augmented examples.Source: §1 · p. 2
  • The graph assumptions allow disconnected subgraphs within a class and downstream classes that combine fine-grained graph components, unlike the exact alignment required by Wei et al. (2020).The framework avoids fitting discrete pseudolabels by learning continuous representations on unlabeled data.Source: §1 · p. 2
  • The method treats contrastive learning as parametric spectral clustering on the population augmentation graph and learns representations by minimizing a variant of the standard contrastive loss.Graph vertices are augmented data, with edges connecting augmentations of the same natural example; the assumptions limit graph partitions and cross-class edges.Source: §1 · pp. 2–3
  • Representations achieve small linear-classification error when their dimension exceeds the maximum number of disconnected augmentation-graph subgraphs, with polynomially many unlabeled samples and downstream labels linear in representation dimension.The required representation dimension grows with the number of graph clusters; the finite-sample unlabeled-data bound depends polynomially on model-family Rademacher complexity and other relevant parameters.Source: §1 · pp. 3–4
  • On standard vision benchmarks, the proposed loss’s features match or outperform several strong baselines under linear-probe evaluation.The algorithm does not rely on stop-gradient, which is essential to SimSiam (Chen and He, 2020).Source: §1 · p. 4

2 Additional related works

Prior work spans empirical self-supervised methods and theories that often assume conditional independence of positive pairs, while practical augmentations are highly correlated. This section relates the paper’s assumption to multi-step same-class mixing and distinguishes its approach from adjacent frameworks.

Empirical works on self-supervised learning.

  • Empirical methods use siamese networks, asymmetry to prevent collapse, or InfoNCE to attract views of the same data and repel views of different data (Grill et al., 2020; Chen and He, 2020; Oord et al., 2018).Many such methods learn features that benefit downstream tasks.Source: §2 · p. 4

Theoretical works on self-supervised learning.

  • Prior theoretical guarantees often assume conditionally independent positive pairs, whereas practical vision augmentations are highly correlated and may be independent only given complex hidden variables (Arora et al., 2019; Tosh et al., 2020, 2021).Reconstruction-based results also study conditional independence, approximate independence for Gaussian data, and weaker assumptions.Source: §2 · pp. 4–5
  • For small-Gaussian-noise augmentations in mixture-of-Gaussians or mixture-of-manifolds data, close positive pairs may require large representation dimension under Tosh et al. (2021), while reconstruction of x+ from x may not yield good features under Lee et al. (2020).The paper notes that Example 3.10 does not satisfy Lee et al.’s β requirement for the particular choice (X1, X2) = (x, x+), though another choice of X2 may address this.Source: §2 · p. 5
  • The paper’s assumption can be interpreted as a neighbor-sampling Markov chain mixing within a class before across the population, unlike prior works’ assumptions about independence of the first positive pair (Arora et al., 2019; Tosh et al., 2020, 2021).Roughly, some later iterates remain likely to share a label while becoming sufficiently independent conditioned on that label or a hidden variable; related augmentation Markov chains appear in Dao et al. (2019).Source: §2 · p. 5
  • Other analyses study task-relevant information, collapse avoidance, latent-variable recovery, or domain adaptation, while Cai et al. (2021) require ground-truth labels during training and this algorithm does not (Tsai et al., 2020; Tian et al., 2020b; Zimmermann et al., 2021).Cai et al. (2021) allow disconnected parts within each class under an expansion condition.Source: §2 · p. 5

Co-training and multi-view learning.

  • Co-training and multi-view learning use distinct feature views; expansion relaxes co-training’s conditional-independence requirement and is related to the paper’s assumption, though most such methods differ from neural contrastive vision methods.Markov chains on augmented data have also been used to study data augmentation (Dao et al., 2019).Source: §2 · pp. 5–6

Graph Laplacian regularization.

  • Graph Laplacian regularization smooths predictions on unlabeled data and is added to a supervised loss, whereas this paper uses the normalized adjacency matrix to define its unsupervised training objective.Source: §2 · p. 6

3 Spectral contrastive learning on population data

This section develops spectral contrastive learning on population augmentation graphs, connecting graph spectral embeddings to a neural objective and establishing linear-probe guarantees under class-separation and connectivity assumptions. It examines graph-partitioning and graph-size-independent guarantees and illustrates the theory with mixtures of manifolds under polynomially small augmentation noise.

3 Spectral contrastive learning on population data

  • The framework treats natural examples as belonging to deterministic ground-truth classes drawn from a population distribution, and evaluates representations by their best linear-probe error.The exposition assumes finite but exponentially large data spaces for convenience and notes an extension to infinite compact spaces under mild regularity conditions.Source: §3 · p. 6

3.1 Augmentation graph and spectral decomposition

  • The population augmentation graph weights pairs by their probability of arising from one natural example, and its leading eigenvectors provide embeddings with graph-like clustering structure.The analysis relies on the population graph rather than the nearly empty graph built from a finite empirical dataset.Source: §3.1 · pp. 7–8

3.2 From spectral decomposition to spectral contrastive learning

  • A neural feature function reparameterizes the spectral factorization objective as an equivalent spectral contrastive loss, while preserving linear-probe performance under the relevant embedding transformations.This parameterization makes the objective usable with neural representations rather than storing a separate embedding for every augmented datapoint.Source: §3.2 · pp. 8–9

3.3 Theoretical guarantees for spectral contrastive loss on population data

  • The guarantee assumes labels are recoverable from augmentations and, for the cluster-based bound, that the graph has at most m well-connected clusters; these conditions imply a spectral gap.Under the at-most-m-clusters assumption, γ2m ≤ 1 − Ω(ρ²/log m).Source: §3.3 · pp. 10–11
  • With k ≥ 2r and a realizable population-loss minimizer, the theorem bounds linear-probe error; when α = 0, it guarantees exact recovery.When k > 2m and the graph-connectivity term dominates α, the stated error term α/ρ2 is small.Source: §3.3 · pp. 11–12
  • Unlike graph-partitioning analyses that guarantee approximation ratios potentially dependent on graph size, the paper guarantees downstream linear-probe accuracy independently of graph size.The analysis uses the downstream labeling-function assumption and a technique characterizing the representations’ linear structure.Source: §3.3 · p. 12

3.4 Provable instantiation of Theorem 3.8 to mixture of manifold data

  • For Gaussian perturbations of a mixture of distributions on disjoint supports, the spectral parameter scales at least linearly with augmentation size and the subpopulation Cheeger constants.For spherical Gaussians with unit identity covariance, the Cheeger constant is Ω(1), yielding ρ ≳ σ.Source: §3.4 · p. 12
  • The mixture example allows labels to identify each generating component or merge components into fewer labels, while distance-based clustering does not apply in the stated setting.The latent within-class distance can be much larger than the distance between class means, which is assumed to be at least on the order of κ·√log d / √d.Source: §3.4 · p. 13
  • For k ≥ 2r + 2, the mixture-of-manifolds example satisfies Assumption 3.6 with α ≤ 1/poly(d), and Theorem 3.11 guarantees small downstream classification error even when σ is polynomially small.The example uses κ-bi-Lipschitz generators of Gaussian mixtures and permits downstream labels that merge mixture components, provided each component receives a single label.Source: §3.4 · p. 13

4 Finite-sample generalization bounds

The section extends spectral-contrastive learning guarantees to finite pretraining and labeled downstream samples. It bounds excess population loss, its effect on downstream error, and the sample complexity of learning a linear probe.

4.1 Unlabeled sample complexity for pretraining

  • When κ = O(1), achieving population-loss suboptimality ϵ requires O(k^4R/ϵ^2) unlabeled samples.Theorem 4.1 bounds the population loss of an empirical-loss minimizer relative to a population-loss minimizer using the feature class's Rademacher complexity.Source: §4.1 · p. 14
  • Under the stated spectral-gap assumptions, downstream error grows linearly with pretraining excess loss; for κ = O(1), unlabeled sample complexity is O(m^6R/ϵ^2ρ^4).The result uses a representation dimension k ≥ max{4r + 2, 2m}; approximate realizability is allowed at the cost of an additional linear-probe error term.Source: §4.1 · pp. 14–15

4.2 Labeled sample complexity for linear probe

  • Finite-sample end-to-end bounds separate downstream error into irreducible population, finite-pretraining, and finite-labeled-sample terms.The required sample sizes are npre = poly(k, d, R, 1/ϵ) and ndown = poly(r, k, 1/ϵ); downstream sample complexity does not depend on hypothesis-class complexity R.Source: §4.2 · pp. 15–16

5 Analysis Framework and Proof Sketch

The analysis reduces guarantees to a population result—small population pretraining loss yields a linear downstream classifier—and connects it to finite-sample training through capacity-controlled generalization. The proof sketch explains the population result using the augmentation graph’s top eigenvectors.

5 Analysis Framework and Proof Sketch

  • The framework’s core step shows that small population pretraining loss implies a linear classifier with small downstream loss.The remaining links from the population result to finite-sample guarantees use standard supervised-learning theory.Source: §5 · pp. 16–17
  • Finite-sample analysis links empirical and population pretraining losses through capacity bounds for parameterized feature families, not by requiring their augmentation graphs to resemble one another.The analysis assumes the model family can express the graph eigenfunctions or eigenvectors and has bounded Rademacher complexity.Source: §5 · pp. 16–17

5.1 Proof Sketch of Theorem 3.8

  • Spectral contrastive embeddings recover the top-k eigenvectors up to row scaling and rotation, so their span supplies a linear head approximating the Bayes labels.The higher-order Cheeger inequality supports a mean-squared error bound for this approximation.Source: §5.1 · pp. 17–18
  • In the binary proof sketch, the Bayes-label vector has limited graph-Laplacian energy because positive augmentation pairs rarely receive different labels, limiting its projection outside the top-k eigenvectors.The argument uses the small Bayes classification error assumption and the fact that the remaining eigenvectors have eigenvalues at least λ_k+1.Source: §5.1 · p. 18
  • The mean-squared approximation gives a classifier close in 0-1 error to the Bayes labels, and averaging predictions across a datapoint’s augmentations does not increase classification error.The proof converts the linear head’s approximation to a thresholded classifier and then considers predictions averaged over augmentations.Source: §5.1 · p. 18

6 Experiments

Experiments evaluate spectral contrastive learning with linear probes on benchmark vision datasets, reporting stronger results than SimCLR and SimSiam on smaller benchmarks and performance similar to other state-of-the-art methods on ImageNet.

Experiments

  • Training minimizes the empirical spectral contrastive loss and samples a fresh augmentation in each iteration.Source: §6 · p. 18

Results

  • The method does not rely on large batch sizes, momentum encoders, or stop-gradient, unlike the cited baseline approaches.The passage contrasts large batches with SimCLR, momentum encoders with BYOL and MoCo, and stop-gradient with SimSiam.Source: §6 · p. 19

Encoder / feature extractor

  • The encoder combines a ResNet backbone, a batch-normalized projection MLP, and a projection onto a sphere of radius √µ; linear evaluation trains a classifier on frozen global-average-pooling features.The projection MLP and projection function improved performance in the reported experiments.Source: §6 · p. 19

Results

  • Spectral contrastive learning outperforms SimCLR and SimSiam on CIFAR-10/100 and Tiny-ImageNet, and achieves similar performance to other state-of-the-art methods on ImageNet.The reported evaluations use linear probes; ImageNet results use 100-epoch pre-training.Source: Table 1 · p. 19, §6 · p. 19, Table 2 · p. 19

7 Conclusion

The paper presents a theoretical framework for self-supervised learning with provable guarantees for downstream linear classification. It abstracts away optimization effects to study pretraining losses and their interaction with population-data structure.

7 Conclusion

  • The framework provides provable guarantees for learned representations on downstream linear classification tasks.It abstracts away optimization effects to focus on pretraining losses and their interaction with population-data structure.Source: §7 · p. 19
  • The analysis captures model inductive bias but not the potential implicit bias of optimizers.Source: §7 · p. 19
  • Future work may design better pretraining losses and analyze finer-grained representation properties using advanced spectral graph theory techniques.The paper points to recent follow-up work by HaoChen et al. (2022) and Shen et al. (2022).Source: §7 · p. 19

A Experiment details · B Proofs for Section 3

The appendix specifies the spectral-contrastive training and linear-evaluation setup and outlines the proof sequence for Theorem 3.8.

A Experiment details

  • Algorithm 1 samples minibatches, draws two augmentations per example, updates the encoder to minimize L, and returns the encoder.The supplied pseudocode excerpts show these steps but omit other intermediate operations.Source: A Experiment details · p. 25
  • Table 3 is captioned as reporting top-1 accuracy under the linear evaluation protocol, identifying the metric and evaluation setting without specifying numerical results in the cited passage.Source: Table 3 · p. 25
  • CIFAR-10/100 use CIFAR ResNet18, while Tiny-ImageNet and ImageNet use ResNet50; projection MLPs have two layers for the former datasets and three for ImageNet.The hidden and output dimensions are 1000 for CIFAR-10/100 and Tiny-ImageNet, and 8192 for ImageNet; µ is 10 for ImageNet and 1, 3, or 10 for the other datasets.Source: A Experiment details · p. 25
  • Encoder training uses momentum SGD with a cosine-decayed learning rate from 0.05, with dataset-specific weight decay, epochs, batch sizes, and GPU counts.CIFAR-10/100 and Tiny-ImageNet use weight decay 0.0005, 800 epochs, batch size 512, and one GTX 1080; ImageNet uses 0.0001, 100 epochs, batch size 384, and eight GTX 1080 GPUs.Source: A Experiment details · p. 25
  • Linear heads are trained for 100 epochs with batch size 256 and no weight decay, using learning rate 30.0 decayed by 10x at epochs 60 and 80.Source: A Experiment details · p. 25
  • The image transformations follow the augmentation strategy described in (Chen and He, 2020).Source: A Experiment details · p. 25

B Proofs for Section 3

  • The appendix first proves a more general version of Theorem 3.8 in Section B.1, then proves Theorem 3.8 in Section B.2.Source: B Proofs for Section 3 · p. 26

B.1 A generalized version of Theorem 3.8 · B.2 Proof of Theorem 3.8

The appendix generalizes the spectral linear-probe guarantee using augmentation-graph spectral and partition quantities, then proves Theorem 3.8 by relating classifier-induced extended labels to its assumptions and applying the generalized result. The argument uses a higher-order Cheeger partition and an ensemble majority-vote condition.

B.1 A generalized version of Theorem 3.8

  • The normalized Laplacian is defined as L = I − D^−1/2AD^−1/2, so its i-th smallest eigenvalue λ_i corresponds to the i-th largest normalized-adjacency eigenvalue 1 − λ_i.Here A is the augmentation-graph adjacency matrix and D is the diagonal degree matrix.Source: §B.1 · p. 26
  • Theorem B.2 gives a linear-probe guarantee for a population spectral-contrastive-loss minimizer when k + 1 = (1 + ζ)k′ and k′ ≥ r, with an error bound involving the sparsest m-partition quantity.It also states that the probe can be chosen with Frobenius norm at most 1/(1 − λ_k), where λ_k is a normalized-Laplacian eigenvalue.Source: §B.1 · p. 26
  • Theorem B.3 extends the probe guarantee to any extended labeling function, with probe norm at most 1/(1 − λ_k) and an error bound stated in terms of that labeling.The proof first obtains a related guarantee depending on λ_{k+1}, then removes that dependence using a higher-order Cheeger inequality (Louis and Makarychev, 2014).Source: §B.1 · p. 27
  • The higher-order Cheeger step supplies a partition whose set conductances bound the sparsest m-partition quantity, yielding the spectral-to-partition bound used to prove Theorem B.2.The proof sets (1 + ζ)t = k + 1 and t = k′, then combines the partition guarantee with Theorem B.3.Source: §B.1 · p. 27

B.2 Proof of Theorem 3.8

  • Lemma B.5 constructs an extended labeling from the classifier-induced partition, with its discrepancy from the ground-truth labels bounded by α.It also relates disagreement between extended labels to disagreement with the natural datapoint’s ground-truth label.Source: §B.2 · pp. 27–28
  • The proof of Theorem 3.8 applies Theorem B.2 to the extended labels formed from the classifier-induced partition, using k′ = ⌊k/2⌋·log(k).The ensemble probe errs only when more than half of a natural datapoint’s augmentations predict a label different from its ground truth.Source: §B.2 · p. 28

B.3 Proof of Theorem B.3 · C Proofs for Section 3.4

The proof establishes linear-probe accuracy by showing that low-eigenvalue Laplacian features approximate label indicators, then relating spectral-contrastive-loss minimizers to those features. It also connects quadratic loss to prediction error to complete the accuracy argument.

B.3 Proof of Theorem B.3

  • Theorem B.3’s proof uses the smallest Laplacian eigenvectors to obtain good linear-probe accuracy, then shows a spectral-contrastive-loss minimizer is equally good.The proof combines eigenvector approximation, a bound on the Rayleigh quotient of extended label indicators, and the equivalence between loss minimizers.Source: §B.3 · pp. 28, 30, 31
  • For k < N with λ_{k+1} > 0, the first k eigenvectors approximate any vector with an error proportional to its Rayleigh quotient, using coefficients with bounded norm.The coefficients’ norm is at most the norm of the original vector.Source: §B.3 · p. 28
  • For an extended label indicator, Claim B.7 relates its Rayleigh quotient to the weighted graph boundary between examples labeled i and those not labeled i.The claim defines that boundary using weights on edges crossing the indicator’s two sides.Source: §B.3 · p. 29
  • A feature extractor f minimizes population spectral contrastive loss if and only if the matrix with rows √w_x f(x) minimizes the matrix approximation loss.The proof rewrites the spectral contrastive loss and matrix approximation objective to show they differ only by a constant.Source: §B.3 · pp. 29–30
  • By the Eckart–Young–Mirsky theorem, matrix-approximation minimizers are the largest eigenvectors of I−L, equivalently the smallest eigenvectors of L.Lemma B.8 therefore identifies spectral-contrastive-loss minimizers with the smallest Laplacian eigenvectors up to data-wise scaling.Source: §B.3 · p. 30

C Proofs for Section 3.4

  • Claim B.9 relates quadratic loss to prediction error, providing the step used to bound the linear predictor’s error rate.The proof of Theorem B.3 invokes this claim before bounding the error rate on X.Source: §B.3 · pp. 30, 32

C.1 Proof of Proposition 3.9

The proof of Proposition 3.9 establishes a lower bound of 1/6 for the right-hand side of Equation (29). It uses a Gaussian total-variation bound and combines intermediate inequalities with a surface-area definition to complete the proof.

C.1 Proof of Proposition 3.9

  • The right-hand side of Equation (29) is lower bounded by 1/6.This is the proof’s explicit intermediate bound.Source: §C.1 · p. 33
  • For x in N(R), the Gaussian total-variation bound yields P(Si|x) ≥ 1/2.The proof uses a total-variation bound of 1/6 for Gaussian distributions with variance σ^2 · Id×d and centers at most σ/6 apart, then combines it with 2/3.Source: §C.1 · p. 33
  • Combining Equations (34), (36), and (37), with the surface-area definition, finishes the proof.The proof cites Guggenheimer (1977, chapter 4) for the surface-area definition.Source: §C.1 · p. 33

C.2 Proof of Theorem 3.11 · C.3 Proof of Lemma C.2 · D Proofs for Section 4

The appendix proves Theorem 3.11 by bounding α and the augmentation-graph partition quantity, and proves Lemma C.2 using regularity of augmentation probabilities and Gaussian isoperimetry.

C.2 Proof of Theorem 3.11

  • In Theorem 3.11’s setting, the data distribution satisfies Assumption 3.6 with α ≤ 1 poly(d′).Source: §C.2 · p. 34
  • The proof also states that an augmentation changes the label with probability at least 1 − 1/poly(d).Source: §C.2 · p. 34
  • For any k′ > r and τ > 0, Lemma C.2 gives a lower bound for the sparest m-partition of the augmentation graph.Source: §C.2 · p. 34
  • The proof combines the α bound with a concentration inequality, sets k′ = ⌊k/2⌋, and applies Theorem 3.8.Source: §C.2 · p. 35

C.3 Proof of Lemma C.2

  • For a set S, Lemma C.2’s proof uses the principle that nearby data cannot have very different probabilities of augmenting into S.It defines Pr(S|x) as the probability that an augmentation of x lies in S.Source: §C.3 · pp. 35–36
  • When k′ > r, the Lemma C.2 proof selects a partition set, considers two cases, and combines them to obtain its bound.Source: §C.3 · pp. 36–37
  • The proof transfers neighborhood bounds through the κ-bi-Lipschitz map Q and invokes Gaussian isoperimetry.Source: §C.3 · p. 37

D.1 Proof of Theorem 4.1 · D.2 Generalization bound for spectral contrastive learning with deep neural networks

The appendix proves a high-probability excess-risk bound for empirical spectral contrastive loss and specializes the generalization analysis to norm-controlled deep neural networks. The proof uses unbiased empirical and subsampled losses, Rademacher complexity, and a projection step.

D.1 Proof of Theorem 4.1

  • The empirical spectral contrastive loss is an unbiased estimator of the population loss.The appendix defines the empirical loss over an i.i.d. dataset and states its unbiasedness.Source: §D.1 · pp. 37–38
  • A permutation-based subsampling scheme produces a tuple loss that is unbiased for the empirical loss, enabling analysis through i.i.d. tuple terms.The scheme samples tuples after permuting the dataset; the resulting tuple loss is an unbiased estimator of the empirical loss.Source: §D.1 · p. 38
  • Lemma D.5 relates tuple-loss Rademacher complexity to the coordinate-wise complexity of feature extractors using Talagrand’s lemma.The lemma assumes feature coordinates are bounded in absolute value by κ.Source: §D.1 · pp. 38–39
  • The passage states an excess-risk bound with probability at least 1−δ, where ˆf is the minimizer of bLnpre(f) in F and f∗ also appears in the bound.Source: §D.1 · p. 40

D.2 Generalization bound for spectral contrastive learning with deep neural networks

  • Theorem D.6 specializes the generalization bound to norm-controlled l-layer ReLU networks with projected outputs, bounded inputs, and bounded layer norms.Its dataset has size 2n_pre; the network maps inputs in X ⊂ R^d with ∥x∥2 ≤ Cx and uses projection to [−κ, κ].Source: §D.2 · p. 40
  • The proof uses the 1-Lipschitz projection and a norm-controlled neural-network Rademacher-complexity bound to apply Theorem 4.1 to the network class.It identifies each output coordinate’s hypothesis class with the real-valued network class followed by projection.Source: §D.2 · p. 41

D.3 Proof of Theorem 4.2 · D.4 Proof of Theorem D.9

The appendices establish a bound on downstream error from near-optimal pretraining and prove a generalized spectral-loss guarantee by reducing it to matrix approximation and spectral projection arguments.

D.3 Proof of Theorem 4.2

  • Under k ≥ 4r + 2, Assumptions 3.6 (α > 0) and 3.7, Theorem D.7 bounds downstream error when the representation’s population loss is within ε of optimum.Source: §D.3 · p. 41
  • Theorem D.7 also guarantees a linear head that achieves the downstream error and has a norm bound.Source: §D.3 · p. 41

D.4 Proof of Theorem D.9

  • For finite augmented data, Theorem D.9 generalizes Theorem B.3 to an ε-optimal spectral-contrastive minimizer and any labeling function, bounding error using φ̂y and Δ(y, ŷ).Source: §D.3 · p. 42

D.3 Proof of Theorem 4.2

  • The proof applies Theorem D.7 by inducing labels from the classifier’s partition, for which the stated quantities satisfy φ̂y ≤ 2α and Δ(y, ŷ) ≤ α.Source: §D.3 · p. 42
  • Theorem 4.2 follows directly as a corollary of Theorems 4.1 and D.7.Source: §D.3 · p. 42

D.4 Proof of Theorem D.9

  • Lemma D.10 equates ε-optimality of the matrix approximation loss with ε-optimality of the population spectral contrastive loss under the weighted matrix representation.Source: §D.4 · p. 43
  • For i ≤ k, Lemma D.12 bounds the squared projection of eigenvector vi outside the feature span by ε/(λk+1 − λi)^2.Source: §D.4 · p. 44
  • Lemma D.13 extends Lemma B.6 by constructing a feature-span linear approximation to a vector, with error controlled using its Rayleigh quotient.Source: §D.4 · pp. 45–46

E Proofs for Section 4.2 · F Formal statements for population with infinite supports

The appendix completes the proof of Theorem 4.3 and extends the population theory to infinite supports under regularity conditions. In that setting, Laplacian eigenfunctions exist and the stated population results carry over by replacing sums with integrals.

E Proofs for Section 4.2

  • Theorem 4.3’s proof concludes by plugging the Theorem 4.1 excess-loss bound into the probe result, which is stated to hold for any excess loss.The proof uses a linear probe and a standard generalization bound before this final step.Source: E Proofs for Section 4.2 · pp. 48–49

F Formal statements for population with infinite supports

  • The theory extends to infinite augmented-data supports, replacing sums, finite graphs, adjacency matrices, and eigenvectors with integrals, infinite graphs, adjacency operators, and eigenfunctions.The section illustrates the extension with X = Rd and notes that a subset of Rd with base measure µ uses dµ in place of dx.Source: F Formal statements for population… · p. 49
  • The extension assumes regularity including finite bounded marginal weights and a uniform B bound on conditional pair probabilities relative to the other-variable marginal; B is not needed in the bound itself.The pair weight function is the density of the joint distribution of a random positive pair.Source: F Formal statements for population… · p. 49
  • The infinite-support formulation defines the Laplacian as an operator on L2(Rd) and defines its eigenfunctions through the operator’s action on functions in that space.The section also frames these functions in the L2(Rd) Hilbert space.Source: F Formal statements for population… · pp. 49–50
  • Under Assumption F.1, the Laplacian has an orthonormal basis of eigenfunctions with eigenvalues in [0, 1] in nondecreasing order.The proof invokes the spectral theorem because L − I is a Hilbert–Schmidt integral operator.Source: F Formal statements for population… · p. 50
  • Theorems 3.8, 4.2, and 4.3 extend to infinite supports by replacing the sum in the derivation with an integral and using the corresponding L2 functions.The paper states that the remaining derivations follow in the same way.Source: F Formal statements for population… · p. 50

Related papers

Loading 2106.04156v7…