Contrastive learning is a comparative-based learning paradigm in which labelers are given triplet queries (A,B,C) of data points, and answer whether in their opinion point A is "closer" to B than C, or vice versa. E.g. if a labeler is given three pictures (A = Lion, B = Tiger, C = Dog), they would say that a lion is closer to a tiger than to a dog. In this talk, we discuss the dimensionality of satisfying m contrastive learning constraints in an l_p metric. In particular, we answer the following question:
What is a sufficiently large dimension d, such that given any m (non-contradictory) constraints of the form "dist(A,B) < dist(A,C)", can we find an embedding into R^d such that all constraints are satisfied? (under the l_p distance). We show that e.g. for p=2 that d = Theta(sqrt(m)) is both necessary and sufficient.
Relatedly, we use our techniques to answer the following natural question for the k-nearest neighbor problem:
What is a sufficiently large dimension d, such that given any metric D on n points, can we find an embedding into R^d that preserves the k-nearest neighbors of each point of D? (under the l_p distance). We show that d = O~(poly(k)) is always sufficient.
Our methods are a combination of combinatorial and algebraic techniques. At the heart of our algorithms is an analysis of a graph which we refer to as the constraint graph, whose properties are associated with the dimension bounds we obtain - and in particular, its arboricity (an important measure of density).