[Paper] Auditing Fairness under Model Updates: Fundamental Complexity and Property-Preserving Updates

Source: arXiv - 2601.05909v1

Overview

Machine‑learning models that power everything from loan approvals to content recommendation are increasingly scrutinized for bias. But in production, models are rarely static – owners continuously retrain or tweak them to adapt to market shifts, regulation changes, or new data. This paper asks: what fairness guarantees can we still audit when the model is allowed to evolve, provided the updates preserve the very property we care about (e.g., statistical parity)? The authors develop a theoretical framework that quantifies how “hard” it is to audit fairness under such strategic updates and propose practical, sample‑efficient algorithms for doing so.

Key Contributions

• Formal definition of property‑preserving updates – a generic way to model arbitrary model changes that keep a chosen fairness metric invariant.
• Information‑theoretic characterization of the minimal labeled data needed to audit fairness after updates, introducing the SP‑dimension, a new combinatorial complexity measure analogous to VC‑dimension but for strategic updates.
• PAC‑style auditing framework built around an Empirical Property Optimization (EPO) oracle, which reduces auditing to a well‑studied optimization problem.
• Distribution‑free auditing bounds for statistical parity, showing that the required sample size scales with the SP‑dimension rather than the size of the underlying hypothesis class.
• Extension to other audit objectives (prediction error, robust risk), demonstrating the versatility of the approach.

Methodology

1. Model the update process:

   • Start with a pre‑audit hypothesis class (\mathcal{H}).
   • Allow an adversarial (or strategic) update that maps any hypothesis (h \in \mathcal{H}) to a new hypothesis (h’ \in \mathcal{H}’).
   • The update is property‑preserving if the fairness metric (e.g., statistical parity) evaluated on the data distribution stays unchanged: (\phi(h) = \phi(h’)).

2. Define the SP‑dimension:

   • For a given fairness property (\phi), the SP‑dimension counts the largest set of examples that can be shattered by updates while still preserving (\phi).
   • Intuitively, a higher SP‑dimension means the update space is richer and auditing becomes harder.

3. Empirical Property Optimization (EPO) oracle:

   • Given a labeled sample, the oracle finds a hypothesis in the updated class that maximizes (or minimizes) the fairness metric of interest.
   • By repeatedly calling the oracle on fresh samples, the auditor can estimate the true fairness value with high confidence (PAC guarantee).

4. Sample‑complexity analysis:

   • Using concentration inequalities and the SP‑dimension, the authors derive bounds on the number of labeled examples needed to guarantee that the estimated fairness is within (\epsilon) of the true value with probability (1-\delta).

5. Generalization to other metrics:

   • The same pipeline works for any property that can be expressed as an expectation over the data (e.g., error rate, robust risk), simply by swapping the objective inside the EPO oracle.

Results & Findings

• Distribution‑free bound: For statistical parity, the required labeled sample size is
  [ O!\left(\frac{\text{SP‑dim} + \log(1/\delta)}{\epsilon^{2}}\right), ]
  matching classic PAC bounds but with SP‑dim replacing VC‑dim.
• Tightness: The authors prove a matching lower bound, showing the SP‑dimension is not just a convenient artifact—it truly captures the intrinsic difficulty of auditing under property‑preserving updates.
• Algorithmic feasibility: When the underlying hypothesis class admits an efficient ERM (e.g., linear models, decision trees), the EPO oracle can be implemented with off‑the‑shelf solvers, making the audit procedure practical.
• Beyond fairness: Extending the analysis to prediction error yields analogous sample‑complexity results, confirming that the framework is a general‑purpose auditing toolkit.

Practical Implications

• Continuous compliance pipelines: Companies can embed the EPO‑based audit as a lightweight check after each model retraining cycle, guaranteeing that fairness metrics remain within acceptable bounds without re‑collecting massive labeled datasets.
• Regulatory readiness: Regulators often require evidence that a model’s bias does not worsen over time. The SP‑dimension provides a concrete, provable metric that auditors can cite when certifying compliance.
• Strategic model updates: Product teams can design “fairness‑preserving” update rules (e.g., fine‑tuning on new data, adding features) that are provably safe under the SP‑dimension analysis, reducing the risk of accidental bias drift.
• Tooling integration: Because the EPO oracle reduces to standard empirical risk minimization with a modified loss, existing ML libraries (scikit‑learn, PyTorch Lightning, TensorFlow) can be leveraged, lowering engineering overhead.
• Cross‑domain applicability: The same methodology can be applied to audit robustness (adversarial risk), privacy leakage, or any measurable property that must stay stable across model versions.

Limitations & Future Work

• Assumption of property preservation: The framework presumes the update intentionally keeps the fairness metric unchanged. In practice, updates may unintentionally violate this, requiring detection mechanisms beyond the current scope.
• Computational cost of the EPO oracle: While tractable for simple hypothesis classes, the oracle may become expensive for deep neural networks or highly non‑convex models, limiting scalability.
• Label dependence: The sample‑complexity bounds rely on access to labeled data for the protected attribute and outcome, which can be costly or privacy‑sensitive in real deployments.
• Extension to intersectional fairness: The paper focuses on binary group fairness (statistical parity). Extending the SP‑dimension analysis to multi‑group or intersectional settings remains an open challenge.

Future research directions include designing adaptive EPO oracles for deep models, exploring unsupervised or weakly‑supervised auditing under updates, and integrating detection of property‑violating updates into the audit loop.

---

Bottom line: This work provides a rigorous yet implementable blueprint for auditing fairness (and other properties) in the wild, where models evolve continuously. By quantifying the intrinsic difficulty of such audits through the SP‑dimension and offering a practical PAC‑style algorithm, it bridges the gap between theoretical fairness guarantees and the day‑to‑day realities of production ML systems.

Authors

• Ayoub Ajarra
• Debabrota Basu

Paper Information

• arXiv ID: 2601.05909v1
• Categories: cs.LG, cs.AI, cs.CY, stat.ML
• Published: January 9, 2026
• PDF: Download PDF