提出首个高效对比学习的PAC学习算法，解决线性表示学习的可学习性难题。
Towards Efficient Contrastive PAC Learning
- 将对比学习转化为ℓ₂距离下的半定规划问题，实现高效求解。
- 在特定大间隔条件下，建立基于Rademacher复杂度的泛化界并导出PAC保证。
- 首次实现对比学习的高效PAC学习，适用于理论研究与可解释模型设计。
本文在PAC学习框架下研究对比学习。尽管近期多项工作基于VC维或Rademacher复杂度给出了对比损失下的统计结果，但其算法本质上效率低下或不满足PAC保证。本文聚焦于线性表示这一基础概念的对比学习，令人惊讶的是，在如此基本的设定下，高效PAC学习的存在性仍长期未解。我们首先证明一般情况下线性表示的对比学习在PAC框架下是难以处理的。随后，当对比样本间距离采用ℓ₂-范数时，该问题可被松弛为半定规划。在此基础上，我们基于Rademacher复杂度建立了泛化保证，并在特定对比大间隔条件下将其连接至PAC保证。据我们所知，这是首个针对对比学习的高效PAC学习算法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。