# Self-supervised Representation Learning with Relative Predictive Coding

Yao-Hung Hubert Tsai1, Martin Q. Ma1, Muqiao Yang1,
Han Zhao23, Louis-Philippe Morency1, Ruslan Salakhutdinov1
1Carnegie Mellon University, 2D.E. Shaw & Co., 3 University of Illinois at
Urbana-Champaign

###### Abstract

This paper introduces Relative Predictive Coding (RPC), a new contrastive
representation learning objective that maintains a good balance among training
stability, minibatch size sensitivity, and downstream task performance. The
key to the success of RPC is two-fold. First, RPC introduces the relative
parameters to regularize the objective for boundedness and low variance.
Second, RPC contains no logarithm and exponential score functions, which are
the main cause of training instability in prior contrastive objectives. We
empirically verify the effectiveness of RPC on benchmark vision and speech
self-supervised learning tasks. Lastly, we relate RPC with mutual information
(MI) estimation, showing RPC can be used to estimate MI with low variance
111Project page: https://github.com/martinmamql/relative_predictive_coding.

##  1 Introduction

Unsupervised learning has drawn tremendous attention recently because it can
extract rich representations without label supervision. Self-supervised
learning, a subset of unsupervised learning, learns representations by
allowing the data to provide supervision (Devlin et al., 2018). Among its
mainstream strategies, self-supervised contrastive learning has been
successful in visual object recognition (He et al., 2020; Tian et al., 2019;
Chen et al., 2020c), speech recognition (Oord et al., 2018; Rivière et al.,
2020), language modeling (Kong et al., 2019), graph representation learning
(Velickovic et al., 2019) and reinforcement learning (Kipf et al., 2019). The
idea of self-supervised contrastive learning is to learn latent
representations such that related instances (e.g., patches from the same
image; defined as positive pairs) will have representations within close
distance, while unrelated instances (e.g., patches from two different images;
defined as negative pairs) will have distant representations (Arora et al.,
2019).

Prior work has formulated the contrastive learning objectives as maximizing
the divergence between the distribution of related and unrelated instances. In
this regard, different divergence measurement often leads to different loss
function design. For example, variational mutual information (MI) estimation
(Poole et al., 2019) inspires Contrastive Predictive Coding (CPC) (Oord et
al., 2018). Note that MI is also the KL-divergence between the distributions
of related and unrelated instances (Cover & Thomas, 2012). While the choices
of the contrastive learning objectives are abundant (Hjelm et al., 2018; Poole
et al., 2019; Ozair et al., 2019), we point out that there are three
challenges faced by existing methods.

The first challenge is the training stability, where an unstable training
process with high variance may be problematic. For example, Hjelm et al.
(2018); Tschannen et al. (2019); Tsai et al. (2020b) show that the contrastive
objectives with large variance cause numerical issues and have a poor
downstream performance with their learned representations. The second
challenge is the sensitivity to minibatch size, where the objectives requiring
a huge minibatch size may restrict their practical usage. For instance,
SimCLRv2 (Chen et al., 2020c) utilizes CPC as its contrastive objective and
reaches state-of-the-art performances on multiple self-supervised and semi-
supervised benchmarks. Nonetheless, the objective is trained with a minibatch
size of $8,192$, and this scale of training requires enormous computational
power. The third challenge is the downstream task performance, which is the
one that we would like to emphasize the most. For this reason, in most cases,
CPC is the objective that we would adopt for contrastive representation
learning, due to its favorable performance in downstream tasks (Tschannen et
al., 2019; Baevski et al., 2020).

This paper presents a new contrastive representation learning objective: the
Relative Predictive Coding (RPC), which attempts to achieve a good balance
among these three challenges: training stability, sensitivity to minibatch
size, and downstream task performance. At the core of RPC is the relative
parameters, which are used to regularize RPC for its boundedness and low
variance. From a modeling perspective, the relative parameters act as a
$\ell_{2}$ regularization for RPC. From a statistical perspective, the
relative parameters prevent RPC from growing to extreme values, as well as
upper bound its variance. In addition to the relative parameters, RPC contains
no logarithm and exponential, which are the main cause of the training
instability for prior contrastive learning objectives (Song & Ermon, 2019).

To empirically verify the effectiveness of RPC, we consider benchmark self-
supervised representation learning tasks, including visual object
classification on CIFAR-10/-100 (Krizhevsky et al., 2009), STL-10 (Coates et
al., 2011), and ImageNet (Russakovsky et al., 2015) and speech recognition on
LibriSpeech (Panayotov et al., 2015). Comparing RPC to prior contrastive
learning objectives, we observe a lower variance during training, a lower
minibatch size sensitivity, and consistent performance improvement. Lastly, we
also relate RPC with MI estimation, empirically showing that RPC can estimate
MI with low variance.

##  2 Proposed Method

Table 1: Different contrastive learning objectives, grouped by measurements of
distribution divergence. $P_{XY}$ represents the distribution of related
samples (positively-paired), and $P_{X}P_{Y}$ represents the distribution of
unrelated samples (negatively-paired). $f(x,y)\in\mathcal{F}$ for
$\mathcal{F}$ being any class of functions
$f:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$. $\dagger$: Compared to
$J_{\rm CPC}$ and $J_{\rm RPC}$, we empirically find $J_{\rm WPC}$ performs
worse on complex real-world image datasets spanning CIFAR-10/-100 (Krizhevsky
et al., 2009) and ImageNet (Russakovsky et al., 2015).

Objective |  Good Training Stability |  Lower Minibatch Size Sensitivity |  Good Downstream Performance
---|---|---|---
relating to KL-divergence between $P_{XY}$ and $P_{X}P_{Y}$:  $J_{\rm DV}$
(Donsker & Varadhan, 1975), $J_{\rm NWJ}$ (Nguyen et al., 2010), and $J_{\rm
CPC}$ (Oord et al., 2018)
${\color[rgb]{1,0,0}J_{\rm DV}(X,Y)}:={\rm sup}_{f\in\mathcal{F}}\,\mathbb{E}_{P_{XY}}[f(x,y)]-\log(\mathbb{E}_{P_{X}P_{Y}}[e^{f(x,y)}])$ | ✗ | ✓ | ✗
${\color[rgb]{1,0,0}J_{\rm NWJ}(X,Y)}:={\rm sup}_{f\in\mathcal{F}}\,\mathbb{E}_{P_{XY}}[f(x,y)]-\mathbb{E}_{P_{X}P_{Y}}[e^{f(x,y)-1}]$ | ✗ | ✓ | ✗
${\color[rgb]{1,0,0}J_{\rm CPC}(X,Y)}:={\rm sup}_{f\in\mathcal{F}}\,\mathbb{E}_{(x,y_{1})\sim P_{XY},\\{y_{j}\\}_{j=2}^{N}\sim P_{Y}}\Big{[}\log\big{(}e^{f(x,y_{1})}/\frac{1}{N}\sum_{j=1}^{N}e^{f(x,y_{j})}\big{)}\Big{]}$ | ✓ | ✗ | ✓
relating to JS-divergence between $P_{XY}$ and $P_{X}P_{Y}$: $J_{\rm JS}$
(Nowozin et al., 2016)
${\color[rgb]{1,0,0}J_{\rm JS}(X,Y)}:={\rm sup}_{f\in\mathcal{F}}\,\mathbb{E}_{P_{XY}}[-\log(1+e^{-f(x,y)})]-\mathbb{E}_{P_{X}P_{Y}}[\log(1+e^{f(x,y)})]$ | ✓ | ✓ | ✗
relating to Wasserstein-divergence between $P_{XY}$ and $P_{X}P_{Y}$: $J_{\rm
WPC}$ (Ozair et al., 2019), with $\mathcal{F_{L}}$ denoting the space of
1-Lipschitz functions
${\color[rgb]{1,0,0}J_{\rm WPC}(X,Y)}:={\rm sup}_{f\in\mathcal{F_{L}}}\,\mathbb{E}_{(x,y_{1})\sim P_{XY},\\{y_{j}\\}_{j=2}^{N}\sim P_{Y}}\Big{[}\log\big{(}e^{f(x,y_{1})}/\frac{1}{N}\sum_{j=1}^{N}e^{f(x,y_{j})}\big{)}\Big{]}$ | ✓ | ✓ | ✗†
relating to $\chi^{2}$-divergence between $P_{XY}$ and $P_{X}P_{Y}$: $J_{\rm
RPC}$ (ours)
${\color[rgb]{1,0,0}J_{\rm RPC}(X,Y)}:={\rm sup}_{f\in\mathcal{F}}\,\mathbb{E}_{P_{XY}}[f(x,y)]-\alpha\mathbb{E}_{P_{X}P_{Y}}[f(x,y)]-\frac{\beta}{2}\mathbb{E}_{P_{XY}}\left[f^{2}(x,y)\right]-\frac{\gamma}{2}\mathbb{E}_{P_{X}P_{Y}}\left[f^{2}(x,y)\right]$ | ✓ | ✓ | ✓

This paper presents a new contrastive representation learning objective - the
Relative Predictive Coding (RPC). At a high level, RPC 1) introduces the
relative parameters to regularize the objective for boundedness and low
variance; and 2) achieves a good balance among the three challenges in the
contrastive representation learning objectives: training stability,
sensitivity to minibatch size, and downstream task performance. We begin by
describing prior contrastive objectives along with their limitations on the
three challenges in Section 2.1. Then, we detail our presented objective and
its modeling benefits in Section 2.2. An overview of different contrastive
learning objectives is provided in Table 1. We defer all the proofs in
Appendix.

##### Notation

We use an uppercase letter to denote a random variable (e.g., $X$), a lower
case letter to denote the outcome of this random variable (e.g., $x$), and a
calligraphy letter to denote the sample space of this random variable (e.g.,
$\mathcal{X}$). Next, if the samples $(x,y)$ are related (or positively-
paired), we refer $(x,y)\sim P_{XY}$ with $P_{XY}$ being the joint
distribution of $X\times Y$. If the samples $(x,y)$ are unrelated (negatively-
paired), we refer $(x,y)\sim P_{X}P_{Y}$ with $P_{X}P_{Y}$ being the product
of marginal distributions over $X\times Y$. Last, we define $f\in\mathcal{F}$
for $\mathcal{F}$ being any class of functions
$f:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$.

###  2.1 Preliminary

Contrastive representation learning encourages the contrastiveness between the
positive and the negative pairs of the representations from the related data
$X$ and $Y$. Specifically, when sampling a pair of representations $(x,y)$
from their joint distribution ($(x,y)\sim P_{XY}$), this pair is defined as a
positive pair; when sampling from the product of marginals ($(x,y)\sim
P_{X}P_{Y}$), this pair is defined as a negative pair. Then, Tsai et al.
(2020b) formalizes this idea such that the contrastiveness of the
representations can be measured by the divergence between $P_{XY}$ and
$P_{X}P_{Y}$, where higher divergence suggests better contrastiveness. To
better understand prior contrastive learning objectives, we categorize them in
terms of different divergence measurements between $P_{XY}$ and $P_{X}P_{Y}$,
with their detailed objectives presented in Table 1.

We instantiate the discussion using Contrastive Predictive Coding (Oord et
al., 2018, $J_{\rm CPC}$), which is a lower bound of $D_{\rm
KL}(P_{XY}\,\|\,P_{X}P_{Y})$ with $D_{\rm KL}$ referring to the KL-divergence:

$J_{\rm CPC}(X,Y):=\underset{f\in\mathcal{F}}{\rm
sup}\,\mathbb{E}_{(x,y_{1})\sim P_{XY},\\{y_{j}\\}_{j=2}^{N}\sim
P_{Y}}\Big{[}\log\frac{e^{f(x,y_{1})}}{\frac{1}{N}\sum_{j=1}^{N}e^{f(x,y_{j})}}\Big{]}.$
(1)

Then, Oord et al. (2018) presents to maximize $J_{\rm CPC}(X,Y)$, so that the
learned representations $X$ and $Y$ have high contrastiveness. We note that
$J_{\rm CPC}$ has been commonly used in many recent self-supervised
representation learning frameworks (He et al., 2020; Chen et al., 2020b),
where they constrain the function to be $f(x,y)={\rm cosine}(x,y)$ with ${\rm
cosine}(\cdot)$ being cosine similarity. Under this function design,
maximizing $J_{\rm CPC}$ leads the representations of related pairs to be
close and representations of unrelated pairs to be distant.

The category of modeling $D_{\rm KL}(P_{XY}\,\|\,P_{X}P_{Y})$ also includes
the Donsker-Varadhan objective ($J_{\rm DV}$ (Donsker & Varadhan, 1975;
Belghazi et al., 2018)) and the Nguyen-Wainright-Jordan objective ($J_{\rm
NWJ}$ (Nguyen et al., 2010; Belghazi et al., 2018)), where Belghazi et al.
(2018); Tsai et al. (2020b) show that $J_{\rm DV}(X,Y)=J_{\rm NWJ}(X,Y)=D_{\rm
KL}(P_{XY}\,\|\,P_{X}P_{Y})$. The other divergence measurements considered in
prior work are $D_{\rm JS}(P_{XY}\,\|\,P_{X}P_{Y})$ (with $D_{\rm JS}$
referring to the Jenson-Shannon divergence) and $D_{\rm
Wass}(P_{XY}\,\|\,P_{X}P_{Y})$ (with $D_{\rm Wass}$ referring to the
Wasserstein-divergence). The instance of modeling $D_{\rm
JS}(P_{XY}\,\|\,P_{X}P_{Y})$ is the Jensen-Shannon f-GAN objective ($J_{\rm
JS}$ (Nowozin et al., 2016; Hjelm et al., 2018)), where $J_{\rm
JS}(X,Y)=2\big{(}D_{\rm JS}(P_{XY}\,\|\,P_{X}P_{Y})-\log 2\big{)}$.222$J_{\rm
JS}(X,Y)$ achieves its supreme value when $f^{*}(x,y)=\log(p(x,y)/p(x)p(y))$
(Tsai et al., 2020b). Plug-in $f^{*}(x,y)$ into $J_{\rm JS}(X,Y)$, we can
conclude $J_{\rm JS}(X,Y)=2(D_{\rm JS}(P_{XY}\,\|\,P_{X}P_{Y})-\log 2)$. The
instance of modeling $D_{\rm Wass}(P_{XY}\,\|\,P_{X}P_{Y})$ is the Wasserstein
Predictive Coding ($J_{\rm WPC}$ (Ozair et al., 2019)), where $J_{\rm
WPC}(X,Y)$ modifies $J_{\rm CPC}(X,Y)$ objective (equation 1) by searching the
function from $\mathcal{F}$ to $\mathcal{F_{L}}$. $\mathcal{F_{L}}$ denotes
any class of 1-Lipschitz continuous functions from
$(\mathcal{X}\times\mathcal{Y})$ to $\mathbb{R}$, and thus
$\mathcal{F_{L}}\subset\mathcal{F}$. Ozair et al. (2019) shows that $J_{\rm
WPC}(X,Y)$ is the lower bound of both $D_{\rm KL}(P_{XY}\,\|\,P_{X}P_{Y})$ and
$D_{\rm Wass}(P_{XY}\,\|\,P_{X}P_{Y})$. See Table 1 for all the equations. To
conclude, the contrastive representation learning objectives are unsupervised
representation learning methods that maximize the distribution divergence
between $P_{XY}$ and $P_{X}P_{Y}$. The learned representations cause high
contrastiveness, and recent work (Arora et al., 2019; Tsai et al., 2020a)
theoretically show that highly-contrastive representations could improve the
performance on downstream tasks.

After discussing prior contrastive representation learning objectives, we
point out three challenges in their practical deployments: training stability,
sensitivity to minibatch training size, and downstream task performance. In
particular, the three challenges can hardly be handled well at the same time,
where we highlight the conclusions in Table 1. Training Stability: The
training stability highly relates to the variance of the objectives, where
Song & Ermon (2019) shows that $J_{\rm DV}$ and $J_{\rm NWJ}$ exhibit
inevitable high variance due to their inclusion of exponential function. As
pointed out by Tsai et al. (2020b), $J_{\rm CPC}$, $J_{\rm WPC}$, and $J_{\rm
JS}$ have better training stability because $J_{\rm CPC}$ and $J_{\rm WPC}$
can be realized as a multi-class classification task and $J_{\rm JS}$ can be
realized as a binary classification task. The cross-entropy loss adopted in
$J_{\rm CPC}$, $J_{\rm WPC}$, and $J_{\rm JS}$ is highly-optimized and stable
in existing optimization package (Abadi et al., 2016; Paszke et al., 2019).
Sensitivity to minibatch training size: Among all the prior contrastive
representation learning methods, $J_{\rm CPC}$ is known to be sensitive to the
minibatch training size (Ozair et al., 2019). Taking a closer look at equation
1, $J_{\rm CPC}$ deploys an instance selection such that $y_{1}$ should be
selected from $\\{y_{1},y_{2},\cdots,y_{N}\\}$, with $(x,y_{1})\sim P_{XY}$,
$(x,y_{j>1})\sim P_{X}P_{Y}$ with $N$ being the minibatch size. Previous work
(Poole et al., 2019; Song & Ermon, 2019; Chen et al., 2020b; Caron et al.,
2020) showed that a large $N$ results in a more challenging instance selection
and forces $J_{\rm CPC}$ to have a better contrastiveness of $y_{1}$ (related
instance for $x$) against $\\{y_{j}\\}_{j=2}^{N}$ (unrelated instance for
$x$). $J_{\rm DV}$, $J_{\rm NWJ}$, and $J_{\rm JS}$ do not consider the
instance selection, and $J_{\rm WPC}$ reduces the minibatch training size
sensitivity by enforcing 1-Lipschitz constraint. Downstream Task Performance:
The downstream task performance is what we care the most among all the three
challenges. $J_{\rm CPC}$ has been the most popular objective as it manifests
superior performance over the other alternatives (Tschannen et al., 2019; Tsai
et al., 2020b; a). We note that although $J_{\rm WPC}$ shows better
performance on Omniglot (Lake et al., 2015) and CelebA (Liu et al., 2015)
datasets, we empirically find it not generalizing well to CIFAR-10/-100
(Krizhevsky et al., 2009) and ImageNet (Russakovsky et al., 2015).

###  2.2 Relative Predictive Coding

In this paper, we present Relative Predictive Coding (RPC), which achieves a
good balance among the three challenges mentioned above:

$J_{\rm RPC}(X,Y):=\underset{f\in\mathcal{F}}{\rm
sup}\,\mathbb{E}_{P_{XY}}[f(x,y)]-\alpha\mathbb{E}_{P_{X}P_{Y}}[f(x,y)]-\frac{\beta}{2}\mathbb{E}_{P_{XY}}\left[f^{2}(x,y)\right]-\frac{\gamma}{2}\mathbb{E}_{P_{X}P_{Y}}\left[f^{2}(x,y)\right],$
(2)

where $\alpha>0$, $\beta>0$, $\gamma>0$ are hyper-parameters and we define
them as relative parameters. Intuitively, $J_{\rm RPC}$ contains no logarithm
or exponential, potentially preventing unstable training due to numerical
issues. Now, we discuss the roles of $\alpha,\beta,\gamma$. At a first glance,
$\alpha$ acts to discourage the scores of $P_{XY}$ and $P_{X}P_{Y}$ from being
close, and $\beta/\gamma$ acts as a $\ell_{2}$ regularization coefficient to
stop $f$ from becoming large. For a deeper analysis, the relative parameters
act to regularize our objective for boundedness and low variance. To show this
claim, we first present the following lemma:

######  Lemma 1 (Optimal Solution for $J_{\rm RPC}$)

Let $r(x,y)=\frac{p(x,y)}{p(x)p(y)}$ be the density ratio. $J_{\rm RPC}$ has
the optimal solution
$f^{*}(x,y)=\frac{r(x,y)-\alpha}{\beta\,r(x,y)+\gamma}:=r_{\alpha,\beta,\gamma}(x,y)$
with $-\frac{\alpha}{\gamma}\leq r_{\alpha,\beta,\gamma}\leq\frac{1}{\beta}$.

Lemma 1 suggests that $J_{\rm RPC}$ achieves its supreme value at the ratio
$r_{\alpha,\beta,\gamma}(x,y)$ indexed by the relative parameters
$\alpha,\beta,\gamma$ (i.e., we term $r_{\alpha,\beta,\gamma}(x,y)$ as the
relative density ratio). We note that $r_{\alpha,\beta,\gamma}(x,y)$ is an
increasing function w.r.t. $r(x,y)$ and is nicely bounded even when $r(x,y)$
is large. We will now show that the bounded $r_{\alpha,\beta,\gamma}$ suggests
the empirical estimation of $J_{\rm RPC}$ has boundeness and low variance. In
particular, let $\\{x_{i},y_{i}\\}_{i=1}^{n}$ be $n$ samples drawn uniformly
at random from $P_{XY}$ and $\\{x^{\prime}_{j},y^{\prime}_{j}\\}_{j=1}^{m}$ be
$m$ samples drawn uniformly at random from $P_{X}P_{Y}$. Then, we use neural
networks to empirically estimate $J_{\rm RPC}$ as $\hat{J}^{m,n}_{\rm RPC}$:

######  Definition 1 ($\hat{J}^{m,n}_{\rm RPC}$, empirical estimation of
$J_{\rm RPC}$)

We parametrize $f$ via a family of neural networks
$\mathcal{F}_{\Theta}:=\\{f_{\theta}:\theta\in\Theta\subseteq\mathbb{R}^{d}\\}$
where $d\in\mathbb{N}$ and $\Theta$ is compact. Then, $\hat{J}^{m,n}_{\rm
RPC}=\sup_{{f}_{\theta}\in\mathcal{F}_{\Theta}}\frac{1}{n}\sum_{i=1}^{n}f_{\theta}(x_{i},y_{i})-\frac{1}{m}\sum_{j=1}^{m}\alpha
f_{\theta}(x^{\prime}_{j},y^{\prime}_{j})-\frac{1}{n}\sum_{i=1}^{n}\frac{\beta}{2}f_{\theta}^{2}(x_{i},y_{i})-\frac{1}{m}\sum_{j=1}^{m}\frac{\gamma}{2}f_{\theta}^{2}(x^{\prime}_{j},y^{\prime}_{j}).$

######  Proposition 1 (Boundedness of $\hat{J}^{m,n}_{\rm RPC}$, informal)

$0\leq J_{\rm RPC}\leq\frac{1}{2\beta}+\frac{\alpha^{2}}{2\gamma}$. Then, with
probability at least $1-\delta$, $|J_{\rm RPC}-\hat{J}^{m,n}_{\rm
RPC}|=O(\sqrt{\frac{d+{\rm log}\,(1/\delta)}{n^{\prime}}}),$ where
$n^{\prime}={\rm min}\,\\{n,m\\}$.

######  Proposition 2 (Variance of $\hat{J}^{m,n}_{\rm RPC}$, informal)

There exist universal constants $c_{1}$ and $c_{2}$ that depend only on
$\alpha,\beta,\gamma$, such that $\mathrm{Var}[\hat{J}^{m,n}_{{\rm
RPC}}]=O\Big{(}\frac{c_{1}}{n}+\frac{c_{2}}{m}\Big{)}.$

From the two propositions, when $m$ and $n$ are large, i.e., the sample sizes
are large, $\hat{J}^{m,n}_{\rm RPC}$ is bounded, and its variance vanishes to
$0$. First, the boundedness of $\hat{J}^{m,n}_{\rm RPC}$ suggests
$\hat{J}^{m,n}_{\rm RPC}$ will not grow to extremely large or small values.
Prior contrastive learning objectives with good training stability (e.g.,
$J_{\rm CPC}$/$J_{\rm JS}$/$J_{\rm WPC}$) also have the boundedness of their
objective values. For instance, the empirical estimation of ${J}_{\rm CPC}$ is
less than ${\rm log}\,N$ (equation 1) (Poole et al., 2019). Nevertheless,
${J}_{\rm CPC}$ often performs the best only when minibatch size is large, and
empirical performances of $J_{\rm JS}$ and $J_{\rm WPC}$ are not as
competitive as ${J}_{\rm CPC}$. Second, the upper bound of the variance
implies the training of $\hat{J}^{m,n}_{\rm RPC}$ can be stable, and in
practice we observe a much smaller value than the stated upper bound. On the
contrary, Song & Ermon (2019) shows that the empirical estimations of
${J}_{\rm DV}$ and ${J}_{\rm NWJ}$ exhibit inevitable variances that grow
exponentially with the true $D_{\mathrm{KL}}(P_{XY}\|P_{X}P_{Y})$.

Lastly, similar to prior contrastive learning objective that are related to
distribution divergence measurement, we associate $J_{\rm RPC}$ with the Chi-
square divergence
$D_{\chi^{2}}(P_{XY}\,\|\,P_{X}P_{Y})=\mathbb{E}_{P_{X}P_{Y}}[r^{2}(x,y)]-1$
(Nielsen & Nock, 2013). The derivations are provided in Appendix. By having
$P^{\prime}=\frac{\beta}{\beta+\gamma}P_{XY}+\frac{\gamma}{\beta+\gamma}P_{X}P_{Y}$
as the mixture distribution of $P_{XY}$ and $P_{X}P_{Y}$, we can rewrite
$J_{\rm RPC}(X,Y)$ as $J_{\rm
RPC}(X,Y)=\frac{\beta+\gamma}{2}\mathbb{E}_{P^{\prime}}[r_{\alpha,\beta,\gamma}^{2}(x,y)]$.
Hence, $J_{\rm RPC}$ can be regarded as a generalization of $D_{\chi^{2}}$
with the relative parameters $\alpha,\beta,\gamma$, where $D_{\chi^{2}}$ can
be recovered from $J_{\rm RPC}$ by specializing $\alpha=0$, $\beta=0$ and
$\gamma=1$ (e.g., $D_{\chi^{2}}=2J_{\rm RPC}|_{\alpha=\beta=0,\gamma=1}-1$).
Note that $J_{\rm RPC}$ may not be a formal divergence measure with arbitrary
$\alpha,\beta,\gamma$.

##  3 Experiments

We provide an overview of the experimental section. First, we conduct
benchmark self-supervised representation learning tasks spanning visual object
classification and speech recognition. This set of experiments are designed to
discuss the three challenges of the contrastive representation learning
objectives: downstream task performance (Section 3.1), training stability
(Section 3.2), and minibatch size sensitivity (Section 3.3). We also provide
an ablation study on the choices of the relative parameters in $J_{\rm RPC}$
(Section 3.4). On these experiments we found that $J_{\rm RPC}$ achieves a
lower variance during training, a lower batch size insensitivity, and
consistent performance improvement. Second, we relate $J_{\rm RPC}$ with
mutual information (MI) estimation (Section 3.5). The connection is that MI is
an average statistic of the density ratio, and we have shown that the optimal
solution of $J_{\rm RPC}$ is the relative density ratio (see Lemma 1). Thus we
could estimate MI using the density ratio transformed from the optimal
solution of $J_{\rm RPC}$. On these two sets of experiments, we fairly compare
$J_{\rm RPC}$ with other contrastive learning objectives. Particularly, across
different objectives, we fix the network, learning rate, optimizer, and batch
size (we use the default configurations suggested by the original
implementations from Chen et al. (2020c), Rivière et al. (2020) and Tsai et
al. (2020b).) The only difference will be the objective itself. In what
follows, we perform the first set of experiments. We defer experimental
details in the Appendix.

##### Datasets.

For the visual objective classification, we consider CIFAR-10/-100 (Krizhevsky
et al., 2009), STL-10 (Coates et al., 2011), and ImageNet (Russakovsky et al.,
2015). CIFAR-10/-100 and ImageNet contain labeled images only, while STL-10
contains labeled and unlabeled images. For the speech recognition, we consider
LibriSpeech-100h (Panayotov et al., 2015) dataset, which contains $100$ hours
of $16{\rm kHz}$ English speech from $251$ speakers with $41$ types of
phonemes.

##### Training and Evaluation Details.

For the vision experiments, we follow the setup from SimCLRv2 (Chen et al.,
2020c), which considers visual object recognition as its downstream task. For
the speech experiments, we follow the setup from prior work (Oord et al.,
2018; Rivière et al., 2020), which consider phoneme classification and speaker
identification as the downstream tasks. Then, we briefly discuss the training
and evaluation details into three modules: 1) related and unrelated data
construction, 2) pre-training, and 3) fine-tuning and evaluation. For more
details, please refer to Appendix or the original implementations.

$\triangleright\,\,$ Related and Unrelated Data Construction. In the vision
experiment, we construct the related images by applying different
augmentations on the same image. Hence, when $(x,y)\sim P_{XY}$, $x$ and $y$
are the same image with different augmentations. The unrelated images are two
randomly selected samples. In the speech experiment, we define the current
latent feature (feature at time $t$) and the future samples (samples at time
$>t$) as related data. In other words, the feature in the latent space should
contain information that can be used to infer future time steps. A latent
feature and randomly selected samples would be considered as unrelated data.

$\triangleright\,\,$ Pre-training. The pre-training stage refers to the self-
supervised training by a contrastive learning objective. Our training
objective is defined in Definition 1, where we use neural networks to
parametrize the function using the constructed related and unrelated data.
Convolutional neural networks are used for vision experiments. Transformers
(Vaswani et al., 2017) and LSTMs (Hochreiter & Schmidhuber, 1997) are used for
speech experiments.

$\triangleright\,\,$ Fine-tuning and Evaluation. After the pre-training stage,
we fix the parameters in the pre-trained networks and add a small fine-tuning
network on top of them. Then, we fine-tune this small network with the
downstream labels in the data’s training split. For the fine-tuning network,
both vision and speech experiments consider multi-layer perceptrons. Last, we
evaluate the fine-tuned representations on the data’s test split. We would
like to point out that we do not normalize the hidden representations encoded
by the pre-training neural network for loss calculation. This hidden
normalization technique is widely applied (Tian et al., 2019; Chen et al.,
2020b; c) to stabilize training and increase performance for prior objectives,
but we find it unnecessary in $J_{\rm RPC}$.

###  3.1 Downstream Task Performances on Vision and Speech

Table 2: Top-1 accuracy (%) for visual object recognition results. $J_{\rm
DV}$ and $J_{\rm NWJ}$ are not reported on ImageNet due to numerical
instability. ResNet depth, width and Selective Kernel (SK) configuration for
each setting are provided in ResNet depth+width+SK column. A slight drop of
$J_{\rm CPC}$ performance compared to Chen et al. (2020c) is because we only
train for $100$ epochs rather than $800$ due to the fact that running 800
epochs uninterruptedly on cloud TPU is very expensive. Also, we did not employ
a memory buffer (He et al., 2020) to store negative samples. We and we did not
employ a memory buffer. We also provide the results from fully supervised
models as a comparison (Chen et al., 2020b; c). Fully supervised training
performs worse on STL-10 because it does not employ the unlabeled samples in
the dataset (Löwe et al., 2019).

Dataset | ResNet Depth+Width+SK | Self-supervised | Supervised
---|---|---|---
$J_{\rm DV}$ | $J_{\rm NWJ}$ | $J_{\rm JS}$ | $J_{\rm WPC}$ | $J_{\rm CPC}$ | $J_{\rm RPC}$
CIFAR-10 |  18 + 1$\times$ \+ No SK | 91.10 | 90.54 | 83.55 | 80.02 | 91.12 | 91.46 | 93.12
CIFAR-10 |  50 + 1$\times$ \+ No SK | 92.23 | 92.67 | 87.34 | 85.93 | 93.42 | 93.57 | 95.70
CIFAR-100 |  18 + 1$\times$ \+ No SK | 77.10 | 77.27 | 74.02 | 72.16 | 77.36 | 77.98 | 79.11
CIFAR-100 |  50 + 1$\times$ \+ No SK | 79.02 | 78.52 | 75.31 | 73.23 | 79.31 | 79.89 | 81.20
STL-10 |  50 + 1$\times$ \+ No SK | 82.25 | 81.17 | 79.07 | 76.50 | 83.40 | 84.10 | 71.40
ImageNet |  50 + 1$\times$ \+ SK | - | - | 66.21 | 62.10 | 73.48 | 74.43 | 78.50
ImageNet |  152 + 2$\times$ \+ SK | - | - | 71.12 | 69.51 | 77.80 | 78.40 | 80.40

For the downstream task performance in the vision domain, we test the proposed
$J_{\rm RPC}$ and other contrastive learning objectives on CIFAR-10/-100
(Krizhevsky et al., 2009), STL-10 (Coates et al., 2011), and ImageNet
ILSVRC-2012 (Russakovsky et al., 2015). Here we report the best performances
$J_{\rm RPC}$ can get on each dataset (we include experimental details in
A.7.) Table 2 shows that the proposed $J_{\rm RPC}$ outperforms other
objectives on all datasets. Using $J_{\rm RPC}$ on the largest network (ResNet
with depth of $152$, channel width of $2$ and selective kernels), the
performance jumps from $77.80\%$ of $J_{\rm CPC}$ to $78.40\%$ of $J_{\rm
RPC}$.

Regarding speech representation learning, the downstream performance for
phoneme and speaker classification are shown in Table 3 (we defer experimental
details in Appendix A.9.) Compared to $J_{\rm CPC}$, $J_{\rm RPC}$ improves
the phoneme classification results with $4.8$ percent and the speaker
classification results with $0.3$ percent, which is closer to the fully
supervised model. Overall, the proposed $J_{\rm RPC}$ performs better than
other unsupervised learning objectives on both phoneme classification and
speaker classification tasks.

Table 3: Accuracy (%) for LibriSpeech-100h phoneme and speaker classification results. We also provide the results from fully supervised model as a comparison (Oord et al., 2018).  Task Name | Self-supervised | Supervised
---|---|---
$J_{\rm CPC}$ | $J_{\rm DV}$ | $J_{\rm NWJ}$ | $J_{\rm RPC}$
Phoneme classification | 64.6 | 61.27 | 62.09 | 69.39 | 74.6
Speaker classification | 97.4 | 95.36 | 95.89 | 97.68 | 98.5
Figure 1: (a) Empirical values of $J_{\rm DV}$, $J_{\rm NWJ}$, $J_{\rm CPC}$
and $J_{\rm RPC}$ performing visual object recognition on CIFAR-10. $J_{\rm
DV}$ and $J_{\rm NWJ}$ soon explode to NaN values and stop the training (shown
as early stopping in the figure), while $J_{\rm CPC}$ and $J_{\rm RPC}$ are
more stable. Performance comparison of $J_{\rm CPC}$ and $J_{\rm RPC}$ on (b)
CIFAR-10 and (c) LibriSpeech-100h with different minibatch sizes, showing that
the performance of $J_{\rm RPC}$ is less sensitive to minibatch size change
compared to $J_{\rm CPC}$.

###  3.2 Training Stability

We provide empirical training stability comparisons on $J_{\rm DV}$, $J_{\rm
NWJ}$, $J_{\rm CPC}$ and $J_{\rm RPC}$ by plotting the values of the
objectives as the training step increases. We apply the four objectives to the
SimCLRv2 framework and train on the CIFAR-10 dataset. All setups of training
are exactly the same except the objectives. From our experiments, $J_{\rm DV}$
and $J_{\rm NWJ}$ soon explode to NaN and disrupt training (shown as early
stopping in Figure 1a; extremely large values are not plotted due to scale
constraints). On the other hand, $J_{\rm RPC}$ and $J_{\rm CPC}$ has low
variance, and both enjoy stable training. As a result, performances using the
representation learned from unstable $J_{\rm DV}$ and $J_{\rm NWJ}$ suffer in
downstream task, while representation learned by $J_{\rm RPC}$ and $J_{\rm
CPC}$ work much better.

###  3.3 Minibatch Size Sensitivity

We then provide the analysis on the effect of minibatch size on $J_{\rm RPC}$
and $J_{\rm CPC}$, since $J_{\rm CPC}$ is known to be sensitive to minibatch
size (Poole et al., 2019). We train SimCLRv2 (Chen et al., 2020c) on CIFAR-10
and the model from Rivière et al. (2020) on LibriSpeech-100h using $J_{\rm
RPC}$ and $J_{\rm CPC}$ with different minibatch sizes. The settings of
relative parameters are the same as Section 3.2. From Figure 1b and 1c, we can
observe that both $J_{\rm RPC}$ and $J_{\rm CPC}$ achieve their optimal
performance at a large minibatch size. However, when the minibatch size
decreases, the performance of $J_{\rm CPC}$ shows higher sensitivity and
suffers more when the number of minibatch samples is small. The result
suggests that the proposed method might be less sensitive to the change of
minibatch size compared to $J_{\rm CPC}$ given the same training settings.

###  3.4 Effect of Relative Parameters

We study the effect of different combinations of relative parameters in
$J_{\rm RPC}$ by comparing downstream performances on visual object
recognition. We train SimCLRv2 on CIFAR-10 with different combinations of
$\alpha,\beta$ and $\gamma$ in $J_{\rm RPC}$ and fix all other experimental
settings. We choose
$\alpha\in\\{0,0.001,1.0\\},\beta\in\\{0,0.001,1.0\\},\gamma\in\\{0,0.001,1.0\\}$
and we report the best performances under each combination of $\alpha,\beta$,
and $\gamma$. From Figure 2, we first observe that $\alpha>0$ has better
downstream performance than $\alpha=0$ when $\beta$ and $\gamma$ are fixed.
This observation is as expected, since $\alpha>0$ encourages representations
of related and unrelated samples to be pushed away. Then, we find that a small
but nonzero $\beta$ ($\beta=0.001$) and a large $\gamma$ ($\gamma=1.0$) give
the best performance compared to other combinations. Since $\beta$ and
$\gamma$ serve as the coefficients of $\ell_{2}$ regularization, the results
imply that the regularization is a strong and sensitive factor that will
influence the performance. The results here are not as competitive as Table 2
because the CIFAR-10 result reported in Table 2 is using a set of relative
parameters ($\alpha=1.0,\beta=0.005,\gamma=1.0$) that is different from the
combinations in this subsection. Also, we use quite different ranges of
$\gamma$ on ImageNet (see A.7 for details.) In conclusion, we find empirically
that a non-zero $\alpha$, a small $\beta$ and a large $\gamma$ will lead to
the optimal representation for the downstream task on CIFAR-10.

Figure 2: Heatmaps of downstream task performance on CIFAR-10, using different
$\alpha$, $\beta$ and $\gamma$ in the $J_{\rm RPC}$. We conclude that a
nonzero $\alpha$, a small $\beta$ $(\beta=0.001)$ and a large
$\gamma(\gamma=1.0)$ are crucial for better performance.

###  3.5 Relation to Mutual Information Estimation

The presented approach also closely relates to mutual information estimation.
For random variables $X$ and $Y$ with joint distribution $P_{XY}$ and product
of marginals $P_{X}P_{Y}$, the mutual information is defined as
$I(X;Y)=D_{\mathrm{KL}}(P_{XY}\|P_{X}P_{Y})$. Lemma 1 states that given
optimal solution $f^{*}(x,y)$ of $J_{\rm RPC}$, we can get the density ratio
$r(x,y):=p(x,y)/p(x)p(y)$ as $r(x,y)=\frac{\gamma/\beta+\alpha}{1-\beta
f^{*}(x,y)}-\frac{\gamma}{\beta}$. We can empirically estimate $\hat{r}(x,y)$
from the estimated $\hat{f}(x,y)$ via this transformation, and use
$\hat{r}(x,y)$ to estimate mutual information (Tsai et al., 2020b).
Specifically, $I(X;Y)\approx\frac{1}{n}\sum_{i=1}^{n}{\rm
log}\,\hat{r}(x_{i},y_{i})$ with $(x_{i},y_{i})\sim P^{\otimes n}_{X,Y}$,
where $P^{\otimes n}_{X,Y}$ is the uniformly sampled empirical distribution of
$P_{X,Y}$.

We follow prior work (Poole et al., 2019; Song & Ermon, 2019; Tsai et al.,
2020b) for the experiments. We consider $X$ and $Y$ as two $20$-dimensional
Gaussians with correlation $\rho$, and our goal is to estimate the mutual
information $I(X;Y)$. Then, we perform a cubic transformation on $y$ so that
$y\mapsto y^{3}$. The first task is referred to as Gaussian task and the
second is referred to as Cubic task, where both have the ground truth
$I(X;Y)=-10{\rm log}\,(1-\rho^{2})$. The models are trained on $20,000$ steps
with $I(X;Y)$ starting at $2$ and increased by $2$ per $4,000$ steps. Our
method is compared with baseline methods $J_{\rm CPC}$ (Oord et al., 2018),
$J_{\rm NWJ}$ (Nguyen et al., 2010), $J_{\rm JS}$ (Nowozin et al., 2016),
SMILE (Song & Ermon, 2019) and Difference of Entropies (DoE) (McAllester &
Stratos, 2020). All approaches use the same network design, learning rate,
optimizer and minibatch size for a fair comparison. First, we observe $J_{\rm
CPC}$ (Oord et al., 2018) has the smallest variance, while it exhibits a large
bias (the estimated mutual information from $J_{\rm CPC}$ has an upper bound
${\rm log}({\rm batch\,size})$). Second, $J_{\rm NWJ}$ (Nguyen et al., 2010)
and $J_{\rm JSD}$ (Poole et al., 2019) have large variances, especially in the
Cubic task. Song & Ermon (2019) pointed out the limitations of $J_{\rm CPC}$,
$J_{\rm NWJ}$, and $J_{\rm JSD}$, and developed the SMILE method, which clips
the value of the estimated density function to reduce the variance of the
estimators. DoE (McAllester & Stratos, 2020) is neither a lower bound nor a
upper bound of mutual information, but can achieve accurate estimates when
underlying mutual information is large. $J_{\rm RPC}$ exhibits comparable bias
and lower variance compared to the SMILE method, and is more stable than the
DoE method. We would like to highlight our method’s low-variance property,
where we neither clip the values of the estimated density ratio nor impose an
upper bound of our estimated mutual information.

Figure 3: Mutual information estimation performed on 20-d correlated Gaussian
distribution, with the correlation increasing each 4K steps. $J_{\rm RPC}$
exhibits smaller variance than SMILE and DoE, and smaller bias than $J_{\rm
CPC}$.

##  4 Related Work

As a subset of unsupervised representation learning, self-supervised
representation learning (SSL) adopts self-defined signals as supervision and
uses the learned representation for downstream tasks, such as object detection
and image captioning (Liu et al., 2020). We categorize SSL work into two
groups: when the signal is the input’s hidden property or the corresponding
view of the input. For the first group, for example, Jigsaw puzzle (Noroozi &
Favaro, 2016) shuffles the image patches and defines the SSL task for
predicting the shuffled positions of the image patches. Other instances are
Predicting Rotations (Gidaris et al., 2018) and Shuffle & Learn (Misra et al.,
2016). For the second group, the SSL task aims at modeling the co-occurrence
of multiple views of data, via the contrastive or the predictive learning
objectives (Tsai et al., 2020a). The predictive objectives encourage
reconstruction from one view of the data to the other, such as predicting the
lower part of an image from its upper part (ImageGPT by Chen et al. (2020a)).
Comparing the contrastive with predictive learning approaches, Tsai et al.
(2020a) points out that the former requires less computational resources for a
good performance but suffers more from the over-fitting problem.

Theoretical analysis (Arora et al., 2019; Tsai et al., 2020a; Tosh et al.,
2020) suggests the contrastively learned representations can lead to a good
downstream performance. Beyond the theory, Tian et al. (2020) shows what
matters more for the performance are 1) the choice of the contrastive learning
objective; and 2) the creation of the positive and negative data pairs in the
contrastive objective. Recent work (Khosla et al., 2020) extends the usage of
contrastive learning from the self-supervised setting to the supervised
setting. The supervised setting defines the positive pairs as the data from
the same class in the contrastive objective, while the self-supervised setting
defines the positive pairs as the data with different augmentations.

Our work also closely rates to the skewed divergence measurement between
distributions (Lee, 1999; 2001; Nielsen, 2010; Yamada et al., 2013). Recall
that the usage of the relative parameters plays a crucial role to regularize
our objective for its boundness and low variance. This idea is similar to the
skewed divergence measurement, that when calculating the divergence between
distributions $P$ and $Q$, instead of considering ${\rm D}(P\,\|\,Q)$, these
approaches consider ${\rm D}(P\,\|\,\alpha P+(1-\alpha)Q)$ with $D$
representing the divergence and $0<\alpha<1$. A natural example is that the
Jensen-Shannon divergence is a symmetric skewed KL divergence: ${D}_{\rm
JS}(P\,\|\,Q)=0.5{D}_{\rm KL}(P\,\|\,0.5P+0.5Q)+0.5{D}_{\rm
KL}(Q\,\|\,0.5P+0.5Q)$. Compared to the non-skewed counterpart, the skewed
divergence has shown to have a more robust estimation for its value (Lee,
1999; 2001; Yamada et al., 2013). Different from these works that focus on
estimating the values of distribution divergence, we focus on learning self-
supervised representations.

##  5 Conclusion

In this work, we present RPC, the Relative Predictive Coding, that achieves a
good balance among the three challenges when modeling a contrastive learning
objective: training stability, sensitivity to minibatch size, and downstream
task performance. We believe this work brings an appealing option for training
self-supervised models and inspires future work to design objectives for
balancing the aforementioned three challenges. In the future, we are
interested in applying RPC in other application domains and developing more
principled approaches for better representation learning.

## Acknowledgement

This work was supported in part by the NSF IIS1763562, NSF Awards #1750439
#1722822, National Institutes of Health, IARPA D17PC00340, ONR Grant
N000141812861, and Facebook PhD Fellowship. We would also like to acknowledge
NVIDIA’s GPU support and Cloud TPU support from Google’s TensorFlow Research
Cloud (TFRC).

## References

  * Abadi et al. (2016) Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al.  Tensorflow: A system for large-scale machine learning.  In _12th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 16)_, pp. 265–283, 2016.
  * Anthony & Bartlett (2009) Martin Anthony and Peter L Bartlett.  _Neural network learning: Theoretical foundations_.  cambridge university press, 2009.
  * Arora et al. (2019) Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi.  A theoretical analysis of contrastive unsupervised representation learning.  _arXiv preprint arXiv:1902.09229_ , 2019.
  * Baevski et al. (2020) Alexei Baevski, Henry Zhou, Abdelrahman Mohamed, and Michael Auli.  wav2vec 2.0: A framework for self-supervised learning of speech representations.  _arXiv preprint arXiv:2006.11477_ , 2020.
  * Bartlett (1998) Peter L Bartlett.  The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network.  _IEEE transactions on Information Theory_ , 44(2):525–536, 1998.
  * Belghazi et al. (2018) Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm.  Mine: mutual information neural estimation.  _arXiv preprint arXiv:1801.04062_ , 2018.
  * Caron et al. (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.09882_ , 2020.
  * Chen et al. (2020a) Mark Chen, Alec Radford, Rewon Child, Jeff Wu, Heewoo Jun, Prafulla Dhariwal, David Luan, and Ilya Sutskever.  Generative pretraining from pixels.  In _Proceedings of the 37th International Conference on Machine Learning_ , 2020a.
  * Chen et al. (2020b) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  _arXiv preprint arXiv:2002.05709_ , 2020b.
  * Chen et al. (2020c) Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton.  Big self-supervised models are strong semi-supervised learners.  _arXiv preprint arXiv:2006.10029_ , 2020c.
  * Chuang et al. (2020) Ching-Yao Chuang, Joshua Robinson, Lin Yen-Chen, Antonio Torralba, and Stefanie Jegelka.  Debiased contrastive learning.  _arXiv preprint arXiv:2007.00224_ , 2020.
  * Coates et al. (2011) Adam Coates, Andrew Ng, and Honglak Lee.  An analysis of single-layer networks in unsupervised feature learning.  In _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , pp. 215–223, 2011.
  * Cover & Thomas (2012) Thomas M Cover and Joy A Thomas.  _Elements of information theory_.  John Wiley & Sons, 2012.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Donsker & Varadhan (1975) Monroe D Donsker and SR Srinivasa Varadhan.  Asymptotic evaluation of certain markov process expectations for large time, i.  _Communications on Pure and Applied Mathematics_ , 28(1):1–47, 1975.
  * Gidaris et al. (2018) Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  _arXiv preprint arXiv:1803.07728_ , 2018.
  * Gulrajani et al. (2017) Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville.  Improved training of wasserstein gans.  In _Advances in neural information processing systems_ , pp. 5767–5777, 2017.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * He et al. (2020) 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 on Computer Vision and Pattern Recognition_ , pp. 9729–9738, 2020.
  * Hjelm et al. (2018) R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio.  Learning deep representations by mutual information estimation and maximization.  _arXiv preprint arXiv:1808.06670_ , 2018.
  * Hochreiter & Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Hornik et al. (1989) K Hornik, M Stinchcombe, and H White.  Multilayer feedforward networks are universal approximators.  _Neural Networks_ , 2(5):359–366, 1989.
  * Ioffe & Szegedy (2015) Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  _arXiv preprint arXiv:1502.03167_ , 2015.
  * Khosla et al. (2020) Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan.  Supervised contrastive learning.  _arXiv preprint arXiv:2004.11362_ , 2020.
  * Kipf et al. (2019) Thomas Kipf, Elise van der Pol, and Max Welling.  Contrastive learning of structured world models.  _arXiv preprint arXiv:1911.12247_ , 2019.
  * Kong et al. (2019) Lingpeng Kong, Cyprien de Masson d’Autume, Wang Ling, Lei Yu, Zihang Dai, and Dani Yogatama.  A mutual information maximization perspective of language representation learning.  _arXiv preprint arXiv:1910.08350_ , 2019.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Lake et al. (2015) Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum.  Human-level concept learning through probabilistic program induction.  _Science_ , 350(6266):1332–1338, 2015.
  * Lee (1999) Lillian Lee.  Measures of distributional similarity.  In _Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics_ , pp. 25–32, College Park, Maryland, USA, June 1999. Association for Computational Linguistics.  doi: 10.3115/1034678.1034693.  URL https://www.aclweb.org/anthology/P99-1004.
  * Lee (2001) Lillian Lee.  On the effectiveness of the skew divergence for statistical language analysis.  In _AISTATS_. Citeseer, 2001.
  * Li et al. (2019) Xiang Li, Wenhai Wang, Xiaolin Hu, and Jian Yang.  Selective kernel networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 510–519, 2019.
  * Liu et al. (2020) Xiao Liu, Fanjin Zhang, Zhenyu Hou, Zhaoyu Wang, Li Mian, Jing Zhang, and Jie Tang.  Self-supervised learning: Generative or contrastive.  _arXiv e-prints_ , pp. arXiv–2006, 2020.
  * Liu et al. (2015) Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.  Deep learning face attributes in the wild.  In _Proceedings of the IEEE international conference on computer vision_ , pp. 3730–3738, 2015.
  * Löwe et al. (2019) Sindy Löwe, Peter O’Connor, and Bastiaan Veeling.  Putting an end to end-to-end: Gradient-isolated learning of representations.  In _Advances in Neural Information Processing Systems_ , pp. 3039–3051, 2019.
  * McAllester & Stratos (2020) David McAllester and Karl Stratos.  Formal limitations on the measurement of mutual information.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 875–884, 2020.
  * Misra et al. (2016) Ishan Misra, C Lawrence Zitnick, and Martial Hebert.  Shuffle and learn: unsupervised learning using temporal order verification.  In _European Conference on Computer Vision_ , pp. 527–544. Springer, 2016.
  * Nguyen et al. (2010) XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan.  Estimating divergence functionals and the likelihood ratio by convex risk minimization.  _IEEE Transactions on Information Theory_ , 56(11):5847–5861, 2010.
  * Nielsen (2010) Frank Nielsen.  A family of statistical symmetric divergences based on jensen’s inequality.  _arXiv preprint arXiv:1009.4004_ , 2010.
  * Nielsen & Nock (2013) Frank Nielsen and Richard Nock.  On the chi square and higher-order chi distances for approximating f-divergences.  _IEEE Signal Processing Letters_ , 21(1):10–13, 2013.
  * Noroozi & Favaro (2016) Mehdi Noroozi and Paolo Favaro.  Unsupervised learning of visual representations by solving jigsaw puzzles.  In _European Conference on Computer Vision_ , pp. 69–84. Springer, 2016.
  * Nowozin et al. (2016) Sebastian Nowozin, Botond Cseke, and Ryota Tomioka.  f-gan: Training generative neural samplers using variational divergence minimization.  In _Advances in neural information processing systems_ , pp. 271–279, 2016.
  * Oord et al. (2018) Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ , 2018.
  * Ozair et al. (2019) Sherjil Ozair, Corey Lynch, Yoshua Bengio, Aaron Van den Oord, Sergey Levine, and Pierre Sermanet.  Wasserstein dependency measure for representation learning.  In _Advances in Neural Information Processing Systems_ , pp. 15604–15614, 2019.
  * Panayotov et al. (2015) Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur.  Librispeech: an asr corpus based on public domain audio books.  In _2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 5206–5210. IEEE, 2015.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems_ , pp. 8024–8035, 2019.
  * Poole et al. (2019) Ben Poole, Sherjil Ozair, Aaron van den Oord, Alexander A Alemi, and George Tucker.  On variational bounds of mutual information.  _arXiv preprint arXiv:1905.06922_ , 2019.
  * Rivière et al. (2020) Morgane Rivière, Armand Joulin, Pierre-Emmanuel Mazaré, and Emmanuel Dupoux.  Unsupervised pretraining transfers well across languages.  In _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 7414–7418. IEEE, 2020.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  _International journal of computer vision_ , 115(3):211–252, 2015.
  * Song & Ermon (2019) Jiaming Song and Stefano Ermon.  Understanding the limitations of variational mutual information estimators.  _arXiv preprint arXiv:1910.06222_ , 2019.
  * Tian et al. (2019) Yonglong Tian, Dilip Krishnan, and Phillip Isola.  Contrastive multiview coding.  _arXiv preprint arXiv:1906.05849_ , 2019.
  * Tian et al. (2020) Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola.  What makes for good views for contrastive learning.  _arXiv preprint arXiv:2005.10243_ , 2020.
  * Tosh et al. (2020) Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu.  Contrastive learning, multi-view redundancy, and linear models.  _arXiv preprint arXiv:2008.10150_ , 2020.
  * Tsai et al. (2020a) Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency.  Demystifying self-supervised learning: An information-theoretical framework.  _arXiv preprint arXiv:2006.05576_ , 2020a.
  * Tsai et al. (2020b) Yao-Hung Hubert Tsai, Han Zhao, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov.  Neural methods for point-wise dependency estimation.  _arXiv preprint arXiv:2006.05553_ , 2020b.
  * Tschannen et al. (2019) Michael Tschannen, Josip Djolonga, Paul K Rubenstein, Sylvain Gelly, and Mario Lucic.  On mutual information maximization for representation learning.  _arXiv preprint arXiv:1907.13625_ , 2019.
  * Van der Vaart (2000) Aad W Van der Vaart.  _Asymptotic statistics_ , volume 3.  Cambridge university press, 2000.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in neural information processing systems_ , pp. 5998–6008, 2017.
  * Velickovic et al. (2019) Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm.  Deep graph infomax.  In _ICLR (Poster)_ , 2019.
  * Yamada et al. (2013) Makoto Yamada, Taiji Suzuki, Takafumi Kanamori, Hirotaka Hachiya, and Masashi Sugiyama.  Relative density-ratio estimation for robust distribution comparison.  _Neural computation_ , 25(5):1324–1370, 2013\.
  * You et al. (2017) Yang You, Igor Gitman, and Boris Ginsburg.  Large batch training of convolutional networks.  _arXiv preprint arXiv:1708.03888_ , 2017.

##  Appendix A Appendix

###  A.1 Proof of Lemma 1 in the Main Text

######  Lemma 2 (Optimal Solution for $J_{\rm RPC}$, restating Lemma 1 in the
main text)

Let

$J_{\rm RPC}(X,Y):=\underset{f\in\mathcal{F}}{\rm
sup}\,\mathbb{E}_{P_{XY}}[f(x,y)]-\alpha\mathbb{E}_{P_{X}P_{Y}}[f(x,y)]-\frac{\beta}{2}\mathbb{E}_{P_{XY}}\left[f^{2}(x,y)\right]-\frac{\gamma}{2}\mathbb{E}_{P_{X}P_{Y}}\left[f^{2}(x,y)\right]$

and $r(x,y)=\frac{p(x,y)}{p(x)p(y)}$ be the density ratio. $J_{\rm RPC}$ has
the optimal solution

$f^{*}(x,y)=\frac{r(x,y)-\alpha}{\beta\,r(x,y)+\gamma}:=r_{\alpha,\beta,\gamma}(x,y)\,\,{\rm
with}\,\,-\frac{\alpha}{\gamma}\leq
r_{\alpha,\beta,\gamma}\leq\frac{1}{\beta}.$

Proof: The second-order functional derivative of the objective is

$-\beta dP_{X,Y}-\gamma dP_{X}P_{Y},$

which is always negative. The negative second-order functional derivative
implies the objective has a supreme value. Then, take the first-order
functional derivative $\frac{\partial J_{\rm RPC}}{\partial m}$ and set it to
zero:

$dP_{X,Y}-\alpha\cdot dP_{X}P_{Y}-\beta\cdot f(x,y)\cdot dP_{X,Y}-\gamma\cdot
f(x,y)\cdot dP_{X}P_{Y}=0.$

We then get

$f^{*}(x,y)=\frac{dP_{X,Y}-\alpha\cdot dP_{X}P_{Y}}{\beta\cdot
dP_{X,Y}+\gamma\cdot dP_{X}P_{Y}}=\frac{p(x,y)-\alpha p(x)p(y)}{\beta
p(x,y)+\gamma p(x)p(y)}=\frac{r(x,y)-\alpha}{\beta r(x,y)+\gamma}.$

Since $0\leq r(x,y)\leq\infty$, we have
$-\frac{\alpha}{\gamma}\leq\frac{r(x,y)-\alpha}{\beta
r(x,y)+\gamma}\leq\frac{1}{\beta}$. Hence,

$\forall\beta\neq 0,\gamma\neq
0,f^{*}(x,y):=r_{\alpha,\beta,\gamma}(x,y)\,\,{\rm
with}\,\,-\frac{\alpha}{\gamma}\leq
r_{\alpha,\beta,\gamma}\leq\frac{1}{\beta}.$

$\square$

###  A.2 Relation between $J_{\rm RPC}$ and $D_{\chi^{2}}$

In this subsection, we aim to show the following: 1)
$D_{\chi^{2}}(P_{XY}\,\|\,P_{X}P_{Y})=\mathbb{E}_{P_{X}P_{Y}}[r^{2}(x,y)]-1$;
and 2) $J_{\rm
RPC}(X,Y)=\frac{\beta+\gamma}{2}\mathbb{E}_{P^{\prime}}[r_{\alpha,\beta,\gamma}^{2}(x,y)]$
by having
$P^{\prime}=\frac{\beta}{\beta+\gamma}P_{XY}+\frac{\gamma}{\beta+\gamma}P_{X}P_{Y}$
as the mixture distribution of $P_{XY}$ and $P_{X}P_{Y}$.

###### Lemma 3

$D_{\chi^{2}}(P_{XY}\,\|\,P_{X}P_{Y})=\mathbb{E}_{P_{X}P_{Y}}[r^{2}(x,y)]-1$

Proof: By definition (Nielsen & Nock, 2013),

$\begin{split}D_{\chi^{2}}(P_{XY}\,\|\,P_{X}P_{Y})&=\int\frac{\Big{(}dP_{XY}\Big{)}^{2}}{dP_{X}P_{Y}}-1=\int\Big{(}\frac{dP_{XY}}{dP_{X}P_{Y}}\Big{)}^{2}dP_{X}P_{Y}-1\\\
&=\int\Big{(}\frac{p(x,y)}{p(x)p(y)}\Big{)}^{2}dP_{X}P_{Y}-1=\int
r^{2}(x,y)dP_{X}P_{Y}-1\\\
&=\mathbb{E}_{P_{X}P_{Y}}[r^{2}(x,y)]-1.\end{split}$

$\square$

###### Lemma 4

Defining
$P^{\prime}=\frac{\beta}{\beta+\gamma}P_{XY}+\frac{\gamma}{\beta+\gamma}P_{X}P_{Y}$
as a mixture distribution of $P_{XY}$ and $P_{X}P_{Y}$, $J_{\rm
RPC}(X,Y)=\frac{\beta+\gamma}{2}\mathbb{E}_{P^{\prime}}[r_{\alpha,\beta,\gamma}^{2}(x,y)]$.

Proof: Plug in the optimal solution $f^{*}(x,y)=\frac{dP_{X,Y}-\alpha\cdot
dP_{X}P_{Y}}{\beta\cdot dP_{X,Y}+\gamma\cdot dP_{X}P_{Y}}$ (see Lemma 2) into
$J_{\rm RPC}$:

$\begin{split}J_{\rm
RPC}&=\mathbb{E}_{P_{XY}}[f^{*}(x,y)]-\alpha\mathbb{E}_{P_{X}P_{Y}}[f^{*}(x,y)]-\frac{\beta}{2}\mathbb{E}_{P_{XY}}\left[{f^{*}}^{2}(x,y)\right]-\frac{\gamma}{2}\mathbb{E}_{P_{X}P_{Y}}\left[{f^{*}}^{2}(x,y)\right]\\\
&=\int f^{*}(x,y)\cdot\Big{(}dP_{XY}-\alpha\cdot
dP_{X}P_{Y}\Big{)}-\frac{1}{2}{f^{*}}^{2}(x,y)\cdot\Big{(}\beta\cdot
dP_{XY}+\gamma\cdot dP_{X}P_{Y}\Big{)}\\\ &=\int\frac{dP_{X,Y}-\alpha\cdot
dP_{X}P_{Y}}{\beta\cdot dP_{X,Y}+\gamma\cdot
dP_{X}P_{Y}}\Big{(}dP_{XY}-\alpha\cdot
dP_{X}P_{Y}\Big{)}-\frac{1}{2}\Big{(}\frac{dP_{X,Y}-\alpha\cdot
dP_{X}P_{Y}}{\beta\cdot dP_{X,Y}+\gamma\cdot
dP_{X}P_{Y}}\Big{)}^{2}\Big{(}\beta\cdot dP_{XY}+\gamma\cdot
dP_{X}P_{Y}\Big{)}\\\ &=\frac{1}{2}\int\Big{(}\frac{dP_{X,Y}-\alpha\cdot
dP_{X}P_{Y}}{\beta\cdot dP_{X,Y}+\gamma\cdot
dP_{X}P_{Y}}\Big{)}^{2}\Big{(}\beta\cdot dP_{XY}+\gamma\cdot
dP_{X}P_{Y}\Big{)}\\\
&=\frac{\beta+\gamma}{2}\int\Big{(}\frac{dP_{X,Y}-\alpha\cdot
dP_{X}P_{Y}}{\beta\cdot dP_{X,Y}+\gamma\cdot
dP_{X}P_{Y}}\Big{)}^{2}\Big{(}\frac{\beta}{\beta+\gamma}\cdot
dP_{XY}+\frac{\gamma}{\beta+\gamma}\cdot dP_{X}P_{Y}\Big{)}.\end{split}$

Since we define $r_{\alpha,\beta,\gamma}=\frac{dP_{X,Y}-\alpha\cdot
dP_{X}P_{Y}}{\beta\cdot dP_{X,Y}+\gamma\cdot dP_{X}P_{Y}}$ and
$P^{\prime}=\frac{\beta}{\beta+\gamma}P_{XY}+\frac{\gamma}{\beta+\gamma}P_{X}P_{Y}$,

$J_{\rm
RPC}=\frac{\beta+\gamma}{2}\mathbb{E}_{P^{\prime}}[r^{2}_{\alpha,\beta,\gamma}(x,y)].$

$\square$

###  A.3 Proof of Proposition 1 in the Main Text

The proof contains two parts: showing $0\leq J_{\rm
RPC}\leq\frac{1}{2\beta}+\frac{\alpha^{2}}{2\gamma}$ (see Section A.3.1) and
$\hat{J}^{m,n}_{\rm RPC}$ is a consistent estimator for $J_{\rm RPC}$ (see
Section A.3.2).

####  A.3.1 Boundness of $J_{\rm RPC}$

######  Lemma 5 (Boundness of $J_{\rm RPC}$)

$0\leq J_{\rm RPC}\leq\frac{1}{2\beta}+\frac{\alpha^{2}}{2\gamma}$

Proof: Lemma 4 suggests $J_{\rm
RPC}(X,Y)=\frac{\beta+\gamma}{2}\mathbb{E}_{P^{\prime}}[r_{\alpha,\beta,\gamma}^{2}(x,y)]$
with
$P^{\prime}=\frac{\beta}{\beta+\gamma}P_{XY}+\frac{\gamma}{\beta+\gamma}P_{X}P_{Y}$
as the mixture distribution of $P_{XY}$ and $P_{X}P_{Y}$. Hence, it is obvious
$J_{\rm RPC}(X,Y)\geq 0$.

We leverage the intermediate results in the proof of Lemma 4:

$\begin{split}J_{\rm
RPC}(X,Y)&=\frac{1}{2}\int\Big{(}\frac{dP_{X,Y}-\alpha\cdot
dP_{X}P_{Y}}{\beta\cdot dP_{X,Y}+\gamma\cdot
dP_{X}P_{Y}}\Big{)}^{2}\Big{(}\beta\cdot dP_{XY}+\gamma\cdot
dP_{X}P_{Y}\Big{)}\\\ &=\frac{1}{2}\int
dP_{X,Y}\Big{(}\frac{dP_{X,Y}-\alpha\cdot dP_{X}P_{Y}}{\beta\cdot
dP_{X,Y}+\gamma\cdot dP_{X}P_{Y}}\Big{)}-\frac{\alpha}{2}\int
dP_{X}P_{Y}\Big{(}\frac{dP_{X,Y}-\alpha\cdot dP_{X}P_{Y}}{\beta\cdot
dP_{X,Y}+\gamma\cdot dP_{X}P_{Y}}\Big{)}\\\
&=\frac{1}{2}\mathbb{E}_{P_{XY}}[r_{\alpha,\beta,\gamma}(x,y)]-\frac{\alpha}{2}\mathbb{E}_{P_{X}P_{Y}}[r_{\alpha,\beta,\gamma}(x,y)].\end{split}$

Since $-\frac{\alpha}{\gamma}\leq r_{\alpha,\beta,\gamma}\leq\frac{1}{\beta}$,
$J_{\rm RPC}(X,Y)\leq\frac{1}{2\beta}+\frac{\alpha^{2}}{2\gamma}$. $\square$

####  A.3.2 Consistency

We first recall the definition of the estimation of $J_{\rm RPC}$:

######  Definition 2 ($\hat{J}^{m,n}_{\rm RPC}$, empirical estimation of
$J_{\rm RPC}$, restating Definition 1 in the main text)

We parametrize $f$ via a family of neural networks
$\mathcal{F}_{\Theta}:=\\{f_{\theta}:\theta\in\Theta\subseteq\mathbb{R}^{d}\\}$
where $d\in\mathbb{N}$ and $\Theta$ is compact. Let
$\\{x_{i},y_{i}\\}_{i=1}^{n}$ be $n$ samples drawn uniformly at random from
$P_{XY}$ and $\\{x^{\prime}_{j},y^{\prime}_{j}\\}_{j=1}^{m}$ be $m$ samples
drawn uniformly at random from $P_{X}P_{Y}$. Then,

$\hat{J}^{m,n}_{\rm
RPC}=\sup_{{f}_{\theta}\in\mathcal{F}_{\Theta}}\frac{1}{n}\sum_{i=1}^{n}f_{\theta}(x_{i},y_{i})-\frac{1}{m}\sum_{j=1}^{m}\alpha
f_{\theta}(x^{\prime}_{j},y^{\prime}_{j})-\frac{1}{n}\sum_{i=1}^{n}\frac{\beta}{2}f_{\theta}^{2}(x_{i},y_{i})-\frac{1}{m}\sum_{j=1}^{m}\frac{\gamma}{2}f_{\theta}^{2}(x^{\prime}_{j},y^{\prime}_{j}).$

Our goal is to show that $\hat{J}^{m,n}_{\rm RPC}$ is a consistent estimator
for $J_{\rm RPC}$. We begin with the following definition:

$\hat{J}^{m,n}_{{\rm
RPC},\theta}:=\frac{1}{n}\sum_{i=1}^{n}f_{\theta}(x_{i},y_{i})-\frac{1}{m}\sum_{j=1}^{m}\alpha
f_{\theta}(x^{\prime}_{j},y^{\prime}_{j})-\frac{1}{n}\sum_{i=1}^{n}\frac{\beta}{2}f_{\theta}^{2}(x_{i},y_{i})-\frac{1}{m}\sum_{j=1}^{m}\frac{\gamma}{2}f_{\theta}^{2}(x^{\prime}_{j},y^{\prime}_{j})$
(3)

and

$\mathbb{E}\Big{[}\hat{J}_{{\rm
RPC},\theta}\Big{]}:=\mathbb{E}_{P_{XY}}[f_{\theta}(x,y)]-\alpha\mathbb{E}_{P_{X}P_{Y}}[f_{\theta}(x,y)]-\frac{\beta}{2}\mathbb{E}_{P_{XY}}[f^{2}_{\theta}(x,y)]-\frac{\gamma}{2}\mathbb{E}_{P_{X}P_{Y}}[f^{2}_{\theta}(x,y)].$
(4)

Then, we follow the steps:

  * •

The first part is about estimation. We show that, with high probability,
$\hat{J}^{m,n}_{{\rm RPC},\theta}$ is close to $\mathbb{E}\Big{[}\hat{J}_{{\rm
RPC},\theta}\Big{]}$, for any given $\theta$.

  * •

The second part is about approximation. We will apply the universal
approximation lemma of neural networks (Hornik et al., 1989) to show that
there exists a network $\theta^{*}$ such that $\mathbb{E}\Big{[}\hat{J}_{{\rm
RPC},\theta^{*}}\Big{]}$ is close to $J_{\rm RPC}$.

##### Part I - Estimation: With high probability, $\hat{J}^{m,n}_{{\rm
RPC},\theta}$ is close to $\mathbb{E}\Big{[}\hat{J}_{{\rm
RPC},\theta}\Big{]}$, for any given $\theta$.

Throughout the analysis on the uniform convergence, we need the assumptions on
the boundness and smoothness of the function $f_{\theta}$. Since we show the
optimal function $f$ is bounded in $J_{\rm RPC}$, we can use the same bounded
values for $f_{\theta}$ without losing too much precision. The smoothness of
the function suggests that the output of the network should only change
slightly when only slightly perturbing the parameters. Specifically, the two
assumptions are as follows:

######  Assumption 1 (boundness of $f_{\theta}$)

There exist universal constants such that $\forall
f_{\theta}\in\mathcal{F}_{\Theta}$, $C_{L}\leq f_{\theta}\leq C_{U}$. For
notations simplicity, we let $M=C_{U}-C_{L}$ be the range of $f_{\theta}$ and
$U={\rm max}\,\\{|C_{U}|,|C_{L}|\\}$ be the maximal absolute value of
$f_{\theta}$. In the paper, we can choose to constrain that
$C_{L}=-\frac{\alpha}{\gamma}$ and $C_{U}=\frac{1}{\beta}$ since the optimal
function $f^{*}$ has $-\frac{\alpha}{\gamma}\leq f^{*}\leq\frac{1}{\beta}$.

######  Assumption 2 (smoothness of $f_{\theta}$)

There exists constant $\rho>0$ such that
$\forall(x,y)\in(\mathcal{X}\times\mathcal{Y})$ and
$\theta_{1},\theta_{2}\in\Theta$,
$|f_{\theta_{1}}(x,y)-f_{\theta_{2}}(x,y)|\leq\rho|\theta_{1}-\theta_{2}|$.

Now, we can bound the rate of uniform convergence of a function class in terms
of covering number (Bartlett, 1998):

######  Lemma 6 (Estimation)

Let $\epsilon>0$ and $\mathcal{N}(\Theta,\epsilon)$ be the covering number of
$\Theta$ with radius $\epsilon$. Then,

$\begin{split}&\Pr\left(\sup_{f_{\theta}\in\mathcal{F}_{\Theta}}\left|\hat{J}^{m,n}_{{\rm
RPC},\theta}-\mathbb{E}\Big{[}\hat{J}_{{\rm
RPC},\theta}\Big{]}\right|\geq{\epsilon}\right)\\\
\leq&2\mathcal{N}(\Theta,\frac{\epsilon}{4\rho\big{(}1+\alpha+2(\beta+\gamma)U\big{)}})\Bigg{(}{\rm
exp}\Big{(}-\frac{n\epsilon^{2}}{32M^{2}}\Big{)}+{\rm
exp}\Big{(}-\frac{m\epsilon^{2}}{32M^{2}\alpha^{2}}\Big{)}+{\rm
exp}\Big{(}-\frac{n\epsilon^{2}}{32U^{2}\beta^{2}}\Big{)}+{\rm
exp}\Big{(}-\frac{m\epsilon^{2}}{32U^{2}\gamma^{2}}\Big{)}\Bigg{)}.\end{split}$

Proof: For notation simplicity, we define the operators

  * •

$P(f)=\mathbb{E}_{P_{XY}}[f(x,y)]$ and
$P_{n}(f)=\frac{1}{n}\sum_{i=1}^{n}f(x_{i},y_{i})$

  * •

$Q(f)=\mathbb{E}_{P_{X}P_{Y}}[f(x,y)]$ and
$Q_{m}(f)=\frac{1}{m}\sum_{j=1}^{m}f(x^{\prime}_{j},y^{\prime}_{j})$

Hence,

$\begin{split}&\left|\hat{J}^{m,n}_{{\rm
RPC},\theta}-\mathbb{E}\Big{[}\hat{J}_{{\rm RPC},\theta}\Big{]}\right|\\\
=&\left|P_{n}(f_{\theta})-P(f_{\theta})-\alpha Q_{m}(f_{\theta})+\alpha
Q(f_{\theta})-\beta P_{n}(f_{\theta}^{2})+\beta P(f_{\theta}^{2})-\gamma
Q_{m}(f_{\theta}^{2})+\gamma Q(f_{\theta}^{2})\right|\\\
\leq&\left|P_{n}(f_{\theta})-P(f_{\theta})\right|+\alpha\left|Q_{m}(f_{\theta})-Q(f_{\theta})\right|+\beta\left|P_{n}(f_{\theta}^{2})-P(f_{\theta}^{2})\right|+\gamma\left|Q_{m}(f_{\theta}^{2})-Q(f_{\theta}^{2})\right|\end{split}$

Let
$\epsilon^{\prime}=\frac{\epsilon}{4\rho\big{(}1+\alpha+2(\beta+\gamma)U\big{)}}$
and $T:=\mathcal{N}(\Theta,\epsilon^{\prime})$. Let
$C=\\{f_{\theta_{1}},f_{\theta_{2}},\cdots,f_{\theta_{T}}\\}$ with
$\\{\theta_{1},\theta_{2},\cdots,\theta_{T}\\}$ be such that
$B_{\infty}(\theta_{1},\epsilon^{\prime})$, $\cdots$,
$B_{\infty}(\theta_{T},\epsilon^{\prime})$ are $\epsilon^{\prime}$ cover.
Hence, for any $f_{\theta}\in\mathcal{F}_{\Theta}$, there is an
$f_{\theta_{k}}\in C$ such that
$\|\theta-\theta_{k}\|_{\infty}\leq\epsilon^{\prime}$.

Then, for any $f_{\theta_{k}}\in C$:

$\begin{split}&\left|\hat{J}^{m,n}_{{\rm
RPC},\theta}-\mathbb{E}\Big{[}\hat{J}_{{\rm RPC},\theta}\Big{]}\right|\\\
\leq&\left|P_{n}(f_{\theta})-P(f_{\theta})\right|+\alpha\left|Q_{m}(f_{\theta})-Q(f_{\theta})\right|+\beta\left|P_{n}(f_{\theta}^{2})-P(f_{\theta}^{2})\right|+\gamma\left|Q_{m}(f_{\theta}^{2})-Q(f_{\theta}^{2})\right|\\\
\leq&\left|P_{n}(f_{\theta_{k}})-P(f_{\theta_{k}})\right|+\left|P_{n}(f_{\theta})-P_{n}(f_{\theta_{k}})\right|+\left|P(f_{\theta})-P(f_{\theta_{k}})\right|\\\
&+\alpha\bigg{(}\left|Q_{m}(f_{\theta_{k}})-Q(f_{\theta_{k}})\right|+\left|Q_{m}(f_{\theta})-Q_{m}(f_{\theta_{k}})\right|+\left|Q(f_{\theta})-Q(f_{\theta_{k}})\right|\bigg{)}\\\
&+\beta\bigg{(}\left|P_{n}(f^{2}_{\theta_{k}})-P(f^{2}_{\theta_{k}})\right|+\left|P_{n}(f^{2}_{\theta})-P_{n}(f^{2}_{\theta_{k}})\right|+\left|P(f^{2}_{\theta})-P(f^{2}_{\theta_{k}})\right|\bigg{)}\\\
&+\gamma\bigg{(}\left|Q_{m}(f^{2}_{\theta_{k}})-Q(f^{2}_{\theta_{k}})\right|+\left|Q_{m}(f^{2}_{\theta})-Q_{m}(f^{2}_{\theta_{k}})\right|+\left|Q(f^{2}_{\theta})-Q(f^{2}_{\theta_{k}})\right|\bigg{)}\\\
\leq&\left|P_{n}(f_{\theta_{k}})-P(f_{\theta_{k}})\right|+\rho\|\theta-\theta_{k}\|+\rho\|\theta-\theta_{k}\|\\\
&+\alpha\bigg{(}\left|Q_{m}(f_{\theta_{k}})-Q(f_{\theta_{k}})\right|+\rho\|\theta-\theta_{k}\|+\rho\|\theta-\theta_{k}\|\bigg{)}\\\
&+\beta\bigg{(}\left|P_{n}(f^{2}_{\theta_{k}})-P(f^{2}_{\theta_{k}})\right|+2\rho
U\|\theta-\theta_{k}\|+2\rho U\|\theta-\theta_{k}\|\bigg{)}\\\
&+\gamma\bigg{(}\left|Q_{m}(f^{2}_{\theta_{k}})-Q(f^{2}_{\theta_{k}})\right|+2\rho
U\|\theta-\theta_{k}\|+2\rho U\|\theta-\theta_{k}\|\bigg{)}\\\
=&\left|P_{n}(f_{\theta_{k}})-P(f_{\theta_{k}})\right|+\alpha\left|Q_{m}(f_{\theta_{k}})-Q(f_{\theta_{k}})\right|+\beta\left|P_{n}(f^{2}_{\theta_{k}})-P(f^{2}_{\theta_{k}})\right|+\gamma\left|Q_{m}(f^{2}_{\theta_{k}})-Q(f^{2}_{\theta_{k}})\right|\\\
&+2\rho\big{(}1+\alpha+2(\beta+\gamma)U\big{)}\|\theta-\theta_{k}\|\\\
\leq&\left|P_{n}(f_{\theta_{k}})-P(f_{\theta_{k}})\right|+\alpha\left|Q_{m}(f_{\theta_{k}})-Q(f_{\theta_{k}})\right|+\beta\left|P_{n}(f^{2}_{\theta_{k}})-P(f^{2}_{\theta_{k}})\right|+\gamma\left|Q_{m}(f^{2}_{\theta_{k}})-Q(f^{2}_{\theta_{k}})\right|+\frac{\epsilon}{2},\end{split}$

where

  * •

$\left|P_{n}(f_{\theta})-P_{n}(f_{\theta_{k}})\right|\leq\rho\|\theta-\theta_{k}\|$
due to Assumption 2, and the result also applies for
$\left|P(f_{\theta})-P(f_{\theta_{k}})\right|$,
$\left|Q_{m}(f_{\theta})-Q_{m}(f_{\theta_{k}})\right|$, and
$\left|Q(f_{\theta})-Q(f_{\theta_{k}})\right|$.

  * •

$\left|P_{n}(f^{2}_{\theta})-P_{n}(f^{2}_{\theta_{k}})\right|\leq
2\|f_{\theta}\|_{\infty}\rho\|\theta-\theta_{k}\|\leq 2\rho
U\|\theta-\theta_{k}\|$ due to Assumptions 1 and 2. The result also applies
for $\left|P(f^{2}_{\theta})-P(f^{2}_{\theta_{k}})\right|$,
$\left|Q_{m}(f^{2}_{\theta})-Q_{m}(f^{2}_{\theta_{k}})\right|$, and
$\left|Q(f^{2}_{\theta})-Q(f^{2}_{\theta_{k}})\right|$.

Hence,

$\begin{split}&\Pr\left(\sup_{f_{\theta}\in\mathcal{F}_{\Theta}}\left|\hat{J}^{m,n}_{{\rm
RPC},\theta}-\mathbb{E}\Big{[}\hat{J}_{{\rm
RPC},\theta}\Big{]}\right|\geq{\epsilon}\right)\\\
\leq&\Pr\left(\underset{f_{\theta_{k}}\in C}{\rm
max}\left|P_{n}(f_{\theta_{k}})-P(f_{\theta_{k}})\right|+\alpha\left|Q_{m}(f_{\theta_{k}})-Q(f_{\theta_{k}})\right|+\beta\left|P_{n}(f^{2}_{\theta_{k}})-P(f^{2}_{\theta_{k}})\right|+\gamma\left|Q_{m}(f^{2}_{\theta_{k}})-Q(f^{2}_{\theta_{k}})\right|+\frac{\epsilon}{2}\geq{\epsilon}\right)\\\
=&\Pr\left(\underset{f_{\theta_{k}}\in C}{\rm
max}\left|P_{n}(f_{\theta_{k}})-P(f_{\theta_{k}})\right|+\alpha\left|Q_{m}(f_{\theta_{k}})-Q(f_{\theta_{k}})\right|+\beta\left|P_{n}(f^{2}_{\theta_{k}})-P(f^{2}_{\theta_{k}})\right|+\gamma\left|Q_{m}(f^{2}_{\theta_{k}})-Q(f^{2}_{\theta_{k}})\right|\geq\frac{\epsilon}{2}\right)\\\
\leq&\sum_{k=1}^{T}\Pr\left(\left|P_{n}(f_{\theta_{k}})-P(f_{\theta_{k}})\right|+\alpha\left|Q_{m}(f_{\theta_{k}})-Q(f_{\theta_{k}})\right|+\beta\left|P_{n}(f^{2}_{\theta_{k}})-P(f^{2}_{\theta_{k}})\right|+\gamma\left|Q_{m}(f^{2}_{\theta_{k}})-Q(f^{2}_{\theta_{k}})\right|\geq\frac{\epsilon}{2}\right)\\\
\leq&\sum_{k=1}^{T}\Pr\left(\left|P_{n}(f_{\theta_{k}})-P(f_{\theta_{k}})\right|\geq\frac{\epsilon}{8}\right)+\Pr\left(\alpha\left|Q_{m}(f_{\theta_{k}})-Q(f_{\theta_{k}})\right|\geq\frac{\epsilon}{8}\right)\\\
&\,\,\,\,\,\,\,\,\,\,+\Pr\left(\beta\left|P_{n}(f^{2}_{\theta_{k}})-P(f^{2}_{\theta_{k}})\right|\geq\frac{\epsilon}{8}\right)+\Pr\left(\gamma\left|Q_{m}(f^{2}_{\theta_{k}})-Q(f^{2}_{\theta_{k}})\right|\geq\frac{\epsilon}{8}\right).\end{split}$

With Hoeffding’s inequality,

  * •

$\Pr\left(\left|P_{n}(f_{\theta_{k}})-P(f_{\theta_{k}})\right|\geq\frac{\epsilon}{8}\right)\leq
2{\rm exp}\Big{(}-\frac{n\epsilon^{2}}{32M^{2}}\Big{)}$

  * •

$\Pr\left(\alpha\left|Q_{m}(f_{\theta_{k}})-Q(f_{\theta_{k}})\right|\geq\frac{\epsilon}{8}\right)\leq
2{\rm exp}\Big{(}-\frac{m\epsilon^{2}}{32M^{2}\alpha^{2}}\Big{)}$

  * •

$\Pr\left(\beta\left|P_{n}(f^{2}_{\theta_{k}})-P(f^{2}_{\theta_{k}})\right|\geq\frac{\epsilon}{8}\right)\leq
2{\rm exp}\Big{(}-\frac{n\epsilon^{2}}{32U^{2}\beta^{2}}\Big{)}$

  * •

$\Pr\left(\gamma\left|Q_{m}(f^{2}_{\theta_{k}})-Q(f^{2}_{\theta_{k}})\right|\geq\frac{\epsilon}{8}\right)\leq
2{\rm exp}\Big{(}-\frac{m\epsilon^{2}}{32U^{2}\gamma^{2}}\Big{)}$

To conclude,

$\begin{split}&\Pr\left(\sup_{f_{\theta}\in\mathcal{F}_{\Theta}}\left|\hat{J}^{m,n}_{{\rm
RPC},\theta}-\mathbb{E}\Big{[}\hat{J}_{{\rm
RPC},\theta}\Big{]}\right|\geq{\epsilon}\right)\\\
\leq&2\mathcal{N}(\Theta,\frac{\epsilon}{4\rho\big{(}1+\alpha+2(\beta+\gamma)U\big{)}})\Bigg{(}{\rm
exp}\Big{(}-\frac{n\epsilon^{2}}{32M^{2}}\Big{)}+{\rm
exp}\Big{(}-\frac{m\epsilon^{2}}{32M^{2}\alpha^{2}}\Big{)}+{\rm
exp}\Big{(}-\frac{n\epsilon^{2}}{32U^{2}\beta^{2}}\Big{)}+{\rm
exp}\Big{(}-\frac{m\epsilon^{2}}{32U^{2}\gamma^{2}}\Big{)}\Bigg{)}.\end{split}$

$\square$

##### Part II - Approximation: Neural Network Universal Approximation.

We leverage the universal function approximation lemma of neural network

######  Lemma 7 (Approximation (Hornik et al., 1989))

Let ${\epsilon}>0$. There exists $d\in\mathbb{N}$ and a family of neural
networks
$\mathcal{F}_{\Theta}:=\\{f_{\theta}:\theta\in\Theta\subseteq\mathbb{R}^{d}\\}$
where $\Theta$ is compact, such that
$\underset{f_{\theta}\in\mathcal{F}_{\Theta}}{\rm
inf}\left|\mathbb{E}\Big{[}\hat{J}_{{\rm RPC},\theta}\Big{]}-J_{\rm
RPC}\right|\leq{\epsilon}$.

##### Part III - Bringing everything together.

Now, we are ready to bring the estimation and approximation together to show
that there exists a neural network $\theta^{*}$ such that, with high
probability, $\hat{J}^{m,n}_{{\rm RPC},\theta}$ can approximate $J_{\rm RPC}$
with $n^{\prime}={\rm min}\,\\{n,m\\}$ at a rate of $O(1/\sqrt{n^{\prime}})$:

###### Proposition 3

With probability at least $1-\delta$, $\exists\theta^{*}\in\Theta$, $|J_{\rm
RPC}-\hat{J}^{m,n}_{\rm RPC,\theta}|=O(\sqrt{\frac{d+{\rm
log}\,(1/\delta)}{n^{\prime}}}),$ where $n^{\prime}={\rm min}\,\\{n,m\\}$.

Proof: The proof follows by combining Lemma 6 and 7.

First, Lemma 7 suggests, $\exists\theta^{*}\in\Theta$,

$\left|\mathbb{E}\Big{[}\hat{J}_{{\rm RPC},\theta^{*}}\Big{]}-J_{\rm
RPC}\right|\leq\frac{{\epsilon}}{2}.$

Next, we perform analysis on the estimation error, aiming to find $n,m$ and
the corresponding probability, such that

$\left|\hat{J}^{m,n}_{\rm RPC,\theta}-\mathbb{E}\Big{[}\hat{J}_{{\rm
RPC},\theta^{*}}\Big{]}\right|\leq\frac{{\epsilon}}{2}.$

Applying Lemma 6 with the covering number of the neural network:
($\mathcal{N}(\Theta,\epsilon)=O\Big{(}{\rm exp}\big{(}d\,{\rm
log}\,(1/\epsilon)\big{)}\Big{)}$ (Anthony & Bartlett, 2009)) and let
$n^{\prime}={\rm min}\\{n,m\\}$:

$\begin{split}&\Pr\left(\sup_{f_{\theta}\in\mathcal{F}_{\Theta}}\left|\hat{J}^{m,n}_{{\rm
RPC},\theta}-\mathbb{E}\Big{[}\hat{J}_{{\rm
RPC},\theta}\Big{]}\right|\geq\frac{{\epsilon}}{2}\right)\\\
\leq&2\mathcal{N}(\Theta,\frac{\epsilon}{8\rho\big{(}1+\alpha+2(\beta+\gamma)U\big{)}})\Bigg{(}{\rm
exp}\Big{(}-\frac{n\epsilon^{2}}{128M^{2}}\Big{)}+{\rm
exp}\Big{(}-\frac{m\epsilon^{2}}{128M^{2}\alpha^{2}}\Big{)}+{\rm
exp}\Big{(}-\frac{n\epsilon^{2}}{128U^{2}\beta^{2}}\Big{)}+{\rm
exp}\Big{(}-\frac{m\epsilon^{2}}{128U^{2}\gamma^{2}}\Big{)}\Bigg{)}\\\ \
=&O\Big{(}{\rm exp}\big{(}d\,{\rm
log}\,(1/\epsilon)-n^{\prime}\epsilon^{2}\big{)}\Big{)},\end{split}$

where the big-O notation absorbs all the constants that do not require in the
following derivation. Since we want to bound the probability with $1-\delta$,
we solve the $\epsilon$ such that

${\rm exp}\big{(}d\,{\rm
log}\,(1/\epsilon)-n^{\prime}\epsilon^{2}\big{)}\leq\delta.$

With ${\rm log}\,(x)\leq x-1$,

$n^{\prime}\epsilon^{2}+d(\epsilon-1)\geq n^{\prime}\epsilon^{2}+d{\rm
log}\,\epsilon\geq{\rm log}\,(1/\delta),$

where this inequality holds when

$\epsilon=O\bigg{(}\sqrt{\frac{d+{\rm log}\,(1/\delta)}{n^{\prime}}}\bigg{)}.$

$\square$

###  A.4 Proof of Proposition 2 in the Main Text - From an Asymptotic
Viewpoint

Here, we provide the variance analysis on $\hat{J}^{m,n}_{\rm RPC}$ via an
asymptotic viewpoint. First, assuming the network is correctly specified, and
hence there exists a network parameter $\theta^{*}$ satisfying
$f^{*}(x,y)=f_{\theta^{*}}(x,y)=r_{\alpha,\beta,\gamma}(x,y)$. Then we recall
that $\hat{J}^{m,n}_{\rm RPC}$ is a consistent estimator of ${J}^{\rm RPC}$
(see Proposition 3), and under regular conditions, the estimated network
parameter $\hat{\theta}$ in $\hat{J}^{m,n}_{\rm RPC}$ satisfying the
asymptotic normality in the large sample limit (see Theorem 5.23 in (Van der
Vaart, 2000)). We recall the definition of $\hat{J}^{m,n}_{{\rm RPC},\theta}$
in equation 3 and let $n^{\prime}={\rm min}\\{n,m\\}$, the asymptotic
expansion of $\hat{J}^{m,n}_{\rm RPC}$ has

$\begin{split}\hat{J}^{m,n}_{{\rm RPC},\theta^{*}}&=\hat{J}^{m,n}_{{\rm
RPC},\hat{\theta}}+\dot{\hat{J}}^{m,n}_{{\rm
RPC},\hat{\theta}}(\theta^{*}-\hat{\theta})+o(\|\theta^{*}-\hat{\theta}\|)\\\
&=\hat{J}^{m,n}_{{\rm RPC},\hat{\theta}}+\dot{\hat{J}}^{m,n}_{{\rm
RPC},\hat{\theta}}(\theta^{*}-\hat{\theta})+o_{p}(\frac{1}{\sqrt{n^{\prime}}})\\\
&=\hat{J}^{m,n}_{{\rm
RPC},\hat{\theta}}+o_{p}(\frac{1}{\sqrt{n^{\prime}}}),\end{split}$ (5)

where $\dot{\hat{J}}^{m,n}_{{\rm RPC},\hat{\theta}}=0$ since $\hat{\theta}$ is
the estimation from $\hat{J}^{m,n}_{{\rm
RPC}}=\underset{f_{\theta}\in\mathcal{F}_{\Theta}}{\rm
sup}\,\hat{J}^{m,n}_{{\rm RPC},\theta}$.

Next, we recall the definition in equation 4:

$\mathbb{E}[\hat{J}_{\rm
RPC,\hat{\theta}}]=\mathbb{E}_{P_{XY}}[f_{\hat{\theta}}(x,y)]-\alpha\mathbb{E}_{P_{X}P_{Y}}[f_{\hat{\theta}}(x,y)]-\frac{\beta}{2}\mathbb{E}_{P_{XY}}[f_{\hat{\theta}}^{2}(x,y)]-\frac{\gamma}{2}\mathbb{E}_{P_{X}P_{Y}}[f_{\hat{\theta}}^{2}(x,y)].$

Likewise, the asymptotic expansion of $\mathbb{E}[\hat{J}_{\rm RPC,\theta}]$
has

$\begin{split}\mathbb{E}[\hat{J}_{\rm
RPC,\hat{\theta}}]&=\mathbb{E}[\hat{J}_{\rm
RPC,\theta^{*}}]+\mathbb{E}[\dot{\hat{J}}_{\rm
RPC,\theta^{*}}](\hat{\theta}-\theta^{*})+o(\|\hat{\theta}-\theta^{*}\|)\\\
&=\mathbb{E}[\hat{J}_{\rm RPC,\theta^{*}}]+\mathbb{E}[\dot{\hat{J}}_{\rm
RPC,\theta^{*}}](\hat{\theta}-\theta^{*})+o_{p}(\frac{1}{\sqrt{n^{\prime}}})\\\
&=\mathbb{E}[\hat{J}_{\rm
RPC,\theta^{*}}]+o_{p}(\frac{1}{\sqrt{n^{\prime}}}),\end{split}$ (6)

where $\mathbb{E}[\dot{\hat{J}}_{\rm RPC,\theta^{*}}]=0$ since
$\mathbb{E}[\hat{J}_{\rm RPC,\theta^{*}}]=J_{\rm RPC}$ and $\theta^{*}$
satisfying $f^{*}(x,y)=f_{\theta^{*}}(x,y)$.

Combining equations 5 and 6:

$\begin{split}\hat{J}^{m,n}_{{\rm RPC},\hat{\theta}}-\mathbb{E}[\hat{J}_{\rm
RPC,\hat{\theta}}]=&\hat{J}^{m,n}_{{\rm RPC},\theta^{*}}-J_{\rm
RPC}+o_{p}(\frac{1}{\sqrt{n^{\prime}}})\\\
=&\frac{1}{n}\sum_{i=1}^{n}f_{\theta}^{*}(x_{i},y_{i})-\alpha\frac{1}{m}\sum_{j=1}^{m}f_{\theta}^{*}(x^{\prime}_{j},y^{\prime}_{j})-\frac{\beta}{2}\frac{1}{n}\sum_{i=1}^{n}f_{\theta^{*}}^{2}(x_{i},y_{i})-\frac{\gamma}{2}\frac{1}{m}\sum_{j=1}^{m}f_{\theta^{*}}^{2}(x^{\prime}_{j},y^{\prime}_{j})\\\
&-\mathbb{E}_{P_{XY}}[f^{*}(x,y)]+\alpha\mathbb{E}_{P_{X}P_{Y}}[f^{*}(x,y)]+\frac{\beta}{2}\mathbb{E}_{P_{XY}}\left[{f^{*}}^{2}(x,y)\right]+\frac{\gamma}{2}\mathbb{E}_{P_{X}P_{Y}}\left[{f^{*}}^{2}(x,y)\right]+o_{p}(\frac{1}{\sqrt{n^{\prime}}})\\\
=&\frac{1}{n}\sum_{i=1}^{n}r_{\alpha,\beta,\gamma}(x_{i},y_{i})-\alpha\frac{1}{m}\sum_{j=1}^{m}r_{\alpha,\beta,\gamma}(x^{\prime}_{j},y^{\prime}_{j})-\frac{\beta}{2}\frac{1}{n}\sum_{i=1}^{n}r_{\alpha,\beta,\gamma}^{2}(x_{i},y_{i})-\frac{\gamma}{2}\frac{1}{m}\sum_{j=1}^{m}r_{\alpha,\beta,\gamma}^{2}(x^{\prime}_{j},y^{\prime}_{j})\\\
&-\mathbb{E}_{P_{XY}}[r_{\alpha,\beta,\gamma}(x,y)]+\alpha\mathbb{E}_{P_{X}P_{Y}}[r_{\alpha,\beta,\gamma}(x,y)]+\frac{\beta}{2}\mathbb{E}_{P_{XY}}\left[r_{\alpha,\beta,\gamma}^{2}(x,y)\right]+\frac{\gamma}{2}\mathbb{E}_{P_{X}P_{Y}}\left[r_{\alpha,\beta,\gamma}^{2}(x,y)\right]\\\
&+o_{p}(\frac{1}{\sqrt{n^{\prime}}})\\\
=&\frac{1}{\sqrt{n}}\cdot\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\Bigg{(}r_{\alpha,\beta,\gamma}(x_{i},y_{i})-\frac{\beta}{2}r_{\alpha,\beta,\gamma}^{2}(x_{i},y_{i})-\mathbb{E}_{P_{XY}}\bigg{[}r_{\alpha,\beta,\gamma}(x,y)-\frac{\beta}{2}r_{\alpha,\beta,\gamma}^{2}(x,y)\bigg{]}\Bigg{)}\\\
&-\frac{1}{\sqrt{m}}\cdot\frac{1}{\sqrt{m}}\sum_{j=1}^{m}\Bigg{(}\alpha
r_{\alpha,\beta,\gamma}(x^{\prime}_{j},y^{\prime}_{j})+\frac{\gamma}{2}r^{2}_{\alpha,\beta,\gamma}(x^{\prime}_{j},y^{\prime}_{j})-\mathbb{E}_{P_{X}P_{Y}}\bigg{[}\alpha
r_{\alpha,\beta,\gamma}(x,y)+\frac{\gamma}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)\bigg{]}\Bigg{)}\\\
&+o_{p}(\frac{1}{\sqrt{n^{\prime}}}).\end{split}$

Therefore, the asymptotic Variance of $\hat{J}^{m,n}_{{\rm RPC}}$ is

$\begin{split}\mathrm{Var}[\hat{J}^{m,n}_{{\rm
RPC}}]=\frac{1}{n}\mathrm{Var}_{P_{XY}}[r_{\alpha,\beta,\gamma}(x,y)-\frac{\beta}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)]+\frac{1}{m}\mathrm{Var}_{P_{X}P_{Y}}[\alpha
r_{\alpha,\beta,\gamma}(x,y)+\frac{\gamma}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)]+o(\frac{1}{n^{\prime}}).\end{split}$

First, we look at
$\mathrm{Var}_{P_{XY}}[r_{\alpha,\beta,\gamma}(x,y)-\frac{\beta}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)]$.
Since $\beta>0$ and $-\frac{\alpha}{\gamma}\leq
r_{\alpha,\beta,\gamma}\leq\frac{1}{\beta}$, simple calculation gives us
$-\frac{2\alpha\gamma+\beta\alpha^{2}}{2\gamma^{2}}\leq
r_{\alpha,\beta,\gamma}(x,y)-\frac{\beta}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)\leq\frac{1}{2\beta}$.
Hence,

$\mathrm{Var}_{P_{XY}}[r_{\alpha,\beta,\gamma}(x,y)-\frac{\beta}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)]\leq{\rm
max}\bigg{\\{}\Big{(}\frac{2\alpha\gamma+\beta\alpha^{2}}{2\gamma^{2}}\Big{)}^{2},\Big{(}\frac{1}{2\beta}\Big{)}^{2}\bigg{\\}}.$

Next, we look at $\mathrm{Var}_{P_{X}P_{Y}}[\alpha
r_{\alpha,\beta,\gamma}(x,y)+\frac{\gamma}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)]$.
Since $\alpha\geq 0,\gamma>0$ and $-\frac{\alpha}{\gamma}\leq
r_{\alpha,\beta,\gamma}\leq\frac{1}{\beta}$, simple calculation gives us
$-\frac{\alpha^{2}}{2\gamma}\leq\alpha
r_{\alpha,\beta,\gamma}(x,y)+\frac{\gamma}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)\leq\frac{2\alpha\beta+\gamma}{2\beta^{2}}$.
Hence,

$\mathrm{Var}_{P_{X}P_{Y}}[\alpha
r_{\alpha,\beta,\gamma}(x,y)+\frac{\gamma}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)]\leq{\rm
max}\bigg{\\{}\Big{(}\frac{\alpha^{2}}{2\gamma}\Big{)}^{2},\Big{(}\frac{2\alpha\beta+\gamma}{2\beta^{2}}\Big{)}^{2}\bigg{\\}}.$

Combining everything together, we restate the Proposition 2 in the main text:

######  Proposition 4 (Asymptotic Variance of $\hat{J}^{m,n}_{\rm RPC}$)

$\begin{split}\mathrm{Var}[\hat{J}^{m,n}_{{\rm
RPC}}]&=\frac{1}{n}\mathrm{Var}_{P_{XY}}[r_{\alpha,\beta,\gamma}(x,y)-\frac{\beta}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)]+\frac{1}{m}\mathrm{Var}_{P_{X}P_{Y}}[\alpha
r_{\alpha,\beta,\gamma}(x,y)+\frac{\gamma}{2}r^{2}_{\alpha,\beta,\gamma}(x,y)]+o(\frac{1}{n^{\prime}})\\\
&\leq\frac{1}{n}{\rm
max}\bigg{\\{}\Big{(}\frac{2\alpha\gamma+\beta\alpha^{2}}{2\gamma^{2}}\Big{)}^{2},\Big{(}\frac{1}{2\beta}\Big{)}^{2}\bigg{\\}}+\frac{1}{m}{\rm
max}\bigg{\\{}\Big{(}\frac{\alpha^{2}}{2\gamma}\Big{)}^{2},\Big{(}\frac{2\alpha\beta+\gamma}{2\beta^{2}}\Big{)}^{2}\bigg{\\}}+o(\frac{1}{n^{\prime}})\end{split}$

###  A.5 Proof of Proposition 2 in the Main Text - From Boundness of
$f_{\theta}$

As discussed in Assumption 1, for the estimation $\hat{J}^{m,n}_{\rm RPC}$, we
can bound the function $f_{\theta}$ in $\mathcal{F}_{\Theta}$ within
$[-\frac{\alpha}{\gamma},\frac{1}{\beta}]$ without losing precision. Then, re-
arranging $\hat{J}^{m,n}_{\rm RPC}$:

$\begin{split}&\sup_{{f}_{\theta}\in\mathcal{F}_{\Theta}}\frac{1}{n}\sum_{i=1}^{n}f_{\theta}(x_{i},y_{i})-\frac{1}{m}\sum_{j=1}^{m}\alpha
f_{\theta}(x^{\prime}_{j},y^{\prime}_{j})-\frac{1}{n}\sum_{i=1}^{n}\frac{\beta}{2}f_{\theta}^{2}(x_{i},y_{i})-\frac{1}{m}\sum_{j=1}^{m}\frac{\gamma}{2}f_{\theta}^{2}(x^{\prime}_{j},y^{\prime}_{j})\\\
&\sup_{{f}_{\theta}\in\mathcal{F}_{\Theta}}\frac{1}{n}\sum_{i=1}^{n}\Big{(}f_{\theta}(x_{i},y_{i})-\frac{\beta}{2}f_{\theta}^{2}(x_{i},y_{i})\Big{)}+\frac{1}{m}\sum_{j=m}^{n}\Big{(}\alpha
f_{\theta}(x^{\prime}_{j},y^{\prime}_{j})+\frac{\gamma}{2}f_{\theta}^{2}(x^{\prime}_{j},y^{\prime}_{j})\Big{)}\end{split}$

Then, since $-\frac{\alpha}{\gamma}\leq
f_{\theta}(\cdot,\cdot)\leq\frac{1}{\beta}$, basic calculations give us

$-\frac{2\alpha\gamma+\beta\alpha^{2}}{2\gamma^{2}}\leq
f_{\theta}(x_{i},y_{i})-\frac{\beta}{2}f_{\theta}^{2}(x_{i},y_{i})\leq\frac{1}{2\beta}\,\,{\rm
and}\,\,-\frac{\alpha^{2}}{2\gamma}\leq\alpha
f_{\theta}(x^{\prime}_{j},y^{\prime}_{j})+\frac{\gamma}{2}f_{\theta}^{2}(x^{\prime}_{j},y^{\prime}_{j})\leq\frac{2\alpha\beta+\gamma}{2\beta^{2}}.$

The resulting variances have

$\mathrm{Var}[f_{\theta}(x_{i},y_{i})-\frac{\beta}{2}f_{\theta}^{2}(x_{i},y_{i})]\leq{\rm
max}\,\bigg{\\{}\Big{(}\frac{2\alpha\gamma+\beta\alpha^{2}}{2\gamma^{2}}\Big{)}^{2},\Big{(}\frac{1}{2\beta}\Big{)}^{2}\bigg{\\}}$

and

$\mathrm{Var}[\alpha
f_{\theta}(x^{\prime}_{j},y^{\prime}_{j})+\frac{\gamma}{2}f_{\theta}^{2}(x^{\prime}_{j},y^{\prime}_{j})]\leq{\rm
max}\,\bigg{\\{}\Big{(}\frac{\alpha^{2}}{2\gamma}\Big{)}^{2},\Big{(}\frac{2\alpha\beta+\gamma}{2\beta^{2}}\Big{)}^{2}\bigg{\\}}.$

Taking the mean of $m,n$ independent random variables gives the result:

######  Proposition 5 (Variance of $\hat{J}^{m,n}_{\rm RPC}$)

$\mathrm{Var}[\hat{J}^{m,n}_{{\rm RPC}}]\leq\frac{1}{n}{\rm
max}\bigg{\\{}\Big{(}\frac{2\alpha\gamma+\beta\alpha^{2}}{2\gamma^{2}}\Big{)}^{2},\Big{(}\frac{1}{2\beta}\Big{)}^{2}\bigg{\\}}+\frac{1}{m}{\rm
max}\bigg{\\{}\Big{(}\frac{\alpha^{2}}{2\gamma}\Big{)}^{2},\Big{(}\frac{2\alpha\beta+\gamma}{2\beta^{2}}\Big{)}^{2}\bigg{\\}}.$

###  A.6 Implementation of Experiments

For visual representation learning, we follow the implementation in
https://github.com/google-research/simclr. For speech representation learning,
we follow the implementation in https://github.com/facebookresearch/CPC_audio.
For MI estimation, we follow the implementation in
https://github.com/yaohungt/Pointwise_Dependency_Neural_Estimation/tree/master/MI_Est_and_CrossModal..

###  A.7 Relative Predictive Coding on Vision

The whole pipeline of pretraining contains the following steps: First, a
stochastic data augmentation will transform one image sample ${\bm{x}}_{k}$ to
two different but correlated augmented views, ${\bm{x}}_{2k-1}^{\prime}$ and
${\bm{x}}_{2k}^{\prime}$. Then a base encoder $f(\cdot)$ implemented using
ResNet (He et al., 2016) will extract representations from augmented views,
creating representations ${\bm{h}}_{2k-1}$ and ${\bm{h}}_{2k}$. Later a small
neural network $g(\cdot)$ called projection head will map ${\bm{h}}_{2k-1}$
and ${\bm{h}}_{2k}$ to ${\bm{z}}_{2k-1}$ and ${\bm{z}}_{2k}$ in a different
latent space. For each minibatch of $N$ samples, there will be $2N$ views
generated. For each image ${\bm{x}}_{k}$ there will be one positive pair
${\bm{x}}_{2k-1}^{\prime}$ and ${\bm{x}}_{2k}^{\prime}$ and $2(N-1)$ negative
samples. The RPC loss between a pair of positive views,
${\bm{x}}_{i}^{\prime}$ and ${\bm{x}}_{j}^{\prime}$ (augmented from the same
image) , can be calculated by the substitution
$f_{\theta}({\bm{x}}_{i}^{\prime},{\bm{x}}_{j}^{\prime})=({\bm{z}}_{i}\cdot{\bm{z}}_{j})/\tau=s_{i,j}$
($\tau$ is a hyperparameter) to the definition of RPC:

$\ell_{i,j}^{\mathrm{RPC}}=-(s_{i,j}-\frac{\alpha}{2(N-1)}\sum_{k=1}^{2N}\bm{1}_{\mathrm{[k\neq
i]}}s_{i,k}-\frac{\beta}{2}s_{i,j}^{2}-\frac{\gamma}{2\cdot
2(N-1)}\sum_{k=1}^{2N}\bm{1}_{\mathrm{[k\neq i]}}s_{i,k}^{2})$ (7)

For losses other than RPC, a hidden normalization of $s_{i,j}$ is often
required by replacing ${\bm{z}}_{i}\cdot{\bm{z}}_{j}$ with
$({\bm{z}}_{i}\cdot{\bm{z}}_{j})/|{\bm{z}}_{i}||{\bm{z}}_{j}|$. CPC and WPC
adopt this, while other objectives needs it to help stabilize training
variance. RPC does not need this normalization.

###  A.8 CIFAR-10/-100 and ImageNet Experiments Details

##### ImageNet

Following the settings in (Chen et al., 2020b; c), we train the model on Cloud
TPU with $128$ cores, with a batch size of $4,096$ and global batch
normalization 333For WPC (Ozair et al., 2019), the global batch normalization
during pretraining is disabled since we enforce 1-Lipschitz by gradient
penalty (Gulrajani et al., 2017). (Ioffe & Szegedy, 2015). Here we refer to
the term batch size as the number of images (or utterances in the speech
experiments) we use per GPU, while the term minibatch size refers to the
number of negative samples used to calculate the objective, such as CPC or our
proposed RPC. The largest model we train is a 152-layer ResNet with selective
kernels (SK) (Li et al., 2019) and $2\times$ wider channels. We use the LARS
optimizer (You et al., 2017) with momentum $0.9$. The learning rate linearly
increases for the first $20$ epochs, reaching a maximum of $6.4$, then decayed
with cosine decay schedule. The weight decay is $10^{-4}$. A MLP projection
head $g(\cdot)$ with three layers is used on top of the ResNet encoder. Unlike
Chen et al. (2020c), we do not use a memory buffer, and train the model for
only $100$ epochs rather than $800$ epochs due to computational constraints.
These two options slightly reduce CPC’s performance benchmark for about $2\%$
with the exact same setting. The unsupervised pre-training is followed by a
supervised fine-tuning. Following SimCLRv2 (Chen et al., 2020b; c), we fine-
tune the 3-layer $g(\cdot)$ for the downstream tasks. We use learning rates
$0.16$ and $0.064$ for standard 50-layer ResNet and larger 152-layer ResNet
respectively, and weight decay and learning rate warmup are removed. Different
from Chen et al. (2020c), we use a batch size of $4,096$, and we do not use
global batch normalization for fine-tuning. For $J_{\rm RPC}$ we disable
hidden normalization and use a temperature $\tau=32$. For all other
objectives, we use hidden normalization and $\tau=0.1$ following previous work
(Chen et al., 2020c). For relative parameters, we use
$\alpha=0.3,\beta=0.001,\gamma=0.1$ and $\alpha=0.3,\beta=0.001,\gamma=0.005$
for ResNet-50 and ResNet-152 respectively.

##### CIFAR-10/-100

Following the settings in (Chen et al., 2020b), we train the model on a single
GPU, with a batch size of $512$ and global batch normalization (Ioffe &
Szegedy, 2015). We use ResNet (He et al., 2016) of depth $18$ and depth $50$,
and does not use Selective Kernel (Li et al., 2019) or a multiplied width
size. We use the LARS optimizer (You et al., 2017) with momentum $0.9$. The
learning rate linearly increases for the first $20$ epochs, reaching a maximum
of $6.4$, then decayed with cosine decay schedule. The weight decay is
$10^{-4}$. A MLP projection head $g(\cdot)$ with three layers is used on top
of the ResNet encoder. Unlike Chen et al. (2020c), we do not use a memory
buffer. We train the model for $1000$ epochs. The unsupervised pre-training is
followed by a supervised fine-tuning. Following SimCLRv2 (Chen et al., 2020b;
c), we fine-tune the 3-layer $g(\cdot)$ for the downstream tasks. We use
learning rates $0.16$ for standard 50-layer ResNet , and weight decay and
learning rate warmup are removed. For $J_{\rm RPC}$ we disable hidden
normalization and use a temperature $\tau=128$. For all other objectives, we
use hidden normalization and $\tau=0.5$ following previous work (Chen et al.,
2020c). For relative parameters, we use $\alpha=1.0,\beta=0.005,\text{ and
}\gamma=1.0$.

##### STL-10

We also perform the pre-training and fine-tuning on STL-10 (Coates et al.,
2011) using the model proposed in Chuang et al. (2020). Chuang et al. (2020)
proposed to indirectly approximate the distribution of negative samples so
that the objective is debiased. However, their implementation of contrastive
learning is consistent with Chen et al. (2020b). We use a ResNet with depth
$50$ as an encoder for pre-training, with Adam optimizer, learning rate
$0.001$ and weight decay $10^{-6}$. The temperature $\tau$ is set to $0.5$ for
all objectives other than $J_{\rm RPC}$, which disables hidden normalization
and use $\tau=128$. The downstream task performance increases from $83.4\%$ of
$J_{\rm CPC}$ to $84.1\%$ of $J_{\rm RPC}$.

Confidence Interval of $J_{\rm RPC}$ and $J_{\rm CPC}$
---
Objective |  CIFAR 10 |  CIFAR 100 |  ImageNet
$J_{\rm CPC}$ |  $(91.09\%,91.13\%)$ |  $(77.11\%,77.36\%)$ |  $(73.39\%,73.48\%)$
$J_{\rm RPC}$ |  $(91.16\%,91.47\%)$ |  $(77.41\%,77.98\%)$ |  $(73.92\%,74.43\%)$
Table 4: Confidence Intervals of performances of $J_{\rm RPC}$ and $J_{\rm
CPC}$ on CIFAR-10/-100 and ImageNet.

##### Confidence Interval

We also provide the confidence interval of $J_{\rm RPC}$ and $J_{\rm CPC}$ on
CIFAR-10, CIFAR-100 and ImageNet, using ResNet-18, ResNet-18 and ResNet-50
respectively (95% confidence level is chosen) in Table 4. Both CPC and RPC use
the same experimental settings throughout this paper. Here we use the relative
parameters ($\alpha=1.0,\beta=0.005,\gamma=1.0$) in $J_{\rm RPC}$ which gives
the best performance on CIFAR-10. The confidence intervals of CPC do not
overlap with the confidence intervals of RPC, which means the difference of
the downstream task performance between RPC and CPC is statistically
significant.

###  A.9 Relative Predictive Coding on Speech

For speech representation learning, we adopt the general architecture from
Oord et al. (2018). Given an input signal ${\bm{x}}_{1:T}$ with $T$ time
steps, we first pass it through an encoder $\phi_{\theta}$ parametrized by
$\theta$ to produce a sequence of hidden representations
$\\{{\bm{h}}_{1:T}\\}$ where ${\bm{h}}_{t}=\phi_{\theta}({\bm{x}}_{t})$. After
that, we obtain the contextual representation ${\bm{c}}_{t}$ at time step $t$
with a sequential model $\psi_{\rho}$ parametrized by $\rho$:
$\mathbf{c}_{t}=\psi_{\rho}({\bm{h}}_{1},\ldots,{\bm{h}}_{t})$, where
${\bm{c}}_{t}$ contains context information before time step $t$. For
unsupervised pre-training, we use a multi-layer convolutional network as the
encoder $\phi_{\theta}$, and an LSTM with hidden dimension $256$ as the
sequential model $\psi_{\rho}$. Here, the contrastiveness is between the
positive pair $({\bm{h}}_{t+k},{\bm{c}}_{t})$ where $k$ is the number of time
steps ahead, and the negative pairs $({\bm{h}}_{i},{\bm{c}}_{t})$, where
${\bm{h}}_{i}$ is randomly sampled from $\mathcal{N}$, a batch of hidden
representation of signals assumed to be unrelated to ${\bm{c}}_{t}$. The
scoring function $f$ based on Equation 2 at step $t$ and look-ahead $k$ will
be
$f_{k}=f_{k}({\bm{h}},{\bm{c}}_{t})=\exp(({\bm{h}})^{\top}{\bm{W}}_{k}{\bm{c}}_{t})$,
where ${\bm{W}}_{k}$ is a learnable linear transformation defined separately
for each $k\in\\{1,...,K\\}$ and $K$ is predetermined as $12$ time steps. The
loss in Equation 2 will then be formulated as:

$\ell^{\mathrm{RPC}}_{t,k}=-(f_{k}({\bm{h}}_{t+k},{\bm{c}}_{t})-\frac{\alpha}{|\mathcal{N}|}\sum_{{\bm{h}}_{i}\in\mathcal{N}}f_{k}({\bm{h}}_{i},{\bm{c}}_{t})-\frac{\beta}{2}f_{k}^{2}({\bm{h}}_{t+k},{\bm{c}}_{t})-\frac{\gamma}{2|\mathcal{N}|}\sum_{{\bm{h}}_{i}\in\mathcal{N}}f_{k}^{2}({\bm{h}}_{i},{\bm{c}}_{t}))$
(8)

We use the following relative parameters: $\alpha=1,\beta=0.25,\text{ and
}\gamma=1$, and we use the temperature $\tau=16$ for $J_{\rm RPC}$. For
$J_{\rm CPC}$ we follow the original implementation which sets $\tau=1$. We
fix all other experimental setups, including architecture, learning rate, and
optimizer. As shown in Table 3, $J_{\rm RPC}$ has better downstream task
performance, and is closer to the performance from a fully supervised model.

###  A.10 Empirical Observations on Variance and Minibatch Size

##### Variance Experiment Setup

We perform the variance comparison of $J_{\rm DV}$, $J_{\rm NWJ}$ and the
proposed $J_{\rm RPC}$. The empirical experiments are performed using SimCLRv2
(Chen et al., 2020c) on CIFAR-10 dataset. We use a ResNet of depth $18$, with
batch size of $512$. We train each objective with $30$K training steps and
record their value. In Figure 1, we use a temperature $\tau=128$ for all
objectives. Unlike other experiments, where hidden normalization is applied to
other objectives, we remove hidden normarlization for all objectives due to
the reality that objectives after normalization does not reflect their
original values. From Figure 1, $J_{\rm RPC}$ enjoys lower variance and more
stable training compared to $J_{\rm DV}$ and $J_{\rm NWJ}$.

##### Minibatch Size Experimental Setup

We perform experiments on the effect of batch size on downstream performances
for different objective. The experiments are performed using SimCLRv2 (Chen et
al., 2020c) on CIFAR-10 dataset, as well as the model from Rivière et al.
(2020) on LibriSpeech-100h dataset (Panayotov et al., 2015). For vision task,
we use the default temperature $\tau=0.5$ from Chen et al. (2020c) and hidden
normalization mentioned in Section 3 for $J_{\rm CPC}$. For $J_{\rm RPC}$ in
vision and speech tasks we use a temperature of $\tau=128$ and $\tau=16$
respectively, both without hidden normalization.

###  A.11 Mutual Information Estimation

Our method is compared with baseline methods CPC (Oord et al., 2018), NWJ
(Nguyen et al., 2010), JSD (Nowozin et al., 2016), and SMILE (Song & Ermon,
2019). All the approaches consider the same design of $f(x,y)$, which is a
3-layer neural network taking concatenated $(x,y)$ as the input. We also fix
the learning rate, the optimizer, and the minibatch size across all the
estimators for a fair comparison.

We present results of mutual information by Relative Predictive Coding using
different sets of relative parameters in Figure 4. In the first row, we set
$\beta=10^{-3}$, $\gamma=1$, and experiment with different $\alpha$ values. In
the second row, we set $\alpha=1$, $\gamma=1$ and in the last row we set
$\alpha=1$, $\beta=10^{-3}$. From the figure, a small $\beta$ around $10^{-3}$
and a large $\gamma$ around $1.0$ is crucial for an estimation that is
relatively low bias and low variance. This conclusion is consistent with
Section 3 in the main text.

Figure 4: Mutual information estimation by RPC performed on 20-d correlated
Gaussian distribution, with different sets of relative parameters.

We also performed comparison between $J_{\rm RPC}$ and Difference of Entropies
(DoE) (McAllester & Stratos, 2020). We performed two sets of experiments: in
the first set of experiments we compare $J_{\rm RPC}$ and DoE when MI is large
($>100$ nats), while in the second set of experiments we compare $J_{\rm RPC}$
and DoE using the setup in this section (MI $<12$ nats and MI increases by 2
per 4k training steps). On the one hand, when MI is large ($>100$ nats), we
acknowledge that DoE is performing well on MI estimation, compared to $J_{\rm
RPC}$ which only estimates the MI around $20$. This analysis is based on the
code from https://github.com/karlstratos/doe. On the other hand, when the true
MI is small, the DoE method is more unstable than $J_{\rm RPC}$, as shown in
Figure 5. Figure 5 illustrates the results of the DoE method when the
distribution is isotropic Gaussian (correctly specified) or Logistic (mis-
specified). Figure 3 only shows the results using Gaussian.

Figure 5: Mutual information estimation by DoE performed on 20-d correlated
Gaussian distribution. The figure on the left shows parametrization under
Gaussian (correctly specified), and the figure on the right shows
parametrization under Logistic (mis-specified).