- Rating
- 4
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper considers the combinatorial sample complexity of learning Euclidean embeddings from anchor-positive-negative triplet comparisons. A triplet is labelled only when the relevant pairwise distances are separated by a specified multiplicative margin. Building on Alon et al. (2024), the authors resolve an open question by improving the margin-dependent VC-dimension upper bound from to , removing the logarithmic factor and the explicit dependence on embedding dimension. They also prove a matching lower bound in the regime where the margin is sufficiently large relative to the number of objects and embedding dimension: The central proof technique randomly projects a high-dimensional margin-satisfying embedding onto one dimension, where each comparison retains a better-than-random probability of being correct. Combining this rounding argument with a one-dimensional Rademacher complexity bound yields the improved upper bound. The lower bound uses an explicit geometric shattering construction. Synthetic and CIFAR-100 experiments provide supporting evidence for the predicted generalization behavior.
Critical strengths
-
The paper resolves a well-defined open theoretical problem and establishes matching upper and lower bounds in an explicit parameter regime. Removing the logarithmic factor gives a sharp, dimension-independent VC-dimension characterization for fixed positive margins.
-
The proof strategy is elegant and informative. Gaussian projection turns a high-dimensional margin constraint into a one-dimensional weak classification advantage, which can then be combined with Rademacher complexity to control shattering.
Critical weaknesses
The scope is limited, even though the result is strong. The theoretical formulation concerns only triplet prediction over a fixed collection of objects with unrestricted embeddings. It does not directly analyze parameterized neural encoders, InfoNCE optimization, or efficient algorithms for learning such embeddings. The matching lower bound only applies under specified relationships among , , and .
Questions for authors
Can the authors sharpen the VC-dimension characterization outside the matching regime, especially when or the margin becomes very small?
We thank the reviewer for their high score and positive evaluation of our paper. Regarding the reviewer’s question, we do not yet know how to extend the lower bound in the case when the margin is small. We believe this to be an interesting research question.