유사성 학습 (similarity learning), 순위 지정 (ranking), 클러스터링 (clustering)을 포함한 많은 머신러닝 (machine learning) 문제들은 경험적 쌍별 손실 함수 (empirical pairwise loss functions)에 의존하며, 이 함수들의 이차적 계산 비용 (quadratic computational cost)은 규모가 커짐에 따라 빠르게 감당하기 어려운 수준이 됩니다. 우리는 조사 샘플링 기법 (survey sampling techniques)을 활용하여, 쌍 (pairs)에 대해 가용한 정보의 일부만을 유지하는 검소한 접근 방식이 모든 쌍을 사용하는 것과 대등한 추정 또는 최적화 성능을 달성할 수 있음을 보여줍니다. 이론과 실험 모두에 의해 뒷받침되는 핵심적인 발견은, 이러한 샘플링 계획 (sampling plans)이 개별 관측치 (individual observations)가 아닌 쌍 (pairs)을 직접적으로 타겟팅해야 한다는 것입니다. 특히, 비전 (vision) 또는 그래프 학습 (graph learning)에서의 임베딩 (embeddings)과 같은 고차원 벡터 (high-dimensional vectors) 간의 쌍별 손실 (pairwise losses)의 경우, 적절한 보조 정보 (auxiliary information)를 사용하여 정보가 풍부한 쌍 (informative pairs)에 더 높은 포함 확률 (inclusion probabilities)을 할당함으로써 전체 쌍 평가 (full pairwise evaluation)에 근접한 성능을 얻을 수 있으며, 이는 정확도와 계산 비용 사이의 원칙적이고 이론적 근거가 있는 절충안 (trade-off)을 제공합니다.