Unleashing Linear Optimizers for Group-Fair Learning and Optimization

By Daniel Alabi, Nicole Immorlica, Adam Tauman Kalai. 2018

28 citations recorded by the source corpus.

Most systems and learning algorithms optimize average performance or average loss–one reason being computational complexity. However, many objectives of practical interest are more complex than simply average loss. This arises, for example, when balancing performance or loss with fairness across people. We prove that, from a computational perspective, optimizing arbitrary objectives that take into account performance over a small number of groups is not significantly harder to optimize than average performance. Our main result is a polynomial-time reduction that uses a linear optimizer to optimize an arbitrary (Lipschitz continuous) function of performance over a (constant) number of possibly-overlapping groups. This includes fairness objectives over small numbers of groups, and we further point out that other existing notions of fairness such as individual fairness can be cast as convex optimization and hence more standard convex techniques can be used. Beyond learning, our approach applies to multi-objective optimization, more generally.

Subfields: Artificial Intelligence, Computer Networks and Communications, Philosophy

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Philosophy

Citations in the corpus

Fair Regression: Quantitative Definitions and Reduction-based Algorithms (2019, background): “Our second fairness deﬁnition, bounded group loss, ﬁts into the general framework of Alabi et al. (2018), whose goal is to minimize a general function of group-wise prediction losses, but their algorithm is less efﬁcient (albeit still polynomial), and they do not provide statistical guarantees.”
A Reductions Approach to Fair Classification (2018, background): “, 2017), and led to extensions with more general optimization objectives (Alabi et al., 2018) and combinatorial protected attributes (Kearns et al.”
Fairness without Harm: Decoupled Classifiers with Preference Guarantees (2019, methodology): “…work presents impossibility results to motivate decoupling (i.e., a bound on the maximum loss of accuracy due to pooled training for different hypothesis classes), as well as a computationally efﬁcient procedure to optimize a joint loss function on a set of classiﬁers (see also Alabi et al., 2018).”
Fairness in Machine Learning: A Survey (2020, background): “Note that sufficient data is required for each subgroup for this method of sampling to not negatively affect performance and fairness, as shown by [9], and that outliers can be problematic [45, 211].”
Fairness risk measures (2019, methodology): “Several other recent works implicitly define perfect fairness in terms of subgroup risks (Dwork et al., 2018; Hashimoto et al., 2018; Alabi et al., 2018).”
Fairness in Machine Learning (2020, unknown): “…optimization problem via the method of Lagrange multipliers [3, 15, 34, 37, 38, 59, 97, 135, 183, 185] or add penalties to the objective [5, 14, 22, 44, 46, 56, 58, 62, 73, 74, 75, 79, 82, 87, 88, 89, 93, 94, 95, 98, 104, 115, 119, 123, 133, 134, 135, 138, 139, 154, 165, 176, 179, 180,…”
Rényi Fair Inference (2019, background): “The third category is the in-process approach that enforces fairness by either introducing constraints or adding a regularization term to the training procedure Zafar et al. (2017; 2015) Alabi et al. (2018).”