  Cluster discrimination is an effective pretext task for unsupervised
representation learning, which often consists of two phases: clustering and
discrimination. Clustering is to assign each instance a pseudo label that will
be used to learn representations in discrimination. The main challenge resides
in clustering since prevalent clustering methods (e.g., k-means) have to run in
a batch mode. Besides, there can be a trivial solution consisting of a
dominating cluster. To address these challenges, we first investigate the
objective of clustering-based representation learning. Based on this, we
propose a novel clustering-based pretext task with online \textbf{Co}nstrained
\textbf{K}-m\textbf{e}ans (\textbf{CoKe}). Compared with the balanced
clustering that each cluster has exactly the same size, we only constrain the
minimal size of each cluster to flexibly capture the inherent data structure.
More importantly, our online assignment method has a theoretical guarantee to
approach the global optimum. By decoupling clustering and discrimination, CoKe
can achieve competitive performance when optimizing with only a single view
from each instance. Extensive experiments on ImageNet and other benchmark data
sets verify both the efficacy and efficiency of our proposal. Code is available
at \url{https://github.com/idstcv/CoKe}.
