  We investigate a general formulation for clustering and transductive few-shot
learning, which integrates prototype-based objectives, Laplacian regularization
and supervision constraints from a few labeled data points. We propose a
concave-convex relaxation of the problem, and derive a computationally
efficient block-coordinate bound optimizer, with convergence guarantee. At each
iteration,our optimizer computes independent (parallel) updates for each
point-to-cluster assignment. Therefore, it could be trivially distributed for
large-scale clustering and few-shot tasks. Furthermore, we provides a thorough
convergence analysis based on point-to-set maps. Were port comprehensive
clustering and few-shot learning experiments over various data sets, showing
that our method yields competitive performances, in term of accuracy and
optimization quality, while scaling up to large problems. Using standard
training on the base classes, without resorting to complex meta-learning and
episodic-training strategies, our approach outperforms state-of-the-art
few-shot methods by significant margins, across various models, settings and
data sets. Surprisingly, we found that even standard clustering procedures
(e.g., K-means), which correspond to particular, non-regularized cases of our
general model, already achieve competitive performances in comparison to the
state-of-the-art in few-shot learning. These surprising results point to the
limitations of the current few-shot benchmarks, and question the viability of a
large body of convoluted few-shot learning techniques in the recent literature.
