Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: Summary:
The paper proposes a self-supervised learning procedure to train deep neural networks within an unsupervised learning setting. The authors build their work on a pretext task that consists in maximizing the information between the input data samples and labels that are basically obtained by a self-labeling procedure that clusters them in K distinct classes. This is similar to what was done in DeepCluster, a previous self-supervised algorithm that self-labels samples through clustering. However, differently from that approach, the current method does not introduce any additional clustering cost functions. Instead it implicitly achieves self-labeling by simply adding the constraint that label assignments equally partition the dataset. This constraint acts as a "regularizer" that allows the authors to minimize the cross-entropy loss between inputs and pseudo-labels while avoiding the degenerate trivial solution where all samples are assigned to the same pseudo-label. As a result, the authors are able to derive a self-labeling method that optimizes the same cross-entropy loss as the classification task. That is done by remarking that minimizing the loss function over the pseudo-label assignments (under the equal partition constraint) can be formulated as an optimal transport problem that can be solved efficiently with a fast version of the Sinkhorn-Knopp algorithm. In practice, what the authors do at training time is to alternate between 1) minimizing the average cross-entropy loss by training the neural network (feature extractor + linear classification head) given a fixed pseudo-labels assignment, and 2) optimizing the pseudo-label assignments implemented as a matrix Q of posterior distribution of labels given the sample index, which, as said, can be done efficiently with a KL-regularized version of Sinkhorn. Moreover, this last step can be carried out simultaneously for multiple distinct classification heads (with possibly different number of labels), each sharing the same feature extractor but inducing a different matrix Q. At this point, the number of classification heads can be treated as a hyperparameter of the algorithm.
The authors then go on to show that this new algorithm is competitive with current state of the art method with several architectures in terms of providing a good feature extractor for downstream image classification, detection and segmentation tasks. They for instance consistently beat DeepCluster, the main direct competitor, on classification and detection tasks.
They also conduct ablation studies that provide interesting insights on the functioning of their algorithms and the effects of the multiple classification heads, the number of clusters, and the quality of the learned assignment. Intriguingly, on ImageNet they find for example that AlexNet obtains better performance at validation when it's trained from scratch on labels obtained with their self-labeling procedure, as opposed to the original labels.

Decision:
In my opinion this paper should be a clear accept. The paper is well written, presents an elegant idea in a clear and straight-forward manner, and is solidly built on top of the current literature on self-supervised learning for image processing, which is also very well summarized.
The feature extractors obtained with the proposed algorithm are convincingly tested and validated on several downstream tasks (like classification on ImageNet, PascalVOC classification, detection and segmentation), and that is done for several base architectures, obtaining performances that are competitive with state-of-the-art. In addition, a series of careful ablation studies help in gleaning some scientific understanding on the method.

Minor comments:
- The authors refer to traditional clustering like k-means as being "generative", which a little confusing. Clustering algorithms can be derived within a probabilistic framework by positing a generative model of the data, however, strictly speaking, k-means is not by itself is not a generative approach. It's a minor point, but it could be helpful to be more precise about this, in order to avoid possible confusion. The main point that the authors want to make in this regard is that their framework eschews having to posit an additional clustering cost function.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper develops a novel self-supervised learning method by combing clustering and representation learning together.
Different from other methods, the two tasks are optimized within the same objective function. Under the weak assumption that the number of samples should be similar across different clusters, the authors further develop a modified Sinkhorn-Knopp algorithm to solve the problem. Experiments on real-world image data demonstrate the effectiveness of the developed solution. In general, the whole paper is well written and the developed solution is interesting. However, I have the following comments:

1. I am still confused about the difference between self-supervised learning and clustering when we do not have labeled data. From my point of view, they are actually the same thing. The authors are suggested to provide more explanations about the differences.
2. The used assumption that samples are uniformed distributed across different cluster are too strong in practice. In many real-world scenarios, the size of the cluster often very a lot, I was wondering how the proposed method can tackle this issue.
3. Experiments are only conducted on the image dataset, which is not quite convincing. The authors are suggested to use the datasets that are normally used in the clustering research to further demonstrate the effectiveness of the method.
4. It is quite surprising that conventional clustering evaluation metrics such as Normalized Mutual Information and Adjusted Rand Index are not used in the experiments.
5. How about the time complexity of the developed algorithm? Can it be scaled to large datasets? Further complexity analyzes are suggested.
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: Summary & Pros
- This paper proposes a representation learning method based on clustering. The proposed method performs clustering and representation learning alternatively and simultaneously. This approach requires only a few domain-specific prior (precisely, CNN prior) while self-supervised learning requires more prior domain knowledge.
- Compared to the previous work, DeepCluster, this paper uses the same objective for clustering and representation learning. For clustering, the objective can be formulated as an optimal transport problem and it can be efficiently solved. This approach provides desired properties such as convergence.
- This paper shows the proposed method outperforms DeepCluster and it achieves comparable performance with SOTA methods in the representation learning literature.

Concerns #1: More analysis should be provided.
- The author claimed that the proposed method has better convergence properties than DeepCluster. To verify that, more experimental or theoretical supports should be provided. For example, the convergence rate might be checked as Figure 2(b) in DeepCluster paper using NMI against the previous iteration.
- If the number of each class is imbalanced, the equipartition constraint might degrade the quality of the label assignment. Thus, ablation studies about the imbalance setting on small-sized datasets such as CIFAR should be provided. I think K-means could prevent such imbalance issues, so in this case, DeepCluster might perform well.

Concerns #2: Performance is still far from SOTA.
- As reported in Section 4.3, the proposed method still underperforms SOTA methods significantly. The SOTA method can be considered as a combination of (instance-wise) clustering and self-supervision. Thus, such a combination should be tried for improving performance.

Concerns #3: How to guarantee this approach finds good semantic representations?
- In this approach, the model generates a task via clustering, so it might suffer from unsuitable solutions even under the equipartition constraint. If we use a very deeper architecture and a larger size of embedding, then the main optimization problem (3) might be solved before correct label assignments. Moreover, at the first iteration, the labels might be totally random, and then clustering quality is also zero. How to guarantee the clustering quality is gradually improved while training?

The proposed method provides meaningful gain compared to the previous work, DeepCluster. I think this direction against self-supervised learning is important because it requires relatively smaller domain knowledge. However,  I'm not sure how the proposed method can converge stably and efficiently. So I think it would be better if more analysis about the convergence is given in a rebuttal.

review_title: Official Blind Review #3

Meta-review: The paper focuses on supervised and self-supervised learning. The originality is to formulate the self-supervised criterion in terms of optimal transport, where the trained representation is required to induce $K$ equidistributed clusters. The formulation is well founded; in practice, the approach proceeds by alternatively optimizing the cross-entropy loss (SGD) and the pseudo-loss, through a fast version of the Sinkhorn-Knopp algorithm, and scales up to million of samples and thousands of classes.

Some concerns about the robustness w.r.t. imbalanced classes, the ability to deliver SOTA supervised performances, the computational complexity have been answered by the rebuttal and handled through new experiments. The convergence toward a local minimum is shown; however, increasing the number of pseudo-label optimization rounds might degrade the results. 

Overall, I recommend to accept the paper as an oral presentation. A more fancy title would do a better justice to this very nice paper ("Self-labelling learning via optimal transport" ?).  
Decision: Accept (Spotlight)