Doing well with less! On Sampling Techniques for Empirical Pairwise Loss Estimation/Minimization

• URL: http://arxiv.org/abs/2606.02345v1
• Date: Mon, 01 Jun 2026 14:54:29 GMT
• Title: Doing well with less! On Sampling Techniques for Empirical Pairwise Loss Estimation/Minimization
• Abstract summary: We show 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.<n>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.
• Score: 1.9233913116824528
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization [12.006706388840934]
  This paper provides a theoretical analysis of a new learning problem for recommender systems where users provide feedback by comparing pairs of items instead of rating them individually.
  arXiv  Detail & Related papers  (2025-02-27T12:17:34Z)
• Efficient Fairness-Performance Pareto Front Computation [45.088727439928704]
  We show that optimal fair representations possess several useful structural properties.<n>We then show that these approxing problems can be solved efficiently via concave programming methods.
  arXiv  Detail & Related papers  (2024-09-26T08:46:48Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the $n$ data distributions. We show that, when the data distributions satisfy a weaker realizability assumption, sample-efficient learning is still feasible.
  arXiv  Detail & Related papers  (2024-02-16T04:32:22Z)
• Pairwise Learning via Stagewise Training in Proximal Setting [0.0]
  We combine adaptive sample size and importance sampling techniques for pairwise learning, with convergence guarantees for nonsmooth convex pairwise loss functions. We demonstrate that sampling opposite instances at each reduces the variance of the gradient, hence accelerating convergence.
  arXiv  Detail & Related papers  (2022-08-08T11:51:01Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss [72.62029620566925]
  Recent works in self-supervised learning have advanced the state-of-the-art by relying on the contrastive learning paradigm. Our work analyzes contrastive learning without assuming conditional independence of positive pairs. We propose a loss that performs spectral decomposition on the population augmentation graph and can be succinctly written as a contrastive learning objective.
  arXiv  Detail & Related papers  (2021-06-08T07:41:02Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  Learning from implicit feedback is challenging because of the difficult nature of the one-class problem. Most conventional methods use a pairwise ranking approach and negative samplers to cope with the one-class problem. We propose a learning-to-rank approach, which achieves convergence speed comparable to the pointwise counterpart.
  arXiv  Detail & Related papers  (2021-05-11T03:38:16Z)
• Evaluating representations by the complexity of learning low-loss predictors [55.94170724668857]
  We consider the problem of evaluating representations of data for use in solving a downstream task. We propose to measure the quality of a representation by the complexity of learning a predictor on top of the representation that achieves low loss on a task of interest.
  arXiv  Detail & Related papers  (2020-09-15T22:06:58Z)
• Machine learning for causal inference: on the use of cross-fit estimators [77.34726150561087]
  Doubly-robust cross-fit estimators have been proposed to yield better statistical properties. We conducted a simulation study to assess the performance of several estimators for the average causal effect (ACE) When used with machine learning, the doubly-robust cross-fit estimators substantially outperformed all of the other estimators in terms of bias, variance, and confidence interval coverage.
  arXiv  Detail & Related papers  (2020-04-21T23:09:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.