提出自适应采样下的配对学习泛化分析框架，解决数据依赖难题。
Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysis
- 融合算法稳定性与PAC-Bayes方法，处理任意自适应采样策略
- 在光滑与非光滑凸问题中，为两类梯度方法提供泛化界
- 适用于排序、度量学习等任务，适合关注泛化性能的研究者
我们研究了基于数据自适应采样方案的随机优化，用于训练配对学习模型。配对学习广泛应用，涵盖排序、度量学习和AUC最大化等任务。与点对点学习不同，配对学习存在输入对间的统计依赖性，现有分析难以处理一般情形。为此，我们拓展了结合算法稳定性与PAC-Bayes的双框架分析方法，可处理优化器中任意数据自适应采样方案。该框架被应用于分析（1）配对随机梯度下降（pairwise SGD），是许多机器学习问题的主流方法；（2）配对随机梯度上升（pairwise SGD ascent），用于对抗训练。这些算法均在每次更新前从离散分布中随机采样索引。已有文献建议使用非均匀采样，本文为其在光滑与非光滑凸问题中提供了泛化保证。
原文摘要 · Abstract (English)
We study stochastic optimization with data-adaptive sampling schemes to train pairwise learning models. Pairwise learning is ubiquitous, and it covers several popular learning tasks such as ranking, metric learning and AUC maximization. A notable difference of pairwise learning from pointwise learning is the statistical dependencies among input pairs, for which existing analyses have not been able to handle in the general setting considered in this paper. To this end, we extend recent results that blend together two algorithm-dependent frameworks of analysis -- algorithmic stability and PAC-Bayes -- which allow us to deal with any data-adaptive sampling scheme in the optimizer. We instantiate this framework to analyze (1) pairwise stochastic gradient descent, which is a default workhorse in many machine learning problems, and (2) pairwise stochastic gradient descent ascent, which is a method used in adversarial training. All of these algorithms make use of a stochastic sampling from a discrete distribution (sample indices) before each update. Non-uniform sampling of these indices has been already suggested in the recent literature, to which our work provides generalization guarantees in both smooth and non-smooth convex problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。