$\displaystyle=\frac{\sqrt{\Delta}}{2(-A)}\sin\left(\sqrt{-A}\frac{\lambda}{L}-\arcsin\left(\frac{B}{\sqrt{\Delta}}\right)\right)-\frac{B}{2A}$
(B.32) $\displaystyle w(\lambda)$
$\displaystyle=\frac{\sqrt{P_{y}^{2}P_{z}^{2}+P_{x}^{2}(2P_{z}^{2}-1)}}{2P_{z}^{2}-1}\sin\left[\sqrt{2P_{z}^{2}-1}\frac{\lambda}{L}-\arcsin\left(\frac{P_{y}P_{z}}{\sqrt{P_{y}^{2}P_{z}^{2}+P_{x}^{2}(2P_{z}^{2}-1)}}\right)\right]-\frac{P_{y}P_{z}}{2P_{z}^{2}-1}$
(B.33) $\displaystyle x(\lambda)$
$\displaystyle=L\sinh^{-1}\left[w(\lambda)\right]\,.$ (B.34)

Final geodesics.

We can now write the geodesics for the $\widetilde{\text{U}(\mathds{H}^{2})}$
geometry in a compact form.

$\displaystyle x(\lambda)$ $\displaystyle=L\sinh^{-1}\left[w(\lambda)\right]$
(B.35) $\displaystyle y(\lambda)$ $\displaystyle=\int{\rm
d}\lambda\;\frac{-P_{z}w+P_{y}}{1+w^{2}}$ (B.36) $\displaystyle z(\lambda)$
$\displaystyle=\int{\rm
d}\lambda\;\frac{2P_{z}w^{2}-P_{y}w+P_{z}}{1+w^{2}}\,,$ (B.37)

where $w$ is determined by the value of $P_{z}$,

$\displaystyle\\!\\!\\!w(\lambda)=\begin{cases}\frac{P_{x}}{\sqrt{1-2P_{z}^{2}}}\sinh\left(\sqrt{1-2P_{z}^{2}}\frac{\lambda}{L}\right)+\frac{P_{y}P_{z}}{1-2P_{z}^{2}}\left[\cosh\left(\sqrt{1-2P_{z}^{2}}\frac{\lambda}{L}\right)-1\right]\,,&\text{if
}P_{z}^{2}<1/2\\\
P_{x}\frac{\lambda}{L}+\frac{P_{y}P_{z}}{2}\frac{\lambda^{2}}{L^{2}}\,,&\text{if
}P_{z}^{2}=1/2\\\
\frac{\sqrt{P_{y}^{2}P_{z}^{2}+P_{x}^{2}(2P_{z}^{2}-1)}}{2P_{z}^{2}-1}\sin\\!\left[\sqrt{2P_{z}^{2}-1}\frac{\lambda}{L}-\arcsin\left(\frac{P_{y}P_{z}}{\sqrt{P_{y}^{2}P_{z}^{2}+P_{x}^{2}(2P_{z}^{2}-1)}}\right)\right]-\frac{P_{y}P_{z}}{2P_{z}^{2}-1}\,,&\text{if
}1/2<P_{z}^{2}<1,\end{cases}$ (B.38)

and we have an additional constraint that $P_{x}^{2}+P_{y}^{2}+P_{z}^{2}=1$.
The fact that these expressions are not smooth with respect to the initial
velocity $\hat{P}$ should not worry us. This features exists within many other
dynamical systems, c.f. elliptical, parabolic and hyperbolic trajectories on
orbital mechanics.

To visualise these geodesics, Figures 30, 30 and 30 show the trajectory of the
above geodesics along selected directions emanating from the origin. The
curved red, green and blue surfaces traced by the set of geodesics with an
initial direction orthogonal to the $x$-, $y$\- and $z$-direction
respectively. The magenta, cyan and yellow surfaces are traced by sets of
geodesics with an initial direction in a small cone around the $x$-, $y$\- and
$z$-direction respectively. The grey surfaces are similar, but are cones
around initial directions with $|P_{x}|=|P_{y}|=|P_{z}|$. To give a clearer
visualisation of the effects of curvature, we have increased its effects by
drawing the surfaces from distance $\lambda=0$ to distance
$\lambda=5\eta_{*}$.

Figure 28: Geodesics of the $\widetilde{\text{U}(\mathds{H}^{2})}$ geometry.
Note that the cyan cone is stretched horizontally, the magenta cone is
stretched more harshly vertically, while the yellow cone is largely
unaffected.

Figure 29: The same visualisation, viewed from a higher angle to show a
clockwise twisting effect of geodesics about the $z$-axis of the geometry; a
similar counter-clockwise twist can be observed around the $y$-axis in the
first plot.

Figure 30: However, around $x$-axis of the geometry geodesics are skewed
towards a diagonal direction rather than twisted.

##  Appendix C Geodesics of the Nil geometry

The Nil case starts along the same general lines from spatial sections of the
Nil-metric (2.18),

$\displaystyle{\rm d}\Sigma_{3}^{2}={\rm
d}x^{2}+\left(1+\frac{x^{2}}{L^{2}}\right){\rm d}y^{2}+{\rm
d}z^{2}-\frac{2x}{L}\ {\rm d}y{\rm d}z\,.$ (C.1)

Note that we have written $L=1/\sqrt{-\kappa}$ for notational convenience. Nil
has two obvious Killing vectors, $\partial_{y}$ and $\partial_{z}$, which lead
two conserved quantities and therefore to two first-order equations,

$\displaystyle Q_{1}$
$\displaystyle=\dot{y}\left(1+\frac{x^{2}}{L^{2}}\right)-x\dot{z}/L$
$\displaystyle\longrightarrow$ $\displaystyle\dot{y}$
$\displaystyle=Q_{1}+Q_{2}x/L.$ (C.2) $\displaystyle Q_{2}$
$\displaystyle=\dot{z}-x\dot{y}/L$ $\displaystyle\longrightarrow$
$\displaystyle\dot{z}$
$\displaystyle=Q_{2}\left(1+\frac{x^{2}}{L^{2}}\right)+Q_{1}x/L\,.$ (C.3)

Unfortunately, the Nil equivalent of (A.5) does not allow for separation of
variables and we must solve the geodesic equation for $x$ directly,

$\displaystyle\ddot{x}(\lambda)+\frac{Q_{2}^{2}}{L^{2}}\left(x(\lambda)+\frac{Q_{1}L}{Q_{2}}\right)=0\,.$
(C.4)

This is the equation for a (shifted) simple harmonic oscillator with angular
frequency $\omega=Q_{2}/L$ and it is solved by,

$\displaystyle
x(\lambda)+\frac{Q_{2}L}{Q_{1}}=C_{1}\cos\left(\omega\lambda\right)+C_{2}\sin\left(\omega\lambda\right)\,.$
(C.5)

From this result it is a straightforward, if tedious, exercise to derive a
full solution for $y$ and $z$. We will omit the details of this calculation
and skip directly to the solution in a convenient form,

$\displaystyle x(\lambda)$
$\displaystyle=x_{0}+\frac{P_{x}}{\omega}\sin(\omega\lambda)-\frac{P_{y}}{\omega}\Big{[}1-\cos(\omega\lambda)\Big{]}$
(C.6) $\displaystyle y(\lambda)$
$\displaystyle=y_{0}+\frac{P_{y}}{\omega}\sin(\omega\lambda)+\frac{P_{x}}{\omega}\Big{[}1-\cos(\omega\lambda)\Big{]}$
(C.7) $\displaystyle z(\lambda)$
$\displaystyle=z_{0}+L\omega\lambda+\frac{x_{0}P_{y}}{L\omega}\sin(\omega\lambda)+\frac{P_{x}^{2}}{4L\omega^{2}}\Big{[}\sin(2\omega\lambda)-2\omega\lambda\Big{]}+\frac{P_{y}^{2}}{4L\omega^{2}}\Big{[}2\omega\lambda-4\sin(\omega\lambda)+\sin(2\omega\lambda)\Big{]}$
(C.8)
$\displaystyle+\frac{2P_{x}}{L\omega^{2}}\Big{[}x_{0}\omega+P_{y}\cos(\omega\lambda)\Big{]}\sin^{2}\left(\frac{\omega\lambda}{2}\right)\,,$
(C.9)

where we have chosen the $Q$s, $C$s and the constants arising from integrating
(C.2) and (C.3) so that $x^{i}(0)=x^{i}_{0}$ and $\dot{x}^{i}(0)=P_{i}$, and
the angular frequency is defined as,
$\omega=\dfrac{LP_{z}-P_{y}x_{0}}{L^{2}}$.

Radial geodesics.

To make these geodesics radial, we set $x_{0}=y_{0}=z_{0}=0$. The angular
frequency now simplifies to $\omega=P_{z}/L$ and we may write exact
expressions for the geodesics as

$\displaystyle x(\lambda)$
$\displaystyle=\frac{LP_{x}}{P_{z}}\sin\left(P_{z}\frac{\lambda}{L}\right)-\frac{LP_{y}}{P_{z}}\left[1-\cos\left(P_{z}\frac{\lambda}{L}\right)\right]$
(C.10) $\displaystyle y(\lambda)$
$\displaystyle=\frac{LP_{y}}{P_{z}}\sin\left(P_{z}\frac{\lambda}{L}\right)+\frac{LP_{x}}{P_{z}}\left[1-\cos\left(P_{z}\frac{\lambda}{L}\right)\right]$
(C.11) $\displaystyle z(\lambda)$
$\displaystyle=P_{z}\lambda+\frac{P_{x}^{2}}{4P_{z}^{2}}\left[2P_{z}\lambda-L\sin\left(\frac{2P_{z}\lambda}{L}\right)\right]+\frac{P_{y}^{2}}{4P_{z}^{2}}\left[2P_{z}\lambda-4L\sin\left(\frac{P_{z}\lambda}{L}\right)+L\sin\left(\frac{2P_{z}\lambda}{L}\right)\right]$
(C.12)
$\displaystyle+\frac{2LP_{x}P_{y}}{P_{z}^{2}}\cos\left(\frac{P_{z}\lambda}{L}\right)\sin^{2}\left(\frac{P_{z}\lambda}{2L}\right)\,.$
(C.13)

Given these expressions, it is productive to reconsider equation (A.5), which
now reads

$\displaystyle 1=\epsilon=P_{x}^{2}+P_{y}^{2}+P_{z}^{2}.$ (C.14)

In effect, this tells us that if we choose initial velocity vector
$\vec{P}=(P_{x},P_{y},P_{z})$ to be of unit length, then $\lambda$
parameterises geodesic distance along the curve. Hence, proper (radial)
distance is again given by $\ell_{\text{rad}}=\lambda_{f}\equiv\rho_{0}$.

To visualise these geodesics we have again plotted select geodesics of this
geometry in Figures 33, 33 and 33. For a description of the surfaces, please
refer to the previous appendix. As in Appendix C, we have augmented the
effects of curvature for a clearer visualisation. For this geometry it was
sufficient to draw the surfaces from distance $\lambda=0$ to distance
$\lambda=2.5\eta_{*}$.

Figure 31: Geodesics of the Nil geometry. Like the
$\widetilde{\text{U}(\mathds{H}^{2})}$ geometry, the cyan cone is stretched
horizontally, the magenta cone is stretched more harshly vertically, while the
yellow cone is largely unaffected.

Figure 32: The same visualisation, viewed from a higher angle to show a
counter-clockwise twisting effect of geodesics about the $z$-axis of the
geometry; a similar twist can be observed around the $y$-axis in the first
plot.

Figure 33: However, around $x$-axis of the geometry geodesics are skewed
towards a diagonal direction rather than twisted. Note that the diagonal
points the other way when compared to $\widetilde{\text{U}(\mathds{H}^{2})}$.

##  Appendix D Geodesics of the Solv geometry

We again start from metric introduced in (2.20) and look at spatial sections,

${\rm d}\Sigma_{3}^{2}={\rm e}^{2z/L}\ {\rm d}x^{2}+{\rm e}^{-2z/L}\ {\rm
d}y^{2}+{\rm d}z^{2}\,.$ (D.1)

This metric admits three Killing vectors, the first is $K_{1}={\rm
e}^{2z/L}\partial_{x}$, the second $K_{2}={\rm e}^{-2z/L}\partial_{y}$ and the
third $K_{3}=-\tfrac{x}{L}{\rm e}^{2z/L}\partial_{x}\ +\ \tfrac{y}{L}{\rm
e}^{-2z/L}\partial_{y}\ +\ \partial_{z}$. These lead to the following first-
order equations,

$\displaystyle\dot{x}$ $\displaystyle=$ $\displaystyle P_{x}{\rm e}^{-2z/L}$
(D.2) $\displaystyle\dot{y}$ $\displaystyle=$ $\displaystyle P_{y}{\rm
e}^{2z/L}$ (D.3) $\displaystyle\dot{z}$ $\displaystyle=$ $\displaystyle
P_{z}+P_{x}\frac{x}{L}-P_{y}\frac{y}{L}\,.$ (D.4)

Unlike in the previous cases, it is hard to solve this system exactly 202020
Upon inserting equations (D.2–D.3) into equations (D.1) one obtains,
$1=\frac{P_{x}^{2}}{{\rm e}^{2z/L}}+\frac{P_{y}^{2}}{{\rm
e}^{-2z/L}}+\dot{z}^{2}\;\Longrightarrow\int\frac{{\rm d}z}{\sqrt{1-{\rm
e}^{-2z/L}P_{x}^{2}-{\rm e}^{2z/L}P_{y}^{2}}}=\lambda\,.$ (D.5) A convenient
variable is $w=e^{z/L}$, in terms of which this equation simplifies to,
$\int\frac{{\rm
d}w}{\sqrt{w^{2}-P_{x}^{2}-w^{4}P_{y}^{2}}}=\frac{\lambda}{L}\,.$ (D.6) This
is an elliptic integral, and so its solution can be expressed in terms of
elliptic functions. Instead of studying these general solutions, we opt for a
much simpler expansion in powers of $1/L$, with the results given in equations
(D.10–D.12).
and so we will opt for a perturbative approach.

Radial geodesics.

We can write $\vec{x}=\sum_{i=0}^{n}\vec{x}_{i}L^{-i}$ and expand the system
above to a desired power $L^{n}$. To linear order, for example, this would
look like

$\displaystyle\dot{x}$ $\displaystyle=P_{x}\big{(}1-2z/L\big{)}$ (D.7)
$\displaystyle\dot{y}$ $\displaystyle=P_{y}\big{(}1+2z/L\big{)}$ (D.8)
$\displaystyle\dot{z}$
$\displaystyle=P_{z}+P_{x}\frac{x}{L}-P_{y}\frac{y}{L}.$ (D.9)

We can then require $x^{i}(0)=0$ and equate terms of equal power of $L$ to
solve the system. This gives the following result,

$\displaystyle x(\lambda)$ $\displaystyle=\lambda
P_{x}\left(1-P_{z}\frac{\lambda}{L}-\frac{1}{3}(1-2P_{y}^{2}+3P_{z}^{2})\frac{\lambda^{2}}{L^{2}}+...\right)$
(D.10) $\displaystyle y(\lambda)$ $\displaystyle=\lambda
P_{y}\left(1+P_{z}\frac{\lambda}{L}+\frac{1}{3}(1-2P_{y}^{2}+3P_{z}^{2})\frac{\lambda^{2}}{L^{2}}+...\right)$
(D.11) $\displaystyle z(\lambda)$
$\displaystyle=P_{z}\lambda+\frac{P_{x}^{2}-P_{y}^{2}}{2}\frac{\lambda}{L}+\frac{P_{z}^{3}-P_{z}}{3}\frac{\lambda^{2}}{L^{2}}+...\,.$
(D.12)

We can evaluate the constraint equation (A.5) at $\lambda=0$, which tells us
that $P_{x}^{2}+P_{y}^{2}+P_{z}^{2}=1$ holds as before. Hence (radial) proper
distance to the origin is again given by
$\ell_{\text{rad}}=\lambda_{f}\equiv\rho_{0}$.

To visualise these geodesics we have again plotted select geodesics of this
geometry in Figures 36, 36 and 36. For a description of the surfaces, please
refer to the previous appendix. As before, for a clearer visualisation we have
augmented the effects of curvature by drawing the surfaces from distance
$\lambda=0$ to distance $\lambda=2.5\eta_{*}$.

Figure 34: Geodesics of the Solv geometry. The geometry is characterized by
geodesics being pushed up- or downward respectively depending on whether $|x|$
is larger or smaller than $|y|$.

Figure 35: The same visualisation, viewed along the $y$-direction and with
some elements removed to show more clearly how geodesics along the $x$-$z$
plane are deflected upwards along a distinctive guitar pick shape.

Figure 36: The same visualisation, viewed along the $x$-direction and with
some elements removed to show more clearly how geodesics along the $y$-$z$
plane are deflected downwards.

## References

  * [1] E. A. Milne, “World-Structure and the Expansion of the Universe.” Zeitschrift fur Astrophysik 6 (1933) 1.
  * [2] A. de Oliveira-Costa, M. Tegmark, M. Zaldarriaga and A. Hamilton, “The Significance of the largest scale CMB fluctuations in WMAP,” Phys. Rev. D 69 (2004), 063516 doi:10.1103/PhysRevD.69.063516 [arXiv:astro-ph/0307282 [astro-ph]].
  * [3] E. Abdalla, G. Franco Abellán, A. Aboubrahim, A. Agnello, O. Akarsu, Y. Akrami, G. Alestas, D. Aloni, L. Amendola and L. A. Anchordoqui, et al. “Cosmology intertwined: A review of the particle physics, astrophysics, and cosmology associated with the cosmological tensions and anomalies,” JHEAp 34 (2022), 49-211 doi:10.1016/j.jheap.2022.04.002 [arXiv:2203.06142 [astro-ph.CO]].
  * [4] P. A. R. Ade et al. [Planck], “Planck 2015 results - XVIII. Background geometry and topology of the Universe,” Astron. Astrophys. 594 (2016), A18 doi:10.1051/0004-6361/201525829 [arXiv:1502.01593 [astro-ph.CO]].
  * [5] P. A. R. Ade et al. [Planck], “Planck 2013 results. XXVI. Background geometry and topology of the Universe,” Astron. Astrophys. 571 (2014), A26 doi:10.1051/0004-6361/201321546 [arXiv:1303.5086 [astro-ph.CO]].
  * [6] K. Land and J. Magueijo, “The Axis of evil,” Phys. Rev. Lett. 95 (2005), 071301 doi:10.1103/PhysRevLett.95.071301 [arXiv:astro-ph/0502237 [astro-ph]].
  * [7] K. Land and J. Magueijo, “Cubic anomalies in WMAP,” Mon. Not. Roy. Astron. Soc. 357 (2005), 994-1002 doi:10.1111/j.1365-2966.2005.08707.x [arXiv:astro-ph/0405519 [astro-ph]].
  * [8] K. Land and J. Magueijo, “The Axis of Evil revisited,” Mon. Not. Roy. Astron. Soc. 378 (2007), 153-158 doi:10.1111/j.1365-2966.2007.11749.x [arXiv:astro-ph/0611518 [astro-ph]].
  * [9] C. J. Copi, D. Huterer, D. J. Schwarz and G. D. Starkman, “Large-scale alignments from WMAP and Planck,” Mon. Not. Roy. Astron. Soc. 449 (2015) no.4, 3458-3470 doi:10.1093/mnras/stv501 [arXiv:1311.4562 [astro-ph.CO]].
  * [10] Y. Akrami et al. [Planck], “Planck 2018 results. VII. Isotropy and Statistics of the CMB,” Astron. Astrophys. 641 (2020), A7 doi:10.1051/0004-6361/201935201 [arXiv:1906.02552 [astro-ph.CO]].
  * [11] P. J. E. Peebles, “Anomalies in Physical Cosmology,” [arXiv:2208.05018 [astro-ph.CO]].
  * [12] P. Jain, G. Narain and S. Sarala, “Large scale alignment of optical polarizations from distant QSOs using coordinate invariant statistics,” Mon. Not. Roy. Astron. Soc. 347 (2004), 394 doi:10.1111/j.1365-2966.2004.07169.x [arXiv:astro-ph/0301530 [astro-ph]].
  * [13] G. E. Marinello, R. G. Clowes, L. E. Campusano, G. M. Williger, I. K. Söchting and M. J. Graham, “Compatibility of the Large Quasar Groups with the Concordance Cosmological Model,” Mon. Not. Roy. Astron. Soc. 461 (2016) no.3, 2267-2281 doi:10.1093/mnras/stw1513 [arXiv:1603.03260 [astro-ph.CO]].
  * [14] P. K. Aluri, P. Cea, P. Chingangbam, M. C. Chu, R. G. Clowes, D. Hutsemékers, J. P. Kochappan, A. Krasiński, A. M. Lopez and L. Liu, et al. “Is the Observable Universe Consistent with the Cosmological Principle?,” [arXiv:2207.05765 [astro-ph.CO]].
  * [15] N. Secrest, S. von Hausegger, M. Rameez, R. Mohayaee and S. Sarkar, “A Challenge to the Standard Cosmological Model,” [arXiv:2206.05624 [astro-ph.CO]].
  * [16] D. J. Schwarz, C. J. Copi, D. Huterer and G. D. Starkman, “CMB Anomalies after Planck,” Class. Quant. Grav. 33 (2016) no.18, 184001 doi:10.1088/0264-9381/33/18/184001 [arXiv:1510.07929 [astro-ph.CO]].
  * [17] L. Perivolaropoulos and F. Skara, “Challenges for $\Lambda$CDM: An update,” New Astron. Rev. 95 (2022), 101659 doi:10.1016/j.newar.2022.101659 [arXiv:2105.05208 [astro-ph.CO]].
  * [18] N. Aghanim et al. [Planck], “Planck 2018 results. VI. Cosmological parameters,” Astron. Astrophys. 641 (2020), A6 [erratum: Astron. Astrophys. 652 (2021), C4] doi:10.1051/0004-6361/201833910 [arXiv:1807.06209 [astro-ph.CO]].
  * [19] C. D. Leonard, P. Bull and R. Allison, “Spatial curvature endgame: Reaching the limit of curvature determination,” Phys. Rev. D 94 (2016) no.2, 023502 doi:10.1103/PhysRevD.94.023502 [arXiv:1604.01410 [astro-ph.CO]].
  * [20] E. Di Dio, F. Montanari, A. Raccanelli, R. Durrer, M. Kamionkowski and J. Lesgourgues, “Curvature constraints from Large Scale Structure,” JCAP 06 (2016), 013 doi:10.1088/1475-7516/2016/06/013 [arXiv:1603.09073 [astro-ph.CO]].
  * [21] N. J. Cornish, D. N. Spergel and G. D. Starkman, “Measuring the topology of the universe,” Proc. Nat. Acad. Sci. 95 (1998), 82 doi:10.1073/pnas.95.1.82 [arXiv:astro-ph/9708083 [astro-ph]].
  * [22] J. P. Luminet and B. F. Roukema, “Topology of the universe: Theory and observation,” [arXiv:astro-ph/9901364 [astro-ph]].
  * [23] J. Sandhu, “Cosmic Topology,” [arXiv:1612.04157 [astro-ph.CO]].
  * [24] A. A. Starobinsky, “New restrictions on spatial topology of the universe from microwave background temperature fluctuations,” JETP Lett. 57 (1993), 622-625 [arXiv:gr-qc/9305019 [gr-qc]].
  * [25] A. de Oliviera Costa and G. F. Smoot, “Constraints on the topology of the universe from the 2-year COBE data,” Astrophys. J. 448 (1995), 477 doi:10.1086/175977 [arXiv:astro-ph/9412003 [astro-ph]].
  * [26] N. J. Cornish, D. N. Spergel, G. D. Starkman and E. Komatsu, “Constraining the topology of the universe,” Phys. Rev. Lett. 92 (2004), 201302 doi:10.1103/PhysRevLett.92.201302 [arXiv:astro-ph/0310233 [astro-ph]].
  * [27] P. M. Vaudrevange, G. D. Starkman, N. J. Cornish and D. N. Spergel, “Constraints on the Topology of the Universe: Extension to General Geometries,” Phys. Rev. D 86 (2012), 083526 doi:10.1103/PhysRevD.86.083526 [arXiv:1206.2939 [astro-ph.CO]].
  * [28] J. P. Luminet, J. Weeks, A. Riazuelo, R. Lehoucq and J. P. Uzan, “Dodecahedral space topology as an explanation for weak wide - angle temperature correlations in the cosmic microwave background,” Nature 425 (2003), 593 doi:10.1038/nature01944 [arXiv:astro-ph/0310253 [astro-ph]].
  * [29] A. Bernui, C. P. Novaes, T. S. Pereira and G. D. Starkman, “Topology and the suppression of CMB large-angle correlations,” [arXiv:1809.05924 [astro-ph.CO]].
  * [30] William P. Thurston, “Three dimensional Manifolds, Kleinian groups and hyperbolic geometry,” Bull. Am. Math. Soc. (N.S.) 6, 357 (1982).
  * [31] G. Perelman, “Finite extinction time for the solutions to the Ricci flow on certain three-manifolds,” [arXiv:math/0307245 [math.DG]].
  * [32] G. Perelman, “The Entropy formula for the Ricci flow and its geometric applications,” [arXiv:math/0211159 [math.DG]].
  * [33] G. Perelman, “Ricci flow with surgery on three-manifolds,” [arXiv:math/0303109 [math.DG]].
  * [34] R. Coquereaux, “The history of the universe is an elliptic curve,” Class. Quant. Grav. 32 (2015) no.11, 115013 [erratum: Class. Quant. Grav. 33 (2016) no.15, 159601] doi:10.1088/0264-9381/32/11/115013 [arXiv:1411.2192 [gr-qc]].
  * [35] R. Coquereaux and A. Grossmann, “Analytic Discussion of Spatially Closed Friedmann Universes With Cosmological Constant and Radiation Pressure,” Annals Phys. 143 (1982), 296 doi:10.1016/0003-4916(82)90030-6
  * [36] H. V. Fagundes, “Closed spaces in cosmology,” Gen. Rel. Grav. 24 (1992), 199 doi:10.1007/BF00756787 [arXiv:0812.4103 [gr-qc]].
  * [37] M. Koussour, H. Filali and M. Bennai, “Two Minimally Interacting Fluids: Matter and Holographic Dark Energy in Bianchi Type-I Universe,” doi:10.2139/ssrn.4028697
  * [38] Izrail Solomonovich Gradshteyn and Iosif Moiseevich Ryzhik, “Table of integrals, series, and products”, Academic press (2014).
  * [39] C. J. G. Vedder, E. Belgacem, N. E. Chisari and T. Prokopec, “Fluctuating Dark Energy and the Luminosity Distance,” [arXiv:2209.00440 [astro-ph.CO]].


#  ProtoCon: Pseudo-label Refinement via Online Clustering and Prototypical
Consistency for Efficient Semi-supervised Learning

Islam Nassar1 Munawar Hayat1 Ehsan Abbasnejad2 Hamid Rezatofighi1
Gholamreza Haffari1
1 Data Science and AI Department, Monash University, Australia –
<EMAIL_ADDRESS>
2 Australian Institute for Machine Learning, The University of Adelaide,
Australia –<EMAIL_ADDRESS>
(October 2020)

###### Abstract

Confidence-based pseudo-labeling is among the dominant approaches in semi-
supervised learning (SSL). It relies on including high-confidence predictions
made on unlabeled data as additional targets to train the model. We propose
ProtoCon, a novel SSL method aimed at the less-explored label-scarce SSL where
such methods usually underperform. ProtoCon refines the pseudo-labels by
leveraging their nearest neighbours’ information. The neighbours are
identified as the training proceeds using an online clustering approach
operating in an embedding space trained via a prototypical loss to encourage
well-formed clusters. The online nature of ProtoCon allows it to utilise the
label history of the entire dataset in one training cycle to refine labels in
the following cycle without the need to store image embeddings. Hence, it can
seamlessly scale to larger datasets at a low cost. Finally, ProtoCon addresses
the poor training signal in the initial phase of training (due to fewer
confident predictions) by introducing an auxiliary self-supervised loss. It
delivers significant gains and faster convergence over state-of-the-art across
5 datasets, including CIFARs, ImageNet and DomainNet.

##  1 Introduction

Figure 1: ProtoCon refines a pseudo-label of a given sample by knowledge of
its neighbours in a prototypical embedding space. Neighbours are identified in
an online manner using constrained K-means clustering. Best viewed zoomed in.

Semi-supervised Learning (SSL) [40, 10] leverages unlabeled data to guide
learning from a small amount of labeled data; thereby, providing a promising
alternative to costly human annotations. In recent years, SSL frontiers have
seen substantial advances through confidence-based pseudo-labeling [21, 38,
43, 22, 42]. In these methods, a model iteratively generates pseudo-labels for
unlabeled samples which are then used as targets to train the model. To
overcome confirmation bias [1, 27] i.e., the model being biased by training on
its own wrong predictions, these methods only retain samples with high
confidence predictions for pseudo-labeling; thus ensuring that only reliable
samples are used to train the model. While confidence works well in moderately
labeled data regimes, it usually struggles in label-scarce settings111We
denote settings with less than 10 images per class as “label-scarce.”. This is
primarily because the model becomes over-confident about the more
distinguishable classes [28, 17] faster than others, leading to a collapse.

In this work, we propose ProtoCon, a novel method which addresses such a
limitation in label-scarce SSL. Its key idea is to complement confidence with
a label refinement strategy to encourage more accurate pseudo-labels. To that
end, we perform the refinement by adopting a co-training [5] framework: for
each image, we obtain two different labels and combine them to obtain our
final pseudo-label. The first is the model’s softmax prediction, whereas the
second is an aggregate pseudo-label describing the image’s neighbourhood based
on the pseudo-labels of other images in its vicinity. However, a key
requirement for the success of co-training is to ensure that the two labels
are obtained using sufficiently different image representations [40] to allow
the model to learn based on their disagreements. As such, we employ a non-
linear projection to map our encoder’s representation into a different
embedding space. We train this projector jointly with the model with a
prototypical consistency objective to ensure it learns a different, yet
relevant, mapping for our images. Then we define the neighbourhood pseudo-
label based on the vicinity in that embedding space. In essence, we minimise a
sample bias by smoothing its pseudo-label in class space via knowledge of its
neighbours in the prototypical space.

Additionally, we design our method to be fully online, enabling us to scale to
large datasets at a low cost. We identify neighbours in the embedding space
on-the-fly as the training proceeds by leveraging online K-means clustering.
This alleviates the need to store expensive image embeddings [22], or to
utilise offline nearest neighbour retrieval [23, 48]. However, applying naive
K-means risks collapsing to only a few imbalanced clusters making it less
useful for our purpose. Hence, we employ a constrained objective [6] lower
bounding each cluster size; thereby, ensuring that each sample has enough
neighbours in its cluster. We show that the online nature of our method allows
it to leverage the entire prediction history in one epoch to refine labels in
the subsequent epoch at a fraction of the cost required by other methods and
with a better performance.

ProtoCon’s final ingredient addresses another limitation of confidence-based
methods: since the model only retains high confident samples for pseudo-
labeling, the initial phase of the training usually suffers from a weak
training signal due to fewer confident predictions. In effect, this leads to
only learning from the very few labeled samples which destabilises the
training potentially due to overfitting [25]. To boost the initial training
signal, we adopt a self-supervised instance-consistency [15, 9] loss applied
on samples that fall below the threshold. Our choice of loss is more
consistent with the classification task as opposed to contrastive instance
discrimination losses [16, 11] which treat each image as its own class. This
helps our method to converge faster without loss of accuracy.

Figure 2: Method overview. A soft pseudo-label $p^{w}$ is first obtained based
on the weak view. Then it is refined using the sample’s cluster pseudo-label
$z^{a}$ before using it as target in $\mathcal{L}_{u}$. Clustering assignments
$a$ are calculated online using the projections of the weak samples $q^{w}$ in
the embedding space $h$ which is trained via a prototypical loss
$\mathcal{L}_{p}$. Prototype targets are updated once after each epoch by
averaging the accumulated projections of reliable samples for each class
throughout the epoch. Cluster pseudo-labels are updated after each epoch using
the cluster assignments/scores of all the samples and their respective hard
pseudo-labels $\hat{y}$. Finally, the self-supervised loss $\mathcal{L}_{c}$
ensures consistency between projections $q^{s}$ and $q^{w}$.

We demonstrate ProtoCon’s superior performance against comparable state-of-
the-art methods on 5 datasets including CIFAR, ImageNet and DomainNet.
Notably, ProtoCon achieves 2.2%, 1% improvement on the SSL ImageNet protocol
with 0.2% and 1% of the labeled data, respectively. Additionally, we show that
our method exhibits faster convergence and more stable initial training
compared to baselines, thanks to our additional self-supervised loss. In
summary, our contributions are:

  * •

We propose a memory-efficient method addressing confirmation bias in label-
scarce SSL via a novel label refinement strategy based on co-training.

  * •

We improve training dynamics and convergence of confidence-based methods by
adopting self-supervised losses to the SSL objective.

  * •

We show state-of-the-art results on 5 SSL benchmarks.

##  2 Background

We begin by reviewing existing SSL approaches with a special focus on relevant
methods in the low-label regime.

Confidence-based pseudo-labeling is an integral component in most of recent
SSL methods [38, 22, 42, 27, 20]. However, recent research shows that using a
fixed threshold underperforms in low-data settings because the model collapses
to the few easy-to-learn classes early in the training. Some researchers
combat this effect by using class- [47] or instance-based [44] adaptive
thresholds, or by aligning [3] or debiasing [42] the pseudo-label distribution
by keeping a running average of pseudo-labels to avoid the inherent imbalance
in pseudo-labels. Another direction focuses on pseudo-label refinement,
whereby the classifier’s predictions are adjusted by training another
projection head on an auxiliary task such as weak-supervision via language
semantics [27], instance-similarity matching [48], or graph-based contrastive
learning [22]. Our method follows the refinement approach, where we employ
online constrained clustering to leverage nearest neighbours information for
refinement. Different from previous methods, our method is fully online and
hence allows using the entire prediction history in one training epoch to
refine pseudo-labels in the subsequent epoch with minimal memory requirements.

Consistency Regularization combined with pseudo-labeling underpins many recent
state-of-the-art SSL methods [43, 24, 35, 4, 38, 22, 20]; it exploits the
smoothness assumption [40] where the model is expected to produce similar
pseudo-labels for minor input perturbations. The seminal FixMatch [38] and
following work [27, 22, 42] leverage this idea by obtaining pseudo-labels
through a weak form of augmentation and applying the loss against the model’s
prediction for a strong augmentation. Our method utilises a similar approach,
but different from previous work, we additionally apply an instance-
consistency loss in our projection embedding space.

Semi-supervision via self-supervision is gaining recent popularity due to the
incredible success of self-supervised learning for model pretraining. Two
common approaches are: 1) performing self-supervised pretraining followed by
supervised fine-tuning on the few labeled samples [11, 12, 15, 26, 9], and 2)
including a self-supervised loss to the semi-supervised objective to enhance
training [46, 25, 41, 22, 48]. However, the choice of the task is crucial:
tasks such as instance discrimination [16, 11], which treats each image as its
own class, can hurt semi-supervised image classification as it partially
conflicts with it. Instead, we use an instance-consistency loss akin to that
of [9] to boost the initial training signal by leveraging samples which are
not retained for pseudo-labeling in the early phase of the training.

##  3 ProtoCon

Preliminaries. We consider a semi-supervised image classification problem,
where we train a model using $M$ labeled samples and $N$ unlabeled samples,
where $N>>M$. We use mini-batches of labeled instances,
$\mathcal{X}=\\{(\boldsymbol{x}_{j},\boldsymbol{y}_{j})\\}_{j=1}^{B}$ and
unlabeled instances, $\mathcal{U}=\\{{\boldsymbol{u}}_{i}\\}_{i=1}^{\mu\cdot
B}$, where the scalar $\mu$ denotes the ratio between the number of unlabeled
and labeled examples in a given batch, and $\boldsymbol{y}$ is the one-hot
vector of the class label $c\in\\{1,\dots,C\\}$. We employ an encoder network
$f$ to get latent representations $f(.)$. We attach a softmax classifier
$g(\cdot)$, which produces a distribution over classes $\boldsymbol{p}=g\circ
f$. Moreover, we attach a projector $h(\cdot)$, an MLP followed by an
$\ell_{2}$ norm layer, to get a normalised embedding
$\boldsymbol{q}\in\mathbb{R}^{d}=h\circ f$. Following [38], we apply weak
augmentations $\mathcal{A}_{w}(\cdot)$ on all images and an additional strong
augmentation [13] $\mathcal{A}_{s}(\cdot)$ only on unlabeled ones.

Motivation. Our aim is to refine pseudo-labels before using them to train our
model in order to minimise confirmation bias in label-scarce SSL. We achieve
this via a co-training approach (see Fig. 2). For each image, we obtain two
pseudo-labels and combine them to obtain our final pseudo-label
$\hat{\boldsymbol{p}}^{w}$. The first is the classifier softmax prediction
${\boldsymbol{p}}^{w}$ based on a weakly augmented image, whereas the second
is an aggregate pseudo-label $\boldsymbol{z}^{a}$ describing the sample’s
neighbourhood. To ensure the two labels are based on sufficiently different
representations, we define an image neighbourhood222We use “neighbourhood” and
“cluster” interchangeably. via online clustering in an embedding space
obtained via projector $h$ and trained for prototypical consistency instead of
class prediction. Projector $h$ and classifier $g$ are jointly trained with
the encoder $f$, while interacting over pseudo-labels. The classifier is
trained with pseudo-labels which are refined based on their nearest neighbours
in the embedding space, whereas the projector $h$ is trained using prototypes
obtained based on the refined pseudo-labels to impose structure on the
embedding space.

Prototypical Space. Here, we discuss our procedure to learn our embedding
space defined by $h$. Inspired by prototypical learning [37], we would like to
encourage well-clustered image projections in our space by attracting samples
to their class prototypes and away from others. Hence, we employ a contrastive
objective using the class prototypes as targets rather than the class labels.
We calculate class prototypes at the end of a given epoch by knowledge of the
“reliable” samples in the previous epoch. Specifically, by employing a memory
bank of $\mathcal{O}(2N)$, we keep track of samples hard pseudo-labels
$\\{\hat{y}_{i}=\operatorname*{arg\,max}(\hat{\boldsymbol{p}}^{w}_{i})\forall\boldsymbol{u}_{i}\in\mathcal{U}\\}$
in a given epoch; as well as a reliability indicator for each sample
$\eta_{i}=\mathds{1}(\max(\hat{\boldsymbol{p}}^{w}_{i})\geq\tau)$ denoting if
its max prediction exceeds the confidence threshold $\tau$. Subsequently, we
update the prototypes $\mathcal{P}\in\mathbb{R}^{C\times d}$ as the average
projections (accumulated over the epoch) of labeled images and reliable
unlabeled images. Formally, let
$\mathcal{I}^{x}_{c}=\\{i|\forall\boldsymbol{x}_{i}\in\mathcal{X},y_{i}=c\\}$
be the indices of labelled instances with true class $c$, and
$\mathcal{I}^{w}_{c}=\\{i|\forall\boldsymbol{u}_{i}\in\mathcal{U},\eta_{i}=1,\hat{y}_{i}=c\\}$
be the indices of the reliable unlabelled samples with hard pseudo-label $c$.
The normalised prototype for class $c$ can then be obtained as per:

$\bar{\mathcal{P}}_{c}=\frac{\sum_{i\in\mathcal{I}^{x}_{c}\cup\mathcal{I}^{w}_{c}}\boldsymbol{q}_{i}}{|\mathcal{I}^{x}_{c}|+|\mathcal{I}^{w}_{c}|},\quad\mathcal{P}_{c}=\frac{\bar{\mathcal{P}}_{c}}{||\bar{\mathcal{P}}_{c}||_{2}}$
(1)

Subsequently, in the following epoch, we minimize the following contrastive
prototypical consistency loss on unlabeled samples:

$\mathcal{L}_{p}=-\frac{1}{\mu B}\sum_{i=1}^{\mu
B}\log\frac{\exp(\boldsymbol{q}^{s}_{i}\cdot\mathcal{P}_{\hat{y}_{i}}/T)}{\sum_{c=1}^{C}\exp(\boldsymbol{q}^{s}_{i}\cdot\mathcal{P}_{c}/T))},$
(2)

where $T$ is a temperature parameter. Note that the loss is applied against
the projection of the strong augmentations to achieve consistency
regularisation as in [38].

Algorithm 1 Pseudo-code of one epoch of ProtoCon

⬇

# f, g, h: encoder, classifier, and projector

# b_x: labeled batch

# b_w, b_s: weak, strong unlabeled batches

# u_id: unique index of unlabeled samples

# N, C: num unlabeled samples, num classes

# CA: cluster assignment bank (N x 2)

# CPL: clusters pseudo-label bank (N x C)

# PH: samples pseudo-label bank (N x 1)

# Q: cluster centers

# P: class prototypes

# P_acc: prototypes accumulator

# alpha: pseudo-label refinement ratio

for b_x, b_w, b_s, u_id in loader:

# forward images and obtain p and q

p_x, p_w, p_s = f(g(b_x, b_w, b_s))

q_x, q_w, q_s = f(h(b_x, b_w, b_s))

# calculate and save cluster assignment

CA[u_id] = calc_clust_assignmnt(q_w, Q) # Eqn.5

# update centers and dual variables

Q = update_cluster_centers(q_w) # Eqn. 6 & 7

#retrieve cluster pseudo-labels from previous epoch

z = CPL[CA[u_id]]

# refine p_w

p_w_hat = alpha*p_w + (1 - alpha)*z # Eqn. 9

# save hard pseudo-labels

PH[u_id] = argmax(p_w_hat)

# accumulate prototypes (of reliable samples only)

P_acc = accum_prototypes(q_x, q_w, PH[u_id])

# apply losses (except in first epoch)

Lx, Lp, Lu, Lc = backward_losses() # Eqn. 2, 10-12

# after each epoch

P = update_prototypes(P_acc) # Eqn. 1

CPL = calc_cluster_pseudo_labels(CA, PH) # Eqn. 8

Online Constrained K-means Here, the goal is to cluster instances in the
prototypical space as a training epoch proceeds, so the cluster assignments
(capturing the neighbourhood of each sample) are used to refine their pseudo-
labels in the following epoch. We employ a mini-batch version of K-means [36].
To avoid collapsing to one (or a few) imbalanced clusters, we ensure that each
cluster has sufficient samples by enforcing a constraint on the lowest
acceptable cluster size. Given our $N$ unlabeled projections, we cluster them
into $K$ clusters defined by centroids
$\mathcal{Q}=[\mathbf{c}_{1},\cdots,\mathbf{c}_{K}]\in\mathbb{R}^{d\times K}$.
We use the constrained K-means objective proposed by [6]:

$\displaystyle\min_{\mathcal{Q},\mu\in\Delta}\sum_{i=1,k=1}^{i=N,k=K}\mu_{i,k}\|\boldsymbol{q}_{i}-\mathbf{c}_{k}\|_{2}^{2}\quad
s.t.\quad\forall k\quad\sum_{i=1}^{N}\mu_{i,k}\geq\gamma$ (3)

where $\gamma$ is the lower-bound of cluster size, $\mu_{i,k}$ is the
assignment of the $i$-th unlabeled sample to the $k$-th cluster, and
$\Delta=\\{\mu|\forall i,\ \sum_{k}\mu_{i,k}=1,\forall
i,k,\mu_{i,k}\in[0,1]\\}$ is the domain of $\mu$. Subsequently, to solve Eqn.
3 in an online mini-batch manner, we adopt the alternate solver proposed in
[32]. For a fixed $\mathcal{Q}$, the problem for updating $\mu$ can be
simplified as an assignment problem. By introducing dual variables $\rho_{k}$
for each constraint $\sum_{i}\mu_{i,k}\geq\gamma$, the assignment can be
obtained by solving the problem:

$\displaystyle\max_{\mu_{i}\in\Delta}\sum_{k}s_{i,k}\mu_{i,k}+\sum_{k}\rho_{k}^{t-1}\mu_{i,k}$
(4)

where $s_{i,k}=\boldsymbol{q}_{i}^{\top}\mathbf{c}_{k}$ is the similarity
between the projection of unlabeled sample $\boldsymbol{u}_{i}$ and the $k$-th
cluster centroid, and $t$ is the mini-batch iteration counter. Eqn. 4 can then
be solved with the closed-form solution:

$\displaystyle\mu_{i,k}=\left\\{\begin{array}[]{cc}1&k=\arg\max_{k}s_{i,k}+\rho_{k}^{t-1}\\\
0&o.w.\end{array}\right.$ (7)

After assignment, dual variables are updated as333Refer to [32] and
supplements for proofs of optimality and more details. :

$\displaystyle\rho_{k}^{t}=\max\\{0,\rho_{k}^{t-1}-\lambda\frac{1}{B}\sum_{i=1}^{B}(\mu_{i,k}^{t}-\frac{\gamma}{N})\\}$
(8)

where $\lambda$ is the dual learning rate. Finally, we update the cluster
centroids after each mini-batch444See supplements for a discussion about
updating the centers every mini-batch opposed to every epoch. as:

$\bar{\mathbf{c}_{k}}^{t}=\frac{\sum_{i}^{m}\mu_{i,k}^{t}\boldsymbol{q}_{i}^{t}}{\sum_{i}^{m}\mu_{i,k}^{t}},\quad\mathbf{c}_{k}^{t}=\frac{\bar{\mathbf{c}_{k}}^{t}}{||\bar{\mathbf{c}_{k}}^{t}||_{2}}$
(9)

where $m$ denotes the total number of received instances until the $t$-th
mini-batch. Accordingly, we maintain another memory bank ($\mathcal{O}(2N)$)
to store two values for each unlabeled instance: its cluster assignment in the
current epoch $a(i)=\\{k|\mu_{i,k}=1\\}$ and the similarity score $s_{i,a(i)}$
(i.e. the distance to its cluster centroid).

Cluster Pseudo-labels are computed at end of each epoch by querying the memory
banks. The purpose is to obtain a distribution over classes $C$ for each of
our clusters based on its members. For a given cluster $k$, we obtain its
label $\boldsymbol{z}^{k}=[z^{k}_{1},\cdots,z^{k}_{C}]$ as the average of the
pseudo-labels of its cluster members weighted by their similarity to its
centroid. Concretely, let
$\mathcal{I}^{k}_{c}=\\{i|\forall\boldsymbol{u}_{i}\in\mathcal{U},a(i)=k,\hat{y}_{i}=c\\}$
be the indices of unlabeled samples which belong to cluster $k$ and have a
hard pseudo-label $c$. The probability of cluster $k$’s members belonging to
class $c$ is given as:

$\displaystyle z^{k}_{c}=\frac{\sum_{i\in\mathcal{I}^{k}_{c}}\quad
s_{i,a(i)}}{\sum_{b=1}^{C}\sum_{j\in\mathcal{I}^{k}_{b}}s_{j,a(j)}}$ (10)

Refining Pseudo-labels. At any given epoch, we now have two pseudo-labels for
an image $\boldsymbol{u}_{i}$: the unrefined pseudo-label
$\boldsymbol{p}^{w}_{i}$ as well as a cluster pseudo-label
$\boldsymbol{z}^{a(i)}$ summarising its prototypical neighbourhood in the
previous epoch. Accordingly, we apply our refinement procedure as follows:
first, as recommended by [3, 22], we perform distribution alignment
($DA(\cdot)$) to encourage the marginal distribution of pseudo-labels to be
close to the marginal of ground-truth
labels555$DA(\boldsymbol{p}^{w})=\boldsymbol{p}^{w}/\bar{\boldsymbol{p}^{w}}$,
where $\bar{\boldsymbol{p}^{w}}$ is a running average of $\boldsymbol{p}^{w}$
during training., then we refine the aligned pseudo-label as per:

$\displaystyle\hat{\boldsymbol{p}}^{w}_{i}=\alpha\cdot
DA(\boldsymbol{p}^{w}_{i})+(1-\alpha)\cdot\boldsymbol{z}^{a(i)}$ (11)

Here, the second term acts as a regulariser to encourage
$\hat{\boldsymbol{p}}^{w}$ to be similar to its cluster members’ and $\alpha$
is a trade-off scalar parameter. Importantly, the refinement here leverages
information based on the entire training set last-epoch information. This is
in contrast to previous work [22, 48] which only stores a limited history of
soft pseudo-labels for refinement, due to more memory requirement
($\mathcal{O}(N\times C)$).

Classification Loss. With the refined pseudo-label, we apply the unlabeled
loss against the model prediction for the strong augmentation as per:

$\mathcal{L}_{u}=\frac{1}{\mu B}\sum_{i=1}^{\mu
B}\eta_{i}\cdot\mathrm{CE}(\hat{\boldsymbol{p}}_{i}^{w},\boldsymbol{p}^{s}_{i}),$
(12)

where $\mathrm{CE}$ denotes cross-entropy. However, unlike [38, 4], we do not
use hard pseudo-labels or sharpening, but instead use the soft pseudo-label
directly. Also, we apply a supervised classification loss over the labeled
data as per:

$\mathcal{L}_{x}=\frac{1}{B}\sum_{i=1}^{B}\mathrm{CE}(\boldsymbol{y}_{i},\boldsymbol{p}^{x}_{i})),$
(13)

Self-supervised Loss. Since we use confidence as a measure of reliability (see
Eqn. 12), early epochs of training suffer from limited supervisory signal when
the model is not yet confident about unlabeled samples, leading to slow
convergence and unstable training. Our final ingredient addresses this by
introducing a consistency loss in the prototypical space on samples which fall
below the confidence threshold $\tau$. We draw inspiration from instance-
consistency self-supervised methods such as BYOL [15] and DINO [9]. In
contrast to contrastive instance discrimination [16, 11], the former imposes
consistency between two (or more) views of an image without using negative
samples. Thereby, we found it to be more aligned with classification tasks
than the latter. Formally, we treat the projection $q$ as soft classes score
over $d$ dimensions, and obtain a distribution over these classes via a
sharpened softmax ($SM(\cdot)$). We then enforce consistency between the weak
and strong views as per:

$\displaystyle\footnotesize\mathcal{L}_{c}=\frac{1}{\mu B}\sum_{i=1}^{\mu
B}(1-\eta_{i})\cdot\mathrm{CE}(SM(\boldsymbol{q}^{w}_{i}/5T),SM(\boldsymbol{q}^{s}_{i}/T))$
(14)

Note that, as in DINO [9], we sharpen the target distribution more than the
source’s to encourage entropy minimization [14]. Unlike DINO, we do not use a
separate EMA model to produce the target, we just use the output of the model
for the weak augmentation. Note that this does not lead to representation
collapse [15] because the network is also trained with additional semi-
supervised losses.

Final Objective. We train our model using a linear combination of all four
losses
$\mathcal{L}=\mathcal{L}_{x}+\lambda_{u}\mathcal{L}_{u}+\lambda_{p}\mathcal{L}_{p}+\lambda_{c}\mathcal{L}_{c}$.
Empirically, we find that fixing $\forall\lambda=1$, the coefficients to
modulate each loss, works well across different datasets. Algorithm 1
describes one epoch of ProtoCon training.

###  3.1 Design Considerations

Number of Clusters is a crucial parameter in our approach. In essence, we
refine a sample prediction obtained by the classifier by aggregating
information from its $n$ nearest neighbours. However, naively doing nearest-
neighbour retrieval has two limitations: 1) it requires storing image features
throughout an epoch which is memory expensive; and 2) it requires a separate
offline nearest-neighbour retrieval step. Instead, we leverage online
clustering to identify nearest-neighbours on-the-fly. To avoid tuning $K$ for
each dataset, we tuned $n$ once instead, then $K$ can be simply calculated as
$K=N/n$. Additionally, we fix $\gamma=0.9n$ to ensure that each cluster
contains sufficient samples to guarantee the quality of the cluster pseudo-
label while relaxing clusters to not necessarily be equi-partitioned.
Empirically, we found that using $n=250$ works reasonably well across
datasets. To put it in context, this corresponds to $K=4800$ for ImageNet, and
$K=200$ for CIFAR datasets.

Multi-head Clustering is another way to ensure robustness of our cluster
pseudo-labels. To account for K-means stochastic nature, we can employ multi-
head clustering to get different cluster assignments based on each head, at
negligible cost. Subsequently, we can average the cluster pseudo-labels across
the different heads. In practice, we find that for large datasets e.g.
ImageNet, cluster assignments slightly vary between heads so it is useful to
use dual heads, while for smaller datasets, a single head is sufficient.

Table 1: CIFAR and Mini-ImageNet accuracy for different amounts of labeled
samples averaged over 5 different splits. All results are produced using the
same codebase and same splits.

|  | CIFAR-10 |  | CIFAR-100 |  | Mini-ImageNet
---|---|---|---|---|---|---
Total labeled samples |  | 20 | 40 | 80 |  | 200 | 400 | 800 |  | 400 | 1000
FixMatch [38] |  | 82.32$\pm$9.77 | 86.29$\pm$4.50 | 92.06$\pm$0.88 |  | 35.37$\pm$5.68 | 51.15$\pm$1.75 | 61.32$\pm$0.92 |  | 17.18$\pm$6.22 | 39.03$\pm$3.99
FixMatch + DA [38, 3] |  | 83.84$\pm$8.35 | 86.98$\pm$3.40 | 92.29$\pm$0.86 |  | 41.28$\pm$6.03 | 52.65$\pm$2.32 | 62.12$\pm$0.79 |  | 19.40$\pm$5.87 | 40.92$\pm$4.71
CoMatch [22] |  | 87.37$\pm$8.47 | 93.09$\pm$1.39 | 93.97$\pm$0.62 |  | 47.92$\pm$4.83 | 58.17$\pm$3.52 | 66.15$\pm$0.71 |  | 21.29$\pm$6.19 | 40.98$\pm$3.52
SimMatch [48] |  | 89.31$\pm$7.73 | 94.51$\pm$2.56 | 94.89$\pm$1.32 |  | 46.01$\pm$6.12 | 57.95$\pm$2.37 | 65.50$\pm$0.93 |  | 25.75$\pm$5.90 | 39.76$\pm$3.77
FixMatch + DB [42] |  | 89.02$\pm$6.37 | 94.60 $\pm$1.31 | 95.60 $\pm$0.12 |  | 46.36$\pm$5.05 | 57.88$\pm$3.34 | 64.84$\pm$0.85 |  | 27.37$\pm$7.01 | 41.05$\pm$3.34
ProtoCon |  | 90.51$\pm$4.02 | 95.20$\pm$1.8 | 96.11$\pm$0.20 |  | 48.25$\pm$4.87 | 59.53$\pm$2.94 | 65.91$\pm$0.57 |  | 29.15$\pm$6.98 | 45.83$\pm$4.15
_delta against best baseline_ |  | +1.20 | +0.60 | +0.51 |  | +0.33 | +1.36 | -0.24 |  | +1.78 | +4.78

Memory Analysis. ProtoCon is particulary useful due to its ability to leverage
the entire prediction history in an epoch to approximate class density over
neighbourhoods (represented by cluster pseudo-labels) with low memory cost.
Particularly, it requires an overall of $\mathcal{O}(4N+K\times C)$: $4N$ to
store hard pseudo-labels, reliability, cluster assignments, and similarity
scores; and $K\times C$ to store the cluster pseudo-labels. In contrast, if we
were to employ a naive offline refinement approach, this would require
$\mathcal{O}(N\times d)$ to store the image embeddings for an epoch. For
ImageNet dataset this translates to 9.6M memory units for ProtoCon opposed to
153.6M for the naive approach666considering $d=128$ which is a 16$\times$
reduction in memory; beside, eliminating the additional time needed to perform
nearest neighbour retrieval.

Table 2: DomainNet accuracy for 2, 4, and 8 labels per class.

|  | Clipart |  | Sketch
---|---|---|---|---
Total labeled samples |  | 690 | 1380 | 2760 |  | 690 | 1380 | 2760
FixMatch [38] |  | 30.21 | 41.21 | 51.29 |  | 12.73 | 21.65 | 33.07
CoMatch [22] |  | 35.49 | 48.62 | 54.98 |  | 24.30 | 33.71 | 41.02
FixMatch + DB [42] |  | 38.97 | 51.44 | 58.31 |  | 25.34 | 35.58 | 43.98
ProtoCon |  | 43.72 | 55.66 | 61.32 |  | 33.94 | 43.51 | 50.88
_delta_ |  | +4.75 | +4.22 | +3.01 |  | +8.60 | +7.93 | +6.90

##  4 Experiments

We begin by validating ProtoCon’s performance on multiple SSL benchmarks
against state-of-the-art methods. Then, we analyse the main components of
ProtoCon to verify their contribution towards the overall performance, and we
perform ablations on important hyperparameters.

###  4.1 Experimental Settings

Datasets. We evaluate ProtoCon on five SSL benchmarks. Following [38, 43, 1],
we evaluate on CIFAR-10(100) [19] datasets, which comprises 50,000 images of
32x32 resolution of 10(100) classes; as well as the more challenging Mini-
ImageNet dataset proposed in [33], having 100 classes with 600 images per
class (84x84 each). We use the same train/test split as in [18] and create
splits for 4 and 10 labeled images per class to test ProtoCon in the low-label
regime. We also test ProtoCon’s performance on the DomainNet [30] dataset,
which has 345 classes from six visual domains: _Clipart_ , _Infograph_ ,
_Painting_ , _Quickdraw_ , _Real_ , and _Sketch_. We evaluate on the _Clipart_
and _Sketch_ domains to verify our method’s efficacy in different visual
domains and on imbalanced datasets. Finally, we evaluate on ImageNet [34] SSL
protocol as in [8, 11, 9, 2]. In all our experiments, we focus on the low-
label regime.

Implementation Details. For CIFAR-10(100), we follow previous work and use
WideResent-28-2(28-8) [45] as our encoder. We use a 2-layer projection MLP
with an embedding dimension $d=64$. The models are trained using SGD with a
momentum of 0.9 and weight decay of 0.0005(0.001) using a batch size of 64 and
$\mu=7$. We set the threshold $\tau=0.95$ and train our models for 1024 epochs
for a fair comparison with the baselines. However, we note that our model
needs substantially fewer epochs to converge (see Fig. 3-b and c). We use a
learning rate of 0.03 with a cosine decay schedule. We use random horizontal
flips for weak augmentations and RandAugment [13] for strong ones. For the
larger datasets: ImageNet and DomainNet, we use a Resnet-50 encoder and
$d=128$, $\mu=5$ and $\tau=0.7$ and follow the same hyperparameters as in [38]
except that we use SimCLR [11] augmentations for the strong view. For
ProtoCon-specific hyperparameters, we consistently use the same parameters
across all experiments: we set $n$ to 250 (corresponding to $K$=200 for
CIFARs, and Mini-ImageNet, and 4800 for ImageNet), and dual learning rate
$\lambda=20$, mixing ratio $\alpha=0.8$, and temperature $T=0.1$.

Baselines. Since our method bears the most resemblance with CoMatch [22], we
compare against it in all our experiments. CoMatch uses graph contrastive
learning to refine pseudo-labels but uses a memory bank to store the last
n-samples embeddings to build the graph. Additionally, we compare with state-
of-the-art SSL method (DebiasPL) [42], which proposes a pseudo-labeling
debiasing plug-in to work with various SSL methods in addition to an adaptive
margin loss to account for inter-class confounding. Finally, we also compare
with the seminal method FixMatch and its variant with Distribution alignment
(DA). We follow Oliver et al. [29] recommendations to ensure a fair comparison
with the baselines, where we implement/adapt all the baselines using the same
codebase to ensure using the same settings across all experiments. As for
ImageNet experiments, we also compare with representation learning baselines
such as SwAV [8], DINO [9], and SimCLR [11], where we report the results
directly from the respective papers. We also include results for ProtoCon and
DebiasPL with additional pretraining (using MOCO [16]) and the Exponential
Moving Average Normalisation method proposed by [7] to match the settings used
in [42, 7].

###  4.2 Results and Analysis

Results. Similar to prior work, we report the results on the test sets of
respective datasets by averaging the results of the last 10 epochs of
training. For CIFAR and Mini-ImageNet, we report the average and standard
deviation over 5 different labeled splits, whereas we report for only 1 split
on larger datasets (ImageNet and DomainNet). Different from most previous
work, we only focus on the very low-label regime (2, 4, and 8 samples per
class, and 0.2% for ImageNet). As shown in Tab. 1 \- 3, we observe that
ProtoCon outperforms baselines in almost all the cases showing a clear
advantage in the low-label regime. It also exhibits less variance across the
different splits (and the different runs within each split). These results
suggest that besides achieving high accuracy, ProtoCon shows robustness and
consistency across splits in low-data regime.

Notably, our method performs particularly well on DomainNet. Unlike ImageNet
and CIFARs, DomainNet is an imbalanced dataset, and prior work [39] shows that
it suffers from high level of label noise. This shows that our method is also
more robust to noisy labels. This can be explained in context of our co-
training approach: using the prototypical neighbourhood label to smooth the
softmax label is an effective way to minimise the effect of label noise. In
line with previous findings [23], since in prototypical learning, all the
instances of a given class are used to calculate a class prototype which is
then used as a prediction target, it results in representations which are more
robust to noisy labels.

Finally, on ImageNet (Tab. 3), we improve upon the closest baseline with gains
of 2.2% in the challenging 0.2% setting; whereas we slightly fall behind PAWS
[2] in the 10% regime, again confirming our method’s usefulness in the label-
scarce scenario.

Figure 3: Analysis Plots. (a): Average disagreement between cluster and
classifier pseudo-labels versus ground truth accuracy of the different pseudo-
labels. The accuracy gap between refined pseudo-labels (green) and the
cluster’s and classifier’s (blue and orange) decreases with disagreement rate
(dashed black) showing that refinement indeed helps. (b), (c): Convergence
plots on CIFAR10/100 show that ProtoCon converges faster due to the additional
self-supervised training signal. (d):  ProtoCon w and w/out consistency loss.

Figure 4: The middle panel shows the most prototypical images of CIFAR-10
classes as identified by our model. Left (resp. right) panels show images
which have more accurate classifier (resp. cluster) pseudo-labels. Cluster
labels are more accurate for prototypical images while classifier labels are
more accurate for images with distinctive features (e.g. truck wheels) even if
not so prototypical. Such diversity of views is key to the success of our co-
training method. Table 3: SSL results on ImageNet with different percentage of
labels. $\dagger$ denotes results produced by our codebase. Other results are
reported as appearing in the cited work.

Method | Pre. | Epochs | 0.2% | 1% | 10%
---|---|---|---|---|---
Supervised | ✗ | 300 | – | 25.4 | 56.4
Representation learning methods: |  |
SwAV [8] | ✓ | 800 | – | 53.9 | 70.2
SimCLRv2++ [12] | ✓ | 1200 | – | 60.0 | 70.5
DINO [9] | ✓ | 300 | – | 55.1 | 67.8
PAWS++ [2] | ✓ | 300 | – | 66.5 | 75.5
PL & consistency methods: |  |
MPL [31] | ✗ | 800 | – | $65.3^{\dagger}$ | 73.9
CoMatch [22] | ✗ | 400 | $44.3^{\dagger}$ | 66.0 | 73.6
FixMatch [38] | ✗ | 300 | – | 51.2 | 71.5
FMatch + DA [38, 3] | ✗ | 300 | $41.1^{\dagger}$ | 53.4 | $71.5^{\dagger}$
FMatch + EMAN [7] | ✓ | 850 | 43.6 | 60.9 | 72.6
FMatch + DB [42] | ✗ | 300 | $45.8^{\dagger}$ | $63.0^{\dagger}$ | $71.7^{\dagger}$
FMatch + DB + EMAN [42] | ✓ | 850 | 47.9 | 63.1 | $72.8^{\dagger}$
ProtoCon | ✗ | 300 | 47.8 | 65.6 | 73.1
ProtoCon \+ EMAN [7] | ✓ | 850 | 50.1 | 67.2 | 73.5
_delta against best baseline_ |  |  | +2.2 | +0.7 | -2.0

How does refinement help? First, we would like to investigate the role of
pseudo-labeling refinement in improving SSL performance. Intuitively, since we
perform refinement by combining pseudo-labels from two different sources (the
classifier predictions in probability space and the cluster labels in the
prototypical space), we expect that there will be disagreements between the
two and hence considering both the views is the key towards the improved
performance. To validate such intuition, we capture a fine-grained view of the
training dynamics throughout the first 300 epochs of CIFAR-10 with 40 labeled
instances scenario, including: samples’ pseudo-labels before and after
refinement as well as their cluster pseudo-labels in each epoch. This enables
us to capture disagreements between the two pseudo-label sources up to the
individual sample level. In Fig. 3-a, we display the average disagreement
between the two sources over the initial phase of the training overlaid with
the classifier, cluster and refined pseudo-label accuracy. We observe that
initially, the disagreement (dashed black line) is high which corresponds to a
larger gap between the accuracies of both heads. As the training proceeds, we
observe that disagreement decreases leading to a respective decrease in the
gap. Additionally, we witness that the refined accuracy curve (green) is
almost always above the individual accuracies (orange and blue) which proves
that, indeed, the synergy between the two sources improves the performance.

On the other hand, to get a qualitative understanding of where each of the
pseudo-labeling sources helps, we dig deeper to classes and individual samples
level where we investigate which classes/samples are the most disagreed-upon
(on average) throughout the training. In Fig. 4, we display the most
prototypical examples of a given class (middle) as identified by the
prototypical scores obtained in the embedding space. We also display the
examples which on average are always correctly classified in the prototypical
space (right) opposed to those in the classifier space (left). As expected, we
find that samples which look more prototypical, albeit with less distinctive
features (e.g. blurry), are the ones almost always correctly classified with
the prototypical head; whereas, samples which have more distinctive features
but are less prototypical are those correctly classified by the discriminative
classifier head. This again confirms our intuitions about how co-training
based on both sources helps to refine the pseudo-label.

Finally, we ask: is it beneficial to use the entire dataset pseudo-label
history to perform refinement or is it sufficient to just use a few samples?
To answer this question, we use only a subset of the samples in each cluster
(sampled uniformly at random) to calculate cluster pseudo-labels in Eqn. 10.
For CIFAR-10 with 20 and 40 labels, we find that this leads to about 1-2%
(4-5%) average drop in performance, if we use half (quarter) of the samples in
each cluster. This reiterates the usefulness of our approach to leverage the
history of all samples (at a lower cost) opposed to a limited history of
samples.

Role of self-supervised loss. Here, we are interested to tear apart our choice
of self-supervised loss and its role towards the performance. To recap, our
intuition behind using that loss is to boost the learning signal in the
initial phase of the training when the model is still not confident enough to
retain samples for pseudo-labeling. As we see in Fig. 3-b and c. there is a
significant speed up of our model’s convergence compared to baseline methods
with a clear boost in the initial epochs. Additionally, to isolate the
potentially confounding effect of our other ingredients, we display in Fig.
3-d the performance of our method with and without the self-supervised loss
which leads to a similar conclusion. Finally, to validate our hypothesis that
instance-consistency loss is more useful than instance-discrimination, we run
a version of ProtoCon with an instance-discrimination loss akin to that of
SimCLR. This version completely collapsed and did not converge at all. We
attribute this to: 1) as verified by SimCLR authors, such methods work best
with large batch sizes to ensure enough negative examples are accounted for;
and 2) these methods treat each image as its own class and contrast it against
every other image and hence are in direct contradiction with the image
classification task; whereas instance-consistency losses only ensure that the
representations learnt are invariant to common factors of variations such as:
color distortions, orientation, _etc_. and are hence more suitable for semi-
supervised image classification tasks.

Table 4: Ablation results. -$\mathcal{L}_{*}$ denotes that the respective loss
is not applied, and  green marks the best option. Results are average accuracy
over 5 runs for CIFAR-10 (80).

Losses |  |  -$\mathcal{L}_{c}$ |  -$\mathcal{L}_{p}$ |  -($\mathcal{L}_{c}$,$\mathcal{L}_{p}$) | All
---|---|---|---|---|---
| 95.3 | 94.8 | 92.3 | 96.1
Cluster size ($n$) |  | 50 | 250 | 500 | 1000
| 95.7 | 96.1 | 94.3 | 92.1
Refinement Ratio ($\alpha$) |  | 0.5 | 0.7 | 0.8 | 0.9
| 86.7 | 94.5 | 96.1 | 95.2

Ablations. Finally, we present an ablation study about the important
hyperparametes of ProtoCon. Specifically, we find that $n$ (minimum samples in
each cluster) and $\alpha$ (mixing ratio between classifier pseudo-label and
cluster pseudo-label) are particularly important. Additionally, we find that
the projection dimension needs to be sufficiently large for larger datasets
(we use $d=64$ for CIFARs and 128 for all others). In Tab. 4, we present
ablation results on CIFAR-10 with 80 labeled instances.

##  5 Conclusion

We introduced ProtoCon, a novel SSL learning approach targeted at the low-
label regime. Our approach combines co-training, clustering and prototypical
learning to improve pseudo-labels accuracy. We demonstrate that our method
leads to significant gains on multiple SSL benchmarks and better convergence
properties. We hope that our work helps to commodify deep learning in domains
where human annotations are expensive to obtain.

Acknowledgement. This work was partly supported by DARPA’s Learning with Less
Labeling (LwLL) program under agreement FA8750-19-2-0501. I. Nassar is
supported by the Australian Government Research Training Program (RTP)
Scholarship, and M. Hayat is supported by the ARC DECRA Fellowship
DE200101100.

## References

  * [1] Eric Arazo, Diego Ortego, Paul Albert, Noel E O’Connor, and Kevin McGuinness.  Pseudo-labeling and confirmation bias in deep semi-supervised learning.  In 2020 International Joint Conference on Neural Networks (IJCNN), pages 1–8. IEEE, 2020.
  * [2] 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 Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8443–8452, 2021.
  * [3] David Berthelot, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel.  Remixmatch: Semi-supervised learning with distribution alignment and augmentation anchoring.  arXiv preprint arXiv:1911.09785, 2019.
  * [4] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel.  Mixmatch: A holistic approach to semi-supervised learning.  In Advances in Neural Information Processing Systems, pages 5049–5059, 2019.
  * [5] Avrim Blum and Tom Mitchell.  Combining labeled and unlabeled data with co-training.  In Proceedings of the eleventh annual conference on Computational learning theory, pages 92–100, 1998.
  * [6] Paul S Bradley, Kristin P Bennett, and Ayhan Demiriz.  Constrained k-means clustering.  Microsoft Research, Redmond, 20(0):0, 2000.
  * [7] Zhaowei Cai, Avinash Ravichandran, Subhransu Maji, Charless Fowlkes, Zhuowen Tu, and Stefano Soatto.  Exponential moving average normalization for self-supervised and semi-supervised learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 194–203, 2021.
  * [8] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  Advances in Neural Information Processing Systems, 33:9912–9924, 2020.
  * [9] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9650–9660, 2021.
  * [10] Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien.  Semi-supervised learning (chapelle, o. et al., eds.; 2006)[book reviews].  IEEE Transactions on Neural Networks, 20(3):542–542, 2009.
  * [11] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR, 2020.
  * [12] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton.  Big self-supervised models are strong semi-supervised learners.  Advances in neural information processing systems, 33:22243–22255, 2020.
  * [13] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le.  Randaugment: Practical automated data augmentation with a reduced search space.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 702–703, 2020.
  * [14] Yves Grandvalet and Yoshua Bengio.  Semi-supervised learning by entropy minimization.  In Advances in neural information processing systems, pages 529–536, 2005.
  * [15] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent-a new approach to self-supervised learning.  Advances in neural information processing systems, 33:21271–21284, 2020.
  * [16] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9729–9738, 2020.
  * [17] Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf.  Why relu networks yield high-confidence predictions far away from the training data and how to mitigate the problem.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 41–50, 2019.
  * [18] Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum.  Label propagation for deep semi-supervised learning.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5070–5079, 2019.
  * [19] Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  2009\.
  * [20] Chia-Wen Kuo, Chih-Yao Ma, Jia-Bin Huang, and Zsolt Kira.  Featmatch: Feature-based augmentation for semi-supervised learning.  arXiv preprint arXiv:2007.08505, 2020.
  * [21] Dong-Hyun Lee.  Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks.  In Workshop on challenges in representation learning, ICML, 2013\.
  * [22] Junnan Li, Caiming Xiong, and Steven CH Hoi.  Comatch: Semi-supervised learning with contrastive graph regularization.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9475–9484, 2021.
  * [23] Junnan Li, Caiming Xiong, and Steven CH Hoi.  Learning from noisy data with robust representation learning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9485–9494, 2021.
  * [24] Yiting Li, Lu Liu, and Robby T Tan.  Decoupled certainty-driven consistency loss for semi-supervised learning.  arXiv preprint arXiv:1901.05657, 2019.
  * [25] Thomas Lucas, Philippe Weinzaepfel, and Gregory Rogez.  Barely-supervised learning: semi-supervised learning with very few labeled images.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 1881–1889, 2022.
  * [26] Islam Nassar, Munawar Hayat, Ehsan Abbasnejad, Hamid Rezatofighi, Mehrtash Harandi, and Gholamreza Haffari.  Lava: Label-efficient visual learning and adaptation.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 147–156, 2023.
  * [27] Islam Nassar, Samitha Herath, Ehsan Abbasnejad, Wray Buntine, and Gholamreza Haffari.  All labels are not created equal: Enhancing semi-supervision via label grouping and co-training.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7241–7250, 2021.
  * [28] Anh Nguyen, Jason Yosinski, and Jeff Clune.  Deep neural networks are easily fooled: High confidence predictions for unrecognizable images.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 427–436, 2015.
  * [29] Avital Oliver, Augustus Odena, Colin A Raffel, Ekin Dogus Cubuk, and Ian Goodfellow.  Realistic evaluation of deep semi-supervised learning algorithms.  In Advances in neural information processing systems, pages 3235–3246, 2018.
  * [30] Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang.  Moment matching for multi-source domain adaptation.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1406–1415, 2019.
  * [31] Hieu Pham, Zihang Dai, Qizhe Xie, and Quoc V Le.  Meta pseudo labels.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11557–11568, 2021.
  * [32] Qi Qian, Yuanhong Xu, Juhua Hu, Hao Li, and Rong Jin.  Unsupervised visual representation learning by online constrained k-means.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16640–16649, 2022.
  * [33] Sachin Ravi and Hugo Larochelle.  Optimization as a model for few-shot learning.  2016\.
  * [34] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  International journal of computer vision, 115(3):211–252, 2015\.
  * [35] Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen.  Regularization with stochastic transformations and perturbations for deep semi-supervised learning.  In Advances in neural information processing systems, pages 1163–1171, 2016.
  * [36] David Sculley.  Web-scale k-means clustering.  In Proceedings of the 19th international conference on World wide web, pages 1177–1178, 2010.
  * [37] Jake Snell, Kevin Swersky, and Richard Zemel.  Prototypical networks for few-shot learning.  Advances in neural information processing systems, 30, 2017.
  * [38] Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel.  Fixmatch: Simplifying semi-supervised learning with consistency and confidence.  arXiv preprint arXiv:2001.07685, 2020.
  * [39] Shuhan Tan, Xingchao Peng, and Kate Saenko.  Class-imbalanced domain adaptation: An empirical odyssey.  In European Conference on Computer Vision, pages 585–602. Springer, 2020.
  * [40] Jesper E Van Engelen and Holger H Hoos.  A survey on semi-supervised learning.  Machine Learning, 109(2):373–440, 2020.
  * [41] Erik Wallin, Lennart Svensson, Fredrik Kahl, and Lars Hammarstrand.  Doublematch: Improving semi-supervised learning with self-supervision.  arXiv preprint arXiv:2205.05575, 2022.
  * [42] Xudong Wang, Zhirong Wu, Long Lian, and Stella X Yu.  Debiased learning from naturally imbalanced pseudo-labels.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14647–14657, 2022.
  * [43] Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V Le.  Unsupervised data augmentation for consistency training.  arXiv preprint arXiv:1904.12848, 2019.
  * [44] Yi Xu, Lei Shang, Jinxing Ye, Qi Qian, Yu-Feng Li, Baigui Sun, Hao Li, and Rong Jin.  Dash: Semi-supervised learning with dynamic thresholding.  In International Conference on Machine Learning, pages 11525–11536. PMLR, 2021.
  * [45] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  arXiv preprint arXiv:1605.07146, 2016.
  * [46] Xiaohua Zhai, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer.  S4l: Self-supervised semi-supervised learning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1476–1485, 2019.
  * [47] Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura, and Takahiro Shinozaki.  Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling.  Advances in Neural Information Processing Systems, 34:18408–18419, 2021.
  * [48] Mingkai Zheng, Shan You, Lang Huang, Fei Wang, Chen Qian, and Chang Xu.  Simmatch: Semi-supervised learning with similarity matching.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14471–14481, 2022.

## Appendix

##  A Constrained K-means Additional Details

Qian et al. [32] proposed the online mini-batch solver for the constrained
K-means objective (Eqn. 3) proposed by [6], and used it for unsupervised
representation learning. In our method, we adopted the same solver but for a
different purpose; we use online clustering as an alternative to offline
nearest neighbour search to identify neighbourhood of images and leverage such
information to perform our label refinement procedure. To that end, due to the
empirical observation that the maximal value of dual variables is well
bounded, our Eqn. 8 is an approximation of the original dual variables update
proposed by Qian et al. after each mini-batch:

$\displaystyle\rho^{t}_{k}=\Pi_{\Delta_{\delta}}(\rho^{t-1}_{k}-\eta\frac{1}{B}\sum_{i=1}^{B}(\mu_{i,k}^{t}-\frac{\gamma}{N})),$
(1)

where $\Pi_{\Delta_{\delta}}$ projects the dual variables to the domain
$\Delta_{\delta}=\\{\rho|\forall k,\rho_{k}\geq 0,\|\rho\|_{1}\leq\delta\\}$.

We refer the readers to the original paper for guarantees of performance
complete proofs.

Figure 5: Analysis Plots. (a): Cluster Purity per class of CIFAR-10 vs
training epochs, when trained using ProtoCon with 4 images per class. (b):
Pseudo-label accuracy per class vs training epochs. Best viewed in color.

Constrained vs unconstrained clustering. Our purpose in ProtoCon is to use
K-means as an alternative for offline nearest-neighbours retrieval, which
automatically mandates that we use equi-partition clustering by constraining
minimum cluster size $\gamma$ to be the number of nearest neighbours $n$.
However, we relax this constraint to $\gamma=0.9n$ to allow cluster sizes to
slightly vary to capture the inherent imbalance in salient properties of
different classes. Empirically, we found this to work well across the datasets
we used. We also tested the setting with $\gamma=0$ which translates to
unconstrained clustering. This setting was unstable and did not lead to
performance gains; where we found that clustering collapses to only a few
clusters. For example in CIFAR-10 (40 labels) setting, K-means converged to
only 20 clusters. The consequence is that we have only 20 cluster pseudo-
labels to use for refining all the unlabeled samples in subsequent epochs
which is a very general summary of neighbourhoods and hence it hurts the
performance rather than help it. Please refer to Tab. 4 for further ablations
on the value of $n$.

Mini-batch updates vs Epoch updates Another decision choice is the frequency
of cluster centroids updates (Eqn. 9). Since ProtoCon does not memorise image
representations, centroids can be updated either every mini-batch, or by
accumulating representations of images based on their cluster assignment
throughout an epoch and then performing the update once at the end of the
epoch. The former solution is useful in helping K-means convergence which
requires multiple assignment-update iterations, however it leads to higher
variance due to the stochastic nature of mini-batches. On the other hand, the
latter solution is also sub-optimal as it requires long time for clusters to
converge. Accordingly, we adopted a warmup period during which we use mini-
batch updates to speed up convergence, henceforward, we switch to epoch
updates to stabilise the centroids and exhibit less variance. We found that
for smaller datasets, 20 epochs of warmup are sufficient, while for the larger
datasets with more classes, we increase the warmup period to 70 epochs.

##  B Additional Training Dynamics Analysis

Here, to further understand ProtoCon, we examine more of its training
dynamics.

Figure 6: Analysis Plots. (a): Pseudo-label accuracy vs epochs. (b): Retention
rate vs epochs which denotes the ratio of unlabeled samples retained by each
method for pseudo-labeling (i.e. with maximum confidence score higher than the
threshold $\tau$.)

Clustering purity vs pseudo-label accuracy. First, we investigate the
properties of the clusters as training proceeds. We follow a similar setup
like that used to obtain Fig. 4, but this time, we use the captured statistics
to calculate cluster purity for each class. Specifically, by the end of each
epoch, we count the members of each cluster (e.g. for CIFAR-10, we use
$K=250$, so we count the number of images assigned by K-means to each of the
250 clusters), then for each cluster, we check the most dominant class among
its members based on their ground truth labels. Subsequently, we calculate the
purity of each cluster as the ratio between the number of images belonging to
the dominant class to the total number of cluster members. Finally, to
calculate purity for a given class, we average the described ratio across all
clusters for which that class is the dominant one. In Fig. 5, we display
cluster purity per class of CIFAR-10 during the first 130 epochs of training
side-by-side to the pseudo-label accuracy for each class. This is to allow us
to investigate the clustering effectivness in the critical initial phase of
training and how it affects the obtained pseudo-labels quality. We see that
for the more distinguishable classes (e.g. truck or ship), clustering purity
increases significantly faster than others matching with a corresponding
increase in pseudo-label accuracy. Whereas for more confusing classes (e.g.
horse and deer), the cluster purity suffers a slow increase accompanied with
what seem to be high disagreement between cluster and classifier pseudo-labels
leading to an overall slow increase of pseudo-label accuracy (note that we
display the refined pseudo-label accuracy in the figure). Finally, the most
confusing classes (e.g. cat and dog) have the lowest cluster purity leading to
a low pseudo-label accuracy at first, but we notice that once the majority of
other classes are learnt (i.e. have higher accuracy, the more confusing
classes start to catch up (notice the cat and dog curves towards the end of
Fig. 5-b). This is in line with our expectation that easy classes are first
learnt by the network, then it moves on to discriminate the less obvious ones.

Pseudo-label Retention Ratio. Like the state-of-the-art SSL method (DebiasPL
[42]), ProtoCon is also a confidence-based pseudo-labeling method albeit with
additional ingredients. Hence, both methods only retain high-confidence
unlabeled samples for pseudo-labeling. In Fig. 6, we examine the retention
rate (i.e. ratio of samples with maximum confidence exceeding the threshold
$\tau$) for both methods as training proceeds (b), and compare it with the
pseudo-labeling accuracy exhibited by each (a). We observe that even though
our method outperforms DebiasPL, in terms of accuracy, throughout the
training, it consistently retains almost 10% less samples for pseudo-labeling.
This finding speaks to our original motivation (see Sec. 1) with regards to
the over-confidence problem underpinning the lower performance of SOTA methods
in label-scarce regime. Compared to its counterparts, ProtoCon is more
conservative when it comes to admitting a sample as “reliable” for pseudo-
labeling; primarily because the refined pseudo-labels we employ is a
combination of the original classifier pseudo-label and the neighbourhood
pseudo-label. As we show in Fig. 3-a, the disagreement between the two results
in a lower overall confidence in predictions. Such conservative nature of
ProtoCon is key to avoiding confirmation bias even when there is only a few
labeled samples available.

Table 5: CIFAR and Mini-ImageNet accuracy in moderate-label regime for
different amounts of labeled samples averaged over 3 different splits. All
results are produced using the same codebase and same splits.

|  | CIFAR-100 |  | Mini-ImageNet
---|---|---|---|---
Total labeled samples |  | 2500 | 4000 |  | 2500 | 4000
FixMatch [38] |  | 71.71$\pm$0.35 | 74.08$\pm$0.13 |  | 44.53$\pm$0.44 | 50.21$\pm$0.09
FixMatch + DB [42] |  | 72.44$\pm$0.15 | 74.43$\pm$0.06 |  | 46.18$\pm$0.23 | 52.00$\pm$0.04
ProtoCon |  | 73.31$\pm$0.43 | 75.18$\pm$0.02 |  | 48.61$\pm$0.34 | 53.67$\pm$0.06
_delta against best baseline_ |  | +0.87 | +0.75 |  | +2.43 | +1.67

Figure 7: Additional examples to complement Fig. 4.

##  C ProtoCon in Moderate-label Regime

In this section, we examine our method performance when more than 10 images
per class are available (which we call moderate-label regime). To recap, our
method primarily aims to address confirmation bias in label-scarce settings.
Yet, intuitively, the refinement strategy might also help moderate-label
regimes. As such, we investigate this hypothesis by running additional
experiments on CIFARs and Mini-ImageNet with 25, and 40 images per class. We
find that for CIFAR-10, performance already saturates after 10 images per
class and most of the compared methods perform similarly. As for the other two
datasets with 100 classes each, we find ProtoCon to still provide performance
gains. However, with more labels available, we find that using less
neighbouring samples to perform the refinement (i.e. less $n$) works better.
Specifically, we reduce $n$ by a factor of 10 (i.e. $n=25$ instead of
$n=250$). Additionally, since with more labels, all the compared methods
exhibit significantly less variance, we report results only based on 3 runs
instead of 5. Please refer to the results in Tab. 5.

##  D Additional Quantitative Examples

Here, we detail our experimental setup for obtaining Fig. 4 and we provide
additional examples in Fig. 7.

Experimental Setup. As training proceeds, for each epoch, we capture per-image
statistics such as: the classifier pseudo-label and its max score (i.e.
$\operatorname*{arg\,max}\boldsymbol{p}_{w}$ and $\max\boldsymbol{p}_{w}$
respectively); cluster pseudo-label and its max score (i.e.
$\operatorname*{arg\,max}\boldsymbol{z}^{a}$ and $\max\boldsymbol{z}^{a}$
respectively), sample prototypical score (i.e.
$\boldsymbol{q}^{w}\cdot\mathcal{P}_{\hat{y}}$) denoting how close a sample is
to its class prototype. Subsequently, to obtain the prototypical images (in
middle panel of Fig. 4 and 7), we rank images of each class based on their
prototypical score averaged over the first 500 epochs of training.
Additionally, we identify images for which the cluster pseudo-labels are, on
average, more accurate than that of the classifier (and the other way around)
by comparing the respective pseudo-labels with the ground truth label of each
image. Thus, we display on the left panel images for which the classifier
pseudo-label is, on average, more accurate than the cluster pseudo-label, and
the opposite on the right panel.

Additional Examples. In Fig. 7, we provide more examples to complement those
in Fig. 4. To reiterate, we see that the cluster pseudo-labels which capture
the samples’ neighbourhood in the prototypical space (trained via our
prototypical loss) are usually more accurate if images are more prototypical
even if they are lacking discriminative features (e.g. blurry images or zoomed
out images). In contrast, the pseudo-labels in the class probability space
(trained via one-hot cross entropy) are usually more accurate for images with
discriminative features (e.g. car bumpers or deer horns) even if they lack
prototypicality. The diversity of views captured via the different labels is
key to ProtoCon’s effectiveness as it helps the classifier learns via the
disagreement between the two views through the refined label.