that $\\{Y_{1},\dots,Y_{J}\\}$ is $\varepsilon/4$-sparse. Therefore, the balls
$\mathcal{B}_{M}(Y_{j},\varepsilon/8)$ for $|Y_{j}-Y_{i}|\leq 4h$ are pairwise
distincts, and are all included in
$\mathcal{B}_{M}(Y_{i},4h+\varepsilon/8)\subset\mathcal{B}_{M}(Y_{i},5h)$. We
conclude by Lemma A.1(iii). Letting $N(z,2h)$ be the number of points $Y_{i}$
belonging to $\mathcal{B}_{M}(z,2h)$, we obtain

$\displaystyle|\phi(\hat{\Psi}_{j}\circ S_{j}(z))-\phi^{\prime}(z)|$
$\displaystyle\lesssim\frac{1}{n}\sum_{i=1}^{n}\left(|K_{h}(Y_{i}-z)|(\varepsilon^{m}+\gamma)+h^{-d}(\varepsilon^{m}+\gamma)\mathbf{1}\\{Y_{i}\in\mathcal{B}_{M}(z,2h)\\}\right)$
$\displaystyle\lesssim\frac{N(z,2h)}{nh^{d}}(\varepsilon^{m}+\gamma).$

If, for every $z\in M$ and some $\lambda>0$, $N(z,2h)\leq\lambda nh^{d}$, then
we have the conclusion. Let us bound

$P_{0}=\mathbb{P}(\exists z\in M,\ N(z,2h)>\lambda nh^{d}).$

If $N(z,2h)>\lambda nh^{d}$, then there exists a point $Y_{i}$ with
$N(Y_{i},4h)\geq N(z,2h)>\lambda nh^{d}$. Hence, $P_{0}\leq
n\mathbb{P}(N(Y_{1},4h)>\lambda nh^{d})$. Conditionally on $Y_{1}$,
$N(Y_{1},4h)=1+U$ with $U$ a binomial random variable of parameters $n-1$ and
$\mu(\mathcal{B}_{M}(Y_{1},4h))\leq
f_{\max}\mathrm{vol}_{M}(\mathcal{B}_{M}(Y_{1},4h))\lesssim h^{d}$ (see Lemma
A.1(iii)). In particular, for $\lambda$ large enough, the probability $P_{0}$
is smaller than $n^{-k/d}$ by Hoeffding’s inequality. ∎

##  Appendix G Lower bounds on minimax risks

In this section, we prove the different lower bounds on minimax risks stated
in the article. The main tool used will be Assouad’s lemma. Fix as in Section
2.4 a statistical model
$(\mathcal{Y},\mathcal{H},\mathcal{Q},\iota,\vartheta)$, where
$\vartheta:\mathcal{Y}\to(E,\mathcal{L})$ is a measurable function taking its
values in some semi-metric space $(E,\mathcal{L})$.

######  Lemma G.1 (Assouad’s lemma [Yu97]).

Let $m\geq 1$ be an integer and $\mathcal{Q}_{m}=\\{\xi_{\sigma},\
\sigma\in\\{-1,1\\}^{m}\\}\subset\mathcal{Q}$ be a set of probability
measures. Assume that for all $\sigma,\sigma^{\prime}\in\\{-1,1\\}^{m}$,

$\mathcal{L}(\vartheta(\xi_{\sigma}),\vartheta(\xi_{\sigma^{\prime}}))\geq|\sigma-\sigma^{\prime}|\delta,$
(G.1)

where
$|\sigma-\sigma^{\prime}|=\sum_{i=1}^{m}\mathbf{1}\\{\sigma(i)\neq\sigma^{\prime}(i)\\}$
is the Hamming distance between $\sigma$ and $\sigma^{\prime}$. Then,

$\mathcal{R}_{n}(\vartheta,\mathcal{Q},\mathcal{L})\geq
m\frac{\delta}{16}\left(1-\max\left\\{TV(\iota_{\\#}\xi_{\sigma},\iota_{\\#}\xi_{\sigma^{\prime}}),\
|\sigma-\sigma^{\prime}|=1\right\\}\right)^{2n}.$ (G.2)

The lower bound on the minimax rates we prove are actually going to hold on
the smaller model of uniform distributions on manifolds.

######  Definition G.2.

Let $k\geq 2$ and $\gamma\geq 0$. The set $\mathcal{Q}^{k}_{d}(\gamma)$ is the
set of probability distributions $\xi$ of random variables $(Y,Z)$, where $Y$
follows the uniform distribution on some manifold $M\in\mathcal{M}^{k}_{d}$
with $f_{\max}^{-1}\leq|\mathrm{vol}_{M}|\leq f_{\min}^{-1}$, and
$Z\in\mathcal{B}(0,\gamma)$ is such that $Z\in T_{Y}M^{\bot}$. The statistical
model is completed by letting $(\mathcal{Y},\mathcal{H})$ be
$\mathbb{R}^{D}\times\mathbb{R}^{D}$ endowed with its Borel $\sigma$-algebra,
$\iota$ be the addition $\mathbb{R}^{D}\times\mathbb{R}^{D}\to\mathbb{R}^{D}$
and $\vartheta(\xi)$ be the first marginal $\mu$ of $\xi$.

We write $\mathcal{Q}^{k}_{d}$ for $\mathcal{Q}^{k}_{d}(0)$. One can check
that $\mathcal{Q}^{k}_{d}(\gamma)\subset\mathcal{Q}^{k,s}_{d}(\gamma)$, with
parameter $L_{s}=f_{\min}^{-1/p}\vee f_{\max}^{1-1/p}$. Therefore, a
lowerbound on the minimax risk on the model $\mathcal{Q}^{k}_{d}(\gamma)$
yields a lowerbound on the minimax risk on the model
$\mathcal{Q}^{k,s}_{d}(\gamma)$ should the parameter $L_{s}$ be large enough.

We build a subfamily of manifolds indexed by $\sigma\in\\{-1,1\\}^{m}$
following [AL19]. By [AL19, Section C.2], there exists a manifold
$M\subset\mathbb{R}^{d+1}$ of reach $2\tau_{\min}$, of volume
$C_{d}\tau_{\min}^{d}$ which contains
$\mathcal{B}_{\mathbb{R}^{d}}(0,\tau_{\min})$. Let $\delta>0$ and consider a
family of $m$ points
$x_{1},\dots,x_{m}\in\mathcal{B}_{\mathbb{R}^{d}}(0,\tau_{\min}/2)$, with
$|x_{i}-x_{i^{\prime}}|\geq 4\delta$ for $i\neq i^{\prime}$ and
$c_{d}(\tau_{\min}/\delta)^{d}\leq m\leq C_{d}(\tau_{\min}/\delta)^{d}$. Let
$0<\Lambda<\delta$ and let $\phi:\mathbb{R}^{d+1}\to[0,1]$ be a smooth radial
function supported on $\mathcal{B}(0,1)$, with $\phi\equiv 1$ on
$\mathcal{B}(0,1/2)$. Let $e$ be the unit vector in the $(d+1)$th direction.
We then let, for $\sigma\in\\{-1,1\\}^{m}$,

$\Phi_{\sigma}^{\Lambda}(x)=x+\sum_{i=1}^{m}\frac{\sigma_{i}+1}{2}\Lambda\phi\left(\frac{x-x_{i}}{\delta}\right)e.$
(G.3)

Let $M_{\sigma}^{\Lambda}=\Phi_{\sigma}^{\Lambda}(M)$ and
$\mu_{\sigma}^{\Lambda}$ be the the uniform measure on $M_{\sigma}^{\Lambda}$.
If $\Lambda\leq c_{k,d,\tau_{\min}}\delta^{k}$, then
$\mu_{\sigma}^{\Lambda}\in\mathcal{Q}^{k}_{d}$, provided that $L_{k}$ is large
enough [AL19, Lemma C.13]. If $\sigma_{i}=1$, the volume of
$\Phi_{\sigma}^{\Lambda}(\mathcal{B}_{\mathbb{R}^{d}}(x_{i},\delta))$
satisfies, with $\omega_{d}$ the volume of the $d$-dimensional unit ball,

$\displaystyle\left|\mathrm{vol}_{M_{\sigma}^{\Lambda}}(\Phi_{\sigma}^{\Lambda}(\mathcal{B}_{\mathbb{R}^{d}}(x_{i},\delta))-\omega_{d}\delta^{d}\right|\leq\int_{\mathcal{B}_{\mathbb{R}^{d}}(x_{i},\delta)}|J\Phi_{\sigma}^{\Lambda}(x)-1|\mathrm{d}x$
$\displaystyle\qquad\leq\int_{\mathcal{B}_{\mathbb{R}^{d}}(x_{i},\delta)}\left|\sqrt{1+\Lambda^{2}\delta^{-2}\left|\nabla\phi\left(\frac{x-x_{i}}{\delta}\right)\right|^{2}}-1\right|\mathrm{d}x\leq
C_{d}\delta^{d}\Lambda^{2}\delta^{-2}.$

Hence, for $\delta$ small enough, we have
$||\mathrm{vol}_{M_{\sigma}^{\Lambda}}|-C_{d}\tau_{\min}^{d}|\leq
mC_{d}\delta^{d}\Lambda^{2}\delta^{-2}\leq C_{d}\tau_{\min}^{d}/3$, as $m\leq
C_{d}(\tau_{\min}/\delta)^{d}$ and $\Lambda\leq
c_{k,d,\tau_{\min}}\delta^{k}$. As a consequence, if
$|\sigma-\sigma^{\prime}|=1$, with for instance $\sigma_{i}=1$ and
$\sigma^{\prime}_{i}=-1$, then

$\displaystyle\operatorname*{TV}(\mu_{\sigma}^{\Lambda},\mu_{\sigma}^{\prime\Lambda})$
$\displaystyle\leq\max(\mu_{\sigma}^{\Lambda}(\Phi_{\sigma}^{\Lambda}(\mathcal{B}_{\mathbb{R}^{d}}(x_{i},\delta))),\mu_{\sigma^{\prime}}^{\Lambda}(\mathcal{B}_{\mathbb{R}^{d}}(x_{i},\delta))\leq
C_{d,\tau_{\min}}\delta^{d}.$ (G.4)

We may now prove the different minimax lower bounds using Assouad’s Lemma on
the family $\\{\mu_{\sigma}^{\Lambda},\ \sigma\in\\{-1,1\\}^{m}\\}$.

###### Proof of Theorem 2.13.

As $g$ is nondecreasing and convex, by Jensen’s inequality, we may assume
without loss of generality that $\mathcal{L}=\operatorname*{TV}$. Let
$\Gamma=|(\mu_{\sigma}^{\Lambda}-\mu_{\sigma^{\prime}}^{\Lambda})(B_{i})|$,
where $B_{i}=\mathcal{B}_{\mathbb{R}^{d}}(x_{i},\delta)$ and
$\sigma(i)\neq\sigma^{\prime}(i)$. Then,
$\operatorname*{TV}(\mu_{\sigma}^{\Lambda},\mu_{\sigma^{\prime}}^{\Lambda})\geq|\sigma-\sigma^{\prime}|\Gamma$.
Furthermore, if for instance $\sigma^{\prime}(i)=1$,
$\Gamma\geq\mu_{\sigma^{\prime}}^{\Lambda}(B_{i})=(\omega_{d}\delta^{d})/|\mathrm{vol}_{M_{\sigma^{\prime}}^{\Lambda}}|\geq
c_{d}\delta^{d}/\tau_{\min}^{d}.$ By Assouad’s Lemma,

$\displaystyle\mathcal{R}_{n}(\mu;\mathcal{Q}^{s,k}_{d};\operatorname*{TV})$
$\displaystyle\geq\mathcal{R}_{n}(\mu;\mathcal{Q}^{k}_{d};\operatorname*{TV})\geq\frac{m}{16}c_{d}\frac{\delta^{d}}{\tau_{\min}^{d}}\left(1-C_{d,\tau_{\min}}\delta^{d}\right)^{2n}\geq
C_{d}\left(1-C_{d,\tau_{\min}}\delta^{d}\right)^{2n}.$

We obtain the conclusion by letting $\delta$ go to $0$. ∎

######  Lemma G.3.

For any $\tau_{\min}>0$ and $1\leq r\leq\infty$, for $f_{\min}$ small enough
and $f_{\max}$, $L_{k}$ large enough, one has

$\displaystyle\mathcal{R}_{n}\left(\frac{\mathrm{vol}_{M}}{|\mathrm{vol}_{M}|},\mathcal{Q}^{k}_{d}(\gamma),W_{r}\right)\gtrsim\gamma+n^{-k/d}.$
(G.5)

###### Proof.

As, $W_{r}\geq W_{1}$, we may assume that $r=1$. Let
$\sigma,\sigma^{\prime}\in\\{-1,1\\}^{m}$ with
$\sigma(i)\neq\sigma^{\prime}(i)$. Let
$p_{\sigma(i)}=\mathrm{vol}_{M_{\sigma}^{\Lambda}}(\mathcal{B}(x_{i},\delta))$
and
$U_{\sigma,i}^{\Lambda}=p_{\sigma(i)}^{-1}(\mathrm{vol}_{M_{\sigma}^{\Lambda}})_{|\mathcal{B}(x_{i},\delta)}$.
By the Kantorovitch-Rubinstein duality formula, $W_{1}(\mu,\nu)=\max\int
f\mathrm{d}(\mu-\nu)$, where the maximum is taken over all $1$-Lipschitz
continuous functions $f:\mathbb{R}^{D}\to\mathbb{R}$. Let $f:x\mapsto x\cdot
e$. Assume for instance that $\sigma(i)=-1$ and $\sigma^{\prime}(i)=1$. We
have $f(x)=0$ for $x\in\mathcal{B}_{M_{\sigma}^{\Lambda}}(x_{i},\delta)$ and
$f(x)=\Lambda$ for
$x\in\mathcal{B}_{M_{\sigma^{\prime}}^{\Lambda}}(x_{i},\delta/2)$. Therefore,
we have, as $p_{\sigma^{\prime}(i)}\leq c\delta^{-d}$,

$\displaystyle
W_{1}(U_{\sigma,i}^{\Lambda},U_{\sigma^{\prime},i}^{\Lambda})\geq
p_{\sigma^{\prime}(i)}^{-1}\Lambda\omega_{d}(\delta/2)^{d}\geq c_{1}\Lambda.$

Note also that
$|p_{\sigma(i)}-p_{\sigma^{\prime}(i)}|\leq\left|\mathrm{vol}_{M_{\sigma}^{\Lambda}}(\Phi_{\sigma}^{\Lambda}(\mathcal{B}_{\mathbb{R}^{d}}(x_{i},\delta))-\omega_{d}\delta^{d}\right|\leq
C_{d}\delta^{d}\Lambda^{2}\delta^{-2}$. Furthermore,
$||\mathrm{vol}_{M_{\sigma}^{\Lambda}}|-|\mathrm{vol}_{M_{\sigma^{\prime}}^{\Lambda}}||\leq\sum_{i=1}^{m}|p_{\sigma(i)}-p_{\sigma^{\prime}(i)}|\leq|\sigma-\sigma^{\prime}|C_{d}\delta^{d}\Lambda^{2}\delta^{-2}$.
Let $f_{i}$ be a $1$-Lipschitz continuous function such that
$W_{1}(U_{\sigma,i}^{\Lambda},U_{\sigma^{\prime},i}^{\Lambda})=\int
f_{i}d(U_{\sigma,i}^{\Lambda}-U_{\sigma^{\prime},i}^{\Lambda})$. One can
choose $f_{i}$ such that $f_{i}(x_{i})=0$, so that the maximum of $|f_{i}|$ on
$\mathcal{B}(x_{i},\delta)$ is at most $\delta$. One can then change the value
of $f_{i}$ outside the ball without changing the value of the integral, so
that $f_{i}$ is supported on $\mathcal{B}(x_{i},2\delta)$ and is $1$-Lipschitz
continuous. Consider the function $f$ obtained by gluing together the
different functions $f_{i}$. The function $f$ is $1$-Lipschitz continuous, so
that

$\displaystyle
W_{1}\left(\mu_{\sigma}^{\Lambda},\mu_{\sigma^{\prime}}^{\Lambda}\right)\geq\sum_{i=1}^{m}\left(\frac{p_{\sigma(i)}}{|\mathrm{vol}_{M_{\sigma}^{\Lambda}}|}U_{\sigma,i}^{\Lambda}-\frac{p_{\sigma^{\prime}(i)}}{|\mathrm{vol}_{M_{\sigma^{\prime}}^{\Lambda}}|}U_{\sigma^{\prime},i}^{\Lambda}\right)(f)$
$\displaystyle\geq\sum_{i=1}^{m}\frac{p_{\sigma(i)}}{|\mathrm{vol}_{M_{\sigma}^{\Lambda}}|}(U_{\sigma,i}^{\Lambda}-U_{\sigma^{\prime},i}^{\Lambda})(f)-|p_{\sigma(i)}-p_{\sigma^{\prime}(i)}|\frac{|U_{\sigma^{\prime},i}^{\Lambda}(f)|}{|\mathrm{vol}_{M_{\sigma}^{\Lambda}}|}-p_{\sigma^{\prime}(i)}|U_{\sigma^{\prime},i}^{\Lambda}(f)|\left|\frac{1}{|\mathrm{vol}_{M_{\sigma}^{\Lambda}}|}-\frac{1}{|\mathrm{vol}_{M_{\sigma^{\prime}}^{\Lambda}}|}\right|$
$\displaystyle\geq\sum_{i=1}^{m}\frac{p_{\sigma(i)}}{|\mathrm{vol}_{M_{\sigma}^{\Lambda}}|}W_{1}(U_{\sigma,i}^{\Lambda},U_{\sigma^{\prime},i}^{\Lambda})-\sum_{i=1}^{m}c_{4}|p_{\sigma(i)}-p_{\sigma^{\prime}(i)}|\delta\mathbf{1}\\{\sigma(i)\neq\sigma^{\prime}(i)\\}-c_{5}\delta|\sigma-\sigma^{\prime}|\delta^{d}\Lambda^{2}\delta^{-2}$
$\displaystyle\geq\sum_{i=1}^{m}\mathbf{1}\\{\sigma(i)\neq\sigma^{\prime}(i)\\}(c_{6}\delta^{d}\Lambda-
c_{4}\delta^{d}\Lambda^{2}\delta^{-1})-c_{5}\delta|\sigma-\sigma^{\prime}|\delta^{d}\Lambda^{2}\delta^{-2}\geq
c_{7}\delta^{d}\Lambda|\sigma-\sigma^{\prime}|.$

Hence, letting $\Lambda=c_{k,d,\tau_{\min},L_{k}}\delta^{k}$ and
$\delta=n^{-1}$, we have, by Assouad’s Lemma,

$\mathcal{R}_{n}\left(\frac{\mathrm{vol}_{M}}{|\mathrm{vol}_{M}|},\mathcal{Q}^{k}_{d}(\gamma),W_{r}\right)\gtrsim
n^{-k/d}.$

Consider now the case $\gamma>0$. Let $M_{0}$ be the $d$-dimensional sphere of
radius $\tau_{\min}$ and $M_{1}$ be the $d$-dimensional sphere of radius
$\tau_{\min}+\delta$. Let $Y$ be uniform on $M_{1}$, and let $\xi$ be the law
of $(Y,0)$. Also, let $\xi^{\prime}$ be the law of
$\left(\left(1+\gamma/\tau_{\min}\right)Y,-\gamma/\tau_{\min}Y\right)$. Then,
$\iota_{\\#}\xi=\iota_{\\#}\xi^{\prime}$, whereas
$W_{1}\left(\frac{\mathrm{vol}_{M_{0}}}{|\mathrm{vol}_{M_{0}}|},\frac{\mathrm{vol}_{M_{1}}}{|\mathrm{vol}_{M_{1}}|}\right)\geq\gamma$.
We conclude by Le Cam lemma [Yu97] that
$\mathcal{R}_{n}\left(\frac{\mathrm{vol}_{M}}{|\mathrm{vol}_{M}|},\mathcal{Q}^{k}_{d}(\gamma),W_{r}\right)\gtrsim\gamma$.∎

###### Proof of Theorem 3.1(iv).

Let $a_{n}=n^{-\frac{s+1}{2s+d}}$ if $d\geq 3$ and $a_{n}=n^{-1/2}$ if $d\leq
2$. As $W_{p}\geq W_{1}$, we may assume without loss of generality that $p=1$,
and up to rescaling, we assume that $\tau_{\min}=\sqrt{d}$. Consider the
manifold $M\subset\mathbb{R}^{d+1}$ containing
$\mathcal{B}_{\mathbb{R}^{d}}(0,\sqrt{d})$ of the previous proof. In
particular, $M$ contains the cube $[-1,1]^{d}$. We adapt the proof of Theorem
3 in [WB19b], where authors consider a family of functions
$f_{\sigma}:[-1,1]^{d}\to M$ indexed by $\sigma\in\\{-1,1\\}^{m}$, with
$f_{\sigma}=1+n^{-1/2}\sum_{j=1}^{m}\sigma_{j}\psi_{j}$, where
$(\psi_{j})_{j=1,\dots,m}$ are elements of a wavelet basis of $[-1,1]^{d}$
(see [WB19b, Appendix E] for details on the construction of the wavelet
basis). If $m\lesssim n^{d/(2s+d)}$, then $t_{0}\leq f_{\sigma}\leq t_{1}$ for
some positive constants $t_{0}<1<t_{1}$, and
$\|f_{\sigma}\|_{B^{s}_{p,q}([-1,1]^{d})}\lesssim 1$. Define a function
$g_{\sigma}$ by $g_{\sigma}(x)=f_{\sigma}(x)$ if $x\in[-1,1]^{d}$ and
$g_{\sigma}(x)=1$ otherwise. The function $g_{\sigma}$ satisfies $t_{0}\leq
g_{\sigma}\leq t_{1}$, as well as
$\|g_{\sigma}\|_{B^{s}_{p,q}(M)}\lesssim\|f_{\sigma}\|_{B^{s}_{p,q}}+|\mathrm{vol}_{M}|^{1/p}\lesssim
1$. Such an inequality is clear for the $\|\cdot\|_{H^{l}_{p}(M)}$ norm for
$l$ an integer, as
$\|g_{\sigma}\|_{H^{l}_{p}(M)}^{p}=\|g_{\sigma}\|_{H^{l}_{p}([-1,1]^{d})}^{p}+\|g_{\sigma}\|_{H^{l}_{p}(M\backslash[-1,1]^{d})}^{p}$,
while the result follows from interpolation for Besov spaces [Lun18, Corollary
1.1.7]. Also, as $\int_{[-1,1]^{d}}f_{\sigma}=1$, we have $\int
g_{\sigma}=|\mathrm{vol}_{M}|$, and $g_{\sigma}/|\mathrm{vol}_{M}|$ is larger
than $f_{\min}=t_{0}/|\mathrm{vol}_{M}|$ and smaller than
$f_{\max}=t_{1}/|\mathrm{vol}_{M}|$. Hence, identifying measures with their
densities, the set

$\mathcal{Q}_{m}=\\{\mu_{\sigma}=g_{\sigma}/|\mathrm{vol}_{M}|,\
\sigma\in\\{-1,1\\}^{m}\\}$

is a subset of $\mathcal{Q}^{s,k}_{d}$ for $f_{\min}$ small enough and
$L_{k}$, $L_{s}$, $f_{\max}$ large enough. Furthermore, for
$\sigma,\sigma^{\prime}\in\\{-1,1\\}^{m}$,
$\operatorname*{TV}(\mu_{\sigma},\mu_{\sigma^{\prime}})=\operatorname*{TV}(f_{\sigma},f_{\sigma}^{\prime})$,
while
$W_{1}(\mu_{\sigma},\mu_{\sigma^{\prime}})=W_{1}(f_{\sigma},f_{\sigma^{\prime}})$
by the Kantorovitch-Rubinstein duality formula. Hence, applying Assouad’s
inequality in the same fashion than in [WB19b, Theorem 3] yields that
$\mathcal{R}_{n}(\mu,\mathcal{Q}^{s,k}_{d},W_{1})\gtrsim a_{n}$. ∎

###### Proof of Theorem 3.7(iv).

According to Lemma G.3,
$\mathcal{R}_{n}(\mu,\mathcal{Q}^{s,k}_{d},W_{p})\geq\mathcal{R}_{n}(\mu,\mathcal{Q}^{k}_{d},W_{p})\gtrsim\gamma+n^{-k/d}$,
and according to Theorem 3.1(iv),
$\mathcal{R}_{n}(\mu,\mathcal{Q}^{s,k}_{d},W_{p})\gtrsim a_{n}$. ∎

##  Appendix H Existence of kernels satisfying conditions $A$, $B(m)$ and
$C(\beta)$

The goal of the section is to prove the existence of a kernel $K$ satisfying
the conditions $A$, $B(m)$ and $C(\beta)$ stated at the beginning of Section
3.

If $K$ is a radial kernel, we have by integration by parts, as $K$ is smooth
with compact support,

$\int_{\mathbb{R}^{d}}\partial^{\alpha_{0}}K(v)v^{\alpha_{1}}\mathrm{d}v=C_{\alpha_{0},\alpha_{1}}\int_{\mathbb{R}^{d}}K(v)v^{\alpha_{1}+\alpha_{0}}\mathrm{d}v=C^{\prime}_{\alpha_{0},\alpha_{1}}\int_{\mathbb{R}}K(r)r^{d+|\alpha_{0}|+|\alpha_{1}|-1}\mathrm{d}r.$

Hence, to show the existence of such a kernel, it suffices to find, for every
$m\geq 0$ and every positive constant $\kappa$, a smooth even function
$K:\mathbb{R}\to\mathbb{R}$ supported on $[-1,1]$ satisfying

  * •

Condition $A^{\prime}$: $\int_{\mathbb{R}}K(r)r^{d-1}\mathrm{d}r=\kappa$,

  * •

Condition $B^{\prime}(m)$: $\int_{\mathbb{R}}K(r)r^{d+i-1}\mathrm{d}r=0$ for
$i=1,\dots,m$,

  * •

Condition $C^{\prime}(\beta)$:
$\int_{\mathbb{R}}K(r)^{-}r^{d-1}\mathrm{d}r\leq\beta$.

We show by recursion on $m$ that for any $\beta>0$, there exists a such a
kernel. For $m=0$, let $K_{0}$ be any smooth even nonnegative function
supported on $[-1,1]$. Then, letting $K=\kappa K_{0}/\int_{\mathbb{R}}K_{0}$,
we obtain a kernel $K$ satisfying the desired conditions for any $\beta>0$.
Consider now the case $m>0$. Let $\beta>0$.

  * •

If $m+d$ is even, then any $K$ satisfying conditions $A^{\prime}$,
$B^{\prime}(m-1)$ and $C^{\prime}(\beta)$ will also satisfy $B^{\prime}(m)$.
Indeed, as $K$ is even, we have $\int_{\mathbb{R}}K(r)r^{m+d-1}\mathrm{d}r=0$,
so that the induction step is proven.

  * •

If $m+d$ is odd, let $K$ be a kernel satisfying conditions $A^{\prime}$,
$B^{\prime}(m-1)$ and $C^{\prime}(\beta/2)$. We use the following lemma.

######  Lemma H.1.

For $i\geq 0$, let $e_{i}:x\in\mathbb{R}\mapsto x^{i+d-1}$ and fix an integer
$m>0$. Then, for any $a\in\mathbb{R}$, let $F_{a}$ be the set of smooth
functions $f:(1,\infty)\to\mathbb{R}$ with compact support satisfying $\int
fe_{i}=0\text{ for }0\leq i<m\text{ and }\int fe_{m}=a$. Then,

$\inf\left\\{\int|f(r)|r^{d-1}\mathrm{d}r,\ f\in F_{a}\right\\}=0.$ (H.1)

Assume first the lemma. Let $a=-\frac{1}{2}\int_{\mathbb{R}}K(r)r^{m+d-1}$ and
$f\in F_{a}$. Then,

$\displaystyle\begin{cases}&\int(K(r)+f(|r|))r^{d-1}\mathrm{d}r=\kappa+\int
f(|r|)r^{d-1}\mathrm{d}r=\kappa\\\ &\int(K(r)+f(|r|))r^{i+d-1}\mathrm{d}r=\int
f(|r|)r^{i+d-1}\mathrm{d}r=0\text{ for }0<i<m\\\
&\int(K(r)+f(|r|))r^{m+d-1}\mathrm{d}r=\int
K(r)r^{m+d-1}\mathrm{d}r+2\int_{1}^{\infty}f(r)r^{m+d-1}\mathrm{d}r=0.\end{cases}$

Hence, the kernel $K+f(|\cdot|)$ satisfies the conditions $A$ and
$B^{\prime}(m)$. Also, we have, as $K(r)=0$ if $|r|\geq 1$,

$\displaystyle\int_{\mathbb{R}}(K(r)+f(|r|))_{-}r^{d-1}\mathrm{d}r=\int_{\mathbb{R}}K(r)_{-}\mathrm{d}r+2\int_{1}^{\infty}f(r)_{-}r^{d-1}\mathrm{d}r$
$\displaystyle\qquad\leq\beta/2+\int_{1}^{\infty}|f(r)|r^{d-1}\mathrm{d}r,$

where we used at the last line that
$\int_{1}^{\infty}f(r)_{-}r^{d-1}\mathrm{d}r=\int_{1}^{\infty}f(r)_{+}r^{d-1}\mathrm{d}r=\frac{1}{2}\int_{1}^{\infty}|f(r)|r^{d-1}\mathrm{d}r$.
Lemma H.1 asserts the existence of $f\in F_{a}$ with
$\int|f(r)|r^{d-1}\mathrm{d}r\leq\beta/2$. For such a choice of $f$, the
kernel $\tilde{K}=K+f(|\cdot|)$ satisfies also $C^{\prime}(\beta)$. Finally,
$f$ has a compact support, included in $[0,R]$ for some $R>0$. The kernel
$\tilde{K}_{1/R}$ is supported on $\mathcal{B}(0,1)$, and satisfies conditions
$A^{\prime}$, $B^{\prime}(m)$ and $C^{\prime}(\beta)$. This concludes the
induction step, and the proof of the existence of kernels satisfying
conditions $A$, $B(m)$ and $C(\beta)$.

###### Proof of Lemma H.1.

Consider functions $f$ supported on $[r_{0},r_{1}]$ for some $1<r_{0}\leq
r_{1}$ to fix. Let $G_{r_{0},r_{1}}$ be the subspace of $L_{2}([r_{0},r_{1}])$
spanned by the functions $e_{i}$ for $0\leq i\leq m-1$ and let $g_{m}$ be the
projection of $e_{m}$ on $G_{r_{0},r_{1}}^{\bot}$ the orthogonal space of
$G_{r_{0},r_{1}}$, with $L_{2}$ norm $\ell$. The function
$f=\frac{ag_{m}}{\ell^{2}}$ is a polynomial of degree $m$ restricted to
$[r_{0},r_{1}]$ and satisfies $\int fe_{i}=0$ for $0\leq i\leq m-1$ by
construction, with $\int fe_{m}=\frac{a}{\ell^{2}}\int e_{m}g_{m}=a$. Also, we
have for any polynomial $P\in G_{r_{0},r_{1}}$,

$\displaystyle\|e_{m}-P\|^{2}_{L_{2}([r_{0},r_{1}])}$
$\displaystyle=\int_{r_{0}}^{r_{1}}|r^{m+d-1}-P(r)|^{2}\mathrm{d}r=\int_{1}^{\frac{r_{1}}{r_{0}}}r_{0}|(r_{0}r)^{d+m-1}-P(rr_{0})|^{2}\mathrm{d}r$
$\displaystyle=r_{0}^{2(d+m)-1}\int_{1}^{\frac{r_{1}}{r_{0}}}|r^{d+m-1}-r_{0}^{-(d+m-1)}P(rr_{0})|^{2}\mathrm{d}r.$

As $r\mapsto r_{0}^{-(d+m-1)}P(rr_{0})$ is an element of $G_{1,r_{1}/r_{0}}$,
letting $r_{1}=2r_{0}$, we obtain

$\displaystyle\ell^{2}$
$\displaystyle=\|g_{m}\|_{L_{2}([r_{0},r_{1}])}^{2}=\min_{P\in
G_{r_{0},r_{1}}}\|e_{m}-P\|^{2}_{L_{2}([r_{0},r_{1}])}$
$\displaystyle=r_{0}^{2(d+m)-1}\min_{P\in
G_{1,2}}\|e_{m}-P\|^{2}_{L_{2}([1,2])}=Cr_{0}^{2(d+m)-1},$

where $C=C_{m}>0$ is the distance between $e_{m}$ restricted to $[1,2]$ and
$G_{1,2}$. The function $f$ is not smooth so that it does not belong to
$F_{a}$. To overcome this issue, we consider a smooth kernel $\rho$ on
$\mathbb{R}$ satisfying $\int\rho=1$ and $\int\rho(r)r^{i}\mathrm{d}r=0$ for
$i=1,\dots,m+d-1$, with support included in
$\mathcal{B}_{\mathbb{R}}(0,r_{0}/2)$. See e.g. [BH19, Section 3.2] for the
construction of such a kernel $\rho$. The map $\rho*f$ is supported on
$(1,\infty)$ and it is straighforward to check that $\rho*f\in F_{a}$ for
$r_{0}>2$. By Young’s inequality,
$\|\rho*f\|_{L_{2}(\mathbb{R})}\leq\|\rho\|_{L_{\infty}(\mathbb{R})}\|f\|_{L_{2}(\mathbb{R})}$,
so that

$\displaystyle\int|\rho*f(r)|r^{d-1}\mathrm{d}r$
$\displaystyle\leq\left(\int_{r_{0}/2}^{5r_{0}/2}r^{2d-2}\mathrm{d}r\right)^{1/2}\|\rho*f\|_{L_{2}(\mathbb{R})}\leq\left(c_{d}r_{0}^{2d-1}\right)^{1/2}\|\rho\|_{L_{\infty}(\mathbb{R})}\|f\|_{L_{2}(\mathbb{R})}$
$\displaystyle\leq C_{d,m}ar_{0}^{-m}$

By letting $r_{0}$ goes to $\infty$, we see that
$\inf\left\\{\int|f(r)|r^{d-1}\mathrm{d}r,\ f\in F_{a}\right\\}=0$. ∎

## References

  * [Aam17] Eddie Aamari.  Vitesses de convergence en inférence géométrique.  PhD thesis, Paris Saclay, 2017.
  * [AKC+19] Eddie Aamari, Jisu Kim, Frédéric Chazal, Bertrand Michel, Alessandro Rinaldo, and Larry Wasserman.  Estimating the reach of a manifold.  Electronic Journal of Statistics, 13(1):1359–1399, 2019.
  * [AL18] Eddie Aamari and Clément Levrard.  Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction.  Discrete & Computational Geometry, 59(4):923–971, 2018.
  * [AL19] Eddie Aamari and Clément Levrard.  Nonasymptotic rates for manifold, tangent space and curvature estimation.  The Annals of Statistics, 47(1):177–204, 2019.
  * [Aub82] Thierry Aubin.  Nonlinear Analysis on Manifolds. Monge-Ampère Equations.  Grundlehren der mathematischen Wissenschaften. Springer New York, 1982\.
  * [BB00] Jean-David Benamou and Yann Brenier.  A computational fluid mechanics solution to the monge-kantorovich mass transfer problem.  Numerische Mathematik, 84:375–393, 01 2000.
  * [BCH18] Gérard Besson, Gilles Courtois, and Sa’ar Hersonsky.  Poincaré inequality on complete Riemannian manifolds with Ricci curvature bounded below.  Mathematical Research Letters, 25(6):1741–1769, 2018.
  * [BCS10] Lorenzo Brasco, Guillaume Carlier, and Filippo Santambrogio.  Congested traffic dynamics, weak flows and very degenerate elliptic equations.  Journal de mathématiques pures et appliquées, 93(6):652–671, 2010.
  * [BH19] Clément Berenfeld and Marc Hoffmann.  Density estimation on an unknown submanifold.  arXiv preprint arXiv:1910.08477, 2019.
  * [BHHS20] Clément Berenfeld, John Harvey, Marc Hoffmann, and Krishnan Shankar.  Estimating the reach of a manifold via its convexity defect function.  arXiv preprint arXiv:2001.08006, 2020.
  * [Bre03] Yann Brenier.  Extended Monge-Kantorovich theory.  In Optimal transportation and applications, pages 91–121. Springer, 2003.
  * [Bre10] Haim Brezis.  Functional Analysis, Sobolev Spaces and Partial Differential Equations.  Universitext. Springer New York, 2010.
  * [BRS+12] Sivaraman Balakrishnan, Alesandro Rinaldo, Don Sheehy, Aarti Singh, and Larry Wasserman.  Minimax rates for homology inference.  In Artificial Intelligence and Statistics, pages 64–72, 2012.
  * [BS17] Tyrus Berry and Timothy Sauer.  Density estimation on manifolds with boundary.  Computational Statistics & Data Analysis, 107:1–17, 2017.
  * [Bur94] Heinrich Burkhardt.  Sur les fonctions de Green relatives à un domaine d’une dimension.  Bulletin de la Société Mathématique de France, 22:71–75, 1894.
  * [CGK+20] Galatia Cleanthous, Athanasios G Georgiadis, Gerard Kerkyacharian, Pencho Petrushev, and Dominique Picard.  Kernel and wavelet density estimators on manifolds and more general metric spaces.  Bernoulli, 26(3):1832–1862, 2020.
  * [dC92] Manfredo Perdigao do Carmo.  Riemannian Geometry.  Mathematics (Boston, Mass.). Birkhäuser, 1992.
  * [Div20] Vincent Divol.  Minimax adaptive estimation in manifold inference.  arXiv preprint arXiv:2001.04896, 2020.
  * [Div21] Vincent Divol.  A short proof on the rate of convergence of the empirical measure for the Wasserstein distance.  arXiv preprint arXiv:2101.08126, 2021.
  * [DSS13] Steffen Dereich, Michael Scheutzow, and Reik Schottstedt.  Constructive quantization: Approximation by empirical measures.  In Annales de l’IHP Probabilités et statistiques, volume 49, pages 1183–1203, 2013.
  * [Dud69] Richard Mansfield Dudley.  The speed of mean Glivenko-Cantelli convergence.  The Annals of Mathematical Statistics, 40(1):40–50, 1969.
  * [DZ01] M.C. Delfour and J.P. Zolésio.  Shapes and Geometries: Analysis, Differential Calculus, and Optimization.  Advances in Design and Control. Society for Industrial and Applied Mathematics, 2001.
  * [Fed59] Herbert Federer.  Curvature measures.  Transactions of the American Mathematical Society, 93(3):418–491, 1959.
  * [FG15] Nicolas Fournier and Arnaud Guillin.  On the rate of convergence in Wasserstein distance of the empirical measure.  Probability Theory and Related Fields, 162(3-4):707–738, 2015.
  * [GN15] Evarist Giné and Richard Nickl.  Mathematical Foundations of Infinite-Dimensional Statistical Models.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2015.
  * [GPPVW12] Christopher Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman.  Minimax manifold estimation.  Journal of machine learning research, 13(May):1263–1291, 2012.
  * [GW03] Joachim Giesen and Uli Wagner.  Shape dimension and intrinsic metric from samples of manifolds with high co-dimension.  In Proceedings of the nineteenth annual symposium on Computational geometry, pages 329–337, 2003.
  * [H+96] Tsutomu Hiroshima et al.  Construction of the Green function on Riemannian manifold using harmonic coordinates.  Journal of Mathematics of Kyoto University, 36(1):1–30, 1996.
  * [HA05] Matthias Hein and Jean-Yves Audibert.  Intrinsic dimensionality estimation of submanifolds in $\mathbb{R}^{d}$.  In Proceedings of the 22nd international conference on Machine learning, pages 289–296. ACM, 2005.
  * [Hen90] Harrie Hendriks.  Nonparametric estimation of a probability density on a Riemannian manifold using Fourier expansions.  The Annals of Statistics, pages 832–849, 1990.
  * [KRW16] Jisu Kim, Alessandro Rinaldo, and Larry Wasserman.  Minimax rates for estimating the dimension of a manifold.  arXiv preprint arXiv:1605.01011, 2016.
  * [L+20] Jing Lei et al.  Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces.  Bernoulli, 26(1):767–798, 2020.
  * [LJM09] Anna V Little, Yoon-Mo Jung, and Mauro Maggioni.  Multiscale estimation of intrinsic dimensionality of data sets.  In 2009 AAAI Fall Symposium Series, 2009.
  * [LLW07] Han Liu, John Lafferty, and Larry Wasserman.  Sparse nonparametric density estimation in high dimensions using the rodeo.  In Artificial Intelligence and Statistics, pages 283–290, 2007\.
  * [Lun18] A. Lunardi.  Interpolation Theory.  Publications of the Scuola Normale Superiore. Scuola Normale Superiore, 2018.
  * [LZZL13] Jicai Liu, Riquan Zhang, Weihua Zhao, and Yazhao Lv.  A robust and efficient estimation method for single index models.  Journal of Multivariate Analysis, 122:226–238, 2013.
  * [NSW08] Partha Niyogi, Stephen Smale, and Shmuel Weinberger.  Finding the homology of submanifolds with high confidence from random samples.  Discrete & Computational Geometry, 39(1-3):419–441, 2008.
  * [PC19] Gabriel Peyré and Marco Cuturi.  Computational optimal transport: With applications to data science.  Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
  * [Pel05] Bruno Pelletier.  Kernel density estimation on Riemannian manifolds.  Statistics & probability letters, 73(3):297–304, 2005.
  * [Pey18] Rémi Peyre.  Comparison between $W_{2}$ distance and $\dot{H}^{-1}$ norm, and localization of Wasserstein distance.  ESAIM. Control, Optimisation and Calculus of Variations, 24(4), 2018\.
  * [PR84] Jean-Baptiste Poly and Gilles Raby.  Fonction distance et singularités.  Bulletin de Sciences Mathématiques, 108:187–195, 1984.
  * [Ros70] Haskell P Rosenthal.  On the subspaces of $L_{p}$ ($p>2$) spanned by sequences of independent random variables.  Israel Journal of Mathematics, 8(3):273–303, 1970.
  * [San15] Filippo Santambrogio.  Optimal transport for applied mathematicians.  Birkäuser, NY, 55:58–63, 2015.
  * [Sog17] Christopher D. Sogge.  Fourier Integrals in Classical Analysis.  Cambridge Tracts in Mathematics. Cambridge University Press, 2 edition, 2017.
  * [SP18] Shashank Singh and Barnabás Póczos.  Minimax distribution estimation in Wasserstein distance.  arXiv preprint arXiv:1802.08855, 2018.
  * [TGHS20] Nicolás García Trillos, Moritz Gerlach, Matthias Hein, and Dejan Slepčev.  Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace–Beltrami operator.  Foundations of Computational Mathematics, 20(4):827–887, 2020.
  * [Tib96] Robert Tibshirani.  Regression shrinkage and selection via the lasso.  Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996.
  * [Tri92] H. Triebel.  Theory of Function Spaces II.  Monographs in Mathematics. Springer Basel, 1992.
  * [Tsy08] Alexandre B Tsybakov.  Introduction to nonparametric estimation.  Springer Science & Business Media, 2008.
  * [Vil08] Cédric Villani.  Optimal transport: old and new, volume 338.  Springer Science & Business Media, 2008.
  * [WB19a] Jonathan Weed and Francis Bach.  Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance.  Bernoulli, 25(4A):2620–2648, 2019.
  * [WB19b] Jonathan Weed and Quentin Berthet.  Estimation of smooth densities in Wasserstein distance.  arXiv preprint arXiv:1902.01778, 2019.
  * [WW20] Hau-Tieng Wu and Nan Wu.  Strong uniform consistency with rates for kernel density estimators with general kernels on manifolds, 2020.
  * [Yu97] Bin Yu.  Assouad, Fano, and Le Cam.  In Festschrift for Lucien Le Cam, pages 423–435. Springer, 1997\.
  * [ZJRS16] Hongyi Zhang, Sashank J Reddi, and Suvrit Sra.  Riemannian SVRG: Fast stochastic optimization on Riemannian manifolds.  Advances in Neural Information Processing Systems, 29:4592–4600, 2016.


# Location-Aware Self-Supervised Transformers

Mathilde Caron Neil Houlsby Cordelia Schmid
Google Research

###### Abstract

†† Correspondence<EMAIL_ADDRESS>Code will be released at:
https://github.com/google-research/scenic/tree/main/scenic/projects/loca

Pixel-level labels are particularly expensive to acquire. Hence, pretraining
is a critical step to improve models on a task like semantic segmentation.
However, prominent algorithms for pretraining neural networks use image-level
objectives, e.g. image classification, image-text alignment à la CLIP, or
self-supervised contrastive learning. These objectives do not model spatial
information, which might be sub-optimal when finetuning on downstream tasks
with spatial reasoning. In this work, we propose to pretrain networks for
semantic segmentation by predicting the relative location of image parts. We
formulate this task as a classification problem where each patch in a query
view has to predict its position relatively to another reference view. We
control the difficulty of the task by masking a subset of the reference patch
features visible to those of the query. Our experiments show that this
location-aware (LOCA) self-supervised pretraining leads to representations
that transfer competitively to several challenging semantic segmentation
benchmarks.

##  1 Introduction

Spatial annotations are extremely time consuming and costly to acquire.
Therefore, pretraining is commonly used to improve performance and label-
efficiency of models reasoning at the pixel-level, such as semantic
segmentation models. The dominant method for pretraining neural networks uses
image-level tasks on massive amounts of supervised data [51, 49, 12, 72, 70].
For example, powerful foundation models such as the recent Flamingo [1], CoCa
[69] or PaLI [14] models, build upon a visual encoder pretrained by matching
aligned image and text pairs with a contrastive loss [49], or by classifying
images into a predefined set of categories [72]. These two standard supervised
pretraining objectives operate at the global (whole image) level, without
explicitly encouraging spatial reasoning.

However, it is unclear whether image-level pretraining is the optimal strategy
when targeting recognition tasks with spatial understanding. In fact, a recent
study by Minderer  _et al_. [43] shows that some models pretrained with image
classification, while being excellent at image-level downstream tasks,
transfer poorly to object detection, a task clearly requiring spatial
reasoning. Motivated by their observation, our goal is to design a pretraining
strategy leading to strong features for pixel-level downstream tasks.
Specifically, we target semantic segmentation in this work.

We argue that the main reason why pretraining is usually done with global
objectives is because annotations are much easier to collect at the image
level rather than at the pixel level. Indeed, the image classification or
image-text datasets typically used in state-of-the-art systems [72, 49] are
orders of magnitude bigger and cover more categories than densely annotated
datasets [73, 39]. Therefore, one approach to unlock the potential of dense,
spatially-aware pretraining at scale might be to move away from annotations,
as proposed by self-supervised learning (SSL) approaches. A successful branch
of SSL, often coined as “contrastive learning”, works by matching the
representation of different views obtained from a same image by means of data
augmentation [32, 13, 10, 29]. Interestingly, Caron  _et al_. [11] have shown
that segmentation masks emerge from the attention maps of Vision Transformers
(ViT) [23] trained with these contrastive methods. However, we found in our
preliminary experiments that salient attention maps do not correlate with
superior performance after finetuning to the semantic segmentation task [76].
We hypothesize that this is because contrastive methods operate at the global
level without explicitly encouraging spatial relationships. Worse, due to
their intensive use of spatial data augmentation such as cropping and
rescaling, they tend to produce localization-invariant features discarding
spatial information [16, 3]. Successful alternative strategies to contrastive
methods have recently emerged [31, 6, 71, 5, 68, 64]. Of particular interest,
masked autoencoders propose to reconstruct masked content [31, 6], hence
encouraging Transformers to learn about relationships between different image
parts.

In this paper, we explore an alternative to content reconstruction to
encourage the emergence of spatial Transformer features, that of predicting
relative image parts location. Specifically, our location-aware approach,
LOCA, simply works by predicting the location of a query view relatively to
another, reference, view as illustrated in Fig. 1. In order to solve the
relative position task, the Transformer needs to reason about the spatial and
semantic relationships between different parts of an image. In practice, this
pretext task admits a simple formulation: we implement our model as a
classification problem where each patch in the query view is trained to
predict its position relatively to the reference view. To be able to locate
themselves in the reference, the query patch features “look” at the reference
through a shallow cross-attention module. We show that we can control the
difficulty of the task and properties of the resulting features by masking
reference patch features to the query. We add a patch feature prediction
objective to our localization framework, explicitly encouraging patches
covering similar locations to have consistent representations. Overall, our
location-aware pretraining can be seen as revisiting the pioneering SSL works
on “Context prediction” [22, 46] in the context of Vision Transformers, which
has attracted only very limited attention so far [71, 17].

Our experiments show that LOCA yields excellent locality and good semantic
understanding, while still being a little behind state-of-the-art methods on
the pure semantic understanding axis. Overall, this yields improved
performance over state-of-the-art supervised [59, 55] and unsupervised [11,
31, 74, 15] representation learning methods for Vision Transformers when
transferred to semantic segmentation, which requires both local and semantic
features. Finally, we also show that our method scales promisingly to large
models and large amount of data, which is a positive signal that LOCA could be
a viable candidate for spatially-aware pretraining at scale.

##  2 Related Work

##### SSL with location prediction.

Pioneering works in SSL proposed to exploit spatial cues to generate pretext
tasks [22, 35, 37, 45, 52, 46, 28]. Notably, inspired by word2vec [42],
Doersch  _et al_. [22] train a network to predict the relative position of a
pair of patches from the same image while Noroozi and Favaro [46] extend this
approach to solving “jigsaw puzzles” by rearranging a set of shuffled crops of
an image. These approaches were developed with Convnets and very little work
has revisited them in the scope of Transformers [71]. Zhai  _et al_. [71]
propose to pretrain a ViT to predict the position of its input patches given
their visual appearance only, i.e. by discarding positional embeddings. We
compare this strategy to the LOCA mechanism in Fig. 2 and Sec. 4.1. Also using
localization, UP-DETR [20] propose to pretrain the DETR [8] architecture
without using any annotations by localizing random boxes in a reference image.
Our initial design is inspired by UP-DETR, though our implementations vary
greatly: we formulate our task as a patch position classification problem
while they follow DETR losses and architecture.

##### Context and masked auto-encoders.

Also exploiting spatial cues for SSL, Pathak  _et al_. [47] propose context
auto-encoders to train Convnets to generate the content of a masked region
based on its surrounding. Recently, masked auto-encoders revisit this
“inpainting” approach to pretraining Vision Transformers [6, 31, 62].
Specifically, the task is to reconstruct masked [6] or dropped [31] patches
from the input sequence tokens, either directly in pixel space [31] or in
feature space [62, 6, 74]. Similar to our approach, masked auto-encoders are
trained with patch-based objectives with a task encouraging the network to
learn local representations of object parts and their spacial arrangement.

##### Dense contrastive SSL.

A prominent line of SSL, often referred to as “contrastive” or “siamese”
approaches, trains networks by matching the representation of different views
obtained from a same image by means of data augmentation [32, 13, 10, 29, 65,
24, 3]. These approaches have primarily been developed with global (image-
level) objectives but several recent works have adapted them to learn local
features [48, 61, 50, 66, 67]. Specifically, instead of matching
representations from global descriptors, they match features that come from
the same location in the original image but seen from different views [48].
Our feature prediction loss is directly inspired from this literature. Also,
we borrow the strategy of back-tracking the data augmentation process of two
views to find their regions that intersect [48].

##### Unsupervised semantic segmentation.

While our goal is to improve pretraining for semantic segmentation, some works
directly target semantic segmentation without using any supervision at all
[18, 60]. Indeed, Caron  _et al_. [11] have shown that unsupervised
segmentation masks emerge from the attention module of ViTs trained with
image-level contrastive objectives such as DINO. Several works build on this
observation and enhance self-supervised features to produce completely
unsupervised segmentation masks [30, 76, 54]. These approaches typically do
not evaluate semantic segmentation after end-to-end finetuning.

##  3 Methodology

###  3.1 Query-reference mechanism

In our work, we propose a query-reference mechanism to predict image parts
localization. Specifically, a query has to predict its position as viewed in a
reference image as illustrated in Fig. 1. We consider a single query per
reference in this section for simplicity but use several in practice. We now
detail our query-reference mechanism.

##### Generating query and reference views.

From an image $x$ of a dataset, we form a reference view (denoted by
$\bm{x}_{ref}$) and a query view (denoted by $\bm{x}_{q}$) using a randomized
data augmentation routine composed of flipping, cropping, rescaling and color
jittering. Because query and reference are generated by two independent
augmentation draws, they usually have different image statistics (i.e.
different scale, region or color histogram). This forces the network to rely
less on low-level cues (chromatic aberration, color, and edge consistency) to
solve the localization task and more on recognizing object parts and their
organization.

The query’s task is to locate itself inside the reference view and therefore
our loss is defined only at the intersection of the two views. Hence, we wish
the query and reference to intersect often. Also, in order to favor the
emergence of image-part representations, we constrain the spatial extent of
the queries. A natural choice then is to sample the reference view so that it
covers a large area of the original image and the query views so that they
cover a small portion of the original image. In practice we use the MSN input
pipeline [3] with random resize-cropping and patch-dropping for generating 10
different query views per reference. Note that as opposed to MSN, our goal is
not to have an identical representation for the different generated views but
to predict their positions relatively to a reference view.

##### Correspondences between query and reference.

Following the standard protocol of the Vision Transformers [23], query and
reference views are divided into non overlapping patches of resolution
$P\times P$. More precisely, the reference view is flattened into
$N_{ref}=\lfloor H_{ref}/P\rfloor\times\lfloor W_{ref}/P\rfloor$ (with
$H_{ref}\times W_{ref}$ the resolution of $x_{ref}$) separate patches
$\bm{x}_{ref}^{i},i\in\\{1,...,N_{ref}\\}$. Default typical values are
$H_{ref}=W_{ref}=224$, $P=16$ and $N_{ref}=196$. A similar “patchification”
process is applied on the query view, resulting in a sequence of $N_{q}$
patches $\bm{x}_{q}^{j},j\in\\{1,...,N_{q}\\}$. Unless specified otherwise, we
have $N_{q}=36$. By back-tracking the data augmentation draws that generated
$\bm{x}_{ref}$ and $\bm{x}_{q}$, we can identify the patch-level
correspondences between these two views. In particular, we know a function
$\bm{h}$ that, given any patch position $j$ in the query view, returns the
position $i=\bm{h}(j)$ of the patch in the reference,
$\bm{x}_{ref}^{\bm{h}(j)}$, that has the greatest overlap with the query patch
$\bm{x}_{q}^{j}$. We implement the function $\bm{h}$ with successive nearest
interpolations and because the patchification grids of $\bm{x}_{q}$ and
$\bm{x}_{ref}$ are usually not exactly aligned, a pair of matching patches,
$\bm{x}_{q}^{j}$ and $\bm{x}_{ref}^{\bm{h}(j)}$, have similar content but do
not generally match perfectly. This effect can be seen in the example in Fig.
1.

Figure 1: LOCA works by predicting the location of a query view relatively to
a reference view. Patch features of the query look at those of the reference
through a cross-attention block before making their prediction. We control the
difficulty of the task by masking part of the reference patch features visible
to the query. We also use a feature prediction loss to encourage patches
covering similar content in different views to be consistent.

###  3.2 Relative localization training

We process both the reference and query views with a Vision Transformer
network [23], denoted by $f$, of internal dimension $d$: $d=768$ for ViT-B and
$d=1024$ for ViT-L. We note $\bm{Z}_{q}\in\mathbb{R}^{d\times N_{q}}$ (resp.
$\bm{Z}_{ref}\in\mathbb{R}^{d\times N_{ref}}$), the output patch
representation matrix of the query (resp. reference) view. In the following,
we detail the self-supervised localization loss applied to these patch
representations.

##### Patch position prediction.

We implement the query localization problem as a $N_{ref}$-way classification
task where each query patch representations has to predict the position of the
patch covering the same content in the reference view, as given by $\bm{h}$.
To that end, the patch representations of the query need to be able to “look”
at those of the reference. We implement this query-reference interaction with
a single cross-attention transformer block, denoted by $g$, whose queries are
computed from $\bm{Z}_{q}$ and keys and values are obtained from
$\bm{Z}_{ref}$. We denote the query representations after they have looked at
the reference as $\bm{G}=g(\bm{Z}_{q},\bm{Z}_{ref})\in\mathbb{R}^{d\times
N_{q}}$ and by $W\in\mathbb{R}^{d\times N_{ref}}$ the final “position
classification” layer. Note that $N_{ref}$ is the total number of positions in
the reference. We train the network to minimize the following position
prediction loss:

$\displaystyle\frac{1}{|\Omega|}\sum_{j\in\Omega}\ell((W^{T}\bm{G})_{j},\bm{h}(j))$
(1)

where $\Omega$ is the set of patch position in the query that has an
intersection with the reference (i.e. where $\bm{h}$ is defined) and $\ell$ is
the standard softmax cross-entropy loss. We average the loss over both the
different query views and the minibatch, and learn $f$, $g$, and $W$
parameters with back-propagation.

##### Masking reference patch features visible to the query.

In practice, we find that problem 1 can be solved near perfectly by the
network (see the validation accuracy in Fig. 3). As empirically shown in Sec.
4.1, one strategy to make the task more challenging is to restrict what the
query can see from the reference. We implement this mechanism by randomly
dropping (or “masking”) a ratio $\eta$ of the patch features input to the
cross-attention block $g$. Specifically, we redefine
$\bm{G}=g(\bm{Z}_{q},m(\bm{Z}_{ref},\eta))$ where $m$ is a random process that
discards $\lfloor\eta N_{ref}\rfloor$ columns of $\bm{Z}_{ref}$. We use
structured dropping (i.e. we keep a consecutive subset of patch tokens) as we
find in our experiments that it leads to superior performance than
unstructured dropping ($+0.8$ mIoU).

(a) Single | (b) LOCA query-reference (Ours)
---|---

Figure 2: Conceptual comparison of single vs query-reference patch position
prediction mechanisms: (a) in a single view as in Zhai  _et al_. [71]; (b) in
a query view relatively to a reference view as in LOCA (Ours). Quantitative
comparison is presented in Fig. 3. Masking is not illustrated here for
simplicity.

##### Patch feature prediction.

Inspired by UP-DETR framework [20], we add a patch feature prediction
objective to our localization framework in order to obtain more semantic
representations. Intuitively, the patch features should not only be able to
locate themselves but also to match those at a similar location in a different
context. We implement this with a patch-based version of the MSN framework [3]
(see Appendix A). Specifically, we use Sinkhorn-Knopp [10, 2] and me-max
regularization [4] schemes to prevent the collapse of the representations, as
well as an exponential moving average (ema) branch [32] for the encoder
processing the reference view. We use the default values from MSN [3] for the
temperature, momentum and me-max parameters. Other patch feature prediction
implementations are possible [11, 13, 32]. We have observed in our preliminary
experiments that this choice has minimal impact on the final performance and
we choose MSN for its stability. Overall, we show in Table 5 that adding the
patch feature prediction loss brings a substantial boost of performance in our
model.

Figure 3: Single vs query-reference patch position prediction mechanisms. For
both mechanisms, we report the position prediction accuracy (left) and the
performance after transfer to semantic segmentation on ADE20k (right) for
different patch masking ratios $\eta$. Query-reference makes for a more
challenging pre-training objective (lower accuracy on the position prediction
task) due to different image statistics between query and reference and
constrained patch interactions. Conceptual differences are illustrated in Fig.
2. Varying the masking ratio controls the difficulty of the task and improves
transfer performance.

###  3.3 Implementation and evaluation protocol

##### Implementation details.

We train our models with a learning rate of $0.001$ (decayed with cosine
schedule), a batch size of $1024$ and a fixed weight decay of $0.1$ with adamw
optimizer [41]. We use ImageNet-1k or ImageNet-21k without labels as our pre-
training dataset [51]. Models for ablations and analyses (in Sec. 4.1 and 4.3)
are trained during 100 epochs while those in Sec. 4.2 and 4.4 are trained for
600 epochs. 100 epochs of training on 16 TPUv2 accelerators take 29 hours. We
use $\eta=0.8$ for masking (see effect in Fig. 4), resulting in 40 keys and
values in input of the cross-attention block. Additional implementation
details are in the Appendix A. We implement LOCA in Jax. Code and models to
reproduce our results will be made publicly available as a scenic project
[21].

##### Evaluation protocol on semantic segmentation.

We evaluate our models by end-to-end finetuning on the following 4 semantic
segmentation benchmarks: ADE20K [73], Pascal Context [44], Pascal VOC [25] and
Cityscapes [19]. Recent works have shown that plain ViT architectures can be
used for dense recognition tasks [56, 38, 43]. Therefore, we follow the linear
decoder protocol of Strudel  _et al_. [56] hence using a minimal amount of
adapter layers to prevent the effect of pretraining of being washed out by
heavy decoders. We validate in Appendix B that we reproduce the implementation
of Strudel  _et al_. [56]. We report results in single scale mode, averaged
over 5 runs as we typically observe a standard deviation of $\pm 0.4$ mIoU on
ADE20k. All evaluation implementation details are in Appendix B.

##  4 Experiments

Figure 4: Masking reference patches to the query improves both classification
and segmentation transfers on ADE20k. However, too extreme masking prevents
the query from solving the task by relative localization which hurts
localization transfer. See second § of Sec. 4.1.

###  4.1 Our Localization Mechanism

In this section, we detail our design choices for the localization task: we
study the query-reference mechanism, analyze and visualize the effect of
masking reference patches and evaluate different loss functions. Models are
run without the feature prediction framework (i.e. with loss (1) only) to
better understand the effect of pure localization training.

Table 1:  Localization loss. We evaluate several variants for the query localization loss and report mIoU on ADE20k semantic segmentation transfer. Predicting the position of all patches versus the position of the central patch only is better, likely because it involves reasoning about the spatial extent of the query. Classification works better than regression in our experiment, despite the fact that regression is advantageously not impacted by the misalignment between query and reference patchification grids.  Output | Predicts spatial extent | Loss | ADE20k
---|---|---|---
Every patch position | ✓ | Classif. | 42.5
Central patch position |  | Classif. | 38.6
Query box coordinates | ✓ | Regress. | 39.0
|  $\eta=0$ |  $\eta=0.8$ | $\eta=1$
---|---|---|---
Query | Reference
Figure 5:  Visualizing LOCA’s predictions. The query location is shown in blue
in the reference and LOCA predictions are shown in red. Columns correspond to
different reference masking rates and we show only patches visible to the
query when it makes its prediction. More examples in the Appendix D. Displayed
images are not seen during training. See discussion in third § of Sec. 4.1.

##### Query-reference mechanism.

We compare the two mechanisms illustrated in Fig. 2. Note that removing
positional embeddings in the “single” strategy is crucial, otherwise the task
is trivial [71]. To avoid confounding factors, we also discard positional
embeddings in the query view in LOCA in this experiment, though we find in
practice it has minor effect on the performance (see Tab. 5). For both
strategies, we vary $\eta$, the proportion of masked patch tokens. In “single”
mechanism, masking patch tokens means that the patches can only attend to the
unmasked patch tokens, i.e. only the unmasked patches take part in the
computation of keys and values of ViT [71]. We run a small hyper-parameter
grid for all runs. The results are in Fig. 3. On the left panel, we report the
validation accuracy for the position prediction task after 100 epochs of
training. This measures how well the network solves its pretraining objective
in a fixed training budget, which enables the comparison of the difficulty of
different pretraining strategies. On the right panel, we show the models
transfer performance.

We see in Fig. 3 that the query-reference mechanism of LOCA is a more
challenging pretraining task than predicting position in a single view as in
Zhai  _et al_. [71] and leads to better representations for semantic
segmentation. This can intuitively be explained by several conceptual
differences. First, in the single mechanism, the network can almost perfectly
solve the task by leveraging low-level non-semantic cues such as chromatic
aberration, color or edges consistency between patches. This is partly
prevented in the query-reference mechanism due to different image statistics
between query and reference (thanks to cropping, rescaling and color
jittering). Second, the way query (i.e. patches that predict a position) and
reference (i.e. context patches) can interact is in stark contrast in the two
mechanisms. In “single”, query and reference are the same and hence interact
in an unconstrained manner at all stages of the computation. With masking,
Zhai  _et al_. [71] modify partly this design by now processing each query
patch independently but still allowing them to fully attend to the reference
patches at each block. By contrast, in LOCA, query patches can attend freely
to each other but cannot look at the reference patches until the last stage of
the network. Intuitively, this more constrained interaction encourages both
query and reference patches to develop stronger final localization features.

Table 2:  Comparison with previous results on semantic segmentation. We report mean IoU for semantic segmentation on the validation set of ADE20k [73], Cityscapes [19] and Pascal Context (“P.Context”) [44] for different self-supervised and supervised pretraining methods. We consider two settings: (i) pretraining on ImageNet-1k with ViT-Base and (ii) pretraining on ImageNet-21k with ViT-Large. Networks are then end-to-end finetuned on the semantic segmentation train set. We follow the experimental setup of Segmenter [56] for end-to-end finetuning of ViT with linear decoder. We report their number for the supervised checkpoints “DeiT” and “Augreg”. Results for the self-supervised methods and for DeiT-III are run by us from official released checkpoints. We report the average over $5$ runs with single-scale mode (*: numbers with multi-scale evaluation).  Method | Supervised |  | ADE20k | P.Context | Cityscapes
---|---|---|---|---|---
ImageNet-1k / ViT-Base |  |
Random init. |  |  | 21.1 | 19.6 | 51.4
DINO [11] |  |  | 44.1 | 50.7 | 78.4
MoCo-v3 [15] |  |  | 45.4 | 51.6 | 78.6
MAE [31] |  |  | 45.5 | 51.7 | 79.7
DeiT [58, 56] | ✓ |  | 47.1 | – | –
DeiT-III [59] | ✓ |  | 47.3 | 53.9 | 79.7
iBOT [74] |  |  | 47.0 | 54.6 | 79.8
LOCA (Ours) |  |  | 47.9 | 54.9 | 79.8
ImageNet-21k / ViT-Large |  |
Augreg [55, 56] | ✓ |  | 50.7 |  56.5* |  80.7*
LOCA (Ours) |  |  | 52.3 | 60.3 | 81.5

##### Masking reference patches.

In Fig. 3, we observed that the localization pretraining task can be solved
near perfectly when all the patches in the reference are visible to the query
(see left panel of Fig. 3 for $\eta=0$). Restricting patches visible to the
query makes the pretraining objective more challenging and leads to better
representations. In Fig. 4, we analyze this effect further. We consider
different masking ratios and report for the same downstream dataset both the
transfer performance on semantic segmentation and multi-label classification
(with frozen backbone) by turning the semantic segmentation annotations into
classification labels. We observe in Fig. 4 that masking improves both
localization and classification capabilities of the network. Intuitively this
is because masking reference patches forces the query to rely less on finding
matching salient points between the two views and more on recognizing object
categories and their parts.

However, when masking becomes too aggressive, the query does not see enough of
the reference to solve its task by relative localization and resorts to other
cues. To understand this phenomenon, we push masking to extreme rates and even
report performance when the reference is not visible at all ($\eta=1$).
Surprisingly, we find that the query still manages to solve the localization
pretraining task to some extent with a localization accuracy of 3.7% while
random guessing would achieve 0.5%. We hypothesize that two ways of solving
the task without looking at the reference are to (i) learn where things are
typically located in images and (ii) memorize all the dataset images. We argue
that the “memorization” regime is akin to an implicit formulation of the
“exemplar” instance discrimination approach of Dosovitskiy  _et al_. [24]
where the network learns to recognize each individual instance of a dataset
(but without a classifier of the size of the dataset as in [24]). Overall,
both learning biases of general dataset statistics and instance discrimination
have been shown to improve transfer performance on classification downstream
tasks [24, 65, 26] which is consistent with the boost in classification
observed for $\eta=1$.

Finally, this experiment shows that an optimal masking ratio for semantic
segmentation features is high, but not too high either so that the network can
still solve the task by relative localization. In practice, we use $\eta=0.8$.

Table 3:  Fewshot semantic segmentation on ADE20k. We report mean IoU for semantic segmentation on the validation set of ADE20k for different pretrained models. Only a fraction (either $1/32$, $1/16$, $1/8$, $1/4$ or $1/2$) of ADE20k training images are used for finetuning. Results are averaged over $5$ different splits. Architecture is ViT-B for all runs and pretraining data is ImageNet-1k.  Method | $1/32$ | $1/16$ | $1/8$ | $1/4$ | $1/2$
---|---|---|---|---|---
DINO [11] | 18.4 | 24.5 | 29.5 | 35.2 | 39.5
MoCo-v3 [15] | 17.7 | 25.2 | 30.8 | 36.5 | 40.7
MAE [31] | 18.4 | 25.3 | 30.5 | 36.1 | 40.6
Supervised - DeiT-III [59] | 20.9 | 27.1 | 32.7 | 38.3 | 42.0
iBOT [74] | 20.9 | 28.0 | 33.4 | 38.7 | 42.6
LOCA (Ours) | 22.2 | 30.0 | 34.4 | 39.1 | 42.8
Table 4:  Disentangling localization and classification on semantic segmentation. We report classification only (with a multi-label classification training) and localization only (with an oracle giving the class of the segmentation masks) evaluations on 4 popular semantic segmentation benchmarks: ADE20k [73], Pascal Context (“P.Cont.”) [44], Pascal VOC (“P.VOC”) [25] and Cityscapes (“City.”) [19]. Details about the classification/location only protocols are in Sec. 4.2. Best number is in bold and second best is underlined. We report performance for different methods pretrained on ImageNet-1k (with or without labels) with ViT-B. LOCA yields excellent locality and good semantic understanding but is still behind image-level pretraining methods on the pure semantic axis (classification only evaluation).  | Classification only (mAP) |  | Localization only (mIoU) |  | Both (mIoU)
---|---|---|---|---|---
Method | ADE20k | P. Cont. | P. VOC | Citysc. |  | ADE20k | P. Cont. | P. VOC | Citysc. |  | ADE20k | P. Cont. | P. VOC | Citysc.
Image-level pretrainings |  |  |  |  |  |  |  |  |  |  |  |  |  |
DINO [11] | 61.6 | 67.7 | 89.9 | 81.5 |  | 64.5 | 71.6 | 78.7 | 79.6 |  | 44.1 | 50.7 | 74.7 | 78.4
MoCo-v3 [15] | 61.1 | 69.3 | 93.6 | 82.1 |  | 66.2 | 73.7 | 79.0 | 79.9 |  | 45.4 | 51.6 | 74.3 | 78.6
Supervised (DeiT-III [59]) | 64.8 | 71.5 | 94.6 | 84.0 |  | 66.5 | 73.6 | 80.1 | 80.7 |  | 47.3 | 53.9 | 76.3 | 79.7
Spatially-aware pretrainings |  |  |  |  |  |  |  |  |  |  |  |  |  |
MAE [31] | 59.0 | 67.6 | 92.8 | 84.3 |  | 67.0 | 74.3 | 79.9 | 81.1 |  | 45.5 | 51.7 | 75.4 | 79.7
LOCA (Ours) | 62.2 | 69.9 | 93.7 | 83.6 |  | 67.9 | 75.4 | 80.5 | 81.4 |  | 47.9 | 54.9 | 76.6 | 79.8

##### Visualizing LOCA’s predictions.

In Fig. 5, we visualize the output of location prediction models trained with
different masking rates: $\eta=0$ (no masking), $\eta=0.8$ (default) and
$\eta=1$ (invisible reference). The first row shows a situation where the
network can make a valid guess about the query’s location solely based on the
query visual appearance, i.e. without looking at the reference. In the second
row, we see that LOCA successfully locates the snout of the dog based on the
reference ear patches. This suggests that it has learned about spatial
arrangement of different parts of a dog. Third row depicts the case where the
network can leverage low-level cues such as edge consistency to locate the
query. The masked variants are restrained in their use of such cues and hence
fail to locate the query. Finally, in last row, there is no visible cue in the
query that allows its localization. The prediction is degenerated for all the
variants.

##### Choice of localization loss.

In Fig. 1, we evaluate different losses for position prediction. First, we
compare predicting the position of all patches versus the position of the
central patch only. We see in Fig. 1 that all patches is better. We
hypothesize that this is because it requires to predict the spatial extent of
the query and not just an anchor point. Second, we compare solving a per-patch
position classification problem versus regressing the coordinates of the query
box in the reference. For box prediction, we use a linear combination of
$\ell_{1}$ loss and the generalized IoU loss, following UP-DETR [20, 8].
Because query and reference patchification grids are usually not aligned,
matching patches in query and reference do not have exactly the same content.
This does not affect the box regression formulation, which might give it an
advantage over per-patch classification. However, we surprisingly find in Fig.
1 that box regression leads to poorer performance than per-patch
classification. It is possible that this loss requires additional hyper-
parameter tuning (we performed a small optimization hyperparameter search but
did not vary from the loss parameters from [8, 20]).

Overall, patch position classification is a simple implementation of our
relative localization problem and works well in practice. It is possible that
refinements (for exemple in the spirit of ROIAlign for detection [33]) lead to
superior performance in the future.

###  4.2 Comparison with previous results

Self-supervised features have been shown to outperform supervised
representations in many papers [10, 31, 29, 11]. However, as the self-
supervised field makes important progress, supervised training recipes also
improve greatly [58, 59, 55, 40, 53]. In this section, we try to keep the
comparison up-to-date by considering state-of-the-art ImageNet supervised
ViTs, namely AugReg [55] on ImageNet-21k and DeiT-III [58] for ImageNet-1k
only. We also compare to popular state-of-the-art SSL models for ViTs: DINO
[11], MoCo-v3 [15], MAE [31] and iBOT [74].

##### Comparison on semantic segmentation benchmarks.

In Tab. 6, we report the performance of different pretraining strategies after
end-to-end finetuning on semantic segmentation on the popular ADE20k, Pascal
Context and Cityscapes benchmarks [73, 44, 19]. We use the linear decoder from
Segmenter [56] as detailed in Sec. 3.3 and Appendix B. Results in Tab. 6
validate that representations learned with LOCA transfer well to semantic
segmentation. Our performance improves over previous self-supervised and
supervised representation learning methods by a margin of $0.6\\!-\\!1.8$.
Notably, we outperform the strong Augreg supervised checkpoint that was
finetuned on high resolution images ($384\times 384$). We further analyze
semantic segmentation performance in the following paragraph by disentangling
the classification and localization aspects.

##### Localization and classification trade-off.

Semantic segmentation is the coupling of classification and localization,
where these two tasks can have different feature preferences. In Tab. 4, we
propose to disentangle classification and localization performance on semantic
segmentation benchmarks which require both. First, we discard local
information and evaluate classification only by finetuning with a multi-label
binary cross-entropy loss. Second, we evaluate localization only by reporting
the performance of an already finetuned semantic segmentation model in
presence of a class oracle. Specifically, the oracle replaces the label of
each mask by the label of the ground truth mask it has the best IoU with. This
evaluation allows to assess the shape and localization of the predictions but
not their class.

In Tab. 4, we compare the behavior of models pretrained with an image-level
versus spatially-aware objective only. We observe that models pretrained with
a global, image-level objective such as DeiT-III or MoCo-v3 tend to be better
on the classification aspect. By contrast, models trained with a spatially-
aware objective such as MAE or LOCA produce more spatially accurate
predictions. Overall, LOCA yields excellent locality and good class-level
understanding (while not beating representations learned with label
classification pretraining [59] on the pure classification axis). This results
in strong semantic segmentations which require both locality and semantic
features.

##### Label-efficient semantic segmentation.

In Tab. 3, we propose to evaluate transformer features when finetuning on
semantic segmentation with access to only a small amount of annotations. In
particular, following Hu  _et al_. [34], we randomly sample $1/2$, $1/4$,
$1/8$, $1/16$ and $1/32$ training images from ADE20k and use only those images
to finetune our model. In the $1/32$ split, as few as $630$ images from ADE20k
training set are used. We report the average over $5$ different folds [34].
The results are in Table 3. We observe that our spatially-aware pretraining
improves label-efficiency of semantic segmentation models. Interestingly, the
gap with previous works become larger when very few images are available for
finetuning.

Table 5:  Ablation study. We ablate different component of LOCA, one at a time. All variants are run during 100 epochs and we report their absolute and relative ($\Delta$) performance (mIoU) after finetuning on semantic segmentation.  | Variant | ADE20k | $\Delta$
---|---|---|---
| LOCA | 46.2 |
1 |  w/o positional embeddings | 45.9 |  $-$ 0.3
2 |  w/ 5 queries instead of 10 | 45.5 |  $-$ 0.7
3 |  w/o color data augmentation | $44.6$ |  $-$ 1.6
4 |  w/ 2 queries instead of 10 | 43.4 |  $-$ 2.8
5 |  w/o feature prediction loss | $42.5$ |  $-$ 3.7

###  4.3 Ablation Study

Table 5 shows an ablation study of several components of our model. The design
choices regarding the relative localization objective have been discussed in
details in Sec. 4.1. In Tab. 5, we see that adding the feature prediction loss
brings a boost of $+3.7$ (row 5). Besides, reducing the number of queries per
reference, for example 5 instead of 10, allows to speed up pretraining time by
$\times 1.6$ while inducing a loss of only $0.7\%$ in performance (see rows 4
and 2). Finally, we observe that our model is quite robust to the ablation of
position embeddings (row 1) or color jittering augmentation (row 3).

###  4.4 Preliminary scaling behavior

Figure 6: Scaling study. We report transfer performance on ADE20k for
different pretrained models. X-axis shows the size of the subset of
ImageNet-21k used for pretraining. Scaling both dataset size and model
capacity results in the best of transfer performance.

A premise of SSL is that it can in theory scale to arbitrary large datasets
since images don’t require any annotations. In this work, we have demonstrated
the potential of location-aware pretraining for a task such as semantic
segmentation. Since location-aware supervised pretraining is not feasible in
practice due to the huge cost of pixel-level annotations, we believe our self-
supervised spatial pretraining could be a good candidate for scaling. Our hope
is that scaling both dataset and model axes improves the performance on
downstream tasks requiring localization abilities, mirroring the trend of
image-level supervised pretrainings [72, 14].

Here, we propose a preliminary scaling study by pretraining on ImageNet-21k
dataset with LOCA with a Base and a Large models. Results are shown in Fig. 6.
Consistent with previous works on scaling image-level supervised ViTs [72], we
observe that we need to scale both datasets and model capacity to achieve the
best of performance. Interestingly, we observe that pretraining our method on
the full ImageNet-21k dataset gives better transfer performance on ADE20k than
using the highly curated ImageNet-1k split only (see $47.9$ vs $48.5$ in Tab.
7). This is not the case for all self-supervised learning methods as recently
observed by [36]. While these preliminary results give promising signal about
LOCA scalability, we note that ImageNet-21k is a relatively curated dataset
and we would still need to probe our model on large, uncurated data [36, 9,
57, 27].

##  5 Conclusion

In this work, we have studied localization as an alternative pretraining
strategy for Vision Transformers. We have shown that it results in spatially-
aware features that transfer competitively to several challenging semantic
segmentation benchmarks. We believe a promising direction for future work is
to combine localization objectives with global image-level ones [74, 7].
Finally, we have focused on semantic segmentation in this paper as it is
representative of tasks requiring spatial reasoning. However, the set of
visual task with localization is very large and we hope that our findings can
serve as a useful checkpoint for future studies beyond the scope of semantic
segmentation or even beyond the scope of still images.

##### Acknowledgement.

We thank Anurag Arnab, Lucas Beyer, Mostafa Dehghani, Ahmet Iscen, Thomas
Lucas, Matthias Minderer, Basil Mustafa, Xingyi Zhou as well as the entire
Ganesha team and Grand Vision group for their precious help, support and
discussions around this project.

## References

  * [1] Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katie Millican, Malcolm Reynolds, et al.  Flamingo: a visual language model for few-shot learning.  arXiv preprint arXiv:2204.14198, 2022.
  * [2] Yuki Markus Asano, Christian Rupprecht, and Andrea Vedaldi.  Self-labelling via simultaneous clustering and representation learning.  In ICLR, 2020.
  * [3] Mahmoud Assran, Mathilde Caron, Ishan Misra, Piotr Bojanowski, Florian Bordes, Pascal Vincent, Armand Joulin, Mike Rabbat, and Nicolas Ballas.  Masked siamese networks for label-efficient learning.  In ECCV, 2022.
  * [4] Mahmoud Assran, Mathilde Caron, Ishan Misra, Piotr Bojanowski, Armand Joulin, Nicolas Ballas, and Michael Rabbat.  Semi-supervised learning of visual features by non-parametrically predicting view assignments with support samples.  In ICCV, 2021.
  * [5] Alexei Baevski, Wei-Ning Hsu, Qiantong Xu, Arun Babu, Jiatao Gu, and Michael Auli.  Data2vec: A general framework for self-supervised learning in speech, vision and language.  arXiv preprint arXiv:2202.03555, 2022.
  * [6] Hangbo Bao, Li Dong, and Furu Wei.  Beit: Bert pre-training of image transformers.  arXiv preprint arXiv:2106.08254, 2021.
  * [7] Adrien Bardes, Jean Ponce, and Yann LeCun.  Vicregl: Self-supervised learning of local visual features.  In NeurIPS, 2021.
  * [8] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In ECCV, 2020.
  * [9] Mathilde Caron, Piotr Bojanowski, Julien Mairal, and Armand Joulin.  Unsupervised pre-training of image features on non-curated data.  In ICCV, 2019.
  * [10] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  In NeurIPS, 2020.
  * [11] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In ICCV, 2021.
  * [12] Joao Carreira and Andrew Zisserman.  Quo vadis, action recognition? a new model and the kinetics dataset.  In CVPR, pages 6299–6308, 2017.
  * [13] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  preprint arXiv:2002.05709, 2020.
  * [14] Xi Chen, Xiao Wang, Soravit Changpinyo, AJ Piergiovanni, Piotr Padlewski, Daniel Salz, Sebastian Goodman, Adam Grycner, Basil Mustafa, Lucas Beyer, et al.  Pali: A jointly-scaled multilingual language-image model.  arXiv preprint arXiv:2209.06794, 2022.
  * [15] Xinlei Chen, Saining Xie, and Kaiming He.  An empirical study of training self-supervised vision transformers.  In ICCV, 2021.
  * [16] Yubei Chen, Adrien Bardes, Zengyi Li, and Yann LeCun.  Intra-instance vicreg: Bag of self-supervised image patch embedding.  arXiv preprint arXiv:2206.08954, 2022.
  * [17] Yingyi Chen, Xi Shen, Yahui Liu, Qinghua Tao, and Johan AK Suykens.  Jigsaw-vit: learning jigsaw puzzles in vision transformer.  arXiv preprint arXiv:2207.11971, 2022.
  * [18] Jang Hyun Cho, Utkarsh Mall, Kavita Bala, and Bharath Hariharan.  Picie: Unsupervised semantic segmentation using invariance and equivariance in clustering.  In CVPR, 2021.
  * [19] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In CVPR, 2016.
  * [20] Zhigang Dai, Bolun Cai, Yugeng Lin, and Junying Chen.  Up-detr: Unsupervised pre-training for object detection with transformers.  In CVPR, 2021.
  * [21] Mostafa Dehghani, Alexey Gritsenko, Anurag Arnab, Matthias Minderer, and Yi Tay.  Scenic: A jax library for computer vision research and beyond.  In CVPR, 2022.
  * [22] Carl Doersch, Abhinav Gupta, and Alexei A Efros.  Unsupervised visual representation learning by context prediction.  In ICCV, 2015.
  * [23] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  preprint arXiv:2010.11929, 2020.
  * [24] Alexey Dosovitskiy, Philipp Fischer, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox.  Discriminative unsupervised feature learning with exemplar convolutional neural networks.  TPAMI, 2016.
  * [25] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman.  The pascal visual object classes (voc) challenge.  IJCV, 2010.
  * [26] Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  arXiv preprint arXiv:1803.07728, 2018.
  * [27] Priya Goyal, Mathilde Caron, Benjamin Lefaudeux, Min Xu, Pengchao Wang, Vivek Pai, Mannat Singh, Vitaliy Liptchinsky, Ishan Misra, Armand Joulin, and Piotr Bojanowski.  Self-supervised pretraining of visual features in the wild.  arXiv preprint arXiv:2103.01988, 2021.
  * [28] Priya Goyal, Dhruv Mahajan, Abhinav Gupta, and Ishan Misra.  Scaling and benchmarking self-supervised visual representation learning.  In ICCV, 2019.
  * [29] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko.  Bootstrap your own latent: A new approach to self-supervised learning.  In NeurIPS, 2020.
  * [30] Mark Hamilton, Zhoutong Zhang, Bharath Hariharan, Noah Snavely, and William T Freeman.  Unsupervised semantic segmentation by distilling feature correspondences.  In ICLR, 2022.
  * [31] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  In CVPR, 2022.
  * [32] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In CVPR, 2020.
  * [33] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In ICCV, 2017.
  * [34] Hanzhe Hu, Fangyun Wei, Han Hu, Qiwei Ye, Jinshi Cui, and Liwei Wang.  Semi-supervised semantic segmentation via adaptive equalization learning.  NeurIPS, 2021.
  * [35] Dahun Kim, Donghyeon Cho, Donggeun Yoo, and In So Kweon.  Learning image representations by completing damaged jigsaw puzzles.  In WACV, 2018.
  * [36] Skanda Koppula, Yazhe Li, Evan Shelhamer, Andrew Jaegle, Nikhil Parthasarathy, Relja Arandjelovic, João Carreira, and Olivier Hénaff.  Where should i spend my flops? efficiency evaluations of visual pre-training methods.  arXiv preprint arXiv:2209.15589, 2022.
  * [37] Hsin-Ying Lee, Jia-Bin Huang, Maneesh Singh, and Ming-Hsuan Yang.  Unsupervised representation learning by sorting sequences.  In ICCV, 2017.
  * [38] Yanghao Li, Hanzi Mao, Ross Girshick, and Kaiming He.  Exploring plain vision transformer backbones for object detection.  arXiv preprint arXiv:2203.16527, 2022.
  * [39] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In ECCV, 2014.
  * [40] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie.  A convnet for the 2020s.  In CVPR, 2022.
  * [41] Ilya Loshchilov and Frank Hutter.  Fixing weight decay regularization in adam.  2018\.
  * [42] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  arXiv preprint arXiv:1301.3781, 2013.
  * [43] Matthias Minderer, Alexey Gritsenko, Austin Stone, Maxim Neumann, Dirk Weissenborn, Alexey Dosovitskiy, Aravindh Mahendran, Anurag Arnab, Mostafa Dehghani, Zhuoran Shen, et al.  Simple open-vocabulary object detection with vision transformers.  arXiv preprint arXiv:2205.06230, 2022.
  * [44] Roozbeh Mottaghi, Xianjie Chen, Xiaobai Liu, Nam-Gyu Cho, Seong-Whan Lee, Sanja Fidler, Raquel Urtasun, and Alan Yuille.  The role of context for object detection and semantic segmentation in the wild.  In CVPR, 2014.
  * [45] T Nathan Mundhenk, Daniel Ho, and Barry Y Chen.  Improvements to context based self-supervised learning.  In CVPR, 2018.
  * [46] Mehdi Noroozi and Paolo Favaro.  Unsupervised learning of visual representations by solving jigsaw puzzles.  In ECCV, 2016.
  * [47] Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros.  Context encoders: Feature learning by inpainting.  In CVPR, 2016.
  * [48] Pedro O Pinheiro, Amjad Almahairi, Ryan Y Benmaleck, Florian Golemo, and Aaron Courville.  Unsupervised learning of dense visual representations.  2020\.
  * [49] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  2021\.
  * [50] Byungseok Roh, Wuhyun Shin, Ildoo Kim, and Sungwoong Kim.  Spatially consistent representation learning.  In CVPR, 2021.
  * [51] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C Berg, and Li Fei-Fei.  Imagenet large scale visual recognition challenge.  IJCV, 2015.
  * [52] Rodrigo Santa Cruz, Basura Fernando, Anoop Cherian, and Stephen Gould.  Deeppermnet: Visual permutation learning.  In CVPR, 2017.
  * [53] Mert Bulent Sariyildiz, Yannis Kalantidis, Karteek Alahari, and Diane Larlus.  Improving the generalization of supervised models.  arXiv:2206.15369, 2022.
  * [54] Oriane Siméoni, Gilles Puy, Huy V Vo, Simon Roburin, Spyros Gidaris, Andrei Bursuc, Patrick Pérez, Renaud Marlet, and Jean Ponce.  Localizing objects with self-supervised transformers and no labels.  arXiv preprint arXiv:2109.14279, 2021.
  * [55] Andreas Steiner, Alexander Kolesnikov, Xiaohua Zhai, Ross Wightman, Jakob Uszkoreit, and Lucas Beyer.  How to train your vit? data, augmentation, and regularization in vision transformers.  arXiv preprint arXiv:2106.10270, 2021.
  * [56] Robin Strudel, Ricardo Garcia, Ivan Laptev, and Cordelia Schmid.  Segmenter: Transformer for semantic segmentation.  In ICCV, 2021.
  * [57] Yonglong Tian, Olivier J Henaff, and Aäron van den Oord.  Divide and contrast: Self-supervised learning from uncurated data.  In ICCV, 2021.
  * [58] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  preprint arXiv:2012.12877, 2020.
  * [59] Hugo Touvron, Matthieu Cord, and Hervé Jégou.  Deit iii: Revenge of the vit.  arXiv preprint arXiv:2204.07118, 2022.
  * [60] Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, and Luc Van Gool.  Unsupervised semantic segmentation by contrasting object mask proposals.  In ICCV, 2021.
  * [61] Xinlong Wang, Rufeng Zhang, Chunhua Shen, Tao Kong, and Lei Li.  Dense contrastive learning for self-supervised visual pre-training.  In CVPR, 2021.
  * [62] Chen Wei, Haoqi Fan, Saining Xie, Chao-Yuan Wu, Alan Yuille, and Christoph Feichtenhofer.  Masked feature prediction for self-supervised visual pre-training.  In CVPR, 2022.
  * [63] Yixuan Wei, Han Hu, Zhenda Xie, Zheng Zhang, Yue Cao, Jianmin Bao, Dong Chen, and Baining Guo.  Contrastive learning rivals masked image modeling in fine-tuning via feature distillation.  arXiv preprint arXiv:2205.14141, 2022.
  * [64] Philippe Weinzaepfel, Vincent Leroy, Thomas Lucas, Romain Brégier, Yohann Cabon, Vaibhav Arora, Leonid Antsfeld, Boris Chidlovskii, Gabriela Csurka, and Jérôme Revaud.  Croco: Self-supervised pre-training for 3d vision tasks by cross-view completion.  In NeurIPS, 2022.
  * [65] Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin.  Unsupervised feature learning via non-parametric instance discrimination.  In CVPR, 2018.
  * [66] Tete Xiao, Colorado J Reed, Xiaolong Wang, Kurt Keutzer, and Trevor Darrell.  Region similarity representation learning.  In ICCV, 2021.
  * [67] Zhenda Xie, Yutong Lin, Zheng Zhang, Yue Cao, Stephen Lin, and Han Hu.  Propagate yourself: Exploring pixel-level consistency for unsupervised visual representation learning.  In CVPR, 2021.
  * [68] Zhenda Xie, Zheng Zhang, Yue Cao, Yutong Lin, Jianmin Bao, Zhuliang Yao, Qi Dai, and Han Hu.  Simmim: A simple framework for masked image modeling.  In CVPR, 2022.
  * [69] Jiahui Yu, Zirui Wang, Vijay Vasudevan, Legg Yeung, Mojtaba Seyedhosseini, and Yonghui Wu.  Coca: Contrastive captioners are image-text foundation models.  arXiv preprint arXiv:2205.01917, 2022.
  * [70] Lu Yuan, Dongdong Chen, Yi-Ling Chen, Noel Codella, Xiyang Dai, Jianfeng Gao, Houdong Hu, Xuedong Huang, Boxin Li, Chunyuan Li, et al.  Florence: A new foundation model for computer vision.  arXiv preprint arXiv:2111.11432, 2021.
  * [71] Shuangfei Zhai, Navdeep Jaitly, Jason Ramapuram, Dan Busbridge, Tatiana Likhomanenko, Joseph Yitan Cheng, Walter Talbott, Chen Huang, Hanlin Goh, and Joshua Susskind.  Position prediction as an effective pretraining strategy.  2022\.
  * [72] Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer.  Scaling vision transformers.  In CVPR, year=2022.
  * [73] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba.  Scene parsing through ade20k dataset.  In CVPR, 2017.
  * [74] Jinghao Zhou, Chen Wei, Huiyu Wang, Wei Shen, Cihang Xie, Alan Yuille, and Tao Kong.  ibot: Image bert pre-training with online tokenizer.  arXiv preprint arXiv:2111.07832, 2021.
  * [75] Xingyi Zhou, Dequan Wang, and Philipp Krähenbühl.  Objects as points.  arXiv preprint arXiv:1904.07850, 2019.
  * [76] Adrian Ziegler and Yuki M Asano.  Self-supervised learning of object parts for semantic segmentation.  In CVPR, 2022.

## Appendix

###  A Pretraining with LOCA

####  A.1 Details on the patch feature prediction loss

In this section, we provide more details on the patch feature prediction loss.
It can be seen as a “patch version” of the self-supervised loss used in the
MSN framework [3]. Specifically, as mentioned in Section 3, we note
$\bm{Z}_{q}\in\mathbb{R}^{d\times N_{q}}$ (resp.
$\bm{Z}_{ref}\in\mathbb{R}^{d\times N_{ref}}$), the output patch
representation matrix of the query (resp. reference) view. We project the
output patch representations with a 2-layer multilayer perceptron (MLP)
projection head, resulting in features
$\bm{\tilde{Z}}_{q}\in\mathbb{R}^{\tilde{d}\times N_{q}}$ (resp.
$\bm{\tilde{Z}}_{ref}\in\mathbb{R}^{\tilde{d}\times N_{ref}}$) with
$\tilde{d}=256$ in our experiments. We note
$\bm{Q}\in\mathbb{R}^{\tilde{d}\times K}$ a set of $K$ learnable prototypes,
each of dimension $\tilde{d}$. In practice we use $K=4096$. We compute a
distribution based on the similarity between these prototypes and each patch
output representation. Specifically, the prediction of the $j^{th}$ patch
feature in the query $\bm{\tilde{Z}}_{q}^{j}$ can be written:

$\bm{p}_{q}^{j}=\text{softmax}(\bm{\tilde{Z}}_{q}^{j}.\bm{Q}/\tau_{q})$

where $\tau_{q}$ is a temperature parameter set to $0.1$ and both
$\bm{\tilde{Z}}_{q}^{j}$ and $\bm{Q}$ are L2-normalized. The goal of the
network is to predict similar distributions for patches in the same location
in the query and reference views. More precisely, the target distribution for
prediction $\bm{p}_{q}^{j}$ is that of the projected corresponding patch
representation of the reference view:

$\bm{p}_{ref}^{i}=\text{softmax}(\bm{\tilde{Z}}_{ref}^{i}.\bm{Q}/\tau_{ref})$

with $i=\bm{h}(j)$ and $\tau_{ref}<\tau_{q}$ (in practice we use
$\tau_{ref}=0.05$). Overall, the patch feature prediction objective that we
minimize is:

$\frac{1}{|\Omega|}\sum_{j\in\Omega}H(\bm{p}_{ref}^{\bm{h}(j)},\bm{p}_{q}^{j})$

where $H$ is the cross-entropy function and $\Omega$ is the set of patch
position in the query that has an intersection with the reference (i.e. where
$\bm{h}$ is defined). The parameters of the branch processing the query views
are updated by minibatch gradient descent. The parameters of the branch
processing the reference views are updated via an exponential moving average
of the encoder parameters processing the query views. We regularize this loss
function with the mean entropy maximization (me-max) protocol [3]. More
precisely in order to encourage the network to use the full set of prototypes
$\bm{Q}$ we maximize the entropy of the average prediction over all the
patches of all the query views in a minibatch.

####  A.2 Implementation Details

We train our models with a base learning rate of $0.001$ (linearly ramped up
during the first $15$ epochs before cosine decay), a batch size of $1024$ and
a weight decay of $0.1$ with adamw optimizer [41]. Models for ablations and
analyses (in Sec. 4.1 and 4.3) are trained during 100 epochs while checkpoints
in Sec. 4.2 and 4.4 are trained for 600 epochs. We use $\eta=0.8$ for masking.
For data augmentation we apply random resized crop, horizontal flipping and
color jittering (following the parameters from BYOL [29]). Momentum parameter
is set to $0.996$ and increased with a cosine schedule to $1$ during training
[29, 74, 11]. We typically use $10$ queries per reference view. Results are
reported with the weights from the momentum branch [11, 74].

###  B Transfer to Semantic Segmentation

####  B.1 Datasets

##### ADE20K [73].

It is a dataset containing scenes with fine-grained labels with 150 semantic
classes and is one of the most challenging semantic segmentation datasets. The
training split is composed of 20,210 images. We report results on the
validation set, composed of 2,000 images.

##### Pascal Context [44].

The training split is composed of 4,998 images with 59 semantic classes and a
background class (hence a total of 60 classes). The validation set has 5,105
images.

##### Pascal VOC [25].

This dataset has a training set of 10,582 images and counts 21 classes (with
background class). We report results on the validation set, it has 1,449
images.

##### Cityscapes [19].

The dataset contains 5,000 images from 50 different cities. We consider the
setup with 19 classes. There are 2,975 images in the training set, 500 images
in the validation set and 1,525 images in the test set (which we do not use).
We report results on the validation set.

Table 6:  Comparison to previous results with UperNet. We report mean IoU for semantic segmentation on the validation set of ADE20k for different self-supervised and supervised representation learning methods. All models use the popular ViT-Base/16 architecture and are pre-trained on ImageNet-1k before being end-to-end finetuned on ADE20k. Results are reported in single-scale mode.  Method | ADE20k
---|---
Supervised on ImageNet-1k
Supervised used in MAE [31] | 47.4
DeiT-III [59] | 49.3
Self-supervised on ImageNet-1k without labels
DINO [11] | 47.2
SimMIM [68] | 47.6
FD-DINO [63] | 47.7
MAE [31] | 48.1
data2vec [5] | 48.2
iBOT [74] | 48.4
LOCA (Ours) | 48.5

####  B.2 Evaluation protocol

We precisely follow the experimental setup of Segmenter [56] for end-to-end
finetuning of Vision Transformer with linear decoder. For data augmentation
during training we apply normalization, random resizing of the image to a
ratio between 0.5 and 2.0, photometric jittering and random horizontal
flipping. We randomly crop images and use padding to preserve aspect ratio. We
use the $512\times 512$ resolution for ADE20k, Pascal VOC and Pascal Context
and $768\times 768$ on Cityscapes. On ADE20k, we train for 127 epochs with
minibatch size of 16 (resulting in 160k iterations). On Pascal, we train for
256 epochs with minibatch size of 16 (resulting in 80k iterations). On
Cityscapes, we train for 215 epochs with minibatch size of 8 (resulting in 80k
iterations). We use the “poly” learning rate decay schedule and sweep the base
learning rate in $\\{1e-4,3e-4,8e-4\\}$ for all of our runs. Weight-decay is
kept fixed at $0.01$. At evaluation time, we use the sliding-window mechanism
with window resolution matching the resolution used during training (i.e.
$512\times 512$ for Pascal and ADE20k and $768\times 768$ for Cityscapes) to
handle varying image sizes during inference. Table 3 row 6 in [56] reports
$48.06$ mIoU (single scale) for finetuning from ViT-B/16 AugReg checkpoint
[55]. Average of 6 runs in the same setup in our codebase gives $47.6\pm 0.4$
mIoU.

Table 7:  Scaling behavior on ImageNet-21k. We report performance (mean IoU on ADE20k - single scale evaluation) for different pretrained LOCA models. “Rand-x” means that we take a random subset of size x in ImageNet-21k. ‘INet-1k” means that we use the ImageNet-1k dataset only for pretrainng.  Method / Split | Rand-130k | Rand-1.3M | Full 13M | INet-1k
---|---|---|---|---
ViT-Base | 41.4 | 46.9 | 48.5 | 47.9
ViT-Large | 39.1 | 48.5 | 52.5 | -

###  C Additional Results

Table 8:  Object detection with ViTDet. We report Average Precision for object detection with CenterNet [75] and ViTDet adaptation protocol [38] on COCO dataset [39]. We follow the standard training schedule of 100 epochs. Architecture is ViT-B for all runs and pretraining data is ImageNet-1k.  Method | AP | AP50 | AP75
---|---|---|---
DINO [11] | 48.5 | 68.9 | 52.8
MoCo-v3 [15] | 48.8 | 69.4 | 53.0
Supervised - DeiT-III [59] | 49.0 | 69.5 | 53.4
LOCA (Ours) | 49.6 | 70.0 | 54.1
iBOT [74] | 49.9 | 70.6 | 54.3
MAE [31] | 52.5 | 71.9 | 57.5

##### UperNet decoder.

In the main paper, we report results for semantic segmentation with end-to-end
finetuning using the linear decoder from Segmenter [56]. In Table 6, we
propose to compare to previously published results with the UperNet decoder
[56]. Note that UperNet is a much more complex decoder than linear with $5300$
times more parameters (76.8M parameters for UperNet versus only 14k for
linear). As a matter of fact, UperNet decoder alone is composed of almost the
same number of parameters than the ViT-Base backbone. Therefore, adapting a
ViT-Base to semantic segmentation with UperNet results in doubling the total
parameter count of the model and training from scratch half of these
parameters. Note that the reported $48.4$mIoU performance for iBOT in Table 6
differs from the reported number in the iBOT paper [74] because recent
correspondence with the authors has let us know that $50.0$ is the best of 5
runs while $48.4$ is the average. Following previous works, we use the 160,000
steps schedule (i.e. we use a minibatch size of 16 and train during 127
epochs). We observe in Table 6 that LOCA still performs competitively when
evaluating in this setting.

##### Scaling behavior.

We report in Table 7 the corresponding numbers for Figure 6 of the main paper.

##### Object detection with ViTDet.

Finally, we propose to evaluate LOCA features when transferring to object
detection. We consider the COCO dataset [39] and use the CenterNet detector
[75] on a ViTDet backbone [38]. We observe in Table 8 that LOCA is competitive
on this benchmark with other strong representation learning methods such as
supervised DeiT-III [59] or iBOT [74]. Remarkably, MAE features are excellent
on this benchmark and outperform all other backbones by a significant margin.
Note that ViTDet protocol has been developed for MAE features and it is
interesting to see that it does not seem to transfer well to other pretrained
weights. We leave further investigation on transfer to object detection for
future work.

###  D Visualizations

In this section, we visualize the output of the pretraining task.
Specifically, in Figure 7, we visualize query location prediction for
different LOCA models. We compare models pretrained with different masking
rates: (i) $\eta=0$: no masking, the reference is entirely visible to the
query; (ii) $\eta=0.8$: default masking rate, only 40 reference patch tokens
are visible to the query; (iii) $\eta=1$: full masking, the reference is
invisible to the query.

In the first rows of Figure 7, we show examples where the network seems to
effectively solve the task by relative location. In those cases, we observe
that LOCA trained with masking rate $\eta=0.8$ manages to locate the query
based on the patches visible from the reference. For example we see that the
network successfully manages to locate the leash joint based on seeing the
patch representations of the head of the dog, or to locate the neck of the
lizard based on the visible patches of its head. By contrast, the network
which does not see the reference at all (i.e. $\eta=1$) cannot successfully
locate the query in those cases. Interestingly, we see that in some cases,
this network ($\eta=1$) can still locate the query by learning where things
are typically located in natural images. For example, we observe in Figure 7
that by recognizing a part such as “ear” it makes a guess that it is more
likely to be at the top of the image rather than at the bottom. However, it
cannot guess if it is left or right because we apply random horizontal flips
between query and reference during training and so this patch is as likely to
occur at the right than at the left of the image.

Lastly, we observe that the network trained with full access to the reference
($\eta=0$) can almost always locate the query. This is because it can rely on
low-level cues such as edge consistency or salient points. The last rows of
Figure 7 illustrate this phenomenon.

query |  $\eta=0$ |  $\eta=0.8$ | $\eta=1$ |  query $\eta=0$ |  $\eta=0.8$ |  $\eta=1$
---|---|---|---|---|---|---
Example of cases where $\eta=0.8$ succeeds and $\eta=1$ fails. The network
relies on relative location.
|
|
|
Example of cases where the query location can easily be inferred from looking
at query alone.
|
|
Example of cases where the network relies on low-level cues. Only the variant
with $\eta=0$ succeeds.
|
|
Figure 7:  Visualizing LOCA’s predictions. The query location is shown in blue
in the reference and LOCA predictions are shown in red. Columns correspond to
different reference masking rates and we show only patches visible to the
query when it makes its prediction. Displayed images are not seen during
training. See discussion in Section D.