A computer-implemented method of training a convolutional neural network, wherein the convolutional neural network has a plurality of network parameters and is configured to receive input images and to process the input images to generate respective embeddings representing the input images in accordance with the network parameters, wherein, once the convolutional neural network is trained, the respective positions of generated embeddings in multi-dimensional embedding space reflect similarities between input images that are represented by the embeddings, the method comprising: obtaining a batch of training images and a ground truth assignment of each of the training images in the batch into a respective cluster of a plurality of clusters; processing the training images in the batch using the neural network and in accordance with current values of the network parameters to generate respective embeddings for each of the training images; determining an oracle clustering score based on the respective embeddings generated using the current values of the network parameters, wherein the oracle clustering score indicates a quality of the clustering defined by the respective embeddings given the ground truth assignment; and adjusting the current values of the network parameters by performing an iteration of a neural network training procedure to optimize an objective function that penalizes the neural network for generating embeddings that do not result in, for each possible clustering assignment other than the ground truth assignment, the oracle clustering score being higher than a clustering score for the possible clustering assignment by at least a structured margin between the possible clustering assignment and the ground truth assignment, wherein the clustering score for each possible clustering assignment indicates a closeness of each of the respective embeddings to a respective nearest representative point of a plurality of representative points in the multi-dimensional embedding space, each of the plurality of representative points corresponding to a respective cluster of the possible clustering assignment, and wherein the structured margin measures a quality of the possible clustering assignment relative to the ground truth assignment. obtaining a batch of training images and a ground truth assignment of each of the training images in the batch into a respective cluster of a plurality of clusters; processing the training images in the batch using the neural network and in accordance with current values of the network parameters to generate respective embeddings for each of the training images; determining an oracle clustering score based on the respective embeddings generated using the current values of the network parameters, wherein the oracle clustering score indicates a quality of the clustering defined by the respective embeddings given the ground truth assignment; and adjusting the current values of the network parameters by performing an iteration of a neural network training procedure to optimize an objective function that penalizes the neural network for generating embeddings that do not result in, for each possible clustering assignment other than the ground truth assignment, the oracle clustering score being higher than a clustering score for the possible clustering assignment by at least a structured margin between the possible clustering assignment and the ground truth assignment, wherein the clustering score for each possible clustering assignment indicates a closeness of each of the respective embeddings to a respective nearest representative point of a plurality of representative points in the multi-dimensional embedding space, each of the plurality of representative points corresponding to a respective cluster of the possible clustering assignment, and wherein the structured margin measures a quality of the possible clustering assignment relative to the ground truth assignment.