Towards Efficient Contrastive PAC Learning
This addresses a foundational gap in machine learning theory by providing the first efficient PAC algorithm for contrastive learning, which is crucial for researchers in theoretical ML and AI.
The paper tackles the problem of efficient PAC learning for contrastive learning of linear representations, showing it is intractable in general but can be solved via a semi-definite program under ℓ₂-norm distance, with generalization guarantees under large-margin conditions.
We study contrastive learning under the PAC learning framework. While a series of recent works have shown statistical results for learning under contrastive loss, based either on the VC-dimension or Rademacher complexity, their algorithms are inherently inefficient or not implying PAC guarantees. In this paper, we consider contrastive learning of the fundamental concept of linear representations. Surprisingly, even under such basic setting, the existence of efficient PAC learners is largely open. We first show that the problem of contrastive PAC learning of linear representations is intractable to solve in general. We then show that it can be relaxed to a semi-definite program when the distance between contrastive samples is measured by the $\ell_2$-norm. We then establish generalization guarantees based on Rademacher complexity, and connect it to PAC guarantees under certain contrastive large-margin conditions. To the best of our knowledge, this is the first efficient PAC learning algorithm for contrastive learning.