用抽样方法大幅减少计算量，仍保持配对损失的高精度
Doing well with less! On Sampling Techniques for Empirical Pairwise Loss Estimation/Minimization
- 直接对配对进行抽样，而非个体样本
- 仅用部分配对即可逼近全量计算效果
- 适合大规模相似性学习与排序任务
许多机器学习问题，如相似性学习、排序和聚类，依赖于经验配对损失函数，其二次计算成本在大规模场景下迅速成为瓶颈。本文证明，通过采用保留部分配对信息的节俭策略，并结合调查抽样技术，可在不牺牲估计或优化性能的前提下，显著降低计算开销。理论与实验共同表明，此类抽样方案必须直接针对配对而非个体观测进行设计。尤其在高维向量（如视觉或图学习中的嵌入）的配对损失场景中，利用辅助信息为有信息量的配对分配更高包含概率，可实现接近全量配对评估的性能，提供了一种在准确率与计算成本之间具有理论保障的权衡机制。
原文摘要 · Abstract (English)
Many machine learning problems, including similarity learning, ranking, and clustering, rely on empirical pairwise loss functions whose quadratic computational cost quickly becomes prohibitive at scale. We demonstrate how a frugal approach that retains only a fraction of the available information on pairs can achieve estimation or optimization performance comparable to that obtained by using all pairs, by leveraging survey sampling techniques. A central finding, supported by both theory and experiments, is that such sampling plans must target pairs directly rather than individual observations. In particular, for pairwise losses between high-dimensional vectors such as embeddings in vision or graph learning, assigning higher inclusion probabilities to informative pairs using suitable auxiliary information yields performance close to full pairwise evaluation, providing a principled and theoretically grounded trade-off between accuracy and computational cost.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。