Source-linked AI summary
Fairness Through Computationally-Bounded Awareness
Michael P. Kim, Omer Reingold, Guy N. Rothblum
TL;DR
The paper addresses fair classification when the similarity metric underlying fairness through awareness is arbitrary and unavailable in full. It introduces metric multifairness over comparison classes and develops learning procedures using bounded metric samples. The resulting framework protects similar, computationally identifiable subpopulations, while the paper characterizes sample-complexity and learnability limits.
Problem
Fair classification needs similarity-based constraints, but requiring an arbitrary metric to be known for every individual pair is infeasible and may prevent learning the metric.
Method
The paper defines metric multifairness over a metric d and a rich, possibly overlapping comparison class C, then learns classifiers using limited random metric samples.
Results
Metric multifairness can be learned with bounded metric access, while guaranteeing fairness across C and showing that stronger guarantees require larger sample complexity.
Takeaways & Limitations
Fairness guarantees can be targeted at efficiently identifiable subpopulations without requiring the learner to know or learn the entire similarity metric.
Takeaways & Limitations
The framework's results are theoretical, and empirical performance across metrics and comparison classes remains future work.
Abstract
from arXiv · showhide
We study the problem of fair classification within the versatile framework of Dwork et al. [ITCS '12], which assumes the existence of a metric that measures similarity between pairs of individuals. Unlike earlier work, we do not assume that the entire metric is known to the learning algorithm; instead, the learner can query this arbitrary metric a bounded number of times. We propose a new notion of fairness called metric multifairness and show how to achieve this notion in our setting. Metric multifairness is parameterized by a similarity metric $d$ on pairs of individuals to classify and a rich collection ${\cal C}$ of (possibly overlapping) "comparison sets" over pairs of individuals. At a high level, metric multifairness guarantees that similar subpopulations are treated similarly, as long as these subpopulations are identified within the class ${\cal C}$.
1 Introduction
Fairness through awareness requires similar individuals to receive similar predictions under a task-specific metric, but assuming that metric is known for every pair is often infeasible. The paper introduces computationally-bounded awareness, which uses limited metric samples while protecting similar subpopulations identifiable by a comparison class.
- Machine-learned classifiers can perpetuate or amplify historical discrimination involving sensitive attributes such as race, gender, or sexual orientation.
- Fairness through awareness requires predictions for similar individuals to differ by no more than their metric distance plus a tolerance.The framework separates externally designed similarity criteria from the learning task.
- Knowing the similarity metric for every pair can be infeasible because it may require expert input, encode latent features, or depend on a complex function of learner-visible features.
- Sampling a small number of metric evaluations cannot guarantee full metric fairness information-theoretically, motivating a weaker but provable fairness notion.
- The paper proposes computationally-bounded awareness, requiring only a small number of random samples from an arbitrary metric while treating similar identifiable subpopulations similarly.The framework preserves the simplicity and flexibility of fairness through awareness without requiring the metric to be learned.
2 Setting and metric multifairness
Metric multifairness relaxes pairwise metric fairness by enforcing statistical similarity constraints over a rich collection of comparison sets. The paper balances guarantee strength against sample complexity by restricting comparisons to sufficiently large and computationally identifiable subpopulations.
- Setting and assumptions: The setting uses an underlying metric d on individuals, data and metric-sample distributions, and convex-loss learning over a bounded linear hypothesis class.Predictions are linear functions projected onto [-1, 1], with normalized feature vectors.
- Metric multifairness: Metric multifairness requires a hypothesis to satisfy Lipschitz-like statistical tests for every comparison set in a collection C.The collection may contain rich, overlapping subsets of individual pairs.
- Metric multifairness: Taking every singleton pair as a comparison recovers ordinary metric fairness, whereas small-sample enforcement requires each comparison to have probability at least γ under the metric-sample distribution.
- Metric multifairness: Coarse group comparisons can miss similar subpopulations within groups, allowing qualified members of one group to receive worse treatment than unqualified members of another.
- Metric multifairness: If a comparison set has average metric distance at most ε, multifairness implies individual metric fairness for at least a 1−p fraction of its pairs with tolerance (ε+τ)/p.Overlapping low-distance comparisons can extend this guarantee to a significant fraction of the population.
- Computationally-bounded awareness: Bounded-complexity comparison classes balance fairness strength with limited metric access by protecting all subpopulations identifiable within the chosen computational bound.The learner receives noisy unbiased metric samples, and the protected subpopulations must be sufficiently represented in that sampling distribution.
- Learning objective: Learning evaluates utility through convex loss relative to an optimal metric-multifair hypothesis in the chosen hypothesis class.
3 Learning a metric multifair hypothesis
The paper formulates fair prediction as a convex optimization problem under metric multifairness constraints and solves it with switching subgradient descent. The method alternates between repairing significantly violated constraints and optimizing predictive loss, with provable fairness, near-optimality, and bounded metric-sample complexity.
- Convex formulation: The objective minimizes expected loss subject to multifairness constraints, using stochastic subgradient descent for linear hypothesis families.The analysis assumes bounded loss Lipschitzness for theorem statements and stochastic subgradient access for both constraints and the objective.
- Guarantees: With probability at least 1 −δ, the method learns a (C, d, τ)-metric multifair and (C, O(τ))-optimal hypothesis for γ-large C.The guarantee is stated for stochastic switching subgradient descent and applies under the theorem’s γ, τ, and δ conditions.
- Complexity: Each iteration uses at most 1 labeled example and runs in ˜O(|C| · n · poly(1/γ, 1/τ, log(1/δ))) time.The number of metric samples depends logarithmically on |C|, while the per-iteration running time depends on |C|.
- Optimization method: Switching subgradient descent repairs a significantly violated constraint; otherwise, it takes a stochastic objective-subgradient step.The algorithm estimates constraint residuals and projects iterates onto the feasible domain when necessary.
- Post-processing: The framework can post-process predictions from a pre-trained model to obtain near-optimal metric-multifair predictions.In this setting, predictions can be represented as a linear hypothesis in N dimensions, and squared loss can preserve fidelity to the original predictions.
- Post-processing: Post-processing fairness guarantees do not generalize outside the N individuals, although utility can improve because predictions need not come from a bounded hypothesis class.The guarantee is therefore limited to the finite set of individuals whose predictions are post-processed.
4 Reducing search to agnostic learning
The paper reduces violated-comparison search to agnostic learning over the corresponding Boolean concept class, enabling efficient multifairness optimization when that class is learnable.
- Complexity: The algorithm’s convergence takes a bounded number of subgradient steps independent of |C|, although constraint search must still be implemented efficiently.An efficient agnostic learner supplies sublinear-time violated-constraint search for rich comparison classes.
- Reduction: The search can be performed without additional metric samples beyond those requested by the agnostic learner.This connects the computational reduction directly to the paper’s bounded-query metric setting.
- Guarantees: An efficient agnostic learner for C yields an efficient algorithm producing metric-multifair, near-optimal predictions.The resulting guarantees are (C, d, τ)-metric multifairness and O(τ)-optimality with respect to the specified comparison family.
- Reduction: The method searches for violated multifairness constraints by converting pairwise residuals into labels for agnostic learning.A highly correlated concept identifies a comparison that guides an update toward feasibility.
- Convergence: Each detected violation of magnitude Ω(γτ) produces Ω(γ^2τ^2) progress in the duality gap.The progress bound supports convergence of the switching subgradient method.
5 Hardness of learning metric multifair hypotheses
The paper establishes that its metric-multifairness learning results are close to the best possible: sample complexity is nearly tight, and efficient high-utility learning requires learnability assumptions.
- Lower bounds: The paper shows its algorithmic results cannot be improved significantly, including a metric sample-complexity lower bound tight up to an Ω(log log(|C|)) factor.The lower-bound analysis focuses on the post-processing setting.
- Computational hardness: Efficient high-utility metric-multifair prediction requires a learnability assumption on the comparison class C.The reduction encodes Boolean concept inversion into learning multifair predictions while preserving the need for utility.
- Cryptographic hardness: Assuming one-way functions exist, no efficient algorithm computes (C, τ)-optimal metric-multifair predictions for general C, d, and constant τ.The hardness follows from a reduction connecting post-processing to distinguishing concepts from random functions.
- Computational hardness: Without learnability assumptions for C, some nontrivial running-time dependence on |C| is necessary.Under stronger cryptographic assumptions, the reduction implies an Ω(|C|^α) dependence for some constant α > 0.
6 Related works and discussion
The discussion positions metric multifairness as a flexible metric-based alternative for subpopulation fairness, while emphasizing that the current results are theoretical and leave empirical validation open.
- Related fairness notions: Metric multifairness differs from calibration- and equalized-error-rate approaches while targeting fairness across rich classes of subpopulations.The paper presents it as a flexible alternative rather than a direct generalization of those notions.
- Metric design: Combining metrics can balance prediction accuracy with corrective treatment, assigning different weights to calibration and representation goals.The paper illustrates this trade-off using credit scores and a metric favoring historically underrepresented populations.
- Metric design: Small metric samples provide a relaxed but still strong fairness guarantee, which the paper identifies as a practical advantage of metric multifairness.This advantage is stated relative to enforcing the combined metric framework when the full metric is available.
- Limitations and future work: The results are theoretical, and empirical testing across different metrics d and comparison classes C remains future work.The authors identify empirical studies across diverse domains as an open direction.
- Related theoretical work: Unlike work assuming a Mahalanobis metric or a fully known metric, this paper studies unknown, unrestricted metrics.The related-work comparison also notes that approximate metric fairness protects all sufficiently large groups and is therefore stricter than metric multifairness.
A Analysis of Algorithm 1
Algorithm 1 returns a weighted average of feasible iterates that satisfies metric multifairness, while a duality argument establishes near-optimal utility under stochastic subgradient assumptions.
- Fairness analysis: If every residual oracle has tolerance τ/5, the returned hypothesis is (C, d, τ)-metric multifair.The conclusion follows by combining oracle tolerance, convexity, and the feasible-iteration bound.
- Fairness analysis: The returned hypothesis is a convex combination of feasible iterates, where no comparison constraint appears significantly violated.The weighted average is formed over iterations in Kf.
- Utility and runtime analysis: The utility analysis uses strong duality and selects dual multipliers with a bounded duality gap to demonstrate near optimality.Feasibility and convex constraints imply Slater’s condition, so strong duality holds.
- Utility and runtime analysis: T > 302M^2B^2n log(n/δ)/τ^2 iterations suffice for the stated high-probability analysis.The guarantee is over the stochastic subgradients and uses probability at least 1 − 8δ.
A.1 Answering residual queries
Residual queries are answered by estimating expected metric distances and prediction deviations over comparison sets using metric and unlabeled samples, with uniform accuracy obtained through concentration and union bounds.
- Query cost: Each residual query can be answered after ˜O evaluations of the current hypothesis.The query procedure combines distance estimation with evaluations of f on sampled pairs.
- Prediction-deviation estimation: For a γ-large comparison class, unlabeled samples estimate every expected prediction deviation E_S[|f(x) − f(x′)|] within τ with probability at least 1 − δ.This estimate supports residual-query evaluation for all comparisons simultaneously.
- Metric-distance estimation: For a γ-large comparison class, metric samples estimate every expected distance E_S[d(x_i, x_j)] within tolerance τ with probability at least 1 − δ.The guarantee is uniform over all S ∈ C.
- Sampling requirement: Sampling log(m)/γ metric samples yields at least 1 − 1/m probability of obtaining a sample from each comparison set.A union bound over C then provides uniform tolerance with probability 1 − δ.
A.2 Answering subgradient queries
Subgradient queries for residual constraints can be implemented without metric samples because their subgradients do not depend on the metric, while stochastic pair samples provide unbiased estimates.
- Metric-free subgradients: Residual subgradients do not depend on d, so computing them requires no metric samples.A legal subgradient is obtained from partial subderivatives of the residual function.
- Stochastic implementation: A single sampled pair provides an unbiased stochastic subgradient estimate whose entries are bounded by 2 when ∥x_i∥_1 ≤ 1.This assumption permits taking M^2 = 4n for the subgradient bound.
A.3 Utility analysis of Algorithm 1
The utility proof decomposes iterations into feasible objective steps and infeasible constraint steps, then controls their duality-gap contributions using potential bounds, step sizes, and stochastic-noise estimates.
- Iteration decomposition: Feasible iterations follow the objective, while infeasible iterations follow violated comparison constraints.The analysis separates these two classes of iterations when expanding the duality gap.
- Constraint steps: For infeasible iterations, convex combinations of violated constraint subgradients suffice to guarantee progress in the duality gap.The algorithm selects corresponding dual multipliers for the comparison constraints.
- Duality-gap bounds: The duality-gap analysis tracks feasible and infeasible contributions with a potential function and separately bounds subgradient noise.The noise term is represented through e(w_k), while Lemmas 10–12 control the relevant contributions.
- Iteration threshold: For T > 302M^2B^2n log(n/δ)/τ^2 iterations, the negative T-dependent term balances the positive error terms in the duality-gap bound.This establishes the iteration threshold used in the proof of Lemma 7.
A.4 Deferred proofs from analysis of Algorithm 1
The deferred proofs bound the duality-gap contributions of feasible and infeasible iterations, establish the projected-update inequality, and control noisy subgradient terms probabilistically.
- Technical identities: The technical lemma rewrites iterate contributions using the potential function uk and the gradient-step relation.The proof connects equations (34)–(36) to Proposition 14 and wk+1 − wk = ηkgk.
- Projected updates: Lemma 13 derives a basic inequality for projected updates from the projection optimality condition.The update is wk+1 = πF(wk − ηkgk), and the resulting inequality holds for every w ∈ F.
- Feasible iterations: Feasible iterations are bounded through the loss gradient, an error term, Lemma 13, and the step-size choice ηL = τ/GM.This bounds each feasible iteration’s contribution to the duality gap.
- Infeasible iterations: Infeasible iterations are handled using a tolerance-τ/5 estimate, subgradients of RS, convex combinations over comparison sets, and ηk = τ^2/M^2.The derivation substitutes gradient and error terms, applies Lemma 13, and uses the constraint-update property.
- Noisy subgradients: Independent mean-zero subgradient errors are bounded coordinatewise with Azuma’s inequality and controlled across coordinates by union bounds.The argument assumes conditional independence given wk and an ℓ∞ bound ε on each random variable.
B Hardness for metric multifair predictions
The hardness results construct bipartite comparison instances that encode Boolean concepts in the metric. They show that metric multifairness can require many metric queries and can face computational barriers under standard cryptographic assumptions.
- Construction: The lower-bound construction splits the universe into X0 and X1 and encodes Boolean concepts through bipartite comparisons and metric values.Comparison sets are defined over X0 × X1, with labels and distances determined using a Boolean function.
- Sample complexity: Ω(log |C|) random metric samples are necessary for metric multifairness, or the algorithm’s loss approaches the no-query baseline.For n-dimensional linear functions over F2, fewer than n linearly independent queries cannot recover the concept with non-trivial accuracy, and n − k queries yield exponentially worsening loss in k.
- Computational hardness: Assuming one-way functions exist, computing optimal metric multifair predictions for arbitrary H, d, and τ requires time (log |H|)ω(1).The result follows by using a pseudorandom-function family to establish an algorithmic barrier.
- Random-function case: For a truly random labeling function, every comparison set has high expected distance, so any τ-optimal prediction set achieves loss O(τ).The stated condition is ES[d(x0, x1)] ≥ 1 − o(1) for all S ∈ H.
- Pseudorandom-function case: For a pseudorandom-function labeling, multifairness forces predictions on the positively labeled X0 points toward the high predictions on X1.The construction yields Ex0:c(x0)=1[f(x0)] ≥ 1 − 2τ, while the feasible solution has loss tied to Prx0∼X0[c(x0)=1].
- Distinguishing argument: A nontrivial loss gap distinguishes pseudorandom-function labels from truly random labels when Prx0∼X0[c(x0)=1] is bounded away from zero.This gives the hardness distinction used in the construction.