Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

strengths_and_weaknesses: Strengths:
- Presentation: the problem is well introduced and the main results are clearly presented
- Impact: the results established seem to be of general interest in addition to solve the label ranking problem
- The paper is technically sound.

Weaknesses: 
- No experimental results limit the impact of the work.
- 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. 

questions: - What is the intuition behind the power 6 in theorem 1 and 2?
- Is Algorithm 2 used for both Theorem 1 and 2?

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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper is the first to study the problem of learning linear label rankings in the presence of noise.

In 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.

They 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.
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.

Quality: The submission is technically sound. All claims are well-supported with proofs.

Clarity: The submission is clearly written and well-organized.

Significance: 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.
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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.

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.

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?

Minor 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.

limitations: The work does not have negative social impacts.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

The 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. 

The paper studies two notions of closeness: kendal-tau distance, and top-r distance. 

The 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. 

While 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.

While 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).

Results: 

1. A polynomial-time algorithm for learning ~W in KT distance from O(d log(k) / (eps (1 - 2eta)^6 ) ) up to distance eps. 

2. A polynomial-time algorithm for learning ~W in top-r distance from O(d k r / (eps (1-2eta)^6 ) ) up to distance eps. 

Important remarks:

The 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.

Because of this connection, the assumption that x is Gaussian is somewhat necessary because there are  super-polynomial lower bounds in the statistical query model.

The 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. 

strengths_and_weaknesses: Strengths:

The 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.

Weaknesses:

I don't really see any strong weaknesses in the paper.  
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.
review_title: null

Meta-review: metareview: The reviewers are unanimous in their strong positive opinion on this paper.  The authors have given the first efficient algorithms for learning noisy linear sorting functions with theoretical guarantees a relevant and useful problems setup for the NeuRIPS community.  The reviewers consider the paper clear and well-presented and thus this is a natural accept.

confidence: Certain
Decision: Accept