Maximum Weighted Loss Discrepancy

Fereshte Khani, Aditi Raghunathan, Percy LiangarXiv 2019 · arXiv

Standard machine learning models typically follow the principle of Empirical Risk Minimization (ERM), which focuses on minimizing the average loss across a population. While effective for the majority, this "crowd-pleasing" approach often leaves specific demographic groups behind, resulting in significantly higher error rates for minorities.

In "Maximum Weighted Loss Discrepancy," researchers Fereshte Khani, Aditi Raghunathan, and Percy Liang from Stanford University propose a framework to quantify and mitigate these disparities, even when demographic labels are unavailable during training.

The Challenge of Unseen Groups

Defining fairness is difficult when relevant subgroups are not explicitly labeled. Furthermore, attempting to protect every possible tiny subgroup leads to a statistical impossibility: it is impossible to accurately estimate the error for very small groups from finite data. Practitioners need a way to protect groups that are large enough to be statistically significant without needing to pre-define them.

The MWLD Framework

The authors introduce Maximum Weighted Loss Discrepancy (MWLD). This metric identifies the group $g$ with the largest weighted difference between its local loss and the global average. To make estimation tractable, they employ a weighting function $w(g) = \mathbb{E}[g]^k$.

Extracted figure from page 4 of Maximum Weighted Loss Discrepancy

By adjusting the hyperparameter $k$, practitioners can control the trade-off. At $k=0$, all groups are treated equally (which is shown to be impossible to estimate), while higher $k$ values focus on groups of a significant size, ensuring the metric is robust to statistical noise.

Variance as a Proxy for Fairness

A key theoretical contribution of the paper is the link between MWLD and Loss Variance (LV). The researchers prove that the square root of the variance of individual losses serves as a mathematical upper bound for the MWLD.

Extracted figure from page 4 of Maximum Weighted Loss Discrepancy

This finding is transformative for practitioners: to ensure no group is disproportionately disadvantaged, one should aim to minimize the variance of losses across all individuals. This makes the model's performance more uniform across the entire population, effectively bounding how much any single group can be disadvantaged compared to the average.

Optimization and Results

The authors propose regularizing models using Loss Variance (LV) or Coarse Loss Variance (CLV) when some attributes are known. They developed an efficient $O(n \log n)$ sorting-based algorithm to compute empirical MWLD, making it practical for large-scale datasets.

Testing on standard benchmarks like COMPAS and Census Income revealed that LV regularization could halve loss variance with only a negligible 1–3% increase in average loss. In some cases, such as the German Credit and Communities and Crime datasets, regularizing for fairness actually improved overall generalization, suggesting that protecting subgroups can lead to more robust models for everyone.

Conclusion

MWLD provides a mathematically grounded way to address algorithmic bias without requiring explicit group labels. By framing fairness as a problem of loss variance, the authors offer a practical and efficient path toward more equitable machine learning systems. Future work remains in determining the optimal policy-driven choice of $k$ and extending these guarantees to more complex, overlapping group structures.

Summary updated

Abstract

Though machine learning algorithms excel at minimizing the average loss over a population, this might lead to large discrepancies between the losses across groups within the population. To capture this inequality, we introduce and study a notion we call maximum weighted loss discrepancy (MWLD), the maximum (weighted) difference between the loss of a group and the loss of the population. We relate MWLD to group fairness notions and robustness to demographic shifts. We then show MWLD satisfies the following three properties: 1) It is statistically impossible to estimate MWLD when all groups have equal weights. 2) For a particular family of weighting functions, we can estimate MWLD efficiently. 3) MWLD is related to loss variance, a quantity that arises in generalization bounds. We estimate MWLD with different weighting functions on four common datasets from the fairness literature. We finally show that loss variance regularization can halve the loss variance of a classifier and hence reduce MWLD without suffering a significant drop in accuracy.
BibTeX
@misc{khani2019maximum,
  author = {Fereshte Khani and Aditi Raghunathan and Percy Liang},
  title = {{Maximum Weighted Loss Discrepancy}},
  year = {2019},
  eprint = {1906.03518},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.03518},
}
Figure