$\displaystyle\leq\frac{\omega+1}{N^{2}}\sum_{i=1}^{N}\left\|g_{k,*}^{i}\right\|^{2}+\frac{1}{N^{2}}\sum_{i\neq
j}\left\langle g_{k,*}^{i},g_{k,*}^{j}\right\rangle\,.$

Next, we first have from Model 1 and Equation 2 that for any $i$ in $[N]$,
$g_{k,*}^{i}=-\varepsilon_{k}^{i}x_{k}^{i}$, secondly because
$\left((\varepsilon_{k}^{i})_{k\in[K],i\in[N]}\right)$ are independent from
$\left((x_{k}^{i})_{k\in[K],i\in[N]}\right)$ (Model 1), we have that
$\mathbb{E}[\|\varepsilon_{k}^{i}x_{k}^{i}\|^{2}]\leq\sigma^{2}R_{i}^{2}$,
hence it results to
$\mathbb{E}\left[\|\xi_{k}^{\mathrm{add}}\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]=\mathbb{E}[\|\xi_{k}^{\mathrm{add}}\|^{2}]=\frac{\omega+1}{N^{2}}\sum_{i=1}^{N}\sigma^{2}R_{i}^{2}\,.$

######  Property S9 (Validity of Item 2.1).

Consider Algorithm 3 in the context of Model 1 with Lemma 1, for any iteration
$k$ in $\mathbb{N}^{*}$, the second moment of the multiplicative noise
$\xi_{k}^{\mathrm{mult}}(w)$ can be bounded for any $w$ in $\mathbb{R}^{d}$ by
$2(\omega+1)\max_{i\in[N]}(R_{i}^{2})\left\|\overline{H}^{1/2}(w-w_{*})\right\|^{2}/N+4(\omega+1)\overline{R}^{2}\sigma^{2}/N$
i.e. Item 2.1 is verified.

Proof  Let $k$ in $\mathbb{N}^{*}$, we note $\eta=w-w_{*}$. Because we
consider Algorithm 3, with Definitions 1 and 2, we write
$\xi_{k}^{\mathrm{mult}}(\eta)=\frac{1}{N}\sum_{i=1}^{N}\xi_{k}^{i,\mathrm{mult}}(\eta)$,
where
$\xi_{k}^{i,\mathrm{mult}}(\eta)=H_{i}\eta-\mathcal{C}(\textsl{g}_{k}^{i}(w))+\mathcal{C}(g_{k,*}^{i})$
is the multiplicative noise on client $i$ in $[N]$, hence developing the
squared norm gives:

$\displaystyle\left\|\xi^{\mathrm{mult}}_{k}\left(\eta\right)\right\|^{2}=\left\|\frac{1}{N}\sum_{i=1}^{N}\xi_{k}^{i,\mathrm{mult}}(\eta)\right\|^{2}=\frac{1}{N^{2}}\sum_{i=1}^{N}\left\|\xi_{k}^{i,\mathrm{mult}}(\eta)\right\|^{2}+\frac{1}{N^{2}}\sum_{i\neq
j}\left\langle\xi_{k}^{i,\mathrm{mult}}(\eta),\xi_{k}^{j,\mathrm{mult}}(\eta)\right\rangle\,.$

Taking expectation w.r.t. the $\sigma$-algebra $\mathcal{F}_{k-1}$, using that
the $N$ compressions are independent (Algorithm 3) and that for any $i$ in
$[N]$, $\mathbb{E}[\xi_{k}^{i,\mathrm{mult}}(\eta)\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]=0$ (Lemma 1) results to have:

$\displaystyle\mathbb{E}[\|\xi^{\mathrm{mult}}_{k}\left(\eta\right)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]=\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbb{E}[\|\xi_{k}^{i,\mathrm{mult}}(\eta)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]\,.$

Next, we use the result of Property S3 for each client $i$ in $[N]$ and we
obtain:

$\displaystyle\mathbb{E}\left[\|\xi^{\mathrm{mult}}_{k}\left(\eta\right)\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle\leq\frac{1}{N^{2}}\sum_{i=1}^{N}\left(2(\omega+1)R_{i}^{2}\|H_{i}^{1/2}(w-w_{*})\|^{2}+4(\omega+1)R_{i}^{2}\sigma^{2}\right)$
$\displaystyle\leq\frac{2(\omega+1)\max_{i\in[N]}(R_{i}^{2})}{N}\|\overline{H}^{1/2}(w-w_{*})\|^{2}+\frac{4(\omega+1)\overline{R}^{2}\sigma^{2}}{N}\,,$

which allows concluding.

######  Property S10 (Validity of Item 2.2).

Consider Algorithm 3 in the context of Model 1 with Lemma 1, for any iteration
$k$ in $\mathbb{N}^{*}$, the second moment of the multiplicative noise
$\xi_{k}^{\mathrm{mult}}(w)$ can be bounded for any $w$ in $\mathbb{R}^{d}$ by
$(\Omega\sigma\max_{i\in[N]}(R_{i}^{2})\|\overline{H}^{1/2}(w-w_{*})\|+(\omega+1)\max_{i\in[N]}(R_{i}^{2})\|\overline{H}^{1/2}(w-w_{*})\|^{2})/N$
i.e. Item 2.2 is verified.

Proof  Let $k$ in $\mathbb{N}^{*}$, we note $\eta=w-w_{*}$. From Property S9,
taking expectation w.r.t. the $\sigma$-algebra $\mathcal{F}_{k-1}$,
decomposing the multiplicative noise results to have:

$\displaystyle\mathbb{E}[\|\xi^{\mathrm{mult}}_{k}\left(\eta\right)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]=\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbb{E}[\|\xi_{k}^{i,\mathrm{mult}}(\eta)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]\,.$

Next we use the result of Property S4 for each client $i$ in $[N]$ and we
obtain:

$\displaystyle\mathbb{E}[\|\xi^{\mathrm{mult}}_{k}\left(\eta\right)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]$
$\displaystyle\leq\frac{1}{N^{2}}\sum_{i=1}^{N}\Omega
R_{i}^{2}\sigma\sqrt{\|H_{i}^{1/2}(w-w_{*})\|^{2}}+(\omega+1)R_{i}^{2}\|H_{i}^{1/2}(w-w_{*})\|^{2}\,.$

With Jensen’s inequality S2 used for concave function:

$\displaystyle\mathbb{E}\left[\left\|\xi^{\mathrm{mult}}_{k}\left(\eta\right)\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle\leq\frac{\Omega\sigma\max_{i\in[N]}(R_{i}^{2})}{N}\sqrt{\frac{1}{N}\sum_{i=1}^{N}\|H_{i}^{1/2}(w-w_{*})\|^{2}}$
$\displaystyle\qquad+\frac{(\omega+1)\max_{i\in[N]}(R_{i}^{2})}{N^{2}}\sum_{i=1}^{N}\|H_{i}^{1/2}(w-w_{*})\|^{2}$
$\displaystyle\leq\frac{\Omega\sigma\max_{i\in[N]}(R_{i}^{2})}{N}\sqrt{\|\overline{H}^{1/2}(w-w_{*})\|^{2}}$
$\displaystyle\qquad+\frac{1}{N}(\omega+1)\max_{i\in[N]}(R_{i}^{2})\|\overline{H}^{1/2}(w-w_{*})\|^{2}\,,$

which allows concluding.

######  Property S11 (Validity of Assumption 3).

Consider Algorithm 3 in the context of Model 1 with Lemma 1, if the compressor
$\mathcal{C}$ is linear, then for any iteration $k$ in $\mathbb{N}^{*}$, the
multiplicative noise $\xi_{k}^{\mathrm{mult}}$ is linear, thus there exist a
matrix $\Xi_{k}$ in $\mathbb{R}^{d\times d}$ such that for any $w$ in
$\mathbb{R}^{d}$, $\xi_{k}^{\mathrm{mult}}(w)=\Xi_{k}w$. Furthermore the
second moment of the multiplicative noise can be bounded for any $w$ in
$\mathbb{R}^{d}$ by
$(\omega+1)\max_{i\in[N]}(R_{i}^{2})\left\|\overline{H}^{1/2}(w-w_{*})\right\|^{2}/N$,
hence Assumption 3 is verified.

Proof  Let $k$ in $\mathbb{N}^{*}$, we note $\eta=w-w_{*}$. Because we
consider Algorithm 3, with Definitions 1 and 2, we write
$\xi_{k}^{\mathrm{mult}}(\eta)=\frac{1}{N}\sum_{i=1}^{N}\xi_{k}^{i,\mathrm{mult}}(\eta)$,
where
$\xi_{k}^{i,\mathrm{mult}}(\eta)=H_{i}\eta-\mathcal{C}(\textsl{g}_{k}^{i}(w))+\mathcal{C}(g_{k,*}^{i})$
is the multiplicative noise on client $i$ in $[N]$. And because for any
clients $i$ in $\\{1,\cdots N\\}$ the random mechanism $\mathcal{C}^{i}_{k}$
is linear, there exists a random matrix $\Pi_{k}^{i}$ in $\mathbb{R}^{d\times
d}$ s.t. for any $z$ in $\mathbb{R}^{d}$, we have
$\mathcal{C}_{k}^{i}(z)=\Pi_{k}^{i}z$, it follows that:

$\displaystyle\xi^{\mathrm{mult}}_{k}\left(\eta\right)=\nabla
F(w)-\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(\textsl{g}_{k}^{i}(w))+\mathcal{C}_{k}^{i}(g_{k,*}^{i})=\left(\overline{H}-\frac{1}{N}\sum_{i=1}^{N}\Pi_{k}^{i}(x_{k}^{i}\otimes
x_{k}^{i})\right)\eta\,.$

Hence, the first part of Item 2.2 is verified with
$\Xi_{k}=\frac{1}{N}\sum_{i=1}^{N}H_{i}-\Pi_{k}^{i}(x_{k}^{i}\otimes
x_{k}^{i})$. From Property S9, taking expectation w.r.t. the $\sigma$-algebra
$\mathcal{F}_{k-1}$, decomposing the multiplicative noise results to have:

$\displaystyle\mathbb{E}\left[\left\|\xi^{\mathrm{mult}}_{k}\left(\eta\right)\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]=\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbb{E}\left[\left\|\xi_{k}^{i,\mathrm{mult}}(\eta)\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]\,.$

Next we use the result of Property S5 for each client $i$ in $[N]$ and we
obtain:

$\displaystyle\mathbb{E}\left[\left\|\xi^{\mathrm{mult}}_{k}\left(\eta\right)\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}(\omega+1)R_{i}^{2}\left\|H_{i}^{1/2}(w-w_{*})\right\|^{2}$
$\displaystyle\leq\frac{(\omega+1)\max_{i\in[N]}(R_{i}^{2})}{N^{2}}\left\|\frac{1}{N}\sum_{i=1}^{N}H_{i}^{1/2}(w-w_{*})\right\|^{2}\,,$

which allows concluding.

######  Property S12 (Validity of Assumption 4).

Considering Algorithm 3 under the setting of Model 2 with Remarks 1 and 1, if
the compressor $\mathcal{C}$ is linear, then for any $k$ in $\mathbb{N}^{*}$,
we have
$\mathfrak{C}_{\mathrm{ania}}\preccurlyeq\sigma^{2}\max_{i\in[N]}(\Sha_{H_{i}})\overline{H}/N$
and
$\mathbb{E}\left[\Xi_{k}\Xi_{k}^{\top}\right]\preccurlyeq\max_{i\in[N]}(R_{i}^{2}\Sha_{H_{i}})\overline{H}/N$,
with $(\Sha_{H_{i}})_{i\in[N]}$ given in Corollary 2. Overall, Assumption 4 is
thus verified.

Proof

First inequality.

By Definition 3, we have
$\mathfrak{C}_{\mathrm{ania}}=\mathbb{E}[\xi_{k}^{\mathrm{add}}\otimes\xi_{k}^{\mathrm{add}}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]=\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbb{E}[\mathcal{C}_{k}^{i}(g_{k,*}^{i})^{{\otimes
2}}\leavevmode\nobreak\ |\leavevmode\nobreak\ \mathcal{F}_{k-1}]$, because for
any client $i$ in $[N]$ $\left((\varepsilon_{k}^{i})_{k\in[K]}\right)$ is
independent from $\left((x_{k}^{i})_{k\in[K]}\right)$ (Model 1) and using
compressor linearity and Equation S25, it gives:

$\mathfrak{C}_{\mathrm{ania}}=\sigma^{2}\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbb{E}\left[\mathcal{C}_{k}^{i}(x_{k}^{i})^{{\otimes
2}}\right]=\frac{\sigma^{2}}{N^{2}}\sum_{i=1}^{N}\mathfrak{C}(\mathcal{C}^{i},p_{{H}_{i}})\preccurlyeq\frac{\sigma^{2}}{N^{2}}\sum_{i=1}^{N}\Sha_{H_{i}}H\preccurlyeq\frac{\sigma^{2}\max_{i\in[N]}(\Sha_{H_{i}})}{N}\overline{H}\,.$

Second inequality.

Using Property S11, because the random mechanism $\mathcal{C}^{i}$ is linear,
there exists two matrices $\Pi_{k}^{i},\Xi_{k}^{i}$ in $\mathbb{R}^{d\times
d}$ s.t. for any $z$ in $\mathbb{R}^{d}$, we have
$\mathcal{C}_{k}^{i}(z)=\Pi_{k}^{i}z$ and
$\xi_{k}^{\mathrm{mult,i}}(z)=\Xi_{k}^{i}z=(H_{i}-\Pi_{k}^{i}(x_{k}^{i}\otimes
x_{k}^{i})z$, which gives that
$\Xi_{k}=\frac{1}{N}\sum_{i=1}^{N}H_{i}-\Pi_{k}^{i}(x_{k}^{i}\otimes
x_{k}^{i})$. It follows that:

$\displaystyle\Xi_{k}\Xi_{k}^{\top}$
$\displaystyle=\frac{1}{N^{2}}\sum_{i=1}^{N}(\Xi_{k}^{i})(\Xi_{k}^{i})^{\top}+\frac{1}{N^{2}}\sum_{i\neq
j}(\Xi_{k}^{i})(\Xi_{k}^{j})^{\top}\,.$

Taking the $\sigma$-algebra $\mathcal{F}_{k-1}$, using that the $N$
compressions are independent (Algorithm 3) and that for any $i$ in $[N]$,
$\mathbb{E}\left[\xi_{k}^{i,\mathrm{mult}}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]=0$ (Lemma 1) results to
have $\mathbb{E}[\Xi_{k}\Xi_{k}^{\top}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]=\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbb{E}\left[(\Xi_{k}^{i})(\Xi_{k}^{i})^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$. Now, we can reuse the
computations given in Property S6 to obtain
$\mathbb{E}\left[(\Xi_{k}^{i})(\Xi_{k}^{i})^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]\preccurlyeq
R_{i}^{2}\Sha_{H_{i}}H_{i}$. Therefore, we can state that
$\mathbb{E}\left[\Xi_{k}\Xi_{k}^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]\preccurlyeq\max_{i\in[N]}(R_{i}^{2}\Sha_{H_{i}})\overline{H}/N$,
which concludes the second part of the verification of Assumption 4.

###  F.2 Heterogeneous optimal point

In this section, we explore further the scenario of concept-shift by adding a
memory mechanism (Mishchenko et al., 2019). This mechanism has been shown by
Philippenko and Dieuleveut (2020) to improve the convergence in the case of
heterogeneous clients. We give below the updates equation defining the
algorithm of distributed compressed LSR with memory.

######  Algorithm 4 (Distributed compressed LMS with control variates).

Each client $i\in[N]$ maintains a sequence $(h_{k}^{i})_{i\in[N]}$ in
$\mathbb{R}^{d}$, observes at any step $k\in[K]$ an oracle
$\textsl{g}_{k}^{i}(\cdot)$ on the gradient of the local objective function
$F_{i}$ and applies an independent random compression mechanism
$\mathcal{C}_{k}^{i}(\cdot)$ to the difference $\textsl{g}_{k}^{i}-h_{k}^{i}$.
And for any step-size $\gamma>0$, any $k\in\mathbb{N}^{*}$, the sequence of
iterates $(w_{k})_{k\in\mathbb{N}}$ satisfies:

$\left\\{\begin{aligned}
&w_{k}=w_{k-1}-\frac{\gamma}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(\textsl{g}_{k}^{i}(w_{k-1})-h_{k-1}^{i})+h_{k-1}^{i}\\\
&h_{k}^{i}=h_{k-1}^{i}+\alpha\mathcal{C}_{k}^{i}(\textsl{g}_{k}^{i}(w_{k-1})-h_{k-1}^{i})\,,\end{aligned}\right.$
(S31)

with $\alpha=1/2(\omega+1)$.

The counterpart of adding memory is that the random fields are no more
identically distributed, thus Definition 1 is not fulfilled, and results from
Section 2 cannot be applied, especially because
$\mathbb{E}\left[\xi_{k}^{\mathrm{add}}\otimes\xi_{k}^{\mathrm{add}}\right]$
changes along iterations. To remedy this problem, we define here the _limit_
of the covariance of the additive noise i.e.
$\mathfrak{C}_{\mathrm{ania}}^{\infty}=\underset{k\to+\infty}{\lim}\mathbb{E}\left[\xi_{k}^{\mathrm{add}}\otimes\xi_{k}^{\mathrm{add}}\right]$.
In the following result, we establish an asymptotic result on the convergence,
similar to Theorem 1.

######  Theorem S4 (CLT for concept-shift heterogeneity).

Consider Algorithm 4 under Model 1 with $\mu>0$ and Lemma 1, for any step-size
$(\gamma_{k})_{k\in\mathbb{N}^{*}}$ s.t. $\gamma_{k}=1/\sqrt{k}$. Then

  1. 1.

$(\sqrt{K}\overline{\eta}_{K-1})_{K>0}\xrightarrow[K\to+\infty]{\mathcal{L}}\mathcal{N}(0,H_{F}^{-1}\mathfrak{C}_{\mathrm{ania}}^{\infty}H_{F}^{-1})$,

  2. 2.

$\mathfrak{C}_{\mathrm{ania}}^{\infty}=\overline{\mathfrak{C}((\mathcal{C}^{i},p_{\Theta_{i}^{\prime}})_{i=1}^{N})}$,
where $p_{\Theta_{i}^{\prime}}$ is the distribution of $g_{k,*}^{i}-\nabla
F_{i}(w_{*})$.

Theorem S4 shows that when using memory, in the settings of heterogeneous
optimal points $(w_{*}^{i})_{i=1}^{N}$, convergence is still impacted by
heterogeneity but with a smaller additive noise’s covariance as
$\Theta_{i}^{\prime}\prec\Theta_{i}$. In particular, in the case of
deterministic gradients (batch case), we case $\Theta_{i}^{\prime}\equiv 0$.
From a technical standpoint, it shows that we recover asymptotically the
results stated by Theorems 1 and 2 in the general setting of i.i.d. random
fields $(\xi_{k}(\eta_{k-1}))_{k\in\mathbb{N}^{*}}$. To prove this theorem, we
show that the assumptions required by Theorem S1 are fulfilled by this
framework.

Proof

For the sake of demonstration, we define a Lyapunov function $V_{k}$ (as in
Mishchenko et al., 2019; Liu et al., 2020; Philippenko and Dieuleveut, 2020),
with $k$ in $\llbracket 1,K\rrbracket$:

$V_{k}=\left\|\eta_{k}\right\|^{2}+2\gamma_{k}^{2}C\frac{1}{N}\sum_{i=1}^{N}\left\|h_{k-1}^{i}-\nabla
F_{i}(w_{*})\right\|^{2}\,,$

with $C$ in $\mathbb{R}^{*}$ being a Lyapunov constant that verifies some
conditions given in Theorem S6 in Philippenko and Dieuleveut (2020). For any
$k$ in $\mathbb{N}$, the Lyapunov function is defined combining two terms: (1)
the distance from parameter $w_{k}$ to the optimal parameter $w_{*}$, (2) for
any client $i$ in $[N]$, the distance between the memory term $h_{k-1}^{i}$
and the true gradient $\nabla F_{i}(w_{*})$.

First, we have that in the case of decreasing step size s.t. for any $k$ in
$\mathbb{N}$, $\gamma_{k}=k^{-\alpha}$, we have
$\eta_{K}\xrightarrow[K\to+\infty]{L^{2}}0$ and
$h_{K}^{i}\xrightarrow[K\to+\infty]{L^{2}}\nabla F_{i}(w_{*})$.

Let $k$ in $\mathbb{N}^{*}$, from the demonstration of the Artemis algorithm
with memory, we have from Theorem S6 in Philippenko and Dieuleveut (2020) (see
page 41-45) that (1) combining Equations (S14) and (S15) in the form
(S14)$+2\gamma_{k}^{2}C$(S15), (2) and applying strong-convexity, allows to
obtain Equation (S17) but adapted to decreasing step-size:

$\displaystyle\mathbb{E}\left[V_{k}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle\leq\left(1-2\gamma_{k}\mu\Box_{k}\right)\left\|w_{k-1}-w_{*}\right\|^{2}+\frac{2\gamma_{k}^{2}C\diamondsuit}{N}\sum_{i=1}^{N}\left\|h_{k-1}^{i}-\nabla
F_{i}(w_{*})\right\|^{2}+\frac{2\gamma_{k}^{2}\sigma\triangle}{N}\,,$

with $\Box_{k},\diamondsuit,\triangle$ being three constants in $\mathbb{R}$
whose exact expression can be found on pages 42-43 in Philippenko and
Dieuleveut (2020). Furthermore, in the same article, they verify that to
obtain a $(1-\gamma_{k}\mu)$ convergence, the following condition on
$\Box_{k},\diamondsuit,\triangle$ are fulfilled for any $k$ in
$\mathbb{N}^{*}$: $\Box_{k}\leq 1/2$ and $\diamondsuit\leq 1-\gamma_{k}\mu$.

These properties are valid under some conditions on the Lyapunov constant $C$,
the step-size $\gamma_{k}$, and the learning rate $\alpha$; these conditions
are provided in the statement of Theorem S6 from (Philippenko and Dieuleveut,
2020) and we don’t recall them here. Hence, we can write that we have:

$\displaystyle\mathbb{E}\left[V_{k}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle\leq(1-\gamma_{k}\mu)\left(\left\|w_{k-1}-w_{*}\right\|^{2}+\frac{2\gamma_{k}^{2}C}{N}\sum_{i=1}^{N}\left\|h_{k-1}^{i}-\nabla
F_{i}(w_{*})\right\|^{2}\right)+\frac{2\gamma_{k}^{2}\sigma^{2}\triangle}{N}\,,$

and because for any $k$ in $N$, the step-size is decreasing, we have
$\gamma_{k}\leq\gamma_{k-1}$, which makes to recover the Lyapunov function
$V_{k-1}$ at step $k-1$: $\mathbb{E}\left[V_{k}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]\leq(1-\gamma_{k}\mu)V_{k-1}+\frac{2\gamma_{k}^{2}\sigma^{2}\triangle}{N}$.
Taking full expectation and unrolling the sequence $(V_{k})_{k\in\mathbb{N}}$,
we obtain:

$\displaystyle\mathbb{E}V_{k}$
$\displaystyle\leq\prod_{i=1}^{k}(1-\gamma_{i}\mu)V_{0}+\frac{2\sigma^{2}\triangle}{N}\sum_{j=1}^{k}\gamma_{j}^{2}\prod_{i=j+1}^{k}(1-\gamma_{i}\mu)\,.$

To show that each part of the bound given in the above equation tends to zero
when $k$ grows to infinity is classical computations and can be find for
instance in lectures notes of Bach (2022, pages 164-167 and 182), and Kushner
and Yin (2003).

To apply Theorem 1 from Polyak and Juditsky (1992, recalled in Theorem S1),
which gives the desired result, it suffices to prove the convergence in
probability of the covariance of the noise $\xi_{k}(\eta_{k-1})$ towards
$\mathfrak{C}_{\mathrm{ania}}$, as $k\to\infty$.

In the following, we show that
$\underset{k\to+\infty}{\lim}\mathbb{E}\left[\xi_{k}(\eta_{k-1})\xi_{k}(\eta_{k-1})^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]\stackrel{{\scriptstyle\mathbb{P}}}{{=}}\mathfrak{C}_{\mathrm{ania}}^{\infty}$.
Let $k$ in $\mathbb{N}^{*}$, for this purpose, we consider the following
additive/multiplicative noise decomposition:

$\left\\{\begin{aligned}
&\xi_{k,*}^{\mathrm{A}}=-\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(g_{k,*}^{i}-\nabla
F_{i}(w_{*}))\\\
&\xi_{k}^{\mathrm{M}}(\eta_{k})=H_{F}\eta_{k}-\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(\textsl{g}_{k}^{i}(w_{k-1})-h_{k-1}^{i})+\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(g_{k,*}-\nabla
F_{i}(w_{*}))+h_{k-1}^{i}\,.\end{aligned}\right.$ (S32)

Furthermore, we have that
$\xi_{k}^{\mathrm{add}}\xrightarrow[k\to+\infty]{L^{2}}\xi_{k,*}^{\mathrm{A}}$
because of the Hölder-inequality (Lemma 1) and because we shown that
$h_{K}^{i}\xrightarrow[K\to+\infty]{L^{2}}\nabla F_{i}(w_{*})$; thereby
$\mathbb{E}[\xi_{k}^{\mathrm{add}}\otimes\xi_{k}^{\mathrm{add}}]\xrightarrow[k\to+\infty]{L^{1}}\mathfrak{C}_{\mathrm{ania}}^{\infty}$.
Next, from Equation S32, we write:

$\displaystyle\xi_{k}(\eta_{k-1})\xi_{k}(\eta_{k-1})^{\top}$
$\displaystyle=(\xi_{k,*}^{\mathrm{A}}-\xi_{k}^{\mathrm{M}}(\eta_{k-1}))(\xi_{k,*}^{\mathrm{A}}-\xi_{k}^{\mathrm{M}}(\eta_{k-1}))^{\top}$
$\displaystyle=\xi_{k,*}^{\mathrm{A}}\otimes\xi_{k,*}^{\mathrm{A}}-\xi_{k,*}^{\mathrm{A}}\xi_{k}^{\mathrm{M}}(\eta_{k-1})^{\top}-\xi_{k}^{\mathrm{M}}(\eta_{k-1})(\xi_{k,*}^{\mathrm{A}})^{\top}+\xi_{k}^{\mathrm{M}}(\eta_{k-1})\otimes\xi_{k}^{\mathrm{M}}(\eta_{k-1})\,.$

(i) Developing the covariance of the additive noise and considering Models 1
and 3 results to
$\mathbb{E}[\xi_{k,*}^{\mathrm{A}}\otimes\xi_{k,*}^{\mathrm{A}}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]=\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbb{E}[\mathcal{C}_{k}^{i}(g_{k,*}^{i}-\nabla
F_{i}(w_{*}))^{{\otimes 2}}\leavevmode\nobreak\ |\leavevmode\nobreak\
\mathcal{F}_{k-1}]$. For any iteration $k$ in $\mathbb{N}^{*}$ and any client
$i$ in $[N]$, we note $\Theta_{i}^{\prime}$ the covariance of
$g_{k,*}^{i}-\nabla F_{i}(w_{*})$, then $g_{k,*}^{i}-\nabla F_{i}(w_{*})$ is
an i.i.d. zero-centered random vectors draw from a distribution
$p_{\Theta_{i}^{\prime}}$, hence we have for any iteration $k$ in
$\mathbb{N}^{*}$,
$\mathfrak{C}_{\mathrm{ania}}^{\infty}=\mathbb{E}[\xi_{k,*}^{\mathrm{A}}\otimes\xi_{k,*}^{\mathrm{A}}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]=\overline{\mathfrak{C}(\mathcal{C}^{i},(p_{\Theta_{i}^{\prime}})_{i=1}^{N})}\,.$

(ii) Second, we show that
$\mathbb{E}\left[\xi_{k}^{\mathrm{M}}(\eta_{k-1})^{{\otimes
2}}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
converge to 0 in probability: it is sufficient to show that
$\|\xi_{k}^{\mathrm{M}}(\eta_{k-1})^{{\otimes 2}}\|_{F}$ tends to 0. To do so,
we use the fact that $\|\xi_{k}^{\mathrm{M}}(\eta_{k-1})^{{\otimes
2}}\|_{F}=\|\xi_{k}^{\mathrm{M}}(\eta_{k-1})\|^{2}_{2}$, it results to the
following decomposition:

$\displaystyle\|\xi_{k}^{\mathrm{M}}(\eta_{k-1})^{{\otimes 2}}\|$
$\displaystyle\leq
3\left\|H\eta_{k-1}\right\|^{2}+3\left\|\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(\textsl{g}_{k}^{i}(w_{k-1})-h_{k-1}^{i})-\mathcal{C}_{k}^{i}(g_{k,*}^{i}-\nabla
F_{i}(w_{*}))\right\|^{2}$
$\displaystyle\qquad\qquad+3\left\|\frac{1}{N}\sum_{i=1}^{N}h_{k-1}^{i}-\nabla
F_{i}(w_{*})\right\|^{2}\,.$

Considering the Hölder inequality given in Item L.2 from Lemma 1, because
$\eta_{k}\xrightarrow[k\to+\infty]{L^{2}}0$ and
$h_{k}^{i}\xrightarrow[k\to+\infty]{L^{2}}\nabla F_{i}(w_{*})$, we deduce that
$\mathbb{E}\left[\xi_{k}^{\mathrm{M}}(\eta_{k-1})^{{\otimes
2}}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
tends to $0$ in $L^{1}$-norm.

(iii) Third, it remains to show that
$\mathbb{E}[\xi_{k}^{\mathrm{M}}(\eta_{k-1})(\xi_{k,*}^{\mathrm{A}})^{\top}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]\xrightarrow[k\to+\infty]{\mathbb{P}}0$. We use the Cauchy-
Schwarz inequality’s S3 for conditional expectation:

$\displaystyle\mathbb{E}\left[\xi_{k}^{\mathrm{M}}(\eta_{k-1})(\xi_{k,*}^{\mathrm{A}})^{\top}\|_{F}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]^{2}$
$\displaystyle=\mathbb{E}\left[\xi_{k}^{\mathrm{M}}(\eta_{k-1})\|_{2}\|(\xi_{k,*}^{\mathrm{A}})^{\top}\|_{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]^{2}$
$\displaystyle\leq\|\mathbb{E}\left[\xi_{k}^{\mathrm{M}}(\eta_{k-1})\|^{2}_{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]\mathbb{E}\left[\|(\xi_{k,*}^{\mathrm{A}})^{\top}\|^{2}_{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]\,.$

The sequence of random vectors $(\xi_{k,*}^{\mathrm{A}})_{k\in\mathbb{N}}$ is
i.i.d., and moreover we have shown previously that
$\xi_{k}^{\mathrm{M}}(\eta_{k-1})^{{\otimes 2}}$ tends to 0, hence
$\mathbb{E}[\xi_{k}^{\mathrm{M}}(\eta_{k-1})(\xi_{k,*}^{\mathrm{A}})^{\top}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]$ converges to $0$ in distribution.
Consequently, noting $\Theta_{i}^{\prime}=\mathbb{E}[g_{k,*}^{i}-\nabla
F_{i}(w_{*}))^{{\otimes 2}}]$ we can state that:

$\displaystyle\mathbb{E}\left[\xi_{k}(\eta_{k-1})^{{\otimes
2}}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]\xrightarrow[k\to+\infty]{\mathbb{P}}\mathfrak{C}_{\mathrm{ania}}^{\infty}=\overline{\mathfrak{C}(\mathcal{C}^{i},(p_{\Theta_{i}^{\prime}})_{i=1}^{N})}\,.$


# Dynamic Channel Selection in Self-Supervised Learning

Tarun KrishnaDynamic Channel Selection in Self-Supervised Learning Insight
Centre for Data Analytics, Dublin City University, Dublin, Ireland  Ayush K.
RaiDynamic Channel Selection in Self-Supervised Learning Insight Centre for
Data Analytics, Dublin City University, Dublin, Ireland  Yasser A. D. Djilali
Insight Centre for Data Analytics, Dublin City University, Dublin, Ireland
Alan F. Smeaton  Insight Centre for Data Analytics, Dublin City University,
Dublin, Ireland
Kevin McGuinness and Noel E. O’Connor  Insight Centre for Data Analytics,
Dublin City University, Dublin, Ireland

###### Abstract

Whilst computer vision models built using self-supervised approaches are now
commonplace, some important questions remain. Do self-supervised models learn
highly redundant channel features? What if a self-supervised network could
dynamically select the important channels and get rid of the unnecessary ones?
Currently, convnets pre-trained with self-supervision have obtained comparable
performance on downstream tasks in comparison to their supervised counterparts
in computer vision. However, there are drawbacks to self-supervised models
including their large numbers of parameters, computationally expensive
training strategies and a clear need for faster inference on downstream tasks.
In this work, our goal is to address the latter by studying how a standard
channel selection method developed for supervised learning can be applied to
networks trained with self-supervision. We validate our findings on a range of
target budgets $t_{d}$ for channel computation on image classification task
across different datasets, specifically CIFAR-10, CIFAR-100, and ImageNet-100,
obtaining comparable performance to that of the original network when
selecting all channels but at a significant reduction in computation reported
in terms of FLOPs.

**footnotetext: Equal contribution.

Keywords: Dynamic Neural Networks, Self-Supervised Learning (SSL), Computer
Vision

##  1 Introduction

Self-supervised pre-training of convolutional neural networks, as mentioned in
[Chen et al., 2020], has almost matched the performance of supervised pre-
training on the ImageNet [Deng et al., 2009] image classification task, but at
a cost of a huge number of parameters and inefficient training and inference
methods. In the supervised learning setting, as described in [Veit and
Belongie, 2018], it is accepted that networks with dynamic data dependent
(conditional) channel computation architectures during inference can lead to
enhanced representation power, adaptivity, interpretability and can greatly
reduce computation cost and memory resources without compromising on the
accuracy by a significant margin. This motivates us to investigate the
behaviour of neural networks with a channel selection mechanism trained under
self-supervision. We hypothesise that self-supervised models are an ideal
candidate for such dynamic network structures as they capture highly redundant
channel features during pre-training. In addition, there is also a great need
to explore more efficient inference methods on downstream tasks for SSL.

In order to establish the trade off between computation and performance, there
are two well established research directions when it comes to introducing
channel sparsity using dynamic structure in neural networks: channel pruning
and channel conditional computation. Dynamic channel pruning, as reported in
[Gao et al., 2018], estimates channel saliency measures and allows a network
to learn and prioritise certain channels and ignore the irrelevant ones given
a fixed target density. Models based on pruning usually learn sparsity through
a three stage pipeline i.e, pretrain-prune-finetune while in other works like
[Tiwari et al., 2021] the pruning stage itself consists of two steps, namely
soft pruning and hard pruning. Conditional channel computation as proposed in
[Herrmann et al., 2020] learns to compute only a subset of channels in every
layer for the given input and hence benefits inference time efficiency and
provides an insight into dataset specific network behaviour. Both channel
pruning and conditional channel computation are categorical decisions that
cannot be optimised by gradient descent methods; however, using the Gumbel-
Softmax trick from [Jang et al., 2016] provides a way to overcome this
challenge. Adafuse [Meng et al., 2020] proposed an adaptive temporal fusion
network that learns a decision policy to dynamically fuse channels from
current and history feature maps (i.e. dynamically deciding which channels to
keep, reuse or skip per layer and per instance) for action recognition.
Notwithstanding these works, the use of dynamic networks for channel selection
has to date been mostly limited to supervised learning settings only.

To the best of our knowledge, there is no study on the impact of conditional
channel selection on SSL. The work described in [Caron et al., 2020b] studies
the effect of standard pruning techniques developed for supervised learning on
a network trained with self-supervision. In particular they use an iterative
magnitude based pruning technique described in [Han et al., 2015], which
compresses the network by alternatively minimising a training objective and
pruning the network parameters with smallest magnitude. The weights of the
resulting sub-network are reset based on a weight initialisation scheme: the
lottery winning ticket [Frankle and Carbin, 2018, Frankle et al., 2020]. We
adopt a similar strategy but focus on exploring the application of standard
conditional channel selection methods, as proposed in [Li et al., 2021], to
self-supervised models during the pre-training stage and do not include any
re-training. Our contributions can be summarised as follows:

  1. 1.

Do self-supervised models learn redundant channel features? Through our
exhaustive evaluation we demonstrate that the SSL model (SimSiam) does indeed
learn redundant channel features.

  2. 2.

We show in Table 1 that exploiting this redundancy leads to a drop in
computational complexity (FLOPs), reducing inference time without excessively
increasing training time, as we learn from scratch and on-the-fly, unlike
competing approaches [Caron et al., 2020b] that involve re-training.

  3. 3.

We demonstrate that this channel selection mechanism preserves the feature
quality when evaluated on the task of image classification and gives
comparable performance when compared with a vanilla (no channel selection) SSL
approach.

##  2 Related Works

###  2.1 Self-Supervised Representation Learning

SSL has recently matched the performance of supervised learning on several
computer vision benchmarks [Chen et al., 2020, Djilali et al., 2021, Krishna
et al., 2021, Bachman et al., 2019, Grill et al., 2020]. Below we summarize
the recent works in the direction of self-supervised learning.

Contrastive Learning. Contrastive learning refers to learning by comparison
[Oord et al., 2018, Chen et al., 2020] where the final objective is based on
some variation of Noise Contrastive Estimation (NCE). The main intuition is to
bring similar instances closer in the embedding space while contrasting them
with other negative samples to avoid feature collapse. These methods are
usually trained in a Siamese setting with shared weights using a large batch
size or memory bank [Chen et al., 2020, Oord et al., 2018, Wu et al., 2018,
Misra and Maaten, 2020].

Clustering Methods. One category of self-supervised methods for representation
learning is based on clustering [Caron et al., 2018, Asano et al., 2019, Caron
et al., 2020a], which alternates between clustering the representations and
learning to predict the cluster assignment. These clustering method are also
based on contrastive approaches but at cluster level, which also makes the
training computationally expensive.

Distillation Methods. Recent approaches like BYOL [Grill et al., 2020] and
SimSiam [Chen and He, 2021], need no negative samples, yet they learn useful
representations and perform on-par with other SSL methods. They learn in a
student-teacher setting and consequently avoid feature collapse. However, why
and how they avoid collapse is still unclear and an open research area.

Information Maximization. A more principled way to avoid feature collapse is
to capture information bottlenecks as in Barlow Twins [Zbontar et al., 2021]
and VICReg [Bardes et al., 2021].

It is unclear how many channel redundant features are learned by these self-
supervised approaches. In this work we aim to study this redundancy by
exploiting a dynamic channel selection mechanism from the literature.

###  2.2 Dynamic Channel Computation

Channel Pruning. Channel pruning estimates channel saliency measures and
eliminates all input and output connections from unimportant channels. The
approach reported in [Wen et al., 2016] added group Lasso on channel weights
to the model’s training loss function resulting in a reduction of the
magnitude of channel weights during training. The authors in [He et al., 2018]
proposed pruning channels using thresholds by setting unimportant channels to
zero. Network Slimming [Liu et al., 2017] used Lasso regularisation with
global thresholds. However, deep models pruned with structured sparsity
methods lose their capabilities and connections permanently. As a result,
dynamic channel pruning methods were devised that learn sparsity through a
three-stage pipeline pretrain-prune-finetune or use pretrained models. The
authors of [Gao et al., 2018] propose feature boosting and suppression (FBS)
to dynamically amplify and suppress output channels computed by convolutional
layers. [Tiwari et al., 2021] presents a deterministic pruning strategy using
the continuous heaviside function and crispness loss to identify a highly
sparse subnetwork from an existing dense network.

Conditional Channel Computation. Regarding conditional computation at the
channel level, the work proposed in [Lin et al., 2017] generates decisions to
skip computation for a subset of output channels. The channel gating network
[Hua et al., 2019] finds regions among the features that contribute less to
the classification result and skips computation on a subset of the input
channels for these ineffective regions. ConvAIG [Veit and Belongie, 2018]
introduced a network with a hard attention mechanism that adaptively selects
specific layers of importance for each input image to assemble an inference
graph by specifying a target rate for each layer. The authors of [Herrmann et
al., 2020] also study conditional computation at the channel level and extend
ConvAIG by learning target rates for each gate by specifying the target rate
for the whole network. DGNet [Li et al., 2021] proposed a dual gating
mechanism by introducing sparsity along two separate dimensions, spatial and
channel, in order to reduce model complexity at run time. For a more detailed
background on sparsity, pruning and conditional computation, we recommend the
review work presented in [Hoefler et al., 2021].

While [Caron et al., 2020b] studied the behaviour of self-supervised models
under standard pruning techniques, we investigate the effect of standard
channel selection methods described in DGNet on self-supervised models. We
also analyse whether networks trained under self-supervision with channel
selection can preserve performance on downstream tasks.

##  3 Method

###  3.1 Self-supervised Module

In this work we consider SimSiam [Chen and He, 2021] as our self-supervised
objective. We use ResNet18 as a base encoder***across all experiments, which
takes two augmented views $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ from an anchor
view $\mathbf{x}$ by applying stochastic augmentation from a set of
augmentations $\mathcal{P}$. $\mathcal{P}$ comprises random resized crop,
color jitter, random gray scale, Gaussian blur and random horizontal flip.
These augmented views are processed through $f_{\boldsymbol{\theta}}$ to get a
compact representation of
$f_{\boldsymbol{\theta}}(\mathbf{x}_{1}),f_{\boldsymbol{\theta}}(\mathbf{x}_{2})\in\mathbb{R}^{512}$.
One view is further processed by a prediction MLP head (bottleneck
architecture) $g_{\boldsymbol{\phi}}$ giving rise to an asymmetric
architecture i.e. $\mathbf{p}_{1}\triangleq
g_{\boldsymbol{\phi}}(f_{\boldsymbol{\theta}}(\mathbf{x}_{1})))$ and
$\mathbf{z}_{2}\triangleq f_{\boldsymbol{\theta}}(\mathbf{x}_{2})$. As a
standard practise, a base encoder is augmented with a projection head MLP
i.e., $f_{\boldsymbol{\theta}}=h\circ m,$ where $m$ and $h$ represents
ResNet18 and projection layers respectively. The SimSiam learning objective
simplifies to a symmetric cosine similarity:

$\mathcal{L}_{\texttt{SSL}}=\frac{1}{2}\mathcal{D}(\mathbf{p_{1}},\texttt{SG}(\mathbf{z_{2}}))+\frac{1}{2}\mathcal{D}(\mathbf{p_{2}},\texttt{SG}(\mathbf{z_{1}})),$
(1)

where $\mathcal{D}(\mathbf{a},\mathbf{b})=-\mathbf{a}^{T}\mathbf{b}$, with
$\mathbf{a}$ and $\mathbf{b}$ being $L_{2}$ normalised vectors***i.e.
$\mathcal{D}(\mathbf{a},\mathbf{b})$ is negative cosine similarity.. SG stands
for Stop-Grad().

###  3.2 Channel Selection via Gating

Preliminaries. Channel selection or conditional computation (data dependent
gates) is often realised through a gating mechanism. A typical output for an
input $\mathbf{x}$ from a convolutional (conv) layer $l$ is given by
$f_{l}(\mathbf{x}_{l-1})\in\mathbb{R}^{C\times H\times W}$ where
$f_{l}(\mathbf{x}_{l-1})$ consists of a convolution operation with kernel size
$k$ followed with a batch normalization layer (BN) and relu ($(\cdot)_{+}$)
non-linearity with $\mathbf{x}_{l-1}$ being the output from the previous
layer. The output from a gated convolutional network can be realised as:
$\hat{f}_{l}(\mathbf{x}_{l-1})=\pi_{l}(\mathbf{x}_{l-1})\cdot\text{BN}(\texttt{conv}_{l}(\mathbf{x}_{l-1}))_{+}$,
where $\pi_{l}(\mathbf{x}_{l-1})\in\\{0,1\\}^{C}$***a vector of dimension
equivalent to number of channels with ones and zeroes is a gate dependent on
input $\mathbf{x}_{l-1}$, which decides whether to keep (“on”) or discard
(“off”) a particular channel. This can be seen as a form of hard attention
(mask). This masking imposes a discrete structure over the network, making a
computational graph for training and inference different. During training this
structure is realised through stochastic gradient descent (SGD), while during
inference it works as hard attention. One of the main reasons for channel
selection is to induce sparsity i.e. operate on a lower computational budget
(less FLOPs) during inference. In this work we closely follow DGNet using
ResNet18 as our base encoder.

Channel Selection (Gating). In order for gates***channel selection to be
effective, they need to estimate the importance of input features. This
importance is often referred to as relevance/saliencies (vectors) of the input
feature map (along the channels) in the literature. This relevance is crucial
in order for the network to avoid trivial solutions. A simpler way is to use
SE block [Hu et al., 2018], as was used in DGNet, to create a relevance
vector. This usually requires getting a context vector
$\mathbf{z}\in\mathbb{R}^{C}$ via global average pooling to accumulate spatial
information. Finally, this context vector $\mathbf{z}$ is passed through a
lightweight network to get channel attention $g_{l}(\mathbf{x}_{l-1})$, which
can be summarized as:

$\displaystyle
g(\mathbf{x}_{l-1})=\mathbf{W}_{1}\Big{(}\text{BN}\big{(}\mathbf{W}_{0}\mathbf{z}\big{)}\Big{)}_{+},\quad\mathbf{W}_{1}\in\mathbb{R}^{C_{l}\times\frac{C_{l-1}}{r}},\mathbf{W}_{0}\in\mathbb{R}^{\frac{C_{l}}{r}\times
C_{l}},$ (2)

where $r$ is a reduction ratio. For more details please refer to [Hu et al.,
2018]. Finally, to achieve binary mask $\pi_{l}(\mathbf{x}_{l-1})$ we can use
the channel attention $g_{l}(\mathbf{x}_{l-1})$ and set
$\pi_{l}^{i}(\mathbf{x}_{l-1})=1$ if $g_{l}^{i}(\mathbf{x}_{l-1})\geq 0$ and
$\pi_{l}^{i}(\mathbf{x}_{l-1})=0$ otherwise. This discrete selection works
during inference but it breaks the computational graph during training. To
make the training possible, the Gumbel-SoftMax Trick [Jang et al., 2016] is
adopted. The Gumbel-Trick has been widely used as reparameterisation technique
for the task of dynamic channel selection [Li et al., 2021, Herrmann et al.,
2020, Veit and Belongie, 2018, Meng et al., 2020]. A gating block is
introduced after the first convolution in Basic Block of Resnet18 following
DGNet. Intuitively, the channel selection network could be interpreted as
learning a policy whether to keep (compute) or discard (skip) a particular
channel.

###  3.3 Optimisation

To remove unimportant channels and induce sparsity in the gating mask
$\pi_{l}(\mathbf{x}_{l-1})$ we need to add an objective based on some budget
$t_{d}$. To this end we use regularisation, a term used in DGNet as sparsity
objective, which is a combination of sparsity and a bound regularisation term:

$\displaystyle{}\mathcal{L}_{G}=\lambda\underbrace{\Bigg{(}\frac{\sum_{l=1}^{L}F^{R}_{l}}{\sum_{l=1}^{L}F_{l}^{O}}-t_{d}\Bigg{)}^{2}}_{\text{Sparsity}}+\gamma\mathcal{L}_{Bound},$

where $F_{l}^{R}$ is the average FLOPs over the batch along with FLOPs
computation of the gating block, while $F_{l}^{O}$ is the original FLOPs
without a gating module. Only the blocks with gating modules take part in FLOP
computation as they are responsible for any sort of sparsity introduced in the
network. The purpose of $L_{Bound}$ is to control early optimisation as
detailed in DGNet.

Final Objective. Overall training objective is defined as:
$\mathcal{L}=\mathcal{L}_{\texttt{SSL}}+\mathcal{L}_{G}$, with $\lambda=5$ and
$\gamma=1$ across all the datasets and training regimes.

Table 1:  Performance comparison of SimSiam with dynamic channel selection
during inference. Evaluated with $k$-nearest neighbours ($k=1$) on the
validation set of CIFAR-10, CIFAR-100 and ImageNet-100 across various target
budgets $t_{d}$. * denotes baseline.

Dataset |  Budget ($t_{d}$) | Acc$\%$ | FLOPs
---|---|---|---
| * | 85.46% | 7.03E8
| 10% | 76.72% | 6.64E7 (90.55%$\downarrow$)
| 20% | 78.78% | 1.25E8 (82.11%$\downarrow$)
| 30% | 80.82% | 2.01E8 (71.41%$\downarrow$)
CIFAR-10 | 40% | 81.35% | 2.66E8 (62.18%$\downarrow$)
| 50% | 81.93% | 3.29E8 (53.15%$\downarrow$)
| 60% | 82.96% | 3.94E8 (43.89%$\downarrow$)
| 70% |  83.08% | 4.58E8 (34.76%$\downarrow$)
| * | 52.96% | 7.03E8
| 10% | 46.84% | 6.88E7 (90.21%$\downarrow$)
| 20% | 49.50% | 1.48E8 (78.88%$\downarrow$)
| 30% | 50.70% | 2.03E8 (71.01%$\downarrow$)
CIFAR-100 | 40% | 52.05% | 2.65E8 (62.32%$\downarrow$)
| 50% | 52.54% | 3.25E8 (53.67%$\downarrow$)
| 60% | 53.18% | 3.95E8 (43.73%$\downarrow$)
| 70% |  53.50% | 4.66E8 (33.69%$\downarrow$)
| * | 64.34% | 1.81E9
| 30% | 56.08% | 5.30E8(70.43%$\downarrow$)
ImageNet-100 | 40% | 57.86% | 7.13E8 (60.66%$\downarrow$)
| 50% |  60.38% | 8.78E8 (51.55%$\downarrow$)

##  4 Experimental Setup

Implementation Details. We closely follow the approach in DGNet for channel
selection. For training, we use SimSiam as a self-supervised model with
ResNet18 as a base encoder whose objective is modified as explained in section
3.3. We train the model with varying target densities $t_{d}$. The
implementation of SimSiam is based on the solo-learn library [da Costa et al.,
2022]. The base encoder is randomly initialised***default initialisation in
Pytorch and is trained with SGD for 500 epochs (for a given target budget
$t_{d}$) with a batch size of 256 on 2 Nvidia 2080Ti GPUs, with a warm-start
of 10 epochs following a cosine decay with base learning rate of 0.01. Since
we are using a very lightweight model as our gating network, there is no
significant computational overhead during training. We report the inference
speedup in terms of the hardware-independent theoretical metric of FLOPs and
not wall-clock time as we are not using any hardware accelerators to utilise
sparsity during training. Code is made available here.

Evaluation. Training and evaluation is carried on train and validation data of
CIFAR-10, CIFAR-100 and ImagNet-100 respectively. For Cifar-10/100 we train
for $t_{d}=\\{0.1,0.2,0.3,0.4,0.5,0.6,0.7\\}$ while for ImageNet-100 we
restrict $t_{d}$ to only $\\{0.3,0.4,0.5\\}$ due to computational constraints.
We use $k$-nearest neighbours as our evaluation metric evaluated with $k=1$.
For baseline we train Simsiam with standard objective without any channel
selection for each of the datasets under consideration (* in Table 1).

Results. Our main findings based on the evaluation criteria validate our
initial hypothesis that self-supervised models can learn highly redundant
channel features.

Table 1 shows that in the case of CIFAR-10, by keeping only 70% of the
channels across the whole network, SimSiam achieves 83.08% accuracy on the KNN
task, which is a minor drop from the baseline performance of 85.46% but at an
ample reduction of 34.76% in FLOPs. Furthermore, we also find that an enormous
90.55% of FLOPs can be reduced by using only 10% of the channels across the
whole network causing a drop of only 8.74% in KNN accuracy. For CIFAR-100, we
found that by restricting the channel usage to only 60% over the whole
network, SimSiam surpasses the baseline KNN accuracy of 52.95% by 0.22%
reaching 53.18%. Additionally, FLOP computation can be reduced by 90.21% by
keeping only 10% of the channels, leading to a drop of only 6.12% in KNN
accuracy. On ImageNet-100, 50% of the channel usage in the entire network
results in 60.38% KNN accuracy, which is 3.96% less than the baseline.
However, this decrease in accuracy is compensated by $\sim$51.55% percent drop
in FLOPs. Aside from this, we get a substantial 70.43% drop in FLOPs by fixing
channel utilization to only 30% in the whole model. Therefore, channel
selection can be thought of as a way to take advantage of the trade-off
between performance and computation depending the downstream task and
individual use case. These results also show that SSL models trained with
channel selection preserve the performance in downstream tasks.

Figure 1 shows the channel activation distribution for CIFAR-10, CIFAR-100 and
ImageNet-100 datasets, revealing a deeper insight into the dataset specific
behaviour of the channel selection network by visualising how many channels in
each ResNet18 blocks are always off (skipped), always on (computed), or input
dependent. We notice that significant number of channels are switched off and
switched on all the time in all the three datasets and while others are input
dependent. The channel distribution for CIFAR-10 and CIFAR-100 are very
similar, which might be due to the fact that image statistics in both of these
datasets are similar.

##  5 Conclusion

In this paper, we studied the behaviour of self-supervised learning when
integrated with channel selection networks given a global target budget for
computational cost. Our empirical results provided interesting insights about
self-supervised learning when trained with channel selection. First, self-
supervised models learn highly redundant channel features that can be
discarded to reduce computational overhead (Figure 1, Table 1). Second, we
showed that channel selection modules can significantly reduce FLOP
computation and make inference more efficient (Table 1). Third, our results
also provide intuition that representations learnt by self-supervised networks
with channel selection can also be transferred to downstream tasks.

Figure 1: Channel distribution over validation set for $t_{d}=0.5$ on
CIFAR-10, CIFAR-100, ImageNet-100

There are, however, some limitations with our work. First, we still need to
evaluate the tranferability of learned representations beyond classification
to other downstream tasks such as object segmentation, detection and instance
retrieval to name a few. Second, the SSL training objective involves
maximizing the agreement between augmented views of the same object or scenes
(instance discrimination) and this forces them to have similar representations
in the embedding space. In this work, we do not account for this by enforcing
some consistency aware constraints for channel selection in the training
objective. These limitations will be addressed in future work.

## Acknowledgments

This work has emanated from research supported by Science Foundation Ireland
(SFI) under Grant Number SFI/12/RC/2289_P2, co-funded by the European Regional
Development Fund and Xperi FotoNation.

## References

  * [Asano et al., 2019] Asano, Y. M., Rupprecht, C., and Vedaldi, A. (2019).  Self-labelling via simultaneous clustering and representation learning.  arXiv preprint arXiv:1911.05371.
  * [Bachman et al., 2019] Bachman, P., Hjelm, R. D., and Buchwalter, W. (2019).  Learning representations by maximizing mutual information across views.  Advances in neural information processing systems, 32.
  * [Bardes et al., 2021] Bardes, A., Ponce, J., and LeCun, Y. (2021).  Vicreg: Variance-invariance-covariance regularization for self-supervised learning.  arXiv preprint arXiv:2105.04906.
  * [Caron et al., 2018] Caron, M., Bojanowski, P., Joulin, A., and Douze, M. (2018).  Deep clustering for unsupervised learning of visual features.  In Proceedings of the European conference on computer vision (ECCV), pages 132–149.
  * [Caron et al., 2020a] Caron, M., Misra, I., Mairal, J., Goyal, P., Bojanowski, P., and Joulin, A. (2020a).  Unsupervised learning of visual features by contrasting cluster assignments.  Advances in Neural Information Processing Systems, 33:9912–9924.
  * [Caron et al., 2020b] Caron, M., Morcos, A., Bojanowski, P., Mairal, J., and Joulin, A. (2020b).  Pruning convolutional neural networks with self-supervision.  arXiv preprint arXiv:2001.03554.
  * [Chen et al., 2020] Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. (2020).  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR.
  * [Chen and He, 2021] Chen, X. and He, K. (2021).  Exploring simple siamese representation learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15750–15758.
  * [da Costa et al., 2022] da Costa, V. G. T., Fini, E., Nabi, M., Sebe, N., and Ricci, E. (2022).  solo-learn: A library of self-supervised methods for visual representation learning.  Journal of Machine Learning Research, 23(56):1–6.
  * [Deng et al., 2009] Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. (2009).  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee.
  * [Djilali et al., 2021] Djilali, Y. A. D., Krishna, T., McGuinness, K., and O’Connor, N. E. (2021).  Rethinking 360deg image visual attention modelling with unsupervised learning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 15414–15424.
  * [Frankle and Carbin, 2018] Frankle, J. and Carbin, M. (2018).  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  arXiv preprint arXiv:1803.03635.
  * [Frankle et al., 2020] Frankle, J., Dziugaite, G. K., Roy, D., and Carbin, M. (2020).  Linear mode connectivity and the lottery ticket hypothesis.  In International Conference on Machine Learning, pages 3259–3269. PMLR.
  * [Gao et al., 2018] Gao, X., Zhao, Y., Dudziak, Ł., Mullins, R., and Xu, C.-z. (2018).  Dynamic channel pruning: Feature boosting and suppression.  arXiv preprint arXiv:1810.05331.
  * [Grill et al., 2020] Grill, J.-B., Strub, F., Altché, F., Tallec, C., Richemond, P., Buchatskaya, E., Doersch, C., Avila Pires, B., Guo, Z., Gheshlaghi Azar, M., et al. (2020).  Bootstrap your own latent-a new approach to self-supervised learning.  Advances in Neural Information Processing Systems, 33:21271–21284.
  * [Han et al., 2015] Han, S., Pool, J., Tran, J., and Dally, W. (2015).  Learning both weights and connections for efficient neural network.  Advances in neural information processing systems, 28.
  * [He et al., 2018] He, Y., Kang, G., Dong, X., Fu, Y., and Yang, Y. (2018).  Soft filter pruning for accelerating deep convolutional neural networks.  arXiv preprint arXiv:1808.06866.
  * [Herrmann et al., 2020] Herrmann, C., Bowen, R. S., and Zabih, R. (2020).  Channel selection using gumbel softmax.  In European Conference on Computer Vision, pages 241–257. Springer.
  * [Hoefler et al., 2021] Hoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N., and Peste, A. (2021).  Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks.  Journal of Machine Learning Research, 22(241):1–124.
  * [Hu et al., 2018] Hu, J., Shen, L., and Sun, G. (2018).  Squeeze-and-excitation networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7132–7141.
  * [Hua et al., 2019] Hua, W., Zhou, Y., De Sa, C. M., Zhang, Z., and Suh, G. E. (2019).  Channel gating neural networks.  Advances in Neural Information Processing Systems, 32.
  * [Jang et al., 2016] Jang, E., Gu, S., and Poole, B. (2016).  Categorical reparameterization with gumbel-softmax.  arXiv preprint arXiv:1611.01144.
  * [Krishna et al., 2021] Krishna, T., McGuinness, K., and O’Connor, N. (2021).  Evaluating contrastive models for instance-based image retrieval.  In Proceedings of the 2021 International Conference on Multimedia Retrieval, pages 471–475.
  * [Li et al., 2021] Li, F., Li, G., He, X., and Cheng, J. (2021).  Dynamic dual gating neural networks.  2021 IEEE/CVF International Conference on Computer Vision (ICCV), pages 5310–5319.
  * [Lin et al., 2017] Lin, J., Rao, Y., Lu, J., and Zhou, J. (2017).  Runtime neural pruning.  Advances in neural information processing systems, 30.
  * [Liu et al., 2017] Liu, Z., Li, J., Shen, Z., Huang, G., Yan, S., and Zhang, C. (2017).  Learning efficient convolutional networks through network slimming.  In Proceedings of the IEEE international conference on computer vision, pages 2736–2744.
  * [Meng et al., 2020] Meng, Y., Panda, R., Lin, C.-C., Sattigeri, P., Karlinsky, L., Saenko, K., Oliva, A., and Feris, R. (2020).  Adafuse: Adaptive temporal fusion network for efficient action recognition.  In International Conference on Learning Representations.
  * [Misra and Maaten, 2020] Misra, I. and Maaten, L. v. d. (2020).  Self-supervised learning of pretext-invariant representations.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6707–6717.
  * [Oord et al., 2018] Oord, A. v. d., Li, Y., and Vinyals, O. (2018).  Representation learning with contrastive predictive coding.  arXiv preprint arXiv:1807.03748.
  * [Tiwari et al., 2021] Tiwari, R., Bamba, U., Chavan, A., and Gupta, D. K. (2021).  Chipnet: Budget-aware pruning with heaviside continuous approximations.  arXiv preprint arXiv:2102.07156.
  * [Veit and Belongie, 2018] Veit, A. and Belongie, S. (2018).  Convolutional networks with adaptive inference graphs.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 3–18.
  * [Wen et al., 2016] Wen, W., Wu, C., Wang, Y., Chen, Y., and Li, H. (2016).  Learning structured sparsity in deep neural networks.  Advances in neural information processing systems, 29.
  * [Wu et al., 2018] Wu, Z., Xiong, Y., Yu, S., and Lin, D. (2018).  Unsupervised feature learning via non-parametric instance-level discrimination.  arXiv preprint arXiv:1805.01978.
  * [Zbontar et al., 2021] Zbontar, J., Jing, L., Misra, I., LeCun, Y., and Deny, S. (2021).  Barlow twins: Self-supervised learning via redundancy reduction.  In International Conference on Machine Learning, pages 12310–12320. PMLR.