Linear Label Ranking with Bounded Noise

Label Ranking (LR) is the supervised task of learning a sorting function that maps feature vectors 𝑥 ∈ R 𝑑 to rankings 𝜎 ( 𝑥 ) ∈ S 𝑘 over a finite set of 𝑘 labels. We focus on the fundamental case of learning linear sorting functions (LSFs) under Gaussian marginals: 𝑥 is sampled from the 𝑑 -dimensional standard normal and the ground truth ranking 𝜎 ⋆ ( 𝑥 ) is the ordering induced by sorting the coordinates of the vector 𝑊 ⋆ 𝑥 , where 𝑊 ⋆ ∈ R 𝑘 × 𝑑 is unknown. We consider learning LSFs in the presence of bounded noise: assuming that a noiseless example is of the form ( 𝑥 , 𝜎 ⋆ ( 𝑥 )) , we observe ( 𝑥 , 𝜋 ) , where for any pair of elements 𝑖 ̸ = 𝑗 , the probability that the order of 𝑖, 𝑗 is different in 𝜋 than in 𝜎 ⋆ ( 𝑥 ) is at most 𝜂 < 1 / 2 . We design efficient non-proper and proper learning algorithms that learn hypotheses within normalized Kendall’s Tau distance 𝜖 from the ground truth with 𝑁 = ̃︀ 𝑂 ( 𝑑 log( 𝑘 ) /𝜖 ) labeled examples and runtime poly ( 𝑁, 𝑘 ) . For the more challenging top-𝑟 disagreement loss, we give an efficient proper learning algorithm that achieves 𝜖 top-𝑟 disagreement with the ground truth with 𝑁 = ̃︀ 𝑂 ( 𝑑𝑘𝑟/𝜖 ) samples and poly ( 𝑁 ) runtime.