Source-linked AI summary
Multiaccuracy: Black-Box Post-Processing for Fairness in Classification
Michael P. Kim, Amirata Ghorbani, James Zou
TL;DR
The paper tackles systematic accuracy disparities affecting identifiable subgroups, including biases caused by underrepresentation or malicious discrimination. It introduces black-box multiaccuracy auditing and post-processing, with Multiaccuracy Boost using limited labeled validation data to correct subgroup errors. The method improves minority-subgroup accuracy across several applications and can also improve overall accuracy, while depending on the auditor’s ability to identify the relevant mistakes.
Problem
Prediction models can maintain high overall accuracy while performing substantially worse on minority subpopulations because of underrepresentation or intentional discrimination.
Method
Multiaccuracy Boost uses black-box access to f0, labeled validation data, and an iterative auditor-driven post-processing procedure to correct errors in identifiable subgroups.
Results
Across realistic applications, post-processing improved minority-subgroup accuracy, including cases where sensitive subgroup identifiers were not explicitly provided.
Takeaways & Limitations
The framework can mitigate systematic subgroup bias while preserving or improving overall classification accuracy and does not require explicit sensitive attributes when subgroup structure is identifiable.
Takeaways & Limitations
Multiaccuracy is limited when subgroup mistakes are too complex or information-theoretically difficult for the bounded auditor to identify.
Abstract
from arXiv · showhide
Prediction systems are successfully deployed in applications ranging from disease diagnosis, to predicting credit worthiness, to image recognition. Even when the overall accuracy is high, these systems may exhibit systematic biases that harm specific subpopulations; such biases may arise inadvertently due to underrepresentation in the data used to train a machine-learning model, or as the result of intentional malicious discrimination. We develop a rigorous framework of *multiaccuracy* auditing and post-processing to ensure accurate predictions across *identifiable subgroups*. Our algorithm, MULTIACCURACY-BOOST, works in any setting where we have black-box access to a predictor and a relatively small set of labeled data for auditing; importantly, this black-box framework allows for improved fairness and accountability of predictions, even when the predictor is minimally transparent. We prove that MULTIACCURACY-BOOST converges efficiently and show that if the initial model is accurate on an identifiable subgroup, then the post-processed model will be also. We experimentally demonstrate the effectiveness of the approach to improve the accuracy among minority subgroups in diverse applications (image classification, finance, population health). Interestingly, MULTIACCURACY-BOOST can improve subpopulation accuracy (e.g. for "black women") even when the sensitive features (e.g. "race", "gender") are not given to the algorithm explicitly.
1 Introduction
The paper addresses systematic subgroup accuracy disparities by auditing and post-processing black-box classifiers with limited labeled validation data. Multiaccuracy Boost identifies subpopulations where predictions fail and iteratively improves performance across minority groups without requiring explicit sensitive attributes.
- Motivation: Minority populations can receive substantially less accurate predictions than majority populations despite high overall model accuracy.Gender Shades found up to a 34% accuracy difference between dark-skinned females and light-skinned males.
- Motivation: Training-data rebalancing is an eventual goal, but historical and social factors can limit immediate access to representative minority data.
- Approach: The framework audits a black-box classifier using a relatively small labeled validation set drawn from a representative distribution.The goal is to test multiaccuracy, requiring predictions to be unbiased across identifiable subgroups.
- Approach: Multiaccuracy Boost uses an auditor to find subpopulations with systematic errors, then iteratively post-processes predictions until multiaccuracy is satisfied.The approach targets both inadvertent and malicious discrimination without assuming how the initial classifier was trained.
- Empirical findings: Across image gender detection, semi-synthetic medical diagnosis, and adult income prediction, post-processing improved accuracy for minority groups without explicitly supplying minority status.The experiments used standard models with good overall error but substantial subgroup biases.
- Empirical findings: Auditing effectiveness depends on the representation used for audit data, with unsupervised autoencoder embeddings outperforming the predictor network’s internal representation in image recognition.
2 Setting and multiaccuracy
Multiaccuracy formalizes subgroup fairness as low prediction bias across a chosen class of identifiable tests. Its auditing procedure learns residual-correlated functions from limited validation data, while richer test classes yield stronger accuracy guarantees on identifiable subpopulations.
- Setting: The setting assumes black-box access to an initial model f0 and a small labeled validation sample from distribution D.D should sufficiently represent important subpopulations and serves as the evaluation distribution for the final model.
- Setting: The framework makes no assumptions about how f0 was trained, covering both inadvertently biased and adversarially discriminatory classifiers.
- Multiaccuracy: Multiaccuracy targets low classification error not only overall but also across subpopulations of the input space.
- Multiaccuracy: For a test class C, (C, α)-multiaccuracy requires predictions to appear unbiased according to every statistical test in C.When C contains characteristic functions for subsets, each subset’s predictions are at most α-biased.
- Guarantees: If C is learnable, multiaccuracy guarantees accuracy on efficiently identifiable subpopulations rather than on every possible statistical test.Requiring all tests would require learning the label function exactly, which is information-theoretically impossible from a small sample.
- Guarantees: For a subpopulation S of density at least γ, if some test in C approximates its labels within τ, then erS(f; y) ≤ 2 · (α + τ)/γ.Thus, multiaccuracy converts residual correlation captured by C into a subgroup classification-error guarantee.
- Auditing: Auditing learns a function correlated with the residual f − y using a small sample from D.Experiments use ridge regression and decision-tree regression auditors to identify underperforming subpopulations and summarize image-model mistakes.
3 Post-processing for multiaccuracy
Multiaccuracy Boost post-processes a black-box classifier by auditing residual errors on identifiable subpopulations and iteratively updating predictions. The method provides convergence, sample-complexity, and do-no-harm guarantees, while highlighting overfitting and representation choices as practical constraints.
- Algorithm: Multiaccuracy Boost uses an auditor to identify subpopulations with systematic residual errors, then applies multiplicative-weights updates until the classifier passes (A, α)-multiaccuracy auditing.The procedure partitions inputs using f0 and iteratively updates predictions on audited sets.
- Practical considerations: Auditing expressive classes can overfit the small validation sample, so the class of tests and iteration count must balance signal discovery against generalization.Empirically, post-processing improves generalization error before overfitting begins.
- Formal guarantees: The algorithm converges to a (C, α)-multiaccurate hypothesis when the auditor agnostically learns test class C, with iteration and sample requirements governed by α, δ, and d(C).The sample complexity depends on the dimension of C and uniform convergence over the auditor’s test class.
- Formal guarantees: The do-no-harm guarantee ensures that audited subpopulations do not experience a significant increase in classification error after post-processing.The formal theorem applies when the subpopulation has probability at least γ and α ≤ βγ.
- Formal guarantees: With derivative-based auditing, Multiaccuracy Boost converges in O(L · log(ℓD(f0; y)/α)) iterations under the stated smoothness conditions.The derivative learner targets a smoothed partial derivative of cross-entropy loss, yielding logarithmic dependence on 1/α.
4 Experimental Evaluation
Across image classification, adult income prediction, and semi-synthetic disease prediction, Multiaccuracy Boost reduced minority-subgroup error using black-box access and small audit sets. Its effectiveness depended on the auditing representation, while auditor outputs also helped localize systematic bias.
- Experimental scope: Multiaccuracy Boost improved minority-subgroup accuracy across gender detection, adult income prediction, and semi-synthetic disease prediction tasks.The experiments used standard initial models with good overall accuracy but substantial subgroup bias.
- Gender detection: 23.1% female error versus 0.7% male error and 10.2% black error versus 5.1% non-black error exposed substantial initial disparities in LFW+a gender classification.After post-processing, minority-subpopulation classification error was substantially reduced, and convergence required 7 iterations.
- Comparison with retraining: Multiaccuracy Boost achieved comparable or improved error rates to retraining while requiring only black-box access and no additional demographic information.The retraining baseline required white-box access to the initial network and used the audit set to retrain its last two layers.
- Data efficiency: When audit data were especially scarce, Multiaccuracy Boost could outperform white-box retraining in overall accuracy and accuracy for initially biased subgroups.Figure 1 compares the accuracy difference between post-processing and retraining as audit-set size decreases.
- Representation matters: The unsupervised VAE representation yielded the best reported representation results, although final- and second-to-last-layer representations were competitive and sometimes better for particular subpopulations.These findings indicate that effectiveness depends on the auditing representation but may be robust across sufficiently expressive encodings.
- Auditing as diagnosis: Auditor activations provided an interpretable diagnostic: after one boost step, the identified bias narrowed from women generally to dark-skinned women specifically.The first audit also associated low activation with men in suits, suggesting suits were predictive of being a man for the original classifier.
- Additional case studies: Against subgroup-specific neural networks, multiaccuracy post-processing achieved better aggregate and subgroup accuracy without requiring explicit gender or race features.The comparison also illustrates data-efficient improvement of a black-box predictor when subgroup-specific training is infeasible or under-sampled.
- Additional case studies: In the UK Biobank semi-synthetic task, Multiaccuracy Boost significantly lowered classification error for the old-female population, which had the least representation in D0.The auditor used 4,000 individuals without gender or age features.
5 Discussion
The paper positions multiaccuracy as a black-box fairness framework for improving accuracy across identifiable subpopulations without requiring explicit subgroup identifiers. It extends prior work with post-processing guarantees that improve disadvantaged groups while preserving accuracy for groups already served well.
- Relation to prior work: The approach extends multiaccuracy from regression to binary classification and differs from white-box fairness training by post-processing an unrestricted initial model.Its technical perspective is related to boosting but operates with limited data and simple auditor classes.
- Guarantees: Multiaccuracy Boost adds a do-no-harm guarantee: groups with initially small classification error retain small error after post-processing.This distinguishes the approach from fairness methods that treat utility as necessarily constrained by parity requirements.
- Framework: Multiaccuracy protects overlapping identifiable subpopulations without requiring explicit knowledge of which groups are vulnerable.Auditors identify subpopulations where the predictor systematically errs.
- Framework: Multiaccuracy post-processes any initial predictor using only black-box access and a small labeled validation set.The validation distribution is intended to represent the population on which final accuracy is evaluated.
- Limitations: The method is limited when subgroup errors are too complex or information-theoretically difficult for the bounded auditor to identify.The authors report that such subpopulations were efficiently identifiable in many realistic settings they studied.
- Empirical findings: Experiments show improved accuracy for underrepresented groups, including cases where sensitive attributes are withheld from the auditor, and often improved overall accuracy as well.The paper reports applications in image classification, medical diagnosis, and adult income prediction.
A Multiaccuracy and classification error
This section connects multiaccuracy to subgroup classification error. It shows that multiaccuracy bounds error on a sufficiently represented subgroup when that subgroup’s labels are approximable by the auditor’s concept class.
- Subgroup error bound: If a subgroup has probability at least γ and its labels are approximated within τ by a concept in C, (C, α)-multiaccuracy bounds its error by 2(α + τ)/γ.The bound separates auditing accuracy α, label-approximation error τ, and subgroup prevalence γ.
- Proof strategy: The proof decomposes a subgroup into correctly and incorrectly classified regions and uses the auditor’s correlation constraint to bound their contributions.Misclassified points contribute at least 1/2 to the relevant expectation.
- Algorithmic guarantee: Theorem 3 applies the subgroup-error analysis to the output of Algorithm 1 when the auditor tests a subgroup characteristic function and its negation.The theorem assumes α ≤ βγ and gives a classification-error bound on the subgroup.
- Proof strategy: Subgroup error is expressed as a convex combination of the errors on its two prediction-defined partitions.The corresponding baseline error is decomposed using the same partition weights.
B Analysis of Algorithm 1
The analysis establishes that Algorithm 1 converges to a multiaccurate hypothesis under an agnostic-learning assumption. The result provides a high-probability convergence guarantee based on the auditor’s concept-class complexity and the target accuracy.
- Convergence: Algorithm 1 converges to a (C, α)-multiaccurate hypothesis in T iterations when the auditor agnostically learns C.The theorem uses learning rate η = O(α).
- Guarantee: The convergence guarantee holds with probability at least 1 − δ over the random samples.The analysis also studies the sample complexity and running time of the algorithm.
B.1 Sample complexity
The sample-complexity analysis uses a generic uniform-convergence argument based on the dimension and covering number of the auditor’s function class. The resulting bounds are not optimized for structure in the class.
- B.1 Sample complexity: The analysis assumes away sample-complexity issues by working with the dimension of the function class C.The proof outline uses metric entropy and a standard uniform-convergence argument.
- B.1 Sample complexity: An ε-covering number N(ε, C, ∥·∥1) supports concentration and uniform control over empirical estimates for every c ∈ C.McDiarmid’s inequality provides concentration, followed by a covering argument and a union bound across iterations.
- B.1 Sample complexity: The generic analysis may yield loose bounds because more sophisticated arguments could exploit structure specific to C.The passage explicitly notes that the exact bound is not optimized.
B.2 Convergence analysis
Multiaccuracy Boost analyzes each multiplicative-weights update through expected cross-entropy loss. Accurate statistical-query estimates ensure measurable progress, so the process reaches a multiaccurate hypothesis efficiently.
- B.2 Convergence analysis: Each update decreases expected cross-entropy loss by a positive amount, and the loss’s lower bound yields convergence.The argument combines per-iteration progress with an upper bound on the initial loss.
- B.2 Convergence analysis: Given α/4-accurate statistical queries, Algorithm 1 converges to a (C, α)-multiaccurate hypothesis in T iterations.The supplied passage states the convergence bound but truncates its explicit expression.
- B.2 Convergence analysis: The multiplicative-weights update links local changes in pointwise cross-entropy to the inner product between the auditor’s update c_t and f − y.This inner product represents global progress in the objective.
- B.2 Convergence analysis: With α/4-accurate statistical queries and updates triggered at estimated correlation at least 3α/4, the loss decreases by at least α^2/16.The update uses η = α/4.
C Linear convergence from gradient learning
Learning cross-entropy gradients gives a specialized auditor for Multiaccuracy Boost. Under bounded-norm assumptions, the resulting procedure converges linearly, with iteration complexity logarithmic in the initial loss and target accuracy.
- C Linear convergence from gradient learning: The proof bounds progress using accurate norm and inner-product estimates, gradient-loss correlation, convexity, and the bound ∥h_f∥_2 ≤ L · ℓ_D(f; y).These conditions connect the auditor’s gradient approximation to multiplicative-weights progress.
- C Linear convergence from gradient learning: The gradient-learning auditor is designed so that Algorithm 1 converges linearly.The auditor returns a partial-derivative approximation when cross-entropy is not already sufficiently small.
- C Linear convergence from gradient learning: Algorithm 1 converges in T = O(L · log(ℓ_D(f_0; y)/α)) iterations under the stated class and auditor assumptions.The proposition assumes α, B, L > 0 and C ⊆ [−B, B]^X.
- C Linear convergence from gradient learning: After O(L · log(ℓ_D(f_0; y)/α)) iterations, cross-entropy drops below α.The update step uses η = 1/(8L).