Linear Label Ranking with Bounded Noise
Authors: Dimitris Fotakis
Alkis Kalavasis
Vasilis Kontonis
Christos Tzamos
Venue: NeurIPS 2022 Accept (2022)
Keywords: Label Ranking
Noise
Gaussian
Linear Sorting Function

Abstract: Label Ranking (LR) is the supervised task of learning a sorting function that maps feature vectors $x \in \mathbb{R}^d$ to rankings $\sigma(x) \in \mathbb S_k$ over a finite set of $k$ labels. We focus on the fundamental case of learning linear sorting functions (LSFs) under Gaussian marginals: $x$ is sampled from the $d$-dimensional standard normal and  the ground truth ranking $\sigma^\star(x)$ is the ordering induced by  sorting the coordinates of the vector $W^\star x$, where  $W^\star \in \mathbb{R}^{k \times d}$ is unknown. We consider learning LSFs in the presence of bounded noise: assuming that a noiseless example is of the form $(x, \sigma^\star(x))$, we observe $(x, \pi)$, where for any pair of elements $i \neq j$, the probability that the order of $i, j$ is different in $\pi$ than in  $\sigma^\star(x)$ is at most $\eta < 1/2$. We design efficient non-proper and proper learning algorithms that  learn hypotheses within normalized Kendall's Tau distance $\epsilon$ from the ground truth  with $N= \widetilde{O}(d\log(k)/\epsilon)$ labeled examples and runtime $\mathrm{poly}(N, k)$. For the more challenging top-$r$ disagreement loss, we give an efficient proper learning algorithm that achieves $\epsilon$ top-$r$ disagreement with the ground truth with $N = \widetilde{O}(d k r /\epsilon)$ samples and $\mathrm{poly}(N)$ runtime.

Linear Label Ranking with Bounded Noise
Dimitris Fotakis NTUA fotakis@cs.c Stt.kiiscssntuua..... ntua.gr
Alkis Kalavasis NTUA kalavasisalkissmaai ntt..tuaaa.....mm..m gr
Vasilis Kontonis UW Madison
kontonis@wisc. edu
Christos Tzamos
UW Madison
tzamos@wisc.cm edu
Abstract
Label Ranking (LR) is the supervised task of learning a sorting function that maps feature vectors E I to rankings (xx) S₃ over finite of &: labels. We focus on the fundamental case of learning linear sorting functions (LSFs) under Gaussian marginals: æ is sampled from the d-dimensional standard normal and the ground truth ranking a* (a:) is the ordering induced by sorting the coordinates of the vector W*,, where W* E Rexd is unknown. We consider learning LSFs in the presence of bounded noise: assuming that noiseless example is of the form (æ, o" (x=), we observe (æc, T). where for any pair of elements * j. the probability that the order of i.j different in than in o²(x) at most 1) 1/2. We design efficient non-proper and proper learning algorithms that learn hypotheses within normalized Kendall's Tau distance e from the ground truth with N (d log(k)/e) labeled examples and runtime poly(N, k). For the more challenging top-r disagreement loss, we give an efficient proper learning algorithm that achieves top-r disagreement with the ground truth with N O(drr/c) samples and poly(N) runtime.
Introduction
1.1 Background and Motivation
Label Ranking (LR) is the problem of learning hypothesis that maps features to rankings over finite set of labels. Given feature vector æ E IRd, sorting function a(.) maps it to a ranking alternatives, i.e., (xx) (z)) is an element of the symmetric group with & elements, Sy- Assuming access to a training dataset of features labeled with their corresponding rankings, i.c., pairs of the form (x, T E _R x Sg. the goal of the learner to find sorting function h(x) that generalizes well over a fresh sample. LR has received significant attention over the years [DSM03, SS07, HFCBOS, CH08, FHMB08] due the large number of applications. For example, ad targeting [DGR 14] is LR instance where for each user we want to use their feature vector to predict a ranking over ad categories and present them with the most relevant. The practical significance of LR has lead to the development of many techniques based on probabilistic models and instance-based methods [CH08, CDH10J, [GDV12, ZLGQ14), decision trees [CHH09], entropy-based ranking trees [RáSRSKIS bagging [AGM17], and random forests [dSSKC17, ZQ18). However, almost all of these works come without provable guarantees and/or fail learn in the presence of noise in the observed rankings.
Linear Sorting Functions (LSFs). In this work, we focus on the fundamental concept class of Linear Sorting functions [HPRZ03). linear sorting function parameterized matrix W E R
with rows W W..... W, takes a feature æ E d maps to W x = (W1 xx K...., We x) E R and
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of the k alternatives such that W. 1 26, W,, In other words, linear sorting function ranks the k alternatives (corresponding to rows of W) with respect to how well they correlate with the feature æ. We denote a linear sorting function with parameter W E R by ow (x: argsort W) where argsort R - S takes as input vector (U),...,, v%) E IR*, sorts it in decreasing order to obtain vi, 2 Via 2 2 Ui and returns the ordering (f1,...: kk)
then outputs an ordering (di.....
ig) ................
Noisy Ranking Distributions. Learning LSFs in the noiseless setting can be done efficiently by using linear programming. However, the common assumption both in theoretical and applied works is that the observed rankings are noisy in the sense that they do not always correspond to the ground-truth ranking. We assume that the probability that the order of two elements i, in the observed ranking is different than their order in the ground-truth ranking a² is at most vj < 1/2.
Definition 1 (Noisy Ranking Distribution). Fix E [0. 102). An monoss ranking distribution M(a*) with ground-trute truth ranking a² E Sy is a probability measure over Sy that, for any i. [k]. with + j, satisfies Pr Pram-ioo)) / L J >-- j] S n
Note that, when = O, we always observe the ground-truth permutation and, in the case of 7j = 1/2, may observe uniformly random permutation. We remark that most natural ranking distributions satisfy this bounded noise property, e.g., (i) the Mallows model, which is probably the most fundamental ranking distribution (see, e.g., [BM09, LB11, CPS13, ABSV14, BFFSZ19, FKS21, DOS18, LM18, MW20, LM21] for a small sample of this line of research) and (ii) the Bradley-Terry-Mane Malllls model [Ma157], which corresponds to the ranking distribution analogue of the -rerley-TTerry-lee Luce Luce model [BT52, Luc12] (the most studied pairwise comparisons model; see, e.g.. [Hun04, NOS17, APA18] and the references therein). For more details, see Appendix E.
We consider the fundamental setting where the feature vector æ E Id is generated by standard normal distribution and the ground-truth ranking for each sample æ is given by the LSF ow (x) for some unknown parameter matrix W R4xdd For a fixed æ. the ranking that we observe comes from an n-noisy ranking distribution with ground-truth ranking dw- (x:).
Definition 2 (Noisy Linear Label Ranking Distribution). Fix 17 [0, 1/2) and some ground-truth parameter matrix W E R We assume that the n-noisy linear label ranking distribution 'D over Id x S2 satisfies the following:
1. The x-marginal of is the d-dimensional standard normal distribution.
2. For any (x, T) DD the distribution of क conditional on an 17-noisy ranking distribution with ground-truth ranking ow- (x)).
At first sight, the assumption that the underlying æ-marginal is the standard normal may look too strong. However, for k = 2. Definition 2 captures the problem of learning linear threshold functions with Massart noise. Without assumptions for the m--margiaa,, it is known [DGT19, CKMY20, DK20, NT22] that optimal learning of halfspaces under Massart noise requires super-polynomial time (in the Statistical Query model of [Kea98]). On the other hand, a lot of recent works [BZ17, MV19, DKTZ20, ZSA20, ZL21] have obtained efficient algorithms for learning Massart halfspaces under Gaussian marginals. The goal of this work is to provide efficient algorithms for the more general problem of learning LSFs with bounded noise under Gaussian marginals.
1.2 Our Results
The main contributions of this paper are the first efficient algorithms for learning LSFs with bounded noise with respect to Kendall's Tau distance and top-r disagreement loss.
Learning in Kendall's Tau Distance. The most standard metric in rankings [SSBD14] is Kendall's Tau (KT) distance which, for two rankings n, T E Sg. measures the fraction of pairs (i. on which they disagree. That is, ( Eie.y 1(i > ()) Our first result is an efficient learning algorithm that, given samples from an noisy linear label ranking distribution D, computes
We use i > j (resp. i Ra j) to denote that the element i is ranked higher (resp. lower) than j according to the ranking
2

---

parameter matrix W that ranks the alternatives almost optimally with respect to the KT distance from the ground truth ranking Ow- (+).
Theorem 1 (Learning LSFs in KT Distance). Fix q E [0,1/2) and e, E (0.1). Let D be an n-noisy linear label ranking distribution satisfying the assumptions of Definition 2 with ground -rrtt LSF
ow. (.). There exists an algorithm that draws N = Ö <1-2n) log(k/b) (8)) samples from DD runs time, and computes a matrix W E R such that, with probability at least
in
1 6,
(Ar((o (a), ow (a)) cc. X
E
Theorem gives the first efficient algorithm with provable guarantees for the supervised problem of learning noisy linear rankings. We remark that the sample complexity of our learning algorithm is qualitatively optimal (up to logarithmic factors) since, for k = 2, our problem subsumes learning linear classifier with Massart noise for which ((d/c) are known to be information theoretically necessary [MN06]. Moreover, our learning algorithm is proper in the sense that it computes a linear sorting function (-(). As opposed to improper learerr (see also Section 1.3), a proper learning algorithm gives us a compact representation (storing W requires (kd) memory) of the sorting function that allows us efficiently compute (with runtime Okd k klog k:)) the ranking corresponding to fresh datapoint E Rdd
Learning in top-r Disagreement. We next present our learning algorithm for the top-r metric formally defined as top-- 7) [ 1 # TI..r. where by Ir. we denote the ordering on the first r elements of the permutation π. The top-r metric is a disagreement metric in the sense that it takes binary values and for r 1 captures the standard (multiclass) top-1 classification loss. We remark that, in contrast with the top-r classification loss, which only requires the predicted label to be in the top-r predictions of the model, the top-r ranking metric that we consider here requires that the model puts the same elements in the same order as the ground truth in the top-r positions. The top-r ranking well motivated as, for example, in ad targeting (discussed in Section 1.1) we want to be accurate on the top-r ad categories for user so that we can diversify the content that they receive.
Theorem 2 (Learning LSFs in top-r Disagreement). Fix nj E [0. 1/2), r E [k] and e, E (0, 1). Let D be an n-noisy linear label ranking distribution satisfying the assumptions of Definition with ground-truth LSF ow- (-). There exists algorithm that draws N = =0 drk
71122y) log(1/5)
samples from D, runs in cample-polynone time and computes a matrix W R such that, with probability at least 8,
(ow (w) sc. Na
E
As direct corollary of our result, obtain a proper algorithm for learning the top-1 element with respect the standard 0-1 loss that uses (kd)) samples. In fact, for small values of r, i.e., r O(1),, our sample complexity is essentially tight. It is known that @(kd) samples are information theoretically necessary [Nat89] for top-1 classification. For the case r k. i.e., when we want to learn the whole ranking with respect to the 0-1 loss, our sample complexity is O(kdd). However, using arguments similar to [DSBDSS1I], one can show that in fact O(d)) ranking samples are sufficient in order to learn the whole ranking with respect to the 0-1 loss. In this case, it is unclear whether a better sample complexity can be achieved with an efficient algorithm and we leave this as an interesting open question for future work.
1.3 Our Techniques
Learning in Kendall's Tau distance. Our proper learning algorithm consists of two steps: an improper learning algorithm that decomposes the ranking problem to O(k2) binary linear classifica- tion problems and a convex (second order conic) program that "compresses" the 2 linear classifiers
Notice that in this Kendall's Tau distance is simply the standard 0-1 binary loss.
*Strictly speaking, those lower bounds do not directly apply in our setting because our labels are whole rankings instead of just the top classes but, in the Appendix D, we show that we can adapt the lower bound technique of (DSBDSSI I] to obtain the same sample complexity lower bound for our ranking setting.
3

---

to obtain k x d matrix W. Our improper learning algorithm splits the ranking learning problem into O(k2) binary, d-dimensional linear classification problems with Massart noise. In particular, for every pair of elements i,j E [k], each binary classification task asks whether element is ranked higher than element j in the ground-truth permutation dw- (a:). As we already discussed, we have that, under the Gaussian distribution, there exist efficient Massart learning algorithms [BZ17, MV19, 19, DKTZ20, ZSA20, ZL21] that can recover linear classifiers sgn(v., 2) that correctly order the pair J for all x apart from a region of O(e) -Gaussan mass. However, we still need to aggregate the results of the approximate binary classifiers in order to obtaín a ranking of the alternatives for each æ. We first show that we can design "voting scheme" that combines the results of the binary classifiers using an efficient constant factor approximation algorithm for the Minimum Feedback Are Set (MFAS) problem [ACN08]. This gives an efficient but improper algorithm for learning LSFFs in Kendall's Tau distance. In order to obtain a proper learning algorithm, we further "compress" the O(k²) approximate linear classifiers with normal vectors Vi and obtain matrix W R with the property that the difference of every two rows W; W is O(c)-close to the vector Vij. More precisely, we show that, given the linear classifiers Vay R we can efficiently compute matrix W E R such that the following angle distance with W* is small:
dangie (W, W*) A max O(W; W, W; Wj) S Oc)). (.)
It is not hard show that, as long the above angle metric is at most (e)), then (in expectation over the standard Gaussian) Kendall's Tau distance between the LSFs is also O(c). A key technical difficulty that we face in this reduction is bounding the "condition number" of the convex (second order conic) program that finds the matrix W given the vectors Vij. see Claim 2. Finally, we remark that the proper learning algorithm of Theorem results in a compact and efficient sorting function that requires: (i) storing (kk) weight vectors as opposed to the initial O(22) vectors of the improper learner; and (ii) evaluating i inner products with æ to find its ranking (instead of O(k2)).
see
Learning in top-r Disagreement. We next turn our attention to the more challenging top-r ranking disagreement metric. particular, suppose that we are interested in recovering only the top element of the ranking. One approach would be to directly use the improper learning algorithm for this task and ask for KT distance of order roughly e/k². The resulting hypothesis would produce good predictions for the top element but the required sample complexity would be O(dk²). While it seems that training O(k2) d-dimensional binary classifiers inherently requires (dd?²) samples, we show that, using the proper KT distance learning algorithm of Theorem 1, can also obtain improved sample complexity results for the top-r metric. Our main technical contribution here is a novel estimate of the top-r disagreement in terms of the angle metric. In general, one can show that the top-r disagreement is at most O(k2) dangie W*). We significantly sharpen this estimate by showing the following lemma.
Lemma 1 (Top-r Disagreement via Parameter Distance), Consider two matrices W, W* e Raxd and let No be the standard Gaussian in d dimensions. We have that
Pr [o (Wx) o1.. (W+x)) s Ö(kr) dangle (W, W N>NN
We remark that Lemma is a general geometric tool that we believe will be useful in other distribution- specific multiclass learning settings. The proof of Lemma mainly relies on geometric Gaussian surface area computations that we believe are of independent interest. For the details, we refer the reader to Section 4. An interesting question with a convex sonvex-geometrie flavor is whether the sharp bound of Lemma also holds under the more general class of isotropic log-concave distributions.
1.4 Related Work
Robust Supervised Learning, We start with a summary of prior work on PAC learning with Massart noise. The Massart noise model was formally defined in [MN06] but similar variants had been defined by Vapnik, Sloan and Rivest [Vap06, Slo88, Slo92, RS94, Slo96]. This model is a strict extension of the Random Classification Noise (RCN) model [AL88], where the label noise uniform, i.e., context-independent and is special case of the agnostic model [Hau18, KSS94], where the label noise is fully adversarial and computational barriers are known to exist [GR09, FGKP06, Dan 16, DKZ20, GGK20, DKPZ21, HSSVG22). Our work partially builds upon the algorithmic task of
4

---

PAC learning halfspaces with Massart noise [BH20]. In the distribution srarbbbtiioniddeeddeenn setting, known efficient algorithms [DGT19, CKMY20, DKT21] achieve error 7) + and the works [DK20, NT22] indicate that this error bound is the best possible in the Statistical Query model [Kea98]. This lower bound motivates the study of the distribution-speciff setting (which is also the case of our work). There is an extensive line of work in this direction: [ABHU15, ABHZ16, Y7.17, ZLC17, BZ17, MV19, DKTZ20, ZSA20, ZL21] with the currently best algorithms succeeding for all d < 1/2 with sample and computational complexity poly(d, 1/e, 1/(1 2n)) under class of distributions including isotropic log-concave distributions. For details, see [DKK+21] J. In this work we focus on Gaussian marginals but some of our results extend to larger distribution classes.
Label Ranking. Our work lies in the area of Label Ranking, which has received significant attention over the years (SS07, HFCB08, CH08, HPRZ03, FHMB08, DSM03). There are multiple approaches for tackling this problem (see [VG10], [ZLY+14]), Some of them are based on probabilistic models [CH08, CDH10, GDV12, ZLGQ14] or may be tree based, such as decision trees [CHH09], entropy based ranking trees and forests [RdSRSKI5, dSSKC17), bagging techniques [AGM17] and random forests [ZQ18]. There are also works focusing on supervised clustering [GDGV13]. Finally, [CH08, CDHI0, CHH09] adopt an instance-based approaches using nearest neighbors approaches. The above results are industrial. From theoretical perspective, LR has been mainly studied from statistical learning theory framework [CV20, CKS18, KGB18, KCS17J. [FKP21] provide some computational guarantees for the performance of decision trees in the noiseless case and some experimental results on the robustness of random forests to noise. The setting of [DGR 14] is close to ours but is investigated from an experimental standpoint. We remark that while reducing LR to multiple binary classification tasks has been used in prior literature [HFCB08, CH12, FKP21J, standard reductions can not tolerate noise in rankings (nevertheless, from experimental perspective, e.g., random forests seem robust to noise but lack formal theoretical guarantees). Our reduction crucially relies on the existence of efficient learning algorithms for binary linear classification with Massart noise.
Notation and Preliminaries
General Notation. We use Ō(-) to omit poly-logarithmic factors. A learning algorithm has sample- polynomial runtime if it runs in time polynomial in the size of the description of the input training set, We denote vectors by boldface æ (with elements æı) and matrices with W, where we let W; Rd denote the i-th of W R and Wij its elements. We denote b the inner product of two vectors and ((a b) their angle. Let Ny denote the d-dimensional standard normal and r((-) the Gaussian surface area.
Rankings. We arg denote the ranking of [k] decreasing order according to the values of v. For ranking म, we let (i) denote the position of the i-th element. If π = T T(x), we may also write T (i) to denote the position of i. We often refer to the elements of ranking as alternatives. For a ranking a, we let o1., denote the top-r part of a. When o = o (x), we may also write o and or (x) will be the alternative at the E-th position. We let AKT denote the (normalized) KT distance, i.e., (KT(T,T) -E 1fi > 5)/ (b) for π, T Sk-
3 Learning in KT distance: Theorem 1
In this section, we present the main tools required to obtain proper learning algorithm of Theorem 1. Our proper algorithm adopts a two-step approach: it first invokes an efficient improper algorithm which, instead of linear sorting function (i.e., a matrix W Rxxd), outputs a list of Olk2) linear classifiers. We then design a novel convex program in order to find the matrix W satisfying the guarantees of Theorem 1. Let us begin with the improper learner for LSFs with bounded noise with respect to the KT distance, whose description can be found in Algorithm 1.
3.1 Improper Learning Algorithm
Let us assume that the target function is o (xx) aw- (a:) argsort (* for some W E R
Binary decomposition and Noise Structure. For each drawn example (æ, x) from the noiss linear label ranking distribution D (see Definition 2), we create (*) binary examples (a, yb)
Step 1:
5

---

Algorithm 1 Non-proper Learning Algorithm ImproperLSF
Input: Training set T {(x', x²' HeM)., c, (0.1). (0,1 Output: Sorting function / Rd + Sk
For any 1 S i jj k. create Ti f(=', sgm( (
For any 1 S jグ S k. compute Vii = MassartLTF(Tij. 1 1ok
P. See Appendix A.1
Ranking Phase: Given æ E R
(a) Construct directed graph G with V(G) = [|]] and edges ezj only if vij > 0 +
(b) Output h(x) = MF)
> See Appendix A.1
with Vij = sgg(((() - T()) for any 1 iiijjs k. We have that
Pr [BU (W, Wj) x)
< 0 x s~
Pr
[T(i) (()) W x < W x]
(a.r))-D
Since M(o*(a:) )) an n7-nossy ranking distribution (see Definition 1), we get that the above quantity is at most 1) < 1/2. Therefore, each sample (z,) can be viewed as sample from a distribution Dij with Gaussian z--maggiaa, optimal linear classifier sgn((W; w æ), and Massart noise r).
Hence, we have reduced the task of learning noisy LSFs to a number of (*) sub-problems concerning the learnability of halfspaces the presence of bounded (Massart) noise.
Step 2: Solving Binary Sub-problems. We can now apply the algorithm MassartLTF for LTFs with Massart noise under standard Gaussian marginals [ZSA20] (for details, see Appendix A.1): for all the pairs of alternatives 1 S i < j S k with accuracy parameter e', confidence 8 = O(8/k²) and
a total number of N = á (1- log(k/8) i.i.d. samples from D, we can obtain a collection of linear classifiers with normal vectors Viy for any j. We remark that each one of these halfspaces Vij achieves disagreement with the ground-truth halfspaces W - W with high probability, i.e.,
Pr (sgn(wzg x) + sgn((W? - Wj) x)] 6'. Na
Step 3: Ranking Phase. We now have to aggregate the linear classifiers and compute a single sorting function Rd + Sg. Given an example æ. we create the tournament graph G with k nodes that contains directed edge eijj if Viy x > O. If G is acyclic, output the induced permutation; otherwise, the graph contains cycles which should be eliminated. In order to output a ranking, we remove cycles from G' with efficient, 3-approximation algorithm for MFAS [ACN08, VZW09]. Hence, the output h(x) and the true target o² (a) will have Eg,,N, (ArT((())) a* (=)) < '3' = 4c'. This last equation indicates why constant factor approximation algorithm suffices for purposes- we can always pick é' = c/4 and complete the proof. For details, see Appendix A.1.
3.2 Proper Learning Algorithm: Theorem 1
Having obtained the improper learning algorithm, we can now describe our proper Algorithm 2. Initially, the algorithm starts similarly with the improper learner and obtains collection of binary linear classifiers. The crucial idea is the next step: the design of an appropriate convex program which will efficiently give the matrix W. We proceed with the details. For the proof, see Appendix A.2.
Algorithm 2 Proper Learning Algorithm ProperLSF
Input: Training set T = { x²) Tre(n) c, E (0, 1). n (0,1/2)
Output: Linear Sorting function h IRd St, i... h(-) ow (-) for some matrix W p
Compute (Dty)ısi<js* = ImproperLLSF(T.c.6b. Setup the CP I and compute W = Ellipsoid
See Algorithm 1 D See Appendix A.2
Ranking Phase: Given æ e Rdd, output h(x)) = argsort (x)
Step 1: Calling Non-proper Learners. As a first step, the algorithm calls Algorithm with parameters e, å and 7 E 1/2) and obtains a list of linear classifiers with normal vectors viy for i < j. Without loss of generality, assume that || la 1.

---

Step 2: Designing and Solving the CP 1. Our main goal is to find matrix W whose LSF is close to the true target in KT distance. We show the following lemma that connects the KT distance between two LSFss with the angle metric (.ngge(:;)) defined in Eq. (1). The proof can be found in the Appendix A.2.
Lemma 2. For W. W E [Rexd it holds E (AKT (ar), ow (x))) dangio (W, W
The above lemma states that, for our purposes, it suffices to control the dangle metric between the guess W and the true matrix W It turns out that, given the binary classifiers Day. we can design convex program whose solution will satisfy this property. Thinking of the binary classifier Viy as a proxy for W W we want each difference W.- W to have small angle with V. or equivalently to have large correlation with it, i.e. (W; - -W)) Viy R WW W5llz To enforce this condition, we can therefore use the second order conic constraint (W;- - W Viy 2 (1 - o)|, - W5ll2. We formulate the following convex program I with variable the matrix W:
| |F 1, such that (W, W2) Jiy 2 (1-6) -) IW, Wyll2 for any 1 si<jsk
Find
W R
(1)
for some & E (0, 1) to be decided. Intuitively, since any Viy has good correlation with W W (by the guarantees of the improper learning algorithm) and the CP I requires that its solution W similarly correlates well with Vij. we expect that dangie (W, ; W*) will be small. We show that:
Claim 1. The convex program is feasible and any solution W of I satisfies dangte (W, WW) S.
To see this, note that any solution of CP I is a matrix W whose angle metric (see Eq. (1)) with the true matrix is small by an application of the triangle inequality between the angles of (Dyy. W W)) and (Bsj, Wi - W;) for any i * j. We next have to deal with the feasibility of CP 1. Our goal is to determine the value of Φ that makes the CP 1 feasible. For the pair S < S k, the guess Viy and the true normal vector W W satisfy, with high probability.
Pr [sgn(u; Uig x) + sgn((W," (y))==)) S.
Under the Gaussian distribution (which is rotationally symmetric), it well known that the angle 0(u, v) between two vectors u, v E Rd is equal to π Præ-~N (sgn(u- x) # sgn(v z)). Hence, using Eq. (2), we get that the angle between the guess Viy and the true normal vector W W (WW; Wj. v1,) I cc. For sufficiently small c, this bound implies that the cosine of the above angle is of order 1 - (ce)² and so the following incquality will hold (since Viy is unit):
(W Wj) vij 2 (1 - 2((c))) IW; - Wi
Hence, by setting o- = 2(cc)2, the convex program with variables W E R will be feasible; since [ < 1 comes without loss of generality, W will be a solution with probability 1- - 6.
Next, we have to control the volume of the feasible region. This is crucial in order to apply the ellipsoid algorithm (for details, see in Appendix 1.2.1) and, hence, solve the convex program. We show the following claim (see Appendix 1 for the proof):
Claim 2.
There exists p 2 2 pol((d...1/c..oo(1//
that the feasible set of CP I with o O(e)
contains a ball (with respect to the Frobenius norm) of radius p.
Critically, the runtime of the ellipsoid algorithm is logarithmic in l/p. So, the ellipsoid runs in time polynomial in the parameters of the problem and outputs the desired matrix W.
4 Learning in top-r Disagreement: Theorem 2
In this section show that the proper learning algorithm of Section 3.2 learns noisy LSFs in the top-r disagreement metric. We have seen that, with (k))loo())/)))) samples, Algorithm 2 of Section 3.2 computes a matrix W such that dangle [W, W S see Claim 1. Let us be more specific. Lemma 2 relates the expected KT distance with the angle metric of the two matrices (see also Equation (1)). Our Algorithm 2 essentially gives an upper bound on this angle metric. When we shift our objective and our goal is to control the top-r disagreement, we can still apply Algorithm which essentially controls the angle metrie. The crucial ingredient that is missing is the relation between the loss
7

---

have to control, i.e., the expected top-r disagreement and the angle metric of Equation 1. This relation presented right after and essentially says that the expected top-r disagreement is at most O (kr) times this angle metric. Hence, in order to get top-r disagreement of order e, it suffices to apply our Algorithm with = ((t/(kr))
We continue with our main contribution which is the following lemma that connects the top-r disagreement metric with the geometric distance dangle(-:)), recall Lemma 1. To keep this sketch simple we shall present a sketch of the proof of Lemma for the special case of top-1 classification, which we restate below. The proof of the top-1 case can be found at the Appendix B. The detailed proof of the general case (r > 1) can be found in the Appendix C.
Lemma 3 (Top-1 Disagreement Loss via (:; D). Consider two matrices U, V E RRx and let Na be the standard Gaussian in d dimensions. We have that
Pr (U=) + (Va)) s So 10.001100 (Nvlogh) danglo (U, V). a~>a
We observe that
Pr N-aN
=
E EE]K
Pr (i #1]- m~
(1)
We denote by c - 1(x a. (Uz) = 1(U, . x 2 0), i.e., this the set
where the ranking corresponding to U picks as the top element. Note that c is the indicator of a homogeneous polyhedral cone since can be written the intersection of homogeneous halfspaces. Using these cones we can rewrite the top-1 disagreement of Eq. (1) as
Pr. (a (Ux)) + 01 (Vx)]= = Σ Pr (x) 1, (x) Z>>Va
(E(A]
Hence, task is to control the mass of the disagreement region of two cones. The next Lemma 4 achieves this task and, combined with Eq. (2) directly gives the conclusion of Lemma 3.
Next we work with two general homogeneous polyhedral cones with set indicators C₁, C2:
Lemma 4 (Cone Disagreement). Let C1, C2 : Rdd + {0, be homogeneous polyhedral cones defined by the unit vectors Ui...., U% and Uı uy respectively. For some universal constant e > 0, it holds that Præ~N, Pra-N,(C((E) # C2(x)] S cvlog k max ((v; u:).
Roadmap of the Proof of Lemma 4: Assume that we rotate one face of the polyhedral cone C1 by very small angle 0 to obtain the perturbed cone C2. At high-level, expect the probability of the disagreement region between the new cone C2 and C1 to be roughly (this is an underestimation) equal to the size of the perturbation 0 times the (Gaussian) surface area of the face of the convex cone that we perturbed. The Gaussian Surface Area (GSA) of a convex set C Rd,, is defined as I(A) & Sox (a(x) (z))). where du(()) is the standard surface measure in Rd and Φz(x) = (2/) extp///exppp11111e || 222 J. In fact, in Claim 3 below, we show that the probability of the disagreement between C1 and C2 is roughly ((8)I(FF) ) Log(LI/
+ 1), where F1 is the face of cone C1 that we rotated. Now, when we perturb all the faces by small angles (all perturbations are at most f), we can show (via sequence of triangle inequalities) that the total probability of the disagreement region is bounded above by the perturbation size 0 times the sum the Gaussian surface area of every face (times logarithmic blow-up factor):
Pr (c((z) # (2(=)) N~
Σ
Surprisingly, for homogeneous convex cones, the above sum cannot grow very fast with k. In fact, we show that it can be at most O( O(Vlog k). To prove this, we crucially rely on the following convex geometry result showing that the Gaussian surface area of a homogeneous convex cone is 0(1)
regardless of the number of its faces k.
Lemma 5 ([Naz03]). Let C' be a homogeneous polyhedral cone with k faces Fi...., Fp. Then C has Gaussian surface area I'(C)= Σ I(F.) < L.
8

---

Using an inequality similar to the fact that the maximum entropy of discrete distribution on k elements is at most log k, and, since, from Lemma 5, it holds that -==1((F))) < 1, we can show that Ei= I(Fi)v (og(T/ + = ((/lgg k). Therefore, with the above lemma we conclude that, if the maximum angle perturbation that we perform on C₁ is 0, then the probability of the disagreement region is O(0). We next give the formal proof resulting in the upper bound of O( Vloog k 8) for the disagreement.
Single Face Perturbation Bound: Claim 3: We will use the following notation for the positive orthant indicator R(z) = -I=
written C1 (ax) = R(Vx) --1 1(z 2 0}. Notice that the homogeneous polyhedral cone C1 can be R(v; ....., Ug
æ). Claim 3 below shows that the disagreement of two cones that differ on a single normal vector is bounded by above by the Gaussian surface area of a particular face Fi times logarithmic blow-up factor Vlog(I/T(F)) + 1).
Claim 3. Let vi..... Uk Rd and r E R with B ((11. T) S 9 for some sufficiently small A E (0, π 72). Let F1 be the face with V1 I of the cone R( ((Va x) and > 0 be some universal constant. Then,
Pr. (R(U1- - F, ..... Uk x.) # R(r L., 122 a...., Us x) s ..T(R)) T(B))))) log (((F) + +1) Na
Proof Sketch of Claim 3. Since the constraints U2 x 2 0, ......, Uk x 2 O are common in the two cones, we have that R(v1 ....., Ug x)- * R(r-x, U2 E, E..... Uy x) only when the first "halfspaces"
disagree, ie., when (vi x (r x) < O. Thus, we have that the LHS probability of Claim 3 is equal to
E a
[R(02 B...., Up x) (()) x) x) < 0J
This expectation contains two terms: the term R(v2- 2.... Ub- x) that contains the last k 1 common constrains of the two cones and the region where the first two halfspacce disagree, i.c., the (r
set {xx (#1 2²) (r- æ² < 0}. In order to upper bound this integral in terms of the angle A, we observe that (for 0 sufficiently small) it is not hard to show (see Appendix B) that the disagreement region, which is itself a (non-convex) cone, is a subset of the region {æ |o x S 28 q æ1}, where q the normalized projection of r onto the orthogonal complement of V1 i.e., q proj..' T/ /lprooj.. rll2-
Therefore, we have that the integral of Eq. (3) is at most
E B NNa
[R(02- R,..., Uk x) 1 20 S 201q x+}]]
This is where the definition of the Gaussian surface area appears. In fact, we have to compute the derivative of the above expression (which is function of () with respect to @ and evaluate it at 9 = O. The idea behind this computation is that we can upper bound probability mass of the cone disagreement, i.e., the term Præ~Nn [R(v] 2..... 2) o R(r U2 ,,,..,, Vh æ)] by its derivative with respect to (evaluated at 0) times 0 by introducing o(0) error. Hence, it suffices to upper bound the value of this derivative at O, which is:
2
E --~N,
[R(U2- I...., Uk x) lq x 0((0 xl)]
where 5 is the Dirac delta function. Notice that, if we did not have the term |q z). the above expression would be exactly equal to two times the Gaussian surface area of the face with 21 x 0, i.e., it would be equal to (F.F). We now show that this extra term of q æ|| can only increase the above surface integral by at most logarithmic factor. For some & to be decided, we have that
=fo
E RR ....., 2k σ)) |q æ0 8(1m) a0)] = JOER N~Na
)a(x))q xldp(())
I pa(x))q x|1flq æ S (ddp(z) + 0a(z) q x 1/ x 2 {x)(())
$
JEFR
#EF,
/ SE J
/f JEFF
dz(z)du(z)+
da(z) q x/1llq x 2 {ddp(x),
where du(x)) is the standard surface measure in Rd. The first integral above is exactly equal to the Gaussian surface area of the face FJ. To bound from above the second term we can use the next claim showing that not a lot of mass of the face F₁ can concentrate on the region where lq az| is very large. Its proof relies standard Gaussian concentration arguments, and is provided in Appendix B.

---

Claim 4. It holds that SAEF, Ód(z)]q x x/1i19-a {)dp(x) & D(exp(-E2/00
Using the above result, we get that
E [R(u2- R...., Up x) 11 x s 28|q =|11 dl an
6=0
By picking 0( log(1 can bound the term Pra-Na [R(v) x. ..,.., Vk x)) a R(r æ, 02 at Ug =x] by its derivative with respect to 0, evaluated times 0.
(lg((1 (1/(((F))))))))))))))))))))))))) the result follows since, up to introducing (()) error,
Our work presents the first theoretical guarantees for (linear) LR with noise and settles interesting directions for future work, as mentioned in Section 1. This paper is theoretical and does not have any negative social impact.
Conclusion.
Acknowledgments and Disclosure of Funding
Dimitris Fotakis and Alkis Kalavasis were supported by the Hellenic Foundation for Research and Innovation (H.FR.I)) under the "First Call for H.F.RII. Research Projects to support Faculty members and Researchers and the procurement high-cost research equipment grant", project BALSAM, HFRIFM11-1424.
References
[ABHU15] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. In Conference on Learning Theory, pages 167-190. PMLR, 2015.
[ABHZ16] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. Learn- ing and 1-bit compressed sensing under asymmetric noise. Conference on Learning Theory, pages 192. PMLR, 2016
[ABSV14] Pranjal Awasthi, Avrim Blum, Or Sheffet, and Aravindan Vijayaraghavan. Learning mixtures of ranking models. arXiv preprint 1400.::1100.770 2014.
[ACN08] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent informa- tion: ranking and clustering. Journal of the ACM (JACM), 55(5):1-27, 2008.
[AGM17] Juan A Aledo, José A Gámez, and David Molina. Tackling the supervised label ranking problem by bagging weak learners. Information Fusion, 35:38-50, 2017.
[AL88] Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning. 2(4):343-377 1988.
[APA18] Arpit Agarwal, Prathamesh Patil, and Shivani Agarwal. Accelerated spectral ranking. International Conference on Machine Learning, pages 70-79. PMLR, 2018.
[BDCBL92] Shai Ben-David, Nicolò Cesa-Bianchi, and Philip M Long. Characterizations of Icarnability for classes of (O..... n)-valued functions. In Proceedings of the fifth annual workshop on Computational learning theory, pages 333-340, 1992.
[BFFSZI9] Róbert Busa-Fekete, Dimitris Fotakis, Balázs Szörényi, and Manolis Zampetakis. Optimal learning of mallows block model. In Conference on Learning Theory, pages 529-532, PMLR, 2019.
[BH20] Maria-Floring Balcan and Nika Haghtalab. Noise in classification, 2020.
[BM09] Mark Braverman and Elchanan Mossel. Sorting from noisy information. arXiv preprint arXiv:0910. /91, 2009.
[BT52] Ralph Allan Bradley and Milton Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-34 1952.
10

---

[BZ17] Maria-Florina F Balcan and Hongyang Zhang. Sample and computationally efficient learning algorithms under s-concave distributions. Advances in Neural Information Processing Systems, 30, 2017.
[CDH10] Weiwei Cheng, Krzysztof Dembczynski, and Eyke Hüllermeier. Label ranking meth- ods based on the plackett-luce model. In ICML, 2010.
[CH08] Weiwei Cheng and Eyke Hüllermeier. massance-based label ranking using the mallows model. In ECCBR Workshops, pages 143-157, 2008.
[CH12] Weiwei Cheng and Eyke Hüllermeier. Probability estimation for multi-class classifica- tion based on label ranking. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 83 83-98. Springer, 2012.
[CHH09) Weiwei Cheng, Jens Hühn, and Eyke Hüllermeier. Decision and instance-based learning for label ranking. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 161-168, 2009.
[CKMY20] Sitan Chen, Frederie Koehler, Ankur Moitra, and Morris Yau. Classification under misspecification: Halfspaces, generalized linear models, and evolvability. Advances in Neural Information Processing Systems, 33:8391-8403 2020.
[CKS18] Stephan Clémençon, Anna Korba, and Eric Sibony. Ranking median regression: Learning to order through local consensus. In Algorithmic Leurning Theory, pages 212-245. PMLR, 2018.
[CPS13] Ioannis Caragiannis, Ariel Procaccia, and Nisarg Shah. When do noisy votes reveal the truth? In Proceedings of the fourteenth ACM conference Electronic commerce, pages 143-160, 2013.
[CV20] Stéphan Clémençon and Robin Vogel. A multiclass classification approach to label ranking. In International Conference Artificial Intelligence and Statistics, pages 1421-1430. PMLR, 2020.
[Dan16] Amit Daniely, Complexity theoretic limitations on learning halfspaces. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 105-117, 2016.
[DGR 14] Nemanja Djurie, Mihajlo Grbovic, Vladan Radosavljevic, Narayan Bhamidipati, and Slobodan Vucetic. Non-linear label ranking for large-scale prediction of long-term user interests. In Twent-FFigtth AAAI Conference on Artificial Intelligence, 2014.
[DGT19] Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-indeeendent pac learning of halfspaces with massart noise. Advances in Neural Information Processing Systems, 2019.
[DK20] Ilias Diakonikolas and Daniel M Kane. Hardness of learning halfspaces with massart noise. arXiv preprint arXiv:2012.09720, 2020.
[DKK+21] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with general massart noise under the gaussian distribution. arXiv preprint arXiv:2108.0877 2021.
[KM05]] Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron- based active learning. In International conference on computational learning theory, pages 249-263. Springer, 2005.
[КPО21]] Ilias Diakonikolas, Daniel M Kane, Thanasis Pittas, and Nikos Zarifis. The optimality of polynomial regression for agnostic learning under gaussian marginals. arXiv preprint arXiv:2 2021.
[DKT21] Ilias Diakonikolas, Daniel Kane, and Christos Tzamos. Forster decompasition and learning halfspaces with noise. Advances Neural Information Processing Systems, 34, 2021.
11

---

[JKТZ20] Ias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learn- ing halfspaces with massart noise under structured distributions. In Conference on Learning Theory, pages 1486-1513. PMLR, 2020.
[DKZ20] Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems, 33: 13.1166-13396 2020.
[DOS18] Anindya De, Ryan O'Donnell, and Rocco Servedio. Learning sparse mixtures of rankings from noisy information. arXiv preprint arXiv: 2018.
[DSBDSS1]] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the emm principle. In Proceedings of the 24th Annual Conference on Learning Theory, pages 207-232. JMLR Workshop and Conference Proceedings. 2011.
[DSM03] Ofer Dekel, Yoram Singer, and Christopher D Manning. Log- models for label ranking. Advances in neural information processing systems, 16:497-504, 2003.
[DSS14] Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems, In Conference on Learning Theory, pages 287-316. PMLR, 2014.
[dSSKC17] Cláudio Rebelo de Sá, Carlos Soares, Arno Knobbe, and Paulo Cortez. Label ranking forests. Expert systems, 34(1)=e12166, 2017.
[FGKP06] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. New results for learning noisy parities and halfspaces. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (F0CS'06), pages 563-574. IEEE, 2006.
[FHMB08] Johannes Fürnkranz, Eyke Hüllermeier, Eneldo Loza Meneía, and Klaus Brinker. Multilabel classification via calibrated label ranking. Machine learning, 73(2):133 153, 2008
[FKP21] Dimitris Fotakis, Alkis Kalavasis, and Eleni Psaroudaki. Label ranking through nonparametric regression. arXiv preprint arXiv:2111.0222 11.02499 2021.
[FKS21] Dimitris Fotakis, Alkis Kalavasis, and Konstantinos Stavropoulos. Aggregating in- complete and noisy rankings. In International Conference on Artificial Intelligence and Statistics, pages 2278222882222 2278-2286. PMLR, 2021.
[GDGV13] Mihajlo Grbovic, Nemanja Djuric, Shengbo Guo, and Slobodan Vucetic. Supervised clustering of label ranking data using label preference information. Machine learning. 93(2-3):191-225, 2013.
(GDV12] Mihajlo Grbovic, Nemanja Djuric, and Slobodan Vucetic. Learning from pairwise preference data using gaussian mixture model. Preference Learning: Problems and Applications in AI, 33, 2012.
[GGK20] Surbhi Goel, Aravind Gollakota, and Adam Klivans. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing , 33:2147- 2158, 2020.
[GR09] Venkatesan Guruswami and Prasad Raghavendra. Hardness of learning halfspaces with noise. SIAM Journal on Computing, 39(2):742-765, 2009.
[aul8]] David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. In The Mathematics of Generalization, pages 37- 16. CRC Press, 2018.
[HFCB08] Eyke Hüllermeier, Johannes Fürnkranz, Weiwei Cheng, and Klaus Brinker. Label ranking by learning pairwise preferences. Artificial Intelligence, 179(1161187--1116 2008.
12

---

[HPRZ03] Sariel Har-Peled, Dan Roth, and Dav Zimak. Constraint classification for multiclass classification and ranking. Advances in neural information processing systems, pages 809-816, 2003. URL: https://prroceediggg neur heurips.co htppscc//aapppp..ee wctppaappee/000//t11ee.. 10226666f8844400644440444222---3 pdf.
[HSSVG22] Daniel Hsu, Clayton Sanford, Rocco Servedio, and Emmanouil-Vasiie Gkaragkounis. Near-optimal statistical query lower bounds for agnostically learning intersections of halfspaces with gaussian marginals. arXiv preprint arXiv:2202.05000 220.000996, 2022.
Vlatakis-
[Hun04] David R Hunter. Mm algorithms for generalized bradley-terry models. The annals of statistics, 32(1):384 -06, 2004.
[KCS17] Anna Korba, Stephan Clémençon, and Eric Sibony, A learning theory of ranking aggregation. Artificial Intelligence and Statistics, pages 1001-1010. PMLR, 2017.
[Kea98] Michael Kearns. Efficient moise-toleran learning from statistical queries. Journal of the ACM (JACM), 4566))983-0006 1998.
[KGB18] Anna Korba, Alexandre Garcia, and Florence Alché Buc. A structured prediction approach for label ranking. arXiv preprint 1007::887.003777 2018.
[KMS06] Claire Cenyon-Mathies and Warren Schudy. How to rank with few errors-a a ptas for weighted feedback are set on tournaments. ELECTRONIC COLL.QUUIUM ON COMPUTATIONAL COMPLEXITY, REPORT NO. 144 (2006). Citeseer, 2006.
[KSS94] Michael Kearns, Robert E Schapire, and Linda M Sellie. Toward efficient agnostic learning. Machine Learning, 17-41115--14, 1994.
15-141,
[LB11] Tyler Lu and Craig Boutilier. Learning mallows models with pairwise preferences. In ICML, 2011.
[LM18] Allen Liu and Ankur Moitra. Efficiently learning mixtures mallows models. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pages 627-638. IEEE, 2018
[LM21] Allen Liu and Ankur Moitra. Robust voting rules from algorithmic robust statistics. arXiv preprint 12.00021 2021.
[Luc12] R Duncan Luce. Individual choice behavior: A theoretical analysis. Courier Corpora- tion, 2012.
[LV07] László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms, 30(3):307-358, 2007.
[Ma157] Colin L Mallows. Non-null ranking models. i. Biometrika, 44(1/2):114-133 1957.
[MN06] Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, (4(5):2332-2366 2006.
[MV19] Oren Mangoubi and Nisheeth K Vishnoi. Nonconvex sampling with the metropolis- adjusted langevin algorithm. In Conference on Learning Theory, pages PMLR, 2019.
[MW20] Cheng Mao and Yihong Wu. Learning mixtures of permutations: Groups of pairwise comparisons and combinatorial method of moments. arXiv preprint arXiv:2009.06784 2020.
[Nat89] Balas Natarajan. On learning sets and functions. Machine Learning, 4(1):67-97, 1989.
[Naz03] Fedor Nazarov. On the maximal perimeter of convex set in R with respect to a gaussian measure. In Geometric aspects of functional analysis, pages 169-187. Springer, 2003.
13

---

[NOS17] Sahand Negahban, Sewoong Oh, and Devavrat Shah. Rank centrality: Ranking from pairwise comparisons. Operations Research, 65(1):266-287, 2017.
[NT22] Rajai Nasser and Stefan Tiegel. Optimal sq lower bounds for learning halfspaces with massart noise. arXiv preprint arXiv:2201.09818, 2022.
Papp81]
Christos H Papadimitrion. On the complexity of integer programming. Journal of the ACM (JACM), 28(4):765-768, 1981.
[RdSRSK15] Cláudio Rehelo de Sá, Carla Rebelo, Carlos Soares, and Amo Knobbe. Distance-based decision tree algorithms for label ranking. In Portuguese Conference on Artificial Intelligence, pages 525-534. Springer, 2015.
[RS94] Ronald I. Rivest and Robert Sloan. A formal model of hierarchical concept-learning. Information and Computation, 114(1):881111 1994.
[Sch98] Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
[Slo88] Robert Sloan. Types of noise in data for concept learning. Proceedings of the first annual Workshop on Computational Learning Theory, pages 91-96, 1988.
[SIo92] Robert Sloan. Corrigendum to types of noise in data for concept learning. In Proceedings of the fifth annual workshop on Computational learning theory, page 450, 1992.
[Slo96] Robert Sloan. Pac learning, noise, and geometry. In Learning and Geometry: Computational Approaches, pages 21-41 Springer, 1996.
[SS07] Shai Shalev-Shwartz. Online learning: Theory, algorithms, and applications. Phl) thesis, The Hebrew University Jerusalem, 2007.
[SSBD14] Shai theory algorithms. Cambridge university press, 2014.
and Shai Ben-David. Understanding machine learning: From
[Vap06] Vladimir Vapnik. Extimation of dependences bused on empirical data. Springer Science & Business Media, 2006.
[VG10] Shankar Vembu and Thomas Gärtner. Label ranking algorithms: A survey. In Preference learning, pages 45-64. Springer, 2010.
[Vis21] Nisheeth K Vishnoi. Algorithms for convex optimization. Cambridge University Press, 2021.
[VZW09] Anke Van Zuylen and David P Williamson. Deterministic pivoting algorithms for constrained ranking and clustering problems. Mathematics of Operations Research, 34(3):594-620 2009.
[YZ17] Songbai Yan and Chicheng Zhang, Revisiting perceptron: Efficient and label-optimal learning of halfspaces. Advances in Neural Information Processing Systems, 30, 2017.
[ZL21] Chicheng Zhang and Yinan Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 4526-452) PMLR, 15-19 Aug 2021.
[7ICC1] Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Conference on Learning Theory, pages 1980-2022. PMLR, 2017.
[ZLGQ14) Yangming Zhou, Yangguang Liu, Xiao-Zhi Gao, and Guoping Qiu. A label ranking method based on gaussian mixture model. Knowledge- Bassd Systems, 72:108-113, 2014.
14

---

[ZLY+14] 14] Yangming Zhou, Yangguang Liu, Jiangang Yang, Xiaoqi He, and Liangliang Liu. A laxonomy of label ranking algorithms. J. Comput. 93):557-555, 2014.
[ZQ18]
Yangming Zhou and Guoping Qiu. Random forest for label ranking. Expert Systems with Applications, 112:99-109, 2018.
[ZSA20]
Chicheng Zhang, Jie Shen, and Pranjal Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 71 84-7197. Curran Associates, Inc., 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] We have presented the assump-
tions of our models and we have explained future research directions in Section 1.
(c) Did you díscuss any potential negative societal impacts of your work? [Yes] We have discussed that the Conclusion paragraph at the end of the main body.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We have specified the theoretical models we are working on, see e.g., Section 1.1.
(b) Did you include complete proofs of all thcoretical results? [Yes] Due to space con- straints we have included the full proofs of the results in the Supp. Material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL.? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "pFlb05RCE1K", "reviewer": "Reviewer_AkRj", "summary": "This work tackles the problem of learning linear sorting functions with bounded noise under Gaussian martingales. The proposed algorithms enjoy strong theoretical sampling guarantees and a polynomial runtime, for both the normalized Kendall’s Tau distance and the top-r disagreement loss.\n", "questions": "- What is the intuition behind the power 6 in theorem 1 and 2?\n- Is Algorithm 2 used for both Theorem 1 and 2?\n", "limitations": "The theoretical limitations are adequately addressed. The authors state that the potential negative societal impacts of their work is N/A due to its theoretical nature. It might still be valuable to mention what could go wrong if the suggested algorithms were actually deployed. \n", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Presentation: the problem is well introduced and the main results are clearly presented\n- Impact: the results established seem to be of general interest in addition to solve the label ranking problem\n- The paper is technically sound.\n\nWeaknesses: \n- No experimental results limit the impact of the work.\n- Clarity: although the first two sections are very clear, the second half of the paper feels harder to follow. It does not feel clear to me whether the stated algorithms are solutions to the problem with KT Distance or with top-r Disagreement, or both. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Tg7tz1w7jN2", "reviewer": "Reviewer_bxrG", "summary": "This paper is the first to study the problem of learning linear label rankings in the presence of noise.\n\nIn the label ranking problem, we are given access to samples of the form $(x,y)$ where $x \\in \\mathbb{R}^d$ and $y$ is a permutation of the sequence {$1, 2, 3, \\ldots, k$}. For example, this can correspond to a ranking of movies by preferences of a particular user in a movie recommendation system. In the **linear** label ranking problem, there is an additional constraint that the ranking should be such that it can be formed by the indices corresponding to a descending sort of the entries of $Wx$ for some matrix $W \\in \\mathbb{R}^{k \\times d}$. Further, in the **noisy** linear label ranking problem, we are given access not to *pure* samples from a linear label ranking distribution but instead samples whose labels are corrupted by some noise. This paper also assumes that the marginal distribution of $x$ needs to be Gaussian.\n\nThey provide two algorithms, one improper and one proper, for learning with error bounds in the normalized Kendall tau (KT) distance. They also provide an algorithm with error bounds in the top-$r$ disagreement metric. In particular, their improper learning algorithm in the KT distance uses algorithms for learning linear-threshold-functions (LTFs) in the Massart noise model as sub-routines.", "questions": "Not any as of now.", "limitations": "This is primarily a theoretical paper and so the authors have mentioned that it doesn't have any negative social impact.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: I am not an expert in this area so I am not entirely sure about other related work. The proposed algorithms and getting them to work (as in proving guarantees for them) are quite non-trivial and so the paper is quite original in my opinion.\n\nQuality: The submission is technically sound. All claims are well-supported with proofs.\n\nClarity: The submission is clearly written and well-organized.\n\nSignificance: The paper is the first to study a very natural problem and so I think it is quite significant. Ranking functions have many applications and developing robust algorithms for learning ranking functions can have good practical impact. On the theoretical front, these problems are also clearly of interest to the NeurIPS community. As mentioned on page 2 of the paper, the case of $k = 2$ captures the problem of learning halfspaces with Massart noise - the best paper award winner of NeurIPS 2019 was on this topic.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IO_lPHqsEFz", "reviewer": "Reviewer_A2Wu", "summary": "This paper considers the learning of linear sorting functions under Gaussian marginals in presence of bounded noise. In the special case k=2, the problem reduces to the well-studied learning of halfspaces with Massart noise. The author generalized the problem setting and provided efficient algorithms with respect to Kendall’s Tau distance and top-r disagreement loss.\n", "questions": "The current work studies bounded noise type. Is there any possibility or evidence of extending it to more challenging noise types, e.g. adversarial noise?\n\nMinor issue: Some notations are not well defined. For example, the sample complexity N could be distinct for different algorithms. r was used both for the top-r problem and for the radius in Claim 2.\n", "limitations": "The work does not have negative social impacts.\n", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The work makes a significant contribution by proposing the first efficient algorithm for learning of LSFs with bounded noise. The basic algorithmic ingredient is an efficient learner ([ZSA20]) for the class of halfspaces (for the special case of k=2). However, the algorithm is generalized to any k (improperly), and is further used to obtain a proper learner using the ellipsoid method. When the error is measured by top-r disagreement loss, the proper learner also achieves improved sample complexity comparing to a naive invocation of the improper learner. The paper is very well-written with technical highlights appropriately placed and the analysis is sound.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HVZg7O2tF9e", "reviewer": "Reviewer_pDth", "summary": "The setup is the following: there is an unknown k x d matrix W and a player observes a feature vector x in R^d and a 'ranking' sigma(x) (i.e., a permutation) over [k] generated as follows. The feature vector x is sampled from a d-dimensional standard Gaussian. Then, the permutation sigma(x) over [k] is generated by sorts the indices of Wx in decreasing order. \n\nThe goal is the learn a matrix ~W which approximates the label ranking, in particular, we want that with high probability over a fresh x drawn from a d-dimensional standard Gaussian, sorting ~Wx gives a permutation which is very close to that of Wx. \n\nThe paper studies two notions of closeness: kendal-tau distance, and top-r distance. \n\nThe kendal-tau distance (KT) between two permutations is the fraction of pairs i,j in [k] where their relative order agrees. In the learning setup, this corresponds to saying that with high probability over x, with high probability over a random (i,j) from [k]x[k], the relative order of (Wx)_i and (Wx)_j agrees with (~Wx)_i and (~Wx)_j. \n\nWhile the kendal-tau distance is well-studied, it is perhaps less motivated in ranking setups, where one is more interested in higher ranked elements. In settings where higher ranked elements are more important, the paper studies the top-r distance. This is a 0-1 distance based on whether the top r ranked elements are exactly the same in exactly the same order.\n\nWhile exact versions of the above are relatively simple (an algorithm using linear programming can find ~W), there is some noise in what the player observes. In particular, the player observes a draw from a distribution which is promised that each pair disagrees with the ground-truth ordering with probability at most eta (where eta < 1/2).\n\nResults: \n\n1. A polynomial-time algorithm for learning ~W in KT distance from O(d log(k) / (eps (1 - 2eta)^6 ) ) up to distance eps. \n\n2. A polynomial-time algorithm for learning ~W in top-r distance from O(d k r / (eps (1-2eta)^6 ) ) up to distance eps. \n\nImportant remarks:\n\nThe noise model is arbitrary as long as it has marginals on pairs which are different with probability at most eta. This, along with the fact that sorting functions are linear, makes the problem a similar of learning halfspaces with Massart noise.\n\nBecause of this connection, the assumption that x is Gaussian is somewhat necessary because there are  super-polynomial lower bounds in the statistical query model.\n\nThe algorithm proceeds in three steps. First, a reduction from a ranking to O(k^2) binary comparisons. Second, an improper learner which aggregates the O(k^2) binary comparisons. Third, an algorithm which uses the intermediate steps of the improper learning to output a hypothesis ~W. While the first and second steps are known and have appeared in the literature before, the novel aspect of this work is finding the matrix ~W -- to do this, the paper proves two interesting geometric lemmas relating the angles between proposed rows of ~W and W with the corresponding KT and top-r distance. \n", "questions": "I don't have any pressing questions.", "limitations": "The work is purely theoretical at this point, and seems to have no potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper studies a natural problem in learning rankings. The problems seem like natural extensions of learning halfspaces with Massart noise, and a good model for learning rankings with noise. From a technical perspective, the approach is natural and the geometric lemmas interesting. The paper is also well-written.\n\nWeaknesses:\n\nI don't really see any strong weaknesses in the paper.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept