acceptodds
Under review as a conference paper at ICLR 2027

Converge to Surprise: Evolutionary Self-supervised Image Clustering

Abstract

A variety of self-supervised image clustering approaches are invented in the past years. However, all dominant approaches are exploitative: The direction of parameter updates is determined by known states (observed input samples and existing parameters). We propose an explorative self-supervised learning framework that steps out of this zone. We define a surprise score that measures how unlikely the model's output representation is, assuming that all pixels are i.i.d. random noise. Maximizing the surprise score forces the deep learning model to reject the random noise null hypothesis, or equivalently, to discover non-randomness from data. Also, we propose a fundamental assumption: a surprise score cannot, in general, be fully optimized by exploitative optimization approaches. Thus, we propose the converge-to-surprise scheme to optimize a model: an evolution-strategy (ES) outer loop, which maximizes the surprise score using the mutation-selection mechanism, paired with a periodic gradient-descent inner loop, which uses the surprising clusters already discovered by ES as surrogate targets. On simple image benchmarks, our framework trained from scratch achieves new state-of-the-art results in non-parametric self-supervised image clustering — the strictest deep-clustering setting, where the number of classes is unknown during training.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
self-supervised learning, evolution strategy, image clustering, explorative vs exploitative, information theory in machine learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_dKCQOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes converge-to-surprise, a self-supervised method for clustering images without knowing the number of clusters in advance. It compares cluster predictions from two independently augmented checkerboard views, rewarding agreement that is unlikely under an i.i.d. pixel-noise assumption.

An evolution strategy explores parameter variations to increase the surprise score, while periodic gradient-descent training reinforces pseudo-labels from surprising, balanced clusters. On MNIST, Fashion-MNIST, and USPS, a ResNet-9 with K=64K=64 achieves competitive results and discovers cluster counts close to 10. The paper reports less satisfactory performance on CIFAR-10.

Critical strengths
  • The core idea is distinctive and easy to follow. The paper uses complementary checkerboard masks to create two views with no shared pixels, then measures how often they receive the same cluster assignment.
  • The optimization strategy is clearly presented. Evolution strategies explore parameter space, while periodic gradient-descent steps reinforce clusters identified as surprising.
  • The experiments include useful component analyses. The ablations examine augmentation, the gradient-training inner loop, and USPS-specific anisotropic augmentation. The authors also report less satisfactory performance on CIFAR-10.
Critical weaknesses
  • The generality of the claims is not yet established. Experiments cover MNIST, Fashion-MNIST, and USPS, with mixed results across datasets and metrics. For example, the method is close to DeepDPM on MNIST ACC but has lower NMI on Fashion-MNIST. These results are promising on the evaluated benchmarks, but provide limited evidence for broader claims about image clustering.
  • The statistical assumptions behind the surprise score need further support. The null match probability is defined as qk=pk2,q_k = p_k^2, which assumes that both views have the same cluster marginal. Since the masks retain different pixel positions, it would help to explain when their output distributions should be identical and whether this holds in practice. The paper also estimates pkp_k from the same batch used to count matches. The authors treat each cluster's match count as binomial and state that dependence across clusters has only a weak effect; clarification of the conditions and limitations of this approximation would strengthen the score's statistical interpretation.
  • The checkerboard masking strategy lacks a direct ablation. The “no augmentation” experiment retains checkerboard masking and removes only augmentation. It therefore does not show whether the checkerboard pattern itself is important or whether a different disjoint partition would work similarly.
  • One reference appears to have inconsistent bibliographic details. The Batina et al. (2011) entry pairs the title “Web text corpus for natural language processing” with Journal of Cryptology, 24(2), 269–291, which appears to refer to a different article. The authors should verify the reference and confirm that the corrected source supports the independence claim.
Questions for authors
  • Checkerboard ablation: The checkerboard pattern is central to the construction, but the current ablations do not isolate its contribution. Have you tried random disjoint half-pixel masks under the same training setup? Comparing those results with checkerboard masking could show whether the specific pattern matters while preserving the no-shared-pixel property. A separate comparison with no masking and independently augmented views could also help assess the effect of using disjoint views, although it would change both masking and pixel overlap.
  • Equal marginals: The score uses qk=pk2,q_k = p_k^2, which seems to rely on the two masked views having equal cluster marginals. Have you checked the marginals separately for each view? If they differ, it would be interesting to see whether using qk=pk(i)pk(j)q_k = p_k^{(i)}p_k^{(j)} changes the surprise scores or clustering results.
  • Sensitivity to spatial structure: Have you tried randomly permuting pixel locations within each image while preserving its pixel-value histogram? Comparing the surprise scores with those on the original data could help clarify whether the score reflects spatial image structure.
  • Equation (64): At q^k=qk\hat q_k = q_k, the sigmoid limit is 1/21/2, whereas the strict indicator shown in the equation is zero. The KL term vanishes at equality, so this may not affect the limiting score, but could the equation be clarified? It would also help to specify how the relaxation is handled at boundary values such as qk=0q_k=0.
  • Binomial bound: Since pkp_k is estimated from the same batch used to count matches, could you clarify the conditions under which the binomial tail bound in Equation (5) applies with this estimate? The paper also notes weak dependence across cluster counts; it would be helpful to explain how that dependence affects the interpretation of the summed score.
  • Number of runs: Table 1 reports results over ten runs, and Table 2 specifies ten runs for the full model and five for each ablation. Appendix F, however, states that five independent experiments were run for each dataset. Could you clarify which run counts apply to the main results and ablations?
2 comments

Thank you again for your detailed and constructive review. Your suggestions were very concrete, and we have now run the checks you proposed. The revised manuscript reports them in Section 4.4, Table 2 and Appendices H and I. We summarize them below.

Q1: checkerboard ablation

Thank you for this suggestion. We trained with random disjoint half-pixel masks under the same setup (five runs per dataset): each image gets a fresh random set of exactly half of the pixel positions for one view and the complement for the other. This keeps the no-shared-pixel property, but in our runs it gave clearly lower results than the checkerboard (Table 2):

ACC (%) / K̂MNISTFashion-MNISTUSPS
checkerboard97.9 / 10.164.1 / 11.293.4 / 10.2
random half mask84.4 / 8.652.9 / 9.280.0 / 8.4

The random mask tends to merge classes. One possible reason is that a random half can leave gaps of several pixels along a stroke, whereas under the checkerboard every missing pixel has its four neighbors in the same view.

Q2: equal marginals (Appendix I)

Because the two patterns are swapped between the views by a per-image coin flip, the two views have equal marginals by construction. To check your stronger question directly, we fixed the white positions to one view and the black positions to the other on every test image:

  • The total-variation distance between the two views' cluster marginals is 0.17%, 0.49% and 0.31% on MNIST, Fashion-MNIST and USPS, close to the 0.14%, 0.30% and 0.28% between two exchangeable views.
  • A Bonferroni-corrected sign test per cluster finds a difference in only one cluster of one MNIST run, in no USPS run, and in 0.7 of 11.2 clusters on average on Fashion-MNIST (largest difference 0.4 points).
  • Replacing pₖ² by pₖ⁽ⁱ⁾ · pₖ⁽ʲ⁾ changes the score by less than 0.5% and leaves the number of surprising clusters unchanged in every run.

Q3: sensitivity to spatial structure (Appendix I)

Following your suggestion, we permuted the pixel positions within each test image before masking. This removes 97–99% of the score, and NMI drops below 9%. On i.i.d. pixel noise, the score falls further, to the level of an independent pairing of the views, and no cluster is surprising. The small residual on permuted images is expected, since the two views still share the image's pixel histogram.

Q4: Equation (64)

Thank you, you are right. The limit holds only for q̂ₖ ≠ qₖ; at q̂ₖ = qₖ the sigmoid equals 1/2. Since D(q̂ₖ ‖ qₖ) = 0 at equality, the limit of the soft score still equals the hard score, and we will state this explicitly. For boundary values, the hard score uses 0 · log 0 = 0: a cluster with no match contributes nothing, and any match implies qₖ > 0, so every term is finite. In the relaxation, q̂ₖ and qₖ are clamped to [10⁻¹², 1 − 10⁻¹²] before the logarithms.

Q5: binomial bound with a plug-in pₖ

We agree that, with pₖ estimated from the same batch, the binomial tail bound is an approximation rather than an exact test. Likewise, because of the dependence across clusters, the summed score is best read as a test statistic rather than the log-probability of a joint event. To calibrate it, we used the exact null given the batch marginals: shuffling one view's predictions across images (the "independent pairing" row in Appendix I). Under this null, the score is 0.6–1.2 × 10⁻³ and no cluster passes τ, compared with about 1.4 on real images. So at our batch size (N = 3000), the plug-in estimate and the dependence across clusters appear to have little practical effect. We will add this clarification to Section 3.2.

Generality

We fully agree that our evidence is limited to three small grayscale datasets, and we will word our claims accordingly. Section 4.4 adds two robustness experiments:

  • Varying the maximum number of clusters K ∈ {32, 64, 96, 128}: the number of inferred clusters stays at 9.3–10.1 (MNIST), 10.7–11.2 (Fashion-MNIST) and 10.2–10.3 (USPS).
  • Keeping only 6–9 classes: the number of inferred clusters follows the true number of classes on MNIST.

Thank you again for the careful reading, including the reference and the run counts, which we corrected earlier. We would be glad to provide any further details.

Thanks for the new experiments and the clear answers. Most of my questions on the statistical side are resolved.

But my main concerns remain. The random-mask result shows that the gain depends on the chessboard pattern itself, since both masks keep the views independent under the null. This is not explained by the statistical argument of the paper, and the comparison without masking is still missing. On generality, the new experiments vary K and K* within the same three datasets, so the evidence is still limited to small grayscale benchmarks, and the revised abstract and conclusion still claim state-of-the-art results. Also, Appendix L cites Table 1 numbers (98.3 / 64.5 / 94.9%) that do not match Table 1.

So I will keep my rating at 2. I do appreciate the effort you put into the discussion.

Reviewer_UgxZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper is easy to follow and understand. It proposes an explorative self-supervised learning framework for self-supervised image clustering. The main idea is to maximize the surprise score to discover non-randomness in data using a mutation-selection mechanism. The surprise objective is interesting, but evolutionary optimization and pseudo-label training are established techniques.

The problem is relevant: discovering meaningful image clusters without knowing the number of classes is practically important. The proposed method improves several reported metrics, especially on USPS, but does not consistently outperform DeepDPM.

Successful results are limited to only 3 small grayscale detests all with only 10 classes while performance on CIFAR-10 is substantially weaker. Comparisons with published baseline results also use different feature-learning pipelines, making it difficult to determine how much improvement comes from the proposed objective and evolutionary optimization.

Critical strengths
  • an interesting approach to non parametric self-supervised images clustering without actually knowing the true number of classes or requiring a separately pre-trained feature extractor
  • promising results supported by useful component ablations
Critical weaknesses
  • Limited evidence of generalization. Successful evaluation covers only three small grayscale datasets, all with ten classes.
  • The improvements are mixed, and their source is not sufficiently isolated. MNIST accuracy is essentially tied with DeepDPM, while Fashion-MNIST NMI decreases from 68.0% to 64.0%. The larget accuracy gain on USPS, depends strongly on dataset-specific anisotropic augmentation: removing ir reduces accuracy from 93.4% to 83.4%.
  • Differences in baseline training pipelines, it makes the advantage attributable to the proposed objective and optimizer uncertain.
Questions for authors
  • Would the proposed method still outperform DeepDPM if both used comparable feature-learning networks, data augmentation, and training budgets?
  • Can the proposed method reliably discover the number of clusters when datasets contain different numbers of classes, and when the maximum allowed number of clusters changes?
  • Could you compare evolutionary search and gradient-based optimization when both use the same pseudo-label training, network, and data augmentation, with comparable computing time? This can help determine whether evolutionary search itself provides the improvement, or whether the improvement mainly comes from the additional pseudo-label training.
Reviewer_2QGbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes an exploratory self-supervised learning framework for non-parametric image clustering that does not require prior knowledge of the number of clusters during training. It overcomes the reliance of existing mainstream methods on specific observed samples or predefined parameters. The framework introduces a surprise score, which quantifies the improbability of the model's output under the null hypothesis that the pixels are independent and random. To maximize this score, the framework employs a two-layer optimization mechanism. The outer loop utilizes an evolutionary strategy, while the inner loop periodically performs gradient descent. Throughout this process, the identified clusters serve as a surrogate objective for training.

Critical strengths

1.The surprise score provides an interpretable objective for discovering non-random structure in images.

2.The framework combines evolution strategies with periodic gradient-descent training on discovered clusters.

3.Experiments show competitive clustering performance on three benchmarks without knowing the number of classes.

Critical weaknesses

1.The evaluation covers a limited range of recent benchmarks and lacks sufficiently controlled comparisons regarding objectives, training procedures, and computational budgets.

2.The distinctions between this approach and related recent research, as well as the statistical and semantic rationale for the surprise score, have not been adequately justified.

Questions for authors

1.Could the authors expand the discussion of recent self-supervised image clustering methods, particularly those that do not assume a fixed number of classes, and clarify the differences in their objectives and optimization strategies?

2.Could the authors compare their method with more recent approaches, specifically those published between 2024 and 2026 that address image clustering when the number of categories is unknown? If direct comparisons are not feasible, please clarify the differences in terms of task settings or evaluation protocols.

3.Conducting further controlled comparisons, while ensuring alignment in objectives, training procedures, and computational budgets, would help refine optimization hypotheses.

4.The statistical interpretation of surprise scores and their connection to semantic clustering requires further clarification and validation.

1 comment

Thank you again for your thoughtful review. Your questions helped us improve the paper, and we have uploaded a revised manuscript. Below we briefly summarize the changes, in the hope that they are helpful.

Q4: statistical interpretation of the surprise score and its link to semantic clusters

We agree that this part deserved a clearer explanation and more validation.

Statistical meaning. Under H₀ (i.i.d. pixels), the two complementary views are independent, so they match at cluster k with probability qₖ = pₖ², and the match count tₖ follows a binomial distribution. By the Chernoff bound (Section 3.2), N · D(q̂ₖ ‖ qₖ) is a lower bound on −log P(tₖ or more matches | H₀). With N = 3000 and τ = 0.005, each cluster counted as surprising has a tail probability below e⁻¹⁵ ≈ 3 × 10⁻⁷ under H₀.

Validation (Section 4.4, Appendix I). We tested the ten trained models per dataset on modified inputs:

  • On i.i.d. pixel noise, i.e. data drawn from H₀, the score falls to the level of an independent pairing of the views, and no cluster is surprising.
  • When pixel positions within each test image are randomly permuted, which keeps the pixel histogram but removes spatial structure, about 97–99% of the score disappears and NMI drops below 9%.
  • The two views have nearly equal cluster marginals, as qₖ = pₖ² assumes. Using the per-view product pₖ⁽ⁱ⁾ · pₖ⁽ʲ⁾ instead changes the score by less than 0.5%.

These results suggest that the score stays close to zero when the data contain no spatial structure, as intended.

Link to semantic clusters. Because the two views are complementary halves of an image, augmented independently, they can only agree on features that survive the augmentation. We added two experiments that we hope shed some light on this (Section 4.4, Appendix H):

  • When only 6, 7, 8 or 9 MNIST classes are kept, the number of inferred clusters follows the true number (exactly 8 and 9 in every run for 8 and 9 classes), with mean ACC of 95–99%.
  • When the output dimension K varies over {32, 64, 96, 128}, the number of inferred clusters stays at 9.3–10.1 on MNIST, 10.7–11.2 on Fashion-MNIST and 10.2–10.3 on USPS.

The model does sometimes merge similar classes, for example digits 4 and 9 in three MNIST runs. Interestingly, these three runs have the lowest final surprise score, so such failures may be detectable without labels.

Q3: controlled comparisons

We agree that controlled comparisons are important. The revised manuscript includes the following:

  • Objective and optimizer (Appendix C, Table 2): with the same ResNet-9, the same masked and augmented views and K = 64, we trained softmax and Gumbel-softmax relaxations of the score by gradient descent. In this comparison, the ES scheme obtained higher scores in 8 of 9 columns, with smaller variance across seeds.
  • Training procedure (Table 2): removing augmentation, the inner-loop gradient-descent training, or the USPS-specific anisotropic augmentation each lowers accuracy.
  • View construction (new, Table 2): a random complementary mask also keeps the views independent under H₀, but in our runs it gave 11–14 points lower ACC than the chessboard mask.
  • Compute: every run, including the ablations, uses one H200 GPU for about 5 h (MNIST, Fashion-MNIST) or 2 h (USPS).

We sincerely apologize that we could not complete the retraining of IIC and DeepDPM with our augmentation within the discussion period, as we had hoped in our previous reply. We will include these results in the final version.

Q1, Q2: recent methods with an unknown number of classes

Thank you for this suggestion. To our knowledge, relatively few methods from 2024–2026 consider exactly our setting: hard cluster IDs, a number of classes that is not given, and no pretrained features. The most related methods we are aware of are:

MethodNumber of classesFeaturesOptimization
DeepDPM (2022)inferred by split/mergepretrained autoencodergradient descent + split/merge
UNSEEN (2024)inferred from an upper bound (dying clusters)pretrained autoencodergradient descent
CLUDI (2025)givenpretrained DINOgradient descent (diffusion teacher–student)
IIC (2019)givenfrom scratchgradient descent on mutual information
Oursinferred (K is only an upper bound)from scratchES + periodic gradient descent

DeepDPM and UNSEEN are included as baselines in Table 1. Methods built on large pretrained encoders, such as CLUDI on DINO, are very strong. Since their features come from pre-training on large external data, a direct comparison with our from-scratch setting might not be fully informative. We will add this comparison to the Related Work section. We may well have missed relevant work, and we would be grateful for any pointers.

Thank you again for your time and helpful feedback. We would be happy to provide any further clarification.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.