Algorithm-Dependent Generalization of AUPRC Optimization: Theory and Algorithm

doi:10.1109/TPAMI.2024.3361861

	Algorithm-Dependent Generalization of AUPRC Optimization: Theory and Algorithm
	Wen, Peisong 1; Xu, Qianqian 1; Yang, Zhiyong 2; He, Yuan 3; Huang, Qingming 1,2,4
	2024-07-01
发表期刊	IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
ISSN	0162-8828
卷号	46 期号:7 页码:5062-5079
摘要	Stochastic optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. Despite extensive studies on AUPRC optimization, generalization is still an open problem. In this work, we present the first trial in the algorithm-dependent generalization of stochastic AUPRC optimization. The obstacles to our destination are three-fold. First, according to the consistency analysis, the majority of existing stochastic estimators are biased with biased sampling strategies. To address this issue, we propose a stochastic estimator with sampling-rate-invariant consistency and reduce the consistency error by estimating the full-batch scores with score memory. Second, standard techniques for algorithm-dependent generalization analysis cannot be directly applied to listwise losses. To fill this gap, we extend the model stability from instance-wise losses to listwise losses. Third, AUPRC optimization involves a compositional optimization problem, which brings complicated computations. In this work, we propose to reduce the computational complexity by matrix spectral decomposition. Based on these techniques, we derive the first algorithm-dependent generalization bound for AUPRC optimization. Motivated by theoretical results, we propose a generalization-induced learning framework, which improves the AUPRC generalization by equivalently increasing the batch size and the number of valid training examples. Practically, experiments on image retrieval and long-tailed classification speak to the effectiveness and soundness of our framework.
关键词	Optimization Stability analysis Stochastic processes Measurement Standards Approximation algorithms Machine learning algorithms Machine learning AUPRC learning to rank algorithm-dependent generalization stability
DOI	10.1109/TPAMI.2024.3361861
收录类别	SCI
语种	英语
资助项目	National Key R#x0026;D Program of China
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Artificial Intelligence ; Engineering, Electrical & Electronic
WOS记录号	WOS:001240147800017
出版者	IEEE COMPUTER SOC
引用统计	被引频次：5[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/39889
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xu, Qianqian; Huang, Qingming
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Key Lab Intelligent Informat Proc, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 101408, Peoples R China 3.Alibaba Grp, Hangzhou, Peoples R China 4.Univ Chinese Acad Sci, Key Lab Big Data Min & Knowledge Management BDKM, Beijing 101408, Peoples R China
推荐引用方式 GB/T 7714	Wen, Peisong,Xu, Qianqian,Yang, Zhiyong,et al. Algorithm-Dependent Generalization of AUPRC Optimization: Theory and Algorithm[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,2024,46(7):5062-5079.
APA	Wen, Peisong,Xu, Qianqian,Yang, Zhiyong,He, Yuan,&Huang, Qingming.(2024).Algorithm-Dependent Generalization of AUPRC Optimization: Theory and Algorithm.IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,46(7),5062-5079.
MLA	Wen, Peisong,et al."Algorithm-Dependent Generalization of AUPRC Optimization: Theory and Algorithm".IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 46.7(2024):5062-5079.