Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sample complexity of contrastive learning, i.e. the minimum number of labeled tuples sufficient for getting high generalization accuracy. We give tight bounds on the sample complexity in a variety of settings, focusing on arbitrary distance functions, $\ell_p$-distances, and tree metrics. Our main result is an (almost) optimal bound on the sample complexity of learning $\ell_p$-distances for integer $p$. For any $p \ge 1$, we show that $\tilde \Theta(nd)$ labeled tuples are necessary and sufficient for learning $d$-dimensional representations of $n$-point datasets. Our results hold for an arbitrary distribution of the input samples and are based on giving the corresponding bounds on the Vapnik-Chervonenkis/Natarajan dimension of the associated problems. We further show that the theoretical bounds on sample complexity obtained via VC/Natarajan dimension can have strong predictive power for experimental results, in contrast with the folklore belief about a substantial gap between the statistical learning theory and the practice of deep learning.

Abstract. It is known that any open necklace with beads of [Formula: see text] types, in which the number of beads of each type is divisible by [Formula: see text], can be partitioned by at most [Formula: see text] cuts into intervals that can be distributed into [Formula: see text] collections, each containing the same number of beads of each type. This is tight for all values of [Formula: see text] and [Formula: see text]. Here, we consider the case of random necklaces, where the number of beads of each type is [Formula: see text]. Then the minimum number of cuts required for a “fair” partition with the above property is a random variable [Formula: see text]. We prove that for fixed [Formula: see text] and large [Formula: see text], this random variable is at least [Formula: see text] with high probability. For [Formula: see text], fixed [Formula: see text], and large [Formula: see text], we determine the asymptotic behavior of the probability that [Formula: see text] for all values of [Formula: see text]. We show that this probability is polynomially small when [Formula: see text], is bounded away from zero when [Formula: see text], and decays like [Formula: see text] when [Formula: see text]. We also show that for large [Formula: see text], [Formula: see text] is at most [Formula: see text] with high probability and that for large [Formula: see text] and large ratio [Formula: see text], [Formula: see text] is [Formula: see text] with high probability.