Linear Label Ranking with Bounded Noise

Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, Christos TzamosNeurIPS 2022 · OpenReview

Executive Summary

Ranking multiple items accurately when training data is corrupted by noise is a fundamental challenge in supervised learning. While robust tools exist for simple binary classification, Label Ranking (LR) is significantly more complex. This paper provides the first efficient algorithms with provable guarantees for learning Linear Sorting Functions (LSFs) in the presence of bounded (Massart) noise. By assuming Gaussian feature distributions, the authors achieve near-optimal sample complexity for minimizing both the Kendall’s Tau distance and the more stringent top-$r$ disagreement loss.

The Challenge of Noisy Label Ranking

Label Ranking is the task of mapping a set of features (e.g., a user's profile) to a full ranking of labels (e.g., categories of advertisements). A standard approach utilizes a Linear Sorting Function (LSF): multiplying a feature vector by a weight matrix yields scores that determine the order of the labels.

However, real-world data is rarely pristine. The authors focus on Massart noise (bounded noise), where for any pair of labels, there is a probability $\eta < 1/2$ that their observed order is flipped compared to the ground truth. While practitioners often rely on heuristics like random forests for ranking, these methods lack theoretical guarantees and frequently degrade in noisy environments. Previous theoretical work has largely focused on noiseless scenarios or binary classification. This research bridges the gap, offering a mathematically rigorous framework for learning rankings from noisy data.

Methodology: Decomposition and Compression

The authors propose a novel two-step algorithmic framework to tackle this problem:

  1. Decomposition and Robust Binary Learning: The ranking problem is broken down into $O(k^2)$ pairwise comparisons (e.g., "Is label A ranked higher than label B?"). Under the assumption that features follow a Gaussian distribution, the authors leverage existing robust algorithms for "Massart halfspaces" to solve these binary classification problems individually.
  2. Convex Compression (Proper Learning): A collection of independent binary classifiers does not inherently form a valid, globally consistent linear ranking. To resolve this, the authors design a novel Second-Order Conic Program (SOCP). This optimization step "compresses" the disparate binary classifiers into a single, compact weight matrix $W$. The resulting model is "proper"—a true linear sorting function that is efficient to store and evaluate.

For the more challenging top-$r$ disagreement loss—where accuracy is only measured on the top $r$ items—the authors introduce a sophisticated geometric analysis based on the Gaussian Surface Area of polyhedral cones to prove the algorithm's efficiency.

Key Insights: Geometry and Gaussians

Because this is a theoretical paper focused on algorithmic analysis and sample complexity, it relies on mathematical proofs rather than empirical datasets. Several key insights drive the theoretical results:

  • Ranking as a Geometry Problem: Rankings are treated as "cones" in high-dimensional space. The disagreement between two ranking functions is conceptualized as the "volume" of the region where these cones fail to overlap.
  • The Power of Gaussians: Assuming Gaussian features allows the authors to leverage powerful tools from high-dimensional geometry, bypassing computational barriers that typically make learning under Massart noise intractable in the general case.
  • Parameter Distance vs. Ranking Loss: A critical theoretical breakthrough is proving that if the parameters (the weight matrices) of two models are close in terms of their angles, the probability that they disagree on the top-$r$ labels is small. The authors show this disagreement is bounded by $O(\sqrt{\log k})$ times the angle distance, yielding a much sharper bound than previously known.

Theoretical Guarantees

The proposed algorithms run in polynomial time relative to the number of labels ($k$), dimensions ($d$), and the inverse of the error ($\epsilon$). The key sample complexity results include:

  • Kendall’s Tau Distance: The algorithm achieves an error of $\epsilon$ using $\tilde{O}(d \log(k) / \epsilon)$ samples. This is qualitatively near-optimal, as even basic binary classification requires $O(d/\epsilon)$ samples.
  • Top-$r$ Disagreement: For the stricter top-$r$ loss, the algorithm achieves $\epsilon$ error with $\tilde{O}(dkr / \epsilon)$ samples.

Limitations and Future Directions

While this work establishes strong theoretical foundations, it presents several avenues for future research:

  • The Gaussian Assumption: The reliance on standard normal distributions for features is a significant limitation. While the authors suggest extensions to "isotropic log-concave" distributions, real-world data distributions are often far more complex.
  • Strict Noise Model: Massart noise is more realistic than purely random noise, but it remains highly structured. Learning under "Agnostic" noise, where corruptions can be adversarial, is a much harder, open problem.
  • Sample Complexity Gaps: For learning the entire ranking ($r=k$) under a 0-1 loss, the current bound is $O(dk^2)$. The authors note that $O(dk)$ might be theoretically achievable, leaving a gap for future work to close.

Summary updated

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.
BibTeX
@inproceedings{fotakis2022linear,
  author = {Dimitris Fotakis and Alkis Kalavasis and Vasilis Kontonis and Christos Tzamos},
  title = {{Linear Label Ranking with Bounded Noise}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=dgWo-UyVEsa},
}
Figure