Technical Summary: Doing Well with Less! On Sampling Techniques for Empirical Pairwise Loss Estimation/Minimization

Problem Statement

Many fundamental machine learning tasks, including similarity learning, ranking, clustering, and contrastive representation learning, rely on minimizing empirical pairwise loss functions. These objectives are formulated as U-statistics of order 2, requiring the evaluation of $O(N^2)$ pairs of observations. When dealing with high-dimensional data (e.g., image or text embeddings), computing the loss over all possible pairs becomes the dominant computational bottleneck, rendering full-pair evaluation prohibitive at scale.

A common heuristic to mitigate this cost is to subsample individual observations and form pairs from the resulting subset. However, this paper argues that such a strategy is suboptimal. The core challenge is to design a sampling scheme that selects a small, informative fraction of pairs to estimate or minimize the empirical risk while maintaining statistical efficiency and correcting for selection bias.

Methodology

The authors propose applying survey sampling theory directly to the population of pairs rather than to individual observations. The methodology is grounded in the Horvitz-Thompson (HT) estimator, which provides an unbiased estimate of the population total (or mean) by weighting observed values by the inverse of their inclusion probabilities.

Core Framework

1. Population Definition: Instead of sampling from the set of observations $I = \{1, \dots, N\}$, the method defines a population of pairs $J = \{(i, j) : 1 \le i < j \le N\}$.
2. Auxiliary Information: The sampling design leverages auxiliary information $\rho(W_i, W_j)$, a proxy correlated with the pairwise loss $\ell(Z_i, Z_j)$. This information can be derived from observation-level features (e.g., metadata, low-dimensional projections) or pair-level features (e.g., graph edge weights).
3. Inclusion Probabilities: Pairs are selected with probabilities proportional to the auxiliary proxy: $\bar{\pi}_{i,j} \propto \rho(W_i, W_j)$. This ensures that "informative" pairs (those likely to contribute significantly to the loss) are sampled more frequently.
4. Estimators:
   • Direct Pair Sampling: Pairs are sampled directly from $J$ using a design $\bar{D}_{\bar{N}}$ (e.g., Poisson or Rejective sampling). The estimator is $\bar{U}_{\bar{D}_{\bar{N}}} = \frac{2}{N(N-1)} \sum_{(i,j) \in \bar{S}} \frac{\ell(Z_i, Z_j)}{\bar{\pi}_{i,j}}$.
   • Observation Sampling (Baseline): Observations are sampled from $I$, and pairs are formed from the subset. The estimator is $\tilde{U}_{D_N} = \frac{2}{N(N-1)} \sum_{i<j \in S} \frac{\ell(Z_i, Z_j)}{\pi_{i,j}}$.

Theoretical Analysis

The paper establishes non-asymptotic bounds for the excess risk of predictors trained on survey-sampled pairs.

• Variance Minimization: The authors prove that for a fixed budget of evaluated pairs, direct pair sampling strictly dominates observation sampling in terms of estimator variance. This holds because observation-level inclusion probabilities are constrained to factorize ($\pi_{i,j} = \pi_i \pi_j$), preventing them from adapting to the full geometry of the pairwise loss.
• Generalization Bounds: Using Bernstein's inequality for independent (Poisson) and negatively associated (Rejective) variables, the paper derives uniform deviation bounds. It shows that the excess risk converges at the standard $O(1/\sqrt{N})$ rate provided the number of sampled pairs $\bar{n}$ scales linearly with $N$ (i.e., $\bar{n} = cN$). This implies that the ratio of evaluated pairs to total available pairs vanishes as $N \to \infty$, yet the learning rate remains optimal.

Key Contributions

1. Theoretical Superiority of Direct Pair Sampling: The paper establishes that direct pair sampling is theoretically optimal for pairwise loss estimation. Proposition 1 demonstrates that no observation-based sampling plan can achieve the same variance as the optimal direct pair sampling plan, even with perfect auxiliary information.
2. Optimal Inclusion Probabilities: Theorem 1 identifies the optimal link function for inclusion probabilities in a pairwise Poisson scheme. The optimal probability is proportional to $\rho^*(W_i, W_j) = \sqrt{E[\ell^2(Z, Z') | W_i, W_j]}$. The paper further shows that using a proxy $\rho$ correlated with the loss yields variance reductions proportional to the quality of the correlation.
3. Non-Asymptotic Generalization Guarantees: Section 4 provides the first non-asymptotic excess risk bounds for pairwise learning based on survey-sampled pairs. It confirms that the $O(1/\sqrt{N})$ convergence rate of full-pair learning is preserved even when only a linear fraction of pairs is evaluated.
4. Empirical Validation: The approach is validated on synthetic data and three real-world datasets (MovieLens, Cora, LFW). Results show that informed pair sampling reduces variance by factors ranging from $2\times$ to over $100\times$ compared to uniform pair sampling and observation sampling, depending on the heterogeneity of the loss and the quality of the auxiliary proxy.

Results

• Variance Reduction: In a sparse signal task, informed pair sampling achieved a $121\times$ variance reduction over uniform pair sampling. On real datasets, the reduction ranged from $1.2\times$ to $76.8\times$ compared to observation-based sampling, with the gain scaling with the squared coefficient of variation of the loss ($CV^2(\ell)$).
• Learning Performance: Experiments on node classification (Cora) and face recognition (LFW) demonstrated that models trained on survey-sampled pairs converge to the performance of full-pair training (the oracle).
  • Bias Correction: Unlike "hard negative mining" or other heuristic selection methods that introduce selection bias, the HT-weighted survey sampling approach remains unbiased. The paper shows that hard sampling plateaus due to uncorrected bias, whereas Poisson and Rejective sampling continue to converge toward the full-pair loss.
  • Robustness: Even with weak auxiliary information (e.g., LFW with correlation $\approx 0.16$), informed sampling never underperformed uniform sampling, though the gains were modest. When a strong proxy (e.g., precomputed contrastive loss) was used, performance matched the oracle closely.

Significance and Claims

The paper claims to provide a principled and theoretically grounded trade-off between computational cost and estimation accuracy for pairwise learning problems.

• Paradigm Shift: It challenges the standard practice of subsampling observations for pairwise tasks, arguing that the natural domain for sampling in these problems is the set of pairs itself.
• Frugality: The methodology enables "doing well with less" by allowing practitioners to evaluate a vanishing fraction of pairs ($O(N)$ instead of $O(N^2)$) while retaining the statistical guarantees of full-pair learning.
• General Applicability: The framework is applicable to any task formulated as a U-statistic of order 2, including ranking, metric learning, and contrastive learning, provided suitable auxiliary information is available to guide the sampling.

The authors conclude that while sharper learning-rate bounds accounting for variance reduction remain an open direction, this work paves the way for more frugal pairwise learning methods through appropriate data selection schemes grounded in survey sampling theory.