Uniform Convergence of Rank-weighted Learning

Justin Khim, Liu Leqi, Adarsh Prasad, Pradeep RavikumarICML 2020 · OpenReview

The Limits of "Average" Performance

Most classical machine learning models are trained to minimize expected loss—essentially aiming for the best average-case performance across a dataset. However, in high-stakes scenarios like healthcare, finance, or contexts where fairness is paramount, optimizing for the "average" is often insufficient. In these domains, we frequently care more about the "tail" of the loss distribution (the worst-case scenarios) or need to explicitly ignore anomalous outliers.

To address this, researchers employ rank-weighted risks. Instead of treating every data point's loss equally, these methods weight losses based on their relative rank. For example, a model might be instructed to "ignore the bottom 5% of losses and focus only on the top 5%." While Conditional Value-at-Risk (CVaR) and Trimmed Risk are highly popular in practice, proving their statistical "generalization"—how well a model trained on a sample will perform on unseen data—is notoriously difficult. Because the weight of a single data point depends on its rank relative to all other points in the dataset, it creates complex dependencies that break standard statistical proof techniques.

This paper provides the first rigorous theoretical framework for the "uniform convergence" of this broad class of rank-weighted learning objectives.

Unifying Risk with L-Statistics

The authors introduce a unified mathematical object called L-Risk, drawing on the classical statistical theory of L-statistics.

  1. A Unified Framework: They demonstrate that L-Risk can represent many existing measures, including CVaR, Trimmed Risk, and Human-Aligned Risk (derived from Cumulative Prospect Theory), simply by altering a "scoring function," denoted as $w(t)$.
  2. Bounded Variation (BV): A critical breakthrough in this work is relaxing the requirement for the scoring function to be perfectly smooth (Lipschitz). Instead, they allow it to have "bounded variation." This is essential because many practical risk measures, like trimming, rely on step functions that are inherently discontinuous.
  3. Stability Analysis: To handle the complex dependencies introduced by ranking, the authors develop a novel "partition argument" to prove that these rank-weighted functions remain stable even when the underlying data is slightly perturbed.
Illustration of the partition argument used to analyze the stability of rank-weighted functions.

By combining VC-dimension theory with covering number bounds for BV functions, the authors successfully derive the first uniform convergence rates for this entire class of risk measures.

Theoretical Guarantees vs. Empirical Reality

The Lipschitz vs. BV Divide

The theoretical analysis reveals that the "smoothness" of the rank-weighting function dictates the learning rate:

  • Smooth (Lipschitz) Weights: If the weighting function is smooth, the model achieves the standard, faster convergence rate of $O(n^{-1/2})$.
  • Discontinuous (Bounded Variation) Weights: If the function is "jumpy" (e.g., a hard cutoff for outliers), the proven convergence rate drops to $O(n^{-1/4})$.

Crucially, the paper proves uniform convergence rather than just pointwise concentration. This provides a much stronger guarantee: any model selected from the hypothesis class based on training data will generalize well, not just one specific model.

The Empirical Gap

While the $O(n^{-1/4})$ bound for discontinuous functions is a significant theoretical milestone, the authors' synthetic experiments (using controlled logistic and linear regression setups) revealed an interesting discrepancy.

Log-log plot of uniform error versus sample size (n). The empirical slopes of roughly -0.5 suggest a convergence rate of O(n^{-1/2}), faster than the theoretical O(n^{-1/4}) bound for bounded variation functions.

Even for non-smooth risks like CVaR and Trimmed Mean, the empirical convergence rate often tracked much closer to $O(n^{-1/2})$ (indicated by a slope of roughly -0.5 on a log-log plot of error versus sample size). This suggests that while the newly established $O(n^{-1/4})$ bound is the first of its kind, it may be conservative, hinting that tighter theoretical bounds likely exist.

Limitations and the Path Forward

The findings open several avenues for future research:

  • Closing the Rate Gap: The primary open question is bridging the gap between the proven $O(n^{-1/4})$ theoretical rate and the observed $O(n^{-1/2})$ empirical performance for BV functions.
  • Optimization Challenges: L-Risks are generally non-convex with respect to model parameters. While the authors demonstrated that a simple iterative weighting heuristic performs competitively, there is a pressing need for optimization algorithms specifically tailored for rank-weighted objectives.
  • Fundamental Limits: While this paper establishes upper bounds on generalization error, the fundamental lower bounds for learning with non-Lipschitz rank weights remain unknown.

Summary updated

Abstract

The decision-theoretic foundations of classical machine learning models have largely focused on estimating model parameters that minimize the expectation of a given loss function. However, as machi...
BibTeX
@inproceedings{khim2020uniform,
  author = {Justin Khim and Liu Leqi and Adarsh Prasad and Pradeep Ravikumar},
  title = {{Uniform Convergence of Rank-weighted Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=XBGrvvknOaw},
}
Figure