Timezone: »
Stochastic optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. Although various algorithms have been extensively studied for AUPRC optimization, the generalization is only guaranteed in the multi-query case. In this work, we present the first trial in the single-query generalization of stochastic AUPRC optimization. For sharper generalization bounds, we focus on algorithm-dependent generalization. There are both algorithmic and theoretical obstacles to our destination. From an algorithmic perspective, we notice that the majority of existing stochastic estimators are biased when the sampling strategy is biased, and is leave-one-out unstable due to the non-decomposability. To address these issues, we propose a sampling-rate-invariant unbiased stochastic estimator with superior stability. On top of this, the AUPRC optimization is formulated as a composition optimization problem, and a stochastic algorithm is proposed to solve this problem. From a theoretical perspective, standard techniques of the algorithm-dependent generalization analysis cannot be directly applied to such a listwise compositional optimization problem. To fill this gap, we extend the model stability from instancewise losses to listwise losses and bridge the corresponding generalization and stability. Additionally, we construct state transition matrices to describe the recurrence of the stability, and simplify calculations by matrix spectrum. Practically, experimental results on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
Author Information
Peisong Wen (Chinese Academy of Sciences)
Qianqian Xu (Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences)
Zhiyong Yang (Chinese Academy of Sciences)
Yuan He (Alibaba Group)
Qingming Huang (University of Chinese Academy of Sciences)
More from the Same Authors
-
2022 Poster: Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm »
HuiYang Shao · Qianqian Xu · Zhiyong Yang · Shilong Bao · Qingming Huang -
2022 Spotlight: OpenAUC: Towards AUC-Oriented Open-Set Recognition »
Zitai Wang · Qianqian Xu · Zhiyong Yang · Yuan He · Xiaochun Cao · Qingming Huang -
2022 Poster: OpenAUC: Towards AUC-Oriented Open-Set Recognition »
Zitai Wang · Qianqian Xu · Zhiyong Yang · Yuan He · Xiaochun Cao · Qingming Huang -
2022 Poster: OTKGE: Multi-modal Knowledge Graph Embeddings via Optimal Transport »
Zongsheng Cao · Qianqian Xu · Zhiyong Yang · Yuan He · Xiaochun Cao · Qingming Huang -
2022 Poster: The Minority Matters: A Diversity-Promoting Collaborative Metric Learning Algorithm »
Shilong Bao · Qianqian Xu · Zhiyong Yang · Yuan He · Xiaochun Cao · Qingming Huang -
2021 Poster: When False Positive is Intolerant: End-to-End Optimization with Low FPR for Multipartite Ranking »
Peisong Wen · Qianqian Xu · Zhiyong Yang · Yuan He · Qingming Huang -
2020 Poster: Heuristic Domain Adaptation »
Shuhao Cui · Xuan Jin · Shuhui Wang · Yuan He · Qingming Huang -
2019 Poster: Generalized Block-Diagonal Structure Pursuit: Learning Soft Latent Task Assignment against Negative Transfer »
Zhiyong Yang · Qianqian Xu · Yangbangyan Jiang · Xiaochun Cao · Qingming Huang -
2019 Poster: DM2C: Deep Mixed-Modal Clustering »
Yangbangyan Jiang · Qianqian Xu · Zhiyong Yang · Xiaochun Cao · Qingming Huang -
2019 Spotlight: DM2C: Deep Mixed-Modal Clustering »
Yangbangyan Jiang · Qianqian Xu · Zhiyong Yang · Xiaochun Cao · Qingming Huang -
2019 Poster: iSplit LBI: Individualized Partial Ranking with Ties via Split LBI »
Qianqian Xu · Xinwei Sun · Zhiyong Yang · Xiaochun Cao · Qingming Huang · Yuan Yao