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!