Uniform convergence, stability and learnability for ranking problems
Wei Gao, Zhi‐Hua Zhou · 2013
Most studies were devoted to the design of effi-cient algorithms and the evaluation and application on diverse ranking problems, whereas few work has been paid to the theoretical studies on rank-ing learnability. In this paper, we study the re-lation between uniform convergence, stability and learnability of ranking. In contrast to supervised learning where the learnability is equivalent to uni-form convergence, we show that the ranking uni-form convergence is sufficient but not necessary for ranking learnability with AERM, and we further present a sufficient condition for ranking uniform convergence with respect to bipartite ranking loss. Considering the ranking uniform convergence be-ing unnecessary for ranking learnability, we prove that the ranking average stability is a necessary and sufficient condition for ranking learnability. 1