PaperlayerView exact revision on arXiv

Source-linked AI summary

A Geometric Theory of Robust Fairness Audits

Binita Maity

arXiv:2608.24818v1cs.LG

TL;DR

Neighborhood-based fairness audits may change when perturbations alter nearest-neighbor relationships, even when model predictions stay fixed. The paper develops a geometric framework linking perturbations to neighborhood replacement and audit deviation, then validates it with Audit Volatility experiments showing that neighborhood geometry governs audit stability.

  • Problem

    The robustness of fairness auditing itself remains largely unexplored, despite audits depending on neighborhoods that can change under feature perturbations.

  • Method

    The paper models local audits as Lipschitz aggregations of pairwise fairness evaluations and derives deterministic, probabilistic, and expected guarantees under bounded perturbations.

  • Results

    Experiments validate the theoretical predictions and show that neighborhood replacement explains observed audit instability across benchmark datasets.

  • Takeaways & Limitations

    Neighborhood geometry provides a principled basis for analyzing and designing robust neighborhood-based fairness audits.

  • Takeaways & Limitations

    The analysis assumes a fixed prediction model, so perturbations affect fairness assessments only through neighborhood geometry.

Abstract

from arXiv · show

Neighborhood-based fairness audits evaluate individual fairness by comparing predictions among similar individuals in feature space. Despite their widespread use, little is known about the robustness of the auditing procedure itself. Because these audits rely on nearest neighbor relationships, small perturbations in feature space can alter local neighborhoods and produce different fairness assessments even when model predictions remain unchanged. We develop a geometric framework for analyzing the robustness of neighborhood-based fairness audits under bounded perturbations. Our analysis establishes sufficient conditions for neighborhood invariance, quantifies how neighborhood replacement propagates to audit instability, and introduces audit volatility, a measure of the expected sensitivity of fairness audits under repeated perturbations. Experiments on benchmark datasets support the theoretical analysis and show that the proposed framework explains the observed stability of neighborhood-based fairness audits.

1 Introduction

Neighborhood-based fairness audits can become unstable when feature perturbations change nearest-neighbor relationships, even if predictions remain fixed. The paper introduces a geometric framework and Audit Volatility to analyze and measure this robustness.

  • Motivation: Neighborhood-based audits can produce different fairness assessments when feature perturbations alter local neighborhoods despite unchanged model predictions.This makes it difficult to distinguish genuine unfairness from instability caused by the auditing procedure.
  • Research gap: Existing robustness research mainly studies prediction models, leaving the stability of fairness audits under feature perturbations largely unexplored.The paper frames audit robustness as a measurement problem distinct from robust model prediction.
  • Approach: The framework models neighborhood-based audits as Lipschitz aggregations of pairwise fairness evaluations over local neighborhoods.This abstraction encompasses a broad class of existing auditing methods.
  • Approach: Deterministic, probabilistic, and expected guarantees connect bounded feature perturbations to neighborhood replacement and audit deviation.The analysis identifies neighborhood replacement as the mechanism governing audit instability.
  • Validation: Audit Volatility quantifies expected audit sensitivity under repeated perturbations and is validated experimentally on benchmark datasets.The experiments support the proposed theory and its robustness analysis.

2 Related Work

Related work establishes individual fairness through similarity-based comparisons and commonly operationalizes it with neighborhood audits. The paper distinguishes its focus from prior robustness studies of prediction models and connects it to measurement reliability.

  • Individual Fairness and Local Fairness Audits: Individual fairness requires similar individuals to receive similar decisions, but application-specific similarity metrics are rarely available in practice.Consequently, fairness is often evaluated through post hoc neighborhood-based audits.
  • Individual Fairness and Local Fairness Audits: Nearest-neighbor consistency measures and FaiTH aggregate pairwise prediction comparisons over local neighborhoods, while toolkits have popularized these audits.Despite differing pairwise functions and aggregation rules, these methods rely on nearest-neighbor relationships.
  • Robustness in Fair Machine Learning: Prior fair-machine-learning robustness work primarily stabilizes predictive models under perturbations rather than the auditing procedure itself.This paper instead assumes predictions remain fixed and studies changes in audit neighborhoods.
  • Robust Statistics and Measurement Reliability: The analysis differs from classical robust statistics by focusing on instability from changes in neighborhood composition rather than contaminated observations or outliers.Robust aggregation techniques nevertheless motivate related aggregation mechanisms.
  • Robust Statistics and Measurement Reliability: The paper treats fairness as a measurement problem and introduces a theoretical framework for audit stability under feature-space perturbations.It identifies neighborhood replacement as the fundamental source of audit instability and introduces Audit Volatility as a robustness measure.

3 Framework for Neighborhood-based Fairness Audits

The framework represents neighborhood-based fairness audits as pairwise fairness evaluations aggregated over nearest neighbors. Lipschitz aggregation separates geometric neighborhood changes from aggregation sensitivity, enabling robustness analysis across auditing methods.

  • Unified Audit Abstraction: Neighborhood-based audits share a computational structure: they aggregate pairwise fairness scores over local neighborhoods.The framework formalizes this common structure across methods with different pairwise functions and aggregation rules.
  • Unified Audit Abstraction: Each local audit combines a pairwise fairness function with an aggregation operator that summarizes scores from an individual’s k-nearest neighbors.This separates pairwise fairness evaluation from aggregation.
  • Unified Audit Abstraction: The dataset-level audit collects the local audit scores for all individuals, providing a unified object for robustness analysis.The abstraction cleanly separates pairwise fairness from aggregation.
  • Lipschitz Aggregation Operators: Robustness depends on the aggregation operator’s sensitivity, which is modeled through a Lipschitz continuity property.The Lipschitz constant quantifies how input-score perturbations affect the aggregated audit.
  • Lipschitz Aggregation Operators: Arithmetic means, weighted means, trimmed means, Winsorized means, and several robust M-estimators fall within the framework under stated regularity conditions.For the arithmetic mean, the Lipschitz constant is LΦ = 1/k.
  • Examples: Consistency-based audits and FaiTH instantiate the framework, while the theory extends to other audits using Lipschitz aggregation.The framework therefore applies uniformly across these example auditing approaches.

4 Stability of Local Fairness Audits

The framework separates neighborhood stability from audit stability: geometric margins determine whether neighborhoods survive perturbations, while neighborhood replacement controls resulting audit deviation and volatility.

  • Framework: The audit analysis assumes fixed model predictions, so perturbations change fairness scores only through neighborhood geometry.The framework models audits on perturbed datasets by comparing local and dataset-level scores before and after neighborhood changes.
  • Geometric Stability: A local separation margin γ_i measures the gap between the farthest neighbor and nearest non-neighbor, with larger margins indicating greater expected robustness.The margin is defined as γ_i = r_min(i) − r_max(i).
  • Geometric Stability: Pairwise distances change by at most 2ε, so local separation margins decrease by at most 4ε under ε-bounded perturbations.The bound follows because neighbor distances may increase by 2ε while non-neighbor distances may decrease by 2ε.
  • Geometric Stability: If γ_i > 4ε, every original neighbor remains closer than every original non-neighbor, preserving the local neighborhood.This deterministic condition provides a sufficient geometric certificate for neighborhood invariance.
  • Probabilistic Robustness: Under random perturbations, neighborhood changes can occur only when the perturbation radius R reaches γ_i/4, linking stability probability to geometry and perturbation uncertainty.The probabilistic formulation separates the dataset-dependent margin γ_i from the stochastic radius R and supports concentration-based guarantees.
  • Audit Stability and Volatility: Audit deviation is governed jointly by aggregation sensitivity and neighborhood replacement, while audit volatility measures expected variation across perturbation realizations.The resulting robustness pipeline connects perturbations to neighborhood replacement and then bounds audit deviation and expected volatility.

5 Experimental Evaluation

Experiments test whether bounded feature perturbations affect neighborhood geometry and fairness-audit robustness as predicted. Across datasets and perturbation models, neighborhood replacement, aggregation sensitivity, and local separation explain audit volatility.

  • Experimental setup: The experiments evaluate geometric predictions, neighborhood replacement, aggregation effects, and dataset geometry on Adult Income, Bank Marketing, and COMPAS.Unless otherwise stated, audits use Euclidean k-nearest neighborhoods with k = 10; reported values average 30 Monte Carlo trials.
  • Neighborhood preservation: Neighborhood Preservation Rate decreases monotonically as perturbation radius increases, with Adult and Bank more stable than COMPAS because of larger local separation margins.These results support Theorem 3 and identify local separation margin as a certificate for neighborhood preservation.
  • Neighborhood replacement: Expected neighborhood replacement increases monotonically with perturbation radius, and COMPAS exhibits substantially greater replacement than Adult and Bank.The difference reflects smaller local separation margins in COMPAS.
  • Audit volatility: Across four perturbation models, audit volatility closely tracks neighborhood replacement, supporting the distribution-independent characterization of Theorem 8.For arithmetic mean aggregation, volatility grows with perturbation magnitude while remaining below the predicted upper bound without observed violations.
  • Aggregation robustness: Trimmed mean and median aggregators consistently yield lower audit volatility than worst-neighbor aggregation, confirming aggregation sensitivity as a robustness determinant.The comparison evaluates arithmetic mean, 20% trimmed mean, median, and worst-neighbor aggregation under identical perturbations.
  • Dataset geometry: Larger local separation margins produce smaller neighborhood replacement and lower audit volatility, which approaches zero for well-separated neighborhoods.This supports the claim that local separation margin is the primary geometric factor governing audit robustness.

6 Conclusion

The paper presents a geometric framework for robustness of neighborhood-based fairness audits and connects bounded feature perturbations to neighborhood replacement and audit deviation. Its conclusion identifies neighborhood replacement and local separation as central to audit stability, with experiments validating the theoretical predictions.

  • 6 Conclusion: The framework models local fairness audits as Lipschitz aggregations of pairwise fairness evaluations and establishes deterministic, probabilistic, and expected stability guarantees.These guarantees relate feature-space perturbations to neighborhood replacement and audit deviation.
  • 6 Conclusion: Audit volatility is introduced as a quantitative measure of audit robustness, while local separation is identified as a geometric certificate for neighborhood preservation.The framework is intended to analyze robustness under bounded feature-space perturbations.
  • 6 Conclusion: The analysis separates feature-space perturbations from the auditing procedure by holding model predictions fixed and tracing effects through geometric changes.This addresses the question of how small perturbations of the underlying feature space affect local fairness audits.
  • 6 Conclusion: The theoretical development bounds pairwise-distance changes, characterizes separation-margin reduction, and derives a sufficient condition for neighborhood invariance under bounded perturbations.The condition is developed through the geometric perturbation model and local separation notion.
  • 6 Conclusion: The proof analysis shows pairwise distances change by at most 2ε, while the local separation margin can decrease by at most 4ε.Neighborhood ordering is preserved when the original separation margin exceeds the worst-case reduction.

A.2 Proof of lemma 2.

The proof establishes that perturbations can reduce local separation by at most 4ε and uses a tight collinear construction to show the bound is attainable. Therefore, margins exceeding 4ε preserve neighbor ordering.

  • A.2 Proof of lemma 2.: The proof bounds margin reduction by combining the worst-case movement of the nearest non-neighbor with the worst-case movement of the farthest neighbor.The argument takes a minimum over points outside the neighborhood and a maximum over original neighbors.
  • A.2 Proof of lemma 2.: A three-point collinear construction with k = 1 attains the 4ε reduction by moving the neighbor away, the non-neighbor toward, and the center toward the non-neighbor.This demonstrates that the bound is tight.
  • A.2 Proof of lemma 2.: When the original separation margin exceeds 4ε, every original neighbor remains closer than every original non-neighbor, preserving the neighborhood.The result follows because the margin remains positive after the worst-case reduction.

A.3 Proof of Theorem 3.

Theorem 3 uses the local separation margin to guarantee neighborhood preservation under bounded perturbations, establishing the geometric basis for audit robustness. Subsequent results connect neighborhood changes to audit deviations and probabilistic stability.

  • Deterministic neighborhood preservation: Theorem 3 guarantees preservation of the k-nearest-neighbor set when the local separation margin exceeds perturbation-induced distance distortion.Every original neighbor remains strictly closer than every original non-neighbor after perturbation.
  • Robustness pipeline: The framework therefore proceeds from bounded perturbations to neighborhood replacement and then to bounded audit deviation.Exact audit stability holds when neighborhoods are preserved, while replacement controls instability otherwise.
  • Deterministic neighborhood preservation: The stability threshold γ_i > 4ε is essentially optimal because the separation margin can decrease by exactly 4ε under an admissible perturbation.Thus, no smaller universal constant supports uniform deterministic preservation guarantees for this perturbation model.
  • Probabilistic robustness: Corollary 4 separates probabilistic neighborhood robustness into dataset geometry, through γ_i, and perturbation uncertainty, through the random radius R.Tail or concentration bounds for R directly yield probabilistic neighborhood-preservation guarantees.
  • Audit stability: Audit changes arise only through neighborhood replacement when the prediction model remains fixed, because pairwise scores for common neighbors are unchanged.The resulting deviation is quantified by the number of replaced neighbors and the aggregation operator’s sensitivity.
  • Audit stability: Theorem 6 bounds audit deviation using the aggregation operator’s Lipschitz constant and the size of the neighborhood replacement set.This creates a perturbation-independent operator bound that becomes geometric when replacement is linked to feature-space perturbations.

A.9 Proof of Corollary 7

The arithmetic-mean audit is analyzed as a Lipschitz aggregation operator, yielding a direct specialization of the general audit-stability theorem. The resulting robustness bound inherits dependence on neighborhood replacement.

  • Arithmetic-mean aggregation: The arithmetic mean is 1/k-Lipschitz with respect to the ℓ1 norm.This follows by bounding the absolute difference between means by the average ℓ1 difference between their input vectors.
  • Arithmetic-mean aggregation: Substituting the arithmetic mean’s Lipschitz constant into Theorem 6 yields its corresponding audit-stability bound.The specialization links arithmetic-mean audit deviation to the replacement structure quantified by the general theorem.
  • Robustness decomposition: The proof decomposes audit robustness into aggregation sensitivity and geometric neighborhood replacement.The operator contributes through its Lipschitz constant, while perturbations contribute through the changed neighbor set.

A.11 Proof of Theorem 8

Theorem 8 extends single-perturbation audit bounds to repeated stochastic perturbations by bounding audit volatility through expected neighborhood replacement. The framework separates aggregation sensitivity from perturbation-induced geometric change.

  • Audit volatility: Theorem 8 bounds audit volatility in terms of the expected amount of neighborhood replacement under stochastic perturbations.It applies the deterministic audit-stability bound inside the expectation.
  • Audit volatility: Audit volatility decreases when either the aggregation operator has a smaller Lipschitz constant or the perturbation model induces less neighborhood replacement.These are the two complementary factors identified by Theorem 8.
  • Robustness framework: The complete framework assigns distinct roles to local separation margin, neighborhood replacement, and expected neighborhood replacement.They govern probabilistic preservation, single-audit deviation, and volatility under stochastic perturbations, respectively.

B Appendix B: Additional Experimental Results

Additional experiments validate Theorem 8 at the largest tested perturbation radius. Across all three datasets, observed audit volatility stays below the theoretical upper bound without per-individual violations.

  • Additional validation: ϵ = 0.20 is the largest perturbation radius used for the additional empirical validation of Theorem 8.The validation uses arithmetic-mean aggregation with k = 10 and M = 1.
  • Additional validation: Across all three datasets, observed audit volatility remains substantially below the corresponding theoretical upper bound.No per-individual violations are observed, although the bound is described as conservative.
  • Additional validation: The experiments support the dependence of audit volatility on expected neighborhood replacement.The results are presented as empirical support for Theorem 8 and the proposed geometric framework.
Loading 2608.24818v1…