Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Optimal VC Dimension of Contrastive Learning with Margin
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo +1
Contrastive learning is a successful paradigm for learning -dimensional geometric representations from a collection of ``anchor--positive--negative'' triplets ,…
cs.DS2026
Strong Refutation of Ordering, Phylogenetic, and Ordinary CSPs, and New Satisfiability and Refutation Thresholds for Triplet and Quartet Reconstruction
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo +1
We study phase transitions and algorithms for refuting CSPs arising in hierarchical clustering (as well as ranking, and ordinary CSPs). Here, variables are assigned to leaves o…
cs.DS2026
Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo
Embedding-based representations in Euclidean space are a cornerstone of modern machine learning, where a major goal is to use the \emph{smallest dimension} that fait…