Understanding Self-supervised Learning with Dual Deep Networks
Authors: Yuandong Tian
Lantao Yu
Xinlei Chen
Surya Ganguli
Venue:  (2021)
Keywords: self-supervised learning
teacher-student setting
theoretical analysis
hierarchical models
representation learning

Abstract: We propose a novel theoretical framework to understand self-supervised learning methods that employ dual pairs of deep ReLU networks (e.g., SimCLR, BYOL). First, we prove that in each SGD update of SimCLR, the weights at each layer are updated by a \emph{covariance operator} that specifically amplifies initial random selectivities that vary across data samples but survive averages over data augmentations. We show this leads to the emergence of hierarchical features, if the input data are generated from a hierarchical latent tree model. With the same framework, we also show analytically that in BYOL, the combination of BatchNorm and a predictor network creates an implicit contrastive term, acting as an approximate covariance operator. Additionally, for linear architectures we derive exact solutions for BYOL that provide conceptual insights into how BYOL can learn useful non-collapsed representations without any contrastive terms that separate negative pairs.  Extensive ablation studies justify our theoretical findings. 

Under review as a conference paper at ICLR 2021
UNDERSTANDING SELF-SUPERVISED LEARNING WITH DUAL DEEP NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose a novel theoretical framework to understand self-supervised learning methods that employ dual pairs of deep ReLU networks (e.g., SimCLR, BYOL). First, we prove that in each SGD update of SimCLR, the weights at each layer are updated by a covariance operator that specifically amplifies initial random selectivities that vary across data samples but survive averages over data augmen- tations. We show this leads the emergence of hierarchical features, if the input data are generated from a hierarchical latent tree model. With the same frame- work, we also show analytically that in BYOL, the combination of BatchNorm and a predictor network creates an implicit contrastive term, acting as an approx- imate covariance operator. Additionally, for linear architectures we derive exact solutions for BYOL that provide conceptual insights into how BYOL can learn useful collaalape representations without any contrastive terms that separate negative pairs. Extensive ablation studies justify our theoretical findings.
INTRODUCTION
While self-supervised learning (SSL) has achieved great empirical success across multiple domains, including computer vision (He et al. 2020 Goyal et al.) 2019] Chen et al. 2020a Grill et al. 2020
Misra and Maaten 2020; Caron et al. 2020). natural language processing (Devlin et al. 2018).
and speech recognition (Wu et al.) 2020 Baevski and Mohamed, 2020 Baevski et al.] 2019)), its
theoretical understanding remains clusive, especially when multi-layer nonlinear deep networks are involved (Bahri et al., 2020). Unlike supervised learning (SL) that deals with labeled data, SSL learns meaningful structures from randomly initialized networks without human- numan-provided labels.
In this paper, we propose a systematic theoretical analysis of SSL with deep ReLU networks. Our analysis imposes parametric assumptions on the input data distribution and is applicable state- of-the-art SSL methods that typically involve two parallel (or dual) deep ReLU networks during training (e.g.. SimCLR (Chen et al., 2020a). BYL (Grill et al. 2020). etc). We do so by developing an analogy between SSL and theoretical framework for anal azilyzing supervised learning, namely the student-teacher setting Tian, 2020; Allen and Li 2020 Lampinen and Ganguli 2018 Saad
and Solla 1996), which also employs a pair of dual networks. Our results indicate that SimCLR weight updates every layer are amplified by a fundamental positive semi definite (PSD) covariance operator that only captures feature variability across data points that survive averages over data augmentation procedures designed in practice scramble semantically unimportant features (e.g. random image crops, blurring or color distortions (Falcon and Chol 2020; Kolesnikov et al. 2019 Misra and Maaten 2020: Purushwalkam and Guptal 2020)). This covariance operator provides a principled tramework to study how SimCLR amplifies initial random selectivity to obtain distinctive features that vary across samples after surviving averages over data-augmentations.
Based on the covariance operator, we further show that (1) in a two-layer setting. a top-level covari- ance operator helps accelerate the learning of low-level features, and (2) when the data are generated by a hierarchical latent tree model, training deep ReLU networks leads to an emergence of the latent variables in its intermediate layers. We also analyze how B BYO might work without negative pairs. First we show analytically that an interplay between the eero-mean operation in BatchNorm and the extra predictor in the online network creates an implicit contrastive term, consistent with empirical observations in the recent blog (Fetterman and Albrecht, 2020). Note this analysis does not rule out the possibility that BYOL could work with other normalization techniques that don't introduce contrastive terms, as shown recently (Richemond et al. 2020a). To address this, we also derive exact solutions to BYL in linear networks without any normalization, providing insight into how BYOL can learn without contrastive terms induced either by negative pairs or by BatchNorm. Finally, we also discover that reinitializing the predictor every few epochs doesn't 't hurt BYO performance, thereby questioning the hypothesis of an optimal predictor in (Grill et al. 2020

---

Under review as a conference paper at ICLR 2021
(a)
Ji(x)
X1
fx
Online (Student) W;
predictor
p())
Loss
Wi
ReLyy
91
Rely
Augmentation
Lager?
Layer my nodes
X1 Kg Paue
Target (Teacher) W/
Ti-- nodes
Figure 1: (a) Overview of the two SSL algorithms we study in this paper: SimCLR (W1 W2 W. no
predictor, NCE Loss) and BYOL (Wi has extra predictor, W2 a moving average). (b) Detailed Notation.
To the best of our knowledge, we are the first to provide systematic theoretical analysis of modern SSL methods with deep ReLU networks that elucidates how both data and data augmentation, drive the learning of internal representations across multiple layers.
Related Work. Besides SimCLR and BYOL, we briefly mention other concurrent SSL frame- works for vision. MoCo (He et al.] 2020; Chen et al. (2200b) keeps a large bank of past representa- tions in a queue as the slow- progressing target to train from. DeepCluster (Caron et al.) 2018) and SWAV (Caron al., 2020) learn the representations by iteratively or implicitly clustering on the cur- rent representations and improving representations using the cluster label. (Alwassel et al.) 2019) applies similar ideas to multi-modality tasks. In contrast, the literature on the analysis of SSL with dual deep ReLU networks is sparse. (Arora et al., 2019) proposes an interesting analysis of how contrastive learning aids downstream classification tasks, given assumptions about data generation. However, it does not explicitly analyze the learning of representations in deep networks.
2 OVERALL FRAMEWORK
Notation. Consider an I--layer ReLU network obeying fi = (fi) and f: Wifi-1 for 1 1,... L. Here fi and fi are n, dimensional pre-activation and activation vectors in layer with fo being the input and fL = fL the output (no ReLU at the top layer). Wi -= are the weight matrices, and vuu)) == max (u, 0) is the element-wise ReLU nonlinearity. We let W (Wi) be all network weights. We also denote the gradient of any loss function with respect to ft by g E R and the derivative of the output fL with respect to an earlier pre-activation fi by the Jacobian matrix [z; W) E P as both play key roles in backpropagation (Fig. (b)).
An analogy between self-supervised and supervised learning: the dual network scenario. Many recent successful approaches to self-supervised learning (SSL), including SimCLR (Chen) et al., 2020a). BYOL (Grill et al., 2020) and MoCo (He et al. 2020), employ dual "Siamese- like" pair (Koch et al. 2013) of such networks (Fig. [b)). Each network has its own set of weights W1 and Wz. receives respective inputs I1 and D2 and generates outputs fi, (x1; Wi) and (22; W2). The pair of inputs [02) } can be either positive negative, depending on drawn from the data distribution
how they are sampled. For a positive pair, single data point p(-), and then two augmented views 21, and 22 are drawn from a conditional augmentation distri- bution (-lr() Possible image augmentations include random crops, blurs or color distortions, that ideally preserve semantic content useful for downstream tasks. In contrast, for negative pair, two different data points æ, x' ~ p(-) are sampled, and then each are augmented independently to generate x; PPngg and 22 (aau(-lax'.. For SimCLR, the dual networks have tied weights with Wi- = W2, and loss function is chosen to encourage the representation pairs to become similar (dissimilar). In BYOL, only positive pairs are used, and the first network Wi called the online network, is trained match the output of the second network W2 (the target), using an additional layer named predictor. The target network ideally provides training targets that can improve the online network's 's representation and does not contribute a gradient. The improved online network gradually incorporated into the target network, yielding a bootstrapping procedure.
positive (negative)
Our fundamental goal is to analyze the mechanisms governing how SSL methods like SimCLR and BYOL lead to the emergence of meaningful intermediate features, starting from random initial- izations, and how these features depend on the data distribution p(x) and augmentation procedure Pang(-lax), Interestingly. the analysis of supervised learning (SL.) often employs a similar dual net- work scenario. called -tudeet-t setting (Tian) 2020 Allen-Zhu and Li 2020: Lampinen and Ganguli, 2018 [aad and Solla 1996), where W/2 are the ground truth weights of a fixed teacher network, which generates outputs in response to random inputs. These input- pairs constitute training data for the first network, which is student network. Only the student network's weights
2

---

Under review as a conference paper at ICLR 2021
W1 are trained to match the target outputs provided by the teacher. This yields an interesting mathe- matical parallel between SL, in which the teacher is fixed and only the student evolves, and SSL, in which both the teacher and student evolve with potentially different dynamics. This mathematical parallel opens the door to using techniques from SL (e.g.. (Tian 2020 to analyze SSL.
Gradient of lg loss for dual deep ReLU networks. As seen above, the (dis) (dis)similarity repre- sentations between a pair of dual networks plays a key role in both SSL and SL. We thus consider minimizing a simple measure of dissimilarity, the squared lg distance r := f - f2.. be- tween the final outputs fT.,, and f..t. of two multi-layer ReLU networks with weights Wi and W2 and inputs #1 and Ø22- Without loss of generality, we only analyze the gradient w.r. W1. For each layer I, we first define the connection (2))) quantity that connects the bottom-up feature vector fi-1 with the top-down Jacobian Jr, which both contribute to the gradient at weight layer I.
Definition 1 (The connection (i(z)). The connection (i W) == fi= W) @ [x; W) R X Here & is the Kronecker product.
Theorem (Squared l2 Gradient for dual deep ReLU networks). The gradient 9w, of w.rl Wi E
RRIXRI- for a single input pair (I1, ]22 is (here KT,;== == K( Wi) and K2,1 == K2 Wz)):
gw. = vec (Orr))) = K1,1 ([],vec(L..) - KJ, (ec,..)
(1)
We used vectorized notation for the gradient 9W; and weights W₁ to emphasize certain the- oretical properties of SSL learning below. The equivalent matrix form is 0r/OWi,
H. [J,,Wi, - -1.---1--,,,12 22,,W,,,f2,.11 ff,1-1
See Appendix for proofs of all theorems in main text.
ANALYSIS OF SIMCLR
As discussed above, SimCLR (Chen et al. 2020a) employs both positive and negative input pairs, and symmetric network structure with Wi W2 W. Let (a11 ] be positive input pair from x, and let (æ1, - } for k I,..., H be H negative pairs. These imput pairs induce corresponding squared & distances in output space, r- 211 f f+,211. and rą- = f1l f
We consider three different contrastive losses, (1) the simple contrastive loss Lsimp := T+ r-.
(2) (soft) Triplet loss L == T log(11 + c - +ro)/) (here ro 2 0 is the margin). Note that -o Lii max(r+ r- + 0) 0) (Schroff et al. 2015). (3) InfoNCE loss (Oord et al. 2018):
e-+//T
L (r+, r1-, .-...---.................... ................................ rH-)
log
(2)
--r + H -k-K
= Note that when | = ||0||| = 1. we have -11luu - v 2 = sim u. D - 1 where sim (u, v)
TTv Tu]|a||eaa. and Eqn. 2 reduces what the original SimCLR uses (the term 1/7 cancels out).
For simplicity, move the analysis of the final layer f2 normalization Appendix A.2 In Ap- pendix F.6 of B BYB Grill et al. (2020) v3, it shows that even without le normalization, the algorithm still works despite numerical instabilities. In this case, the goal of our analysis is to show that useful weight components grow exponentially in the gradient updates.
One property of these loss functions is important for our analysis: Theorem (Common Property of Contrastive Losses). For loss functions L E (iiimp Litt Lico),
we have aL 0, AL 0 for 1 < k S. H and ØL. yr. E aL 0.
8r
Brk
Brk
With Theorem I and Theorem 2. we now present our first main contribution. The gradient in Sim- CLR governed by a positive semi-definite (PSD) covariance operator at any layer
Theorem (Covariance Operator for Lismp). With large batch limit, Wi 's update under Lsimp is:
Wi + 1) = (t) + adW,(t), where vec(AW((t)) = Opeime (W)yec(W((t)) (3)
where Op-imp : Varpl.) (R; E 1RU0I-1XACmL- is the covariance operator for Lsimp- [2 W) := Epprppp((( [Kr (2': W)] is the expected connection under the augmentation distri- bution, conditional on the datapoint and a is the learning rate.
Theorem 4 (Covariance Operator for Li and Lice (H 1, single negative pair)). Let ==
(x) - fz The covariance operator OP((W) = !af (pp))())))) [Ki(x) - Ki(x')] + corr, where corr = OB [v ((( x')ttV (m (f(("") For Lis ((r) (r rolir (and lim,-so TT(r S ro)). For Thcor E(r) 1 --to
1r--
Ite r For Isimp: E(r) and corr 0.
3

---

Under review as a conference paper at ICLR 2021
A
x(
(a)
(b)
(d)
w
FC
Generative model
2
data
x(3g.73)
mothod
(c)
W2.
P(a (su)
PC
X4
Augmentation (keep 2, and change z')
Hisrarchical Lateeni
Deepp ReLU networks
Tree Middll
Figure 2: Overview of Sec. (a) To analyze the functionality of the covariance operator V [=o) (Eqn. B), we assume that Nature generates the data from a certain generative model with latent variable 2g and z', while data augmentation takes Ø=20, ="), changes z' but keeps 20 intact. (b) Sec. / one layer one neuron example. (e) Sec. (4.2 two-layer case where V [K] and V [2] interplay. (d) Sec. 4.3 Hierarchical Latent Tree Models and deep RcLU networks trained with SimCLR. latent variable Ap, and corresponding nodes N₁
multi-layer ReLU side, covers a subset input æ resembling local receptive fields ConvNet.
Above, we use Cov Gov-[x,y X == E (E(XX E - EYD" and [[[X] Cov X XX (Cov[X, Y] means {()) 1). The covariance operator OP, (W)) a time-varying PSD matrix over the entire training procedure. Therefore, all its eigenvalues are non-negative and at any time t, Wi is most amplified along its largest eigenmodes. Intuitively, (P)) ignores different views of the same sample æ by averaging over the augmentation distribution to compute (x),, and then com- putes the expected covariance of this augmentation averaged connection with respect to the data distribution p(æ). Thus, at all layers, any variability the connection across different data points, that survives augmentation averages, leads to weight amplification. This amplification of weights by the PSD data covariance of an augmentation averaged connection constitutes fundamental de- scription of SimCLR learning dynamics for arbitrary data and augmentation distributions.
4 HOW THE COVARIANCE OPERATOR DRIVES THE EMERGENCE OF FEATURES
To concretely illustrate how the fundamental covariance operator derived in Theorem drives fea- ture emergence in SimCLR, we setup the following paradigm for analysis. The input x: = x x=2, z') is assumed to be generated by two groups of latent variables, class/sample-speccfff latents zo and muisance latents 2/. We assume data augmentation only changes 2' while preserving 2g (Fig. a)).
For brevity we use Theorem 3 (iimp)) then OP- V., (zt(K((z)) since =' is averaged out in Ki (=0).
In this setting, we first show that linear neuron performs PCA within an augmentation preserved subspace. We then consider how nonlinear neurons with local receptive fields (RFs) can learn to detect simple objects. Finally, we extend our analysis to deep ReL.U networks exposed to data gener- ated by hierarchical latent tree model (HLTM), proving that, with sufficient over parameterization, there exist lucky nodes at initialization whose activation is correlated with latent variables underly- ing the data, and that SimCLR amplifies these initial lucky representations during learning.
4.1 SELF-SUPERVISED LEARNING AND THE SINGLE NEURON: ILLUSTRATIVE EXAMPLES
A single linear neuron performs PCA in a preserved subspace. For a single linear neuron (L n1 = 1), the connection in definition| lis simply K1(x) = Now imagine the input space can be decomposed into the direct sum of a semantically relevant subspace, and its orthogonal complement, which corresponds to a subspace of nuisance features. Furthermore, suppose the aug- mentation distribution Pang (a)) is obtained by multiplying x: by random Gaussian matrix that acts only in the nuisance subspace, thereby identically preserving the semantic subspace. Then the aug- mentation averaged connection (z:) Q' where Q* is projection operator onto the semantic subspace. In essence, only the projection of data onto the semantic subspace survives augmentation averaging, as the nuisance subspace is scrambled. Then OP = [K[ [x)] = Q x Q*T. Thus the covariance of the data distribution, projected onto the semantic subspace, governs the growth of the weight vector Wi, demonstrating SimCLR on a single linear neuron performs PCA within semantic subspace preserved by data augmentation.
A single linear neuron cannot detect localized objects. We now consider a generative model in which data vectors can be thought of as images of objects of the form x=20, where 2g is an important latent semantic variable denoting object identity, while z' is an unimportant latent variable denoting nuisance features, like object pose or location. The augmentation procedure scrambles pose/position while preserving object identity. Consider a simple concrete example (Fig. [3(a)):
ear + e(s4+1) mod
2g = 1
x(20. 2/) =
(4)
e. + e(2442) mod d 2g = 2,
Here 0 05 d d-dd1 - 1 denotes d discrete translational object positions on a periodic ring and 20 e
(1,2) denotes two possible objects 11 and 101. The distribution is uniform both over objects
4

---

Under review as a conference paper at ICLR 2021
(al)
(a2)
(b)
2g =
20
Pattern
A
44
mg(l)
22(2)
Figure 3: (a) Two ID objects under translation: (al) Two different objects 11 (zo = 1) and 101 (z) = 2) located different locations specified by z', (u2) The frequency table for neuron with local receptive field of size 2. (b) In two-layer case (Fig. ((e). V[Ki] and V[Ka interplay in two-cluster data distribution.
(Feg.
and positions: p(zu, 2') 2d Augmentation shifts the object to a uniformly random position via Paug(2 (='| |=0) = 1/d. For single linear neuron Ki(#)) ac, and the augmentation-aavragel connection is (=n) 3 and is actually independent of object identity 2g (both objects activate two pixels at any location). Thus OP1 Zzo [R]( = 0 and no learning happens.
local receptive field (RF) does not help. In the same generative model, now consider a linear neu-
ron with a local RF of width 2. Within the RF only four patterns can arise: 00, 01, 10, 11. Taking
the expectation over 2' given =o (Fig. 3 a2)) yields K2 (20=1) = [011 + 2oo + 110 + (d - 3) 3o00
and (20=2) d [2xo1 + 2010 + (d 4)zoo)) Here, I1 E IR? denotes pattern 11. This yields
1 uu
OP1 2o [2o)]
where u == I1 300
T01
310
(5)
4d
and OP1 E Rx22 since the RF has width 2. Note that the signed sum of the four pattern vectors in actually cancel, so that u = 0. implying OP1 = and no learning happens. Interestingly, although the conditional distribution of the 4 input patterns depends on the object identity 20 (Fig. (a))), linear neuron cannot learn to discriminate the objects.
nonlinear neuron with local RF can learn to detect object selective features. With a ReLU neuron with weight vector w, from Def. | the connection is now K₃ (Ix, w) (wTar) Suppose wt) happens to be selective for a single pattern Tp (where p E {00, 01, 10, 11 11)), i.c., wt) > 0 and w a() < O for p' # p. The augmentation averaged connection is then Ki (zo) x B. where the proportionality constant depends on object identity 2n and can be read off (Fig. aa))). Since this averaged connection varies with object identity zo
for all p, the covariance operator OP1 is nonzero and is given by V=o [K [2o)] = C. where the constant Cp > 0 depends on the selective pattern 3 the dot product 2. wt grows over time:
p and can be computed from 3 a2). By Theorem
w.][[[ + = xx (I2x2 + 2. vn(1= = (1 (1+ -cpl1=1p111 ur],nn(() (1) > (l)) > O. (6)
Thus the learning dynamics amplifies the initial selectivity the object selective feature vector T. in a way that cannot be done with a linear neuron. Note this argument also holds with bias terms and initial selectivity for more than one pattern. Moreover, with a local RF, the probability of weak initial selectivity to local object sensitive features is high, and we may expect amplification of such weak selectivity in real neural network training, as observed in other settings (Williams et al. 2018).
4.2 A TWO-LAYER CASE WITH MULTIPLE HIDDEN NEURONS
Now consider a two-layer network (L 2). The hidden layer has nı ReLU neurons while the output has n2 (Fig. 2(c)). In this case, the augmentation-average connection (2(2)) at the lower layer I = 1 can be written as (d no is the input dimension):
(20) = [22,] u (za), (2)), W2,n, u.,, (20)]T E Ruidxng
where Wi, E Rd and W2, E R² are weight vectors into and out of hidden neuron j (Fig. ())., and u, == E2130 [x(20, T.) a(20, z') 2 0)] E gd is the augmentation average of only those inputs that activate hidden neuron j. While the gradient dynamics in SimCLR under Laimp
has a close form (Eqn. 65). is hard to see what happens. Instead, we consider an intuitive sub-case:
Theorem (Dynamics two-layer (W2 diagonal)). If n2 and W2 flag(w2,1,.... W2,n1):
t [ W,, W2.5, W
ii w², A,Wi. where A₁ == V [u, (z0))
(8)
Note that for ReLU neurons, Aj changes with wi.j. while for linear neurons, Aj would be con- stant, since gating v (w = 1. It is easy to see that dw3,//tt = d||wi,,1l /13/dt /dt and thus 2 [/. + where is some time-independent constant. Since A₁ is always PSD, w A, 2 0 and | generically increases, which in turn accelerates the dynamics of wi.i which is most amplified at any given time, along the largest eigenvector of Ay. This dynamics ex- hibits top-down modulation whereby the lap-l weights accelerate the training of the lower layer.
5

---

Under review as a conference paper at ICLR 2021
Symbol
Definition
Size
Description
Ni. Z
The set of all nodes and all latent variables at layer L.
Nodes corresponding to latent variable Zy. Aa are children under .Vj..
2v Fa
2 2
The top-down transition prohability from En Σv. Expected activation JJ given 3y. (zy 's descendants are marginalized).
2z(2p). 2
E. [Bz ppl. [0s (2,)]
scalar, 2
Su. JNrch
[Nuul |
Activations for all nodes j E NN and for the children of N₁,
Pav
2F 11 = -1
scalar in 11,1
Polarity of the transitional probability.
Po
P(zo 1) - P(z0
0)
scalar
Polarity of probability of root latent 2g.
8k
Z (1x(1)) vx (0))
scalar
Discrepancy of node & w.r. its latent variable (x))))-
[
Child selectivity vector.
Table 1: Notation for Sec. 4.3 (binary symmetric HM..M).
2020) also mention similar concept in supervised learning, called "backward feature correction." Here we demonstrate rigorously that a similar behavior can occur in SSL under gradient descent in the 2-layer case when the top layer W2 is diagonal.
Previous works (Allen-Zhu and Li
As an example, consider considerr a mixture of Gaussians: x [1 = and let Aw" := " w.. then in the linear case, Aj ~ -u" TT" and w1,5 converges to =Aw" (Fig. b)). In the nonlinear case with multiple Gaussians, if one of the Gaussians sits at the origin (e.g.. background noise), then dependent on initialization, A, evolves into w for some center k, and wi. + wng. Note this dynamics is insensitive to specific parametric forms of the input data.
o²)
4.3 DEEP RELU SSL TRAINING WITH HIERARCIICCA LATENT TREE MODELS (HLTM)
We next study how multi-layer ReLU networks learn from data generated by an HLTM, in which visible Icaf variables are sampled via a hierarchical branching diffusion process through a sequence of latent variables starting from a root variable 2g (Fig. dd left)) The HL represents a mathemat- ical abstraction of the hierarchical structure real-world objects, which consist of spatially localized parts and subparts, all of which can lie in different configurations or occluded states. See Appendix for a detailed description and motivation for the HLTM. Simpler versions of the HITM have been used mathematically model how both infants and linear neural networks learn hicrarchical struc- ture (Saxe et al. 2019).. We examine when a multi-layer ReIU network with spatially local RFs can learn the latent generative variables when exposed only to the visible leaf variables (Fig, 2 right)).
We define symbols in Tbl. At layer I, we have categorical latent variables {z where μ E 2, indexes different latent variables. Each zn can take discrete values. The topmost latent variable is 2o. Following the tree structure, for μ E 2, and 11, V22 Z conditional independence holds: P(Zz, Zuz kp) IP(z,, (x,, Izy). The final sample x is just the collection of all visible leaf variables (Fig. 2 d)). and thus depends on all latent variables. Corresponding to the hierarchical tree model, each neural network node Ni maps
unique μ. (uj) 2, Let N,, be all nodes that map to μs. For j E NNy, its activation f, only depends on the value of 2μ and its descendant latent variables, through input œ. Define (zx) := E= [f zn] as the expected activation w.r.t zn. Given a sample æ, data augmentation involves resampling all zn. (which are x' in Fig. 2 fixing the root 2g-
Symmetric Binary HLTM Here we consider a symmetric binary case: each 2p E {0, and for E Z,, E Z1-1, P(z,- = 1zp 1) = P( = 0) 0) (1 + p/2 where the polarity Peu E 1-1, 1] measures how informative žμ is. If Purr #1 then there no stochasticity in the top-down generation process; PPr = 0 means no information in the downstream latents and the posterior of žy given the observation æ can only be uniform. See Appendix for more general cases.
Now we compute covariance operator OP,- Vzo (2(o) at different layers, where Ky(20) =
Eg [Na ] Here we mainly check the term Ey [ |zo] and assume Ju is constant.
Theorem 6 (Activation covariance in binary HLTM). Vao E. [vva [co] = a Here a₂ ( and op == pô, (1 Po). If maxap |paal < 1, then lim Pay. + 0 0 μ E Z
Theorem 6 suggests when Pop and ||a, || are large, the covariance OP,, = a. @ J[J is large and training is faster. For deep HLTM and deep networks, at lower layers, Po,, + 0 and Po is uniform due mixing of the Markov Chain, making OP,, small. Thus training in SSL is faster at the top layers where the covariance operators have large magnitude. On the other hand, large || a,, I /2/r is large, or the expected activation us (z())) is selective for different
implies sa (1*(1) Uy (0))22 values of 2, for v E ch(H). Interestingly, this can be achieved by pverpparamtterizationn (WW, > 1):
6

---

Under review as a conference paper at ICLR 2021
Theorem 7 (Lucky nodes in deep ReLU networks regarding to tion). Suppose each element of the weights Wt between layer 1 and are initialized with Uniform| - 3//// Fw N/ There exists of so that V[[x|z]] S of for any k E NN. For any j Z4+1. if N₂ ((ex(())) then with high probability, there exists at least one node j E N2 so that their activaaivtion gap By (1) o0( = 2wJa, a > 0 and the activations satisfy:
HLTM at initializa-
(1x (0)) ( (5+
( N 30
Σ REV
6 PHu 1 of
4|
Intuitively, this means that with large polarity Pur (strong top-down signals), randomly initialized over-parameterrzze ReLU networks yield selective neurons, if the lower layer also contains selective ones. For example, when oi
= 9, if Per 2 63.3% then there is a gap between expected activations (1(1) and (0) and the gap is larger when the selectivity in the lower layer / is higher. Note that at the lowest layer, {ux} } are themselves observable leaf latent variables and are selective by definition. So bottom-up mathematical induction of latent selectivity will unfold.
If we further assume Ju = I, then after the gradient update, for the "lucky" node j we have:
a. + = a [I [++ [ wy(() = (1 _
> (,, > 0
which means that the pre-activation gap (1) - 0)( = 2w] au grows over time and the latent variable zn is learned (instantiated as fÿ) during training, even if the network is never supervised with its true value. While here we analyze the simplest case JJ.. I), in practice Ju changes over time. Similar to Sec. 4.2 once the top layer starts to have large weights, the magnitude of Jj for lower layer becomes larger and training is accelerated.
We implement the HLTM and confirm, as predicted by our theory, that the intermediate layers of deep ReLUU networks do indeed learn the latent variables of the HLTM (see Tbl. 2 below).
ANALYSIS OF INGREDIENTS UNDERLYING BYOL LEARNING
In BYO,, the two networks are no-longer identical and, interestingly. only positive pairs are used for training. The first network with weights Wi W == (Woase: predd is an online network that is trained to predict the output of the second target network with weights W2 = W., using a learnable predictor Wi Wpred to map the online to target outputs (Fig. [a) and Fig. 1 in Grill et al. (2020)) In contrast, the target network has W := (Wag where W Masg is an exponential moving average (EMA) of Whase: W/sse (1 + 1) = Yema W (t) + +(1 - Yemaa ) Woase (t). Since B BOL only
uses positive pairs, we consider the following loss function:
[ W) - fz.(x=:
(10)
where the input data are positive pairs: 31, 2. ~ Pang( (+ and x ~ p(.). The two outputs, fy (x1; and (x4; W"), are from the online and the target networks, respectively. Note that L' < L due to the presence of an extra predictor on the side online network (W).
With neither EMA (7ema = 0) nor the predictor, W = W and the BYOL update without BN is
vec (AWi)
Exe
(+1=) [K] )]] vei(Wi)
(11)
(see App. E. for proof). This update only promotes variance minimization in the representations of different augmented views of the same data samples and therefore would yield model collapse.
We now consider the effects played by the extra predictor and BatchNorm (BN) (loffe and Szegedy 2013) in BYOL. Our interest in BatchNorm is motivated by a recent blogpost (Fetterman and Al- brecht 2020j. We will see that combining both could yield sufficient condition to create an implicit contrastive term that could help BYO learn. As pointed out recently by Richemond et al. (2020a), BYOL can still work using other normalization techniques that do not rely on cross batch statistics (e.g., GroupNorm (Wu and He 2018). Weight Standardization (Qiao et al., 2019) and careful ini- tialization of affine transform of activations). In Appendix F we derive exact solutions to BYOL for linear architectures without any normalization. to provide conceptual insights into how BYOL can still learn withou! contrastive terms, at least in the linear setting. Here we focus on NatchNorm, leaving an analysis of other normalization techniques in nonlinear BYOL settings for future work.
When adding predictor. Theorem I can still be applied by adding identity layers on top of the target network W so that the online and the target networks have the same depth. Theorem 5 in Tian
7

---

Under review as a conference paper at ICLR 2021
2018 demonstrates this version of BN shifts the downward gradients their mini-batch mean is 0:
1 B
9 :
E VEB
- 9:
(12)
Here gi is the i-th sample in a batch and It is the batch average (same for fi). Backpropagating through this BN (vs. just subtracting the mean only in the forward pass leads to a correction term:
Theorem 8. (1) the network is linear from layer to the topmost and (2) the downward gradient
gi undergoes Eqn. [2] then with large batch limits, the correction of the update i (For brevity, dependency on W is omitted, while dependency on W is made explicit):
vec(öW = EE [Ki())] EE [K(x)) vec(Wi) - Ex [K] (x;; Wi)j vec(W[))
(13)
and the corrected weight update is AW: == AW + SW7N.. Using Equ. 11 we have: ver( (Wi) = vec(AWi)ee - V Ri [x)) (Wi) + Cov [x(())) Ri(m; W')] vec(W;) (14)
Corollary (SimCLR). For SimCLR with contrastive losses Lsimp, Lisi and Lnces 8W7' O.
5.1 THE CASE WITHOUT EMA (Tema = 0 AND THUS Whase = Wasse)
In BYOL when the predictor is present, W of W and BN is present, from the analysis above we know that SW?n * 0, which provides an implicit contrastive term. Note that W * W means there is a predictor, the online network uses EMA, or both. We first discuss the case without EMA.
From Theorem 8 if we further consider a single linear predictor. then the following holds. Here basse (z) == (x: Wbsse) and zero-meat mean expected connection K((x)) == Kı(x) E [[(z)). Corollary (The role of predictor in BYOL). If Wpred = (Wpred) J is linear and no EMA, then brasa (xbbaso(>)]e (2> pred (I Wpred )J (aabba (z)) voc(Wi). If there is no stop gradient, then (.C(AW,) = 2vec (W)) syym Vv (x) (I- "p vec(W))
voc(A (W( voc(AWi) Dyy syy
+ Ex
The Predictor. To see why Wpred plays a critical role, we check some special case,
W pred = 3l xny (W has to be squared matrix), then vec(AWi) = vec(AWi))ae) + 3(1
3)V a KKee (x) veo(W,) If0 <3 3 < 1, then 3(1 - B) > 0 and the covariance operator appears.
In this regime, BYOL works like SimCLR, except that it also minimizes variance across different
augmented views of the same data sample through vec( A AWi)sym (Eqn. TT,, the first term in Eqn. 14
Indeed, the recent blogpost (Fetterman and Albrecht 2020) as well as our own experiments (Tbl. 3 suggests that standard YOL. without BN fails. In addition, we also initialize the predictor with small positive weights (See Appendix G.4). and reinitialize the predictor weights once in a while (Tbl. 5) and BYOL still works, consistent with our theoretical prediction.
Stop Gradient. In BYOL, the target network W" serves target to be learned from, but does not contribute gradients to the current weight W. Without EMA, we might wonder whether the target network should also contribute the gradient or not. Corollary matter what preed is, the update always contains (weighted) negative covariance operator.
2 shows that this won't work: no
5.2 DYNAMICS OF EXPONENTIAL MOVING AVERAGE (EMA)
On the other hand, the EMA part might play different role. Consider the following linear dynamic system, which is simplified version of Eqn. [4 (we omit vec(AWi)aym and W/- Wi.ema):
wtt + 1) (t) = Am (t) = a (()) + (1 A)Wema(t)
(15)
Theorem 9 (EMA dynamics in Eqn. 15
wtt x (1 + k)². Here we define R. = 1n +
a) (V1+ a)) -) and rj = 1 Toma. Moreover, if 2 0, then K S 2/(1/a+1/m1
From the analysis above, when /3 is small, we see that the coefficient before Wi (~ 322 is typically smaller than that before Wr.ma (~~ B). This means X >> O. In this case, K. > 0 and w(l) grows exponentially and learning happens. Compared to no EMA case (Nema = 0 or 17 = 1), with EMA, we have zj < 1 and becomes smaller. Then the growth is less aggressive and training stabilizes.
In Py PyTrrch, the former is x-x. mean () and the latter is x-x mean () ah ()- A formal treatment requires Jacobian J incorporate BatchNorm's contribution and is left for future work.
8

---

Under review as a conference paper at ICLR 2021
Table 2: Normalized Correlation between the topmost latent variables in binary HI.TM and topmost nodes in
deep ReLU networks (L 5) go up when training with SimCLR with NCE loss. We see higher correlations at
both initialization and end of training, with more over--arameene weereparamttrizaaioonn (Left: [V = 2. Right: [W₂,] 5).
Pur
Initial|
epoch 20 epochs
Puo
Initial I epoch 20 epochs
Uniform 0.7, 1
0.51
0.69
0.76
~ Uniform 0.7, 1
0.60
0.72
0,88
Uniform 0.8. 1
0.65
0.76
0.79
Uniform 0..8. 1
0.73
0.80
0.87
Uniform 00.,
0.81
0.85
0.86
Uniform (0.9, 0.87
0.90
0.95
Table 3: Top-1 STL performance with different combination of predictor (P), EMA and BatchNorm using
BYOL. EMA means "aaaa = 0.996, Batch size is 128 and all experiments run on 5 seeds and 100 epochs.
EMA
BN
EMA, BN
P
P. EMA
P. BN
P. E.A,, BN
38.7 0.6
39.3
33.0 0.9
32.8 0.5
3. 3.2
63.6 = 1.06
78.1
Table 4: Top-1 STL performance using different BatchNorm components in the predictor and the projector of BYOL (Tema 0.996, 100 epochs). There is affine part. "И²" zero-mean normalization only. "H, o" = BN without affine, "v, ot normalization with mean and std but only hackpropagating through mean. All variants with detached zero-mean normalization (in red) yield similar poor performance as normalization.
Ill
n ,²,0
11. a
78.1 0.3 44.2 - 7.0 43.9 4.2 0.6 0.6 722
0.6 48.3 2.7 76.3 0.4 47.0
Table Top-1 performance of BYOL using reinitialization of the predictor every T epochs.
Original BYOL
ReInit T' =
Reinit T 10
Relnit T = 20
STL-10 (100 epochs)
78.1
78.6
79.1
79.0
ImageNet (60 epochs)
60.9
61.9
62.4
62.4
6 EXPERIMENTS
We test our theoretical findings through experiments on STL-10 (Coates et al.) 2011) and Ima- geNet (Deng et al.) 2009). We use simplified linear evaluation protocol: the linear classifier is trained on frozen representations computed without data augmentation. This reuses pre-computed representations and accelerates evaluation by 10x. See Sec. G.3 for detailed setup.
Hierarchical I. Latent Tree Model (HLTM). We implement HLTMM and check whether the intermediate layers of deep ReLU networks lear the corresponding latent variables at the same layer. The degree of learning is measured by the normalized correlations between the ground truth latent variable Ey and its best corresponding node j N Tbl. 2 indicates this measure increases with over- parameterization and learning, consistent with our analysis (Sec. 4.3 More experiments in Sec. G.2
Factors underlying BYOL performance. To test our theory, we perform an ablation study of BYOL on STL-10 by modifying three key components: predictor, E.M and BN. Tbl. 3 shows that BN and predictor are important and EMA further improves the performance. First, without a predictor, neither BN nor EMA give good performance. A predictor without BN still doesn't work. A predictor with BN starts to show good performance (63.6%) and further adding EMA leads to the best performance (78.1 %).. This is consistent with our theoretical findings in Sec. 5 which we show that using a predictor with BN yields OW.FN # 0 and leads to an implicit contrastive term
To further test our understanding of the role played by BN, we fractionate BN into several sub-components: subtract by batch mean (mean-norm) norm), divide by batch standard deviation (std-norm) and affine, and do ablation studies (Tbl. 4p. Surprisingly. removing affine yields slightly better performance STL-10 (from 78.1% % 78.7%). We also find that variants of mean-nore rm performs reasonably, while variants of detached mean-norm has similar poor perfor- mance as no normalization, supporting that centralizing backpropagated gradient leads to implicit contrastive terms (Sec. 5). Note that std no rm also helps, which we leave for future analysis.
We also check whether the online network requires an "optimal predictor" as suggested by recent version (v3) of YOL. For this, we reinitialize the predictor (ReInit) every 7 epochs and compare the final performance under linear evaluation protocol. Interestingly. as shown in Tbl. [5] actually improves the performance a bit, compared to the original BYOL that keeps training the same predictor, which should therefore be closer optimal. Moreover, if we shrink the initial weight
Re Rnit
range of the predictor to make Cov (x), K7(æ; W")] (third term in Eqn. 14 more dominant, and reduce the learning rate, the performance further improves (See Tbl. T0 thereby corroborating our analysis.
Appendix G.4

---

Under review as a conference paper at ICLR 2021
REFERENCES
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 9729-9738, 2020.
Priya Goyal, Dhruv Mahajan, Abhinav Gupta, and Ishan Misra. Scaling and benchmarking self- supervised visual representation learning. In Proceedings of the IEEE International Conference on Computer Vision, pages 6391-6400, 2019.
Ting Chen, Simon Korblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint wrXiv:2002.05709 2020a.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent: A new approach to self-supervised learning. arXiv preprint NoXiv:2006.07733, 2020.
Ishan Misra and I Laurens van der Maaten, Self-supervised learning of pretext-invarian representa- tions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6707-6717, 2020.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. arXiv preprint arXiv:2006.0998 09882, 2020.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: arXiv:1810.04805. 2018.
Anne Wu, Changhan Wang, Juan Pino, and Jiatao Gu. Self-supervised representations improve end-to-end speech translation. arXiv preprint arXiv:2006. 12124, 2020.
Alexci Baevski and Abdelrahman Mohamed. Effectiveness of self-supervised pre-training for asr. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7694-7698. IEEE, 2020.
Alexei Baevski, Steffen Schneider, and Michael Auli. vq-wav2vec: Self-supervised learning of discrete speech representations. arXiv preprint arXiv:1900.0544 2019.
Yasaman Bahri, Jonathan Kadmon, Jeffrey Pennington, Sam Schoenholz, Jascha Sohl-Dickstein, and Surya Ganguli. Statistical mechanics of deep learning, Annual Review of Condensed Malter Physics, March 2020.
Yuandong Tian. Student specialization in deep relu networks with finite width and input dimension. ICML, 2020.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.04441. 2020.
Andrew K Lampinen and Surya Ganguli. An analytic theory of generalization dynamics and trans- fer learning in deep linear networks. In International Conference on Learning Representations (ICLR), 2018
David Saad and Sara Solla. Dynamics of on-line gradient descent learning for multilayer neural networks. In Advances in neural information processing systems, pages 302-308, 1996.
William Falcon and Kyunghyun Cho. A framework for contrastive self-supervised learning and designing a new approach, 2020.
Alexander Kolesnikov, Xiaohua Zhai, and Lucas Beyer. Revisiting self-supervised visual represen- tation learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recog- nition, pages 1920-1929, 2019.
Senthil Purushwalkam and Abhinav Gupta. Demystifying contrastive self-supervised learning: In- variances, augmentations and dataset biases. arXiv preprint arXiv:2007. 139/6, 2020.
10

---

Under review as a conference paper at ICLR 2021
Abe Fetterman and Josh Albrecht. Understanding self-supervised and contrastive learning with "bootstrap your own latent" (byol), 2020.
io/ understanding self supervised contrastive htw.nninngtm..ffsssss....
Pierre H. Richemond, Bean-Bastien Grill, Florent Altché, Corentin Tallec, Florian Strub, Andrew Brock, Samuel Smith, Soham De, Razvan Pascanu, Bilal Piot, and Michal Valko. Byol works even without batch statistics. arXiv, 2020a.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.04297, 2020b.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In Proceedings of the European Conference on Computer Vision (ECCV), pages 132-149, 2018.
Humam Alwassel. Dhruv Mahajan, Lorenzo Torresani, Bernard Ghanem, and Du Tran. Self- supervised learning by cross-modal audio-video clustering. arXiv preprint 1oXiv:1911.122 2019.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. February 2019.
Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov. Siamese neural networks for one-shot image recognition. In ICML deep learning workshop, volume 2. Lille, 2015.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings the IEEE conference on computer vision and pattern recognition, pages 815-823, 2015.
Aaron den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. XrXiv preprint arXiv:1807.037444 2018.
Alex H Williams, Tony Hyun Kim, Forca Wang. Saurabh Vyas, Stephen Ryu, Krishna V Shenoy, Mark Schnitzer, Tamara G Kolda, and Surya Ganguli. Unsupervised discovery of demixed, Low-Dimensional neural dynamics across multiple timescales through tensor component anal- ysis. Neuron, 1099 1111009911111111 111..c8, June 2018.
Andrew M Saxe, James L McClelland, and Surya Ganguli. A mathematical theory of semantic development in deep neural networks. Proc. Narl. Acad. Sci. U. S. A., May 2019.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. ICML, 2015.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference computer vision (ECCV), pages 1-1 2018
Siyuan Qiao, Huiyu Wang, Chenxi Liu, Wei Shen, and Alan Yuille. Weight standardization. arXiv 2019.
preprint arXiv:1903.105:
Yuandong Tian. A theoretical framework for deep locally connected relu network. arXiv preprint arXiv:1809. 10829, 2018
Adam Coates, Andrew Ng, and Honglak Lee. An analysis single-layer networks in unsupervised feature learning. In Proceedings of the fourteenth international conference on artificial intelli- gence and statistics, pages 215-223, 2011.
J. Deng, W. Dong, R. Socher, I.-J. Li, K. Li, and I., Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPRO9, 2009.
JG Liao and Arthur Berg. Sharpening jensen's inequality. The American Statistician, 2018.
Pierre H Richemond, Brock, Samuel Smith, Soham De, Razvan Pascanu, Bilal Piot, and Michal Valko. BYOL works even without batch statistics. October 2020b.
Grill, Florent Altché, Corentin Tallec, Florian Strub, Andrew
A Saxe, J McClelland, and S Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In International Conference on Learning Representations (ICLR), 2014.
Pierre Baldi and Kurt Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Netw., 2(1 5553588, January 1989.
11

---

Under review as a conference paper at ICLR 2021
A BACKGROUND AND BASIC SETTING (SECTION 2
A.1 LEMMAS
Definition 2 (reversibilityy) A layer is reversible if there is Gi(æ; W) E - so that fi(;; W) Gi(a; Wif W) and 9t-1 (2; for some constant PSD matrix R 3 Q = 0. A network is reversible if all layers are.
Note that many different kinds of layers have this reversible property, including linear layers (MLP and Conv) and (leaky) ReLU nonlinearity. For multi-layer ReL.U network, for each layer we have:
Gr W) (r W)W, Q X
(16)
where D, E IR RI is a binary diagonal matrix that encodes the gating of each neuron at layer The gating (i W) depends on the current input æ and current weight W.
In addition to ReLU, other activation function also satisfies this condition, including linear, LeakyReLU and monomial activations. For example, for power activation ()xx = x² where p > 1, we have (where fi is the pre- arevaccivation at layer l):
Gr W) = (f:)"
Qr pm
(17)
Note that the reversibility is not the same invertible. Specifically, reversibility only requires the transfer function of a backpropagation gradient is transpose of the forward function.
Remark.
Lemma 1 (Recursive Gradient Update (Extension to Lemma in (Tian) 2020 Let (pseudo)- Jacobian matrix (z = XNLL and recursively define Jı-1(z) (x) = ((())/QG(((z) e
R 1 Here vQi is the constant PSD matrix so that vQivQi = Qi = O.
If (I) the network is reversible (Def. 2 and (2) vQi commutes with Ji(zl)) and J((2))))((Z2) then minimizing the lg objective
r(Wi) == 2 (11 Wi) - fh)j-fr(a (w Wo)l
(18)
with respect to weight matrix W at layer yields the following gradient at layer
gi Jj (x1::)
[J((= f( Wi) [[(2: Wa) Wa)
(19)
Proof. We prove by induction. Note that our definition of W, is the transpose of W, defined in TTia 2020 Also our gi(z)) is the gradient before nonlinearity, while (Tian) 2020 uses the same symbol for the gradient after nonlinearity.
For notation brievity, we let fi(x1) == f(( and Gi(z1) Gi(zi; Wi). Similar for 22 and W2.
When = L, by the property of fz-loss, we know that gr = fa( W1) - fa Wz), by setting (x( = (x2)) = I, the condition holds. Now suppose for layer I, we have:
= (a1) [((x)))((m)) - ((z2)
(20)
Then:
91-1 = (z1))Q1
(21)
= (it
(22)
= GT(Z1) (()(())))))))
(23)
(1,)
= (11)
((m))Q f1 - (iG S(
(24)
jmn(ar)
= (211)
(1)) - (202
(25)
12

---

Under review as a conference paper at ICLR 2021
Note that for multi-layered ReLU network, G1(zz) Di(=) Qi I for each ReLU+Linear layer, if we set ø 2g x. Wi W. W/ W (teacher weights), then we go back to the original Lemma in iTan 2020).
Remark on ResNet. Note that the same structure holds for blocks of ResNet with ReLU activation.
An alternative form of Lemma [ Note that we can alternatively group linear weight with its
immediate downward nonlinearity and Lemma] [ still holds. In this case, we will have:
gi = JT(1)) (((1))((())))))))))))))))))))( J((22) (((22)
(26)
where (x)):) is the (pseudo-NJacobian. Jacobian: J((=) == / (i.e., with respect the pre-activation
ft), as defined in the notation paragraph of Sec. and Φi is the back-propagated gradient after the nonlinearity. This will be used in the following Lemma For other reversible layers (e.g.. Eqn. [7).
the relationship between the pseudo-Jacon Jacuba- and the real one differ by constant (e.g., some power of vp).
A.2
E NORMALIZATION THE TOPMOST LAYER
For Ez-normalized layer fi := ft fi-1/|lfi-1le we have Gi == 1/1lft-1ll2 In xn, and due to the following identity (here ÿ :- / 13y112))
θÿ
1 (I "
(27)
oy
Therefore we have 0f//Of-1 (Jmxn - f.ffG) and we could set Qi = - fift, which is projection matrix and thus PSD. Furthermore, since the normalization layer is the topmost, Jj II and Q trivially commutes with J7 J..
The only issue is that Qr is not constant matrix and can change over training. Therefore Lemma doesn't apply exactly to such layer but can be regarded as an approximate way to model.
A.3
THEOREM
Now prove Theorem I in more general setting where the network is reversible (note that deep ReLU networks are included and its Q₁ is simple identity matrix):
Lemma (Squared l Gradient for dual deep reversible networks). The gradient gw, of the squared loss r with respect to W1 E Raixne- for a single input pair {æ1, 222) is:
gw; vec (0r/0W1,)) = K1.1 KK,, vec((,.)) - KJ, (eo,ve(Wa.))
(28)
Here Ki(x; W) = (a: W) @ (7 W). K1,1 = Ki(a1; Wi) and K2,1 == Ki(x2; W2).
Proof. We consider more general case where the two towers have different parameters, namely Wi and W3. Applying Lemma T for the branch with input æ1 the linear layer I, and we have (See
Eqn. 26
Φ1,1 JI, W2,
(29)
where f1.-1 fi-1(11) Wi) is the activation of layer just below the linear layer tower (similar for other symbols), and 91,1 is the back- pooo-propggated gradient after the nonlincarity.
In this case, the gradient (and the weight update, according to gradient descent) of the weight Wi between layer and layer is:
dr
(30)
AW11
(31)
Using vec(AXB) = (BT & A)vec(X) (where @ is the Kronecker product), we have:
Dr 0r aWi,)
(fu 8 H1rr) vec(W1.1) - (fr1-188111 @ (122)) vec(W2.)
vec
(32)
13

---

Under review as a conference paper at ICLR 2021
Let
(x; = & (x; W) E Rum--1
(33)
Note that (r; W) is a function of the current weight W. which includes weights at all layers. By the mixed-product property of Kronecker product (A @ B)(C @ D) AC @ BD, we have:
Ör
vec
(W1
- Ki( Tve (2.1)
(34)
= (((x1) [K((z1) voo (Wi,))
(35)
where K((xi)) = Ki(mn Wi) and ((()2) = (2 W2). In SimCLR case, we have W1 W2 W so
dr
vec
= (K((a)) Ki(x=2)] vec(Wi)
(36)
ow,
B ANALYSIS OF SIMCLR USING MAACHER-STUDENS SETTING (SECTION 3
B. THEOREM
Proof. For Luimp and Leni the derivation is obvious. For Luce, we have:
0L
r-/1
>0
(37)
Ör+
e-r-ft + Σ#= -
öL c-r+/ r +
Tk-
<0,
== b= H
(38)
Örk-
D Lx'=l -x- 11
and obviously have:
ØL.
θT.
+ Σ
0
(39)
θr+
Ork-
k=1
B.2 THE COVARIANCE OPERATOR UNDER DIFFERENT LOSS FUNCTIONS
Lemma 3. For loss function that satisfies Theorem 2 with a batch of size one with samples
X' = { 24,, $1-, 011-122..... xH-}. }. where 21, ~ Paug (-(x) are augmentation from the same
sample x, and Tyk- Paug (122%)) are augmentations from independent samples a' p(.). We have:
H
ØL
vec(sw.) = K((a11)
- -1 veo(Wi)
(40)
Ōrk-
x
Proof. First we have:
0L 0L dr+
aL drk-
veo(gw;) oW,
+ Σ dr OW
(41)
Ōr_ OW.
Then we compute each terms. Using Theorem T we know that:
dr+
aw, Ki(())(K((<I)) K)(
(42)
Örk-
= (((Z))((((Z1)) X((=x=))vec(WW))) k = 1.....n
(43)
oW,
Since Eqn. 39 holds, K((x)) (#1) will be cancelled out and we have:
"
aL
veo(gw,) = Ki(x1)
(Ki(x=)) - Ki( vec(Wi)
(44)
Dr
14

---

Under review as a conference paper at ICLR 2021
B.3
THEOREM 3
Proof. For Limpp == 7--7--1 r-, we have H = and aL
br_ = -1. Therefore using Lemma
we have:
vec(sw,) = - Ki( (x7 k7 veo(Wi)
(45)
Taking large batch limits, we know that E (x) (x+) Ex (5(())K] (x) since æ1,24 Paug (-|zz) are all augmented data points from common sample a. On the other hand, E (x1 K7 (xx-)] = Ez [x)] Ex [x)] since 21 ~ (-1x) and z Paug(-lazs
are generated from independent samples a and ryg. and independent data augmentation. Therefore,
vec(gw;)
{ Es (x) (x)) Ex [K(())] EE [x)( (vec(Wi)
(46)
V. [a)) vei(Wi)
(47)
The conclusion follows since gradient descent is used and AW; -9w.
B.4 THEOREM
When 0L/Ork- no longer constant, we consider its expansion with respect to un- augmented data point Xo {x, #/. 3. data sample that includes both positive and negative pairs. Note that 21, Paug (-(x) and
Proof.
Here X' (æ1. #1..:1-..... 2H is one
It ~ Paug (-(r,) for k H.
0L
AL Ôrk-
+e
(48)
Ork-
x
No
where e a bounded quantity for Leri (lel S 1) and Lnce (lel S 2/T).
We consider H = where there is only single negative pair (and r-). In this case Ng = f0r x').
Let r f (x) fz (ax) ((²))13
[12 and E(x, x²) == 3r
BL
Note that for Liri, it is not differentiable, so could use its soft version: (-+, log(1
elr+ +lo+=r+ It is easy to see that lim,-0 Li (-) - max(r+ ro, 0).
For the two losses:
For Lij we have
e -// E(x, x') [(r) e-TolT -e-
(49)
For Tnnce, we have
E(x,x') = E((r) = 1 r-/l
(50)
T 1//
Note that for Lú we have lim,- I(r < ra). for Luger since it is differentiable, by Taylor expansion we have = O(1 2212, x 21|2, x__ - x'112), which will be used later.
The constant term with respect data augmentation. the following, we first consider the term ç. which only depends on un-augmented data points Xg. From Lemma we now have a term in the gradient:
gi(2)) = - (x))) (x+) - KT (x: [(r, x' we)v)e(W))
(51)
Under the large batch limit, taking expectation with respect to data augmentation Pang and notice that all augmentations are done independently, given un-augmented data æ and x', we have:
(ar x²) Exass [x)( = - Ki(x)) [R] (x: - KTT (T(')) E(x, x (e))))
(52)
Symmetrically, if swap or and xr' since both are sampled from the same distribution p(-), have:
gi .x) Ki(w')) [KT KJ (=)) E( ae)ee(W)))))
(53)
15

---

Under review as a conference paper at ICLR 2021
since f(x', xz) only depends the squared &g distance (Eqn. 49 and Equ. 50 we have f(x',
{(x, x²) [(r) and thus:
(1 x²) gi (ar' x))
[T(()) - (T Ri(a')
(x)) ((r)veo(Wi)
(as/(K(())R(((())((() Ri(2'))TvooWWI)
(54)
Therefore, we have:
Ex (g) x')]
En x' (<(r)(Ki(z)) - (K((()))(((()) Ri(x'))² vec(W))155
2
1
ve
w [K((z) Ki(x')] vec(Wi)
(56)
2
Bound the error. For Lnce, let F ==
8L.
then we can compute their partial derivatives:
Dr
OF -FL/T
OF
dr = F(//
(57)
dr+
Note that [F(L/T F)1 1/72 is always bounded. From Taylor expansion, we have:
OF c= 0r+ (F+ (r+ - r4) Ør- (F+.-_) (r- -r
OF
(58)
for derivatives evaluated some point { f-) the line connecting (1r, n. a²) and (a1 84. x- r4 and r are squared ( distances evaluated at (x,, æ, x'), therefore, r4 = 0 and r fx)
f=²'11 (note that here we just use := fL for brevity).
Therefore, we have r+ 0 = 2 (xx)) f(x+)(++++ )12 and
- [f(x) f(x')) ( f(x)) (f(xx) faa'))]
1 [l((((a)) - f(x)) (f(x-) - f(x')))1
+
(59)
Therefore, have:
OF
(r+ .2)
72 2 / [f(a)) - f (xx+) (2)))a)) ( (a+ ax) da)
1
E
s
0r+
1 tr' aug [xx]]
(60)
7
where tr'V aug
VraV [ : trVa. x' p ( (-1zz) [f is a scalar. Similarly, using Lemma 4 we have the
following (using ||a| + 1|6112 / laa bl(2). Here co max [] Eg Ex'' [f 11::
dr_ (r_ 2
OF
Bpsag
(61)
[f(()) f(x'))) (Viraang [f[x] + tr
trVang ang [f|xd + 200 + tr trVauglff [f(z]] + VrV [f(=')
72
Let Mr = max [|K((a)]] so finally we have:
a jang (e (<((())(( (K7 (x+) KT 1)]1
<
F aug ||e K((x)))))))))))))))))) K2 (2x+) ) KT( ))Il
2M
(V trV [f]]] + co )] + 3trE (Vang If [zx]|]]]]]))) [x]](] (
5
2B xp())
2B
[f(()) - f(x'')l
72
Note that there no augmentation (i.e., Pang (ang (m) = 8(æ) x)), then co = 0, V Vang [ ac and the error (Eqn. 62) is also zero. A small range of augmentation yields tight bound.
For LT... the derivation is similar. The only difference is that have 1/7 rather than 1/7² in Eqn. (62 Note that this didn't change the order of the bound since {(r) (and thus the covariance operator) has one less 1/7 as well. We could also see that for hard loss Liri, since T - 0 this bound will be very loose. We leave more tight bound as the future work.
16

---

Under review as a conference paper at ICLR 2021
Remarks for H 1. Note that for H > 1, Luce has multiple negative pairs and 0L/Ork- e-Th-/T/20 (x)) where ((X) : e+ =k=1
Ek== E Tn- While the nominator -Ta-TT still only depends the distance between 21 and æg- (which is good), the normalization constant (
depends on + distance pairs simultaneously. This leads to
aL
e -1
&
(63)
Ork- Xo 1 k=1 1///
which causes issues with the symmetry trick (Eqn. negative pairs at the same time.
because the denominator involves many
However, if we think given one pair of distinct data point (ær, 2'). the normalized constant Z aver- aged over data augmentation approximately constant due homogeneity of the dataset and data augmentation, then Eqn. c4n can still be applied and similar conclusion follows.
C
THE DYNAMICS OF TWO-LAYER RELU NETWORK AND THE INTERPLAYS OF COVARIANCE OPERATORS BETWEEN NEARBY LAYERS (SECTION 4.2)
C.I THBBRRM 5
Proof. For convenience, we define the centralized version uz(z)): úz(=)) = uz(20) Ezg [2)() E Rd and the matrices Ask: := Cov (u; ux(2)) = Ezo ( (=n) (=o)] Raxdd Here both j and & run from 1 to n1.
At layer / 1 the covariance operator is V (20)) I w2 w2 Raidxaid
On the other hand, if we check the second layer Note that for input j of the second layer, we can compute its expectation with respect to 2 2| as 2,,2 On the other hand, since the last layer doesn't 't have ReLU nonlinearity, the Jacobian J2 = In xnz which is independent of the input. So we have:
we could compute K2(20) E R R
w u1 (20)
w (2()))
K2(z0)
Inxxna X
(64)
wI.,, un, (zo)
So at layer/ / = 2 we can compute the covariance operator V [K2(z0) = As Anxxn xna Painaxman Here [wT.AAj.li,l] x
E
Using these two covariance operators, we are able to write down the weight update in SimCLR setting with simple contrastive loss (here Qj == Σx A5x w1, W E Rdxws):
w1 = Qj W2.j. T2e = Q] W1.
(65)
The dynamics of Eqn. 65 can be quite general and hard to solve. In the following, we talk about some special cases.
Diagonal W2- We consider the case where W2 is a diagonal and square matrix, so nı n2 and W2 = dlag(W2,1. 222,2, ................................ (2,,n,) and remains such a structure throughout the training. Note that this also means there is no bias term for all output nodes.
In this case, we could simplify Eqn. 65 due the fact that now wor (t) for + k at any time step & (again all biases are zero in the top-layer, otherwise the orthogonal condition do hold):
W1s
Wis ú2 (wT, A w w1.)
(66)
(67)
Note that if we multiply wn, to Eqn. 66 and multiply W2.j to Eqn. 67 we arrive at:
cl [ 1
[w], A w
(68)
2
dt
dwž
(wT, Wr
(69)
2 dt
17

---

Under review as a conference paper at ICLR 2021
Therefore, d|| 11l21,11l/dt dw3, /t and thus ||w1ll22 =wz, with time- iime-independent constant c.
D HIERARCHICAL LATENT TREE MODELS (SECTION 4.3
D.I LEMMAS
Lemma (Variance Squashing). Suppose a function o b:R+ RR IR is L-Lipschitz contimuous: lØ(x) [(v)l L| y) then for p(.), we have:
vll((a)) V pa/x
(70)
Proof. Suppose z, p()) are independent samples and ue == E [o(x)). Note that V[o(x)] can be written as the following:
E [lo(2) -bv)
[[(((x)) us) - (Ø(v) m=))
[[(x)) m + LE [ló(v) mol3] 2E [(o(x) (o)((()) - pb)
2Vz(o(z)
(71)
Therefore we have:
L EE [ y1 7,2V, [xr]
v)(d(=)] E [l)(()) +(v)99 s
(72)
Lemma 5 (Sharpened Jensen's inequality (Liao and Berg 2018). ) If function & is twice differen- tiable, and x ~ v(-), then we have:
V(x inf 0" <B((()) - (x)) [x)) -
2 V/z) sup ø"
(73)
2
Lemma 6 (Sharpened Jensen's inequality for ReLU activation). For ReLU activation (bxx) max(x, 0) and x ~ p(-), we have:
0 < [(=)
Vplz
(74)
Proof. Since tp is a convex function, by Jensen's inequality we have E [v(x)] - (BB [x])
2 0. For
the other side, let μ == EP [x]] and have (note that for ReLU, v(x) v(4) s J p
(W0C) (()))((x)dr
E [v)x)) 4/ (E (x:)
(75)
/ 11r- 100 plp(x)do
(76)
(ʃ |r 10- (c-uuPp(a)ddl -)Pp(()de)))
1/2
(fole)de)
1/2
(77)
(78)
where the last inequality is due Cauchy-Schwarz
D.2 MOTIVATION AND DESCRIPTION OF A GENERAL HLTM
Here describe general Hierarchical Latent Tree Model (HLTM) of data, and the structure of multilayer neural network that learns from this data. The structure of the HT.TM is motivated by the hierarchical structure of our world in which objects may consist of parts, which in turn may consist of subparts. Moreover the parts and subparts may be in different configurations in relation each
18

---

Under review as a conference paper at ICLR 2021
Symbol
Definition
Size
Description
Z
The set of all latent variables at layer of the generative model.
N
The set of all neurons at layer of the neural network.
N
The set of neurons that corresponds to
Usechton No
The of neurons that corresponds to children of latent 2p.
Number of possible categorical values taken by 2μ E (O...., M, 1}.
O I,
mp
All-one and all all-zerr vectors.
[P(=u|=n)]
ma my
The top-down transition probability from 2u to Zy.
Par
2P(2,==1 (2,=1
scalar in [1,
Polarity of the transitional probability in the binary case.
diag[E (2o)]
mo x mi
The diagonal matrix of probability of zo taking different values.
(2(p))
Ex [
scalar
Expectation activation fj given žy (Z 's descendants are marginalized),
V2
by (2,))
Vector form By (zz).
f f
Ifs IIbe, fu Jalke
Activations for all nodes E N₁ and for the children of VV
vok. VoLNga
F. [fx zoll, (VoekeNNg
mo, mo W
Expected activation conditioned on 20
Sk
(1) ou (0))
scalar [
Discrepancy of node w.r. its latent variable kp(k)- Child selectivity vector in the binary case.
(uv(k) salReNp
Table 6: Extended notation in HLTM.
(a)
(b)
1=2
OOO N
P(s, (R))
Fully connected
A
(c)
E
V
B
000
PC
Pyun
Paur
Pyus
a
Latent
x(2
Deep nelworks
HAMHAN
Tree Model (HLTM)
Vidble variable
Figure 4: (a) The Hierarchical Latent Tree Model (HLTM). (b) Correspondence between latent variables and nodes in the intermediate layer of neural networks. (c) Definition of vg, 8, and a, in Table, 6
19

---

Under review as a conference paper at ICLR 2021
other in any given instantiation of the object, any given subpart could be occluded in any given view of an object.
The HLTM is a very simple toy model that represents a highly abstract mathematical version of this much more realistic scenario. It consists of a tree structured generative model of data (see Fig. 2 d)
and Fig. D. Simpler versions of this generative model have been used to mathematically model how both infants and linear neural networks learn hierarchically structured data (Saxe et al.) 2019). At
the top of the tree (i.e. level L), single categorical latent variable 20 takes one of mo possible integer values values in {0 ..... me - 1}. with a prior distribution P(zo). One can roughly think
of the value of zo as denoting the identity of one of mo possible objects. At level L - 1 there is set of latent variables - This set is indexed by l and each latent variable zn is itself categorical variable that takes one of m, values in {O..... y 1}. Roughly we can think of each latent variable zn as corresponding to a part, and the different values of Ey. reflect different configurations or occlusion states of that part. The conditional probability distributions P(z 20), or mo by my transition probability matrices, can roughly be thought of as collectively reflecting the distribution over the presence or absence, as well as configurationll and occlusional states of each part μr, conditioned on object identity 2g. This process can continue onwards to describe subparts of parts, etc...
D.3 A TWO-LAYER EXAMPLE TO DEMONSTRATE NOTATION
For simplicity, here we demonstrate the notation in a two-layer generative model, and two-layer network with L = 2. Thus the top, middle, and leaf levels of the generative model are labelled by [ = 2, 1. respectively, with corresponding latents 2o, 2μ and Zy, and the corresponding input, hidden, and final layers of the neural network are labelled by = 0, 1, respectively.
As shown in Fig. 4 at the leaf level 1 = 0 there are set of visible variables Zn. This set is indexed by and each visible variable 2n is itself a categorical variable that takes one of my values in the set (0. ........ m. - 1}. Roughly we can think of each 2g as a pixel, or more generally, some visible feature. For simplicity, we assume that each part zn at level I affects distinct subset of pixels or visible features zy. In essence, we assume each visible variable 2, is a child of unique level latent variable zy in the generative tree process (Fig. d)). In the rough analogy to objects and parts, in this abstraction, each part μ controls the appearance of subset of spatially localized nearby pixels or visual features y that are all children of part μ. Conversely, each such local cluster of pixels or feature values is influenced by the state of single part. The conditional probability distribution P(zulzy), m, by m, transition probability matrix, then describes the distribution over pixel or visual feature values žy of each child pixel v, conditioned on state žμ of the parent part μ.
We next consider the two-layer ReLU network that learns from data generated from the two-layer HLTM (right hand side of Fig. d)). The neural network has set of input neurons that are in one to one correspondence with the pixels or visible variables 2n that arise at the leaves of the HLTM, where / = 0. For any given object 2n at layer/ / = 2, and its associated parts states zn at layer / = 1, and visible feature values zn at layer/ / O, the input neurons of the neural network receive only the visible feature values &n as real analog inputs. Thus the neural network does not have direct access to the latent variables 2g and zy that generate these visible variables.
Over peee-prramttrizatioon. While in the pixel level. there one to one correspondence between the children v of a subpart μ and the pixel, in the hidden layer, more than one neuron could cor- respond to Zμ (i.c., pool from pixels whose values We thus let N₁, denote the set of such hidden neurons, and we let MG denote the set of all neurons in layer of the network. Thus Ny is a subset of Mr. We further let let Afch denote the subset of neurons in layer 0 that provide input to the hidden layer neurons in Ny Thus A/ch is a subset of No. Each neuron in the subset A/ch is in one to one correspondence with the children (i.e.. some =.) of latent variable žμ in the generative tree (see Fig. dd).
influenced by part μ), which is form of
over-paver over-parameterizatiin
In applying SSL in this setup, each object is specified by set of values for zg (object identity), zn (configurational and occlusional states of parts), and 2n (pixel values). Given any such object and its realization of configurational and occlusional states of parts and the resulting pixel values, assume that the process of data augmentation corresponds to resampling 2n and 2, from the conditional distributions IP(2 (o) and P( while fixing object identity 2g. This augmentation process then roughly corresponds to being able to sample the same object under different parts configurations and views.
20

---

Under review as a conference paper at ICLR 2021
The key question of interest that wish to address is, under this generative model of data and model of data augmentation, what do the hidden units of the neural network learn? particular, can they invert the generative model to convert pixels values at neural layer / = 0 into hidden representations 1 that reflect the existence of parts, with their associated states zu? More
at neural layer precisely, can the network learn hidden units whose activation across all data points correlates well with the values latent variable zn takes across all data points? We address this question next, first introducing further simplifying technical assumptions on the generative model and further notation.
D.4 A GENERAL STRUCTURE OF CONDITIONAL DISTRIBUTIONS IN THE HLTM
For convenience, we define the following symbols for k E Nich (note that W Noh is the number of the children of the node set Nyw):
Vuk
Eg [fllzu] PuoCAyUl E R
(79)
V V.Veh
[UNR)NENSE
(80)
E2 [slln]] = Vunga E Th
0j =
(81)
As an extension of binary symmetric HLTM, we make an assumption for the transitional probability: Assumption 1. For Іu E 21 and u E Zt-1, the transitional probability matrix Pau == [TP(zu zn)] has decomposition Pau m, 1 + Cuu where Cpu = O2 and 1p 0,,
Note that Cuu = 0 is obvious due to the property of conditional probability. The real condition is 1T = Op. If my my, then Par is square matrix and Assumption [ double-stochastic. Assumption I
equivalent to Pau. is
makes computation of jur easy for any 2n and zu.
Lemma 7 (Transition Probability). If Assumption 7 holds, then for μ 2,. Z1-1 and Zt-2, 2 we have:
Pça= Pup
ma 1 CuuCva
(82)
In general, for any p E Nú, and Ni with > 12, we have:
Ppa+
ma 1,11
Cgs P....kbhi...
II
(83)
Proof. Using Assumption |
we have
Puce
P Pur Pua
(84)
11,11 C.0)
(-1,11 Cva
(85)
my
ma
since 111, = my, Cpvl, 1, = O, and 1]Cua = O.. the conclusion follows.
Remark. In the symmetric binary HLTM mentioned in the main text, all Cyu can be parameterized as (here q = [-1,
Cpu (puc)
1
Puw
-Pp
qq
(86)
2
Puv
Ppv
This is because 1 O2 and C, = 02 provides 4 linear constraints (1 redundant), leaving
1 free parameter, which is the polarity Ppu E [-1,1] of latent variable 2n given its parent 2μ- Moreover, since T q 2, the parameterization is close under multiplication:
C(pp)) = qqp " " PauPua 2 99p PuuPua = C(purPva)
(87)
21

---

Under review as a conference paper at ICLR 2021
D.5 THEOREM
Proof.
First note that for each node & E NNp.
Vok
=
EE 10
Σ
E2 (rllz)
Po Uk
(88)
2v
=
1o17 1 + Cou Vk
(89)
ml
1 my
1o1 + Co.
(90)
Note that 101]ue a constant regarding to change of 2g. So we could remove it when computing covariance operator. On the other hand, for categorical distribution
(IP 0), u()),, (P(zo 1), u(1)),
(P(zo mo 1), ummo 1))
With Po == ((ag(P(zo)); the mean is EE [u] 17Puu and its covariance can written as (here
1 = 1o):
1 [u] (u 11 Pou Po(u- P1 u (Po Pol11Po)u
(91)
Note that each column of Vo.Ng. is vor. Setting u = Vok and we have:
V sa 2 f 2200 V V.NNa (Po P.)
(92)
Note that Ego [Pox] = 1 2 + Eo (Con my), since 1Tp,1 = With some computation, we could see Cov., [ook Uok/ = Cov.,, sn (Cou(R) Uks Cou(ke) ow
my
The equation above can be applied for any cardinality of latent variables. In the binary symmetric case, have (note here we define pa P(zo 1) P(zo 0), and q := [-1,1]]
Po Po 11 = 4 p1-1")qq
(93)
Note that in the binary symmetric case, according to remarks in Lemma all Cpu 1 qqt and could compute Un:
1 ua us = pou (v)(1)) us (0)) = Po0
Cou = 2 PPo
(94)
where according to Eqn. 87
have:
Pay
II
Pas
(95)
and the covariance between node is and Ne' can be computed as:
Cov zn [voR, vow"]
Cov (ou Cou
(96)
Pou(H))PO(()) 8&8K
4 TTqqTq(( q(1 (11-11111 -p)-
(97)
(1 (3)
(98)
Poy Purk) ( -
(99)
The last equality is due to the fact that due to tree structure, the path from 20 all child nodes in Arch must pass Zي.
Therefore we can compute the covariance operator:
W s0
[E
SNaa |20 = po (1 P
(100)
When L + +00, we have:
Pao
II
Paß - 0
(101)
O,....,,B.....p
and thus the covariance becomes well.
22

---

Under review as a conference paper at ICLR 2021
D.6 THEOREM
Proof. According to our setting, for each node k E Ni, there exists a unique latent variable o, with == vk) that corresponds to it. In the following we omit its dependency on & for brevity.
Since are dealing with binary case, define the following for convenience:
k
(1)
(102)
2k (0)
(103)
= (ug + ux) = (LE [fulzy = 1] - EE [fklzv = =0]
(104)
N = [UNJEENDn ERR !
(105)
Sk = j(0t - U/ = (E= [felzy = 1] - EE [falze = 0))
(106)
d = [SK]RENZL E R
(107)
We also define the sensitivity of node k to be A :- [( (vg )21. Intuitively, a large A means
that the node & is sensitive for changes of latent variable Zy. If A = 0, then the node is invariant to latent variable z..
We first consider pre-activation J5 = Ex WikJK and its expectation with respect to latent variable
of : E, 1 = =1] 1].
8j E2 [5 2/ 0)
(108)
Note that for each node A E Noch we have:
F/ = Up + SM
U/u Uk Sk
(109)
Let a₂ = [aulKENa
=
and V+ M.NNon
u A
[[fklzg 11
Tyych ag
(110)
U Aas
Vi.gg
[f 0]
Uyan ag.
(111)
Then we have oft = w] u Vah and o = w uNga.
Note that wy is a random variable with each entry Wykk Uniform
-ow [ ow
It is easy to verify that E [uca]] = 0 and V[wuu] = o /lAcy. Therefore, for two dimensional vector ün j0] U JT, we compute its first and second order moments: Ew [ö,] 0 and V [را]
W Va VT M.Nes o (u ( Wyal.
Define the positive and negative set (note that = Pkv
A {1r : a 2 0}, A_ [k: ak < 0}
(112)
Without loss of generality, assume that ΣeEA_ at EKEA_ ar. In the following, show there exists with Xy is greater than some positive threshold. Otherwise the proof is symmetric and can show X, is lower than some negative threshold.
When | is large, by Central Limit Theorem, v can regarded as zero-mean 2D Gaussian distribution and have for some
O:
Vcaw. I
1 - crf(Ve/2)
P
0
(113)
Moreover, a; A O, then the following probability is also not small
Veaw w
P
0
and
(114)
Weh
23

---

Under review as a conference paper at ICLR 2021
Therefore, when Vi O(exp(c)), with high probability, there exists wy that
Veaw
8j w] A
ll+
Dj wj y 0
(115)
Since w 2 (all fa are after ReLU and non non-negative), this leads to:
Veow
vcow
0j
Σ KEA
of
ow
W
Σ
Puu
(116)
W
kENs
By Jensen's inequality, we have (note that (xx) = max (1r, 0) is the ReL.U activation):
E 15ااا = 1] E= ( =
(117)
v B Fx =1) ((0)) 2 ow
Σ
(118)
2|Wa
kEN
On the other hand, we also want to compute Vi == E. 1رااا = 0J using sharpened Jensen's in- equality (Lemma For this need to compute the conditional covariance V Vzlfglzu]:
30
Σ S (a
[=[[ulzn]
(119)
Wcb
3
[V[nkze]] V Va E. [falzul])
(120)
Nc
30 of +
W E. E. (afllzu]
(121)
Note that @ is due to conditional independence: ftr as the computed activation, only depends on latent variable by and its descendants. Given Zμo all 2, and their respective descendants are inde- pendent of each other and so does fu. ) is due to the fact that each Wis. are sampled from uniform distribution and lursk Tw
Wohh-
Here V V, [E. [fx | = 21{11 - -ppw) can be computed analytically. It is the variance of binomial distribution: with probability { PPv) we get vy otherwise get u Therefore, we finally have:
V=lfsleul 30
of
S Σ
piw))
(122)
W
As side note, using Lemma 4 since ReLU function v has Lipschitz constant S smaller), know that:
(empirically it is
V=lfslyu 530 of Wcch Σ 22 Pzw))
(123)
Finally using Lemma 6 and 0j 0, we have:
15 = E. [5 Epp = 0] =E [b((5)) zp = o)
(124)
S w EE [ Zzp = -0) + v V= = 0)
(125)
VV =
(126)
3
I ow 330
Σ sg Piw0)
(127)
|Avcl
24

---

Under review as a conference paper at ICLR 2021
Combining Eqn. 118 and Eqn. 127
we have bound for Ay:
A (0,) (0,
30
W
sk
6
6
Piv
-1)
oî
(128)
E THE ANALYSIS OF BYOL IN SEC. 5
E. DERIVATION OF BYOL GRADIENT
Note that for BYOL,, we have:
Ör (orr) ow,
VCC
= K((x1;W) [K] (01: W)vec(Wi) - Kj (az; W'vee(W[))
(129)
under large batchsize, we have (note that omit W for any term that depends on W, but make dependence of W explicit in the math expression):
Ör ow,
vec
=Egwp(() [E (ax'-paant(1a (Ki('') (x')) vec(W;) - K] (x: W'vee(WW))
For brevity, we write Ez [:] = Exwppt) [1] and Eyg = Re Sang-annl-le [+]. Similar for V. And the equation above can be written
Ör aw:
vec
Ex (V (2( vec(Wi)
(130)
E. (K(())) [K] (x)vec((W)) KT W"ve((W])]
(131)
In terms of weight update by gradient descent, since AW - aw, we have:
Dr
vec (AW))
-E (Var [K] vecc))
(132)
Ex (x) [K] (x))ec(()) K7 (z; W")vec(W]]]
(133)
If we consider the special case W = W then the last two terms cancelled out, yielding:
vec( (W sym En (Kr') vec(W;)
(134)
And the general update (Fqn. 136 can be written as: vec (AW))
veo (oo(AWi)sym
(135)
E. (R(()) (W)) RT (a:; W")vcc(W]))
(136)
E.2 THEOREM 8
Proof. When BN is present, Eqn. 129 needs to be corrected with an additional term, aw;
Dr = 8W;
SW7'., where SWin is defined as tollows:
SWPN 1
Dig.
(137)
B
From the proof of Theorem (see Eqn. 26 know that for each sample B (note that by definition, the back-propagated gradient after nonlinearity ği equals to Digi, where gf is the back- propagated gradient before nonlinearity):
Digi J (iW. -(O---(IWW
(138)
Since the network is linear from layer to the topmost layer L, we have Dj D,. Since the only input dependent part in Jř is the gating function between the current layer and the topmost layer T., for linear network the gating is always 1 and thus Jr Jí and is independent of input data. We
25

---

Under review as a conference paper at ICLR 2021
now have (note that omit W for any terms that are dependent on W, but will write V explicitly for terms that are depend on W"):
8W7
Digifi DI
(139)
= J. J.Wiii -
(140)
Therefore we have:
vec(óW,"") = (fi-1 @ J7) [(f-1 @ vee - (fi-1 @ (eW") Note that by assumption, since Ji doesn't 't depend on the input data, we have
(141)
fi 2 J = EB fi @ J = EB [i @ J
(142)
Taking large batchsize limits and notice that the batch B could contain any augmented data generated from independent samples from p(-), we have:
vec(SWPM)
Em [Kr( Ea [K] vec(Wi)
(143)
Ea,w' [K((z') Ex,,' [K] (a'; Wi) vec(W))
(144)
important thing is that the expectation is taking over ~ p(x) and x' Paug (+(x). Intuitively, this is because fi-1 and gi are averages over the entire batch, which has both intra-sample and inter-sample variation.
With augment-meat connection (xx we could write:
voc(dW?"N)
Eg [x)) Eg KT (x)] voc(Wi) En [x)] Ex [x; (a:; Wx)] voe(W))
= Ex [[]()]]
[E,, [K] (=:] veo(Wi) E. [K] (æ; W']] vec(W())
(145)
Plug in SWI,BN into Eqn.
136 and we have corrected gradient for BYOL:
Ör
dr ow,
vec
vec
vec (DW?")
(146)
oW;
We (V Va'mpame [Ki('']]] vec(Wi) + Ve [Ki(z)] vec(Wi)
(147)
- Cova [Ki(z)) Ki(æ; W³)] Wi)
(148)
And the weight update AW, AW, + SWIN is:
vec
AW,
Pug Wa'npan (-12) [K(('') vec Va [R((x)] vec(Wi)
(149)
+ Cov [R((x), Ka W')] vec(W])
(150)
Using Eqn. 134
we have:
vec
AW;
= vec(AWi) + voc(SWaN)
(151)
vec(AWi)syer
(152)
Vr [x]] veo( + Cov [Ri(s), K((a;W)) veo(W))
(153)
E.3 COROLLARY
Proof. In this case, both the target and online networks use the same weight and there no predictor. This means W = W. Therefore, in Eqn. 145 all W, = W/ and 8W?t = 0.
Note that for SimCLR, the loss function contains both positive pair squared distance r4 and negative pair squared distance r-. The argument above shows that 5W.nN for positive pair distance r For negative pair distance r., with the same logic in Theorem. g we will see dW/BN takes the same form as Eqn. 145 and thus is zero as well.
Remarks. Note that BatchNorm does not matter in terms of gradient update, modulo its benefit during optimization. This is justified in the recent blogpost (Fetterman and Albrecht, 2020).
26

---

Under review as a conference paper at ICLR 2021
E.4 COROLLARY
Proof. By our condition, we consider the case that the extra predictor is a linear layer: Wpred (weed); )- Note that W Wredd E R xaz is a squared matrix, otherwise we cannot compute the loss function between the output fz/ from the online network with the output fL from the target network.
In this case, for connection (x(x:) the common part of the network (in Whase), we have:
Ki(x) = (a) @ (T) = fi-1(x) @ //bbase (x) pred
(154)
(f-i(() @ haso ( prod
(155)
Here ba,e (2)) ) the Jacobian from the current layer to the layer right before the extra predictor. The last equality is due the fact that fi-1 is vector. Therefore, for augment-mean K((æ)), since Wreed doesn't it depend on the input data distribution, we have:
Ki(x) baee ( pred
(156)
where K1,baso (z) = (x; W.ase). To make things concise, let R((x)) == K((x)) - Er [xx]
Obviously have Ki(x)) (x) pred And the covariance operator becomes:
V [i; = E. (1,baso(z)) (T) W prea 1.base (x:)
(157)
pred
Now let ÁW; be the last two terms in Equ. 14
vee( AW) = Va [R(( W)]
vec(Wi) + Cov [Ri( K(<x; W"]] voc(W))
(158)
Since there is no EMA, Wasse = Whsee and we have:
voc(AW) = {-Va Vv [i(x;; + Cov Ri(x; W), Ri Wi)l voc(Wi)
(159)
= Eg Ki, (x)) (reed Wrrod) RTbba (2r) vec(Wi)
(160)
Therefore, the final expression of veo (i) the following:
vec AW) vec (W) + vec(SW?
{ -E (Va'mpouel- a)) [x(])))]] Ex (2), prea (I W prea) K
J.as (x)) vec(Ws)
there is no stop gradient on the target network side, and we receive gradient from both the on- line and the target network, then for any common layer I, the weight update (e)) becomes symmetric (note that this can be derived by swapping W with W and add the two terms together):
vec (W))
2veo A WWi)aym Jym
(161)
(Va [i( W)] Va [Ki( Will vec(Wi)
(162)
Cov Ri; W), R2(:; Wi)l voc(Wi)
(163)
Cov
Ki W\), Re Wi] vec(Wi)
(164)
which gives:
voc( AW) = 2vcc( (AW))
Ex R base (x) W Wprea) - Wpred R.T Baae (az) voc(Wi)
=
2vec( A W/) ssym
Vn KK.basc (2:) W Wproa) vec(W,)
(165)
27

---

Under review as a conference paper at ICLR 2021
E.5
THEOREM 9
Proof. Consider the following discrete dynamics of a weight vector w (t):
- ((((+))-(()) a (1) + (1 A)Wema
(166)
where is the learning rate, Wema (L
Teea Wemaa (1) + (1 7ema)w(()) is the exponential
moving average of (t). For convenience, we use 17 := Tema-
Since it is recurrence equation, we apply z-transform on the temporal domain, where w(2) ==
Z|w (t) = 0 (())² _ This leads to:
2 z(w (2) w(0)) w(2) (w((2 Z| W ema (t)] ()) A))
(167)
Note that for W Wema (t) we have:
2( ((eema Wems (0)) = (1 - 1) Wema (2) + r7w(2)
(168)
If we set Wems (0) = 0, i.c., the target network is all zero at the beginning, then it gives Wema (2)
2- 1+. w (2). Plugging back to Eqn. a6d we have:
71
z (z) - w())) = w(z) aww(z
+ (1 21
(169)
And then we could solve w()):
2(2 12--++7
((2) (z 1) (17 a)(2 1) + ama w(()
(170)
Note that the denominator has two roots 2 and Z2:
21,2 = 2
2 17 a (17 + 1077
(171)
and uz(2 can be written as
z(2 - + 11)
w(2)
(z 21 xn2) w()
(172)
Without loss of generality, let ž < 22. The larger root 22 > when < 0, so the zero (z = 1-77
Tema) in the nominator won't It cancel out the pole at 22. And we have:
(z 21) - (z 22)
(173)
(z - (1 22)
22
21
(2 - 21) - 22))
1
1
(174)
22 21
2 - 2/2
2 - 21
1
1
(175)
22 21
1 2/2
1 --2
where 1/(1 112 corresponds to a power series =i in the temporal domain. Therefore, could see (t) has exponential growth due to 22 >
Now let us check how 22 changes over 17, i.e., how the parameter Yemaa = 1 77 of EMA affects the learning process. We have:
22 1+ 71 a
4amd
1
(176)
(n an)
Use the fact that (1 + 12) < 1 + 1/x for 2 have:
1 + & 4amA
2/2 - 1 <
(177)
4
( a)²
Compared to no EMA case (i.c., Yema 0 or 77 1), with Yema but close to 1 (or equivalently, 7) is close to 0), the upper bound of 22 becomes smaller but still greater than 1, and the exponential
growth is less aggressive, which stabilizes the training. Note that if Jema = 1 (or 1 = 0), then
Wema (1) Wema (0) and learning also doesn't 't happen.
28

---

Under review as a conference paper at ICLR 2021
F EXACT SOLUTIONS TO BYOL WITH LINEAR ARCHITECTURES WITHOUT BATCHNORM
An interesting property of BYOL is that it finds useful non-collapsed solutions for the online net- work and target network, despite the fact that it does not employ contrastive terms separate the representations of negative pairs. While BatchNorm can implicitly introduce contrastive terms in BYOL, as discussed in the main paper, recent work (Richemond et al., 2020b) has shown that other normalization methods which do not introduce contrastive terms, nevertheless enable BYOL to work well. We therefore analyze BYOL in a simple linear setting to obtain insight into why it does not lead to collapsed solutions, BOI learning dynamies this setting, and discuss their stability. We then discuss specific models for data distributions and augmentation procedures, and show how the fixed point solutions of BOLL learning dynamics depend on both data and augmentation distributions. We then discuss how our theory reveals a fundamental role for the predictor in avoiding collapse in BYOL solutions. Finally, we derive highly reduced three dimensional description of BYOL learning dynamics that pro- vide considerable insights into dynamical mechanisms enabling BOOL to avoid collapsed solutions without negative pairs to force apart representations of different objects.
without BatchNorm. We first derive exact fixed point solutions to
F.1 THE FIXED POINT STRUCTURE OF BOL LEARNING DYNAMICS.
We consider single linear layer online network with weights W1 E R and single layer target network with weights e E R Additionally, the online network has a predictor layer with weights W22 E R that maps the output of the online network to the output space of the target network. BYOL only uses positive pairs in which a single data point x is drawn from the data distribution p(-), and then two augmented views 21 and 22 are drawn from a conditional augmentation distribution (-ar(- The loss function driving the learning dynamics of the online weights W1 and predictor weights W2 given single positive pair {æ), 22) and a given target network θ is then given by
L. = W2 Ox:212
(178)
In contrast, the dynamics of the target network weights θ follows that of the online weights Wi through an exponential moving average. In the limit of large batch sizes and slow learning rates, the combined learning dynamics then well approximated by the continuous time ordinary differential equations (see e.g. Saxe et al. (2014) for analogous equations in the setting of supervised learning):
dW2
(0 W2 WT
(179)
di
dW1
W [e W2W
(180)
dt
d0
Tt di
θ W1,
(181)
where
E Ez, [
(182)
yd Ex, [x1 E Emp()))) (())²
(183)
and
K (x)) Exe Panng (-1w) [x]1]
(184)
Here En is the correlation matrix of a single augmented view Φ; of the data æ, while 2 is the corre- lation matrix between two augmented views of the same data point, or equivalently, the correlation matrix of the augmentation averaged vector K (z). Additionally, we have retained the possibility of having three different learning rates for the online, predictor, and target networks, represented by the time constants To. Tp. and 7. respectively.
Because of the linearity of the networks, the final outcome of learning depends on the data and augmentation procedures only through the two correlation matrices Σ¹ and Ed. Examining equa- tion equatiion 181 we find sufficient conditions for a fixed point given by W2W, = Ord and Wi O Inserting the second equation into the first and right multiplying both sides by |-
29

---

Under review as a conference paper at ICLR 2021
(assuming Ed is invertible), yields manifold of fixed point solutions in W1 and W2 satisfying the nonlinear equation
W2W1 = WE
(185)
This constitutes a set of n1 X f2 nonlinear equations in (01 x n22) + (n2 x n2) unknowns, yielding generically a nonlinear manifold of solutions in Wi and W2 of dimensionality n2 X corresponding to the number of predictor parameters. For concreteness, we will assume that n2 I n1, so that the online and target networks perform dimensionality reduction. Then a special class of solutions to equation
185 can be obtained by assuming the f2 rows of W1 correspond to n2 left-eigenvectors of E and W2 is a diagonal matrix with the corresponding eigenvalues. This special class of solutions can then be generalized by a transformation W2 - SW2S-1 and W1 + SW1 where S is any invertible n2 by 122 matrix. Indeed this transformation is symmetry of equation [85] which defines the solution manifold.
In addition to these families of solutions, the collapsed solution W1 = W2 = - 0 also exists, and natural question is, why doesn't 't BYOL generically converge to this collapsed solution? This question can be addressed by analyzing the stability of both the collapsed solution and the families of solutions presented above. The basic calculation involves computing the Jacobian of the vector field defining the dynamics of equation 179 through equation [8] A fixed point solution is stable and only all eigenvalues of the Jacobian evaluated at a fixed point solution are negative. Using methods similar to that of Baldi and Hornik (1989), which carried out a similar stability analysis for learning dynamies in two weight layer linear networks in the supervised setting, it is possible to show that all of the above fixed point solutions are unstable except for those derived from the special solutions where the n2 rows of Wi correspond the top n2 principal eigenmodes of ><
Thus this analysis sketch provides conceptual insights into why BYOL, at least in this simple setting, learns nontrivial, and potentially useful representations with only positive examples, and does not converge to the naive collapsed solution. Basically, the collapsed solution, as well as other subdomi- nant solutions, are unstable. while solutions corresponding to the principal eigenmodes of E [> are stable. Thus, from generic initial conditions, one would expect that the row space of the online network would converge to the span of the top n2 principal eigenmodes of [d
F.2 ILLUSTRATIVE MODELS FOR DATA AND DATA AUGMENTATION
While the above section suggests that BYOL converges to the top eigenmodes of [-[=>]-1, here we make this result more concrete by giving illustrative examples of data distributions and data augmentation procedures, and the resulting properties of 2dd
Multiplicative scrambling. Consider for example multiplicative subspace scrambling model, used in the illustration of SIMCLR in Sec. 4.1 In this model, data augmentation scrambles subspace by multiplying by a random Gaussian matrix, while identically preserving the orthogonal complement of the subspace. In applications, the scrambled subspace could correspond to space of nuisance features, while the preserved subspace could correspond semantically important features.
More precisely, we consider a random scrambling operator A which only scrambles data vectors within fixed ht dimensional subspace spanned by the orthonormal columns of the no x k ma- trix U. Within this subspace, data vectors are scrambled by a random Gaussian k matrix B. Thus A takes the form A p + U UBT where pe the no - I dimensional conserved, semantically important, subspace orthogonal to the span of the columns of U, and the elements of B are i.i.d. zero mean unit variance Gaussian random variables δ. Under this simple model, the augmentation average K K(x) ) in equa- tion 184 becomes K(x) p'.. Thus, intuitively, under multiplicative subspace scrambling. the only aspect of a data vector that survives averaging over augmentations is the projection of this data vector onto the preserved subspace. Then the correlation matrix of two different augmented views is Ed PC pe while the correlation matrix of two identical views is Σ* = Σ' where is the correlation matrix of the data distribution. Thus BYOL learns the prin- cipal eigenmodes of --
UUT is a projection operator onto
so that EE Ba)
===EE-pp [x=T]]
p- P. -. In the special case in which Pe commutes with Σ² we have the simple result that Σー = p which is completely independent of the data correlation matrix Σ Thus in this simple setting BYOL. learns the subspace of features that are identically conserved under data augmentation. independent of how much data variance there is in the different dimensions of this conserved subspace.
30

---

Under review as a conference paper at ICLR 2021
It is interesting to compare SimCLR in the same setting, which learns the principal eigenmodes of P'E" p as described in Sec. 4.T] Thus SimCLR also projects to the conserved subspace, but further inftuenced by the correlation matrix of the data within this subspace. In actual applications. which performs better will depend on whether or not features of high variance within the conserved subspace are important for downstream tasks; SimCLR (BYOL) should perform better if conserved features of high variance are (are not) important.
Additive scrambling. We also consider, as an illustrative example, data augmentation procedures which simply add Gaussian noise with a prescribed noise covariance matrix hn, Under this model, we have Σ- Ed E" while Ed Σ". Thus in this setting. BYOL learns principal eigenmodes of E- + Thus intuitively, dimensions with larger noise variance attenuated in learned BOL representations. On the otherhand, correlations the data that are not attenuated by noise are preferentially learned, but the degree to which they are learned is not strongly influenced by the magnitude of the data correlation (i.e. consider dimensions that lie along small eigenvalues of )").
F.3 THE IMPORTANCE OF THE PREDICTOR IN BYOL.
Here we note that our theory explains why the predictor plays a crucial role in BYOL learning in this simple setting, as is observed empirically in more complex settings. To see this, we can model the removal of the predictor by simply setting W₂ = I in all the above equations. The fixed point solutions then obey W1 Wi [ This will only have nontrivial, non-collapsed solutions if EEE""- has eigenvectors with eigenvalue 1. Rows of Wi consisting of linear combinations of these eigenvectors will then constitute solutions.
This constraint of eigenvalue 1 yields much more restrictive condition on data distributions and augmentation procedures for B BYL to have non-collapsed solutions. It however be satisfied in multiplicative scrambling if an eigenvector of the data matrix Σ² lies in the column space of the projection operator pe (in which case it is an eigenvector of eigenvalue 1 of 2- PSE"P. This condition cannot however be generically satisfied for additive scrambling case, in which generically all the eigenvalues of [E")] this case, without predictor, it can be checked that the collapsed solution Wi = O 0 is stable. In contrast, with a predictor, the collapsed solution can be checked to be unstable, and therefore will not be found from generic initial conditions.
E- + Σ"1-1 are less than 1. In
Thus overall, in this simple setting, our theory provides conceptual insight into how the introduc- tion of a predictor is crucial for creating new non-collapsed solutions for BYOL, whose existence destabilizes the collapsed solutions.
F.4 REDUCTION OF B BYO LEARNING DYNAMICS TO LOW DIMENSIONS
The full learning dynamics in equation 179 to equation 181 constitutes a of high dimensional nonlinea ODEs which are difficult to solve from arbitrary initial conditions. However, there is a special class of decoupled initial conditions which permits additional insight. Consider the special case in which Σe and Ed commute, and so are simultaneously diagonalizable and share a common set of cigenvectors, which we denote by u E R Consider also special set of initial conditions where each row of W, and the corresponding row of θ are both proportional to one of the eigen- modes u", with scalar proportionality constants w and 6 respectively, and W2 is diagonal, with the corresponding diagonal element given by wg. Then it is straightforward to see that under the dynamics in equation [79 to equation [8T] that the structure of this initial condition will remain the same, with only the scalars wf. 00 and wy changing over time. Moreover, the scalars decouple across the different indices a, and the dynamics are driven by the eigenvalues A and Xy of Σ, and E.a respectively. Inserting this special class of initial conditions into the dynamics in equation 179 to equation [8] and dropping the index, we find the dynamics of the triplet of scalars is given by
To dwz
[0>a
W2W As] wi
(186)
dt
dwp
Pp dt
w2
10da [o
(187)
d0
0
+
(188)
di
31

---

Under review as a conference paper at ICLR 2021
Fixed target
Tied predictor
No predictor
W2
theta
theta
w1
W
W
Figure 5: visualization of BYOL dynamics in low dimensions. Left: Black arrows denote the vector field of the flow in the wy and w2 of plane online and predictor weights Eqns. [86] and [87 when the target network weight
fixed to 1. For 3 panels, X, = 1, Aa 1/2, and To Tp Te 1, and all vectors are normalized to unit length to indicate direction of flow alone. The red curve shows the hyperoblic manifold of stable fixed points 22y0; O while the red point at the origin is an unstable fixed point. For fixed target network, the online and predictor weights will cooperatively amplify each other to escape the collapsed solution the origin. Middle: A visualization of the full low dimensional YOL dynamics in Eqns 186 88 when the online and predictor weights are tied that wy w2 w. The green curve shows the
nullcline 0 = w corresponding to de
ar = 0 and the blue curve shows part of the nullcline dor ar = 0 correponndng
w² 0AaA,'. The intersection of these two nullelines yields two fixed points (red dots): an unstable collapsed solution at the origin w 0 = 0, and stable nontrivial solution with 0 = and w Aad Right: A visualization of dynamics in Equs 186 188 when the the predictor is removed, so that wa is fixed to 1. The resulting two dimensional flow field on
Wi and 0 is shown (black arrows). The green curve shows the ar 0, while the blue curve shows the nullcline ws OAaA,' The slope The resulting nulleline structure yields single fixed point the origin which is stable. Thus there only exists collapsed solution. In the special case where A.da 1, the two nullclines coincide, yielding one dimensional manifold of solutions.
nullcline = corresponding to
of this nullcline A²
Alternatively, this low dimensional dynamies can be obtained from equation 179 to equation 181 not only by considering a special class of decoupled initial conditions, but also by considering the special case where every matrix is simply 1 by 1 matrix, making the scalar replacements W1 -> W1, Xa-
W2 + W22 Q + 0, Σ² - Ay and dd
The fixed point conditions of this dynamics are given by 0 = wa and W2 = 0AaA-1 Thus the collapsed point W)- = W2 0 0 is solution. Additionally wy = Aa and wi = taking any value is also family of non-collapsed solutions. We can understand the three dimensional dynamics intuitively as follows when Ti >> To and T, = Tp. In this case, the target network evolves very slowly compared to the online network, as is done in practice, and for simplicity we use the same learning rate for the predictor we do for the online network. In this situation, as approximately constant on the fast time scale of T, on which the online and predictor weights wi and Wy evolve. Then the joint dynamics in equation 186 and equation 187 obeys gradient descent on the error function
can treat A
E Ne (0xa w2w1)
(189)
Iso-contours of constant error are hyperbolas in the w1 by We plane, and for fixed 6, the origin w1 = W2 = 0 is a saddle point, yielding an unstable fixed point (see Fig. (left)). From generic initial conditions, Wi and W2 will then cooperatively amplify each other to rapidly escape the collapsed solution at the origin, and approach the zero error hyperbolic contour w2w1 OAa where 0 is close to its initial value. Then the slower target network will adjust, slowly moving this contour until 0 = wi. The more rapid dynamics of wi and w2 will hug the moving contour W2w; = 0A as 9 slowly adjusts. In this fashion. the joint fast dynamics of wM and W2, combined with the slow dynamics of 0, lead to a nonzero fixed point for all 3 values, despite the existence collapsed fixed point at the origin. Moreover, the larger the ratio Aa which is determined by the data, the larger the final values of both wi and wa will tend to be.
We can obtain further insight by noting that the submanifold wi w2, in which the online and predictor weights are tied, constitutes an invariant submanifold of the dynamics in Eqns. [86 to 1881 if w1 W2 any instant of time, then this condition holds for all future time. Therefore
32

---

Under review as a conference paper at ICLR 2021
(a)
(b)
ja "s1" Ex
[ =
Fully connected
"s10" Byool
Z
Zann
Esn1
Es1o
Ze11
Ks100
Zanon
Exno1
Ze01n
20011
Zanon
Zeno
Zano
20111
Figure 6: The Hierarchical Latent Tree Model (HLTM) used in our experiments (Sec. G.2 and Sec.
6
can both analyze and visualize the dynamics on this two dimensional invariant submanifold, with coordinates w wi wy and 0 (Fig. 5 (middle)). This analysis clearly shows an unstable collapsed solution at the origin, with w = 8 0, and a stable non-collapsed solution at w = 8 = >a>,
We note again, that the generic existence of these non-collapsed solutions in Fig. Fig-5deepends critically on the presence of a predictor with adjustable weights Wg. Removing the predictor corresponds to forcing W2 = 1, and non-collapsed solutions cannot exist unless Aa = X,, as demonstrated in Fig. 5 (right). Thus, remarkably, in YOL in this simple setting, the introduction of predictor network plays a erucial role, even though neither adds the expressive capacity of the online network, nor improves its ability to match the target network. Instead, it plays a crucial role by dramatically modifying the learning dynamics (compare c.g. Fig middle and right panels), thereby enabling convergence to noncollapsed solutions through dynamical mechanism whereby the online and predictor network cooperatively amplify each others' weights to escape collapsed solutions Fig. 5 (left)).
Overall, this analysis of BYOL learning dynamics provides considerable insight into the dynami- cal mechanisms enabling BYOL to avoid collapsed solutions, without negative pairs to force apart representations, in what is likely to be the simplest nontrivial setting.
G ADDITIONAL EXPERIMENTS
G.1 EXPERIMENTS ON TWO-LAYER NETWORK
We follow the setting in Theorem 5 i.e., two-layer ReLU network (L = 2) that contains the same number of hidden nodes as the number of output nodes (n, = 122). The top-layer weight W2 is a diagonal matrix with no bias (note that "no bias" is important here, otherwise we won't have un! W2,x = 0 for j A k).
We conduct experiments to verify our theoretical reasoning in Sec. 4.2
We use Lice (r = 0.05 and H = 1) and Liipp and use SGD optimizer with learning rate of 0.01. All experiments with 5000 minibatches with batchsize 128. We test cases with and without & normalization at the output layer. For each setting, i.e., (loss, normalization), we run 30 random seeds. The data are generated by mixture of 10 Gaussian distributions (with uniform prior on each mixture), with mean Pa (O, I) and covariance matrix Σ₁ 0.1/. We set the first cluster to be zero-mean.
Without l normalization. Fig. 7 shows the weight growth of the top (W2) and bottom (W1) layer. As predicted by Theorem 5] the weight quickly grows infinity. Note that the y-axis is log scale so exponential growth is shown as linear. From the figure, it clear that with Lempp their growth is super exponential due to the inter-plays between the top and the bottom layers. On the other hand, with Luce. the growth slows down due to the fact that its associated covariance operator has weight which decays exponentially when the representations of two distinct samples become far apart.
With le normalization. With the normalization, the weights will not grow substantially and we focus ourselves more on the meaning of each intermediate nodes after training. From the theoretical reasoning in Sec. 4.2 in the ReI.U case, we should see each node gradually moves towards (or specializes to) cluster after training. Fig. 8 shows that node j that is only active for I cluster centers (out of 10) have much higher [w2,5] than some other node that is active on many cluster centers. This shows that those "specialized" nodes has undergone learning and their fan-out weight magnitude |/2 becomes (or remains) high, according the dynamics in Theorem
33

---

Under review as a conference paper at ICLR 2021
normalization, growth [W;]
& (W,)
10
log
0-
1200
1200
Without normalication. the growth of (W:]
Without norma coctiiization... growth of (Wa)
0.4
1.52
0.0
1.00
10g19.1
0.96
0.84
-0.6-
1000
2000
3000
5000
2000 3000
40000
5000
Number minbattrhes.
Number minsbatrhes
Figure 7: Top row: Without & normalization. training with SimCLR and Leimp leads to fast growth time (each curve is one training curve of 30 trials with different
of the weight magnitude random seeds). Furthermore, this growth is super exponential due to the interplay between top and bottom layers, suggested by the dynamics in Eqn. 8 Note that the y-axis is in log scale. Bottom row: Without & normalization, Luce has more stable weight magnitude over training since its covariance operator weighted (See Theorem
Relationship specialization of [Way]
Relationship specialization
0.35
Magiitat the byer u5gg2 M6.1
twp-tter woggt M6,1
0.32
0.10
0.30
0.08
0.06
0.04
0.02
#Cluster that activate
Figure 8: When W2,, is high, the corresponding node j is highly selective one specific cluster of the data generative models. On the other hand, those node j with low selectivity has very small W2,5 and does not contribute substantially the output of the network. Training with L (Left Plot) seems to yield stronger selectivity than with Laimp (Right Plot).
34

---

Under review as a conference paper at ICLR 2021
depliy oepthem degthe
della 1o7
hid-2
delta k.
fide5
Nid-10
Norm 0P
Nam op
Norm
1.5
1.0
0.5
0
0.0
10
20
30
50
10
20
40
50
30
2.5
Beeaatons
Perations
3.0
Perations
2.5
2.5
depthorg
deta lowar-00 0.9
Nd:110
1.5
2.0
1.5
1.0
1.0
0.5
0.5
0.5
10
20
30
50
0
10
20
30
40
10
30
40
teraPinns
therations
Itersttone
Figure 9: Ablation of how the Frobenius norm of the covariance operator OP changes over training, under different factors: depth L. sample range of Par (Pur (infformmella.llowee 1J) and over- parameterization W- Top row: covariance operator of immediate left latent variable of the root node Bottom row: covariance operator of immediate right child of the root node 2o.
G.2 HLTM
We also check how the norm of the covariance operator (OP) changes during training in differ- ent situations. For this set of experiments, we construct complete binary tree of depth L. The class/sample-specific latent 20 is at the root, while other nuisance latent variables are labeled with a binary encoding (e.g.. f "s010" for 2p that is the left-right-left child of the root 2g). Please check Fig. (6 for details.
Again we use SimCLR with the L loss (T 0.1 and H 1) to train the model. l normal- ization used in the output layer. The results are shown in Fig. g and Fig. 10 We could see that norm of the covariance operator indeed go up, showing that it gets amplified during train- ing. We perform grid search of depth [3, 4, 5,. delta-lower [0.7, 0.8, 0.9] (and the po- larity Ppr ~ Uniform]delt lower, 1] at each layer) and over-parameterization parameter hid [Wall = [2, 5, 10). For each experiment configuration, we run 30 random seeds.
G.3 BYOL EXPERIMENTS SETUP
For all STL-10 task, we use ResNet18 as Wbase. The extra predictor is two layer. It takes 128 dimensional input, has hidden layer of size 512, and its output is also 128 dimensional. We use ReLU in-between the two layers. When we add BN to the predictor, we add it before ReLU activation. When we say there is no BN in Tbl. 3 we remove BN in both predictor and projector layer (but not in the encoder). Same as BYOL paper Grrll al. 2020), symmetric loss function is used with & normalization in the topmost layer.
We use simple SGD optimizer. The learning rate is 0.03 (unless otherwise stated), momentum is 0.9 and weight decay 0.0004. The training batchsize is 128. The ImageNet experiment runs 32 GPUs with a batchsize 4096.
G.4 ADDITIONAL BYOL EXPERIMENTS
Based on our theoretical analysis, we try training the predictor in different ways and check whether it still works.
From the analysis in Sec. 5 we know that the reason why BYOL works is due to the dominance of Cov (x)),, Kí (x; WJ and its resemblance of the covariance operator V. [x))), which is PSD matrix.
35

---

Under review as a conference paper at ICLR 2021
0.5
deptbied Supthw
della lowe 3.7
hed-2
0.5
0.5
Jowor-
Norm of
0.3
0,4
0.1
0.1
0.0
0.0
0.0
20
30
50
10
30
50
10
30
40
herations
Iterations
Rteritoons
0.14
0.08
depth-5
dett_lower--
detb, Jower=0
0.150
0.12
datta lower=0.8
Ndws
0.08
data lower-
0.125
add- 10
0.08
Nerm
0.04
0.06
0.075
0.04
0.02
0.025
20
40
19
40
10
40
Merations
Figure 10: Ablation of how the Frobenius norm of the covariance operator OP changes over training. Same setting as Fig. 9 but focus on lower level. Note that since we have used Eg normalization at the topmost layer, the growth of the covariance operator is likely not due to the growth of the weight magnitudes, but due to more discriminative representations of the input features fp. with respect to different 20- Top row: covariance operator left-right-left latent variable from the root node zp; Bottom row: covariance operator right-left-right-let latent variable from the root node zu-
The dominance should be stronger if the predictor has smaller weights than normally initialized using Xavier/Kaiming initialization. Also, Cov ( Ky(æ; W")] should behave more like PSD matrix, if the predictor's 's weights are all small positive numbers and no BN is used.
The following table justifies theoretical findings. In particular, Tbl. TO better performance in STL-10 with smaller learning rate and smaller sample range of the predictor weights.
Table 7: Training one-layer predictor with positive initial weights and no EMA (7ema = 0). All experiments run for seeds.
Sample range predictor weight
[0, 0.01]
0.02)
[0. 0.05)
With BN in predictor
62.78 1.40
62.94 + 1.03
62.31 = 1.80
Without BN in predictor
71.95 + 0.27
72.06 + 0.44
71.91 + 0.59
Table 8: Training one-layer predictor with positive initial weights with EMA (Tema 0.996) and predictor resetting every T' = 10 epochs. All experiments run for 3 seeds. Note that Xavier range is Uniform| (0.0rrm/001155 0.15, 0.15] and our initialization range is much smaller than that.
Sample range of predictor weight
10, 0.003]
10, 0.005)
0.00.
With BN in predictor
65.61 = 1.34
70.56 = 0.57
70.87 1.51
Without BN in predictor
74.39 + 0.67
74.52 + 0.63
74.80 + 0.57
36

---

Under review as a conference paper at ICLR 2021
Table Same as Tbl. 8 but with different weight range. All experiments run for 3 seeds.
Sample range of predictor weight
00.0.01
[0. 0.022
[0, 0.05
With BN in predictor
68.98 2.34
66.56 1.70
68.41 1.19
Without BN in predictor
74.66 + 0.81
73.60 + 0.32
74.34 + 0.77
Table 10: Top-1 Performance STL-10 with two-layer predictor with BN and EMA (Yema 0.996). Learning rate is smaller (0.02) and predictor weight sampled from
Uniform[-ranee range]. Note that for this, Xavier range is Uniform[-0.097, 0.097] and our
range is smaller.
Weight range
0.01
0.02
0.03
0.05
T 3
79.48 + 0.40
79.70
+ 0.47
79.66 + 0.37
78.63 + 0.10
5
78.97
0.62
79.63
0.23
79.65
0.37
79.01
0.27
T= = 10
79.25
0.20
79.63
+.33+020 0.22
79.58
0.25
79.18 + 0.22
T 20
79.15 + 0.66
1.91
79.78 0.05
7..54
37


Reviews:
[{"review_id": "iFGgvXfqfS9", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provided in-depth theoretical analysis of self-supervised learning, focusing on two network structures (SimCLR, BYOL). They proved that a covariance operator plays an important role in the SGD learning of self-supervised algorithms. Simulation experiments were provided to justify the theoretical findings. The paper is well written, with rigorous mathematical derivations.\n\nHere are a few comments on the technical details:\n1) In Theorem 3 there is an assumption that the derivative of L with respect to rk- is a constant. Is this a reasonable assumption in real situations? Can we see how this assumption is justified (or violated) in real data? \n\n2) Below equation (37) in the appendix, the above assumption becomes derivative of L with respect to rk-^2, and H is replaced with n in the constant. It seems that there is some discrepancy with the statement of Theorem 3, and some explanation may be helpful.\n\n3) In the first paragraph of Section 4, it is stated that \"all nuisance latents z' are integrated out in K(z_0)\". This statement seems to be a little vague to me. More rigorous definitions and derivations may be needed here to support the claim.\n\n4) A related follow-up question is, how would the augmentation distribution impact the analysis? What would be a good augmentation transform?", "extra_scores": {}, "extra_text": {}}, {"review_id": "gHbY_xI60M7", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aimed to understand the self-supervised learning algorithm under a teacher-student network setting. The authors argued that the gradient are specified by a covariance operator, that can amplify extracting the intrinsic features that are invariant to the data augmentation.\n\nI have several concerns on this paper, mainly on the over-simplified setting, unrealistic assumption, and inaccurate claim. Also, the presentation is weird.\n\nThe detailed comments:\n1. I feel most of the theorem are just simple calculus. It’s inappropriate to claim such calculation results as theorem. At least one theorem should contain some information on the property of the terms of interest.\n2. As far as I know, there’s no existing empirical work used the ell_2 loss on the feature as the dissimilarity, though when the features have norm 1 (which cannot simply hold in practice) there are some connections between the ell_2 loss and inner product. I personally would argue that, the authors should first make an empirical justification on this simplification, say such dissimilarity measure can empirically work. I don’t think this is a valid simplification. The authors may argue that methods like simCLR have normalization before computing pairwise similarity, but this will dramatically influence the gradient update. Maybe the remaining conclusion still holds, but at least the authors should include such part.\n3. I would like to say that the assumption for Theorem 3, i.e. the gradient of the negative samples are identical, are too strong and unrealistic. Definitely this will not happen, even though the negative samples are from the same distribution, there should be some variance. I cannot accept such assumption. Even take H=1 is better than this assumption.\n4. Beta is used without any introduction.\n5. As the authors say, the covariance operator are changing over time, it’s hard to claim that this covariance operator let the parameter align with some specific direction that is good to learn a good representation. Take the NTK limit may be one possible way to get some more interested result, however, the authors haven’t done that.\n6. And I would argue that, with only analysis on gradient, it’s rather hard to make some strong claim. There are several existing work on homogenous neural network that characterize the optimization and solution with e.g. separable data, which is much more convincing.\n7. I feel the description starting from Section 4 on two groups of latent variables are so intuitive and also unrealistic. How can we identify such groups of latent variables and how can we make sure in practice we don’t perturb the class/sample-specific latent? On the other hand, what if we perturb the class/sample-specific latent? Imagine we have a Gaussian mixture of two isotropic components, if we augment the data with the isotropic Gaussian, can we make an informative projection onto low dimension with self-supervised learning? I think the current intuitive and unrealistic setting restricted the potential application in practice.\n8. What’s the definition of bar{K}_l(z_0) as the input of this term should be x? What’s the form of the term after integrated out z^\\prime? I feel there are so many ambiguities here and I’m afraid I cannot accept such claim.\n9. I think the arguments in Section 4.1 need to be justified more formally, if this is a `theoretical’ paper. I wonder what does the author want to say in Section 4.1, the importance of non-linear activation? \n10. In Section 4.2, why constrained to 1 output? I would like to ask, as in the derivation in Section 3, there should be no straightforward barrier on considering this more general case?\n11. In Theorem 4, is the A matrix fixed during the dynamics? I’m quite skeptical on that, as the w in the definition of u are changed over time, which can influence the indicator. Also, why we have the covariance is equal to zero? Is that the normal case? Also, there are so many ambiguities here, see 9, can the authors give all the formal description of the neural network we considered, the input data distribution, etc. in a clear way? To be honest, I cannot understand the proof of Theorem 4 as well, due to these ambiguities.\n12. For the description in the last of Page 7, I totally get confused. What does the authors want to say on that? Even the parameter converge to some point, we cannot say during the optimization it keeps the indicator 1? Can the authors stop using such ambiguous description and give some formal description and claim?\n13. What’s the meaning of considering such HLTM? Can it represent the general case of learning? I need to say the authors does not convince me that such setting is general and it’s necessary to consider the multi-layer network with such setting. I would like to say, it’s better first considering the fully-connect network rather than considering the network with local receptive field.\n14. I would like to say the organization of Section 4.3 is really weird. Can the authors give a formal description in the neural network and generative model in Section 4.3, even in the appendix with simpler but clear model? I don’t even know the data generating process of x given z, thus does not the meaning of given a sample x how to resampling z^\\prime. As the notation are only described in Table 1, I cannot get the meaning of each term in the theorem. Give some description on each of term with a formalized mathematical description on the generative model and network, please.\n15. Also, I does not feel the theorem in Section 4.3 give some strong arguments. What we really care in the self-supervised learning is the quality of representation, the sample complexity, the convergence analysis, none of them have been addressed by the author formally. Instead, I feel Theorem 6 presented here is not of particular interest. Also, the discussion is quite intuitive.\n16. What’s the sym subscript in Equation 10? Please introduce the notation before used it. Also, what’s the term deltaW_l^{BN} in Equation 12? Please be self-contained.\n17. The observation of Theorem 7 can be interesting, however, in practice, what we really do during BN is the latter one, i.e. x - x.mean().detach()? And in fact, the mean we subtract in BN is a moving average statistics. I feel it can explain something, but not why BYOL works. The claim that such observation give an analysis of why BYOL work is not accurate. In the contrast, I think it even predict that BYOL will not work or at least need to be fixed.\n18. Overall, what the authors have proposed are better understood as some intuition or observation, not some rigorous theory.\n\nTo sum up, I feel the presentation is weird. The settings are over-simplified and the authors even didn’t introduce the setting with formal description. The assumption can be too strong while some explanations are too intuitive. The authors want to argue several points, however, none of them are strong enough and can be claimed as 'theorem' (I feel they are only 'observations'). Meanwhile, I feel the authors include such different points in the main text with the expense of readability.\n\nIf this is an empirical paper introduced some observation on the self-supervised learning with detailed ablation study and some kinds of theoretical characterization, I’m happy to accept this paper. However, as I don’t feel the authors provide either strong theoretical results or detailed ablation study, meanwhile, the presentation is totally a disaster, I think this paper is not suitable for publishing right now.", "extra_scores": {}, "extra_text": {}}, {"review_id": "avHyr_g10QK", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper does theoretical analysis about self supervised learning (SSL), esp. those methods using contrastive learning. It zooms into one-layer and two-layer networks and proves contrastive learning can converge to weights corresponding to largest eigenvector of a covariance matrix. Experiments on synthetic and real datasets are consistent with theoretical conclusions.\n\nReasons for score: \nThe covariance operator sheds light to the black-box learning process of contrastive learning. Approximating the data distribution with a hierarchical latent tree model is an interesting technique. This work may inspire practical tools to improve SSL. \n\nIssues:\n1. My major concern is the analysis about BYOL. The authors of BYOL disagree with the conclusion in this paper that BatchNorm provides implicit contrastive objective for BYOL, in a newly released paper \"BYOL works even without batch statistics\". I'd ask the authors, does this invalidate your analysis about BYOL? Or does the GroupNorm + weight standardization also provide implicit contrastive objective, similar as BN? \n2. To what degree the validity of the theoretical analysis depends on the type of the loss? Say if I change the InfoNCE loss to some other loss, will that invalidate the whole analysis?\n3. A typo in page 4: \"we setup the following...\" => \"we set up the following...\"\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "GBbGQ7CYnyJ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Strengths:\n\tThis paper tried to analyze the “Black-box” of the contrastive learning by inspecting the weight update during contrastive learning. The analysis and conclusion seem promising.\n\tThis paper made a theoretically analysis on BYOL and conducted a variety of ablation studies to study the impacts of BN layer and predictor in BYOL. And some interesting experimental results and conclusions are presented, which sheds light on the further explorations on self-supervised learning.\nWeakness:\nWhile I still have some questions:\n\tIn [1], it has been proved that BYOL can work without BN in predictor, which seems contradictory the conclusion given in this paper. I recommend the author to compare with this conclusion.\n\tIn Table 5, it seems that reinitializing the predictor will improve the performance a bit. I wonder if the improvements will gradually decrease or even vanish for longer training epochs.\n\n[1] BYOL works even without batch statistics. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "0qb0RI4aybE", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a novel theoretical framework to understand self-supervised learning\nmethods that employ dual pairs of deep ReLU networks. The finding is interesting and novel. The experiments support the conclusion. However, there are several issues.\n\nThe paper should explain the motivation to choose simCLR for analysis.\nThe paper defines the covariance operator from contrast loss and the paper declare that the theory is suitable for deep ReLU networks with dual pairs. How to define the covariance operator for other kinds of loss function of deep ReLU networks with dual pairs, such as triplet loss.\nThe experiment setting should be listed. Such as the learning rate, the training time and the date augmentation used in the experiments. The paper also needs experiments about the magnitude of the covariance operator and the training time.\nThe paper analysis the activation gap and the weights of different layer for HLTM. The paper needs experiments about the activation gap grows over time and the weight of the top layer and lower layer change over time.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents new analysis for self-supervised learning. All reviewers are positive about some new perspectives of the analysis. However, some serious concerns have been raised about the rigorousness and the presentation clarity. The paper would be significantly improved, if the authors could address the concerns.
Decision: Reject