Optimal Sample Complexity of Contrastive Learning

We thank the reviewer for their comments. We updated the PDF, which now includes all of the suggested changes.

Q: Typos:

• page 4: Outline of techniques: P is a polynomial of degree $2$, not $2d$.
• Theorem 3.3 proof, first line: Should it be $d<n$ here?
• Please search for "Kulis Kulis" and "Warren Warren" in the paper and remove such duplicates.
• page 8, second line: Should $<$ be replaced by $\le$?

A: Thank you, fixed!

Q: Reducing dependence on n: It may be good to state bounds with the assumptions mentioned (k latent classes etc.)

A: In case there are $k$ latent classes, all the results would be as in Table 1, with $n$ being replaced with $k$.

Q: In Definition 2.1, the symbol $S_3$ seems to be used before definition.

A: Thank you for pointing it out. Definition 2.1 introduces the notion of sample complexity, and also introduces notation $S_3$ for the sample complexity. We clarified the wording: “the sample complexity of contrastive learning, denoted as $S_3(\epsilon, \delta)$”

We thank the reviewer for their comments. We updated the PDF, which now includes all of the suggested changes. We would to highlight that:

• as you correctly mentioned in the summary, our work provides distribution-independent assumptions, which separates our work from other related works that make various assumptions about the data, model, or training process;
• our bounds are achieved using PAC-learning techniques, which, contrary to the widespread belief, demonstrates that PAC-learning techniques are applicable to the contrastive learning setting.

We also would be very grateful if you could clarify why soundness was estimated as “2. Fair”. Please let us know if you have any specific questions about the proof of our results.

Q: A thorough comparison with the known sample complexity bounds.

A: We first would like to emphasize that our setting is substantially different from all the previous work we are aware of: namely, we estimate the sample complexity without any assumptions on data distribution, classifier, or training algorithm. Moreover, multiple works measure the classifier quality using some continuous loss function instead of prediction accuracy (and hence $\epsilon$ is formulated in terms of the loss function), which again makes the results incomparable. We below outline the works on sample complexity which are most related to ours:

• “Sample complexity of learning Mahalanobis distance metrics” by N. Verma and K. Branson shows that learning a $n \times n$ Mahalanobis matrix requires $O(\frac{n}{\epsilon^2})$ samples.
• “Tree Learning: Optimal Sample Complexity and Algorithms” by Avdiukhin et al. (AAAI 2023) is an example of the complexity bound for the specific metric case, showing that the VC dimension of tree learning is $\Theta(n)$. The goal of tree learning is to build a hierarchy on $n$ points such that constraints of the form “$c$ is separated from $a$ and $b$ first” are satisfied. This is a metric case where the distance between $a$ and $b$ can be defined as the number of leaves under the least common ancestor of $a$ and $b$.
• Saunshi et al. (2019) provide sample complexity bounds for transfer learning settings.
• A line of work considers the sample complexity of recovering metric embeddings using noisy queries in various settings. In particular, “Landmark Ordinal Embedding” by Ghosh et al. shows that $O(d^8 n \log n)$ noisy triplet queries suffice to achieve a constant additive divergence.

Q: While I understand the page limit of the main body, there seems to be relatively less than enough content on the main results of this work in the main body. Perhaps consider moving more technical parts from the appendix into the main body.

A: Thank you for the suggestion, we moved the proof of Theorem B.2 (constant $d$ case) to the main body. Given the page limit, while other technical results can’t be included in the main body, we give an outline of the proofs in the “Outline of the techniques”.

Q: The structure of the paper could be reorganized a bit: e.g., the paragraph "Reducing dependence on n" could be part of the discussions after presenting the full main results.

A: Thank you, we moved it to the “Extensions” section.

Q: What do you think is the primary reason/insight that the upper bounds for $\ell_p$-distances are different between odd and even p?

A: The main reason that the upper bounds for odd $p$ are different from the upper bounds for even $p$ is that, for even $p$, $\|x - y\|_p^p$ is a polynomial in $x_1,\ldots,x_d,y_1, \ldots, y_d$, while for odd $p$ it is not, and it is not even a $p$-times continuously differentiable. Intuitively, $\|x - y\|_p^p$ is a worse-behaving function for odd $p$ than for even $p$, so it is not surprising that the upper bound is similarly worse.

Q: Is it possible to characterize the sample complexity bound when the cardinality of $V$ is infinite?

A: We briefly outline the idea in the paragraph “Reducing dependence on $n$”. The following are natural scenarios.

• In practice, in order to reduce $n$ one can use any unsupervised method which allows one to perform deduplication without substantially affecting the metric structure. For example, an extremely common assumption in the literature is that the data comes from $k \ll n$ different classes. In this case, one can consider using an unsupervised clustering algorithm (e.g. a pretrained neural network) to partition the points into $k$ clusters, effectively replacing $n$ with $k$ in all bounds.
• Another practical scenario is that the distribution is supported on a large domain but contains a large number of low-probability outliers. In this case, one can replace $n$ with the support of 99% of the distribution at the cost of a small increase in error.

Q: "Outline of the techniques": why "P is some polynomial of degree 2d"?

A: Thank you, this is a typo - P is a polynomial of degree 2.

Q: $(x_1^−,x_2^−) \to (x_3^−,x_4^−)$

A: Thank you, fixed!

First, we would like to thank the reviewer for their helpful comments. We would like to add that one of the main points of our work lies in the fact that we provide sample complexity bounds without any assumptions on the data distribution or the learning algorithm. We also would like to emphasize that the focus of our work is sample complexity - namely, how many labeled examples are necessary to produce a good classifier, regardless of the model and the training algorithm. This question is important by itself since it allows one to determine whether the amount of data available is sufficient to train a good classifier.

Q: The proof arguments are somewhat non-constructive, due to using a counting argument/pigeonhole principle, and hence while the theory may explain certain observations (e.g., the experimental results in Appendix F), it is unlikely to give effective learning algorithms and the constants in the resulting bounds are unlikely to be sharpened. This may be nitpicking, but are weaknesses nonetheless.

A: The learning algorithm suggested by our work is Empirical Risk Minimization (ERM), i.e. minimizing the error on the sample data (which is optimal for statistical learning problems in general). While theoretically the ERM problem is computationally hard, any algorithm which performs well in practice can be used. Empirical success of deep learning architectures makes them a suitable choice for the problems we consider. The focus of our work is to quantify the amount of data required for fitting such architectures to the training data while providing generalization guarantees.

Q: While the experimental results (in Appendix F) verify the growth of error rates as predicted by the theory for ResNet18 on certain parameter ranges, there is not much explanations regarding, e.g., what representations (e.g., deep learning architectures) are expressive enough to achieve the sample bounds as predicted by the theory. That is, the representations (given by the theory) are somehow non-explicit/ineffective, is that the case?

A: One property of the neural network architecture that we can analyze is the dimension of the embedding layer, denoted as $d$. In particular: Using our results, given the number of available samples, one can estimate whether they are sufficient for achieving low generalization error. In particular, our work shows that for networks with a Euclidean embedding layer of dimension $d$, approximately $nd$ samples are necessary and sufficient where n is the number of different points in the domain. Furthermore, in the well-separated case we show that the number of samples required is independent of the dimension of the embedding layer.

We thank the reviewer for their comments. We updated the PDF, which now includes all of the suggested changes. In addition to the strengths of our work you identified, we would like to highlight the following important aspects of our work:

• our work shows that, contrary to the widespread belief, PAC-learning can provide useful bounds for sample complexity in deep learning, specifically in the contrastive learning setting;
• our work provides bounds that are independent of any assumptions on the input or the learning algorithm.

Q: Personally, I find it hard to follow the results by chapter. For example, Section 3 should be all about the bounds in $\ell_p$ norm, and so Theorem 3.1 (Arbitrary distance) should come before this section. And I think it would be easier to follow if Section 3 is only for $k=1$ and Section 4 is only for $k>1$.

A: Thank you, we moved Theorem 3.1 to the previous section. We moved the results from subsection 3.1 to a separate section.

Q: I would put "(1+$\alpha$)-separable $\ell_2$" in the same category as $\ell_p$.

A: Fixed

Q: The "Same" labels for quadruplet learning and k negatives have different meaning; while the former refer to all distance functions above, the latter only refers to the ℓp distances. Could the authors modify the table so that this distinction becomes clearer?

A: Thank you for pointing this out. We’ve clarified in Table 1 that our results for k negatives in fact cover all distances and not just ℓp (the results are in Appendix C.1).