$\displaystyle\quad-\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}\bigg{[}\mathbb{I}_{\\{y=j\\}}\mathrm{logit}_{i}(F;X)\left[O(1)\cdot\psi_{r,j,l}+\mathcal{E}_{5}+\mathcal{E}_{6}\right]\bigg{]}$
$\displaystyle\quad-\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}\bigg{[}\mathbb{I}_{\\{y\neq
i,y\neq
j\\}}\mathrm{logit}_{i}(F;X)\left[\frac{0.4s}{k}\cdot\psi_{r,j,l}+\mathcal{E}_{5}+\mathcal{E}_{6}\right]\bigg{]}$
$\displaystyle=\frac{k-1}{k^{2}}\cdot\left[\frac{0.4s}{k}\cdot\psi_{r,j,l}+\mathcal{E}_{5}+\mathcal{E}_{6}\right]-\frac{1}{k^{2}}\left[\psi_{r,j,l}\cdot
O(1)+\mathcal{E}_{5}+\mathcal{E}_{6}\right]$
$\displaystyle\quad-\frac{k-2}{k^{2}}\left[\frac{0.4s}{k}\cdot\psi_{r,j,l}+\mathcal{E}_{5}+\mathcal{E}_{6}\right],$

where $\frac{1}{k},\frac{1}{k},\frac{k-2}{k}$ is the ratios for each type of
data and at $t=0$, we have $\mathrm{logit}_{i}(F;X)=\frac{1}{k},i\in[k]$
because we initialize $u_{i,r}=0$. Therefore, if we ignore the small term, at
$t=1$, we have

$\displaystyle u_{i,r}^{(1)}$
$\displaystyle\approx\eta_{2}\left(\frac{0.4(k-1)s}{k^{3}}-\frac{O(1)}{k^{2}}-\frac{0.4(k-2)s}{k^{3}}\right)\psi_{r,j,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}$
$\displaystyle\approx\eta_{2}\left(\frac{0.4s}{k^{3}}-\frac{O(1)}{k^{2}}\right)\psi_{r,j,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}<0.$
(16)

Using this weight, we could also obtain the bounds of loss function after the
update of $w_{r},r\in[km]$ (we will show the following inequality in (G.2.3)
after we update $w_{r}$):

$\displaystyle 0\leq 1-\mathrm{logit}_{y}(F;X)$
$\displaystyle\leq\tilde{O}\left(\frac{1}{k}\right),$ $\displaystyle
0\leq\mathrm{logit}_{i}(F;X)$
$\displaystyle\leq\tilde{O}\left(\frac{1}{k}\right),\quad\forall
i\in[k]\setminus y.$

Thus, at $t=2$, we have

$\displaystyle u_{i,r}^{(2)}$
$\displaystyle\geq\eta_{2}\left(\frac{0.4s}{k^{3}}-\frac{O(1)}{k^{2}}\right)\psi_{r,j,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}-\tilde{O}\left(\frac{\eta_{2}}{k^{2}}\right)\psi_{r,j,l}-\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k^{2}},$
$\displaystyle u_{i,r}^{(2)}$
$\displaystyle\leq\eta_{2}\left(\frac{0.4s}{k^{3}}-\frac{O(1)}{k^{2}}\right)\psi_{r,j,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}+\tilde{O}\left(\frac{\eta_{2}}{k^{3}}\right)\psi_{r,j,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k^{2}}.$

So the approximation of $u_{i,r}^{(2)}$ is

$u_{i,r}^{(2)}\approx-\tilde{O}\left(\frac{\eta_{2}}{k^{2}}\right)\psi_{r,j,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}.$

Then for $t>2$, as we continue to train to minimize the loss function,
$1-\mathrm{logit}_{y}(F;X)$ will become smaller and so as
$\mathrm{logit}_{i}(F;X),i\in[k]\setminus y$. So the main term in
$u_{i,r},i\in[k],r\in[km]$ is the term of the first two updates and there is
nearly no order changes on values of weights after the first two step of
gradient descent. Thus, for simplicity of analysis, we could take

$\displaystyle
u_{i,r}^{(t)}\approx-\tilde{O}\left(\frac{\eta_{2}}{k^{2}}\right)\psi_{r,j,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k},\quad\mbox{for
}t\geq 2.$ (17)

Similar to the former case, when $r\in\mathcal{M}_{i,l}^{(0)}$, we have

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}[-\nabla_{u_{i,r}}L(F;X,y)]$
$\displaystyle=\frac{k-1}{k^{2}}\left[\psi_{r,i,l}\cdot
O(1)+\mathcal{E}_{5}+\mathcal{E}_{6}\right]$
$\displaystyle\quad-\frac{k-1}{k^{2}}\left[\frac{0.4s}{k}\cdot\psi_{r,i,l}+\mathcal{E}_{5}+\mathcal{E}_{6}\right]$

Then if we ignore the small term, at $t=1$, we have

$\displaystyle u_{i,r}^{(1)}$
$\displaystyle\approx\eta_{2}\left(\frac{O(1)\cdot(k-1)}{k^{2}}-\frac{0.4s(k-1)}{k^{3}}\right)\psi_{r,i,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}>0.$
(18)

Similar to the former analysis, for simplicity of analysis, we also take that

$\displaystyle
u_{i,r}^{(t)}\approx\tilde{O}\left(\frac{\eta_{2}}{k}\right)\psi_{r,i,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k},\quad\mbox{for
}t\geq 2.$ (19)

####  G.2.2 Finetuning of $w_{r}$ and Proof of Lemma G.1

After the update of $u_{i,r}$, we then finetune $w_{r}$. We have the
gradients:

$\displaystyle-\nabla_{w_{r}}L(F;X,y)$
$\displaystyle=(1-\mathrm{logit}_{y}(F;X))u_{y,r}\sum_{p\in[P]}\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p}\rangle)x_{p}$ $\displaystyle\quad-\sum_{i\in[k]\setminus
y}\mathrm{logit}_{i}(F;X)u_{i,r}\sum_{p\in[P]}\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p}\rangle)x_{p}$
$\displaystyle=\bigg{[}(1-\mathrm{logit}_{y}(F;X))u_{y,r}-\sum_{j\in[k]\setminus
y}\mathrm{logit}_{j}(F;X)u_{j,r}\bigg{]}\sum_{p\in[P]}\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p}\rangle)x_{p}$

##### Diagonal correlations.

For $r\in\mathcal{M}_{i,l}^{(0)}$, as we initialize $w_{r}$ by the pretrained
encoder, we have

$\displaystyle\sum_{p\in[P]}\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p}\rangle)\langle x_{p},v_{i,l}\rangle$
$\displaystyle=\mathbb{I}_{\\{v_{i,l}\in\mathcal{V}(X)\\}}\sum_{p\in\mathcal{P}_{v_{i,l}}(X)}\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p}\rangle)(z_{p}+\gamma+\sigma_{p})$
$\displaystyle\quad+\tilde{O}(\sigma_{0}^{q-1})\cdot(\gamma+\sigma_{p})\cdot(s+1)$
$\displaystyle\quad+\tilde{O}((\sigma_{0}\gamma
k)^{q-1})\cdot(\gamma+\sigma_{p})\cdot P.$

Thus,

$\displaystyle\langle-\nabla_{w_{r}}L(F;X,y),v_{i,l}\rangle$
$\displaystyle=(V_{r,i,l}+\mathcal{E}_{1}+\mathcal{E}_{2})\bigg{[}(1-\mathrm{logit}_{y}(F;X))u_{y,r}-\sum_{j\in[k]\setminus
y}\mathrm{logit}_{j}(F;X)u_{j,r}\bigg{]}.$ (20)

At $t=1$, for every $(X,y)\sim\mathcal{Z}_{\mathrm{down}}$, when $i=y$, put
(G.2.1) and (18) into (20), we have

$\displaystyle\langle-\nabla_{w_{r}}L(F;X,y),v_{i,l}\rangle$
$\displaystyle=\eta_{2}\left(\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\right)(V_{r,i,l}+\mathcal{E}_{1}+\mathcal{E}_{2})(1-\mathrm{logit}_{y}(F;X))\psi_{r,i,l}$
$\displaystyle\quad+(V_{r,i,l}+\mathcal{E}_{1}+\mathcal{E}_{2})\cdot\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}$

Similarly, when $y\neq i$,

$\displaystyle\langle-\nabla_{w_{r}}L(F;X,y),v_{i,l}\rangle$
$\displaystyle=\eta_{2}\left(-\frac{O(1)}{k}+\frac{0.4s}{k^{2}}\right)(V_{r,i,l}+\mathcal{E}_{1}+\mathcal{E}_{2})\mathrm{logit}_{i}(F;X)\psi_{r,i,l}$
$\displaystyle\quad+(V_{r,i,l}+\mathcal{E}_{1}+\mathcal{E}_{2})\cdot\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}$

Denote $S_{i,l}=\sum_{p\in\mathcal{P}_{v_{i,l}}(X)}z_{p}$. We have

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}[\langle-\nabla_{w_{r}}L(F;X,y),v_{i,l}\rangle]$
$\displaystyle=\frac{1}{k}\eta_{2}\left(\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\right)S_{i,l}\frac{k-1}{k}\psi_{r,i,l}$
$\displaystyle\quad+\frac{k-1}{k}\eta_{2}\left(-\frac{O(1)}{k}+\frac{0.4s}{k^{2}}\right)S_{i,l}\frac{s}{k^{2}}\psi_{r,i,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}$
$\displaystyle=\left(\frac{k-1}{k^{2}}-\frac{(k-1)s}{k^{3}}\right)\eta_{2}\left(\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\right)S_{i,l}\psi_{r,i,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}.$

Thus, at $t=1$, we have

$\displaystyle\langle w_{r}^{(1)},v_{i,l}\rangle$ $\displaystyle=\langle
w_{r}^{(0)},v_{i,l}\rangle+O\left(\frac{\eta_{1}\eta_{2}}{k^{2}}\right)\psi_{r,i,l}+\frac{\eta_{1}\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}$
(21)
$\displaystyle\leq\Lambda_{i,l}^{(T)}+O\left(\frac{\eta_{1}\eta_{2}}{k^{2}}\right)\Lambda_{i,l}^{(T)}+\frac{\eta_{1}\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}\leq\tilde{O}(1),$

when $\eta_{1}\eta_{2}\leq\tilde{O}(k^{2})$. The lower bound on $\langle
w_{r}^{(1)},v_{i,l}\rangle$ can be easily obtained by similar methods.

Besides, for $t>1$, for every $(X,y)\sim\mathcal{Z}_{\mathrm{down}}$, when
$i=y$, putting (17) and (19) into (20) and keeping the main term, we have

$\displaystyle\langle-\nabla_{w_{r}}L(F;X,y),v_{i,l}\rangle$
$\displaystyle\approx\tilde{O}\left(\frac{\eta_{2}}{k}\right)(V_{r,i,l}+\mathcal{E}_{1}+\mathcal{E}_{2})(1-\mathrm{logit}_{y}(F;X))\psi_{r,i,l}$
$\displaystyle\quad+(V_{r,i,l}+\mathcal{E}_{1}+\mathcal{E}_{2})\cdot\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}$

Similarly, when $y\neq i$,

$\displaystyle\langle-\nabla_{w_{r}}L(F;X,y),v_{i,l}\rangle$
$\displaystyle\approx-\tilde{O}\left(\frac{\eta_{2}}{k}\right)(V_{r,i,l}+\mathcal{E}_{1}+\mathcal{E}_{2})\mathrm{logit}_{i}(F;X)\psi_{r,i,l}$
$\displaystyle\quad+(V_{r,i,l}+\mathcal{E}_{1}+\mathcal{E}_{2})\cdot\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}$

Suppose induction hypothesis C.3 holds at time $t$. Now we have that

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down},m}}$
$\displaystyle[\langle-\nabla_{w_{r}}L(F;X,y),v_{i,l}\rangle]$
$\displaystyle\overset{(a)}{\geq}\tilde{O}\left(\frac{\eta_{2}}{k}\right)\psi_{r,i,l}\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down},m}}\bigg{[}\mathbb{I}_{\\{y=i\\}}(1-\mathrm{logit}_{y}(F;X))$
$\displaystyle\quad-0.4\mathbb{I}_{\\{y\neq
i\\}}\mathrm{logit}_{i}(F;X)\bigg{]}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}.$

where (a) is because for $y\neq i$,
$V_{r,i,l}=0.4\mathbb{I}_{\\{v_{i,l}\in\mathcal{V}(X)\\}}\leq 0.4$, and

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down},s}}$
$\displaystyle[\langle-\nabla_{w_{r}}L(F;X,y),v_{i,\hat{l}}\rangle]$
$\displaystyle\overset{(a)}{\geq}\tilde{O}\left(\frac{\eta_{2}}{k}\right)\psi_{r,i,\hat{l}}\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down},s}}\bigg{[}\mathbb{I}_{\\{y=i\\}}(1-\mathrm{logit}_{y}(F;X))$
$\displaystyle\quad-0.4\mathbb{I}_{\\{y\neq
i\\}}\mathrm{logit}_{i}(F;X)\bigg{]}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}.$

Thus, using the result $\psi_{r,i,l}\geq\frac{1}{\mathrm{polylog}(k)}$, we
obtain

$\displaystyle\sum_{i\in[k]}$ $\displaystyle\langle
w_{r}^{(t+1)},v_{i,l}\rangle\geq\sum_{i\in[k]}\langle
w_{r}^{(t)},v_{i,l}\rangle+\tilde{\Omega}\left(\frac{\eta_{1}\eta_{2}}{k}\right)\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}\bigg{[}(1-\mathrm{logit}_{y}(F;X))\bigg{]}+\eta_{1}\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6}).$

As the induction hypothesis C.3 still holds in the training process, we have
$\Lambda_{i,l}^{(t)}\leq\tilde{O}(1)$. Thus,

$\displaystyle\sum_{t=1}^{T_{\mathrm{down}}}\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}\bigg{[}(1-\mathrm{logit}_{y}(F;X))\bigg{]}+\tilde{O}\bigg{(}{kT_{\mathrm{down}}(\mathcal{E}_{5}+\mathcal{E}_{6})}\bigg{)}\leq\tilde{O}\left(\frac{k^{2}}{\eta_{1}\eta_{2}}\right).$
(22)

So, if we assume induction hypothesis C.3 holds for all iteration $<t$, then

$\displaystyle\langle w_{r}^{(t)},v_{i,l}\rangle$ $\displaystyle\leq\langle
w_{r}^{(1)},v_{i,l}\rangle+\tilde{O}\left(\frac{\eta_{1}\eta_{2}}{k^{2}}\right)\sum_{t=1}^{t}\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}\bigg{[}(1-\mathrm{logit}_{y}(F;X))\bigg{]}$
$\displaystyle\quad+\frac{t\eta_{1}\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}\leq\tilde{O}(1).$

##### Off-diagonal correlations.

For $r\in\mathcal{M}_{i,l}^{(0)}$, as we initialize $w_{r}$ by the pretrained
encoder, we have

$\displaystyle\sum_{p\in[P]}\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p}\rangle)\langle x_{p},v_{j,l^{\prime}}\rangle$
$\displaystyle=\hat{V}_{r,i,l}(X)(\gamma+\sigma_{p})+\mathbb{I}_{\\{v_{j,l^{\prime}}\in\mathcal{V}(X)\\}}\tilde{O}(\sigma_{0}^{q-1})+\mathcal{E}_{1}+\mathcal{E}_{2}.$

Thus,

$\displaystyle\langle-\nabla_{w_{r}}L(F;X,y),v_{j,l^{\prime}}\rangle$
$\displaystyle=(\hat{V}_{r,i,l}(X)(\gamma+\sigma_{p})+\mathbb{I}_{\\{v_{j,l^{\prime}}\in\mathcal{V}(X)\\}}\tilde{O}(\sigma_{0}^{q-1})+\mathcal{E}_{1}+\mathcal{E}_{2})$
$\displaystyle\quad\times\bigg{[}(1-\mathrm{logit}_{y}(F;X))u_{y,r}-\sum_{j\in[k]\setminus
y}\mathrm{logit}_{j}(F;X)u_{j,r}\bigg{]}.$ (23)

At $t=1$, for every $(X,y)\sim\mathcal{Z}_{\mathrm{down}}$, when $i=y$, put
(G.2.1) and (18) into (G.2.2), we have

$\displaystyle\langle-\nabla_{w_{r}}L(F;X,y),v_{j,l^{\prime}}\rangle$
$\displaystyle=((\gamma+\sigma_{p})+\mathbb{I}_{\\{v_{j,l^{\prime}}\in\mathcal{V}(X)\\}}\tilde{O}(\sigma_{0}^{q-1}))$
$\displaystyle\quad\times\left(\eta_{2}\left(\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\right)(1-\mathrm{logit}_{y}(F;X))\psi_{r,i,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}\right)$

Similarly, when $y\neq i$ but $y=j$,

$\displaystyle\langle-\nabla_{w_{r}}L(F;X,y),v_{j,l}\rangle$
$\displaystyle=\left(\mathbb{I}_{\\{v_{i,l}\in\mathcal{V}(X)\\}}(\gamma+\sigma_{p})+\tilde{O}(\sigma_{0}^{q-1})+\mathcal{E}_{1}+\mathcal{E}_{2}\right)$
$\displaystyle\quad\times\bigg{(}\eta_{2}\left(-\frac{O(1)}{k}+\frac{0.4s}{k^{2}}\right)\mathrm{logit}_{i}(F;X)\psi_{r,i,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}\bigg{)}.$

When $y\neq i$ and $y\neq j$,

$\displaystyle\langle-\nabla_{w_{r}}L(F;X,y),v_{j,l}\rangle$
$\displaystyle=\left(\mathbb{I}_{\\{v_{i,l}\in\mathcal{V}(X)\\}}(\gamma+\sigma_{p})+\mathbb{I}_{\\{v_{j,l^{\prime}}\in\mathcal{V}(X)\\}}\tilde{O}(\sigma_{0}^{q-1})+\mathcal{E}_{1}+\mathcal{E}_{2}\right)$
$\displaystyle\quad\times\bigg{(}\eta_{2}\left(-\frac{O(1)}{k}+\frac{0.4s}{k^{2}}\right)\mathrm{logit}_{i}(F;X)\psi_{r,i,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}\bigg{)}.$

Therefore,

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}$
$\displaystyle[\langle-\nabla_{w_{r}}L(F;X,y),v_{j,l^{\prime}}\rangle]$
$\displaystyle=\frac{1}{k}((\gamma+\sigma_{p})+\tilde{O}(s\sigma_{0}^{q-1}/k))\eta_{2}\left(\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\right)\frac{k-1}{k}\psi_{r,i,l}$
$\displaystyle\quad+\frac{1}{k}\left(\frac{s}{k}(\gamma+\sigma_{p})+\tilde{O}(\sigma_{0}^{q-1})\right)\eta_{2}\left(-\frac{O(1)}{k}+\frac{0.4s}{k^{2}}\right)\frac{1}{k}\psi_{r,i,l}$
$\displaystyle\quad+\frac{k-2}{k}\left(\frac{s}{k}(\gamma+\sigma_{p})+\tilde{O}(s\sigma_{0}^{q-1}/k)\right)\eta_{2}\left(-\frac{O(1)}{k}+\frac{0.4s}{k^{2}}\right)\frac{1}{k}\psi_{r,i,l}$
$\displaystyle\quad+\frac{\eta_{2}(\gamma+\sigma_{p})(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}$
$\displaystyle=-\frac{s}{k}((\gamma+\sigma_{p})+\tilde{O}(\sigma_{0}^{q-1}))\eta_{2}\left(\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\right)\psi_{r,i,l}+\frac{\eta_{2}(\gamma+\sigma_{p})(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}.$

Thus, at $t=1$, we have

$\displaystyle\langle$ $\displaystyle
w_{r}^{(1)},v_{j,l^{\prime}}\rangle\leq\langle
w_{r}^{(0)},v_{j,l^{\prime}}\rangle+\tilde{O}\left(\frac{\eta_{1}\eta_{2}}{k^{2}}(\gamma+\sigma_{p})\right)\psi_{r,i,l}+\frac{\eta_{1}\eta_{2}(\gamma+\sigma_{p})(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}\leq\tilde{O}(\sigma_{0}),$

when $\eta_{1}\eta_{2}\leq\tilde{O}(k^{2})$. Suppose induction hypothesis C.3
holds for all iterations $<t$. We have

$\displaystyle\langle w_{r}^{(t)},v_{j,l^{\prime}}\rangle$
$\displaystyle\leq\langle
w_{r}^{(1)},v_{j,l^{\prime}}\rangle+\tilde{O}\left(\frac{\eta_{1}\eta_{2}}{k^{2}}(\gamma+\sigma_{p})\right)\sum_{t=1}^{T_{\mathrm{down}}}\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}\bigg{[}(1-\mathrm{logit}_{y}(F;X))\bigg{]}$
$\displaystyle\quad+\frac{T_{\mathrm{down}}\eta_{1}\eta_{2}(\gamma+\sigma_{p})(\mathcal{E}_{5}+\mathcal{E}_{6})}{k}\leq\tilde{O}(\sigma_{0})$

##### Kernels outside $\cup_{i\in[k],l\in[2]}\mathcal{M}_{i,l}^{(0)}$.

For $r\notin\mathcal{M}_{i,l}^{(0)}$, as we initialize $w_{r}$ by the
pretrained encoder, we have

$\displaystyle\sum_{p\in[P]}\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p}\rangle)\langle x_{p},v_{i,l}\rangle$
$\displaystyle=\tilde{O}(\sigma_{0}^{q-1})+\mathcal{E}_{1}+\mathcal{E}_{2},$

which is very small and there is nearly no increase on $\langle
w_{r},v_{i,l}\rangle$. Thus, when induction hypothesis C.3 holds for all
iterations $<t$, for $r\notin\mathcal{M}_{i,l}^{(0)}$, we have $\langle
w_{r}^{(t)},v_{i,l}\rangle\leq\tilde{O}(\sigma_{0})$.

##### Noise correlations.

For every $r\in[km]$, for every $(X^{*},y^{*})\in\mathcal{Z}$ and every
$p^{*}\in[P]$, we have that

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}}\left[\mathbb{I}_{X=X^{*}}\langle-\nabla_{w_{r}}L(F;X,y),\xi_{p^{*}}\rangle\right]=\tilde{\Theta}\big{(}\frac{1}{N_{2}}\big{)}\mathbb{E}_{(X,y)\sim\mathcal{Z}}\bigg{[}(\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p^{*}}\rangle\pm o(1/\sqrt{d}))$
$\displaystyle\quad\times\Big{[}(1-\mathrm{logit}_{y}(F;X^{*}))u_{y,r}-\sum_{j\in[k]\setminus
y}\mathrm{logit}_{j}(F;X^{*})u_{j,r}\Big{]}\bigg{]},$

and

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}}\left[\mathbb{I}_{X\neq
X^{*}}\langle-\nabla_{w_{r}}L(F;X,y),\xi_{p^{*}}\rangle\right]=\pm
o(1/\sqrt{d}).$

For every $v_{i,l}\in\mathcal{V}$, for every $r\in\mathcal{M}_{i,l}^{(0)}$,
for every $p^{*}\in\mathcal{P}_{v_{i,l}}(X^{*})$, when $i=y$, we have

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}}$
$\displaystyle[\mathbb{I}_{\\{i=y\\}}\langle-\nabla_{w_{r}}L(F;X,y),\xi_{p^{*}}\rangle]$
$\displaystyle=\tilde{\Theta}\big{(}\frac{\eta_{2}}{N_{2}}\big{)}\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p^{*}}\rangle)\left(\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\right)(1-\mathrm{logit}_{y}(F;X^{*}))\psi_{r,i,l}\pm
o(1/\sqrt{d})$
$\displaystyle\overset{(a)}{=}\tilde{\Theta}\big{(}\frac{\eta_{2}}{N_{2}}\big{)}\left(\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\right)\psi_{r,i,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{N_{2}k}\pm
o(\eta_{2}/\sqrt{d}),$

where $(a)$ is because $1-\mathrm{logit}_{y}(F;X^{*})=\frac{k-1}{k}$ at $t=0$.
When $i\neq y$, we have

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}}$
$\displaystyle[\mathbb{I}_{\\{i\neq
y\\}}\langle-\nabla_{w_{r}}L(F;X,y),\xi_{p^{*}}\rangle]$
$\displaystyle=\tilde{\Theta}\big{(}\frac{1}{(k-1)N_{2}}\big{)}\eta_{2}\left(-\frac{O(1)}{k}+\frac{0.4s}{k^{2}}\right)\psi_{r,i,l}+\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{N_{2}k(k-1)}\pm
o(\eta_{2}/\sqrt{d}),$

Thus, we have

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}}\left[\langle-\nabla_{w_{r}}L(F;X,y),\xi_{p^{*}}\rangle\right]=\frac{\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{N_{2}k^{2}}\pm
o(\eta_{2}/\sqrt{d}),$

and

$\displaystyle\langle w_{r}^{(1)},\xi_{p}\rangle=\langle
w_{r}^{(0)},\xi_{p}\rangle+\frac{\eta_{1}\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{N_{2}k^{2}}\pm
o(\eta_{1}\eta_{2}/\sqrt{d})\leq\tilde{o}(\sigma_{0}).$

Thus, when induction hypothesis C.3 holds for all iterations $<t$, we have

$\displaystyle\langle w_{r}^{(t)},\xi_{p}\rangle\leq\langle
w_{r}^{(1)},\xi_{p}\rangle+\frac{T_{\mathrm{down}}\eta_{1}\eta_{2}(\mathcal{E}_{5}+\mathcal{E}_{6})}{N_{2}k^{2}}\pm
o(T_{\mathrm{down}}\eta_{1}\eta_{2}/\sqrt{d})\leq\tilde{o}(\sigma_{0}).$

Similarly, following the similar step as in the proof of Lemma F.6, we can
also prove other claims about the noise correlations in the downstream tasks.
We skip the similar steps here.

Combining all above results, we can prove the Lemma G.1.

####  G.2.3 Training Loss and Proof of Theorem G.2 (a)

We set $\eta_{2}$ to be $O(k)$. The reason why we set the step size to $O(k)$
is in the first step, the weights of negative parts $(<0)$ and positive parts
$(>0)$ is well separated. Thus, by setting a suitable step length
$\eta_{2}=O(k)$, we can obtain a small loss in the first update of (G.1). We
will show that the training loss is small in the following.

After one-step training, at $t=1$, for
$(X,y)\in\mathcal{Z}_{\mathrm{down},m}$, we have

$\displaystyle F_{j}(X)-F_{y}(X)$
$\displaystyle=\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{j,l}^{(0)}}(u_{j,r}-u_{y,r})\Big{(}\psi_{r,j,l}\cdot
Z_{j,l}(X)+\mathcal{E}_{5}+\mathcal{E}_{6}\Big{)}+\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{y,l}^{(0)}}(u_{j,r}-u_{y,r})\Big{(}\psi_{r,y,l}\cdot
Z_{y,l}(X)+\mathcal{E}_{5}+\mathcal{E}_{6}\Big{)}$
$\displaystyle\quad+\sum_{i\in[k]\setminus\\{j,y\\},l\in[2]}\sum_{r\in\mathcal{M}_{i,l}^{(0)}}(u_{j,r}-u_{y,r})\Big{(}\psi_{r,v^{\prime}}\cdot
Z_{v^{\prime}}(X)+\mathcal{E}_{5}+\mathcal{E}_{6}\Big{)}$
$\displaystyle\overset{(a)}{=}\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{j,l}^{(0)}}(u_{j,r}-u_{y,r})\Big{(}\psi_{r,j,l}\cdot
Z_{j,l}(X)+\mathcal{E}_{5}+\mathcal{E}_{6}\Big{)}+\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{y,l}^{(0)}}(u_{j,r}-u_{y,r})\Big{(}\psi_{r,y,l}\cdot
Z_{y,l}(X)+\mathcal{E}_{5}+\mathcal{E}_{6}\Big{)}$
$\displaystyle\quad+\eta_{2}m_{0}(\mathcal{E}_{5}+\mathcal{E}_{6})$
$\displaystyle=\eta_{2}\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{j,l}^{(0)}}\left(\frac{O(1)\cdot(k-1)}{k^{2}}-\frac{0.4s(k-1)}{k^{3}}-\frac{0.4s}{k^{3}}+\frac{O(1)}{k^{2}}\right)\Big{(}\psi_{r,j,l}^{2}\cdot
Z_{j,l}(X)\Big{)}$
$\displaystyle\quad+\eta_{2}\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{y,l}^{(0)}}\left(\frac{0.4s}{k^{3}}-\frac{O(1)}{k^{2}}-\frac{O(1)\cdot(k-1)}{k^{2}}+\frac{0.4s(k-1)}{k^{3}}\right)\Big{(}\psi_{r,y,l}^{2}\cdot
Z_{y,l}(X)\Big{)}+\eta_{2}m_{0}(\mathcal{E}_{5}+\mathcal{E}_{6})$
$\displaystyle=\eta_{2}\Big{(}\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\Big{)}\left(\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{j,l}^{(0)}}\psi_{r,j,l}^{2}\cdot
Z_{j,l}(X)-\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{y,l}^{(0)}}\psi_{r,y,l}^{2}\cdot
Z_{y,l}(X)\right)+\eta_{2}m_{0}(\mathcal{E}_{5}+\mathcal{E}_{6})$
$\displaystyle=\eta_{2}\bigg{(}\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\bigg{)}\left(0.4\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{j,l}^{(0)}}\mathbb{I}_{\\{v_{j,l}\in\mathcal{V}(X)\\}}\psi_{r,j,l}^{2}-\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{y,l}^{(0)}}\psi_{r,y,l}^{2}\right)+\eta_{2}m_{0}(\mathcal{E}_{5}+\mathcal{E}_{6}),$

where (a) is because the third term is nearly zero. We could show the similar
result for single-view data. At $t=1$, for
$(X,y)\in\mathcal{Z}_{\mathrm{down},s}$, we have

$\displaystyle F_{j}(X)-F_{y}(X)$
$\displaystyle=\eta_{2}\bigg{(}\frac{O(1)}{k}-\frac{0.4s}{k^{2}}\bigg{)}\bigg{(}0.4\sum_{l=1}^{2}\sum_{r\in\mathcal{M}_{j,l}^{(0)}}\mathbb{I}_{\\{v_{j,l}\in\mathcal{V}(X)\\}}\psi_{r,j,l}^{2}-\sum_{r\in\mathcal{M}_{y,\hat{l}}^{(0)}}\psi_{r,y,\hat{l}}^{2}$
$\displaystyle\quad-\rho\sum_{r\in\mathcal{M}_{y,3-\hat{l}}^{(0)}}\psi_{r,y,3-\hat{l}}^{2}\bigg{)}+\eta_{2}m_{0}(\mathcal{E}_{5}+\mathcal{E}_{6}).$

Thus, at $t=1$, we have

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down},m}}\left[\mathrm{logit}_{y}(F;X)\right]$
$\displaystyle\approx\bigg{[}\Big{(}\frac{2s}{k}-\frac{2s^{2}}{k^{2}}\Big{)}\frac{1}{1+\sum_{i\in[k]\setminus
y}e^{0.4\Psi_{i,l}-\Psi_{y}}}+\frac{s^{2}}{k^{2}}\frac{1}{1+\sum_{i\in[k]\setminus
y}e^{0.4\Psi_{i}-\Psi_{y}}}$
$\displaystyle\quad+\Big{(}1-\frac{s}{k}\Big{)}^{2}\frac{1}{1+\sum_{i\in[k]\setminus
y}e^{0.4s/k-\Psi_{y}}}\bigg{]}$ $\displaystyle\geq
1-\tilde{O}\Big{(}\frac{1}{k}\Big{)},$ (24)

where the last inequality using the result that
$\psi_{r,i,l}\geq\frac{1}{\mathrm{polylog}(k)}$ and
$\psi_{r,i,l}\leq\tilde{O}(1)$ from Lemma F.1 at initialization,
$|\mathcal{M}_{i,l}^{0}|\leq O(\log^{5}k)$ from Lemma C.1. We could obtain the
similar results for single-view data.

Finally, if we set
$T_{\mathrm{down}}\geq\frac{\mathrm{poly}(k)}{\eta_{1}\eta_{2}}$, according to
(22), it is easy to verify that

$\displaystyle\frac{1}{T_{\mathrm{down}}}\sum_{t=1}^{T_{\mathrm{down}}}\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}\left[-\log\frac{e^{F_{y}(X)}}{\sum_{j\in[k]}e^{F_{j}(X)}}\right]$
$\displaystyle\leq\frac{1}{T_{\mathrm{down}}}\sum_{t_{1}=1}^{T_{\mathrm{down}}}\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}\left[1-\mathrm{logit}_{y}(F;X)\right]$
$\displaystyle\leq\frac{1}{\mathrm{poly}(k)}.$

This implies that the training loss is small and so we prove Theorem G.2 (a).

####  G.2.4 Proof of Theorem G.2 (b)

In this subsection, we prove Theorem G.2 (b). For $(X,y)\sim\mathcal{D}_{m}$,
due to our definition of data structure in Definition 1, with probability at
least $1-e^{-\Omega(\log^{2}k)}$, it satisfies that for every
$j\in[k]\setminus y$,

$\displaystyle F_{j}(X)-F_{y}(X)\approx
O(1)\cdot\left(0.4\sum_{l=1}^{2}\mathbb{I}_{\\{v_{j,l}\in\mathcal{V}(X)\\}}\Psi_{j,l}-\sum_{l=1}^{2}\Psi_{y,l}\right).$
(25)

and for $(X,y)\sim\mathcal{D}_{s}$,

$\displaystyle F_{j}(X)-F_{y}(X)\approx
O(1)\cdot\left(0.4\sum_{l=1}^{2}\mathbb{I}_{\\{v_{j,l}\in\mathcal{V}(X)\\}}\Psi_{j,l}-\rho\Psi_{y,3-\hat{l}}-\Psi_{y,\hat{l}}\right).$
(26)

To prove Theorem G.2 (b), we need a lemma:

######  Lemma G.4.

For every $(X,y)\in\mathcal{Z}_{\mathrm{down}}$,

$\displaystyle
1-\mathrm{logit}_{y}(F;X)\leq\tilde{O}\left(\frac{k^{4}}{s^{2}}\right)\cdot\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}[1-\mathrm{logit}_{y}(F;X)].$

(The same also hold with probability $\geq 1-e^{-\Omega(\log^{2}k)}$ for every
$(X,y)\sim\mathcal{D}$ on the left hand side.)

Furthermore, if
$\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}[1-\mathrm{logit}_{y}(F;X)]\leq\frac{1}{k^{5}}$
is sufficiently small, we have for every $j\in[k]\setminus y$,

$\displaystyle F_{j}(X)-F_{y}(X)\leq-\tilde{O}(1).$

###### Proof of Lemma G.4.

The proof of Lemma G.4 for multi-view data has been shown in (Allen-Zhu & Li,
2020, Claim C.16). Now we prove this lemma also holds for single-view data.

For a data point $(X,y)\in\mathcal{Z}_{\mathrm{down},s}$, let us denote by
$\mathcal{H}(X)$ be the set of all $i\in[k]\setminus\\{y\\}$ such that

$\displaystyle\sum_{l\in[2]}\sum_{p\in\mathcal{P}_{v_{i,l}}(X)}z_{p}\geq
0.8-\frac{1}{100\log
k},\quad\sum_{l\in[2]}\sum_{p\in\mathcal{P}_{v_{y,l}}(X)}z_{p}\leq
1+\rho+\frac{1}{100\log k}.$

Now suppose $1-\mathrm{logit}_{y}(F;X)=\zeta(X)$, then using
$\min\\{1,\beta\\}\leq 2\left(1-\frac{1}{1+\beta}\right)$, we have

$\displaystyle\min\Big{\\{}1,\sum_{i\in[k]\setminus\\{y\\}}e^{F_{i}(X)-F_{y}(X)}\Big{\\}}\leq
2\zeta(X).$

By (26) and our definition of $\mathcal{H}(X)$, this implies that

$\displaystyle\min\Big{\\{}1,\sum_{i\in\mathcal{H}(X)}e^{O(1)\cdot(0.4\Psi_{i}-\rho\Psi_{y,3-\hat{l}}-\Psi_{y,\hat{l}})}\Big{\\}}\leq
4\zeta(X)$

Now we define
$\phi=\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down},s}}[1-\mathrm{logit}_{y}(F;X)]$,
then

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down},s}}\left[\min\Big{\\{}1,\sum_{i\in\mathcal{H}(X)}e^{O(1)\cdot(0.4\Psi_{i}-\rho\Psi_{y,3-\hat{l}}-\Psi_{y,\hat{l}})}\Big{\\}}\right]\leq
4\phi$ $\displaystyle\Longrightarrow$
$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down},s}}\left[\sum_{i\in\mathcal{H}(X)}\min\Big{\\{}\frac{1}{k},e^{O(1)\cdot(0.4\Psi_{i}-\rho\Psi_{y,3-\hat{l}}-\Psi_{y,\hat{l}})}\Big{\\}}\right]\leq
4\phi.$

It equals to

$\displaystyle\sum_{j\in[k]}\sum_{i\in[k]}\mathbb{I}_{\\{i\neq
j\\}}\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down},s}}[\mathbb{I}_{\\{j=y\\}}\mathbb{I}_{\\{i\in\mathcal{H}(X)\\}}]\min\Big{\\{}\frac{1}{k},e^{O(1)\cdot(0.4\Psi_{i}-\rho\Psi_{y,3-\hat{l}}-\Psi_{y,\hat{l}})}\Big{\\}}\leq
4\phi.$

Note that for every $i\neq j\in[k]$, the probability of choosing a single-view
sample $(X,y)$ from $\mathcal{Z}_{\mathrm{down},s}$ with $y=j$ and
$i\in\mathcal{H}(X)$ is at least
$\Omega\big{(}\frac{1}{k}\cdot\frac{s^{2}}{k^{2}}\big{)}$. This implies

$\displaystyle\sum_{j\in[k]}\sum_{i\in[k]\setminus
j}\min\Big{\\{}\frac{1}{k},e^{O(1)\cdot(0.4\Psi_{i}-\rho\Psi_{y,3-\hat{l}}-\Psi_{y,\hat{l}})}\Big{\\}}\leq\tilde{O}\Big{(}\frac{k^{3}}{s^{2}}\phi\Big{)}.$

Finally, using $1-\frac{1}{1+\beta}\leq\min\\{1,\beta\\}$, for every
$(X,y)\sim\mathcal{Z}_{\mathrm{down},s}$, we have

$\displaystyle 1-\mathrm{logit}_{y}(F;X)$
$\displaystyle\leq\min\Big{\\{}1,\sum_{i\in[k]\setminus
y}2e^{O(1)\cdot(0.4\Psi_{i}-\rho\Psi_{y,3-\hat{l}}-\Psi_{y,\hat{l}})}\Big{\\}}$
$\displaystyle\leq k\cdot\sum_{i\in[k]\setminus
y}\min\Big{\\{}\frac{1}{k},e^{O(1)\cdot(0.4\Psi_{i}-\rho\Psi_{y,3-\hat{l}}-\Psi_{y,\hat{l}})}\Big{\\}}\leq\tilde{O}\Big{(}\frac{k^{4}}{s^{2}}\phi\Big{)}.$

This implies that when
$\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down},s}}\left[(1-\mathrm{logit}_{y}(F;X))\right]\leq\frac{1}{k^{5}}$,
we have

$\displaystyle
0.4\Psi_{i}-\rho\Psi_{y,3-\hat{l}}-\Psi_{y,\hat{l}}\leq-\tilde{O}(1).$

∎

As we have proved in Section G.2.3 that

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}\left[(1-\mathrm{logit}_{y}(F;X))\right]\leq\frac{1}{\mathrm{poly}(k)},$

We could set
$T_{\mathrm{down}}\geq\tilde{O}\left(\frac{k^{7}}{\eta_{1}\eta_{2}}\right)$
and then based on Lemma G.4, we have

$\displaystyle\Pr_{(X,y)\in\mathcal{D}}\left[F_{y}(X)\geq\max_{j\neq
y}F_{j}(X)+\tilde{O}(1)\right]\geq 1-e^{-\Omega(\log^{2}k)}.$

##  Appendix H Extensions on Other MRP Methods

We have prove that Theorem C.4 holds in the above sections, which means that
under the Teacher-Student Framework, the pretraining phase can capture all
features. In this section, we extend our proof methods to other popular mask-
reconstruction pretraining methods. Here we mainly consider the masked
autoencoder (MAE) structure He et al. (2021). For simplicity of analysis, we
set the weights of the decoder as the copy of encoder weights and add a linear
layer with $b_{i}=c(\theta),i\in[P]$ to finally obtain the recovered patches.
The explicit framework is shown in Fig. 6.

Figure 6: Masked Autoencoder

Denote the position encoding of patch $p$ as
$\mathbf{e}_{p}\in\mathbb{R}^{P}$, where at position $p$ the element equal to
1, otherwise the element equal to 0. Recall that
$\bm{\epsilon}X=(\epsilon_{1}x_{1},\epsilon_{2}x_{2},\ldots,\epsilon_{P}x_{P})$.
Under this framework, the loss function is

$\displaystyle L(H;X,\bm{\epsilon})$
$\displaystyle=\frac{1}{2}\sum_{p\in[P]}\big{\|}x_{p}-c(\theta)\sum_{r\in[km]}w_{r}\overline{\mathrm{ReLU}}(\langle
w_{r},\mathbf{e}_{p}^{T}\bm{\epsilon}X\rangle)\big{\|}_{2}^{2}$
$\displaystyle=\frac{1}{2}\sum_{p\in[P]}\big{\|}x_{p}-c(\theta)\sum_{r\in[km]}w_{r}\overline{\mathrm{ReLU}}(\langle
w_{r},\epsilon_{p}x_{p}\rangle)\big{\|}_{2}^{2}$

and

$\displaystyle L(H;X)=\mathbb{E}_{\bm{\epsilon}}[L(H;X,\bm{\epsilon})]$
$\displaystyle=\frac{1}{2}\sum_{p\in[P]}\big{\|}x_{p}-\sum_{r\in[km]}w_{r}\overline{\mathrm{ReLU}}(\langle
w_{r},x_{p}\rangle)\big{\|}_{2}^{2}$
$\displaystyle\quad+\frac{1}{2}\left(\frac{1-\theta}{\theta}\right)\sum_{p\in[P]}\big{\|}\sum_{r\in[km]}w_{r}\overline{\mathrm{ReLU}}(\langle
w_{r},x_{p}\rangle)\big{\|}_{2}^{2}.$

Denote

$\displaystyle A_{r,p}(X)=\overline{\mathrm{ReLU}}(\langle
w_{r},x_{p}\rangle)+\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p}\rangle)[\langle w_{r},x_{p}\rangle]^{+}.$

We have that

######  Fact 2.2.

Given the data point $(X,y)\in\mathcal{D}$, for every $w_{r},r\in[km]$,

$\displaystyle-\nabla_{w_{r}}L(X)=\sum_{p\in[P]}A_{r,p}\left(x_{p}-\frac{1}{\theta}\sum_{r^{\prime}\in[km]}w_{r^{\prime}}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle)\right).$

To prove that under MAE framework, the pretraining can also capture all
features, we have the same induction hypothesis as Induction Hypothesis C.3
but now the parameter assumption is a little different. Our new assumptions
are shown as follows:

######  Assumption H.1 (Parameter Assumption: MAE framework).

The parameters introduced in the paper need to satisfy the following
conditions:

  * •

$\varrho$ is the threshold for the smoothed ReLU activation. We assume
$\varrho=\frac{1}{\mathrm{polylog}(k)}$.

  * •

$q\geq 4$ and $\sigma_{0}^{q-2}\leq\frac{1}{k}$.

  * •

$\gamma$ controls feature noise.
$\gamma\leq\tilde{O}\left(\frac{\sigma_{0}}{k}\right)$.

  * •

$s$ controls feature sparsity. $s=\Theta(\mathrm{polylog}(k))$.

  * •

$N\geq\tilde{\omega}\Big{(}\frac{k}{\sigma_{0}^{q-1}}\Big{)}$,$\sqrt{d}\geq\tilde{\omega}(k/\sigma_{0}^{q-1})$,
and $P\leq\sigma_{0}^{-q+1/2}$.

  * •

$\mathrm{polylog}(k)\leq m\leq\sqrt{k}$.

  * •

$\eta\geq\frac{1}{k^{q(q-2)}}$ and $\eta\leq\frac{1}{\mathrm{poly}(k)}$.

  * •

$c(\theta)=\frac{1}{\theta}$.

Now we have the following result on the feature learning process of MAE.

######  Theorem H.2 (Feature learning process of MAE).

Suppose Assumption H.1 holds. By running the gradient descent step based on
gradient Fact. 2.2 with learning rate $\eta\leq\frac{1}{\mathrm{poly}(k)}$,
after $T=\frac{\mathrm{poly}(k)}{\eta}$ iterations, for sufficiently large
$k>0$, Induction Hypothesis C.3 holds for all iterations $t=0,1,\ldots,T$ with
high probability.

See its proof in Appendix H.2.5. Similarly, we also have the result about the
performance on downstream classification tasks shown as follows.

######  Theorem H.3 (Performance on downstream classification tasks under MAE
pretraining).

For $N_{2}\geq k$ many samples, setting the learning rate $\eta_{2}=\Theta(k)$
and $\eta_{1}\leq\tilde{\Theta}(k)$, after
$T_{\mathrm{down}}\geq\frac{\mathrm{poly}(k)}{\eta_{1}\eta_{2}}$ many
iterations, with high probability, we have

  * (a)

(training loss is small) for every $(X,y)\in\mathcal{Z}_{\mathrm{down}}$,
i.e.,

$\displaystyle
L_{\mathrm{down}}(F)=\mathbb{E}_{(X,y)\sim\mathcal{Z}_{\mathrm{down}}}[L_{\mathrm{down}}(F;X,y)]\leq\frac{1}{\mathrm{poly}(k)}.$

  * (b)

(test performance is good) for new data point $(X,y)\sim\mathcal{D}$, the test
performance is

$\displaystyle\Pr_{(X,y)\in\mathcal{D}}\left[F_{y}(X)\geq\max_{j\neq
y}F_{j}(X)+\tilde{O}(1)\right]\geq 1-e^{-\Omega(\log^{2}k)}.$

See its proof in Appendix H.2.6. Theorem H.2 guarantees that under MAE
pretraining, the pretrained convolution kernels can capture all discriminative
features in the data and each convolution kernel only grab at most one
discriminative feature. Such a result accords with the result of MRP in
Theorem 1 of the manuscript. Please refer to more detailed discussion and
analysis of Theorem 1 in manuscript. _We also note that the assumptions under
MAE framework are more strict than the assumptions of Teacher-Student
framework. In the assumptions of MAE, we need $q\geq 4$, which means we need
to let the low-magnitude feature noises to be compressed much much smaller in
order that we can separate the true feature from feature noises._ Then Theorem
H.3 shows that as we have captured all features in the MAE pretraining phase,
we can also obtain very high accuracy with high probability in the downstream
classification tasks. Therefore, compared with supervised learning, MAE also
shows better performance on classification downstream task. This result shows
the generality of our analysis framework.

To prove Theorem H.2 and Theorem H.3, we mainly follow the similar framework
used to prove Theorems 1 and Theorem 2 in the manuscript. To begin with, we
first prove some auxiliary theories based on which one can easily prove the
desired results.

###  H.1 Some Results from Induction Hypothesis C.3 under MAE

We first introduce some claims about the terms in the gradients.

######  Claim H.4.

Suppose Assumption H.1 and Induction Hypothesis C.3 holds at iterations $t$.
Then for every $r\in\mathcal{M}_{i,l}^{(0)}$, we have

  * •

if $p\in\mathcal{P}_{v_{i,l}}(X)$,

$\displaystyle
A_{r,p}(X)=\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}\overline{\mathrm{ReLU}}(\langle
w_{r},x_{p}\rangle)+\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}\overline{\mathrm{ReLU}}^{\prime}(\langle
w_{r},x_{p}\rangle)[\langle w_{r},x_{p}\rangle]^{+}.$

  * •

if $p\in\mathcal{P}(X)\setminus\mathcal{P}_{v_{i,l}}(X)$,

$\displaystyle A_{r,p}(X)\approx\tilde{O}(\sigma_{0}^{q}).$

  * •

if $p\in[P]\setminus\mathcal{P}(X)$,

$\displaystyle A_{r,p}(X)\approx\tilde{O}((\sigma_{0}\gamma k)^{q}).$

We also denote

$\displaystyle\Delta_{p}(X)=x_{p}-\frac{1}{\theta}\sum_{r^{\prime}\in[km]}w_{r^{\prime}}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle).$

######  Claim H.5.

Suppose Assumption H.1 and Induction Hypothesis C.3 holds at iterations $t$,

  * •

When $p\in\mathcal{P}_{v_{i,l}}(X)$, we have

$\displaystyle\langle\Delta_{p}(X),v_{i,l}\rangle$
$\displaystyle=z_{p}\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}-\frac{1}{\theta}\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r^{\prime}},v_{i,l}\rangle\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle)-\sum_{r^{\prime}\notin\mathcal{M}_{i,l}^{(0)}}\tilde{O}(\sigma_{0})\tilde{O}(\sigma_{0}^{q})$
$\displaystyle=z_{p}\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}-\frac{1}{\theta}\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r^{\prime}},v_{i,l}\rangle\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle)\pm\tilde{O}(\sigma_{0}^{q-\frac{1}{2}}).$

  * •

When $p\notin\mathcal{P}_{v_{i,l}}(X)$ but
$p\in\mathcal{P}_{v_{j,l^{\prime}}}(X)$ for $v_{j,l^{\prime}}\neq v_{i,l}$, we
have

$\displaystyle\langle\Delta_{p}(X),v_{i,l}\rangle$
$\displaystyle=\gamma\pm\tilde{O}(\sigma_{0}^{q-\frac{1}{2}})\pm\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r^{\prime}},v_{i,l}\rangle\tilde{O}(\sigma_{0}^{q})\pm\sum_{r^{\prime}\in\mathcal{M}_{j,l^{\prime}}^{(0)}}\mathbb{I}_{v_{j,l^{\prime}}\in\mathcal{V}(X)}\tilde{O}(\sigma_{0})\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle).$

  * •

When $p\in[P]\setminus\mathcal{P}(X)$, we have

$\displaystyle\langle\Delta_{p}(X),v_{i,l}\rangle$
$\displaystyle=\gamma\pm\tilde{O}(\sigma_{0}^{q+1}(\gamma
k)^{q})\pm\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r^{\prime}},v_{i,l}\rangle\tilde{O}((\sigma_{0}\gamma k)^{q}).$

Now we have some claims for the gradients. The proof is just based on the
result from Claim H.4 and Claim H.5.

######  Claim H.6.

Suppose Assumption H.1 and Induction Hypothesis C.3 holds at iterations $t$.
Then for every $v_{i,l}\in\mathcal{V}$, for every
$r\in\mathcal{M}_{i,l}^{(0)}$, for every $(X,y)\in\mathcal{Z}$, we have

  * (a)

$\displaystyle-\langle$ $\displaystyle\nabla_{w_{r}}L(X),v_{i,l}\rangle$
$\displaystyle=\sum_{p\in\mathcal{P}_{v_{i,l}}(X)}A_{r,p}\left(z_{p}\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}-\frac{1}{\theta}\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r^{\prime}},v_{i,l}\rangle\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle)\right)$
$\displaystyle\quad\pm\gamma\tilde{O}(\sigma_{0}^{q})\pm\tilde{O}(\sigma_{0}^{2q-1/2})\pm\tilde{O}((\sigma_{0}^{2q+1})(\gamma
k)^{2q})\cdot P$

  * (b)

for $v_{j,l^{\prime}}\neq v_{i,l}$,

$\displaystyle-\langle$
$\displaystyle\nabla_{w_{r}}L(X),v_{j,l^{\prime}}\rangle$
$\displaystyle=\pm\sum_{p\in\mathcal{P}_{v_{i,l}}(X)}A_{r,p}(\gamma+\tilde{O}(\sigma_{0}^{q-\frac{1}{2}}))\pm\gamma\tilde{O}(\sigma_{0}^{q})\pm\tilde{O}(\sigma_{0}^{2q-1/2})\pm\tilde{O}((\sigma_{0}^{2q+1})(\gamma
k)^{2q})\cdot P$
$\displaystyle\quad+\sum_{p\in\mathcal{P}_{v_{j,l^{\prime}}}(X)}\tilde{O}(\sigma_{0}^{q})\left(z_{p}\mathbb{I}_{v_{j,l^{\prime}}\in\mathcal{V}(X)}-\frac{1}{\theta}\sum_{r^{\prime}\in\mathcal{M}_{j,l^{\prime}}^{(0)}}\langle
w_{r^{\prime}},v_{j,l^{\prime}}\rangle\mathbb{I}_{v_{j,l^{\prime}}\in\mathcal{V}(X)}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle)\right).$

##### Intuitions on Claim H.6.

From Claim H.6, we can find that the positive-correlation gradient
$-\langle\nabla_{w_{r}}L(X),v_{i,l}\rangle$ has a non-small term that drive
the correlation between $w_{r}$ and $v_{i,l}$ when
$r\in\mathcal{M}_{i,l}^{(0)}$ to increase during the training courses. How the
correlation increase will be shown in Claim H.7 in the following. On the other
hand, the negative correlations will keep small as the negative-correlation
gradients $-\langle\nabla_{w_{r}}L(X),v_{j,l^{\prime}}\rangle$ always have
small terms. These intuitions are same as the intuitions under Teacher-Student
Framework and thus we could also prove that MAE pretraining could also capture
all features.

Now we have the following claim shows about at which iteration
$\Lambda_{i,l}^{(t)}$ will be greater than $\varrho$.

######  Claim H.7.

Suppose Assumption C.2 holds and induction hypothesis C.3 holds at iteration
$t$. For every $v_{i,l}$, suppose $\Lambda_{i,l}^{(t)}\leq\varrho$. Then we
have

$\displaystyle\Lambda_{i,l}^{(t+1)}\approx\Lambda_{i,l}^{(t)}+\tilde{\Theta}\left(\frac{\eta}{k}\right)\overline{\mathrm{ReLU}}(\langle
w_{r},v_{i,l}\rangle).$

###### Proof of Claim H.7.

Recall that $\Lambda_{i,l}^{(t)}:=\max_{r\in[km]}[\langle
w_{r}^{(t)},v_{i,l}\rangle]^{+}.$ We choose any $r\in[km]$ that makes $\langle
w_{r}^{(t)},v_{i,l}\rangle\geq\tilde{\Omega}(\sigma_{0})$. Now we show the
updates. We know that

$\displaystyle\langle w_{r}^{(t+1)},v_{i,l}\rangle=\langle
w_{r}^{(t)},v_{i,l}\rangle+\eta\mathbb{E}_{(X,y)\sim\mathcal{Z}}\left[\langle-\nabla_{w_{r}}L(X),v_{i,l}\rangle\right]$

Using Claim H.6 and following the similar method in the proof of Claim E.4, we
have

$\displaystyle-\langle\nabla_{w_{r}}L(X),v_{i,l}\rangle$
$\displaystyle=\sum_{p\in\mathcal{P}_{v_{i,l}}(X)}A_{r,p}\left(z_{p}\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}-\frac{1}{\theta}\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r^{\prime}},v_{i,l}\rangle\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle)\right)$
$\displaystyle=\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}\overline{\mathrm{ReLU}}(\langle
w_{r},v_{i,l}\rangle)\left(1-(1/\theta)\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},v_{i,l}\rangle)\langle w_{r^{\prime}},v_{i,l}\rangle\right)$
$\displaystyle\quad\times\sum_{p\in\mathcal{P}_{v_{i,l}}(X)}(1+q)z_{p}^{q+1}.$

As the term
$(1/\theta)\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},v_{i,l}\rangle)\langle w_{r^{\prime}},v_{i,l}\rangle$ is small
at the intial stage compared with the constant 1, we have

$\displaystyle\Lambda_{i,l}^{(t+1)}\approx\Lambda_{i,l}^{(t)}+\tilde{\Theta}\left(\frac{\eta}{k}\right)\overline{\mathrm{ReLU}}(\langle
w_{r},v_{i,l}\rangle).$

∎

Using Claim E.5, and
$\tilde{\Omega}(\sigma_{0})\leq\Lambda_{i,l}^{(0)}\leq\tilde{O}(\sigma_{0})$,
we have the following result:

######  Claim H.8.

Suppose Assumption H.1 holds and Induction Hypothesis C.3 holds for every
iteration. Define
$T_{0}:=\tilde{\Theta}\left(\frac{k}{\eta\sigma_{0}^{q-1}}\right).$ We have
that when $t\geq T_{0}$, it satisfies
$\Lambda_{i,l}^{(t)}\geq\Theta\left(\frac{1}{\mathrm{polylog}(k)}\right)$.

###  H.2 Proof of Theorem H.2

####  H.2.1 Diagonal correlations

######  Lemma H.9.

Suppose Assumption H.1 holds and Induction Hypothesis C.3 holds for all
iterations $<t$. We have

$\displaystyle\forall
v_{i,l}\in\mathcal{V}:\quad\Lambda_{i,l}^{(t)}\leq\min\left\\{\sqrt{\frac{\theta}{|\mathcal{M}_{i,l}^{(0)}|}},\tilde{O}(1)\right\\}.$

###### Proof.

Suppose we are now at some iteration $t>T_{0}$. In this stage,
$\Lambda_{i,l}^{(t)}\geq 1/\mathrm{polylog}(k)$. As
$T_{0}=\tilde{\Theta}\left(\frac{k}{\eta\sigma_{0}^{q-1}}\right)$ and
$\eta\leq\frac{1}{\mathrm{poly}(k)}$, we have

$\displaystyle-\langle\nabla_{w_{r}}L(X),v_{i,l}\rangle$
$\displaystyle=\sum_{p\in\mathcal{P}_{v_{i,l}}(X)}A_{r,p}\left(z_{p}\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}-\frac{1}{\theta}\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r^{\prime}},v_{i,l}\rangle\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle)\right)$
$\displaystyle=\mathbb{I}_{v_{i,l}\in\mathcal{V}(X)}[\langle
w_{r},v_{i,l}\rangle]^{+}\left(1-(1/\theta)\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r^{\prime}},v_{i,l}\rangle^{2}\right)\sum_{p\in\mathcal{P}_{v_{i,l}}(X)}2z_{p}^{2}.$

Then we have

$\displaystyle[\langle w_{r}^{(t+1)},v_{i,l}\rangle]^{+}$
$\displaystyle\leq[\langle
w_{r}^{(t)},v_{i,l}\rangle]^{+}+\tilde{O}\left(\frac{\eta}{k}\right)[\langle
w_{r}^{(t)},v_{i,l}\rangle]^{+}$

Taking the maximum on both side and as we are at $t>T_{0}$, we have

$\displaystyle\max_{r\in\mathcal{M}_{i,l}^{(0)}}[\langle
w_{r}^{(t+1)},v_{i,l}\rangle]^{+}\leq\max_{r\in\mathcal{M}_{i,l}^{(0)}}[\langle
w_{r}^{(t)},v_{i,l}\rangle]^{+}\left(1+\tilde{O}\left(\frac{\eta}{k}\right)\right).$

When $t\leq T=T_{0}+\tilde{O}\big{(}\frac{k}{\eta}\big{)}$, we have

$\displaystyle\Lambda_{i,l}^{(t)}\leq\tilde{O}(1).$

Besides, we also need

$\displaystyle 1-(1/\theta)\sum_{r^{\prime}\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r^{\prime}},v_{i,l}\rangle^{2}\geq 0,$

which means

$\displaystyle\Lambda_{i,l}^{(t)}\leq\sqrt{\frac{\theta}{|\mathcal{M}_{i,l}^{(0)}|}}.$

This condition shows that when
$\Lambda_{i,l}^{(t)}\to\sqrt{\frac{\theta}{|\mathcal{M}_{i,l}^{(0)}|}}$, the
increase on the positive correlations tends to zero and the training process
becomes to converge. ∎

######  Lemma H.10.

Suppose Assumption H.1 holds and Induction Hypothesis C.3 holds for all
iterations $<t$. We have

$\displaystyle\forall v_{i,l}\in\mathcal{V},\forall
r\in\mathcal{M}_{i,l}^{(0)}:\quad\langle
w_{r}^{(t)},v_{i,l}\rangle\geq-\tilde{O}(\sigma_{0}).$

###### Proof.

We start with any iteration $t$ that is $\langle
w_{r}^{(t)},v_{i,l}\rangle\leq-\tilde{\Omega}(\sigma_{0})$ to see how negative
the next iteration will be. Without loss of generality, we consider the case
when $\langle
w_{r}^{(t^{\prime})},v_{i,l}\rangle\leq-\tilde{\Omega}(\sigma_{0})$ holds for
every $t^{\prime}\geq t$. Then based on Claim H.6 and when we assum $\langle
w_{r}^{(t^{\prime})},v_{i,l}\rangle\leq-\tilde{\Omega}(\sigma_{0})$,
$A_{r,p}=0$, we have

$\displaystyle\langle w_{r}^{(t+1)},v_{i,l}\rangle$ $\displaystyle\geq\langle
w_{r}^{(t)},v_{i,l}\rangle-\gamma\tilde{O}(\sigma_{0}^{q})-\tilde{O}(\sigma_{0}^{2q-1/2})-\tilde{O}((\sigma_{0}^{2q+1})(\gamma
k)^{2q})\cdot P.$

When $t\leq T_{0}$, we have

$\displaystyle\langle w_{r}^{(t+1)},v_{i,l}\rangle$ $\displaystyle\geq\langle
w_{r}^{(t)},v_{i,l}\rangle-\gamma\tilde{O}(\sigma_{0}^{q})-\tilde{O}(\sigma_{0}^{2q-1/2})-\tilde{O}((\sigma_{0}^{2q+1})(\gamma
k)^{2q})\cdot P$ $\displaystyle\geq-\tilde{O}(\sigma_{0})-\eta
T_{0}(\gamma\tilde{O}(\sigma_{0}^{q})+\tilde{O}(\sigma_{0}^{2q-1/2})+\tilde{O}((\sigma_{0}^{2q+1})(\gamma
k)^{2q})\cdot P)$ $\displaystyle\geq-\tilde{O}(\sigma_{0}).$

When $t\in[T_{0},T]$, we have

$\displaystyle\langle w_{r}^{(t+1)},v_{i,l}\rangle$ $\displaystyle\geq\langle
w_{r}^{(T_{0})},v_{i,l}\rangle-\eta(\gamma\tilde{O}(\sigma_{0}^{q})+\tilde{O}(\sigma_{0}^{2q-1/2})+\tilde{O}((\sigma_{0}^{2q+1})(\gamma
k)^{2q})\cdot P)$
$\displaystyle\geq-\tilde{O}(\sigma_{0})-\eta(T-T_{0})(\gamma\tilde{O}(\sigma_{0}^{q})+\tilde{O}(\sigma_{0}^{2q-1/2})+\tilde{O}((\sigma_{0}^{2q+1})(\gamma
k)^{2q})\cdot P)$ $\displaystyle\geq-\tilde{O}(\sigma_{0}).$

∎

####  H.2.2 Off-diagonal correlations

######  Lemma H.11.

Suppose Assumption H.1 holds and Induction Hypothesis C.3 holds for all
iterations $<t$. Then

$\displaystyle\forall v_{i,l}\in\mathcal{V},\forall
r\in\mathcal{M}_{i,l}^{(0)},~{}\mbox{for }v_{j,l^{\prime}}\neq
v_{i,l}:\quad|\langle
w_{r}^{(t)},v_{j,l^{\prime}}\rangle|\leq\tilde{O}(\sigma_{0}).$

###### Proof.

Stage I. We first consider the stage when $t\leq T_{0}$. For every
$r\in\mathcal{M}_{i,l}^{(0)}$, using Claim H.6, we have

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}}$
$\displaystyle[-\langle\nabla_{w_{r}}L(X),v_{j,l^{\prime}}\rangle]$
$\displaystyle\leq\mathbb{E}_{(X,y)\sim\mathcal{Z}}\left[\sum_{p\in\mathcal{P}_{v_{i,l}}(X)}A_{r,p}\right](\gamma+\tilde{O}(\sigma_{0}^{q-\frac{1}{2}}))+\gamma\tilde{O}(\sigma_{0}^{q})+\tilde{O}(\sigma_{0}^{2q-1/2})+\tilde{O}((\sigma_{0}^{2q+1})(\gamma
k)^{2q})\cdot P+\tilde{O}(\sigma_{0}^{q})$
$\displaystyle\quad\times\mathbb{E}_{(X,y)\sim\mathcal{Z}}\left[\sum_{p\in\mathcal{P}_{v_{j,l^{\prime}}}(X)}\left(z_{p}\mathbb{I}_{v_{j,l^{\prime}}\in\mathcal{V}(X)}-\frac{1}{\theta}\sum_{r^{\prime}\in\mathcal{M}_{j,l^{\prime}}^{(0)}}\langle
w_{r^{\prime}},v_{j,l^{\prime}}\rangle\mathbb{I}_{v_{j,l^{\prime}}\in\mathcal{V}(X)}\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle)\right)\right]$
$\displaystyle\leq\tilde{\Theta}\left(\frac{1}{k}\right)\overline{\mathrm{ReLU}}(\langle
w_{r},v_{i,l}\rangle)(\gamma+\tilde{O}(\sigma_{0}^{q-\frac{1}{2}}))+\tilde{O}\left(\frac{\sigma_{0}^{q}}{k}\right).$

From Claim H.7, we have that

$\displaystyle\tilde{\Theta}\left(\frac{\eta}{k}\right)\sum_{t=0}^{T_{0}-1}\overline{\mathrm{ReLU}}(\langle
w_{r}^{(t)},v_{i,l}\rangle)=\Lambda_{i,l}^{(T_{0})}-\Lambda_{i,l}^{(0)}\leq\frac{1}{\mathrm{polylog}(k)}.$

Thus, when $t\leq T_{0}$,

$\displaystyle|\langle w_{r}^{(t)},v_{j,l^{\prime}}\rangle|$
$\displaystyle\leq|\langle
w_{r}^{(0)},v_{j,l^{\prime}}\rangle|+\gamma+\tilde{O}(\sigma_{0}^{q-\frac{1}{2}})+T_{0}\tilde{O}\left(\frac{\eta\sigma_{0}^{q}}{k}\right)\leq\tilde{O}(\sigma_{0}).$

Stage II. When $t\in[T_{0},T]$, we have

$\displaystyle|\langle w_{r}^{(t)},v_{j,l^{\prime}}\rangle|$
$\displaystyle\leq|\langle
w_{r}^{(T_{0})},v_{j,l^{\prime}}\rangle|+\tilde{O}\bigg{(}\frac{\eta(T-T_{0})}{k}\bigg{)}\cdot(\overline{\mathrm{ReLU}}(\langle
w_{r},v_{i,l}\rangle)(\gamma+\tilde{O}(\sigma_{0}^{q-\frac{1}{2}}))+\tilde{O}\left(\sigma_{0}^{q}\right))$
$\displaystyle\leq\tilde{O}(\sigma_{0}).$

∎

####  H.2.3 Lottery winning: kernels inside $\mathcal{M}_{i,l}^{(0)}$

######  Lemma H.12.

Suppose Assumption H.1 holds and Induction Hypothesis C.3 holds for all
iterations $<t$. Then

$\displaystyle\forall v_{i,l}\in\mathcal{V},\forall
r\notin\mathcal{M}_{i,l}^{(0)}:\quad\langle
w_{r}^{(t)},v_{i,l}\rangle\leq\tilde{O}(\sigma_{0}).$

###### Proof.

When $r\in\mathcal{M}_{j,l^{\prime}}^{(0)},(v_{j,l^{\prime}}\neq v_{i,l})$, we
have prove that $\langle w_{r}^{(t)},v_{i,l}\rangle\leq\tilde{O}(\sigma_{0})$
in Lemma H.11. So we only prove the case when
$r\notin\cup_{i\in[k],l\in[2]}\mathcal{M}_{i,l}^{(0)}$.

We assume that there exists an
$w_{r^{\prime}}\notin\cup_{i\in[k],l\in[2]}\mathcal{M}_{i,l}^{(0)}$ such that
induction hypothesis C.3 (a)-(c) holds for every $(X,y)\in\mathcal{Z}$. We
want to see if the sequence $\langle w_{r^{\prime}}^{(t)},v_{i,l}\rangle$ will
increase more quickly than $\max_{r\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r}^{(t)},v_{i,l}\rangle$.

Stage I. We first consider when $t\leq T_{0}$. In this stage,
$\Lambda_{i,l}^{(t)}\leq\varrho$. We define two sequences. First, we take
$w_{r^{*}}=\operatorname*{argmax}_{r\in\mathcal{M}_{i,l}^{(0)}}\langle
w_{r}^{(0)},v_{i,l}\rangle$ and define $x_{t}:=\langle
w_{r^{*}}^{(t)},v_{i,l}\rangle\cdot\big{(}\frac{s}{qk}\big{)}^{1/(q-1)}\frac{1}{\varrho}$.
We also define $y_{t}=\max\\{\langle
w_{r^{\prime}}^{(t)},v_{i,l}\rangle\cdot\big{(}\frac{s}{qk}\big{)}^{1/(q-1)}\frac{1}{\varrho},\sigma_{0}\\}$.
From Claim H.7, when $t\leq T_{0}$, we have that

$\displaystyle\langle w_{r^{*}}^{(t+1)},v_{i,l}\rangle$ $\displaystyle=\langle
w_{r^{*}}^{(t)},v_{i,l}\rangle+\Theta\left(\frac{s\eta}{k}\right)\overline{\mathrm{ReLU}}(\langle
w_{r^{*}}^{(t)},v_{i,l}\rangle)$ $\displaystyle\geq\langle
w_{r^{*}}^{(t)},v_{i,l}\rangle+\Theta\left(\frac{s\eta}{k}\right)\frac{1}{q\varrho^{q-1}}([\langle
w_{r^{*}},v_{i,l}\rangle]^{+})^{q}.$

Let $S=\left(\frac{1+C/(\log(k)-C)}{1+1/\log(k)}\right)^{q-2},C>1$. We have

$\displaystyle\langle w_{r^{\prime}}^{(t+1)},v_{i,l}\rangle$
$\displaystyle=\langle
w_{r^{\prime}}^{(t)},v_{i,l}\rangle+\Theta\left(\frac{s\eta}{k}\right)\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}}^{(t)},v_{i,l}\rangle)$ $\displaystyle\leq\langle
w_{r^{\prime}}^{(t)},v_{i,l}\rangle+\Theta\left(\frac{s\eta}{k}\right)\frac{1}{q\varrho^{q-1}}([\langle
w_{r^{\prime}}^{(t)},v_{i,l}\rangle]^{+})^{q}S.$

Then following the same process as the proof of Lemma F.5, we have

$\displaystyle\langle
w_{r^{\prime}}^{(t)},v_{i,l}\rangle\leq\tilde{O}(\sigma_{0}).$

The proof of Stage II is also similar to Lemma F.5. ∎

####  H.2.4 Noise correlation

As our noise correlation result is similar to Lemma F.6, we don’t repeat it
here but just prove it holds under MAE framework and under our new parameter
assumptions.

###### Proof of Lemma F.6 under MAE framework.

For every $r\in[km]$, for every $(X^{*},y^{*})\in\mathcal{Z}$ and every
$p^{*}\in[P]$, we have that

$\displaystyle\langle-\nabla_{w_{r}}$ $\displaystyle
L(X),\xi_{p^{*}}\rangle=\sum_{p\in[P]}A_{r,p}\left(\langle
x_{p},\xi_{p^{*}}\rangle-\frac{1}{\theta}\sum_{r^{\prime}\in[km]}\langle
w_{r^{\prime}},\xi_{p^{*}}\rangle\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p}\rangle)\right).$

When $X\neq X^{*}$, we have $|\langle
x_{p},\xi_{p^{*}}\rangle|\leq\tilde{O}(\sigma_{p})\leq o(1/\sqrt{d})$; and
when $X=X^{*}$ but $p\neq p^{*}$, we have $|\langle
x_{p},\xi_{p^{*}}\rangle|\leq\tilde{O}(\sigma_{p})\leq o(1/\sqrt{d})$.
Therefore, we have

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}}\bigg{[}\langle-\nabla_{w_{r}}L(X),\xi_{p^{*}}\rangle\bigg{]}$
$\displaystyle=\mathbb{E}_{(X,y)\in\mathcal{Z}}\bigg{[}\mathbb{I}_{X=X^{*}}\langle-\nabla_{w_{r}}L(X),\xi_{p^{*}}\rangle+\mathbb{I}_{X\neq
X^{*}}\langle-\nabla_{w_{r}}L(X),\xi_{p^{*}}\rangle\bigg{]}.$

Now we begin to prove (a). For every $v_{i,l}\in\mathcal{V}$, for every
$r\in\mathcal{M}_{i,l}^{(0)}$, for every
$p^{*}\in\mathcal{P}_{v_{i,l}}(X^{*})$, using the induction hypothesis C.3,
when $t\in[0,T_{0}]$, we have that for the first term,

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}}\bigg{[}\mathbb{I}_{X=X^{*}}\langle-\nabla_{w_{r}}L(X),\xi_{p^{*}}\rangle\bigg{]}$
$\displaystyle=\frac{1}{N}\mathbb{E}_{(X^{*},y^{*})\sim\mathcal{Z}}\left[A_{r,p^{*}}\left(\langle
x_{p^{*}},\xi_{p^{*}}\rangle-\frac{1}{\theta}\sum_{r^{\prime}\in[km]}\langle
w_{r^{\prime}},\xi_{p^{*}}\rangle\overline{\mathrm{ReLU}}(\langle
w_{r^{\prime}},x_{p^{*}}\rangle)\right)\pm
o\left(\frac{1}{\sqrt{d}}\right)\pm\tilde{o}(\sigma_{0})\overline{\mathrm{ReLU}}(\Lambda_{i,l}^{(t)})\right]$

For the second term,

$\displaystyle\mathbb{E}_{(X,y)\sim\mathcal{Z}}\bigg{[}\mathbb{I}_{X\neq
X^{*}}\langle-\nabla_{w_{r}}L(X),\xi_{p^{*}}\rangle\bigg{]}$
$\displaystyle=\pm
o\left(\frac{1}{\sqrt{d}}\right)\pm\tilde{o}(\sigma_{0})\overline{\mathrm{ReLU}}(\Lambda_{i,l}^{(t)})$

Thus, we have

$\displaystyle\langle w_{r}^{(t+1)},\xi_{p^{*}}\rangle$
$\displaystyle\leq\langle
w_{r}^{(t)},\xi_{p^{*}}\rangle+\tilde{O}\left(\frac{\eta}{N}\right)\tilde{o}(\sigma_{0})\overline{\mathrm{ReLU}}(\Lambda_{i,l}^{(t)})+o\left(\frac{\eta}{\sqrt{d}}\right)+\tilde{o}(\eta\sigma_{0})\overline{\mathrm{ReLU}}(\Lambda_{i,l}^{(t)}),$

Now we use the results from Lemma H.9, when $t\leq T_{0}$,

$\displaystyle\langle w_{r}^{(t)},\xi_{p^{*}}\rangle$
$\displaystyle\leq\langle
w_{r}^{(t-1)},\xi_{p^{*}}\rangle+\tilde{o}(\eta\sigma_{0})\overline{\mathrm{ReLU}}(\Lambda_{i,l}^{(t)})+o\left(\frac{\eta}{\sqrt{d}}\right)$
$\displaystyle\leq\langle
w_{r}^{(0)},\xi_{p^{*}}\rangle+\tilde{o}(\eta\sigma_{0})\sum_{t=0}^{T_{0}-1}\overline{\mathrm{ReLU}}(\Lambda_{i,l}^{(t)})+o\left(\frac{\eta
T_{0}}{\sqrt{d}}\right)$ $\displaystyle\leq\tilde{o}(\sigma_{0}).$

So when $N\geq\tilde{\omega}\Big{(}\frac{k}{\sigma_{0}^{q-1}}\Big{)}$ and
$\sqrt{d}\geq\tilde{\omega}(k/\sigma_{0}^{q-1})$, we have $\langle
w_{r}^{(t)},\xi_{p^{*}}\rangle\leq\tilde{o}(\sigma_{0})$. Therefore, for
$t\in[T_{0},T]$, we have

$\displaystyle\langle w_{r}^{(t)},\xi_{p^{*}}\rangle$
$\displaystyle\leq\langle
w_{r}^{(T_{0})},\xi_{p^{*}}\rangle+\tilde{O}\left(\frac{\eta(t-T_{0})}{N}\right)+o\left(\frac{\eta(t-T_{0})}{\sqrt{d}}\right)\leq\tilde{o}(\sigma_{0}),$

when $\sqrt{d}\geq\tilde{\omega}(k)$. Following the similar process, we could
also prove (b)-(e). ∎

####  H.2.5 Proof of Theorem H.2

Theorem H.2 can be easily obtained following the similar steps in the proof of
Theorem C.4 when we have Lemma H.10-Lemma H.12.

####  H.2.6 Proof of Theorem H.3

Theorem H.3 can be easily obtained following the same steps in the proof of
Theorem G.2 in Section G.

###  H.3 Discussion on BEiT methods

We have proved that the pretraining phase can capture all features both under
Teacher-Student framework and MAE framework. Now we have a discussion on BEiT
framework (Bao et al., 2021). For BEiT, if we regard the pretrained encoder of
BEiT as a fixed teacher and stuck an additional layer to map the patch token
feature of BEiT encoder to discrete pseudo label, then this setting becomes
very similar to our setting. The only different is the BEiT encoder (teacher)
is fixed, while our teacher encoder is learned online (updated along with the
weights of the student). Since there are a lot of similarities between these
two frameworks, our proof methods can naturally extend to BEiT with the
suitable choices of additional layers.